SQL Selectivity Estimates and Query Plans
SQL query planners use column statistics to estimate predicate selectivity: the fraction of rows that a condition will match. They turn that fraction into a cardinality estimate, the expected number of rows at each step of a query, and use those estimates to choose an execution plan.
That estimate is not the query result. It is a prediction made before the query runs.
Why the estimate matters
A planner may have several ways to execute the same SQL:
- scan every row in a table;
- use an index to find matching rows;
- join two inputs with a hash table;
- repeatedly look up rows with a nested-loop join;
- sort rows, or use an existing ordering.
Each option has different costs. The right choice depends heavily on how many rows flow through each operation.
For example, an index lookup is often excellent when a predicate matches 10 rows out of 10 million. If it matches 8 million rows, walking the index and then fetching millions of table rows can be slower than reading the table sequentially. A nested-loop join can be efficient when its inner lookup runs 20 times, but disastrous when the planner expects 20 iterations and the outer input actually contains 20 million rows.
The planner therefore needs an answer to questions such as:
“How many rows will
status = 'pending'produce?”
Without statistics, it would have to rely on crude fixed guesses or choose a plan without knowing the likely result size.
What a histogram represents
A database collects statistics by examining a sample of a table, usually when an administrator or automatic maintenance process requests statistics to be refreshed. It does not normally store every column value in the planner's statistics. Instead, it stores a compact summary.
A histogram divides a column's value range into buckets and records boundaries that describe how many values fall into each region. Many systems use approximately equal-frequency buckets: each bucket contains roughly the same number of sampled rows, even though the numeric or alphabetical widths of the buckets may differ.
Consider a column containing order totals. A simplified histogram might look like this:
| Bucket | Value range | Approximate share of rows |
|---|---|---|
| 1 | 0–10 | 10% |
| 2 | 10–25 | 10% |
| 3 | 25–80 | 10% |
| 4 | 80–1,000 | 10% |
The wide final range tells us that values are sparse there; the narrow first ranges contain denser values. A predicate such as total < 25 covers about two buckets, so the planner can estimate that roughly 20% of rows match.
For a range that ends inside a bucket, the planner interpolates within that bucket. This is an approximation: it assumes values are distributed reasonably smoothly inside the range, which may be false when values cluster at particular points.
Histograms are most useful for range predicates such as <, >, and BETWEEN. Equality predicates often use additional statistics, especially a list of most common values. If status = 'pending' appears in that list, the planner can use its measured frequency instead of pretending that all distinct statuses are equally common.
Statistics commonly also include the number of distinct values and the fraction of nulls. A null is the absence of a value, and ordinary comparisons such as column = 5 do not match nulls. These facts help the planner estimate predicates involving equality, IS NULL, and other conditions.
From a predicate to a plan
Suppose a table has 10 million rows and statistics suggest that this condition matches 0.01% of them:
SELECT *
FROM orders
WHERE customer_id = 42;
The planner converts the selectivity into an estimated cardinality:
10,000,000 rows × 0.0001 = 1,000 estimated rows
It then estimates the cost of retrieving those rows through an index and compares that with scanning the whole table. The selected plan is based on the estimated work, not on the SQL text alone.
For multiple predicates, the planner must estimate how they overlap. With no evidence to the contrary, it may assume that conditions are independent. If one condition is estimated to match 10% of rows and another 20%, it may estimate their conjunction as 2%:
0.10 × 0.20 = 0.02
That assumption fails when columns are correlated. In an orders table, country = 'US' and currency = 'USD' are related; multiplying independent percentages may predict far too few or too many rows. Some database systems collect extended or multi-column statistics to capture selected relationships, but these summaries are still approximations.
The same estimates continue through joins. If the planner underestimates the rows produced by a filter, it may also underestimate the number of join comparisons, result rows, and sort operations downstream. An early error can therefore affect the entire plan.
Why errors become dramatic
A small estimate error is not equally damaging everywhere. It becomes dangerous when it crosses a plan decision's threshold.
Imagine the planner estimates that a filter returns 50 rows. It chooses a nested-loop join and performs an indexed lookup for each row. In reality, the filter returns 500,000 rows because the histogram missed a heavily populated range. The lookup is now repeated half a million times, with random access and join overhead that a hash join or sequential scan might have avoided.
The reverse error also matters. If the planner thinks a predicate matches most of a table when it actually matches a handful of rows, it may choose a sequential scan and ignore a useful index. The query still produces the correct result, but it does far more work than necessary.
This is why an execution plan can look inexplicably wrong during an incident: the plan was rational for the row counts the planner believed, even though those beliefs were inaccurate.
Finding and fixing bad estimates
Plan inspection commonly shows estimated rows alongside actual rows. In PostgreSQL, for example, EXPLAIN ANALYZE executes the query and reports both. Other database systems expose equivalent estimated-versus-actual information. A large mismatch—such as an estimate of 10 rows and an actual count of 1,000,000—is a strong clue that cardinality estimation affected the plan.
Typical causes include stale statistics after a large data change, a sample that missed a rare but important value distribution, correlated predicates, and expressions or data types for which the available statistics are weak. Refreshing statistics can help, and increasing the statistics detail for an important column can give the planner more histogram boundaries or common-value entries to work with.
Statistics cannot predict future data perfectly. The goal is not exact knowledge; it is a sufficiently accurate model of likely row counts. Query planners use that model to make cost comparisons, and when the model is badly wrong, a locally sensible choice can become a globally disastrous execution plan.