Explain what selectivity and cardinality mean to a query optimizer, how a predicate's selectivity is turned into an estimated row count, and why an error in an early estimate is more damaging than an error in the cost formula.

## Definitions - **Cardinality**: the number of rows a relational expression produces. The optimizer needs it for every intermediate node, not just the final result. - **Selectivity**: the fraction of its input a predicate lets through, between 0 and 1. Selectivity 0.01 means 1% survives. Confusingly, "highly selective" means a *low* fraction — a filter that eliminates most rows. The basic relation is `estimated_rows_out = estimated_rows_in × selectivity`. Everything else in the optimizer is downstream of getting this right. ## How selectivity gets computed Starting from the table's row count and per-column statistics, the optimizer applies formulas per predicate shape: - **Equality on a column, `col = literal`.** If a most-common-value list contains the literal, use its recorded frequency directly — this is what makes skewed columns estimable. Otherwise fall back to uniformity over the remaining distinct values: roughly `1/D`, adjusted for the fraction of rows covered by the MCV list and by nulls. - **Equality with an unknown value** (a bind parameter not yet known, or a value produced at run time): no literal to look up, so the optimizer uses an average — typically `1/D` — or, in some engines, delays the decision until the first execution supplies a value. - **Range, `col > x` / `col BETWEEN a AND b`.** Read off the histogram: sum the buckets fully inside the range and interpolate within the partially covered ones. - **Inequality, `col <> x`.** `1 − selectivity(col = x)`. - **IS NULL.** Directly from the recorded null fraction. - **Opaque predicates** — a user-defined function, a LIKE with a leading wildcard, an expression over a column with no matching statistics — cannot be estimated from statistics, so the optimizer substitutes a fixed default constant. These defaults are guesses and are frequently far off. - **Joins.** The classic estimate for an equijoin on columns with distinct counts D1 and D2 is `rows1 × rows2 / max(D1, D2)`, which assumes containment of the smaller domain in the larger and uniform distribution on both sides. - **Conjunctions and disjunctions.** Combined assuming independence: `sel(A AND B) = sel(A) × sel(B)`, `sel(A OR B) = sel(A) + sel(B) − sel(A) × sel(B)`. ## Why cardinality error dominates plan quality Three compounding reasons. **1. Every cost term is linear or worse in cardinality.** Rows determine CPU terms directly, pages touched by index paths, sort sizes, hash-table sizes. Multiply the row estimate by 1,000 and the plan's cost moves by about the same factor — while getting a cost constant wrong by a factor of two just shifts it by two. **2. Estimates propagate.** The estimated output of one operator is the estimated input of the next. A base-table filter estimated at 100 rows when the truth is 100,000 poisons the join above it, and the join above that. Errors compound multiplicatively up the tree, and the deeper the plan the worse it gets. Empirical studies of optimizers consistently find estimation error growing by orders of magnitude across a few joins, while the cost model itself contributes comparatively little. **3. Errors are not symmetric.** Under-estimation is far more dangerous than over-estimation, because the plans that look attractive for tiny inputs are exactly the ones that degrade catastrophically at scale: a nested loop join whose inner side is re-probed once per outer row is excellent at 50 outer rows and ruinous at 5 million; a hash table sized for a small group count spills hard when the count is huge. Over-estimation usually buys a robust plan that is merely a bit slower than necessary. ## How you see it Every engine's executed plan shows estimated rows next to actual rows per operator. Reading a plan means scanning for the *first* operator, bottom-up, where the ratio blows out — that node is the cause, and everything above it is a consequence. Fixing the topmost symptom is the classic wasted afternoon. ## Where estimates go wrong in practice - **Stale statistics** after a bulk load, a migration, or a data distribution shift. - **Correlated columns**, where the independence assumption multiplies selectivities that should not be multiplied. - **Skew** not captured by the statistics, especially on columns with a few very hot values. - **Opaque predicates**: expressions over columns, function calls, leading-wildcard pattern matches — all fall back to defaults. - **Parameters**: an estimate made from one parameter value reused for a very different one. - **Values outside the histogram range** — a common case for monotonically increasing timestamps, where "today" is beyond the last analyze and gets estimated as nearly empty. ## Remedies Refresh and, where supported, increase the resolution of statistics on the offending columns; create multi-column statistics for correlated predicates; make opaque predicates estimable by materializing the expression into a column with its own statistics; break parameter sensitivity by recompiling or by splitting the workload; and, where the engine offers it, use feedback mechanisms that re-plan using observed rather than estimated cardinalities. Pinning a plan is the blunt last resort — it hides the error rather than fixing it, and it must be revisited as the data moves. ## The sentence to leave in the interviewer's head Optimizers rarely fail because the cost model mispriced a page read; they fail because they were told the wrong number of rows, and every decision above that point inherited the mistake.