The Crossover Between an Index Scan and a Sequential Scan

An index exists to avoid reading rows that do not match, and the naive conclusion is that a selective predicate should always use one. The conclusion is wrong, and the reason is that an index lookup has a fixed cost per row that a sequential read does not. Reading a table front to back streams pages in whatever order the storage prefers and pays for each page once. Reading it through an index visits pages in key order, which is almost never the order they are stored in, and may revisit the same page many times as successive keys land on it. Past some fraction of the table, the second strategy costs more than the first, and the fraction is smaller than most people expect.

The planner’s job is to find that fraction for each query, and its answer depends on a handful of quantities: the number of matching rows, the number of distinct pages those rows occupy, and how the pages are priced relative to a sequential read. The last of these is a constant, the first two are estimates, and the middle one is the quantity that implementations model least directly.

The arithmetic of a heap fetch

Take a relation of P pages holding N rows, so that a page holds N/P rows on average. A sequential scan reads all P pages. An index scan matching a fraction f of the rows must fetch fN row versions, and the pages it touches depend on how those rows are distributed.

If matching rows were spread uniformly at random across pages, the number of distinct pages touched by fN random row fetches is the classic occupancy result: P times (1 minus (1 minus 1/P)^(fN)). For small fN relative to P, that is close to fN, meaning nearly one page per row. For fN comparable to P, it approaches P, meaning every page is touched, some of them many times.

An index scan does not fetch pages at random, it fetches them in key order, and the two models differ in an important way: the random model lets the buffer pool absorb repeat visits, because a page touched early may still be resident when it is touched again. Key-order traversal does not have that property unless the buffer is large enough to hold the working set, so the number of physical reads can approach the number of distinct pages, each read once, in an order the device did not choose.

Pricing those pages as random reads at four times the sequential rate, the crossover satisfies:

$$fN \cdot c_r + fN \cdot c_{cpu} = P \cdot c_s + N \cdot c_{cpu}$$

where $c_r$ and $c_s$ are the random and sequential page costs and $c_{cpu}$ is the per-tuple cost. Solving for the case where the index touches one page per row gives $f \approx (P c_s + N c_{cpu}) / (N (c_r + c_{cpu}))$. The page term alone, $P c_s / (N c_r)$, is the page count divided by four times the row count; for a table with 100 rows per page that is 1/400, a quarter of one percent. The CPU term raises it, because the sequential scan pays the per-tuple cost for every row whether it matches or not. With a four-to-one random-to-sequential ratio and a million rows in 10,000 pages, the crossover lands near half a percent. Any predicate matching more than about that fraction is cheaper to satisfy by reading the whole table.

That figure is the reason a query returning a few thousand rows out of a million often scans. It is also the reason the answer is so sensitive to the random-to-sequential ratio: halve that ratio to reflect solid-state storage and the crossover doubles.

Physical correlation moves the crossover by orders of magnitude

The model above assumes matching rows are scattered. Real tables often are not. A table loaded in timestamp order has its timestamps correlated with physical position, so a range predicate on the timestamp selects a contiguous run of pages. Reading that run by index is a sequential read with a short seek at each end, and the number of pages touched equals the run length rather than the row count.

PostgreSQL records this as a per-column statistic named correlation, computed during ANALYZE as a value between -1 and 1 describing the strength of the linear relationship between the column’s order and physical row order. A value near 1 or -1 tells the planner that an index scan on that column will read pages in roughly storage order; a value near 0 tells it that every row fetch is likely to touch a fresh page.

The planner uses that number to interpolate between the two page-count models. This is why the same query, with the same selectivity, can use an index on one table and a sequential scan on another: the tables have the same shape and different physical order. It is also why a table that was loaded sorted and then updated in place gradually loses the property. Updates that do not fit on the original page move rows elsewhere, scattering them, and the correlation statistic falls as the table’s physical order decays. The statistic is refreshed only when ANALYZE runs, so a table that has been heavily updated may have a stored correlation that no longer describes it.

Clustering a table on an index, or loading it in key order, is therefore a physical design decision with a direct effect on plan choice, not merely a maintenance nicety. It converts a class of queries from random-page access into range access, and it does so without changing a single query or index definition.

Bitmap scans trade ordering for page locality

The third access path exists to break the ordering constraint. A bitmap scan first walks the index and builds, in memory, a bitmap of the heap pages that contain matching rows. It then reads those pages in physical order, skipping the ones with no matches. Because pages are visited once, in storage order, the cost model for a bitmap scan is close to the sequential model with a reduced page count.

Two properties follow. First, the bitmap loses the index’s ordering, so a query with ORDER BY on the indexed column cannot use a bitmap scan to avoid a sort, whereas a plain index scan can. Second, the bitmap is a fixed-size structure. When the number of matching rows exceeds the space allocated for it, the scan degrades: rather than storing one bit per row, it stores one bit per page and rechecks the predicate against every row on each matching page. That degradation is silent in the plan, which still says “Bitmap Heap Scan”, and shows up only as a sudden increase in rows filtered.

The bitmap also loses the ability to return rows incrementally in a useful order for a nested loop above it, which matters when the scan is the inner side of a join. A bitmap scan is a batch operation: it needs the whole bitmap before it can return the first row, so its startup cost is high even when its total cost is low. That distinction, introduced in the anatomy of planner costs, is what makes the choice between plain index and bitmap depend on whether the caller intends to stop early.

Index-only scans remove the heap entirely

If every column the query needs is present in the index, the heap fetch disappears and the cost model changes shape: the scan reads index pages only, and the number of rows per page is the index’s fanout rather than the table’s. An index on (customer_id, created_at) can answer SELECT created_at FROM orders WHERE customer_id = ? without touching the table, and the saving is the entire heap term.

The condition is stricter than “the columns appear in the index”. The visibility map, a per-page bitmap recording which pages contain only tuples visible to all transactions, must be consulted to confirm that an index entry’s heap tuple is actually visible. Pages whose visibility bit is set can be skipped; pages without it must be visited to check tuple visibility. A table that has just been bulk loaded has few visibility bits set, so an index-only scan on it behaves much like a plain index scan until vacuum marks the pages. This is why the same query can switch from an index-only plan to an index plan after a large insert, and why vacuum is a planner-visible operation rather than only a space-reclamation one.

Covering indexes widen the index to include the columns a query needs, and the trade is direct: each additional column increases the index’s size, reducing fanout and therefore rows per page, and increases the write cost of every insert and update. An index that covers a hot query is worth that cost; one that covers a rarely run report is not, and nothing in the planner will tell the difference between them.

Where the estimate, not the model, decides

Every quantity in the crossover calculation except the page costs is an estimate. The row count comes from the predicate selectivity, described in selectivity estimation from histograms, and the page count comes from a model that assumes uniformity within the matching set. Both assumptions fail in ways that produce a plan flip rather than a small error.

A predicate on a column with a skewed distribution is estimated from an averaged bucket, so a value matching a tenth of the table can be estimated at a hundredth. The planner then computes an index scan cost appropriate for a hundredth, chooses the index, and the executor performs a hundred times more row fetches than the cost model priced. The reverse also happens: a value estimated as matching half the table, when it matches one row, produces a sequential scan that reads everything to find almost nothing.

The reliable diagnostic is the estimated against actual row count at the scan node in EXPLAIN ANALYZE. When those two numbers diverge by more than an order of magnitude, the access path choice is a consequence rather than a cause, and changing cost constants will only move the failure to a different query. Fixing the statistic, the predicate form, or the table’s physical ordering addresses the actual problem.