A cost-based query optimizer must decide whether to reach a table through an index or read it whole. Explain how an estimated selectivity, derived from stored statistics, drives that decision.
answer
- stats to selectivity to rows to cost
- scan cost flat, index cost rises with N
- 1/d default, histograms and MCV fix skew
- independence assumption breaks on correlated columns
- estimated vs actual rows is the diagnostic
basics
~20 sThe 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.
solid answer
~60 sThe optimizer never counts rows at planning time; it **estimates**. From stored statistics such as row count, distinct values, most-common values and histograms, it computes a **selectivity**, the fraction of rows the predicate is expected to match, and multiplies by the table's row count to get an estimated row count. That estimate then feeds a cost formula for each candidate path. The full-scan cost is essentially the table's page count at a sequential price, independent of the estimate. The index path's cost is the index descent plus leaf pages proportional to the estimated matches, plus row fetches priced somewhere between sequential and random depending on how well the table's physical order correlates with the index key. The optimizer computes both numbers and takes the smaller. So the estimate is the pivot. A wrong estimate does not produce a wrong *result*, it produces a wrong *plan*: underestimate and the engine picks an index path that ends up doing hundreds of thousands of random fetches; overestimate and it scans a huge table to return twelve rows.
code
text · 4 linesIndex Scan using t_c_idx on t (cost=0.4..8.4 rows=30 width=64)
(actual time=0.02..940 rows=312,455 loops=1)
Index Cond: c = 'X'
-- estimate 30, reality 312,455 -> path chosen on a false premisego deeper
Say that the database guesses how many rows will match using stored statistics, and picks the index when that guess is small and a full read when it is large.
Name the statistics involved, show that scan cost is flat while index cost grows with the estimate, and mention that skewed values can flip the choice.
Lead with the estimate-versus-actual diagnostic, enumerate the common estimation failure modes such as staleness, correlation and opaque expressions, and fix the input rather than overriding the output.
Frame estimation quality as an operational property to be engineered: sampling and refresh policy, extended statistics where correlation matters, predicate shapes that stay estimable, and the blast radius when an estimate is wrong at scale.
## The decision the optimizer is actually making Given `SELECT ... FROM t WHERE c = ?`, several physical plans return identical rows. The optimizer's job is to guess which is cheapest before running any of them. It does this by assigning each candidate a number and comparing. The input that varies most, and therefore determines the answer, is **how many rows the predicate will match**. ## Step 1: selectivity from statistics **Selectivity** is the estimated fraction of rows surviving a predicate, between 0 and 1. Estimated rows = selectivity x table row count. The optimizer derives it from statistics collected in the background and stored in the catalog. Typical ingredients: - **Number of distinct values.** For equality on a column with `d` distinct values and no skew information, selectivity is approximated as `1/d`. - **Most-common-value lists.** For skewed columns, the frequency of specific frequent values is stored, so equality on a frequent value estimates high and on a rare value estimates low. - **Histograms.** Value ranges divided into buckets, used to estimate range predicates. - **Null fraction**, useful for null-related predicates. - **Row count and page count** of the table itself. These are sampled and periodically refreshed, so they are approximations of a moving target. ## Step 2: from estimated rows to path cost With an estimate `N` and table statistics, the optimizer prices each path. **Full scan.** Cost is roughly `page_count x sequential_page_cost + row_count x per_row_cpu_cost`. Note that `N` barely appears; the scan reads everything regardless. This is a near-constant baseline. **Index path.** Cost is roughly: `index descent + (index_pages x N/total) x sequential_cost + row_fetch_cost(N) + N x per_row_cpu_cost` The term that matters is `row_fetch_cost(N)`, which grows with `N` and is priced between the sequential and random page costs, depending on how well the table's physical layout matches index-key order. Both formulas produce abstract cost units, not milliseconds. Their calibration constants encode how much more expensive a random page read is than a sequential one, and how cheap CPU work is by comparison, and those constants are configurable in most engines. ## Step 3: the comparison and its crossover Because the scan's cost is flat in `N` and the index path's rises with `N`, the two lines cross. Below the crossover the optimizer chooses the index; above it, the scan. The choice is therefore not a property of the query text but of the estimated row count for the specific predicate and, when the predicate has parameters, for the specific parameter values. This explains behaviour that otherwise looks arbitrary: - The same query uses an index for one value and a scan for another, because the most-common-value list says one is rare and the other frequent. - Adding a second predicate changes the path, because combined selectivity multiplies down and pushes the estimate below the crossover. - A query that scanned yesterday uses the index today because the table grew, changing both the estimate and the page count. ## Step 4: where estimates go wrong Since the estimate drives everything, its failure modes are the practical content of this topic. - **Stale statistics.** After a bulk load or a large delete, the stored distribution no longer matches reality. Estimates can be off by orders of magnitude. - **Correlated predicates.** Optimizers commonly assume predicate independence and multiply selectivities. For `city = 'Paris' AND country = 'France'` that multiplication badly underestimates, because the two conditions are almost the same condition. Extended or multi-column statistics exist in several engines to repair this. - **Skew without skew statistics.** Uniformity is assumed when no most-common-value information exists, so a value appearing in 90 percent of rows is estimated at `1/d`. - **Opaque expressions.** A predicate wrapping a column in a function, or comparing against a value the optimizer cannot see, falls back to hard-coded default selectivities that are frequently far from the truth. - **Parameter sensitivity.** When a plan is compiled once and reused for many parameter values, the estimate reflects only the value present at compile time. ## Step 5: how to inspect the reasoning Every serious engine can show the plan with **estimated versus actual** row counts per node. That comparison is the single most useful diagnostic in this whole area. If the estimate says 30 rows and reality is 300,000, the path was chosen on a false premise and the fix is upstream, in statistics or in predicate formulation, not in forcing the plan. If estimates match reality and the plan is still poor, the cost model's calibration or the physical layout is the suspect instead. ## The one-sentence version Statistics produce an estimated selectivity; selectivity produces an estimated row count; the row count is fed into a cost formula per access path; the cheapest formula wins. Get the estimate wrong and every downstream decision is wrong with it.
- What do the numbers the optimizer produces actually represent, and can you compare them across two different databases?They are abstract cost units on an internal scale, anchored to configurable constants such as the assumed price of a sequential page read, a random page read, and per-row CPU work. They are meaningful only for comparing candidate plans for the same statement on the same instance with the same configuration. Comparing them across systems, or reading them as milliseconds, is meaningless.
- Two predicates on strongly correlated columns are combined with AND. Why does the optimizer typically underestimate, and what can be done?Most optimizers assume predicates are independent and multiply their selectivities, so two conditions that are effectively the same condition get their fractions multiplied twice and the estimate collapses far below reality. The result is often an index path chosen for what turns out to be a large row set. Remedies include multi-column or extended statistics that record the dependency, rewriting to a single indexed expression, or an index on the combined columns so the estimate comes from one distribution.
saying these in an interview costs you the question
- Believing the optimizer counts the matching rows before choosing a plan
- Treating cost units as milliseconds or comparing them across different databases
- Assuming statistics are exact rather than sampled and periodically refreshed
- Ignoring the independence assumption, so correlated predicates are expected to estimate correctly
- Jumping to forcing an index instead of first comparing estimated with actual row counts