Query Optimisation | Computer Science

$\mathrm{SQL} \xrightarrow{\mathrm{parse} \mathrm{AST} \xrightarrow{\mathrm{rewrite} \mathrm{Logical} plan \xrightarrow{\mathrm{optimise} \mathrm{Physical} plan \xrightarrow{\mathrm{execute} \mathrm{Result}}}}}$

The optimiser estimates the cost of alternative execution plans and chooses the cheapest.

Cost model. Cost = I/O cost (disk page accesses) + CPU cost. For disk-bound queries, I/O Dominates.

Catalog statistics: Table cardinality ($n$), attribute value cardinality, number of distinct Values, histogram of value distribution, index information.

Selectivity estimation. For a predicate $\sigma_{A = v}(R)$The selectivity is approximately $1 / V(A, R)$ where $V(A, R)$ is the number of distinct values of $A$ in $R$.

Nested-loop join. For each tuple in $R$Scan all of $S$.

$\mathrm{Cost} = n_R \cdot n_S \mathrm{ page} accesses (worst case)$

If one relation fits in memory, buffer it and scan the other: cost = $n_R + n_S$.

Block nested-loop join. Use $B$ buffer pages. Load blocks of $R$ into $B - 2$ buffers, scan $S$ With the remaining buffer.

$\mathrm{Cost} = n_R + \lceil n_R / (B - 2) \rceil \cdot n_S$

Sort-merge join. Sort both relations on the join attribute, then merge.

$\mathrm{Cost} = 2 \cdot n_R \cdot \log_{B-1}(n_R) + 2 \cdot n_S \cdot \log_{B-1}(n_S) + n_R + n_S$

Efficient for large relations, especially when both are already sorted.

Hash join. Build a hash table on the smaller relation (build phase), then probe with the larger (probe phase).

$\mathrm{Cost} = 3 \cdot (n_R + n_S) \mathrm{ (if build relation fits in memory)}$

Best for equi-joins when one relation fits in memory.

Index nested-loop join. For each tuple in $R$Use an index on $S$ to find matching tuples.

$\mathrm{Cost} = n_R \cdot (\mathrm{index} lookup cost)$

Efficient if $S$ has an index on the join attribute and $n_R$ is small.

The optimiser explores the space of equivalent logical plans and physical implementations. For $k$ Joins, the number of join orderings is $O(k!)$ (left-deep trees) or $O(3^k)$ (bushy trees). Practical optimisers use dynamic programming with pruning.

Heuristic transformations:

• Push selections down (reduce intermediate result sizes).
• Push projections down (reduce column widths).
• Convert cross products to joins when possible.
• Reorder joins based on estimated cardinalities.

• Assuming the cheapest plan for one query is best for all. The optimal join order depends critically on selectivity estimates. Outdated statistics produce poor plans.
• Forgetting that selectivity estimates are just estimates. Uniform distribution assumptions are often wrong. Histograms and sampling improve accuracy but never guarantee correctness.
• Confusing left-deep and bushy trees for the same join. Left-deep trees pipeline well but may miss optimal orderings. Bushy trees can exploit more parallelism.
• Thinking index nested-loop join always beats full table scan. If the outer relation is large and the index has poor selectivity (many matching tuples per key), scanning may be cheaper.

Problem. Consider $R$ with 1000 pages and $S$ with 500 pages, 100 buffer pages ($B = 100$). Compare the cost of block nested-loop join vs sort-merge join.

Solution. Block nested-loop: $\mathrm{Cost} = 1000 + \lceil 1000/(100-2)\rceil \cdot 500 = 1000 + 11 \cdot 500 = 6500$ pages.

Sort-merge: sorting $R$ costs $2 \cdot 1000 \cdot \log_{99}(1000) \approx 2 \cdot 1000 \cdot 2 = 4000$. Sorting $S$: $2 \cdot 500 \cdot \log_{99}(500) \approx 2 \cdot 500 \cdot 2 = 2000$. Merge: $1000 + 500 = 1500$. Total: $4000 + 2000 + 1500 = 7500$ pages.

Block nested-loop is cheaper in this case (6500 vs 7500). $\blacksquare$

Problem. Estimate selectivity for $\sigma_{A > 100 \land B = 5}(R)$ given $V(A,R) = 50$, $\min(A)=0$, $\max(A)=200$, $V(B,R) = 20$.

Solution. For $A > 100$: selectivity $\approx (200-100)/(200-0) = 0.5$. For $B = 5$: selectivity $\approx 1/20 = 0.05$. Assuming independence: combined selectivity $= 0.5 \times 0.05 = 0.025$ (2.5% of rows). $\blacksquare$

• Big data systems: Query optimisers in Spark SQL, Hive, and Presto use cost-based optimisation adapted for distributed execution, factoring in network transfer costs.
• NoSQL databases: Document stores like MongoDB have query optimisers that select between collection scans and index usage, with query planners showing execution statistics.
• Data warehousing: Columnar databases (Snowflake, Redshift) use optimisers that account for column pruning, vectorised execution, and zone maps for min-max pruning.
• Stream processing: Optimisers for streaming SQL (Flink, Kafka Streams) extend cost models to handle windowed aggregations, state size, and watermark propagation.

flowchart TD
    A[7_Query Optimisation] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

Query optimisation is the difference between a librarian who checks every shelf and one who uses the card catalogue. The query planner examines your SQL and figures out the fastest way to execute it — which index to use, which table to scan first, how to join efficiently. Execution plans are the map of this journey, showing each step and its estimated cost. Without optimisation, a simple join could scan billions of rows; with it, the database finds the answer in milliseconds. The optimizer uses statistics about your data to make educated guesses, which is why stale statistics can lead to terrible performance.

• Site Home: Main landing page for computer-science notes.

• Practice: Practice problems for revision.

• Discrete Mathematics

• Algorithm Implementation

This section provides detailed coverage of advanced concepts, including full derivations, proofs, and extended examples.

Complete mathematical derivations and proofs are provided where appropriate. Each step is explained to ensure understanding of the underlying reasoning.

Advanced examples demonstrate the application of concepts to complex problems. These examples go beyond standard exam questions to develop deeper understanding.

This material connects to current research and advanced applications in the field. Understanding these connections provides context for the study material.

Ensure you have mastered the prerequisite material before attempting this advanced content.