Fast reads send bills to writes

Adding an order lookup index makes reads cheaper by adding work to every relevant write. PostgreSQL cannot treat the index as an occasionally refreshed cache: a chosen plan relies on it to contain every candidate required by its operator semantics, even while transactions overlap and crashes remain possible. Write-time maintenance pays for read-time trust.

An insert creates a heap tuple version and adds entries to the indexes on the indexed columns. The heap tuple has a physical identifier, and each index entry stores the key plus that identifier. The order matters with respect to WAL and visibility, but the link is simple: the heap owns the row version, and the index owns routes to find it. A reader may find an index entry before the inserting transaction commits, so heap visibility checks decide whether it counts.

Updates split the story

An update is often more expensive than it looks. If an indexed column changes, the new tuple version needs new index entries. The old entries cannot necessarily vanish right away, because old snapshots may still see the old tuple version. If no indexed column changes and the new version fits on the same heap page, a heap-only update can avoid adding new index entries. That optimization preserves read paths and reduces write amplification.

Trace three kinds of write

An insert creates a heap version, computes every indexed key, and inserts entries pointing to that version. An update to an indexed order status creates a new heap version and new status-index entries; old entries remain usable by old snapshots until cleanup. If an update changes no indexed value and fits a new version on the same heap page, a HOT chain can let existing index entries lead through page-local versions instead.

A delete marks the heap version through transaction metadata but usually leaves index removal for later vacuum. Across all three cases, transient obsolete entries are acceptable because heap visibility filters them. Missing a required entry for a visible version is not. This asymmetry—allow false candidates, never false absence—lets index maintenance remain correct without synchronously erasing every trace of history.

Deletion is usually deferred

Deletes are delayed too. A delete marks the heap tuple version as no longer visible to future snapshots once the deleting transaction commits. The index entry may remain until cleanup. During that window, an index scan can find a dead entry, visit the heap, and discard it. This sounds inefficient, but it keeps deletes from having to coordinate immediate removal across every old reader. Cleanup becomes a separate maintenance concern.

The hardest index maintenance problem is the page split. A B-tree leaf page eventually fills. To insert another key, the database allocates a new page, moves some entries, links the pages, and inserts a separator into the parent. If the parent is full, the split propagates upward. If the root splits, the tree grows taller. All of this must happen while concurrent readers can still search safely and concurrent writers may target nearby keys.

Structure changes while readers walk it

A stop-the-world split would be easy to trust and hard to live with. It locks the entire index, rearranges pages, and resumes work. The approach is simple but unacceptable for a busy server. A concurrent split uses page-level locks, right-links, high keys, and ordered steps, so a reader that lands on an old page can move right if the key range it wants shifted. The structure changes, but the search invariant holds.

WAL is part of index maintenance too. A page split is not a private memory event. If the server crashes after some split pages reach disk and others do not, recovery must restore a consistent tree. The log records for index changes must describe enough to redo the operation. Otherwise the index might point to missing heap tuples, drop keys, or break its ordering. Crash safety matters as much for indexes as for heap pages.

Unique indexes add concurrency tension. Suppose two transactions insert the same key. Neither should ignore the other, because one may commit and one may abort. The index must detect the possible conflict and coordinate with transaction status. A transaction may wait to see whether the other commits. If the other aborts, the key may be allowed. If it commits, the waiting transaction must fail. Uniqueness therefore depends on coordination between the index and the transaction manager.

Bulk index creation takes a different path. Building an index by inserting one entry at a time can be much slower than scanning the heap, sorting keys, and constructing pages in order. Concurrent builds still have to account for writes that happen while the build runs. The database may need multiple phases to capture a consistent set of entries without blocking ordinary work for too long.

The maintenance test

For every visible heap version, ask whether each relevant index can produce it as a candidate. For every candidate, ask which heap check can safely reject it. This asymmetric test permits deferred cleanup and HOT chains while forbidding silent absence. Structural changes add one more obligation: searches concurrent with a split must retain a route to the correct key range.