Many relational optimizers stop doing exhaustive join-order search once a query exceeds a certain number of joined tables and switch to a greedy or randomized/genetic algorithm. Why, and what do you give up?

## Why exhaustive search has to stop Dynamic programming over subsets examines `3^n` combinations and stores `2^n` memo entries. Concretely: n=12 is a few hundred thousand memo entries and low-millions of combinations — fine. n=20 is a million memo entries and 3.5 billion combinations — not fine. And optimization time is not free: it is paid on every plan-cache miss, inside the user's latency budget. A query that executes in 40 ms should not spend 900 ms being planned. So engines carry a configurable **join-count threshold**. Under it, exact search; over it, something cheaper. The threshold is usually in the 8–12 range by default. Note that the count is of *relations after flattening* — inlined views and subqueries pull their base tables into the same optimization region, so a query that visually joins six things can easily cross the threshold. ## Fallback 1 — greedy construction Start with each relation as its own unit. Repeatedly pick the pair of units connected by a join predicate whose combination looks best — usually smallest estimated output cardinality, sometimes lowest estimated cost — and fuse them. Repeat until one unit remains. - Complexity is roughly `O(n^3)` (n-1 fusion steps, each scanning O(n^2) pairs). - **Deterministic**: the same inputs and statistics produce the same plan, which matters enormously for operational predictability. - **Myopic**: it never reconsiders. Choosing the smallest intermediate now can force an expensive join later — the classic failure of any greedy algorithm on a problem without matroid structure. ## Fallback 2 — randomized / genetic search Encode a join order as a chromosome (for example, a permutation of relation ids interpreted as a left-deep order). Generate a random initial population, evaluate each with the ordinary cost model as the fitness function, then iterate: select fitter individuals, recombine them with a crossover operator that preserves permutation validity, mutate occasionally, and keep the best found after a fixed number of generations or a time budget. - Explores a broad, non-local sample of the space, so it can find good plans well outside greedy's reach. - **Stochastic**: unless the seed is fixed, repeated planning of the same query can produce different plans. Some engines pin a seed precisely to restore determinism. - Bounded cost by construction — you choose the population size and generation count, so planning time is capped. Other randomized approaches exist in the literature (iterative improvement, simulated annealing, two-phase combinations); they share the same profile: bounded time, no optimality guarantee. ## What you actually give up 1. **The optimality guarantee.** DP promises the cheapest plan *under the cost model and estimates*. Heuristics promise only a plan. The practical gap is usually modest but has a long tail: occasionally a heuristic misses an order that is 100x better. 2. **Determinism (for randomized search).** Two application servers, or the same server after a restart, can plan the same statement differently. Latency graphs then show bimodal behaviour with no code change to blame — an unpleasant on-call experience. 3. **Explainability.** With DP you can reason about why a plan won on cost. With a genetic search, "it is what the search happened to find" is the honest answer. ## What you keep Bounded planning time, and therefore a bounded worst case. That is the point of the tradeoff: for very wide queries, the risk of spending unbounded time searching outweighs the value of the last few percent of plan quality. ## Engineering response - **Reduce the effective join count** before it crosses the threshold: split the statement, materialize a stable intermediate, avoid stacking views that flatten into one huge optimization region. - **Raise the threshold deliberately** for a small number of important analytic statements where the planning cost is amortized over a long execution, and measure the planning time you just bought. - **Reuse plans** — prepared statements, plan caching, or an engine-level stored plan — so a heavily-joined query is planned once rather than per execution. - **Fix estimates first.** Past the threshold, the heuristic search is guided by the same cardinality estimates; bad statistics make both the search and the resulting plan worse, and no amount of extra search compensates.