The Query Optimizer

A SQL query is first translated into a logical query plan: a tree of relational algebra operators (select, project, join) with no commitment to algorithms or order. Because joins are associative and commutative, and selections and projections can be pushed around, this logical tree has many equivalent rearrangements. A physical plan additionally fixes, for every logical operator, a concrete algorithm (hash join vs. sort-merge join vs. nested loops) and an access path (sequential scan, index scan). The set of all physical plans equivalent to the query is the search space; the optimizer's job is plan enumeration: generate a manageable subset of this space and pick the least-cost member, using a cost model built from statistics, selectivity estimates, and per-operator cost formulas (covered in Cost Estimation for Query Plans). The dominant source of combinatorial explosion is join order. Given relations `R1, R2, …, Rn` to be joined, there are, for a strictly left-deep tree, `n!` orderings, and if bushy (non-left-deep) trees are allowed there are even more shapes — roughly `(2n-2)!/(n-1)!` distinct binary tree shapes with labeled leaves, exponential in `n` either way. Trying all of them and costing each from scratch is wasteful, because different join orders share overlapping sub-joins whose optimal plans can be computed once and reused. This is exactly the structural signature of a dynamic programming (DP) problem: overlapping subproblems plus optimal substructure. The key subtlety that separates this from a naive "cheapest subplan wins" DP is interesting orders. A sub-join's output might be needed sorted (for a later merge join or for `ORDER BY`/`GROUP BY`), so the optimizer must keep, for every subset of relations, not just the single cheapest plan but the cheapest plan for each output order that some later operator might exploit — because a slightly more expensive sub-plan that happens to already be sorted the right way can save an expensive sort downstream and win globally. This idea originates in the classic System R optimizer and remains the conceptual backbone of essentially every cost-based optimizer in use today.

The standard algorithm is bottom-up dynamic programming over subsets of relations, augmented with interesting-order bookkeeping. We build it up in three stages: the plain subset-DP recurrence, then adding physical properties, then the full algorithm with pruning.

Stage 1 — the subset recurrence. For a query joining relations `{R1,…,Rn}`, define `bestPlan(S)` for every subset `S ⊆ {R1,…,Rn}` as the cheapest plan computing the join of exactly the relations in `S`, ignoring for a moment which order the result comes out in. The base case is a single relation: `bestPlan({Ri})` is the cheapest access path for `Ri` alone (sequential scan vs. available index scans, each costed using selectivity estimates from Cost Estimation for Query Plans). For `|S| ≥ 2`: ``` bestPlan(S) = min over all splits S = S1 ∪ S2 (S1, S2 disjoint, both nonempty, and (S1, S2) connected by at least one applicable join predicate) of: joinCost(bestPlan(S1), bestPlan(S2)) ``` The join itself may use sort-merge, hash join, or nested loops (from Join Algorithms: Sort-Merge and Join Algorithms: Hash Join), and the optimizer costs each applicable algorithm for the split and keeps the cheapest. Requiring `S1` and `S2` to be connected by a join predicate — rather than allowing arbitrary cross products — is what keeps the search space in practice much smaller than the full combinatorial bound, since most queries have sparse join graphs.

Stage 2 — interesting orders. Instead of one `bestPlan(S)`, the optimizer maintains a small table `bestPlan(S, order)` for each subset `S` and each "interesting" sort order — an order that some later part of the query (a `GROUP BY`, an `ORDER BY`, a merge join with a relation outside `S`) could exploit. For each `(S, order)` pair we keep only the cheapest plan whose output happens to satisfy `order` (or which can cheaply be made to, by using a sort-merge join that produces it as a byproduct), plus always the single overall cheapest plan for `S` regardless of order (the "unordered" entry). This is a form of Pareto-optimal bookkeeping: a plan survives if no other plan for the same subset is both cheaper and at least as useful order-wise.

Stage 3 — full System R style algorithm. ``` PSEUDOCODE: System-R style DP join enumeration Input: relations R = {R1, ..., Rn} join graph G (predicates connecting relations) set of interesting orders O = {o1, ..., ok} (derived from ORDER BY, GROUP BY, and merge-join opportunities) Output: optimal physical plan for the full join of R 1. for each Ri in R: 2. for each access path AP of Ri (seq scan, each usable index): 3. plan <- cost and build a scan-plan using AP 4. record plan as a candidate for bestPlans[{Ri}] 5. prune bestPlans[{Ri}] to Pareto-optimal set over (cost, order) 6. for size s = 2 to n: 7. for each subset S of R with |S| = s: 8. bestPlans[S] <- empty set 9. for each way to split S = S1 (union) S2, S1,S2 nonempty, disjoint: 10. if S1 and S2 are NOT connected by a join predicate in G: 11. skip this split // avoid cartesian products 12. for each plan1 in bestPlans[S1]: 13. for each plan2 in bestPlans[S2]: 14. for each join algorithm A in {hash join, sort-merge, nested loop} applicable to (plan1, plan2): 15. newPlan <- build join(plan1, plan2, A) 16. cost <- estimateCost(newPlan) // uses stats from // Cost Estimation module 17. order <- outputOrder(newPlan) // e.g. sort-merge // preserves/produces an order 18. add newPlan to bestPlans[S] tagged with (cost, order) 19. bestPlans[S] <- prune bestPlans[S] to Pareto-optimal set: keep a plan iff no other plan in the set has both lower-or-equal cost AND an order at least as useful for every remaining need 20. return the plan in bestPlans[R] with globally minimum (cost + cost of any final required sort not already satisfied) ``` Two implementation notes make this efficient in practice. First, `bestPlans[S]` is stored in a hash table keyed by the bitmask of `S`, so subset lookups are `O(1)` amortized; there are `2ⁿ` such keys. Second, real optimizers additionally apply branch-and-bound pruning: once a candidate's partial cost already exceeds the best complete plan found so far, that branch is abandoned early, which does not change worst-case complexity but dramatically shrinks the constant factor in practice.

Correctness (why DP finds the true optimum). The argument rests on a principle of optimality: the cheapest plan for joining a subset `S` is built exclusively from cheapest plans (per relevant order) of some partition of `S` into two smaller connected subsets, combined with one join operator. This holds because join cost functions used in practice (for hash join, sort-merge, nested loop) depend only on: the sizes and orders of the two inputs, and the join algorithm chosen — not on the internal structure of how each input's plan was built. Formally, cost is separable: `cost(join(P1, P2, A)) = f(cost(P1), cost(P2), size(P1), size(P2), A)` for a fixed, known function `f`. If a strictly cheaper plan for `S1` existed but were discarded, substituting it into any optimal plan for `S` that used `S1` as a sub-join would only decrease (or keep equal, accounting for order) the total cost — a contradiction. This is the same substitution argument that underlies optimality proofs for shortest paths (Bellman's principle) and for other subset-DP problems like the traveling-salesman DP. The one place this substitution argument needs care is exactly interesting orders: a plan for `S1` that is cheaper in isolation might force an extra sort later, making the global total worse. This is why the algorithm does not discard a slightly more expensive sub-plan if it produces a useful order "for free" — the Pareto pruning in step 19 is precisely the fix that restores the optimality argument: for every subset, we keep every plan that is undominated in the (cost, order) space, so that whichever order the eventual parent operator needs, the right candidate survives.

Time complexity. Let `n` be the number of relations. There are `2ⁿ` subsets. For each subset `S` of size `s`, there are `2^(s-1) - 1` ways to split it into two nonempty disjoint parts (ignoring which part is "left"), so summing over all subsets gives ``` Σ (over all S ⊆ R) (number of splits of S) = O(3ⁿ) ``` This `3ⁿ` bound comes from a standard identity: summing over all subsets `S`, the number of ordered pairs `(S1, S2)` with `S1 ∪ S2 = S` and `S1 ∩ S2 = ∅` equals `3ⁿ` (each of the `n` elements independently goes to `S1`, `S2`, or neither, i.e. outside `S` entirely). Each split does `O(1)` work per join algorithm considered (a constant number of algorithms), plus a constant factor for the number of interesting orders `k` tracked per subset (typically small, since real queries have few `ORDER BY`/`GROUP BY`/merge-join needs). So the algorithm runs in `O(3ⁿ · k)` time and `O(2ⁿ · k)` space to store `bestPlans`.

Honest tradeoffs. `O(3ⁿ)` is exponential, so this exact DP is only practical for modest `n` (roughly up to 12–16 tables depending on implementation and pruning aggressiveness). Restricting to left-deep trees only — where every join has at least one base relation as its right input, common because it matches pipeline-friendly execution — cuts the shape space but the join-order search over which relation joins next is still `O(n · 2�ff)`-ish (`O(n²·2ⁿ)` with a simpler recurrence over subsets and "last relation added"), still exponential but with a smaller base and much smaller constants than full bushy enumeration. Beyond the exact-DP regime, production systems fall back to:

• Greedy / heuristic join ordering (e.g., always join the two currently-smallest relations, or order by decreasing selectivity), `O(n log n)` or `O(n²)`, no optimality guarantee.
• Randomized search (simulated annealing, iterative improvement, genetic algorithms — PostgreSQL's `GEQO` kicks in above a configurable table count), trades a probabilistic near-optimum for polynomial-ish runtime.
• Bounded DP (limit bushy-tree consideration, or DP only over left-deep shapes, or cap subset size explored exhaustively then switch heuristic).

None of these change the fundamental point: DP is exact but exponential; heuristics are polynomial but inexact. The choice is a deliberate engineering tradeoff, not an oversight.

Consider the query joining four relations with the following (illustrative) statistics and join predicates, forming a chain join graph `A – B – C – D` (A joins B, B joins C, C joins D; no direct A–C, A–D, or B–D predicates):

Step 1 — base relations. Each `bestPlans[{X}]` holds the cheapest scan, plus (for D) a second candidate: a plan that produces rows pre-sorted on `orderId` via an index scan, kept because it satisfies the interesting order even though a sequential scan might have lower raw scan cost.

Step 2 — size-2 subsets. Only connected pairs are considered: `AB`, `BC`, `CD` (not `AC`, `AD`, `BD`, since there's no direct predicate — a cross product would be far more expensive and is skipped by the connectivity check in line 10 of the pseudocode). For `AB`: hash join with B (2,000 rows) as the build side costs far less than the reverse, since hash join cost is dominated by building the hash table on the smaller input. For `CD`: since D must eventually be sorted by `orderId` anyway, a sort-merge join here is evaluated too, and if it produces `orderId`-sorted output "for free" (using an already-sorted access path on D), it is kept as the interesting-order-tagged candidate for `CD` even if a hash join is nominally a few cost-units cheaper.

Step 3 — size-3 subsets. `ABC` can only be built from `AB ⋈ C` (connected: B–C predicate exists) or `A ⋈ BC` (connected via B–C join's presence of B). Both are tried and costed; suppose `AB ⋈ C` wins because `AB` is small (after `custId` join, ~2,000 rows) and hash-joining against tiny `C` (50 rows) is cheap. `BCD` is similarly built from `BC ⋈ D` or `B ⋈ CD`; here the `CD`-with-order-tag candidate is combined with `B` if doing so still yields useful order, or the plain cheapest `CD` is used otherwise — the algorithm compares both and keeps whichever survives Pareto pruning.

Step 4 — size-4, the full join. `ABCD` can only be assembled from connected splits of the chain: `AB ⋈ CD`, `ABC ⋈ D`, or `A ⋈ BCD` (splits like `AC ⋈ BD` are impossible since `AC` and `BD` were never built — no predicate connects them). Suppose the costs come out as:

If nothing downstream needs `orderId` order, the optimizer picks `AB ⋈ CD` via hash join at cost 18,500 — the naive cheapest. But if the query's outer context needs the final result sorted by `orderId` (say for a merge with an external result stream, our stated requirement on D), the plain hash-join plan at 18,500 would still need an explicit final sort, say costing 2,000 more, totaling 20,500 — worse than the 19,200 order-preserving alternative. Because the optimizer tracked the order-tagged `CD` candidate all along instead of discarding it as "locally more expensive," it correctly selects the 19,200 plan as globally optimal. This is precisely the scenario the interesting-order bookkeeping in Stage 2 exists to catch.

The dynamic-programming approach to join-order optimization was introduced as part of the System R project at IBM Research, whose cost-based optimizer became the template nearly every relational database has followed since. The paper by Selinger, Astrahan, Chamberlin, Lorie, and Price, "Access Path Selection in a Relational Database Management System" (1979), is the canonical reference: it introduced both the subset-DP recurrence and the concept of interesting orders in essentially the form still used today.

Every major relational database — PostgreSQL, MySQL, Oracle, SQL Server, DB2, and cloud warehouses like Snowflake, BigQuery, and Redshift — runs some variant of cost-based DP join enumeration, typically with a cutover to heuristic or randomized search above a configurable table count (PostgreSQL's `join_collapse_limit` and `GEQO` threshold are direct, user-visible knobs controlling exactly this switch). Analytics engines processing star-schema and snowflake-schema queries with many small dimension tables joined to one large fact table depend heavily on correct join ordering to avoid materializing enormous intermediate results. Distributed query engines (Spark SQL, Presto/Trino, distributed variants of Postgres) extend the same DP core with additional physical properties beyond sort order — data partitioning and replication — since a "distribution-interesting" property (like being partitioned on the join key) can save an expensive network shuffle exactly the way a sort order saves a `Sort` operator, a direct generalization of the interesting-orders idea. Understanding this algorithm is also foundational background for Query Optimization Fundamentals and connects directly to how execution engines later exploit the chosen plan via Join Algorithms: Sort-Merge and Join Algorithms: Hash Join.

Ask the tutor: How would this DP algorithm need to change to account for distributed join costs like network shuffles across partitioned data?