Cost-Based Optimization

They are summaries of the data — row counts, distinct values per column, null fractions, common values, value distributions — that the query planner reads to guess how many rows each step will produce. Missing or stale statistics make those guesses wrong, so the planner picks a bad access path or join method and the query runs far slower.

The optimizer estimates what fraction of rows the predicate will match using stored statistics, converts that fraction into an estimated cost for each candidate path, and picks the cheapest. Low estimated selectivity favours the index; high favours the full scan.

Selectivity is the fraction of rows a predicate keeps (0 to 1); cardinality is the resulting row count — input rows times selectivity. Every cost term scales with cardinality, and estimates feed into the next operator, so an early error multiplies up the plan tree and produces structurally wrong join and access choices.

Join order never changes the result, but it changes the size of the intermediate results carried between operators, so cost can differ by orders of magnitude. The number of orderings grows factorially: eight tables give 40,320 left-deep orders and roughly 17 million bushy ones.

Typically number of distinct values (NDV), null fraction, a most-common-value list with frequencies, a histogram of the rest, and average value width. NDV alone implies every value is equally common; the MCV list records the actual frequency of skewed values, so a rare and a dominant value are estimated differently.

Capture the current plan with estimated and actual row counts. If the estimate is far above reality, the input changed: stale or refreshed statistics, data growth, or skew across parameter values. Fix the estimate before overriding the plan.

It assumes the columns are statistically independent. When they are correlated — a city implies its state, a model implies its manufacturer — multiplying selectivities counts the same restriction twice and severely under-estimates rows. Fix with multi-column statistics, a materialized combined column, or a schema change that removes the redundancy.

The load changed the data but not the catalog statistics, so the optimizer is planning against yesterday's picture — old row counts and a histogram whose maximum value predates the new rows. Estimates collapse, plans flip. Fix by running an ANALYZE-style refresh on the loaded tables; prevent by making that refresh the last step of the load job.

Collecting matches into a bitmap first lets the engine sort and deduplicate page addresses, then read table pages once each in physical order. That converts scattered random reads into a mostly sequential pass, and lets several indexes be combined before touching the table.

Cost combines estimated I/O (pages touched, weighted differently for sequential versus random access) with CPU terms (per row processed, per predicate evaluated, per index entry). The result is an abstract unit for comparing plans on the same query, not a time prediction. Random access is weighted higher because scattered reads lose readahead and locality.

In a left-deep tree every join's right input is a base table, so joins form a pipeline. In a bushy tree both inputs can be intermediate results. Left-deep shrinks the search space from about (2n-2)!/(n-1)! to n! and pipelines well, but bushy plans can be far better for star-shaped queries and parallel execution.

An equi-width histogram splits the value range into buckets of equal width, so a dense region lands in one huge bucket. An equi-depth (equi-height) histogram splits so every bucket holds about the same number of rows, giving narrow buckets where data is dense. Equi-depth handles skew far better, which is why engines prefer it, with an MCV list handling single dominant values it cannot represent.

How closely the table's physical row order matches the index key order. When rows with adjacent keys sit on the same pages, one fetch serves many matches; when they are scattered, each match costs its own random page read. Optimizers store this as a clustering or correlation statistic.

Capture the executed plan with actual row counts and compare them to the estimates operator by operator, bottom-up. The lowest node where estimated and actual diverge sharply is the cause. Common sources: stale statistics, correlated predicates, parameter-sensitive plans, opaque predicates, and values beyond the histogram's range.

Exhaustive dynamic programming is exponential — roughly 3^n time and 2^n memory — so past about a dozen tables the planning time and memory exceed any benefit. Engines switch to greedy construction or randomized/genetic search. You give up the guarantee of the cheapest plan under the cost model, and randomized search also gives up plan determinism.

It builds plans bottom-up over subsets of tables: best plan for every single table, then every pair, then every triple, keeping only the cheapest plan per subset. Reusing sub-results turns a factorial search into roughly 3^n time and 2^n memory. It also keeps extra plans that produce a useful sort order.

Sampling makes statistics gathering cheap but approximate. Row counts, null fractions and histogram boundaries extrapolate well from a modest sample. The number of distinct values (NDV) is the hard one: it cannot be reliably extrapolated, and long-tail distributions are systematically under-estimated, which inflates equality selectivity and distorts join estimates.

Default to letting the optimizer adapt, and invest in the inputs: good statistics and estimable predicates. Pin only the few statements whose worst case is unacceptable, treat each pin as a dated exception with an owner, and monitor pinned plans for decay.

Adaptivity and predictability trade off directly. Let the optimizer adapt by default, since it tracks data change; pin plans only for a small set of critical queries where a regression is unacceptable. Pinning freezes today's plan — including out of better future plans — so each pin needs an owner, a review date, and monitoring.

Both symptoms say the query is past the optimizer's exhaustive-search threshold and is being planned by a randomized heuristic. Reduce the effective relation count by decomposing the statement or materializing stable sub-results, make planning happen once via plan reuse or pinning, and fix the statistics that guide whichever search runs.

Treat freshness per table class, not globally. Let automatic refresh handle small hot tables. For huge tables, tighten the change threshold since a percentage-based trigger fires far too late. For loaded tables, refresh explicitly at the end of the load. Raise sampling targets only on skewed, heavily-filtered columns, and monitor staleness as a signal.