A predicate matches about 30 percent of a ten-million-row table and a perfectly suitable index exists on that column, yet the optimizer chooses a full table scan. Explain why that can genuinely be the cheaper plan.
answer
- random fetch per row vs sequential page sweep
- rows per page: matches can exceed page count
- crossover is single-digit percent
- clustering pushes crossover higher
- covering index removes the lookup
basics
~20 sIndex access costs one random page fetch per matched row on top of walking the index; a scan reads pages sequentially with read-ahead and touches each page once. Past a few percent of the table the index path reads more pages than the table has, so scanning wins.
solid answer
~50 sAn index range scan does two things: walk the leaf entries in key order, then fetch each qualifying row from the table. If the rows are scattered, that second step is one random page read per row, and the same page can be visited repeatedly. A full scan reads every page exactly once, sequentially, with read-ahead, and no tree descent. So the comparison is roughly: matched rows times random-fetch cost versus total pages times sequential-page cost. With hundreds of rows per page, three million matched rows can easily require more page visits than the table's total page count. The crossover point is usually low, single-digit percent of the table, and it depends on the correlation between index order and physical row order: perfectly clustered data pushes it much higher because consecutive index entries hit the same page. Exceptions: if the index contains every column the query needs, no row fetches happen and the index stays competitive at high selectivity.
go deeper
Say that using the index means jumping to each row individually, while a scan reads the table straight through, so once many rows match the scan is faster.
Quantify it with rows per page and page counts, state that the crossover is only a few percent, and name clustering and covering as the factors that move it.
Bring in cost constants versus real storage, cache state, sort-by-pointer batching, and parallel scans, and check estimate accuracy before declaring the plan wrong.
Treat it as workload design: whether the query should return that volume at all, physical layout and partitioning choices, and calibrating cost constants to the actual storage tier.
## The two cost shapes **Full scan**: read every page of the table exactly once. Pages come in large sequential requests with read-ahead, so per-page cost is low and the total is *pages*, independent of how many rows match. CPU cost is one predicate evaluation per row. **Index range scan plus row lookup**: descend the tree (a handful of page reads), walk the matching leaf entries (cheap, and proportional to matches), then for each qualifying entry fetch the row from the table. That last step is the expensive part - a lookup by row pointer or by primary key, landing on an essentially arbitrary page. The optimizer models roughly: cost_scan = pages x seq_page_cost + rows x cpu_cost, versus cost_index = tree_descent + matched_entries x index_cpu + matched_rows x random_page_cost x (1 - clustering benefit). ## Why the crossover comes so early A typical page holds tens to hundreds of rows. If a ten-million-row table has a hundred rows per page, it occupies a hundred thousand pages. Matching three million rows through a scattered index means up to three million page fetches - thirty times more page visits than the whole table contains, and each one random rather than sequential. Even if buffering deduplicates repeats, you would still be touching nearly every page, but one at a time and out of order. That is why crossover from index to scan typically lands somewhere in the low single-digit percentages rather than at fifty percent, which is the number candidates usually guess. ## What moves the crossover - **Clustering / correlation.** If physical row order matches index key order - a timestamp column on an append-only table, or a clustered table read by its own key - consecutive index entries land on the same or adjacent pages. Fetches become effectively sequential and the index stays cheaper far longer. Optimizers track this as a correlation or clustering statistic precisely because it changes the answer by an order of magnitude. - **Covering.** If the index contains every column the query needs, the lookup step disappears entirely and cost becomes proportional to index size, which is normally far smaller than the table. - **Cache state and cost constants.** The modelled ratio between random and sequential page cost, and the assumed fraction of pages already cached, are configuration. Defaults calibrated for rotating disks over-price random access on flash storage, so an under-tuned system will pick scans too eagerly. - **Row width.** Wide rows mean fewer rows per page, more pages, a costlier scan, and therefore a later crossover. - **Parallelism.** Where the engine can split a scan across workers, the effective scan cost falls further, pushing the crossover even earlier. ## Tiny tables At the other extreme, a lookup table of two hundred rows occupies one or two pages. Reading it entirely costs one or two I/Os; the index costs a root page, a leaf page, and then the row fetch. The index can never win, and it is normal and correct to see scans on small tables. Candidates who insist the index "should" be used here are misreading the cost model. ## Middle-ground plans Engines are not restricted to seek-or-scan. Many can gather the matching row pointers from the index, sort them into physical order, and then fetch rows in one increasing sweep, converting random reads into near-sequential ones - typically at the price of losing index sort order and needing memory proportional to the match count. Some can scan only the index when it covers the query, or combine several indexes. Knowing these intermediate strategies exist is what separates a middle from a senior answer. ## How to respond in practice First decide whether the scan is actually wrong. If estimated and actual row counts agree and the query really does return three million rows, the optimizer is right and the fix belongs at the query or product level - paginate, aggregate in the database, or filter harder. Only if the estimate is wrong, or if the data is far better clustered than the statistics believe, is there an optimizer problem to solve. Forcing the index on a genuinely large result set reliably makes things slower, not faster.
- Two columns have identical selectivity but the optimizer uses the index for one and scans for the other. What differs?Almost certainly the correlation between index key order and physical row order. A column whose values grow with insertion order, such as a creation timestamp, has its matching rows packed into a few adjacent pages, so lookups behave sequentially. A randomly distributed column such as a UUID scatters its matches over the whole table, making each lookup a separate random page fetch. Optimizers keep a clustering statistic for exactly this reason.
- How does an index that contains every column the query needs change this calculation?It removes the table lookup entirely, so cost becomes reading part of the index rather than fetching rows. Since the index is narrower than the table, the effective crossover moves far to the right and the index can win even for large result fractions. The tradeoff is a wider index with higher write and storage cost, and it only applies while the query selects no column outside the index.
saying these in an interview costs you the question
- Believing the crossover from index to scan sits near fifty percent of the table
- Ignoring that each matched row may cost a separate random page read
- Assuming a scan in the plan is always a defect to be forced away
- Not accounting for physical clustering when explaining why one column indexes well and another does not
- Expecting an index to help on a table that fits in one or two pages