You need to estimate, in pages of I/O, the cost of retrieving 200,000 matching rows from a 10-million-row table through an index versus reading the whole table sequentially. Walk through the arithmetic and state the assumptions you would make.

seniorshould knowfreq 45%

answer

rows to pages first, always
10M / 50 = 200,000 pages
leaf entries approx 400 per page
random costs approx 4x sequential
answer is a range: packed vs scattered

basics

~20 s

Convert rows to pages. With 50 rows per page the table is 200,000 pages, read sequentially. The index path costs a few index pages plus up to 200,000 random row fetches, each several times more expensive. The scan wins by roughly an order of magnitude.

solid answer

~60 s

Work in pages, and state the assumptions out loud.

Assume an 8 KB page and roughly 50 rows per page, so 10,000,000 rows occupy about 200,000 pages. A full scan is 200,000 sequential page reads.

The index path: a B+Tree over 10M keys is about four levels, so the descent is roughly 4 pages. If about 400 index entries fit per leaf page, 200,000 matching entries span about 500 leaf pages, read in key order. Then the row fetches: worst case one page per matching row, 200,000 random reads; best case, if matching rows are physically packed together, only about 4,000 pages (200,000 rows / 50 per page).

Now price them. A random read is conventionally modelled at several times the cost of a sequential one, often around 4x. Worst case the index path is roughly 200,000 x 4 = 800,000 sequential-equivalents versus the scan's 200,000, so the scan wins by about 4x, and much more once repeated visits to the same page are counted. Only in the tightly packed case, about 4,000 x 4 = 16,000, does the index path win.

Work in pages, and state the assumptions out loud. Assume an 8 KB page and roughly 50 rows per page, so 10,000,000 rows occupy about **200,000 pages**. A full scan is 200,000 sequential page reads. The index path: a B+Tree over 10M keys is about four levels, so the descent is roughly 4 pages. If about 400 index entries fit per leaf page, 200,000 matching entries span about **500 leaf pages**, read in key order. Then the row fetches: worst case one page per matching row, **200,000 random reads**; best case, if matching rows are physically packed together, only about 4,000 pages (200,000 rows / 50 per page). Now price them. A random read is conventionally modelled at several times the cost of a sequential one, often around 4x. Worst case the index path is roughly `200,000 x 4 = 800,000` sequential-equivalents versus the scan's 200,000, so the scan wins by about 4x, and much more once repeated visits to the same page are counted. Only in the tightly packed case, about `4,000 x 4 = 16,000`, does the index path win.

code

text · 9 lines

text

assumptions: 8KB page, ~50 rows/page, ~400 index entries/leaf, c_rand ~ 4 x c_seq

table pages         = 10,000,000 / 50  = 200,000   (~1.6 GB)
seq scan cost       = 200,000 x 1      = 200,000 units

index descent       ~ 4 pages
leaf pages walked   = 200,000 / 400    = 500 pages
row fetches, scattered = ~200,000 random -> 200,000 x 4 = 800,000 units
row fetches, packed    = 200,000 / 50 = 4,000 pages -> 4,000-16,000 units

go deeper

for a junior

At minimum convert rows to pages and note that the index path does one lookup per matching row while the scan reads each page once.

for a middle

Produce both totals with stated assumptions, and name the random-versus-sequential price difference as the reason the index path can lose.

for a senior

Give the answer as a range driven by physical row layout, correct it for cache residency and repeat page visits, then say which measurement you would take to validate the model.

for a principal

Turn the model into a design input: at what data volume does each access pattern stop being affordable, and what layout, partitioning, or storage decision keeps the important queries on the cheap side of the crossover.

Step 1: convert everything to pages

Engines read pages, so rows are the wrong unit. You need two conversions.

Rows per table page = usable page bytes / average row size. With an 8 KB page, some header overhead, and a row of roughly 150 bytes, about 50 rows per page is a reasonable working figure. Then:

table pages = 10,000,000 / 50 = 200,000 pages = about 1.6 GB.

Entries per index leaf page = usable page bytes / (key size + pointer). For a small key, say 8 bytes plus a 6 to 8 byte pointer plus per-entry overhead, roughly 400 entries per leaf page is a fair estimate. Then:

leaf pages for 200,000 matches = 200,000 / 400 = 500 pages.

Announce these numbers as assumptions. The interviewer is testing whether you can build the model, not whether you memorised page sizes.

Step 2: cost the sequential scan

200,000 pages read in physical order. Read-ahead turns this into a modest number of large requests, so the effective per-page cost is the sequential unit, c_seq = 1 by convention. Total: 200,000 units. Elapsed time is easy to sanity-check: at 500 MB/s effective sequential throughput, 1.6 GB takes roughly 3 seconds; at 2 GB/s, well under a second.

Step 3: cost the index path

Three components.

Descent. A B+Tree with 400 entries per node over 10M keys needs about log_400(10,000,000) which is under 3, so call it 3 to 4 pages. Negligible, and usually cached.
Leaf walk. 500 leaf pages, read in key order, close to sequential. About 500 units. Also small.
Row fetches. This is the whole game. The engine has 200,000 pointers and must read the page each points at.

The fetch count depends entirely on how the matching rows are laid out physically:

Worst case, uniformly scattered. Nearly every fetch lands on a different page, and the same page is often revisited later in key order. Distinct pages touched approaches the full 200,000-page table, and total requests can be around 200,000 or more. Priced at random cost c_rand, conventionally about 4x sequential, that is roughly 800,000 units.
Best case, tightly packed. If matching rows were written together and remain adjacent, 200,000 rows occupy about 200,000 / 50 = 4,000 pages, and key order visits them almost in physical order. Roughly 4,000 to 16,000 units depending on how sequential the visits look.

Step 4: compare and conclude

Path	Units (approx)
Sequential scan	200,000
Index path, scattered rows	800,000+
Index path, packed rows	4,000 to 16,000

So the answer is conditional and that is the point: for 2 percent of a table, the index path wins outright if the matching rows are physically grouped, and loses by around 4x or worse if they are scattered. A candidate who gives a single number without stating that dependency has missed the mechanism.

Step 5: the corrections that matter in reality

Buffer pool. If a significant share of the table is resident in memory, many random fetches become memory hits and c_rand collapses toward c_seq. Re-run the arithmetic with a hit ratio: effective cost = misses x c_rand + hits x c_mem. On a table far larger than memory, assume the pessimistic case.
Repeat visits. Index order revisits pages. With caching, later visits are cheap; without it they are full random reads. This is why the worst case can exceed the table's page count.
Random-to-sequential ratio by hardware. The classic 4x figure is a modelling convention. On NVMe with deep queues the gap narrows, perhaps 1.5x to 2x for throughput, though per-request overhead persists. On network-attached storage with per-request latency, the gap widens sharply.
Concurrency and parallelism. A parallel sequential scan splits pages across workers and shrinks elapsed time further, which pushes the crossover even more in the scan's favour on analytic-style queries.
What the query returns. If the index carries every column the query needs, component 3 disappears entirely and the cost is just 500-ish leaf pages, which changes the verdict completely.

Step 6: how to check yourself against reality

Don't stop at arithmetic. Ask the engine to report actual buffer statistics for the query: pages read versus pages hit in cache, distinct pages, and elapsed time. The ratio between predicted and observed page counts tells you whether your rows-per-page and layout assumptions held. This habit, model first, measure second, reconcile the gap, is what separates a senior answer from a recital of rules of thumb.

## Step 1: convert everything to pages Engines read pages, so rows are the wrong unit. You need two conversions. **Rows per table page** = usable page bytes / average row size. With an 8 KB page, some header overhead, and a row of roughly 150 bytes, about 50 rows per page is a reasonable working figure. Then: `table pages = 10,000,000 / 50 = 200,000 pages` = about 1.6 GB. **Entries per index leaf page** = usable page bytes / (key size + pointer). For a small key, say 8 bytes plus a 6 to 8 byte pointer plus per-entry overhead, roughly 400 entries per leaf page is a fair estimate. Then: `leaf pages for 200,000 matches = 200,000 / 400 = 500 pages`. Announce these numbers as assumptions. The interviewer is testing whether you can build the model, not whether you memorised page sizes. ## Step 2: cost the sequential scan 200,000 pages read in physical order. Read-ahead turns this into a modest number of large requests, so the effective per-page cost is the sequential unit, `c_seq = 1` by convention. Total: **200,000 units**. Elapsed time is easy to sanity-check: at 500 MB/s effective sequential throughput, 1.6 GB takes roughly 3 seconds; at 2 GB/s, well under a second. ## Step 3: cost the index path Three components. 1. **Descent.** A B+Tree with 400 entries per node over 10M keys needs about `log_400(10,000,000)` which is under 3, so call it 3 to 4 pages. Negligible, and usually cached. 2. **Leaf walk.** 500 leaf pages, read in key order, close to sequential. About 500 units. Also small. 3. **Row fetches.** This is the whole game. The engine has 200,000 pointers and must read the page each points at. The fetch count depends entirely on how the matching rows are laid out physically: - **Worst case, uniformly scattered.** Nearly every fetch lands on a different page, and the same page is often revisited later in key order. Distinct pages touched approaches the full 200,000-page table, and total requests can be around 200,000 or more. Priced at random cost `c_rand`, conventionally about 4x sequential, that is roughly **800,000 units**. - **Best case, tightly packed.** If matching rows were written together and remain adjacent, 200,000 rows occupy about `200,000 / 50 = 4,000` pages, and key order visits them almost in physical order. Roughly **4,000 to 16,000 units** depending on how sequential the visits look. ## Step 4: compare and conclude | Path | Units (approx) | |---|---| | Sequential scan | 200,000 | | Index path, scattered rows | 800,000+ | | Index path, packed rows | 4,000 to 16,000 | So the answer is conditional and that is the point: for 2 percent of a table, the index path wins outright if the matching rows are physically grouped, and loses by around 4x or worse if they are scattered. A candidate who gives a single number without stating that dependency has missed the mechanism. ## Step 5: the corrections that matter in reality - **Buffer pool.** If a significant share of the table is resident in memory, many random fetches become memory hits and `c_rand` collapses toward `c_seq`. Re-run the arithmetic with a hit ratio: `effective cost = misses x c_rand + hits x c_mem`. On a table far larger than memory, assume the pessimistic case. - **Repeat visits.** Index order revisits pages. With caching, later visits are cheap; without it they are full random reads. This is why the worst case can exceed the table's page count. - **Random-to-sequential ratio by hardware.** The classic 4x figure is a modelling convention. On NVMe with deep queues the gap narrows, perhaps 1.5x to 2x for throughput, though per-request overhead persists. On network-attached storage with per-request latency, the gap widens sharply. - **Concurrency and parallelism.** A parallel sequential scan splits pages across workers and shrinks elapsed time further, which pushes the crossover even more in the scan's favour on analytic-style queries. - **What the query returns.** If the index carries every column the query needs, component 3 disappears entirely and the cost is just 500-ish leaf pages, which changes the verdict completely. ## Step 6: how to check yourself against reality Don't stop at arithmetic. Ask the engine to report actual buffer statistics for the query: pages read versus pages hit in cache, distinct pages, and elapsed time. The ratio between predicted and observed page counts tells you whether your rows-per-page and layout assumptions held. This habit, model first, measure second, reconcile the gap, is what separates a senior answer from a recital of rules of thumb.

How would a fully cached table change your conclusion?
It shrinks the penalty on random access, because a cache hit costs roughly the same wherever the page sits. Re-run the model with a hit ratio, so effective cost becomes misses times the random price plus hits times a near-zero memory price. On a table that fits in the buffer pool the index path stays viable at a much higher match fraction, which is exactly why a query that is fine in a warm staging environment can collapse on a cold, much larger production table.
What measurement would you take to check whether your assumed rows-per-page figure was right?
Ask the engine for the table's physical size and its row count, and divide: size in pages over rows gives observed rows per page directly. Then run the query with per-statement buffer accounting enabled and compare the pages actually read with your prediction. A large gap usually means the average row is wider than assumed, or that space is being wasted by dead row versions and fragmentation.

saying these in an interview costs you the question

Answering in rows rather than pages, so both paths look proportional to match count
Giving one number without stating whether matching rows are packed or scattered
Pricing random and sequential reads identically because the storage is SSD
Forgetting that index order can revisit the same page many times, so requests can exceed table pages
Ignoring the buffer pool entirely, or assuming everything is cached without checking table size against memory

You need to estimate, in pages of I/O, the cost of retrieving 200,000 matching rows from a 10-million-row table through an index versus reading the whole table sequentially. Walk through the arithmetic and state the assumptions you would make.

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Step 1: convert everything to pages

Step 2: cost the sequential scan

Step 3: cost the index path

Step 4: compare and conclude

Step 5: the corrections that matter in reality

Step 6: how to check yourself against reality

▾common follow-ups2 questions

▾red flags5 flags

§ context

▾related questions7 questions

▾related topics3 topics

Step 1: convert everything to pages

Step 2: cost the sequential scan

Step 3: cost the index path

Step 4: compare and conclude

Step 5: the corrections that matter in reality

Step 6: how to check yourself against reality

answer

go deeper

context