SQL Query Cardinality Estimation and Histograms
A SQL query planner’s cardinality estimator predicts how many rows each step of a query will produce. It uses statistics about the stored data—often including histograms—to turn conditions such as price > 100 into row-count estimates. The planner then uses those estimates to choose an execution plan.
The problem: choosing before running
A SQL query can often be executed in many logically equivalent ways. For example, a database might:
- read every row in a table and test a condition;
- use an index to find matching rows;
- join two tables by scanning one for each row of the other;
- build a hash table for one input and probe it with the other;
- join tables in a different order.
An execution plan is the selected sequence of these operations. The planner must choose one before it has produced the query’s result, so it cannot simply measure the amount of work first.
Without estimates, it would have to rely on fixed rules or choose plans by guesswork. That is especially dangerous for joins: joining a 10-row result to a million-row result is a very different task from joining two 10-million-row results. The cardinality estimator gives the planner a model of the amount of data flowing through each possible plan.
From a predicate to a row estimate
A predicate is a condition that is either true or false for a row, such as status = 'paid' or created_at >= DATE '2025-01-01'. The estimator usually reasons first in terms of selectivity, the estimated fraction of rows that satisfy the predicate, and then multiplies by the input row count.
Suppose a table has one million rows and the estimator believes that 2% satisfy a condition:
SELECT *
FROM orders
WHERE status = 'paid';
The estimated cardinality of the filter is therefore about 20,000 rows. This estimate is not the query result and does not require checking all million rows. It is a prediction used during planning.
The database obtains the prediction from column statistics. A statistics collection process, commonly run by a command such as ANALYZE, samples table rows and records properties such as the approximate number of distinct values, the proportion of nulls, and the distribution of values. The statistics are much smaller than the table, so they can be consulted quickly while planning.
How a histogram represents a distribution
A histogram divides a column’s value range into buckets. Each bucket records boundaries and an estimate of how much of the data lies between those boundaries. The exact format differs between database systems, but the idea is the same: preserve a compact picture of where values occur.
Imagine a temperature column whose statistics contain boundaries like these:
| Bucket | Value range | Estimated share of rows |
|---|---|---|
| 1 | 0–10 | 20% |
| 2 | 10–20 | 50% |
| 3 | 20–30 | 25% |
| 4 | 30–40 | 5% |
For this query:
SELECT *
FROM readings
WHERE temperature >= 30;
the estimator can use the final bucket and predict that roughly 5% of rows match. If the table contains 200,000 rows, the estimate is about 10,000 rows.
For a boundary inside a bucket, the estimator usually interpolates. If values are assumed to be spread evenly through the 20–30 bucket, temperature >= 25 would be estimated as roughly half of that bucket plus all later buckets. The assumption is approximate, but it is generally more useful than pretending every value is equally likely across the entire column.
Histograms are particularly useful for range predicates. Equality predicates need another common statistic: a most-common-values list, which records frequent values and their frequencies. If 40% of rows have status = 'pending', the estimator should not treat pending like a rare status. For values not listed as common, it uses a broader estimate based on the remaining distribution.
Combining conditions and joins
For a query with multiple predicates, the estimator combines their selectivities. A simple model may assume that conditions are independent:
SELECT *
FROM orders
WHERE status = 'paid'
AND total_amount > 1000;
If it estimates 20% of rows as paid and 5% as having a large total, it may estimate 0.20 × 0.05 = 1% satisfying both conditions. With one million input rows, that becomes 10,000 rows.
Real data often violates independence. High-value orders might be unusually likely to be paid, or a city and postal code might be tightly related. Some systems collect extended or multi-column statistics to capture such relationships; otherwise, the multiplication can be badly wrong.
For a join, the estimator predicts how many rows match between two inputs using information such as distinct-value counts and value distributions. It then propagates that result to the next operation. An early error can therefore grow as a plan adds filters and joins.
Why the estimate changes the plan
Consider a query that filters a large table. If the planner expects only a few matching rows, an index scan—looking up matching locations through an index—may be cheaper than reading the whole table. If it expects most rows to match, a sequential scan—reading the table from beginning to end—may be cheaper because it avoids many scattered lookups.
Estimates also influence join algorithms and join order:
- A small estimated input can make a nested-loop join attractive.
- A larger input may favor a hash join or another set-oriented strategy.
- A relation estimated to be selective may be joined early, reducing the rows passed to later operations.
- Estimated row counts affect memory decisions, such as how large an in-memory hash structure is expected to be.
The planner combines these row estimates with estimates of operation costs, including disk reads, CPU work, and memory use. Cardinality is not the only input, but it is often the input that determines which costs look small.
When estimates go wrong
Statistics are a summary of sampled data, not a live copy of the table. They can become stale after large data changes, miss unusual distributions, or lack information about correlations. A planner may estimate 100 rows and receive 10 million instead. A nested-loop plan chosen for 100 rows can then perform disastrously when repeated millions of times.
This is why plan output commonly shows both estimated rows and, when execution is measured, actual rows. A large difference is evidence that the planner’s model—not necessarily the SQL syntax or the database engine’s correctness—is inaccurate. Updating statistics, increasing the detail collected for important columns, or providing better multi-column statistics can improve future choices.
The estimator is therefore the planner’s forecast of data volume. Histograms and related statistics make that forecast distribution-aware, and the forecast guides nearly every major choice in the execution plan.