The reframe: a layer limited by what the system can know
Why is planning a different kind of problem from everything below it, and why do estimation errors grow so fast?
What is different about this part of the system
Everything below the planner in a database answers one kind of question: given that you must do X, what is the cheapest way to do X? Sequential or random reads, hash or sort, locks or versions. The input is data and the output is data. The limit is physical (bandwidth, latency) or logical (conflicts, durability).
Planning is the first part whose input is not data and whose output is not data. Its input is a description of a result you want. Its output is a decision. Nothing in it touches a row. Because of this, its main limit is neither physical nor logical but informational: the number that decides which plan is cheapest (the size of each intermediate result) cannot be observed until some plan has run and produced it. The optimizer must commit before it is allowed to find out.
A second limit sits next to it, and it is unusual: planning is a computation billed to the query it is planning. A join algorithm does not spend part of the query's time budget deciding to be a join algorithm. The planner does. The search space grows faster than exponentially with the number of joins, the time budget is a fraction of a runtime you do not know yet, and spending more time on search quickly stops paying off, because the thing you search against (the cost estimate) is itself wrong.
One constraint stops mattering: the constant factor of an operator. How cleverly a hash join probes its table can change the speed by a factor of two or three. But the planner chooses between plans that differ by a factor of 10³ to 10⁶ (a thousand to a million). Getting the join order and the pruning right dominates everything an operator can win or lose. So tuning an operator is usually the wrong move when a query is slow.
Why errors multiply instead of adding
This derivation makes the rest of this mechanism almost inevitable, so it comes first.
The optimizer combines selectivity estimates by multiplication.
- For a condition with several parts joined by AND, it computes s₁ × s₂ × … × sₙ. This is correct only if the parts are independent (knowing one tells you nothing about the others).
- For a join it computes |A| × |B| / max(NDV_A, NDV_B), where NDV means the number of distinct values of the join column on each side. This is correct only if the join is uniform and containment holds. We define both in Estimating cost.
- the fraction of rows a predicate keeps
Each of these is an assumption of independence or uniformity in a new form, and each error is a ratio ("ten times too small"), not a difference ("ten rows too few"). Ratios combine by multiplying. So the estimate for a join of k tables carries the product of k separate error factors. The estimation error grows exponentially with the number of joins. Research on the Join Order Benchmark (a well-known test of optimizers on realistic data) measured errors of up to 10⁸× on real schemas.
Two consequences follow, and they set the agenda for this whole mechanism.
First, the error leans toward underestimation. Independence multiplies selectivities that are in reality correlated, and correlated conditions together are less selective than the product suggests (more rows pass than predicted). So the systematic direction of the error is "this will be small". That is the dangerous direction. Underestimating makes the planner:
- choose a hash table that does not fit in memory,
- send ("broadcast") to every machine a table that is not small,
- use a nested loop over an input that is not few rows.
Overestimating only costs a plan that is conservatively slow. So the error is asymmetric in likelihood and, worse, violently asymmetric in consequence.
Second, refining the cost model is nearly pointless while cardinalities are this wrong. This is the most useful correction here, because folklore says the opposite: "better cost models give better plans." In fact, give a crude cost model the true cardinalities and it picks good plans. Give a beautifully calibrated cost model estimated cardinalities and it picks bad plans with confidence. Cost-model work is second-order. Work on cardinality, and even more, on not needing the cardinality at all, is first-order.
This is the answer to Dev's first suggestion.