Learning Optimizers: Learned Cardinality Models and Plan Regression

The estimator described in selectivity estimation from histograms is a fixed-size summary of one column, and its errors are structural rather than incidental: it cannot represent correlation between columns, it assumes uniformity inside every bucket, and its accuracy is bounded by the number of buckets. A model trained on query feedback can in principle represent all of that, because it is fitted to the joint distribution rather than to marginals. The reason it has not replaced the histogram is not that the idea fails to improve estimates. It is that a better estimate is not the same thing as a better plan, and the second is what the system is judged on.

What a learned model replaces, and what it cannot

The catalog’s statistics serve three consumers, not one. They feed selectivity estimation, they feed the distinct-value counts that join formulas divide by, and they feed the row-count estimate used to size memory grants. A learned model that predicts the cardinality of a predicate combination can serve the first consumer directly and the third indirectly, but it produces no distinct count for the second unless it is trained for that separately.

That asymmetry matters because the join formulas are where the compounding happens. A model that predicts the output of a two-table join accurately does not by itself tell the search described in join order search and the plan space how to estimate a three-table join whose middle relation it has never seen. Learned optimizers handle this by predicting at the level of the whole query or of a subplan, which is a different interface from the per-operator estimate the executor expects.

The training data is the second constraint. A model fitted to a workload learns the distributions that workload queries, which is exactly right for those queries and arbitrary for others. A query outside the training distribution gets a prediction with no error bound, and nothing in the model reports its own uncertainty. The histogram, for all its crudeness, has an error that is bounded by its bucket mass; the learned model has an error that is bounded by nothing in particular.

Why a lower average error is not a better plan

Suppose a learned model reduces the mean error of cardinality estimates by an order of magnitude. The planner’s decisions are not functions of mean error; they are functions of whether the estimate falls on one side of a crossover. A hash join versus a nested loop is decided by a threshold, and an estimate that is wrong but on the correct side of the threshold produces the right plan. An estimate that is better on average but crosses the threshold in the wrong direction for one query produces a wrong plan for that query.

The distinction is between a regression in the metric and a regression in the outcome. Systems that have deployed learned or feedback-driven estimators report exactly this pattern: aggregate accuracy improves while a small fraction of queries get materially worse plans. Those queries are the ones whose cost curve is steep near their true cardinality, which is to say the ones that were already sensitive.

There is a second and more subtle reason. The optimizer’s cost model was tuned, over years, against the errors of the estimator it ships with. Cost constants, the selectivity of a nested loop’s inner side, the assumptions about correlation, the pricing of a Gather node: all of these were calibrated in the presence of histogram error. Replacing the estimator changes the distribution of errors and invalidates part of that calibration. The cost model and the estimator are a matched pair, and swapping one half does not leave the other intact.

Plan management as the containment mechanism

If the problem is that a plan change can regress a specific query, the direct response is to detect the regression and revert it. Plan management systems store a plan per statement, monitor its execution, and compare the observed cost against a baseline; when a new plan is worse than the stored one, the stored plan is used instead. The mechanism requires that the old plan still be executable, which means retaining it beyond the point where the schema or statistics changed.

The engineering difficulty is the baseline. Execution cost varies with cache state, concurrency, and parameter values, so a comparison between one execution of the old plan and one of the new is dominated by noise. Systems that do this well compare distributions over many executions, or compare against a model of the expected cost, and they are conservative about switching because a false regression costs a good plan.

SQL Server’s automatic plan correction and Oracle’s SQL plan management are two implementations of the same idea: keep a known-good plan, detect when a re-plan produced something worse, and fall back. The detection is not free, and the fallback is not always possible: a plan that references an index which has since been dropped cannot be reinstated.

The containment is partial in a specific way. It protects queries that were previously executing well and then regressed. It does not protect a query that was always badly planned, because there is no good plan to fall back to, and it does not help a new query with no history. A learned estimator’s characteristic failure, which is a confident wrong prediction on an out-of-distribution query, falls into both gaps.

Explicit hints and the cost of overrides

The oldest containment mechanism is the explicit hint: a directive in the statement or in a plan guide that fixes a join order, an access path, or an algorithm. Hints work because they move the decision from a model to a human, and they fail for the same reason. A hinted plan is frozen against changes in data volume, and a hint that was correct for a million rows may be wrong for a billion. Systems accumulate hints the way they accumulate indexes: each one solves a problem at the time it was written and constrains the optimizer forever after.

The cost-model escape hatch is the same idea at a different granularity. Lowering the random page cost changes every plan that depends on the random-to-sequential ratio, which is a broad intervention for a narrow problem. Per-statement settings, where they exist, scope it better.

Neither is a substitute for fixing the estimate. A hint that forces a hash join on a query whose estimate is wrong by a factor of a hundred will produce the right algorithm and the wrong memory grant, and the hash table will spill. The estimate reaches further into the plan than the algorithm choice.

Where the learning actually helps

The empirical result that has held up is narrower than the original claims. Learned models help most where the underlying distribution is stable and the queries are repetitive: a workload of a few hundred statement shapes against tables whose data changes slowly. They help least where the data is appended continuously, because the model must be retrained and the retraining is the same staleness problem as ANALYZE with a larger cost.

The other place learning has been effective is not cardinality at all but the search itself. Instead of predicting cardinalities, a model can learn which plan shapes tend to be good for which query shapes and use that as a prior to guide enumeration, or as a way to skip costing candidates that are almost never chosen. That use is a heuristic over the search space, and its errors are bounded by the search’s ability to still evaluate the candidates it does consider. It is a weaker claim than replacing the cost model, and it is the one that fits the architecture.

For the person reading a plan, none of this changes the diagnostic method. The estimated row count at a node, compared against the actual, identifies where the model diverged. Whether the model is a histogram, an extended statistic, or a neural network, the divergence is at a specific node with a specific predicate, and the plan above that node is a consequence. The difference a learned model makes is that the divergence can occur on a query that no single-column statistic could ever have represented, which is progress and also the reason the failure is harder to explain.