Two tables of the same size each have a B-tree index on a filtered column, and a query matches the same number of rows in each, yet the optimizer costs the index path far higher on one of them. Which table property explains the difference, and how does the optimizer measure it?
answer
- physical order vs key order agreement
- distinct pages touched, not rows matched
- one physical order, so one clustered index
- correlation coefficient or clustering factor stat
- reorder table, or make the fetch unnecessary
basics
~20 sHow closely the table's physical row order matches the index key order. When rows with adjacent keys sit on the same pages, one fetch serves many matches; when they are scattered, each match costs its own random page read. Optimizers store this as a clustering or correlation statistic.
solid answer
~60 sThe property is **physical clustering**, sometimes called correlation between index-key order and row order on disk. When the optimizer walks index entries in key order and fetches rows, the number of *distinct pages* it touches depends on layout, not on match count. In a well-clustered table, rows with neighbouring keys were written together, so retrieving 10,000 rows may touch only 200 pages, visited nearly in physical order. In a scattered table those same 10,000 rows sit on 10,000 different pages, hit in random order, and pages are revisited. Optimizers capture this as a stored statistic: a correlation coefficient between key order and physical position, or a clustering factor that estimates page switches while walking the index. That value is fed into the cost formula to price the row fetches somewhere between the sequential and random page cost. High clustering pushes the fetch cost toward sequential and keeps the index path attractive at high match counts; poor clustering pushes it toward random and makes the optimizer prefer a scan much earlier. It is a per-index property, since a table can be well ordered for one key and scattered for every other.
code
text · 7 linesN = 10,000 matching rows, 50 rows per page
well clustered -> ~200 distinct pages, ascending order -> near-sequential
scattered -> ~10,000 distinct pages, random order -> full random cost
stat form A: correlation in [-1, 1], 1 = key order equals physical order
stat form B: clustering factor between table_pages (best) and row_count (worst)go deeper
Say that if the matching rows happen to sit next to each other on disk the database fetches them cheaply, and if they are spread out it has to jump around a lot.
Quantify with distinct pages touched versus rows matched, and note that the optimizer stores a per-index statistic describing how well the orders agree.
Name the statistic, explain how it interpolates the per-fetch price between sequential and random, and give the remedies: reorder for the dominant pattern, accept it for the others, or eliminate the fetch entirely.
Treat physical ordering as a first-class design decision with one winner per table, tied to insert patterns, partitioning, and which access paths the system commits to serving cheaply as data grows.
## The missing variable Many people model the index path as `descent + N fetches`. That model has an implicit assumption: one fetch equals one page read at random cost. Reality varies enormously with **where the matching rows physically live**, and optimizers model that variance explicitly. Ignoring it is the most common reason a hand estimate disagrees with the engine's choice. ## What clustering means A table's rows have a physical position: page number and slot. An index has a logical order: sorted by key. **Clustering** is the degree to which those two orders agree. - **Well clustered.** Rows inserted in key order and left in place. An append-only event table indexed on its timestamp is the canonical example: scanning a key range walks nearly contiguous pages. - **Poorly clustered.** Insert order unrelated to key order, or rows relocated by updates. An index on a customer identifier in a table filled in event-time order is the canonical example: two rows for the same customer can sit anywhere. A table has at most one physical order, so at most one index can be well clustered. Every other index on that table is correlated with the physical order only by accident. ## Why it moves the cost so much Walk index entries in key order and count distinct pages touched for `N` matching rows, on a table with `r` rows per page: - **Perfect clustering:** about `N / r` distinct pages, visited in ascending order, so effectively sequential. For N = 10,000 and r = 50, that is 200 cheap reads. - **Zero clustering:** up to `N` distinct pages in random order, and the same page revisited later without benefit if it has been evicted. For N = 10,000 that is 10,000 random reads. Same index, same match count, a 50x difference in fetch count and an even bigger difference in price once the random-versus-sequential multiplier is applied. That is why the optimizer must know about it, and why it can rationally choose an index on one table and a scan on an otherwise identical one. ## How engines measure it The implementations differ in detail, but the idea is shared. - Some store a **correlation coefficient** between the column's ordering and the row's physical position, sampled during statistics collection, ranging from 1 (identical order) through 0 (unrelated) to -1 (reverse order). The cost formula interpolates the per-fetch price between the sequential and random constants using that coefficient. - Others store a **clustering factor**: an approximation of how many times a page switch would occur while walking the whole index in order. Its floor is the table's page count (perfectly clustered) and its ceiling is the row count (fully scattered). Comparing the stored value against those two anchors tells you immediately how clustered an index is. Either way it is derived from a sample during a statistics refresh, so it goes stale like any other statistic, and it is stored per index, not per table. ## Practical consequences 1. **Diagnosing a rejected index.** Before concluding the optimizer is wrong, check the clustering statistic for that index. A near-zero correlation on a large table is a perfectly good reason to reject an index path at a few percent selectivity. 2. **Reordering the table.** Physically rewriting the table in the order of a chosen index restores clustering and can transform a query's cost without changing a single line of SQL. It is a one-off operation, not maintained automatically, so ordering drifts again as new rows arrive and rows are updated. 3. **Choosing which key to cluster on.** Only one key can win. That is an architectural decision: usually the key used by the heaviest range-scanning access pattern, often a time column or a tenant identifier. 4. **Insert patterns matter more than index definitions.** If rows for a single logical entity are written over months interleaved with everyone else's, no index will make them contiguous. Partitioning or an index-organised layout keyed on that entity is the structural fix. 5. **Making the fetch irrelevant.** If the index carries all needed columns, the row fetch disappears and clustering stops mattering for that query. ## How to talk about it in an interview Name the property, explain the distinct-pages argument with a concrete ratio, note that it is stored per index and refreshed with statistics, and say what you would do about it: check the statistic first, consider physically reordering the table for the dominant access path, and remember that only one order can be favoured. That progression, mechanism, measurement, remedy, is what makes it a senior answer rather than a definition.
- Can a table have more than one well-clustered index, and what follows from the answer?No. A table has a single physical row order, so at most one index can match it closely; every other index is correlated only by coincidence. The practical consequence is that clustering is an architectural choice about which access pattern gets the cheap path, typically the heaviest range-scan pattern such as time or tenant. Other patterns must be served differently, for example by indexes that carry all needed columns so the row fetch disappears.
- You physically reorder a table by an index and the query gets much faster. Will it stay that way?Not automatically. The reorder is a point-in-time operation; new inserts land wherever there is free space and updates can relocate rows, so the ordering decays at a rate set by the write pattern. Keeping the benefit means either repeating the reorganisation periodically, choosing a key whose natural insert order already matches, such as an increasing timestamp, or moving to a structure that maintains the order, such as an index-organised table or partitioning aligned with the key.
Collecting all books by one author is trivial when the shelf is sorted by author and painful when it is sorted by acquisition date, even though the same number of books is involved.
saying these in an interview costs you the question
- Assuming every index path costs one random read per matching row regardless of layout
- Thinking clustering is a property of the table alone rather than of a particular index
- Believing several indexes on the same table can all be well clustered
- Expecting a physical reorder to be maintained automatically after new writes
- Calling the optimizer wrong for rejecting an index without checking the clustering statistic