Cardinality Estimation
Cardinality estimation predicts how many rows each query step will produce; bad estimates lead to poor join orders, wrong algorithms, and memory spills.
Definition
Cardinality estimation is the optimizer's process of predicting the number of rows a predicate, join, or aggregation will output. It uses statistics such as histograms, most-common-value lists, distinct counts, and null fractions, combined with assumptions about independence and data distribution.
Context and scope
Every cost-based plan depends on row estimates. When estimates are wrong by orders of magnitude, the optimizer may choose a nested loop for a large input or hash join for a tiny one, causing latency spikes that look mysterious from the SQL alone.
Common misconceptions
- Cardinality estimation is exact, so a wrong estimate indicates a database bug.
- Adding an index fixes bad estimates because the optimizer will simply use it.
Anti-patterns
- Never running ANALYZE or updating statistics after large data loads.
- Assuming correlation between columns that the optimizer treats as independent.
Related concepts
Related examples
Authoritative source
https://www.postgresql.org/docs/current/planner-optimizer.html
How it works
For a simple equality predicate, the optimizer estimates selectivity from a most-common-values list or a histogram. For a range, it integrates the histogram. For a join, it combines input cardinalities with selectivity derived from the join keys, often assuming uniform distribution and independence. For AND conditions, it multiplies selectivities; for OR, it adds them and subtracts the overlap.
These assumptions are the weak point. City and postal code are correlated, but independent multiplication underestimates or overestimates the pair. Skewed foreign keys make a join estimate wrong when one customer has most orders. Expressions such as lower(email) or casts can hide statistics unless an expression index or extended statistics covers them.
Diagnosing estimates
Compare EXPLAIN estimated rows with EXPLAIN ANALYZE actual rows at each node. The first large discrepancy is usually the root cause. Check when statistics were last collected, whether the column has a histogram, and whether predicates are sargable. In PostgreSQL, pg_stats shows the histogram and distinct estimate; extended statistics can capture correlation between columns.
When to use it
This matters most for multi-join analytical queries, large skew, and plans that change with parameter values. For point lookups on a unique key, estimation is trivial. For reporting queries over years of data, an estimate off by a factor of 100 can select the wrong join strategy and spill to disk.
Trade-offs and example
More statistics improve estimates but increase analyze time and catalog size. Sampling is cheaper but noisier for rare values. Hints can override a bad estimate, but they freeze a decision that may become wrong as data changes.
Example: WHERE city = 'Seattle' AND postal_code = '98101'. If each predicate is estimated at 1 percent and multiplied, the planner expects 0.01 percent of rows, while the true combination may be 2 percent. A nested loop looks cheap and then runs far longer than a hash join. Extended statistics or a rewritten query can restore a sane estimate.