Secondary Indexes Under MVCC: Version Chasing and Index Write Amplification

An index entry is a claim about a physical row location, and multi-version storage makes physical row locations disposable. When an update writes a new row version at a new location, every index that pointed at the old location must gain an entry for the new one. A table with five indexes therefore turns one logical update into six physical writes, and the cost of that multiplication is the least discussed consequence of versioning.

The problem compounds on the read path. An index lookup returns a location that may hold a version the reader cannot see, and the reader must follow the version chain forward until it finds one that its snapshot accepts. The index cannot tell it which version is current for its snapshot, because the index does not know about snapshots.

The index has no version information

A B-tree index entry in a versioned heap engine is a key value plus a pointer to a heap tuple. That is all. The entry does not carry the transaction identifier of the row it points to, and it does not carry a validity interval.

This is a deliberate separation. The visibility decision requires the transaction identifier and the snapshot, and putting both into the index would make every visibility check an index check, inflating the index by the size of a transaction identifier plus flags per entry. Instead, the index is a map from key to location, and the heap tuple at that location answers the visibility question.

The consequence is that the index can contain several entries with the same key, each pointing at a different version of the same logical row, all of them valid as locations and most of them invisible to any given reader. A unique index cannot be unique in the physical sense for this reason; uniqueness is enforced by checking whether any visible version with the key exists, not by the absence of duplicate entries.

-- A non-unique index over a column that is logically unique:
-- duplicates accumulate as the row is updated, one entry per version.
CREATE INDEX orders_ref_idx ON orders (ref);

SELECT ctid, ref FROM orders WHERE ref = 'A-1002';
-- ctid    | ref
-- (0,3)   | A-1002     -- superseded version, dead to most snapshots
-- (1,7)   | A-1002     -- current version

A reader that lands on (0,3) must fetch the heap tuple, read its header, find that its deleting transaction is visible, follow ctid to (1,7), fetch again, and accept. The second fetch is not free, and for a chain of many versions the walk is repeated.

Chasing versions on the read path

The chase has a bound that depends on the access path, and the bound is the difference between an index scan and a bitmap scan in practice.

For an index scan, the executor takes an index entry, fetches the heap tuple, evaluates visibility, and if the tuple is not visible follows the chain. Each hop is a heap access, and each hop requires the page containing the next version. If the versions are spread across pages, the hops are page fetches, and the scan’s cost becomes proportional to the number of versions rather than to the number of matching rows.

For a bitmap scan, the executor collects all matching index entries into a bitmap keyed by page, then visits each page once and checks every candidate tuple on it. The chase still happens per candidate, but the page visits are deduplicated, so the cost is bounded by the number of distinct pages rather than the number of entries. This is why a query that returns a small fraction of a heavily updated table often performs better with a bitmap plan even when an index scan would seem more direct.

The pathological case is a query whose snapshot is old and whose target rows have been updated many times. Every index entry it examines leads to a chain that must be walked to a version that the snapshot accepts, and the walk terminates at the oldest version the snapshot can see, which is the far end of the chain. The number of heap accesses is the sum of chain lengths, not the number of rows returned.

Index-only scans and the visibility map

The one way to avoid the heap fetch is to answer the query from the index alone, which requires that the index contain every column the query references. When it does, the executor can return values from the index entry without visiting the heap.

The obstacle is visibility. The index entry does not say whether the tuple it points at is visible to the snapshot, and the whole point of an index-only scan is to avoid finding out from the heap. The solution is a separate structure that records, per page, whether every tuple on that page is visible to all snapshots — the visibility map.

-- An index-only scan is possible when the index covers the query
-- and the visibility map says the pages need no heap check.
CREATE INDEX orders_status_covering ON orders (status) INCLUDE (total);
SELECT status, total FROM orders WHERE status = 'open';

If the visibility map marks the page as all-visible, the index entry can be trusted and no heap access occurs. If the page is not marked, the executor must fetch the heap tuple to confirm visibility, and the scan degrades to an ordinary index scan with the extra cost of having read the index for nothing.

The map is updated by collection, not by the writer. A page becomes all-visible only after every tuple on it is visible to every snapshot, which is exactly the condition that collection establishes when it processes the page. This is the direct link between vacuum horizons and dead version collection and read performance: a stalled horizon keeps pages off the all-visible map, and every index-only scan over those pages turns into a heap-fetching scan.

Write amplification from multiple indexes

The write path multiplies more visibly. An insert writes one heap tuple and one entry in each index. An update that changes an indexed column writes a new heap tuple, a new entry in each index whose key changed, and, in the heap-version design, leaves the old entries in place to be removed later.

An update that changes no indexed column still writes a new heap tuple, and every index must gain an entry for it, because the index entry points at the old location and the old location is now superseded. The engine cannot rewrite the existing entry in place, since the old version may still be needed by a snapshot. So the amplification applies even to updates that appear index-neutral.

The arithmetic is straightforward: with n indexes, one logical row update produces n + 1 writes to the heap and index structures, plus n + 1 entries of write-ahead log if the structures are logged. Reducing the index count is the only lever that reduces the multiplier, which is why the guidance to drop unused indexes is stronger in a versioned engine than in a non-versioned one: an unused index costs nothing on reads and a full share of the write amplification on every update.

-- Which indexes exist, and how many times each has been used to scan.
SELECT indexrelname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
WHERE relname = 'orders'
ORDER BY idx_scan;

An index with zero scans over a representative period is pure cost: it contributes its share to every update and returns nothing.

Fill factor and the space cost of versioning

A B-tree page that is filled completely cannot accept a new entry without splitting, and a split copies half the page’s contents to a new page and updates the parent. Under versioning, index inserts arrive at a rate proportional to the update rate, so pages fill and split more often than in a non-versioned store.

The standard mitigation is to leave free space on each page at build time, so that inserts can be placed without splitting. A fill factor below 100 percent reserves that space. The trade is direct: lower fill factor means fewer splits and more pages, higher means the reverse. The right value depends on the update rate on the indexed column and on whether the key is monotonically increasing — a key like a sequence value always inserts at the rightmost page and gains nothing from free space elsewhere.

The second space cost is dead entries. An index entry pointing at a superseded tuple remains in the index until collection removes it, and collection removes it only when the tuple itself is removed. This means index bloat tracks heap bloat with a multiplier of the index count, and a table with a stalled horizon accumulates dead entries in every index as well as dead tuples in the heap.

Hot updates and the index avoidance

One optimization is worth naming because it inverts the usual rule. If an update changes no indexed column, and the new version can be placed on the same page as the old one with room to spare, some engines record the update in a way that lets the index entry be reused rather than duplicated.

The mechanism needs two conditions to hold: no indexed column changed, and the new version fits on the same page as the old one. When both hold, the old line pointer is redirected to the new version, and the index entry is left alone. The result is that the index does not grow at all for that update, and the heap gains one tuple.

The conditions fail often enough that the optimization is opportunistic rather than reliable. A page that is nearly full cannot accept the new tuple, and an update that touches any indexed column forces a real index insert for every index that covers that column. The practical implication is that the choice of which columns to index determines not just read performance but whether updates can take the cheap path. An index over a frequently updated column guarantees the expensive path on every update that touches it.

Reading the statistics

The observable signals of index-level versioning problems are distinct from heap-level ones. Index scan counts rising while the returned row count stays flat suggests version chasing: the executor is examining many entries to return few rows. A ratio of tuples read to rows returned that grows over time is the same signal in different units.

Index size growing faster than the row count indicates dead entries that collection has not removed. This is expected under a stalled horizon and is the index-side counterpart of heap bloat.

And a query plan that uses an index-only scan but shows heap fetches indicates that the visibility map is not marked, which points back to the horizon rather than to the index. The index is fine; the map is stale; the cause is a snapshot that has not advanced.

None of these signals is specific to a particular engine. They follow from the structure described here: an index that knows nothing about versions, a heap that holds them, and a collection process that decides when either can be compacted. The design that produces them is the one described in heap tuple headers and visibility, and the alternative that keeps history outside the heap shifts the same costs into the undo area described in undo records and version reconstruction, where the index churn disappears and the reconstruction cost takes its place.