Join Order Search and the Explosion of the Plan Space

For n relations, the number of distinct orders in which they can be joined is n factorial if every pair may be joined at any point. That figure understates the problem rather than overstating it: each join can also be implemented by several algorithms, each with its own cost profile, and the join tree can take shapes other than a chain. Ten tables give more than three million orders before any algorithm choice is made. Twenty tables give a number larger than the age of the universe in seconds. An optimizer that enumerated all of them would never return, so every practical planner is a search procedure over a deliberately restricted space, and the restrictions are where the interesting engineering lives.

The restriction that matters most is the tree shape. A join tree is either left-deep, in which the right input of every join is a base relation, or it permits composite inputs on both sides. Left-deep trees correspond to fully pipelined plans: the right side is scanned or probed while the left side streams, and no intermediate result has to be materialised. Bushy trees can be cheaper, because they allow two small intermediate results to be joined, but each composite input must be materialised, which costs memory and a possible spill to disk.

Left-deep trees and the pipelining constraint

A left-deep tree of four relations joins A to B, then the result to C, then that result to D. With hash joins throughout, the plan builds a hash table on the right input at each level and probes it with the rows streaming from the left. Nothing is written to disk unless a hash table exceeds the memory granted to it, and the first row can be produced after the leftmost scan starts. That exception is the one the search cannot see: the cost of a plan that spills is not the cost of the plan that was scored, as memory limits and spill sets out.

A bushy tree of the same four relations joins A to B and C to D independently, then joins the two results. The inner join produces a materialised intermediate result, which is then read back. The advantage is that if A×B is tiny and C×D is tiny, their join is tiny too, and the total work is far less than any left-deep order. The disadvantage is the materialisation: a temporary relation, its write cost, and its read cost, all of which must be paid before the final join can begin.

The classic dynamic-programming formulation restricts the search to left-deep trees precisely so that the cost of a plan can be computed incrementally. If the cheapest plan for a set S of relations is known, then the cheapest left-deep plan for S joined to a new relation R is computed by extending it, and the extension cost depends only on the size of S’s result and R. That is a Bellman-style recurrence, and it makes the search polynomial in the number of subsets for a fixed number of relations.

The state space is the set of subsets of the relations, so 2^n states, and for each subset the algorithm considers every way of splitting it into a left part and a single relation. That is n times 2^n transitions, each requiring a cardinality estimate for the intermediate result. For ten relations, 1024 subsets and roughly 10,000 transitions, which is fast. For twenty, a million subsets and twenty million transitions, which is no longer fast, and the memory required to hold the cheapest plan per subset becomes the binding constraint.

best = {frozenset([r]): (scan_cost(r), r) for r in relations}

for size in range(2, len(relations) + 1):
    for subset in subsets_of_size(size):          # 2^n subsets in total
        for r in subset:
            left = subset - {r}
            if left not in best or not connected(subset):
                continue                            # unconnected subsets are cross products
            cost = best[left][0] + join_cost(left, r, best[left][1])
            if subset not in best or cost < best[subset][0]:
                best[subset] = (cost, (best[left][1], r))

The connected check is what makes the loop affordable on real queries: a subset with no predicate path between its relations is skipped before any costing happens, so a star schema whose dimensions connect only through the fact table enumerates a small fraction of the theoretical space.

Predicate placement prunes before costing

The subset enumeration is over joins that are legal, and most joins are not. A query joining ten tables through a chain of foreign keys has, at each step, only one or two relations that can legally be joined next, because a join with no connecting predicate is a cross product. The optimizer records which pairs have join predicates and refuses to consider a subset unless it is connected: every relation in it reachable from every other through predicates inside the subset.

This is the single most effective pruning rule, and it is why real queries with a dozen tables often search a space of dozens of orders rather than billions. The rule is a graph property, computed once from the query’s predicate list, and it is applied before any costing happens. It also explains why the same number of tables produces wildly different planning times depending on how they are connected: a star schema with one fact table and nine dimensions has a legal join graph in which the fact table must be joined first, and the enumeration collapses.

Cross products are not forbidden, they are priced. A query that genuinely requires one, such as a join on a range predicate that the optimizer cannot express as an equality, produces a search space with no connectivity to prune and a plan that may take noticeably longer to find. Products differ on whether they allow cross products at all in the search; those that do not will produce a plan with a filter instead, which is correct but slower to execute.

Interesting orders, and why the cheapest plan is not always chosen

The dynamic program as described keeps one plan per subset: the cheapest. That is wrong whenever a plan produces rows in an order that a later operation can exploit. A plan whose output is sorted on the join key lets a merge join above it skip its sort, and a plan whose output is sorted on the final ORDER BY lets the query skip its final sort. Both are worth paying extra for at the lower level.

The 1979 Selinger paper formalises this by keeping, per subset, one plan for each “interesting order”, meaning each ordering that some later operator could use. The cost of a subset then becomes a vector rather than a scalar, and the comparison between two plans for the same subset depends on which order the parent needs. A sort operation is added as a way to convert any plan into any interesting order, priced at its own cost, so the search never loses a plan it might need.

This is the mechanism behind a plan that costs more at the scan level and less overall. Without interesting orders, the optimizer would pick a cheap unsorted scan and then pay for a sort at the top; with them, it can pick the more expensive index scan whose output is already ordered and skip the sort entirely. The bookkeeping cost is real, because the number of distinct interesting orders grows with the number of sort keys and joins, and implementations cap it.

When the search is truncated: genetic and greedy fallbacks

Past a threshold on the number of relations, exhaustive subset enumeration stops being affordable. PostgreSQL’s geqo_threshold defaults to 12 relations, above which the planner switches from dynamic programming to a genetic algorithm. The genetic search does not enumerate subsets; it maintains a population of join orders, evaluates each, and combines the better ones, with mutation and crossover over the sequence of relations. It is not guaranteed to find the optimum, and it is not deterministic in the same way, but it returns a plan in bounded time.

The switch is visible in behaviour. Below the threshold, adding a table to a query increases planning time in a way that tracks the subset count. Above it, planning time becomes roughly stable while plan quality becomes variable: two runs of the same query can produce different orders, and the chosen order may be several times worse than the best available. Raising the threshold moves the boundary but does not remove it, because the underlying enumeration is exponential either way.

Other systems use greedy construction instead: repeatedly join the pair of relations whose intermediate result is smallest, or whose join is cheapest, and never revisit the choice. Greedy search is linear in the number of relations, and it fails on the shapes where a locally cheap join is globally bad, which is exactly the star-schema case where joining two small dimensions first produces a cross product. Implementations that use greedy search usually add a rule to forbid joining two relations that lack a predicate between them, which recovers most of the loss.

The cost of the estimate inside the search

Every transition in the dynamic program needs a cardinality estimate for the intermediate result, and the estimate is produced by the same machinery that estimates base predicates. For a join of two relations, the standard formula multiplies the two input cardinalities by the join selectivity, which is derived from the equality of the join columns’ distinct-value counts. For a chain of joins, the estimates compound: each level’s output becomes the next level’s input, and an error at level two propagates through every level above it.

This is why join order search and cardinality estimation cannot be evaluated separately. A search that enumerates the right space but scores it with estimates that are wrong by a factor of a hundred will pick the plan that is best under the wrong numbers, and the error compounds with each level of the tree. The containment assumption underlying those estimates, and the cases where it fails, are the subject of join cardinality and the containment assumption.

The practical consequence for anyone reading a plan is that the join order printed is the optimizer’s conclusion, not its reasoning. A surprising order is usually a sign that one intermediate cardinality was estimated far from reality, and the estimated row counts at each node are the evidence. Reordering the query’s FROM clause does not change the search in systems that enumerate orders freely, though it does in systems that respect join hints or that fall back to syntactic order when the search is disabled.