Walk through exactly what a relational engine does when a query filters using a secondary (non-clustered) index but also selects columns that the index itself does not contain.
answer
- search index, then fetch each row
- leaf entry = key + locator
- heap: physical RID; clustered: primary key
- second step is per matching row
- random I/O, not sequential
basics
~20 sIt searches the secondary index to find the matching entries, and each entry carries a pointer to the row - either a physical row address or the primary key. For every match it then reads the actual row from the table to get the missing columns. Two lookups per row.
solid answer
~50 sTwo steps. First the engine descends the secondary index B+Tree to the first matching key and walks the leaf entries in key order; those entries contain the indexed columns plus a locator for the row. Second, for each entry it uses that locator to fetch the full row: on a heap-organized table the locator is a physical address (page and slot) and the fetch is one page read; on a table stored in primary-key order the locator is the primary-key value and the fetch is a second B+Tree descent through the clustered structure. The important consequence is that the second step's cost is per matching row, not per query, and each fetch usually lands on an arbitrary page. So the index is excellent when few rows match and degrades quickly as matches grow - which is why the optimizer switches to a full scan past a fairly small fraction of the table. Selecting fewer columns, or ones already in the index, avoids the second step entirely.
code
text · 6 linesIndex Scan using idx_orders_status on orders (rows=1,240)
Index Cond: (status = 'PENDING')
-- entries hold (status, <row locator>)
-> Row lookup: 1,240 fetches to read customer_id, total_amount
heap storage : locator = (page, slot) -> 1 page read each
clustered storage : locator = order_id -> B+Tree descent eachgo deeper
Describe the two steps plainly - find matching entries in the index, then read each row for the remaining columns - and note that this is why very broad filters are slow through an index.
Contrast a heap row identifier with a primary-key locator, and explain that the per-row fetch cost is what drives the optimizer's crossover to a full scan.
Add random versus sequential I/O, pointer-sort batching and prefetch, and the cases where the engine must visit the row even for a covered query.
Frame it as physical design: which access patterns deserve to avoid lookups, and what that costs in write amplification and buffer-pool residency across the whole index set.
## The vocabulary - **Secondary index** (also called non-clustered): a B+Tree ordered by some column or columns that are *not* how the table's rows are physically stored. Its leaf entries hold the indexed values plus a locator that identifies the row. - **Primary storage**: either a *heap*, where rows sit wherever there is space, or a *clustered/index-organized* table, where rows are stored in the leaves of a B+Tree ordered by the primary key. - **Row lookup** (also called bookmark lookup, RID lookup, key lookup, or table access by index rowid): the second step that turns a locator into a full row. ## Step one: the index search The engine starts at the index root and follows separator keys down to the leaf level, typically two to four page reads for a large table because B+Tree fanout is high. It arrives at the first leaf entry matching the predicate and then walks forward through the linked leaf pages while the predicate still holds. This part is efficient and proportional to the number of matches, and the results come back in index key order - which is why an ORDER BY on the same columns can sometimes skip a sort. Each leaf entry contains: the indexed column values, and the locator. ## Step two: the row lookup If the query needs any column that is not in the index, the engine must visit the row itself. - **On a heap**: the locator is a physical row identifier - file, page, slot. Resolving it is a direct page read; no tree traversal. The catch is that if the row later grew and had to move, some engines leave a forwarding pointer at the old address, so the fetch can cost an extra hop. - **On a clustered table**: the locator is the primary-key value, and resolving it means descending the clustered B+Tree from its root, another two to four page reads, plus the comparisons on the way down. Either way, the destination page is essentially arbitrary from the storage system's point of view. Consecutive index entries in key order can point at rows scattered anywhere, so lookups are random I/O rather than the sequential streaming a table scan enjoys. ## Why this dominates cost The first step happens once per query. The second happens once per matching row. Ten matches is trivial. Five hundred thousand matches means up to five hundred thousand separate page visits, which is why optimizers abandon secondary indexes for anything but selective predicates. It also explains why the same index can be brilliant for one query and useless for another over the same table: the difference is how many rows match and how many columns are needed. Engines soften the blow in a few ways worth knowing: buffering means repeated visits to the same page may be cache hits; some engines collect the locators first, sort them into physical order, and then fetch in one increasing sweep, converting random reads into near-sequential ones at the cost of losing index order; and prefetching can overlap fetches. ## What removes the second step If the index happens to contain every column the query touches - the filter columns, the projected columns, and any join or sort columns - the engine can answer purely from index pages. Note also that on a clustered table the primary-key columns are effectively free in every secondary index, because they are already stored there as the locator, so a query selecting only indexed columns plus the primary key needs no lookup. ## Locking and concurrency footnote The two-step structure also matters under concurrency. A lookup that follows a stale or already-modified pointer must re-check row visibility, and in some engines the secondary index does not carry enough version information to decide visibility on its own, forcing a visit to the row even when the index would otherwise cover the query. That is why "the index covers it" is a property of the engine's implementation, not just of the column list. ## How to say it in an interview Say "search the index, then fetch each row" first, then name the locator difference between heap and clustered storage, then state the cost consequence - per-row random fetches, so the index only pays off for selective predicates. That three-beat answer is what interviewers are listening for.
- Why is the second step usually random I/O rather than sequential?The index leaves are ordered by the indexed column, but the rows are physically arranged by something else - insertion order on a heap, primary-key order in a clustered table. Adjacent index entries therefore point at unrelated pages, so each fetch is an independent seek. Only when the indexed column correlates strongly with physical row order do the fetches become effectively sequential.
- Does the number of columns in the SELECT list change whether a lookup is needed?Yes. The lookup exists solely to retrieve columns the index does not hold, so if every column referenced anywhere in the statement - projection, filter, join, and sort - is present in the index, the engine can skip it. On a clustered table the primary-key columns count as present because they are stored in each secondary entry as the locator. Selecting all columns with a wildcard almost guarantees a lookup.
saying these in an interview costs you the question
- Describing index access as a single step that returns whole rows directly
- Believing the row lookup happens once per query rather than once per matching row
- Assuming a secondary index always makes any query on that column fast regardless of how many rows match
- Not knowing that the locator differs between heap and clustered storage
- Thinking the lookup cost is negligible because the index search was cheap