Query plan estimation

Why can a database holding accurate statistics still pick a plan thousands of times slower than the obvious one?

The statistics were refreshed this morning and every histogram matches the data exactly. The query is four tables and two WHERE clauses — nothing exotic. And the optimizer picks a plan that runs forty minutes where a plan a person would write on a napkin runs in two seconds.

The tempting diagnosis is stale statistics, and sometimes it is right. But grant that every number the optimizer holds is correct. Can it still choose catastrophically? It can — because it never has the number it actually needs.

An optimizer chooses a plan by estimating each candidate's cost, and cost is dominated by how many rows flow between operators. Everything rests on cardinality estimation: how many rows survive this filter, how many come out of this join.

What does it have to work with? Per-column summaries — a histogram of one column's values, a distinct count, a most-common-values list — describing each column marginally, one at a time. But a query asks about a conjunction, and answering one exactly needs the joint distribution across the columns involved, an object exponentially large in the number of columns and therefore not stored. So the optimizer combines marginals with an assumption, near-universally independence: the selectivity of A and B together is the selectivity of A times that of B.

Watch what that does with perfectly accurate inputs. Ten million rows; a predicate on city matching one row in a thousand, exactly right; a predicate on postcode matching one row in a thousand, also exactly right. Independence gives one in a million, so the estimate is ten rows. But postcode determines city; the predicates are not independent, they are nearly redundant, so the true count is whichever is narrower: about ten thousand rows. A thousandfold underestimate, every statistic correct. The error lives entirely in the combination rule.

Now let the plan follow. Ten estimated rows makes a nested loop with an index lookup look wonderful — ten probes is nothing. Ten thousand actual rows means ten thousand scattered probes, each potentially a page fetch, where a hash join would have made one sequential pass. The thousandfold cardinality error becomes a comparable time error, because the two plans' cost curves cross somewhere between ten and ten thousand rows and the estimate landed on the wrong side of the crossing.

Then compounding. A join's estimated output feeds the next join's estimate, so errors multiply along the tree rather than averaging out. Ioannidis and Christodoulakis made this point in 1991 — I recall the result rather than derive it — that estimation errors propagate exponentially in the number of joins. A factor of ten at a leaf becomes orders of magnitude at the root, which is why two-table plans are usually fine and eight-table plans are a lottery.

One further feature makes this lethal rather than merely inaccurate: the penalty for being wrong is asymmetric. Underestimate and you pick nested loops, whose cost rises without bound as the true row count rises. Overestimate and you pick a hash join or a scan, whose cost is bounded by the input size however few rows qualify; you waste a fixed amount and finish. The two directions carry wildly different risk, while the optimizer compares only point estimates. It chooses as if the estimates were facts.

Now make the account falsifiable, because "correlated predicates" must be distinguishable from "stale statistics". The prediction is precise: recomputing single-column statistics should change nothing, since they were already right, while creating one extended statistic over exactly the correlated pair should flip the plan — same data, same query, two commands. The refuting observation is equally clean: if a plain refresh of single-column statistics fixed it, staleness was the cause and this account does not apply.

Try it from the other side too. If the mechanism is missing joint information rather than bad arithmetic, a plan that measures rather than estimating should not suffer — and adaptive execution, which counts rows as they are produced and re-plans when they diverge, is evidence that the estimate is the weak link rather than the cost model.

Two refinements connect the reasoning. First, "the optimizer was wrong" is the wrong framing: given its inputs the arithmetic was right, and the missing input was the joint distribution, which no realistic amount of statistics-gathering supplies. Cardinality estimation is structurally proxy evidence — the only way to know exactly how many rows satisfy a conjunction is to evaluate it, which is the very work being planned. That constraint will hold in twenty years, whatever the storage engine.

Second, correlation is not the only source of error. Estimates over join results, user-defined functions, parameters unknown at planning time, and expressions no histogram describes are all weakly grounded, and some systems simply substitute a fixed guess. Correlated predicates are the clearest case only because they show the failure with perfect statistics.

Worth naming what is not the explanation. Query hints and frozen plans are widespread and they work, but their popularity is mostly operational risk — an operator prefers a merely adequate plan that never changes to a usually-better one that can regress overnight. That is a defensible tolerance for variance, not evidence that hand-written plans are better, and it locks in decisions that stop being right as data grows.

This differs from the concurrency problems transactions solve, and is a cousin of progress-bar estimation with one sharp distinction: a progress bar that guesses wrong merely misinforms, whereas a wrong cardinality changes the strategy executed — and the strategies differ in whether their cost has a ceiling.

• How extended statistics are built, and why you cannot simply create them for every pair of columns.
• Why sampling-based estimation still struggles with highly selective predicates, however large the sample.

Every term the collection defines is gathered in the glossary.