Join order search
How can an optimizer search a space with billions of plans, and what happens when it cannot?
The size of the space
For n relations, the number of left-deep join orders (each join takes a base table as its right input) is n!. The number of bushy orders (joins can take other joins as inputs) is (2(n − 1))! / (n − 1)!.
| n relations | Left-deep: n! | Bushy: (2(n−1))! / (n−1)! |
|---|---|---|
| 10 | 3.6 million | about 1.8 × 10¹⁰ |
Full enumeration is not an option, so the question becomes: what structure permits pruning?
Dynamic programming and the principle of optimality
Dynamic programming (DP) works because of the principle of optimality: cost is monotone in sub-plan cost, so the best plan for a set S of relations can be built from the best plans for subsets of S, and each subset needs to be solved only once. Solving every subset by every binary split costs O(3ⁿ).
| n | 3ⁿ |
|---|---|
| 10 | about 59,000 |
| 20 | about 3.5 billion |
That is the DP cliff. DP is comfortable up to about 12 relations, painful to about 15, and impossible after.
Interesting orders: the principle is false as stated
The principle of optimality is false as stated, and the reason is a mechanism that is often left out of introductions. A suboptimal sub-plan that delivers a useful sort order can beat the optimal sub-plan overall, because it lets a later merge join skip a sort.
So the DP table cannot hold one best plan per subset. It must hold one best plan per subset per distinct physical property. Selinger's interesting orders are exactly this. Distributed planners generalize the idea to data distribution: hash-partitioned on x, broadcast, or single-node. A sub-plan already partitioned on the next join key saves an exchange. This is why a distributed optimizer's memo is larger than a single-node one at the same table count: the property vector has an extra dimension, and that dimension is the expensive one.
Enforcers
Physical property reasoning also introduces enforcers. When a required property (a sort order, a distribution) is not delivered, the planner inserts an operator that supplies it: a sort or an exchange. Placing enforcers optimally is itself part of the search. This is where the real difference between a distributed and a single-node planner lies. It is not in the join algorithms. It is in the fact that data movement is a dimension of the plan space that does not exist on one machine.
When DP is out of reach
Greedy methods (for example GOO, or "pick the join with the smallest estimated result first") run in O(n³) with no guarantee. Their failure mode is systematic, not random: they commit early to the pair that looks smallest under estimates that are least reliable for exactly the small results they are chasing.
Genetic search (PostgreSQL's GEQO, which starts when the query has at least geqo_threshold = 12 relations) has a property that is best called a defect, not a technique: it is nondeterministic. The same query, the same data and the same statistics can receive different plans on different executions. That turns an optimization problem into a plan-stability problem. A mean improvement is bought with variance, and someone will be paged about the variance. Here the principle from The reframe: a layer limited by what the system can know returns: in production, variance matters more than the mean.
Honest claim typing: the search is not the real limit
Join ordering is NP-hard in general. But the practically decisive point is different: for the queries people really run, the search is not the binding constraint. The estimates are. Exhaustively searching 10⁹ plans against cardinalities that are 10⁴ off is a rigorous optimization of the wrong objective. This is why the field's effort moved from search algorithms (1980s-90s) to estimation (2000s), and then to adaptivity (2010s onward). Each move was an admission that the previous one had been solving a tractable problem, not the binding one.
Query graph shape matters more than table count
One structural fact matters more than n: the shape of the query graph (tables as nodes, join conditions as edges).
| Shape | Description | Difficulty |
|---|---|---|
| Chain | A joins B joins C joins D | O(n²) connected subgraphs; easy |
| Star | One big fact table joined to many small tables | Small effective space, since small tables have no useful interaction with each other |
| Clique | Every table joins every other | Explodes |
Real BI workloads are stars and snowflakes (stars whose dimension tables have their own dimension tables). That is why star-specific machinery exists (star transformation, heuristics that build bushy plans over the dimensions), and why an optimizer's results on a standard benchmark like TPC-H tell you little about its behavior on a 40-table snowflake.
In one sentence: DP is O(3ⁿ) and dies at about 15 relations; the principle of optimality only holds once you index the table by physical property as well as by relation set; and past the cliff you are in nondeterministic heuristic territory where plan stability, not plan quality, becomes the problem.