Cardinality estimation and histograms
Estimate surviving and joined rows from distributions while identifying where skew, correlation, NULLs, and sampling defeat simple assumptions.
On this page
The question for today
What you’ll understand
- Turn a selectivity estimate into an estimated row count.
- Distinguish common-value frequencies from the residual histogram population.
- Quantify the effect of correlated predicates on an independence estimate.
A planner must choose algorithms before it knows how many rows each operator will actually produce. Cardinality estimation supplies those predictions. It is an inference problem built from incomplete summaries, not a count obtained by running the query. Good diagnosis asks which distributional assumption was wrong and how that error influenced downstream work, instead of treating every estimate as an unexplained optimizer preference.
Separate base size from the surviving fraction
Begin with a relation-size estimate and a predicate selectivity between zero and one. Their product predicts surviving rows. The base estimate may itself come from sampled or previously collected statistics, adjusted for table growth, rather than an exact current count. Changes in data volume, distribution, and parameter values can all matter. A table with the right total size but a newly dominant tenant can still have a badly estimated tenant filter. Record the relevant parameter and statistics age when comparing the plan with observed rows.
Most-common-value frequencies describe selected individual values. A residual histogram summarizes the distribution not represented by those common values, with NULL fractions handled separately. Equal-frequency histogram buckets contain approximately equal population, not equal numeric width. Estimating a threshold within a bucket requires another assumption about how that population is distributed inside it. A histogram is therefore not a detailed lookup table of every possible value. Increasing its detail can help some distributions, but it cannot make missing cross-column relationships appear automatically.
Independent conditions multiply only when independence is justified
For two conditions, the correct joint probability is the probability of the first multiplied by the conditional probability of the second given the first. Replacing that conditional probability with the second condition's marginal probability assumes independence. Postal region and country, product family and model, or two columns copied from one another can violate it dramatically. The resulting underestimate can encourage a repeated lookup strategy that is cheap for a handful of rows and expensive for thousands. Correlation is about the filtered population, not merely a vague statement that columns are related.
Extended statistics can capture selected dependencies, joint common values, or distinct-count information for supported cases. They are not a general multitable distribution model, and the planner need not use every statistic for every expression. Join estimation adds overlap of key domains, key multiplicities, foreign-key knowledge, and the effects of previous filters. A simple uniform key model can be useful for reasoning, but a hot key can dominate output and memory. Check where the first large row-count discrepancy appears instead of blaming a later join solely because it emits the final large result.
Sampling uncertainty is not the same as model bias
Statistics collection usually examines a sample, introducing ordinary sampling error. A simplified distribution family introduces a different problem: even an enormous sample cannot repair a model that deliberately discards the relevant relationship. Distinguish these causes before changing collection targets. Compare several representative parameter values, including common and rare cases, and preserve the same data snapshot when possible. If the application mixes tenants with very different distributions, a plan that works for an average parameter may be unsuitable at either extreme.
The sampling lab isolates sampling variability under an assumption. Reset, set both p=0.2 and n=20, predict sample-mean variance 0.008, then Play or Step. Separately Reset, set both p=0.2 and n=80, predict variance 0.002, then Play or Step. The bars are exact binomial masses and playback highlights outcomes, not new random samples. Real table sampling, clustered rows, correlated predicates, and planner histograms are absent. Explain why reducing this modeled variance does not by itself correct a biased independence estimate.
Work it through
Two accurate marginals can produce a bad joint estimate
A table has 200,000 rows. Exactly ten percent have region R, exactly ten percent have country C, and every R row is a C row. Estimate WHERE region=R AND country=C using independence, then compare with the stated population.
The independence estimate multiplies 200,000 × 0.1 × 0.1, predicting 2,000 rows. Each marginal estimate is individually correct.
Because every R row also has C, the conditional probability P(C|R) is one. The actual qualifying count is 200,000 × 0.1 × 1 = 20,000 rows.
The estimate is ten times too small. An accurate dependence model for this supported predicate case could repair the joint estimate; merely recollecting the same two independent marginals cannot encode the missing conditional relationship.
A cardinality error can come from a structural assumption even when both table size and single-column selectivities are accurate.
The living notebook
Explore the model
Interactive lab · sampling
Separate sampling variance from a missing dependency
Reset, set both p=0.2 and n=20, predict variance of the sample mean 0.008, then Play or Step. Separately Reset, set both p=0.2 and n=80, predict 0.002, then Play or Step. This is an exact independent Bernoulli sampling distribution, not a table sampler or cardinality estimator.
- Mean sample proportion
- 0.5
- Sample-mean variance
- 0.0125
- Uniform CDF error bound
- ≤ 0.1062
Exact binomial masses for the mean of n independent Bernoulli trials, compared with normal mass between adjacent half-count boundaries; normal tails outside the finite support remain outside the bars. Playback highlights outcomes, not random samples. The Berry–Esseen bound applies to standardized CDFs, not individual bars or continuity-corrected errors. At p = 0 or 1, normal comparison and that bound are disabled. Normal-CDF evaluation uses a numerical approximation with absolute error below 7.5×10⁻⁸ (at most 1.5×10⁻⁷ per interval, before rounding). Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forA larger independent sample narrows this distribution but does not encode a cross-column relationship the model ignores.
Pause & reason
Check your understanding
Your turn
Try it yourself
In a teaching equality estimate, NULLs occupy 0.1 of rows and stored common values occupy 0.3. There are sixty remaining distinct non-NULL values, assumed equally frequent. Estimate one such remaining value's selectivity and row count in 120,000 rows.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Remove the NULL and common-value masses before dividing the residual mass.
Compare with the solution
The residual mass is 1−0.1−0.3=0.6. Dividing by sixty gives selectivity 0.01 and an estimated 1,200 rows. The result assumes equal residual frequencies and a value in that residual domain; it is not exact for arbitrary skew or an absent value.
Keep the idea
Take it with you
- Row counts depend on both base-size estimates and predicate selectivity.
- Histograms and common-value lists describe different parts of a distribution.
- Distinguish sampling variability from correlation or skew omitted by a model.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.