OrioleDB's real argument: MVCC has to version the index, not just the row

A dev.to walkthrough of OrioleDB's concurrency control makes one claim worth pulling out of the usual storage-engine pitch: MVCC does not only track row history, it also records the search-key space ^[1]. That framing explains why the fix had to reach down into the index access method, and why zheap, which stayed carefully above it, did not survive.

zheap took the obvious route. It moved old tuples out of the heap into an out-of-place undo log and rebuilt historical row versions from there, all at the table access method level, without touching the index access method ^[2]. It was eventually abandoned ^[2]. OrioleDB extends the same undo idea to cover the search-key space with an MVCC index access method ^[3].

The reason is easiest to see in the post's own example. An open snapshot exists while another transaction runs `UPDATE orders SET status = 'closed' WHERE order_id = 42`; a secondary index that held an entry like ('open', 42) now holds ('closed', 42) ^[4]. Row undo can reconstruct `status = 'open'` once row 42 has been found, but it cannot scan the old `open` range to find row 42, because the current tree routes that row under `closed` ^[4]. Reconstruction and reachability are separate problems.

Every engine pays for the second one somewhere. PostgreSQL keeps old heap tuples and old index entries until VACUUM can safely remove them; InnoDB keeps old secondary records as delete-marked entries until purge; OrioleDB's native indexes use page-level undo to reconstruct the historical searchable key space instead ^[5]. That is why OrioleDB keeps two kinds of history: row-level undo for an older tuple value, and page-level undo for older B-tree leaf contents and key ranges ^[6]. Page-level undo covers ordinary insertions and deletions but also physical maintenance such as compaction, splits and merges, which move keys and change page boundaries even when nothing logical has changed ^[7].

The layout follows from that. Complete rows live in a primary B-tree keyed by the primary key, or by an internal key if none is defined; a native secondary leaf stores the secondary key plus the primary key rather than a heap TID ^[8][9]. A native secondary lookup is two searches: secondary tree for the primary key, primary tree for the row ^[10]. Both trees participate in snapshot visibility, so the secondary index is not just a candidate generator to be repaired at the row ^[10].

Then the ecosystem bill arrives. GiST, GIN, SP-GiST, BRIN, hash and any extension-supplied index type understand neither OrioleDB primary keys nor its undo ^[11]. OrioleDB bridges them: the ordinary index stores a synthetic heap-shaped `bridge_ctid`, and an internal bridge tree maps that to the primary key ^[12]. Compatibility is preserved, but the design gets an extra lookup back, plus stale index entries and a VACUUM cleanup cycle ^[13]. A bridged lookup is three searches, one more than native, a 1.5x increase in index traversals per row ^[14][15].

What to watch is the split maintenance contract ^[13]. Native and bridged indexes now age differently in the same table, which means a workload's exposure to VACUUM depends on which index types it happens to use ^[11][13], and the cost of page-level undo during splits and merges ^[7] is the number that will decide whether versioning the key space is cheaper than retaining it.