vault

Database Statistics and Cardinality Estimation

12 min read

Database Statistics and Cardinality Estimation

Every decision a cost-based optimizer makes — index or scan, hash or nested loop, which join order — rests on one prediction: how many rows will this operation produce? The optimizer cannot run the query to find out, so it estimates cardinalities from compact statistical summaries of each column: how many distinct values it holds, which values are most common and how frequent, and how the rest are distributed across a histogram. From these it computes a selectivity (the fraction of rows a predicate passes) and multiplies by the table’s row count. The estimates are built on two load-bearing assumptions — uniformity (values within a histogram bucket are evenly spread) and independence (predicates on different columns are unrelated) — and when real data violates them, especially for correlated columns, the estimates fail by orders of magnitude. This is not a minor detail: Leis et al.’s landmark study concluded that “cardinality estimation errors are the dominant cause of sub-optimal plans” and that these errors “grow exponentially with the number of joins” (Leis et al., How Good Are Query Optimizers, Really?, VLDB 2015). Cardinality estimation is the optimizer’s single greatest weakness — and understanding it is the key to diagnosing almost every mysteriously slow query.

Mental Model

A database cannot afford to scan a table to answer “how many rows match x > 5000?” every time it plans a query — so it keeps a thumbnail of each column’s distribution, gathered periodically by sampling (PostgreSQL’s ANALYZE), and reasons about that thumbnail instead. The thumbnail has three parts: a count of distinct values, a list of the few most common values with their exact frequencies, and a histogram summarizing the long tail. To estimate a predicate’s selectivity, the optimizer asks the thumbnail — is this value one of the common ones (use its exact frequency)? is it a range (measure how much of the histogram it covers)? — and combines multiple predicates by assuming they are independent (multiply the selectivities). That last assumption is the fragile one: real columns are often correlated (a city and its zip code, a car’s make and model), and multiplying independent selectivities for correlated columns produces catastrophic underestimates.

flowchart TB
  ANALYZE["ANALYZE samples the table"] --> STATS["Per-column statistics (pg_statistic / pg_stats)"]
  STATS --> NF["null_frac"]
  STATS --> ND["n_distinct"]
  STATS --> MCV["most_common_vals + most_common_freqs"]
  STATS --> HIST["histogram_bounds (equi-depth)"]
  PRED["Predicate: col = v / col < v / col1=col2"] --> SEL{"Estimate selectivity"}
  MCV --> SEL
  HIST --> SEL
  ND --> SEL
  SEL --> ROWS["rows = table_cardinality × selectivity"]
  P2["Predicate on col A AND col B"] --> IND["assume independence:<br/>sel = sel_A × sel_B"]
  IND -.->|"breaks when A,B correlated<br/>→ huge underestimate"| WRONG["catastrophic misestimate"]
  WRONG --> FIX["CREATE STATISTICS<br/>(dependencies / ndistinct / mcv)"]

How row estimates are produced and where they break. What it shows: ANALYZE samples the table into per-column statistics (null fraction, distinct count, a most-common-values list, and an equi-depth histogram); the optimizer turns a predicate into a selectivity using the relevant piece, then scales the table’s row count. The insight to take: single-column estimates are usually good; the disaster is the independence assumption for multiple predicates — multiplying sel_A × sel_B for correlated columns can be off by orders of magnitude, which is exactly what multi-column extended statistics (CREATE STATISTICS) exist to repair.

What Statistics Are Gathered

PostgreSQL collects statistics with the ANALYZE command (also run by autovacuum), storing them in the pg_statistic catalog and exposing them readably through the pg_stats view. They “are always approximate even when freshly updated,” because ANALYZE samples rather than scanning the whole table (PostgreSQL, Planner Statistics). The per-column values that matter (PostgreSQL, pg_stats):

  • null_frac — the fraction of the column that is NULL.
  • n_distinct — the number of distinct values. If positive, it is the estimated count; if negative, it is the negative of the ratio of distinct values to rows, so -1 means “every value is distinct” (a unique column) and the estimate scales with the table as it grows. This encoding lets the estimate stay correct for a growing unique key.
  • most_common_vals (MCV) and most_common_freqs — a list of the most frequent values and their exact measured frequencies. This captures skew: the handful of values that appear far more often than average get their true frequency stored rather than being averaged away.
  • histogram_bounds — an equi-depth (equal-frequency) histogram of the remaining, non-MCV values: a list of boundary values chosen so that roughly the same number of rows falls between each adjacent pair.
  • correlation — how well the physical row order matches the column’s sort order (used by The Index versus Sequential Scan Decision, not by cardinality estimation directly).

The amount of detail — the maximum number of MCV entries and histogram buckets — is set by default_statistics_target, whose “default limit is presently 100 entries” (PostgreSQL, Planner Statistics; runtime-config-query). Raising it gives finer histograms (better estimates on skewed data) at the cost of slower ANALYZE and larger stats.

Equi-width vs equi-depth histograms

A histogram summarizes a distribution as buckets. An equi-width histogram uses buckets of equal value range (e.g. 0–100, 100–200, …) — simple, but terrible for skew: if 90% of rows fall in one range, that bucket’s single count says nothing about the distribution within it. An equi-depth (equi-height) histogram instead makes each bucket hold roughly the same number of rows, so buckets are narrow where data is dense and wide where it is sparse — adapting automatically to skew. PostgreSQL (and most modern engines) use equi-depth histograms, which is why the boundary values in histogram_bounds are unevenly spaced.

The Selectivity Formulas — Worked

All the following are from PostgreSQL’s own worked examples on a table tenk1 with 10,000 rows (PostgreSQL, Row Estimation Examples). The optimizer first fixes the base cardinality by reading reltuples/relpages from pg_class and scaling, then applies a selectivity.

Range predicate → histogram. For WHERE unique1 < 1000 with histogram_bounds = {0,993,1997,3050,...,9995} (10 buckets), the value 1000 lands in the second bucket (993–1997), and:

selectivity = (1 + (1000 - 993)/(1997 - 993)) / 10
            = 0.100697
rows = 10000 * 0.100697 = 1007

The (value − bucket.min)/(bucket.max − bucket.min) term interpolates within the bucket — this is exactly the uniformity assumption in action: it presumes values are evenly spread inside the bucket.

Equality on a common value → MCV. For WHERE stringu1 = 'CRAAAA' where 'CRAAAA' is in most_common_vals with most_common_freqs entry 0.003, the estimate uses the stored exact frequency directly:

selectivity = mcf[3] = 0.003
rows = 10000 * 0.003 = 30

Equality on a non-common value → the “everything else” formula. For WHERE stringu1 = 'xxx' (not in the MCV list), the selectivity spreads the non-MCV probability mass over the non-MCV distinct values:

selectivity = (1 - sum(mcv_freqs)) / (n_distinct - num_mcv)
            = (1 - 0.03033) / (676 - 10) = 0.0014559
rows = 10000 * 0.0014559 = 15

When there is no MCV list at all, this collapses to the classic 1/n_distinct uniform-equality estimate — the ancestor of System R’s F = 1/ICARD(column index) for column = value (Selinger et al. 1979).

Join equality → the join-selectivity formula. For t1.unique2 = t2.unique2 on two unique columns (n_distinct = -1, no MCVs):

selectivity = (1 - null_frac1)(1 - null_frac2) / max(n_distinct1, n_distinct2)
rows = (outer_card * inner_card) * selectivity

Dividing by the larger distinct-count is the containment assumption — every value of the smaller-domain side has a match in the larger. This is the direct descendant of System R’s col1 = col2 rule, F = 1/MAX(ICARD(col1 index), ICARD(col2 index)).

The Two Fatal Assumptions

Uniformity — values within a histogram bucket are evenly distributed — is usually a mild error, smoothed by having up to 100 buckets. The dangerous one is independence: for a conjunction, PostgreSQL “assumes independence and multiplies selectivities”:

selectivity(A AND B) = selectivity(A) * selectivity(B)

This is correct only when the columns are statistically independent. When they are correlated, it is catastrophically wrong. PostgreSQL’s own extended-statistics documentation demonstrates it with a table where columns a and b are made identical (PostgreSQL, Multivariate Statistics Examples):

CREATE TABLE t (a INT, b INT);
INSERT INTO t SELECT i % 100, i % 100 FROM generate_series(1, 10000) s(i);
ANALYZE t;
EXPLAIN SELECT * FROM t WHERE a = 1 AND b = 1;
--  Estimated rows: 1     Actual rows: 100

Each predicate alone has selectivity 0.01 (100 distinct values), so independence gives 0.01 × 0.01 = 0.0001, i.e. 1 row. But because a always equals b, the second predicate adds no filtering — the true answer is 100 rows. A two-orders-of-magnitude underestimate from a two-column conjunction. Real-world correlations (city and zip_code, country and language, make and model) produce exactly this, and each such factor multiplies the error. Underestimates are especially dangerous because they push the optimizer toward nested-loop joins and non-covering index plans that are ruinous when the real row count is large — see Join Algorithms and Cost-Based Query Optimization.

Extended (Multi-Column) Statistics — the Fix

PostgreSQL’s remedy is CREATE STATISTICS, which gathers multivariate statistics over a group of columns (PostgreSQL, CREATE STATISTICS; Multivariate Examples). Three kinds, each targeting a different failure:

Functional dependencies capture “column a determines column b,” so a filter on b is redundant once a is fixed. Applied to the example above:

CREATE STATISTICS stts (dependencies) ON a, b FROM t;
ANALYZE t;
EXPLAIN SELECT * FROM t WHERE a = 1 AND b = 1;
--  Estimated rows: 100    Actual rows: 100   ✓

The estimate snaps from 1 to the correct 100. Functional dependencies are cheap but handle only equality clauses.

N-distinct (ndistinct) fixes grouping estimates. Without it, GROUP BY a, b is estimated by multiplying per-column distinct counts (100 × 100 = 10000, capped, giving 1000) when the true number of distinct (a,b) pairs is 100:

CREATE STATISTICS stts (dependencies, ndistinct) ON a, b FROM t;
--  GROUP BY a,b:  Estimated rows: 100   Actual rows: 100   ✓

MCV (multivariate most-common-values) stores actual combinations of values, so it can detect impossible combinations that functional dependencies cannot:

CREATE STATISTICS stts2 (mcv) ON a, b FROM t;
EXPLAIN SELECT * FROM t WHERE a = 1 AND b = 10;
--  Estimated rows: 1    Actual rows: 0    (combination (1,10) doesn't exist)

It also handles non-equality clauses (a <= 49 AND b > 49), which the other two kinds cannot. The trade is cost: MCV statistics are more expensive to compute and store than functional dependencies. Other engines have analogues — Oracle’s extended statistics / column groups, SQL Server’s multi-column statistics and density vectors.

”Estimation Is the Optimizer’s Achilles Heel”

The definitive empirical case is Leis et al.’s “How Good Are Query Optimizers, Really?” (VLDB 2015), which introduced the Join Order Benchmark (JOB) on real, correlated IMDB data specifically because synthetic uniform benchmarks (like TPC-H) hide estimation weakness (Leis et al. 2015). Its findings reframed optimizer research:

  • Cardinality estimation, not the cost model, is the dominant error source. When the optimizers were fed true cardinalities, they produced near-optimal plans — the search and cost arithmetic were fine. The failures came from wrong row estimates.
  • Errors compound with joins. “Cardinality estimate errors grow exponentially with the number of joins” — because each intermediate result’s estimate feeds the next, multiplicatively. A 10× error per join becomes 1000× across three joins.
  • Real data breaks the assumptions. Independence and uniformity fail on correlated, skewed real-world columns; join-selectivity prediction is where estimators are worst.

The takeaway for practitioners: the optimizer is not stupid, but it is blind — it sees only its statistical thumbnail, and when that thumbnail lies (stale, too coarse, or missing multi-column correlation), it makes confident, disastrous choices.

Failure Modes and Diagnosis

  • Stale statistics. After a bulk load or a data-distribution shift, estimates reflect the old data until the next ANALYZE. Symptom: EXPLAIN ANALYZE shows estimated rows wildly off actual rows on a single table’s scan. Fix: ANALYZE (or tune autovacuum’s analyze thresholds).
  • Correlated columns. Multi-predicate underestimates driving bad nested-loop plans. Symptom: estimate ≈ 1 but actual is large on a multi-column WHERE. Fix: CREATE STATISTICS.
  • Skew beyond the MCV list. A value that is common but not in the top-100 MCV list gets the flat non-MCV estimate. Symptom: one particular value’s query is mis-estimated while others are fine. Fix: raise default_statistics_target (bigger MCV list + histogram).
  • Estimation past the histogram edge. Predicates on values outside the sampled range (e.g. created_at > now() on a table whose newest sampled row is a week old) estimate near zero. Symptom: recent-data queries get nested loops. Fix: frequent ANALYZE on append-heavy tables.
  • Cross-column joins with hidden correlation. JOB’s core finding — join-selectivity errors compounding — has no easy single-table fix; it is the fundamental hard problem, and the reason adaptive/learned cardinality estimation is an active research frontier.

Production Notes

The operational discipline is: keep statistics fresh (autovacuum/ANALYZE), and read the estimate. EXPLAIN ANALYZE’s estimated-vs-actual row counts, node by node, are the primary instrument — the first node where the two diverge sharply is where the misestimate enters and the plan goes wrong. When single-table estimates are fine but a multi-column filter is off, reach for extended statistics before touching work_mem or hints. Because estimation degrades with join depth, deeply-nested analytical queries are the ones most likely to get a bad plan from a good optimizer — which is exactly why the cross-cutting theme of the Database Internals MOC is that “the optimizer is only as good as its statistics.” Every performance mystery in Cost-Based Query Optimization eventually bottoms out here.

See Also

Graph View