Explain how the classic System R (Selinger) dynamic-programming algorithm chooses a join order, and why it is cheaper than trying every ordering.
answer
- Subsets, not permutations
- Pass k joins best (k-1)-subset + 1 relation
- Principle of optimality → one plan per subset
- O(3^n) time, O(2^n) memory
- Interesting orders kept as extra plans
basics
~20 sIt builds plans bottom-up over subsets of tables: best plan for every single table, then every pair, then every triple, keeping only the cheapest plan per subset. Reusing sub-results turns a factorial search into roughly 3^n time and 2^n memory. It also keeps extra plans that produce a useful sort order.
solid answer
~50 sSystem R's optimizer enumerates **subsets, not permutations**. Pass 1 finds the cheapest access path for each single table. Pass k builds every k-table subset by joining an already-optimized (k-1)-subset with one more relation, costing each combination and keeping only the winner for that subset. Pass n yields the final plan. It works because of the **principle of optimality**: if the cheapest plan for {A,B,C,D} joins {A,B,C} to D, the {A,B,C} part must itself be the cheapest way to produce {A,B,C}. So each subset needs one surviving plan instead of all its orderings. Cost drops from about `n!` to `O(3^n)` time with `O(2^n)` memory. Two refinements matter. Cross products are skipped unless unavoidable. And the algorithm keeps a second plan per subset when it delivers an **interesting order** — a sort order useful to a later merge join, group-by or ORDER BY — because a locally costlier plan can be globally cheaper.
code
text · 4 linespass 1: {A} idx_scan {B} seq_scan {C} idx_scan {D} seq_scan
pass 2: {A,B} hash(A,B) {B,C} merge(B,C) {C,D} nl(C,D) ...
pass 3: {A,B,C} = best( join({A,B},C), join({B,C},A), ... )
pass 4: {A,B,C,D} = best( join({A,B,C},D), join({A,B},{C,D}), ... )go deeper
Recall that the optimizer builds plans bottom-up over groups of tables and reuses the best sub-plan instead of trying every order.
State the pass structure, the principle of optimality, and that complexity is exponential but far below factorial.
Add interesting orders, cross-product pruning, and the caveat that optimality is relative to the cost model and estimates.
Frame DP as one point on a search-cost curve: exact below a threshold, heuristics above it, with estimate quality — not search exhaustiveness — usually the binding constraint on plan quality.
## The problem it solves Enumerating every join order is factorial. The 1979 System R optimizer, described by Selinger and colleagues, is the algorithm essentially every cost-based relational optimizer still descends from. Its insight is that the enormous number of *orderings* collapses onto a much smaller number of *subsets of tables*. ## The algorithm, pass by pass Let the query join relations R1..Rn. **Pass 1 — single relations.** For each relation, evaluate every access path: sequential scan, each usable index scan, index-only scan. Apply the single-table predicates. Keep the cheapest plan for that relation (plus any interesting-order plans, below). **Pass k — k-relation subsets.** For each subset S of size k, and for each way of splitting S into an already-optimized subset S' of size k-1 and a remaining relation R, form the join of best-plan(S') with best-plan({R}) using each physical join method available. Cost each candidate. Store only the cheapest plan for S. **Pass n.** The single surviving plan for the full set of relations, with any final sort/aggregation on top, is the chosen plan. The optimizer keeps a memo table keyed by subset — conceptually a map from a bitmap of relations to its best plan and estimated cost and cardinality. ## Why it is correct to throw plans away The justification is the **principle of optimality**. Suppose the true best plan for the whole query joins the group {A,B,C} to D. The cost of that top join depends on its inputs only through the *cardinality* and *cost* of the {A,B,C} sub-result — not through how {A,B,C} was computed. Cardinality is a property of the set, identical for all orders. Therefore the cheapest way to build {A,B,C} can be substituted without changing the top join's cost, and the best whole-query plan must contain the best sub-plan. Hence one surviving plan per subset suffices. ## Complexity There are `2^n` subsets, and summing over all splits of all subsets gives `3^n` (each relation is in S', in S\S', or outside S). So the algorithm is roughly `O(3^n)` time and `O(2^n)` memory in the general bushy case — versus `n!`-ish for naive enumeration. For n=12 that is millions of steps instead of hundreds of millions of orderings; for n=20 it is still hopeless, which is why thresholds and fallbacks exist. If the search is restricted to left-deep trees, the inner loop only ever joins a subset to a *single base relation*, and the work is closer to `n * 2^n`. ## Interesting orders — the important wrinkle Strict "one plan per subset" is subtly wrong. A plan that is slightly more expensive but delivers its rows already sorted on a join column can feed a cheap merge join above, or satisfy an ORDER BY / GROUP BY for free. Selinger's answer was to keep, per subset, the cheapest unordered plan **plus** the cheapest plan for each *interesting order* — a sort order mentioned somewhere in the query (join columns, GROUP BY, ORDER BY). Modern optimizers generalize this to a broader notion of physical properties (sort order, partitioning, distribution) and prune plans only when one is cheaper *and* no weaker in properties. ## Other prunings baked in - **Cross products avoided.** Subsets whose relations are not connected in the join graph are skipped, unless the query genuinely has no predicate linking them. On chain-shaped join graphs this removes most of the space. - **Cost-based pruning.** Any candidate already exceeding the best known cost for the same subset is dropped immediately. - **Predicate pushdown first.** Single-table predicates are applied in pass 1, so all later cardinalities reflect them. ## What it does not fix DP guarantees the cheapest plan **under the cost model and the cardinality estimates**. It does nothing about estimation error, which compounds multiplicatively up the tree — a plan can be provably optimal for the estimates and terrible for reality. And it remains exponential, so every real engine has a join-count threshold past which it stops doing DP altogether.
- What is an interesting order and why does keeping one break the 'one plan per subset' rule?An interesting order is a sort order the rest of the query can exploit — a join key for a later merge join, or the GROUP BY / ORDER BY columns. A plan can be locally more expensive yet globally cheaper because it saves a sort above. So the optimizer keeps the cheapest plan per interesting order alongside the cheapest unordered plan, and prunes only when a plan is both cheaper and no weaker in physical properties.
- Does dynamic programming guarantee the fastest plan in production?No. It guarantees the cheapest plan under the cost model and the cardinality estimates it was given. If statistics are stale or correlations are missed, the estimates are wrong and the 'optimal' plan can be far from the fastest. Estimation error compounds up the join tree, so deep plans are the most exposed.
- Why is the complexity 3^n rather than 2^n?There are 2^n subsets, but for each subset the algorithm considers every way of splitting it into two parts. Summing over all subsets and all splits, each relation is independently in the left part, the right part, or outside the subset — three choices per relation, hence 3^n total combinations examined.
Like computing shortest routes between cities: once you know the cheapest way to reach a given group of stops, you never re-derive it — you extend it.
saying these in an interview costs you the question
- Describing it as trying all n! orderings with a cost function — that is exactly what it avoids
- Saying it is polynomial; it is exponential, just far smaller than factorial
- Forgetting interesting orders and asserting strictly one plan per subset
- Claiming DP output is optimal in wall-clock terms rather than optimal under the cost model
- Confusing the memo table (subsets) with a cache of previously executed queries