Relational Query Optimization theory

Relational algebra forms the formal mathematical substrate of relational databases, modeling data transformations as operators on relations (sets or multisets of tuples). Two relational algebra expressions E_1 and E_2 are defined as equivalent (E_1 ≡ E_2) if they produce the identical multiset of tuples on every valid database instance.



Foundational Equivalence Theorems:

1. Commutativity and Associativity of Joins and Cartesian Products:

- Commutativity: R ⋈_θ S ≡ S ⋈_θ R, and R × S ≡ S × R.

- Associativity: (R ⋈_θ1 S) ⋈_θ2 T ≡ R ⋈_θ1 (S ⋈_θ2 T).

Join commutativity and associativity allow the query optimizer to evaluate all possible permutations of join orderings, searching for the permutation that minimizes intermediate result sizes.



2. Commutativity and Cascading of Selections:

- Cascading: σ_{θ_1 ∧ θ_2}(R) ≡ σ_{θ_1}(σ_{θ_2}(R)).

- Commutativity: σ_{θ_1}(σ_{θ_2}(R)) ≡ σ_{θ_2}(σ_{θ_1}(R)).



3. Commuting Selection with Cartesian Products and Joins (Predicate Pushdown):

- If selection predicate θ involves only attributes belonging to relation R:

σ_θ(R × S) ≡ (σ_θ(R)) × S, and σ_θ(R ⋈ S) ≡ (σ_θ(R)) ⋈ S.

- If selection predicate θ decomposes into θ_1 ∧ θ_2, where θ_1 contains only attributes of R and θ_2 contains only attributes of S:

σ_{θ_1 ∧ θ_2}(R ⋈ S) ≡ (σ_{θ_1}(R)) ⋈ (σ_{θ_2}(S)).



4. Commuting Projections with Joins (Projection Pruning):

- If L is a list of attributes, π_L(R ⋈ S) can push projections down to π_{L ∩ attr(R)}(R) and π_{L ∩ attr(S)}(S), provided all attributes referenced in the join predicate θ are temporarily retained.



Heuristic Rule-Based Optimization (Predicate Pushdown):

In a naive unoptimized query, the database engine would execute a Cartesian product or full join across multi-million-tuple relations (producing an enormous intermediate relation of size |R| × |S|), and only then apply filtering predicates σ_θ. By systematically applying the Predicate Pushdown transformation rule, the optimizer pushes selection operators down the expression tree directly to the leaf scan operators. Filtering tuples at the storage layer reduces the cardinality of intermediate relations from millions of tuples to dozens of tuples before expensive join operators are invoked. This single heuristic rule reduces disk I/O, memory buffer consumption, and CPU comparison cycles by several orders of magnitude.

Join algorithms represent the physical operators implementing logical equi-joins (R ⋈_{R.A = S.B} S). Let relation R contain |R| tuples occupying B(R) disk blocks, relation S contain |S| tuples occupying B(S) disk blocks, and let available buffer memory be B frames.



1. Simple (Tuple-Based) Nested Loop Join (TNLJ):

- Algorithm: For each tuple r ∈ R, scan the entirety of relation S; for each tuple s ∈ S, test if r.A == s.B; if true, emit tuple (r, s).

- CPU Complexity: Exactly |R| · |S| tuple comparisons (strictly quadratic O(|R|·|S|)).

- Disk I/O Cost: If buffer pool holds only 3 pages (1 for R, 1 for S, 1 output), R is read once (B(R) blocks), and for each of the |R| tuples, S is scanned from disk: Total I/O = B(R) + |R| · B(S). For |R| = 100,000 tuples and B(S) = 1,000 blocks, this incurs over 100 million disk block reads, rendering TNLJ catastrophically slow on large datasets.



2. Block Nested Loop Join (BNLJ):

- Algorithm: BNLJ exploits available buffer memory (B frames). It allocates B − 2 frames to read an entire 'block' or 'chunk' of relation R into RAM. It uses 1 frame as an input buffer for S and 1 frame as an output buffer. For each block of R in memory, S is scanned once. Tuples within memory are compared using an in-memory hash index or nested loop.

- Disk I/O Cost: Relation R is partitioned into ⌈B(R) / (B − 2)⌉ chunks. For each chunk of R, relation S is read completely once: Total I/O = B(R) + ⌈B(R) / (B − 2)⌉ · B(S).

- Architectural Optimization: The optimizer chooses the smaller relation (in terms of pages B(R) < B(S)) as the outer relation R, minimizing the chunk count ⌈B(R) / (B − 2)⌉. When B(R) ≤ B − 2 (the entire outer relation fits in buffer memory), S is scanned exactly once, reducing I/O to the absolute minimum: B(R) + B(S).



3. Index Nested Loop Join (INLJ):

- Algorithm: Applicable when an index (B+ Tree or Hash index) exists on the join attribute S.B of the inner relation S. For each tuple r ∈ R, the engine uses the index to probe directly for matching tuples in S, bypassing a sequential scan of S.

- Disk I/O Cost: Total I/O = B(R) + |R| · (Cost of Index Probe + Cost of Tuple Fetch).

- If the index is a clustered B+ Tree of height h: each probe costs h block reads + 1 data block read, yielding Total I/O = B(R) + |R| · (h + 1).

- If the index is unclustered, each matching tuple may reside on a separate physical page, costing 1 random I/O per match.

- Performance Profile: INLJ is dramatically superior when relation R has been heavily filtered by prior predicates (small |R|) and S has an efficient clustered index, executing in O(|R| · log |S|) time.

Sort-Merge Join (SMJ) and Hash Join (HJ) are modern database workhorses capable of processing massive relations with near-linear complexity.



1. Sort-Merge Join (SMJ):

- Phase 1 (Sorting): Both relations R and S are sorted on their join attributes (R.A and S.B) using external merge sort, unless an existing index or prior operator already provides sorted order.

- Phase 2 (Merging): Two cursors p_R and p_S iterate through the sorted sequences in lockstep: if R[p_R].A < S[p_S].B, advance p_R; if R[p_R].A > S[p_S].B, advance p_S; if R[p_R].A == S[p_S].B, output matching joined tuples. If duplicate join keys exist, cursors back-track across identical key groups.

- I/O Cost: If external sort requires 2 passes per relation, sorting costs 2 B(R) (1 + ⌈log_{B-1} ⌈B(R)/B⌉⌉) + 2 B(S) (1 + ⌈log_{B-1} ⌈B(S)/B⌉⌉). The merge pass requires B(R) + B(S) reads. Total I/O ≈ 3(B(R) + B(S)) to 5(B(R) + B(S)).

- CPU Complexity: O(|R| log |R| + |S| log |S|) for sorting, plus O(|R| + |S|) comparisons for the merge phase (in the worst-case of all identical keys, merge degrades to O(|R| · |S|)).



2. In-Memory Hash Join (HJ):

- Phase 1 (Build Phase): The optimizer selects the smaller relation (say R) as the build input. A hash function h(key) partitions R into an in-memory hash table of buckets. For each tuple r ∈ R, compute h(r.A) and insert r into the bucket chain. (Takes |R| insertions).

- Phase 2 (Probe Phase): The engine scans relation S as the probe input. For each tuple s ∈ S, compute h(s.B) to locate the target bucket in R's hash table. The engine traverses the bucket chain, evaluating key equality r.A == s.B. (Takes |S| probes).

- I/O Cost: If R fits in memory, B(R) + B(S) I/Os (each relation read once from disk).

- CPU Complexity: Under uniform hashing and O(1) bucket lookups, exactly O(|R| + |S|) operations. For |R| = |S| = N, exactly 2N tuple operations!



Comparative Dominance:

- Hash Join dominates when relations are unsorted, memory is sufficient to hold the build hash table, and the join condition is a strict equi-join (=). Hash Join requires no ordering and achieves optimal O(N) CPU throughput.

- Sort-Merge Join dominates when: (1) Inputs are already sorted by prior operators or clustered B+ Tree index scans; (2) The query contains subsequent GROUP BY or ORDER BY clauses on the join attribute, preserving the 'interesting order' and eliminating downstream sorting; (3) The join predicate involves range inequalities (<, <=, >, >=), where hash joins cannot function; or (4) Extreme data skew causes hash bucket overflow.

In 1979, Patricia Selinger and the IBM System R research team published the seminal foundation of cost-based query optimization. Given a query joining k relations {R_1, R_2, ..., R_k}, there exist (2k − 2)! / (k − 1)! possible bushy join trees, and k! left-deep join trees. Exhaustive search across all plans is computationally intractable for large k.



1. Left-Deep Join Trees Restriction:

- System R restricts the primary search space to Left-Deep Trees (trees where the right child of every join operator must be a base relation, never an intermediate join result).

- Advantages: Left-deep trees allow pipelined execution. As tuples are emitted by the left child join, they immediately probe the right base relation without materializing intermediate results to temporary disk storage, minimizing buffer footprint.



2. Dynamic Programming Algorithm Mechanics:

- The algorithm constructs optimal join plans bottom-up by increasing subset size:

- Size 1: For each single relation R_i, determine the cheapest physical access path (full table scan vs available index scans).

- Size 2: For each pair {R_i, R_j}, evaluate joining R_i and R_j using all physical join operators (Nested Loop, Sort-Merge, Hash Join). Retain only the lowest-cost plan for set {R_i, R_j}.

- Size s: For each subset of s relations S ⊂ {R_1, ..., R_k}, evaluate joining optimal subplans of size s − 1 with the remaining base relation R_m ∈ S. By the Bellman Principle of Optimality, the optimal plan for subset S is composed of the optimal subplan for S \ {R_m} joined with R_m.

- Complexity: Reduces join search complexity from O(k!) to O(k · 2^k), making queries with 10 to 15 joins tractable.



3. The Role of 'Interesting Orders':

A vital exception to standard dynamic programming pruning occurs when a plan produces tuples sorted in an order that could benefit subsequent query operations (e.g., ORDER BY, GROUP BY, or a subsequent Sort-Merge Join). Such an ordering is designated an **Interesting Order**.

- If Plan A for {R_1, R_2} has higher cost than Plan B, but Plan A delivers tuples sorted on an interesting order while Plan B produces unsorted output, the optimizer CANNOT discard Plan A!

- Discarding Plan A could force a downstream Sort operator costing millions of cycles, whereas retaining Plan A allows the downstream operator to execute at zero additional cost.

- Therefore, Selinger DP retains the cheapest plan overall AND the cheapest plan for each distinct interesting order, guaranteeing global cost optimality.

The query optimizer's cost formulas depend decisively on Cardinality Estimation: predicting the number of tuples that will satisfy selection predicates and survive intermediate join operators.



1. System Catalog Statistics:

The catalog maintains vital statistics updated via ANALYZE commands:

- |R| or N_R: Total cardinality (tuple count) of relation R.

- B(R): Number of physical disk blocks (pages) occupied by R.

- V(A, R): Number of distinct values for attribute A in relation R.

- min(A, R), max(A, R): Minimum and maximum values of attribute A.



2. Standard Selectivity Factor (sel) Formulas:

- Equality Predicate (σ_{A = constant}): Under the Uniform Distribution Assumption, each distinct value appears with equal probability 1 / V(A, R):

sel(A = c) = 1 / V(A, R).

Estimated output cardinality: |σ_{A = c}(R)| = |R| / V(A, R).

- Range Predicate (σ_{A > constant}):

sel(A > c) = (max(A, R) − c) / (max(A, R) − min(A, R)).

- Equi-Join (R ⋈_{R.A = S.B} S): Assuming containment of value sets:

sel(R ⋈ S) = 1 / max(V(A, R), V(B, S)).

Estimated join size: |R ⋈ S| = (|R| · |S|) / max(V(A, R), V(B, S)).



3. Conjunctive Predicates and Attribute Value Independence (AVI):

For multiple predicates σ_{θ_1 ∧ θ_2}, naive optimizers multiply individual selectivities:

sel(θ_1 ∧ θ_2) = sel(θ_1) · sel(θ_2).

- Limitation: Real-world data exhibits strong attribute correlation (e.g., σ_{Make = 'Audi' ∧ Model = 'A4'}). Multiplying independent selectivities drastically underestimates cardinality, causing the optimizer to pick disastrous execution plans (e.g., choosing nested loop join based on an estimated 5 tuples when 50,000 actually exist).



4. Equi-Width vs Equi-Depth Histograms:

To overcome uniform distribution limitations, databases build statistical histograms on attribute distributions:

- Equi-Width Histograms: The domain [min, max] is divided into k intervals of equal width. The histogram records the tuple count in each bucket. Fails when data has extreme spikes or heavy skew.

- Equi-Depth (Equi-Height) Histograms: Bucket boundaries are chosen such that every bucket contains approximately the same number of tuples (|R| / k). Skewed data regions automatically receive narrower buckets with higher resolution, providing substantially superior selectivity estimation for range queries and eliminating worst-case estimation errors.

A common misconception among software engineers is that an index scan is always faster than a sequential table scan. In reality, the query optimizer evaluates a fundamental physical threshold known as the **Index Scan Tipping Point**.



1. Clustered vs Unclustered Index Architecture:

- Clustered (Primary) Index: The physical table data rows are stored on disk in the exact sorted order of the index key. Once the B+ Tree search locates the first matching leaf entry, all matching tuples reside in contiguous physical disk blocks.

- Unclustered (Secondary) Index: The index leaf entries store pointers (Record IDs / rowids: page number + slot offset) to physical data pages. The physical table rows are scattered randomly across data pages on disk.



2. The Mechanics of the Tipping Point:

Suppose a query requests `SELECT * FROM Orders WHERE order_date >= '2024-01-01'`. Let the query match a fraction s (selectivity) of the table:

- Sequential Full Table Scan: The database reads every data page sequentially. Sequential disk I/O on modern NVMe SSDs or disk arrays streams at 2,000 to 5,000 MB/s, utilizing large multi-block read-ahead buffers (e.g., 128KB to 1MB per read syscall). Cost = B(R) sequential block reads.

- Unclustered Index Scan: For each matching tuple, the engine reads an index leaf, extracts the tuple pointer, and performs a random disk read to fetch the heap data page. Random disk access lacks read-ahead prefetching and incurs device seek/controller overhead (typically 50 to 100 MB/s, 20× to 50× slower than sequential streaming).

- If the table contains 1,000,000 tuples across 20,000 pages, and the selectivity is 5% (50,000 matching tuples):

- Full Table Scan reads 20,000 pages sequentially (~10 ms on NVMe SSD).

- Unclustered Index Scan reads ~500 index pages plus 50,000 random data page fetches. In the worst case, 50,000 random page reads incur 500 ms to 5 seconds of latency!



3. The Tipping Point Definition:

The selectivity percentage s* where the cost of random page reads via an unclustered index exceeds the cost of a full table scan is the **Tipping Point** (typically between 2% and 10% selectivity in physical systems).

If selectivity exceeds the tipping point (s > s*), the optimizer intentionally ignores the unclustered index and executes a Full Table Scan, maximizing overall throughput.

When relations R and S exceed available RAM buffer memory M, an in-memory hash join fails due to memory exhaustion. The standard industrial solution is the **Grace Hash Join** algorithm (originally designed for the GRACE database machine at the University of Tokyo):



1. Partitioning (Divide) Phase:

- The system allocates M buffer frames: M − 1 frames as output buffers and 1 frame as an input buffer.

- A partition hash function h_1(key) maps join keys to integers {0, 1, ..., M − 2}.

- Relation R is scanned: for each tuple, h_1(r.A) routes the tuple to output buffer B_i. When a buffer fills, it is flushed to disk as partition R_i.

- Relation S is identically scanned and partitioned using the exact same hash function h_1 into partitions S_0, S_1, ..., S_{M-2}.

- Hash Invariant: If a tuple r ∈ R matches s ∈ S (r.A == s.B), then h_1(r.A) == h_1(s.B). Therefore, matching tuples MUST reside in identically numbered partitions R_i and S_i. No cross-partition comparisons are ever required!



2. Join (Conquer) Phase:

- For each partition pair (R_i, S_i) from i = 0 to M − 2:

- The engine reads partition R_i into memory and builds an in-memory hash table using a second, independent hash function h_2(key) ≠ h_1.

- The engine streams partition S_i through memory, probing the h_2 hash table and emitting joined tuples.

- Both partitions are freed before proceeding to partition i + 1.



3. I/O Complexity of Grace Hash Join:

- Partitioning Phase: Reads R and S (B(R) + B(S)), writes partitions to disk (B(R) + B(S)).

- Join Phase: Reads each partition R_i and S_i once from disk (B(R) + B(S)).

- Total Disk I/O = 3 · (B(R) + B(S)) disk block transfers. This achieves optimal linear I/O scaling matching external Sort-Merge Join!



4. Recursive Partitioning and Skew Handling:

- If an individual partition R_i still exceeds memory (due to non-uniform key distribution or hash collisions), the algorithm applies **Recursive Partitioning**: it re-partitions R_i and S_i using a third hash function h_3, creating sub-partitions until each fits in RAM.

- Hash Skew & Heavy Hitters: When a specific join key occurs millions of times (e.g., null values or default foreign keys), all occurrences map to the identical bucket regardless of hash function. Modern engines detect heavy hitters during partitioning, isolating skewed keys into dedicated memory buffers or processing them via hybrid broadcast joins to prevent system thrashing.