Why indexes exist and when they win

When is a separate index worth building, and what exactly do we trade?

Giving up on the data

Before indexes, everything that makes a query fast works by arranging the data itself: layout, clustering, partitioning, sort order, column storage. All of these make the bytes you want land near each other. And all of them hit one hard limit:

Indexing is different because it gives up on the data. An index is not an arrangement of the data. It is a separate, derived, redundant structure whose only job is to answer "where is it?" Once you accept redundancy, the single-order limit disappears. You can have as many orderings as you are willing to pay for.

That is the trade. Three constraints stop mattering and three new ones appear.

---

The governing question: when does the reader save more than the writer pays?

An index is worth building only when the reader saves more than the writer pays. The read side has a clean derivation, and it is worth doing, because the folklore version is everywhere and slightly wrong.

• A scan reads all N rows in order. Let s be the per-row cost of sequential access. Cost: N × s.
• An index lookup finds k matching rows by random access. Let r be the per-row cost of random access. The tree descent adds only a few reads, so we ignore it. Cost: about k × r.

The index wins when

The old rule of thumb "an index stops helping past about 5% selectivity" is not a law. It is s/r on 2005 hardware, rounded. PostgreSQL exposes the ratio directly as two settings, seq_page_cost and random_page_cost, with defaults 1.0 and 4.0. People are told to lower random_page_cost to about 1.1 on NVMe SSDs (very fast flash storage) because s/r moved a great deal when the mechanical seek went away. It is the same equation with different hardware and a different answer.

(With the defaults 1.0 and 4.0, a naive row-for-row reading gives a 25% crossover, not 5%; the page-level arithmetic below gives 0.25%, because many rows share a page, and caching moves it again. The crossover is a hardware ratio, not a constant.)

Worked example: the crossover with real numbers

parcels has N = 100,000,000 rows. With f = 100 rows per page it occupies 1,000,000 pages.

• Scan: read all pages sequentially. Cost = 1,000,000 pages × 1.0 = 1,000,000 units.
• Unclustered index lookup (matching rows scattered, one page each): cost = k × 4.0.
• The index wins when 4k < 1,000,000, so k < 250,000 rows, which is 0.25% of the table.

So for Priya's first index, if the status = 'delayed' filter matches 8% of the rows (8 million rows), the index is hopeless: 8,000,000 × 4 = 32,000,000 units against 1,000,000 for the scan. The planner is right to ignore it. On NVMe with random_page_cost = 1.1, the break-even rises to about 909,000 rows (0.9%). Still far below 8%.

Two corrections that matter more than the formula

1. The unit is pages, not rows. If the k matching rows lie on k different pages, you pay k random reads. If they are clustered together, you pay far fewer. This is why PostgreSQL keeps a per-column correlation statistic (how closely the column's order matches the physical row order). It is also why "clustered versus non-clustered" is the highest-leverage distinction in Index anatomy: clustering changes the number of pages k in the numerator, not the cost r.

2. r is not a constant. It is a step function. An index that fits in memory (the buffer pool) has one r. The same index, one byte too large for the buffer pool, has a different, much larger r. Indexes have cliffs, not curves. This is the general law "a fixed resource meeting exponential growth": index size grows with the data, memory does not, and the cost function jumps at the point where they cross.

What else moves the crossover

• With wide columnar rows, the rows-per-page count for the needed columns goes up enormously. That pushes the crossover down and favors scans. This is one mechanical reason analytic engines have few indexes.
• On object storage there is no random access at the page level at all. The question is no longer "index or scan" but "can I avoid fetching this object?", which per-file metadata answers with a skip instead of a lookup (sparse indexes and zone maps).

The planner has to make this choice before the query runs, from an estimate of k; how it gets that wrong near the crossover is access path selection.

The write side has no clean formula, and that is the point

Read benefit can be estimated. Write cost is certain. N indexes means roughly N times the write-path work, N times the space and N times the number of things that can break. That is why the honest default in most systems is "fewer indexes than you think", and why finding and dropping unused indexes is a standard production task.

---