Optimizer statistics are usually gathered from a sample of rows rather than a full scan. What error does sampling introduce, and which statistic is hardest to estimate accurately from a sample?
answer
- Full scan too costly ⇒ block-level sampling
- Proportions (nulls, widths, quantiles) extrapolate fine
- NDV is the hard one — singletons are ambiguous
- Long tails ⇒ systematic under-estimation
- NDV sits in the join-cardinality denominator
basics
~20 sSampling 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.
solid answer
~1 minGathering statistics with a full scan of a billion-row table would cost as much as a full query, so engines sample — typically a fixed number of rows or a percentage, read as random blocks. Most statistics extrapolate well. Row counts and null fractions are simple proportions with error shrinking as the square root of sample size. Histogram boundaries are quantile estimates and are also fairly robust: an equi-depth boundary is stable because it depends on rank, not on rare values. **NDV is the exception**, and it is a known-hard problem. Whether a value appears once in a sample tells you almost nothing about whether it appears once or a thousand times in the table, and values absent from the sample are invisible. Estimators exist but all have adversarial cases; with a long tail of rare values NDV is typically under-estimated. That matters because equality selectivity is roughly `1/NDV`. Under-estimating NDV inflates the estimated rows per value, which propagates into join cardinality estimates and can flip both the join method and the join order. Block-level sampling adds a second problem: physically clustered values make a block sample less diverse than a true random row sample, biasing NDV further down.
code
text · 6 linessample: 30,000 rows -> 12,000 distinct, 9,000 seen exactly once
case A: those singletons are truly rare -> table NDV ~ tens of millions
case B: you hit each of 20,000 values once -> table NDV ~ 20,000
same sample, 1000x difference in NDV, no way to tell them apartgo deeper
Know that statistics come from a sample, so they are approximate, and that distinct-value counts are the least trustworthy part.
Explain why proportions extrapolate but distinct counts do not, and connect NDV to equality selectivity.
Add the join-cardinality denominator, the block-sampling clustering bias, and targeted remedies such as raising per-column targets or pinning NDV.
Weigh gathering cost against plan stability fleet-wide: which columns justify larger samples or exact/sketch-based distinct counts, and where a manually pinned value is the cheaper guarantee.
## Why sampling at all Computing exact statistics means reading every row: exact NDV needs a distinct count over the whole column, exact histograms need a full sort. On large tables that costs as much as running a large query, and statistics must be refreshed regularly. So engines sample — often a fixed row target (tens of thousands of rows, scaled by the statistics target) or a percentage — and extrapolate. Sampling is almost always **block-level** in practice: reading random individual rows would mean one random I/O per row, so engines pick random pages and take the rows within them. This is much faster and introduces a bias we will return to. ## What extrapolates well - **Row count**: usually taken from table metadata or extrapolated from page counts and average row width. Accurate enough. - **Null fraction**: a simple proportion. Standard sampling error, shrinking with the square root of the sample size; a 30,000-row sample estimates a proportion to well under a percentage point. - **Average value width**: another mean; extrapolates fine. - **Histogram boundaries**: these are quantile estimates. Quantiles depend on rank, not on individual rare values, so they are robust — a modest sample places equi-depth boundaries close to their true positions. - **MCV frequencies**: heavy hitters are, by definition, well represented in any sample. Their frequencies estimate accurately. What is uncertain is the *cutoff*: which borderline values deserve a slot in the list. ## What does not: distinct-value count NDV estimation from a sample is a genuinely hard problem with a well-known negative result: no estimator can guarantee small error across all distributions without sampling a large fraction of the data. The intuition is easy to state. Suppose your sample of 30,000 rows from a 100-million-row table contains 12,000 distinct values, 9,000 of which appear exactly once. Are those singletons rare values that each appear once in the whole table — implying an NDV in the tens of millions? Or are they members of a moderately-sized value set that you happened to hit once each — implying an NDV of maybe 20,000? **The sample cannot distinguish these cases**, yet they differ by three orders of magnitude. And values absent from the sample contribute nothing at all, so the tail is systematically invisible. Estimators in use (Chao, Shlosser, the Gee estimator, hybrid schemes) work from the counts of values seen exactly once, exactly twice, and so on, to guess how much mass is hidden. Each has adversarial distributions where it is badly wrong. The practical tendency across all of them is **under-estimation on long-tailed distributions** — precisely the shape real data usually has. ## Why NDV error hurts more than other errors Equality selectivity for a non-MCV value is approximately `(1 - null_fraction) / NDV`. Under-estimate NDV by 10x and you over-estimate rows-per-value by 10x. Worse, NDV feeds **join cardinality estimation**. The textbook estimate for an equijoin is `|R| * |S| / max(NDV_R, NDV_S)`. NDV therefore sits in the denominator of the single most consequential estimate in the plan. A 10x NDV error becomes a 10x join cardinality error, which compounds multiplicatively through a deep join tree and readily flips both the join algorithm and the join order. ## The block-sampling bias Block sampling reads all rows from a set of random pages. If equal values are physically clustered — which they usually are, because data arrives in batches or is loaded sorted — then a sampled page contributes many copies of the same few values. The sample looks *less* diverse than the column really is, pushing NDV estimates further down. This is why a column can have accurate histograms and a badly wrong NDV at the same time. ## What to do about it 1. **Raise the statistics target** on the specific columns whose NDV matters — high-cardinality join keys and heavily-filtered predicates. A larger target means a larger sample and usually a better NDV estimate, at the cost of a longer gathering pass. 2. **Pin NDV manually** where the true value is known and stable. Most engines allow overriding a column's distinct-value figure (for instance as a negative ratio meaning "distinct values scale with row count"). For a column you know is unique-per-row or has a fixed small domain, this eliminates the error outright. 3. **Prefer exact where cheap.** Some engines compute exact NDV when the table is small enough, or use sketch-based estimators (HyperLogLog-style) that give bounded relative error from a single pass. 4. **Recognize the symptom.** A join whose estimate is off by a large factor while the underlying scan estimates are accurate points at NDV or at correlation, not at row counts. 5. **Do not fix it by raising the global sample size.** Gathering cost is paid on every refresh across every table; targeted increases are the right shape of intervention. ## The one-line takeaway *Proportions sample well; counts of distinct things do not. NDV is the statistic most likely to be wrong, it is usually wrong in the direction of too small, and it sits in the denominator of the join cardinality estimate.*
- Why does an NDV error matter more than an equally sized error in the null fraction?Because NDV appears in the denominator of both equality selectivity and the standard equijoin cardinality formula, so its error scales the most consequential estimate in the plan and compounds up the join tree. A null-fraction error shifts one scan's estimate by a bounded proportion and rarely changes the plan shape.
- How does block-level sampling bias distinct-value estimation?Block sampling takes all rows from randomly chosen pages. If equal values are physically clustered — common when data is loaded in batches or sorted order — each sampled page yields many duplicates, so the sample appears less diverse than the column truly is. That pushes the NDV estimate downward on top of the estimator's own long-tail bias.
- What can you do when you know the true distinct-value count and the optimizer does not?Most engines let you override a column's distinct-value statistic explicitly, often expressed as an absolute count or as a negative ratio meaning distinct values scale with row count. For a column you know is unique per row or has a fixed small domain, pinning it removes the estimation error entirely, at the cost of a manual value that must be revisited if the data's nature changes.
Estimating how many distinct surnames a country has by sampling one street: you can nail the share of people who are left-handed, but the number of surnames you never met is unknowable from that street.
saying these in an interview costs you the question
- Assuming statistics are computed from a full scan of the table
- Believing a bigger sample always fixes distinct-value estimation
- Thinking distinct-value counts extrapolate linearly from a sample
- Ignoring that NDV errors propagate into join cardinality, not just single-table filters
- Raising the global sampling target to fix one column's estimate