The selectivity crossover
Your query has an index and Postgres refuses to use it. At what fraction of the table does reading all of it in order start to win?
One table of a million rows has an index on the filtered column, and the engine bets on the cheapest way in before it reads anything. Three plans are costed side by side and one is picked. Move the fraction the query matches and watch the chosen plan flip.
Board: The Query Planner →Two dials and a toggle. Every number on the page updates as soon as you move one.
try this Drag What fraction of the table the query actually matches upward one notch at a time, and watch The plan it picks.
One table: 1,000,000 rows across 10,000 pages (100 rows to an 8 KB page), with a b-tree on the filtered column costing 2,725 pages and acorrelation of 0.5. Postgres' own shipped constants: seq_page_cost 1.0,cpu_tuple_cost 0.01. Every number here is a Postgres cost, not a time. Costs are arbitrary units anchored on one sequential page read = 1.0. The planner compares plans in these units. They are not milliseconds and were not measured on any machine. The model decides which plan it expects to be cheapest, and that is all a planner chooses.
The rule of thumb says an index stops being worth it somewhere around 5–10% of the table. At these settings, where does the cost model actually put it?
The bet
50,000
rows the planner expects
The plan it picks
Collect the addresses first, then sweep in page order
Bitmap Heap Scan
cost=935.50..11435.50
The crossover
1.17%
of the table, where the sequential scan overtakes the index scan at random_page_cost 4.0
The bet slip
This is the output format you will see in practice. The rows= on the first line is the planner's estimate. The actual rows= underneath is what the query returned. The gap between them is the most useful diagnostic in EXPLAIN (ANALYZE). The stale toggle above lets you change that gap.
Bitmap Heap Scan on t (cost=935.50..11435.50 rows=50,000 width=80)
(actual rows=50,000 loops=1)
Heap pages read: 10,000 in page orderThe statistics are current, so the planner's estimate matches reality. It picks the plan that is actually cheapest at this selectivity. Correct inputs and correct arithmetic give the correct answer.
The three ways in, costed
| Plan | cost=first..all | Heap pages read | In what order | Verdict |
|---|---|---|---|---|
| Walk the whole table in order Seq Scan | 0.00..22500.00 | 10,000 | physical order | - |
| Look each row up, then go and fetch it Index Scan | 0.43..31549.18 | 10,000 | index order | - |
| Collect the addresses first, then sweep in page order Bitmap Heap Scan | 935.50..11435.50 | 10,000 | page order | picked, and cheapest |
Why the planner reached for this one
The middle option, and often overlooked. Collect every matching row's address from the index, sort the addresses by page number, then make one pass over the heap in page order. That turns random I/O into reads the device can prefetch. As the sweep covers more of the table, its per-page cost slides from random toward sequential. It degrades gradually into a sequential scan, so Postgres uses it across the wide middle range.
The tradeoff: Turns the index's random fetches into one ordered sweep. It cannot return any row until the whole bitmap is built, which is its startup cost.
Where the crossover lands: Around one percent of the table, far below the usual five-to-ten-percent figure. At the shipped default the flip comes much earlier than most people expect. That is why Postgres often skips an index you were sure it would use.
Why an index scan is not always better
An index scan pays one random heap fetch per matching row. A sequential scan reads every page once, in the order the device reads fastest. Its cost does not change with selectivity: matching three rows and matching a million cost the same. Past some fraction of the table, seeking to most of the rows does more I/O, in the slower pattern, than reading all of them. That fraction is the crossover. It is anoutput of the cost model, and it changes with the settings.
The page strip above shows the same thing without arithmetic. A page holds a matching row with probability1 − (1 − s)^100, so pages fill far faster than the selectivity grows. Once your query matches a few percent of the table, nearly every page has a match. Fetching only the matching rows then means fetching every page anyway. The index only changes the order you visit them in, and random order is slower for the device.
The knob that moves it
Two constants decide where the flip falls. seq_page_cost is fixed at 1.0, the unit every other cost is quoted in. random_page_cost ships at 4.0, a default calibrated for spinning disks with a moving arm. Slide it and the crossover moves by more than an order of magnitude, with no change to the data.
This is at or near the shipped default, calibrated for spinning disks with a moving arm. On flash it is outdated. The planner avoids good index scans and reads whole tables instead, and the crossover sits far lower than most people expect.
Statistics drive the plan
The planner cannot read your table to decide how to read it. Instead it uses statistics thatANALYZE collects from a random sample. Switch the stale toggle on and the statistics freeze at 500 rows, the numbers from before the bulk load. The planner's reasoning is still correct. Its input is out of date, so every choice that follows is based on the wrong row count.
Every plan on this page returns exactly the same rows, at every dial setting. A sequential scan, an index scan and a bitmap scan are three procedures for one result. SQL describes what to return, and the planner decides how. The dials change what a query costs, never what it returns. A mis-planned query is slow but still correct, so it often goes unnoticed.
Fix the input to the planner. Run ANALYZE, add multivariate statistics for correlated columns, raise the statistics target on a skewed column, or set random_page_cost to match your storage. Postgres has no query hints. A hint fixes today's decision in your code, and it stays wrong after the data changes.
Limits of this model
Every number here is a Postgres cost, not a time. Costs are arbitrary units anchored on one sequential page read = 1.0. The planner compares plans in these units. They are not milliseconds and were not measured on any machine. The model decides which plan it expects to be cheapest, and that is all a planner chooses.
This lab only chooses how to read one table. The four-orders-of-magnitude spread on the board comes from join planning: nested loop, hash or merge, and the order the tables are joined in, searched bottom-up with dynamic programming. A bad row estimate does far more damage there. The worst case is a nested loop chosen for an outer side the planner expected to be one row, which turned out to be a hundred and eighty thousand. This page does not model joins.
Correlation is fixed at 0.5, and it matters as much as the storage dial. Take an index on a column whose physical order matches its sorted order, such as an append-only timestamp. It keeps winning far past where a shuffled column would flip, because its "random" heap fetches are effectively sequential. Every plan cost here depends on that number, and this page does not let you change it. Postgres measures it; you cannot configure it.
The row estimate here is a single dial. Real mis-estimates have several causes. Stale statistics after a bulk load is the simplest. Others include correlated columns whose selectivities are multiplied as if independent, skew that a 30,000-row sample missed, a join selectivity no per-column statistic can express, and a generic prepared-statement plan built for the average parameter instead of the one your hot path uses.
Sources
see also Access Path Selection in a Relational Database Management System and A Relational Model of Data for Large Shared Data Banks in Papers.