Clustered and Secondary Access Paths and the Cost of a Row Fetch

An index is a data structure that maps a key to the location of a row. The two ways to answer “where is the row” produce the two great families of table organization, and the difference between them is not a detail of implementation. It determines how many pages a lookup touches, how a range scan behaves once it has found its first row, how updates move data, and what a secondary index entry costs in bytes.

Two answers to the location question

A heap-organized table stores rows in pages with no ordering, and a secondary index entry holds the key plus a pointer to the row’s physical location, usually a page identifier and a slot number. A lookup descends the index, gets the location, and then reads the row page. Two structures, two descents, and the second descent is a random access to a page that the index gave no locality information about.

A clustered table stores rows inside the primary index itself: the leaves of the primary B-tree are the table pages, holding entire rows rather than pointers. A lookup descends the primary index and arrives at the row directly. One structure, one descent. There is no separate row fetch, and there is no such thing as a row whose location must be updated when it moves, because the row’s identity in the tree is its key.

Between them sits the index-organized table with an overflow area: rows live in the primary index until they exceed some size threshold, at which point the long columns move to overflow pages and the index leaf keeps a prefix plus a pointer. That variant is a compromise forced by the fact that clustered storage works badly for very wide rows, since a row that cannot fit in a page forces either overflow chains or a page format that tolerates multi-page rows.

The row fetch is the expensive half

The arithmetic that decides whether a secondary index helps is the cost ratio between a sequential page read and a random page read, and how many rows per page the fetch touches.

Take a query returning 1000 rows through a secondary index on a heap table with 50 rows per page. If those rows are scattered, the fetch touches close to 1000 pages, one row from each. If the table were clustered on the index key, the same 1000 rows would occupy about 20 pages, read sequentially. The index descent is identical in both cases; the difference is entirely in what happens after the leaf entry is found.

This produces the classic planner crossover. A secondary index scan costs roughly $d + r \cdot p$ where $d$ is the descent, $r$ the number of rows fetched, and $p$ the probability a fetch is not already in cache. A full table scan costs $P$ page reads for $P$ pages, regardless of how many rows match, because it reads every page once and in order. The index wins while $r \cdot p < P$, and it loses when the selectivity is poor enough that the fetch touches most pages anyway. Random page reads also cost more per page than sequential ones on rotating media, by a factor that used to be large enough to shift the crossover to a few percent selectivity, and on flash the factor is much smaller but not one, since a random read still pays the full device latency rather than being merged with neighbours.

The clustering factor is the statistic that captures this. It measures how well the index order corresponds to the physical order of the table pages: if the index entries for a range of keys all point into a small number of table pages, the factor is low and the index is nearly as cheap as a clustered one. If they point one per page across the whole table, the factor approaches the page count. A table loaded in index order has a good clustering factor until updates scramble it, and updates to a clustered table’s key are exactly the case that forces a row to move.

What a secondary entry costs

Every secondary index entry in a clustered table must contain the clustered key, because that is the only way to find the row. In a heap table the entry contains a physical pointer, typically 6 bytes in a page-and-slot form. In a clustered table the entry contains the primary key, which may be 4 bytes for an integer surrogate and 100 or more for a composite natural key.

That cost is multiplied by every secondary index and by every entry. A table with a 16-byte primary key and five secondary indexes stores 80 extra bytes of key material per row across those indexes before any indexed column is counted, and that reduces the fanout of each index’s pages. It is the main argument against natural composite primary keys in clustered engines, and the reason a monotonically increasing surrogate key is the conventional choice.

The pointer in a heap table is not free either. A row that moves because an update made it larger requires every secondary index entry pointing to it to be updated, either immediately or through a forwarding pointer that the index entry points at instead. Engines that use forwarding leave stale pointers behind and need a background pass to repair them; engines that update in place pay the write cost at update time. Either way, the indirection is a real cost that clustered storage avoids by making the key itself the identity, at the price of paying for the key in every index.

Covering indexes and the index-only scan

If the index contains every column a query needs, the row fetch disappears and the plan becomes an index-only scan. The leaf entry is then the whole answer, and the cost model loses the fetch term entirely.

Whether the engine can know the index is sufficient depends on visibility. In a clustered table, a leaf entry contains the full row, so any index is covering. In a heap table, an index-only scan must establish that the row version visible to the transaction is the one the index reflects. Systems that keep visibility in the index, or that maintain a per-page visibility map, can skip the fetch; systems that keep visibility only in the heap must check the heap page for any row whose visibility is uncertain, which for recently modified rows is most of them. This is why an index-only scan on a heap table can be slower than expected: it avoids the row data but not the page visits.

Adding columns to an index to make it covering is a trade with a direction. Each added column increases entry size, reducing fanout and increasing the index’s space; each added column also increases the write cost of every insert and update to the table, because one more structure must be maintained. An index that exists solely to make one query covering is often better replaced by restructuring the query or by accepting the fetch.

Where each organization fails

Clustered storage degrades on sequential inserts of non-monotonic keys: inserting random primary keys into a clustered index causes page splits scattered across the whole tree, with each split leaving half-empty pages and dirtying the path to the root. A surrogate key that increases monotonically confines the splits to the rightmost leaf, which is why it is preferred even when it carries no meaning. Sequential keys have their own failure: every insert contends on the same rightmost page, and the contention is on the page latch rather than on a lock, so it does not show up as lock waits and instead shows up as CPU spent spinning. The concurrent descent machinery that makes this tolerable is covered in concurrent descent and page latching.

Heap storage degrades on range queries with poor clustering, where a scan of a million index entries becomes a million random page reads unless the planner abandons the index. It also degrades on updates that change indexed columns, since each such update rewrites index entries and leaves a dead row version behind, and the space reclaimed by vacuuming is the reason heap tables need a background process that clustered tables can largely avoid.

A third organization, the column store, changes the question: rows are not fetched at all, because a scan reads only the columns named and decompresses contiguous runs. The access path there is a column segment and a bitmap of matching positions, and the analogue of the row fetch is the cost of reconstructing rows from positions, which is why column stores avoid it by aggregating in place. The trade between row and column organization is orthogonal to the clustered-versus-heap choice, and a system can be clustered within a column store by sorting the column segments on a chosen key.