How Does a SQL Optimizer Choose Join Algorithms?

A cost-based SQL query optimizer selects between nested-loop joins, hash joins, and sort-merge joins by estimating the total resource cost of each physical operator for a given query plan. It combines table statistics, available indexes, memory budgets, and sort order requirements to predict CPU and I/O expenses, then picks the algorithm with the lowest estimated total cost.

The Cost Model Foundation

Relational databases translate a declarative SQL query into a tree of physical operators. For a join between two relations \(R\) and \(S\), the optimizer evaluates a cost function typically modeled as:

\[\text{Cost} = w_{\text{io}} \cdot \text{I/O}_{\text{pages}} + w_{\text{cpu}} \cdot \text{CPU}_{\text{tuples}}\]

Here, \(\text{I/O}_{\text{pages}}\) represents the estimated number of disk or buffer-pool page reads, \(\text{CPU}_{\text{tuples}}\) represents the number of tuple comparisons or hash computations, and \(w_{\text{io}}\) and \(w_{\text{cpu}}\) are system-calibrated weights. To estimate these quantities, the optimizer relies on catalog statistics such as row counts (\(|R|\) and \(|S|\)), page counts (\(P_R\) and \(P_S\)), histograms, and distinct value counts.

Nested-Loop Join

A nested-loop join iterates over each tuple in the outer relation \(R\) and scans the inner relation \(S\) for matching tuples.

  • Block Nested-Loop Join: When no index exists on the join key of \(S\), the optimizer reads \(R\) in chunks that fit into available memory buffers. The I/O cost is roughly \(P_R + \lceil P_R / B \rceil \cdot P_S\), where \(B\) is the number of buffer pages.
  • Index Nested-Loop Join: When \(S\) has an index (such as a B-tree) on the join column, the inner scan is replaced by an index lookup per outer tuple. The cost drops to \(P_R + |R| \cdot c_{\text{index}}\), where \(c_{\text{index}}\) is the cost of traversing the index.

Optimizers favor nested-loop joins when the outer relation is very small, when a selective index exists on the inner relation, or when the query uses non-equijoin predicates (such as < or !=) that hash and sort-merge joins cannot directly handle.

Hash Join

A hash join is designed for equijoins and works in two phases: build and probe. The optimizer designates the smaller relation (say \(R\)) as the build input, constructing an in-memory hash table on its join key. It then streams the larger relation \(S\) (the probe input), hashing each tuple's join key to find matches.

If the build input fits entirely in the allocated memory (\(P_R \le M\)), the I/O cost is linear:

\[\text{Cost}_{\text{hash}} \approx P_R + P_S\]

If \(R\) exceeds available memory, the optimizer uses a grace hash join, partitioning both \(R\) and \(S\) into \(k\) buckets on disk and joining each bucket pair independently. This increases the I/O cost to approximately \(3(P_R + P_S)\) due to writing and re-reading partitions.

Optimizers choose hash joins for large, unsorted datasets joined on equality predicates, provided there is enough memory to avoid excessive disk spilling.

Sort-Merge Join

A sort-merge join also targets equijoins and consists of two stages: sorting both relations on the join key, followed by a linear merge scan.

  • If both inputs are already sorted—for example, from an index scan or an upstream ORDER BY—the sort phase is skipped, and the I/O cost is simply \(P_R + P_S\).
  • If either input is unsorted, the optimizer adds external merge-sort costs, which scale as \(O(P \log_B P)\) I/O operations.

Optimizers prefer sort-merge joins when one or both inputs are already ordered on the join key, when memory is too constrained for a hash table, or when the query requires the output to be sorted (such as for a subsequent ORDER BY, GROUP BY, or DISTINCT operation), allowing the sort cost to be amortized across multiple operators.

How the Optimizer Makes the Final Decision

The optimizer does not evaluate join algorithms in isolation; it considers them as part of a global plan search (often using dynamic programming, as in System R). For each join node, it tracks physical properties like sort order and estimates cardinality using selectivity factors. It then compares the cheapest valid plan for each algorithm, balancing immediate I/O and CPU costs against downstream benefits like avoiding extra sorts.