Selectivity Estimation from Histograms and Most-Common-Value Lists

The cost model described in the anatomy of planner costs multiplies a row count by a selectivity. That selectivity is not measured. It comes from a small summary of the column’s distribution, collected by an explicit or automatic statistics-gathering command and stored in the catalog, and the quality of the resulting plan is bounded by the quality of that summary. A histogram over a million distinct values compressed into a few hundred buckets is a lossy sketch, and every estimator built on it is a guess with a documented procedure.

The design problem is that a full value-frequency map would be exact and enormous. A column with a million distinct values needs a million counters, and the counter table would need to be rewritten whenever the data changed. Statistics have to be cheap to collect, cheap to store, and cheap to consult during planning, which means they must be a fixed-size sketch. Three families of sketch are in use, and the choice among them determines which predicates are estimated well.

Equidepth buckets put equal mass in each bucket

A range histogram divides the value domain into buckets and stores, per bucket, the count of rows falling inside. The naive layout is equiwidth: split the domain from minimum to maximum into k intervals of equal width. It is trivial to compute a bucket boundary from a constant, and it fails badly on skewed data. A column where 90 percent of rows are zero and the rest spread over a wide range puts almost all mass in the first equiwidth bucket, so a predicate on that bucket estimates 90 percent of the table for any range inside it.

The equidepth layout instead chooses boundaries so that each bucket holds roughly the same number of rows. With 100 buckets, each covers about 1 percent of the table. A range predicate then estimates by finding which buckets the range overlaps and interpolating within the boundary buckets, assuming values are uniformly distributed inside each one. Skew within a bucket is invisible, so accuracy degrades as the bucket count falls relative to the distinct-value count, but the error is bounded by the bucket’s mass rather than by the whole table’s.

Boundary handling is where implementations differ. A range from a to b that fully contains several buckets contributes their full counts. A range that ends inside a bucket contributes a fraction of that bucket proportional to the fraction of the bucket’s value span covered. This interpolation assumes uniformity, and for a bucket spanning values 1000 through 1010 with 5000 rows, a predicate x <= 1005 is estimated at roughly half the bucket, or 2500 rows, regardless of the actual distribution of those eleven values. Narrow ranges inside a single bucket are therefore the worst case for a range histogram, and a common reason for a wrong row count on a query that looks selective.

def range_selectivity(buckets, lo, hi):
    """buckets: list of (min_value, max_value, rows), roughly equal mass each."""
    total = sum(rows for _, _, rows in buckets)
    matched = 0.0
    for bmin, bmax, rows in buckets:
        if bmax < lo or bmin > hi:
            continue
        span = bmax - bmin + 1
        overlap = min(bmax, hi) - max(bmin, lo) + 1
        matched += rows * overlap / span  # uniform within the bucket
    return matched / total

The bucket count is a per-column target, not a guarantee. PostgreSQL’s default_statistics_target is 100 by default, and it is interpreted per column and per statistic type rather than as a total budget, so a column with a histogram and a most-common-value list consumes roughly twice that number of stored entries. Raising the target for a specific column is done with ALTER TABLE ... ALTER COLUMN ... SET STATISTICS, and it is the correct response when a column’s distribution matters and 100 buckets cannot resolve it. The cost is a longer ANALYZE and more catalog rows, both small next to the plan risk.

The most-common-value list covers what the histogram cannot

Frequent values are exactly the ones a histogram handles worst, because a bucket containing a very common value has that value’s mass averaged across its whole span. Every serious implementation therefore extracts the top k values by frequency into a separate list, storing each value with its exact frequency, and excludes those values from the histogram so the buckets describe only the residue.

The estimate for col = constant then takes one of three branches. If the constant appears in the most-common-value list, the estimate is the stored frequency, which is exact as of the last statistics collection. If it does not, the estimator assumes the value is one of the non-frequent distinct values and divides the remaining row mass by the remaining distinct count. For a column with 10,000 distinct values of which 50 are listed, a non-listed constant is estimated at (rows minus listed mass) divided by 9,950.

This branch is why estimates for equality predicates on unique columns are reliable and estimates on non-unique, non-listed values can be off by orders of magnitude. The residual-distinct formula is a uniformity assumption across the entire tail, so a column with 9,000 values appearing once and 950 appearing a hundred times each produces the same estimate for a member of either group. Increasing the statistics target is the only lever: more listed values shrink the tail the formula has to guess about.

Null fractions are tracked separately and apply before either branch. A predicate col = 5 is estimated as (1 minus null fraction) times the value selectivity, and col IS NULL uses the null fraction directly. A column that is 99 percent null and has one common value will have that value’s frequency stored against the non-null population, and mixing the two produces an estimate that is wrong by a factor of a hundred. Products that store the null fraction alongside the distinct count get this right; the failure mode shows up when the fraction is stale.

Distinct counts, and what they cost to maintain

A distinct-value count answers SELECT COUNT(DISTINCT col) without scanning, and it feeds the residual-value formula above. Exact maintenance of a distinct count requires tracking every value, which is why the catalog usually stores an estimate produced during sampling rather than an exact figure, and why the number can move between two runs of ANALYZE on unchanged data.

The interaction with multi-column statistics is the interesting part. Two columns that are functionally dependent, such as a city and its postal code, each have their own distinct counts, and the product of the two is a gross overestimate of the distinct pairs. A planner that assumes independence on a join or a grouped aggregate will price the operation as if it produced far more groups than it does. Extended statistics address this by collecting a distinct count over the column combination, and the estimator can then apply a correction factor derived from the ratio of the combined count to the product of individual counts.

Why single-column statistics break on correlated predicates

The estimator combines independent predicates by multiplying their selectivities. WHERE city = 'Paris' AND country = 'France' is estimated as the selectivity of each condition times the other, which yields a fraction of a percent of the table even though the second condition is implied by the first. The result is an estimate too low by orders of magnitude, and the planner responds by choosing a nested loop over an index when a hash join and a sequential scan would be correct. This is the most common single cause of a plan that is catastrophic rather than merely suboptimal.

The same multiplication applies to WHERE a = 1 AND b = 2 on two columns that are individually selective but jointly common, such as a status flag and a timestamp bucket. Nothing in a per-column histogram can detect either situation, because the correlation lives in the joint distribution and the sketch discards it.

Three mitigations exist, and each has a cost. Extended statistics collect a joint distinct count and, in some products, a multivariate histogram over a small set of column groups; they must be declared, they cost collection time proportional to the group size, and they only cover the groups someone thought to declare. Expression statistics let the planner estimate a predicate on a computed expression by collecting a histogram over that expression, which handles the case where the correlation is inside a function call. The third mitigation is not a statistic at all: rewriting the predicate so the implication is explicit, which is a schema-and-query change rather than a planner one.

Sampling, staleness, and the cost of being current

Statistics are collected from a sample, not a full scan, in most systems. PostgreSQL’s ANALYZE takes a sample sized by the statistics target and scales the observed frequencies up to the table’s row count, and the sample is drawn from pages rather than rows so that the read cost is bounded. A sample of a few thousand rows estimates a frequency of 0.1 percent with a relative error around a few percent, and estimates a frequency of 0.001 percent poorly, because such a value may not appear at all.

The sampling design produces one specific artefact worth knowing: the estimate for a value that appears exactly once in the sample is the same regardless of whether it appears once or four times in the table, since the scaling factor is applied to an observed count of one. Values at the boundary of the most-common-value list are the least stable entries in the catalog, and two consecutive ANALYZE runs can move a value in or out of the list, changing the estimate by an order of magnitude and, occasionally, the plan.

Staleness is the other half. Automatic statistics collection triggers on a fraction of the table having changed, typically ten percent of rows for a large table, which means a table that grows by nine percent has statistics describing the previous shape of the data. Bulk loads that append a new value range are the classic case: the histogram’s maximum is below the new values, so any predicate on the new range is estimated as matching nothing, and the plan chosen for it is appropriate for an empty result. Running statistics collection after a bulk load is not a tuning refinement; it is the step that makes the estimates describe the table that exists.

None of this is visible in the query text. A predicate that returns a million rows and one that returns ten are the same characters, and the difference between a good plan and a bad one is entirely in a sketch collected at some earlier time. The next layer of the problem, where several such estimates must be combined across a join, is covered in join cardinality and the containment assumption, and that is where the errors compound rather than merely appear.