Two queries each match about 50,000 rows through secondary indexes on the same table and each needs columns the index does not hold. One finishes in milliseconds, the other takes many seconds in row lookups. What property of the data explains the difference, and how would you confirm it?

## Same row count, different cost Row lookup cost is not counted in rows, it is counted in **distinct pages touched and how they are reached**. Two queries returning the same number of rows can differ by two orders of magnitude because of how those rows are spread across pages. - **Well-correlated index.** The indexed column's order tracks physical row order. Consecutive index entries resolve to rows on the same page. With a hundred rows per page, 50,000 matches touch roughly 500 pages, and they are visited in increasing order, so read-ahead works and most visits after the first per page are cache hits. - **Uncorrelated index.** Matching rows are sprinkled across the whole table. 50,000 matches touch up to 50,000 distinct pages, in unpredictable order, none of which prefetch helps. Each is an independent random access, and if the touched set exceeds available cache, revisits also miss. That is a difference of about a hundred times in page visits and, once you account for random versus sequential access, potentially much more in wall time. ## Where correlation comes from Correlation is a property of *insert behaviour*, not of the index definition: - Append-only tables have rows physically ordered by insertion time, so any monotonically increasing column - creation timestamp, sequence-based identifier - is naturally well correlated. - In clustered storage, an index on a prefix of the clustered key, or on a column functionally tied to it, is well correlated by construction. - Low-cardinality flags such as status are usually badly correlated, because rows of every status are interleaved throughout the table - and worse, status values *change*, so rows drift. - Foreign keys are correlated only if children were inserted grouped by parent; if they arrive interleaved by time, they are scattered. - Update-heavy workloads erode correlation over time as rows move. Optimizers track this explicitly - as a correlation figure or a clustering factor - precisely because it changes the estimated cost of the lookup step by an order of magnitude. A stale value here is a common cause of a plan that looks reasonable and behaves terribly. ## Confirming it 1. Get the plan with **actual** timings and per-node buffer statistics: pages hit in cache versus pages read from storage, at the lookup node. Massive read counts relative to matched rows is the signature of scatter. 2. Read the engine's clustering or correlation statistic for the two indexes and compare. 3. Sanity-check with a query that computes how many distinct pages the matching rows occupy, where the engine exposes physical row locations. 4. Compare cold and warm runs. A well-correlated query is fast even cold; a scattered one is fast only when its whole working set happens to be cached, which makes it look intermittent in production. ## Remedies and their costs - **Physically reorder the table** by the important index's key. This is dramatic and cheap to reason about, but it is a one-time operation that usually rewrites the table and takes locks, it only helps *one* access order, and correlation decays again as new rows arrive in a different order. - **Partition** so that the interesting rows are colocated in their own segment. This keeps the benefit as data grows and helps retention operations too, but partitioning is a schema-wide commitment that affects every query, not just this one. - **Eliminate the lookup** by including the needed columns in the index, so the row is never visited. Effective, at the cost of a wider index and more write work. - **Sort-by-locator batching.** Several engines can collect locators, sort them into physical order, and sweep the table once. Where the engine chooses this automatically, scatter hurts less; where it must be enabled or is blocked by needing index order for a sort, you may be able to influence it by removing the ordering requirement. - **Reduce the match count.** Often the honest fix: 50,000 rows fetched to display twenty is a query-design problem, and a more selective predicate or aggregation in the database beats any physical tuning. ## The interview signal Weak answers say "the second index is less selective" - but the premise fixed the row count, so selectivity is equal. The expected move is to separate *how many rows match* from *how those rows are laid out*, name correlation or clustering factor, and then propose a diagnosis based on measured page reads rather than a guess.