For a query that matches a large fraction of a table's rows, reading the entire table can be cheaper than using a perfectly valid index on the filtered column. Explain why that happens, and roughly what fraction of rows is the tipping point.
answer
- flat line vs rising line, they cross
- one random fetch per matching row
- 20 percent scattered can touch every page
- crossover roughly 5 to 20 percent, not a law
- clustering, row width, cache move it
basics
~20 sThe index path pays roughly one random page read per matching row, on top of index reads. A full scan pays one cheap sequential read per table page, no matter how many rows match. Past a few percent of rows matched, the scan wins.
solid answer
~60 sThe two paths have different cost shapes. A full scan costs `table pages x sequential read cost` regardless of how many rows match. The index path costs the index traversal plus, in the worst case, one **random** page read per matching row, and a random read costs several times a sequential one because it cannot be batched or read ahead. So as selectivity worsens, the index path's cost grows linearly with the number of matching rows while the scan's cost stays flat. Once the matching rows are spread across most of the table's pages, the index path reads about the same number of pages as the scan, but one at a time, and it also read the whole index to get there. It ends up strictly worse. The crossover is usually low, commonly in the region of **5 to 20 percent of rows**, sometimes as low as 1 to 2 percent on wide rows or cold cache. The exact point depends on rows per page, how tightly matching rows cluster together, cache residency, and the engine's random-to-sequential cost ratio, so quote it as a range and explain what moves it.
code
text · 5 linestable orders: 1,000,000 rows in 20,000 pages (50 rows/page)
status = 'CANCELLED' -> matches 800 rows -> index scan: ~4 + ~800 random fetches
status = 'SHIPPED' -> matches 700,000 -> seq scan: 20,000 sequential reads
(index path would revisit nearly all 20,000 pages randomly)go deeper
Get the core intuition across: the index makes you jump around the table once per matching row, and if there are many matches it is cheaper to read the table straight through.
Give the cost shapes in pages, name random versus sequential cost, and quote the crossover as a range with the factors that move it: clustering, rows per page, cache.
Work a concrete numeric example, connect it to skewed parameter values needing different plans, and propose real fixes such as a more selective composite index or a partial index rather than forcing the path.
Frame it as a data-distribution and layout question: which access patterns you commit to supporting, how physical ordering and partitioning keep the index path viable at scale, and when accepting scans is the correct design.
## The two cost curves Start from the fact that engines read fixed-size pages, and reason in pages. **Full scan.** Let `P` be the number of pages in the table. The scan reads all `P`, in physical order, at the cheap sequential price. Call the unit cost `c_seq`. Total: `P x c_seq`. It does not matter whether the predicate matches one row or all of them; it is a flat line. **Index scan plus row fetch.** Let `N` be the number of rows the predicate matches. The engine descends the B+Tree (three or four pages), walks enough leaf pages to collect `N` entries, then performs up to `N` fetches of table pages. Those fetches are scattered, so they cost `c_rand` each, and `c_rand` is materially higher than `c_seq`, typically modelled as roughly four times, though the real ratio depends on hardware and cache. Total: roughly `index pages x c_seq + N x c_rand`. That is a rising line, and its slope is steep because of `c_rand`. Two rising-versus-flat lines cross. Below the crossover the index wins by orders of magnitude; above it the scan wins, and past a point the index path is not merely worse but catastrophically worse, because it can issue more single-page requests than the table has pages. ## Why the index path can read more pages than the table contains This surprises people. Suppose a table has 1,000,000 rows in 20,000 pages, so 50 rows per page, and a query matches 200,000 rows, 20 percent. If the matching rows are scattered uniformly, essentially every one of the 20,000 pages contains some matching row, so the index path must touch all 20,000 pages anyway. Worse, it touches them in key order, so the same page is often revisited many times as different matching keys point into it. Without effective caching the engine can perform far more than 20,000 page requests, each of them random, plus the cost of reading a large slice of the index. The scan does 20,000 sequential reads and stops. The index path loses by a wide margin. ## What moves the crossover - **Rows per page.** Narrow rows pack tightly, so a given fraction of rows spreads across a given fraction of pages more densely. Wide rows mean fewer rows per page, which pushes the crossover higher, since matching fewer rows already implies touching many pages. - **Physical ordering of matching rows.** If rows with adjacent index keys were inserted together and therefore sit on the same pages, one fetch serves many matches and the index path stays competitive much further out. If they are scattered, the crossover collapses toward a few percent. Time-ordered data queried by time is the classic well-ordered case; a status column updated in place is the classic scattered case. - **Cache residency.** If the table is fully in the buffer pool, `c_rand` approaches `c_seq` and the index path holds up longer. On a cold, much larger than memory table, the index path degrades fast. - **Storage characteristics.** On SSD and NVMe the random-to-sequential penalty is smaller than on spinning disks, but it is not zero: thousands of small requests still cost more syscalls, more queueing, and less read-ahead than a few large ones. - **What the query needs.** If the index covers every column referenced, the row fetch disappears and the crossover argument changes entirely; that path stays cheap even at high match counts. ## Practical consequences 1. **A full scan is often the right plan.** Seeing one in a plan is not automatically a defect. On a table with two distinct status values, no index on status will ever help a query asking for the common one. 2. **Low-cardinality columns rarely benefit from a plain index for equality on the frequent value**, though they can help for the rare value. Skewed data means the same index is right for one parameter value and wrong for another. 3. **Reducing the number of matching rows is the real fix.** Add a more selective predicate, a composite index whose extra column filters further, or a partial index restricted to the rare value. 4. **Do not force the index.** Overriding the engine to use an index on an unselective predicate is one of the most common ways to turn a slow query into a much slower one. ## How to answer the numeric part Give a range and the reasoning behind it rather than a single figure: the tipping point sits in the region of a few percent up to roughly 20 percent of rows, and moves with clustering, row width, and cache. A candidate who says "about 5 to 20 percent, lower when matching rows are scattered and the table is bigger than memory" sounds far stronger than one who recites "10 percent" as a law.
- The same query with a different parameter value should use different paths. How can one index serve both cases well?It cannot serve both with one plan, but it can with per-value estimation. If statistics carry a histogram or most-common-value list, the optimizer can estimate the row count for the specific value and choose the index for the rare value and a scan for the frequent one. Where the engine caches one plan for all parameter values, this is exactly the skew problem that produces erratic timings, and the mitigations are re-planning per value or splitting into separate statements.
- If matching rows are physically clustered together, how does that change the argument?It flattens the index path's cost curve. When rows with adjacent keys sit on the same pages, one page fetch satisfies many matching entries, so the number of distinct pages touched grows far more slowly than the number of matching rows. A well-ordered table can make the index path competitive at a much higher fraction of rows, which is why physical ordering is itself a tuning lever.
Picking up scattered groceries one aisle trip at a time is fast for three items and absurd for two hundred; at some basket size you just walk every aisle once.
saying these in an interview costs you the question
- Stating a fixed universal threshold such as exactly 10 percent as if it were a rule of the standard
- Concluding the index is broken or the statistics are wrong whenever a scan is chosen for an unselective predicate
- Assuming the index path can never read more pages than the table holds
- Ignoring caching and row width, so the crossover is treated as a property of the query alone
- Proposing to force the index as the fix for a slow unselective query