skip to content

Which per-column statistics does a cost-based optimizer typically store, and what does a most-common-value list give you that a plain distinct-value count cannot?

level: middleimportance: must knowfreq 48%

answer

  1. NDV, null fraction, MCV, histogram, width, correlation
  2. NDV alone ⇒ uniformity assumption
  3. selectivity ≈ (1 - nullfrac) / NDV
  4. MCV = measured frequency for skewed values
  5. MCV mass removed ⇒ better tail estimates too

basics

~20 s

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.

solid answer

~50 s

The standard set is: **NDV** (distinct values), **null fraction**, an **MCV list** (top-k values plus their frequencies), a **histogram** over the non-MCV remainder, **average value width**, and often a **physical-order correlation** figure. With only NDV, the optimizer must assume a uniform distribution: selectivity of `col = ?` is `(1 - null_fraction) / NDV`. That is fine for an identifier-like column and badly wrong under skew. Take a `status` column with 6 values where `'COMPLETED'` is 97% of rows and `'FAILED'` is 0.1%. Uniformity says both are ~16.7%. Reality differs by three orders of magnitude, and so does the right plan: index scan for `'FAILED'`, sequential scan for `'COMPLETED'`. The MCV list fixes exactly this. If the literal is in the list, its recorded frequency is used directly. If not, the optimizer subtracts the MCV mass and spreads the remainder over the remaining distinct values — which is also why a good MCV list improves estimates for the values it does *not* contain.

code

text · 6 lines
text
status column, 100,000,000 rows, NDV = 6

              actual     NDV-only est.   with MCV list
COMPLETED     97.0%      16.7%           97.0%
PENDING        2.5%      16.7%            2.5%
FAILED         0.1%      16.7%            0.125%

go deeper

for a junior

List the statistics and say NDV assumes every value is equally common while the MCV list records real frequencies for the common ones.

for a middle

Give the selectivity formula, work a skewed example, and explain how the estimate flips the access-path choice.

for a senior

Add the limits — tail values, cross-column correlation, MCV staleness on migrating status columns — and connect skew to parameter-sensitive cached plans.

for a principal

Reason about which columns deserve raised statistics targets or extended statistics as a cost/benefit call across the fleet, not per query.

## The standard per-column statistics | statistic | what it is | what it estimates | |---|---|---| | NDV | number of distinct non-null values | equality selectivity under uniformity | | null fraction | share of rows that are NULL | `IS NULL` / `IS NOT NULL` | | MCV list | top-k values with frequencies | equality on skewed values | | histogram | distribution of non-MCV values | range predicates | | average width | mean bytes per value | row size, memory grants | | correlation | how closely logical order matches physical order | random vs sequential I/O cost for index scans | Most engines let you tune the target size (number of MCV entries / histogram buckets) per column. ## Why NDV alone is not enough The uniformity assumption is the default fallback: with `n` rows, NDV `d`, and null fraction `f`, the estimate for `col = <literal>` is `n * (1 - f) / d`. This is a reasonable approximation for high-cardinality, evenly-spread columns such as surrogate keys or hashes. Real business columns are rarely uniform. Status flags, country codes, tenant identifiers, event types and boolean-ish columns are all heavily skewed — a handful of values dominate and a long tail is nearly empty. Under skew, uniformity is wrong in *both* directions at once: it wildly under-estimates the dominant value and wildly over-estimates the rare one. Both errors produce bad plans, and the rare-value case is the dangerous one because it is exactly the query users run. ## What the MCV list adds The MCV list stores the top-k values by frequency together with the *measured* fraction of rows each holds. - If the query's literal is in the list, the optimizer uses the stored frequency directly. This is the single largest accuracy win available on skewed columns. - If it is not in the list, the optimizer subtracts the total MCV mass and the null fraction, then spreads the remainder uniformly across `NDV - k` remaining values. So capturing the heavy hitters also **improves accuracy for the tail**, because the tail no longer has to absorb the heavy hitters' share. Concretely: `status` with 6 values, `'COMPLETED'` at 97%, `'PENDING'` 2.5%, four others sharing 0.5%. NDV-only estimates every value at 16.7%. With an MCV list of the top two, `'COMPLETED'` estimates at 97%, `'PENDING'` at 2.5%, and each of the remaining four at 0.125% — all close to the truth. That difference decides the plan. At 0.1% of a 100M-row table, an index scan touching ~100k rows is right. At 97%, an index scan would touch nearly every row through random I/O plus table lookups; a sequential scan is dramatically cheaper. Same query text, different literal, opposite correct plans — which is also why plan caching of parameterized statements over skewed columns is treacherous. ## What the MCV list does *not* solve 1. **Values not in the list still get uniform treatment** within the remainder. A column with thousands of moderately-skewed values needs a bigger MCV target or a better histogram, not just the default top-k. 2. **Cross-column correlation.** Per-column statistics assume independence: the estimate for `country = 'FR' AND city = 'Paris'` is the product of two selectivities, which grossly under-estimates because the predicates are correlated. Fixing this needs multi-column/extended statistics, which most engines support as an explicit opt-in. 3. **Freshness.** An MCV list is a snapshot. A column whose hot value shifts over time — a `state` column where rows migrate from `'NEW'` to `'DONE'` — has an MCV list that ages badly even when the row count barely changes. 4. **Skew that is not value-based**, such as time-clustered inserts, is a histogram-boundary problem rather than an MCV one. ## What to say in an interview Lead with the list of statistics, then the one crisp sentence that shows you understand the mechanism: *NDV forces a uniformity assumption; the MCV list replaces that assumption with measured frequencies for the values where the assumption is most wrong, and by removing their mass it also sharpens the estimate for everything else.*

  • Why does a good MCV list improve estimates even for values that are not in it?
    Because the optimizer subtracts the total frequency mass of the MCV entries and the null fraction before spreading what remains over the remaining distinct values. Without the list, the heavy hitters' share is smeared across every value, inflating estimates for rare ones. Capturing the heavy hitters removes that distortion from the tail.
  • What kind of estimation error do per-column statistics fundamentally cannot fix?
    Correlation between columns. Per-column statistics force an independence assumption, so the selectivity of two predicates is estimated as the product of their individual selectivities. For correlated columns such as country and city, or manufacturer and model, that under-estimates badly. The remedy is multi-column or extended statistics, which most engines require you to declare explicitly.
  • Why can a cached plan be dangerous on a skewed column?
    Because the right plan depends on the literal. A parameterized query on a column where one value covers 97% of rows and another covers 0.1% wants a sequential scan for the first and an index scan for the second. A plan cached from the first execution can then be badly wrong for later parameter values, which is the classic parameter-sensitivity problem.

saying these in an interview costs you the question

  • Assuming uniform distribution is 'usually fine' for business columns like status or country
  • Confusing NDV with row count
  • Thinking an MCV list stores all distinct values rather than the top-k
  • Believing per-column statistics can capture correlation between two columns
  • Saying the same plan must be right for every literal on a given column

context

resolving links…