OrioleDB Multi-Version Concurrency Control

MVCC not only tracks row history but also records the search-key space. To better understand PostgreSQL MVCC, it's useful to look at some alternatives. One is zheap, which introduced out-of-place undo logging to rebuild historical row versions by storing old tuples in an undo log instead of the heap. This was done entirely at the table access method level, without modifying the index access method, but it was eventually abandoned. A more recent development is OrioleDB, which extends this approach to cover the search-key space with an MVCC index access method. Due to PostgreSQL's extensive ecosystem that supports multiple index types such as hash, GIN, BRIN, SPGiST, and others through extensions, OrioleDB uses a "bridge index" to ensure compatibility.

OrioleDB: Why MVCC Reaches Into the B-tree

OrioleDB is a PostgreSQL table access method that replaces the ordinary heap with index-organized, version-aware B-trees. Complete rows are stored in the primary B-tree. Native secondary indexes store the secondary key plus the primary key, allowing them to point back to the complete row.

That layout is easy to compare with InnoDB's clustered index, but the key difference is not clustering. It is how OrioleDB preserves old snapshots as rows, keys, and B-tree pages change. OrioleDB keeps two kinds of history:

1. row-level undo reconstructs an older tuple value
2. page-level undo reconstructs older B-tree leaf contents and key ranges

The second kind is what makes OrioleDB architecturally interesting. MVCC must preserve not only what a row used to contain but also where an old query would have found it.

The indexed-key problem

Suppose an old snapshot is open while another transaction modifies an order:

UPDATE orders
SET status = 'closed'
WHERE order_id = 42;

Before the update, a secondary index contains an entry conceptually like ('open', 42). Afterward, the current tree contains ('closed', 42).

Row undo can reconstruct the old value status = 'open' after row 42 has been found. It cannot scan the old open range to find row 42. The current secondary B-tree routes the row under closed.

An MVCC engine must therefore solve two distinct problems:

Problem	Question
Payload visibility	Which version of row 42 may this snapshot read?
Predicate reachability	Should a scan of status = 'open' enumerate row 42?

PostgreSQL solves reachability by retaining old heap tuples and old index entries until VACUUM can safely remove them. InnoDB retains old secondary records as delete-marked entries until purge. OrioleDB's native indexes instead use page-level undo to reconstruct the historical searchable key space.

How OrioleDB stores the current database

The primary B-tree stores complete rows. Its key is the table's primary key, or an internal key if no primary key is defined. A native secondary leaf stores the secondary key and primary key rather than a PostgreSQL heap TID.

A secondary lookup therefore follows this path from the secondary key:

1. search the secondary B-tree to find the primary key of the row
2. search the primary B-tree to find the row with all its values

Both trees participate in snapshot visibility. A secondary index is not merely a current-key candidate generator whose result can always be repaired at the primary row. It must first enumerate the keys that were part of the requested snapshot.

This tight integration has both benefits and costs. OrioleDB can make its native indexes understand its version model directly. However, PostgreSQL index access methods such as GiST, GIN, SP-GiST, BRIN, hash, and any new index type brought by a PostgreSQL extension do not understand OrioleDB primary keys or undo.

OrioleDB supports those methods through bridge indexes. An ordinary index stores a synthetic heap-shaped bridge_ctid. An internal OrioleDB bridge tree maps that identifier to the primary key. This preserves PostgreSQL's index-AM extensibility but adds an extra lookup and reintroduces stale index entries and a VACUUM cleanup cycle into the design. Native and bridged indexes therefore have different maintenance contracts.

A secondary lookup from such indexes now follows this path:

1. search the secondary index to find the bridge_ctid
2. search the bridge index to find the primary key of the row
3. search the primary B-tree to find the row

Why OrioleDB needs two undo histories

Row-level undo maintains a tuple's history. It records enough information to select or reconstruct the row version visible at a snapshot. The same undo machinery also supports transaction rollback.

Page-level undo records changes to B-tree leaves. It covers ordinary changes, such as insertions and deletions, as well as physical maintenance, such as compaction, splits, and merges. These operations can move keys or change page boundaries, even when their purpose is only to keep the current tree balanced.

That distinction matters during a range scan. A page split may move an old key onto a page that did not exist at the snapshot. A merge may erase the boundary that an old scan needs. OrioleDB can reconstruct a historical page image and, where necessary, merge historical and live items while preserving order and avoiding omissions or duplicates.

The conceptual read path for the example is:

1. reconstruct the old secondary range containing ('open', 42)
2. obtain primary key 42
3. find row 42 in the primary tree at the same snapshot
4. apply row undo if the current row is too new
5. return the old row

Page undo answers why the scan finds the row. Row undo answers what the row contained.

B-tree maintenance becomes MVCC maintenance

In PostgreSQL, a B-tree split is primarily a physical index operation. Historical membership persists because old index tuples still point to old heap tuples. The index does not need to preserve the old page topology for snapshot reads.

In OrioleDB, a split also changes the partitioning of the searchable key space. Compaction, merge, and page reuse carry the same additional obligation. A page cannot be treated as irrelevant merely because it is obsolete in the current tree. Retained snapshots may still need its earlier contents or boundaries.

This moves work rather than eliminating it:

• native trees avoid PostgreSQL's heap-to-index vacuum cycle
• row and page undo consume space while old snapshots remain relevant
• scans may reconstruct historical images
• split and merge code participates in visibility and retention
• recycling history too early produces a snapshot too old boundary
• checkpoints and recovery must preserve consistency across primary and secondary tree updates

A single logical update can modify the primary tree and several secondaries. Current OrioleDB tracks the short primary-applied, secondary-pending interval to prevent a checkpoint from permanently merging mismatched tree states. Recovery starts from a copy-on-write checkpoint, replays row-level WAL, repairs derived secondary work as needed, and rolls back incomplete transactions.

Comparison with other engines

The engines below often use similar words while assigning history to different structures:

Engine	Current organization	How old indexed membership survives	Principal deferred cost
PostgreSQL	Heap tuples plus separate indexes	Old index entries continue to reference old version TIDs	Heap and index VACUUM, freezing, and bloat control
OrioleDB native	Complete rows in primary B-tree. Secondaries carry primary keys	Page undo reconstructs historical leaf items and ranges	Undo retention, reconstruction, and tree-aware reclamation
OrioleDB bridged	Native primary plus synthetic identities in ordinary index AMs	External entries plus a versioned bridge mapping	Extra lookups and bridge-aware VACUUM
Oracle Database	Heap blocks, indexes, undo, and consistent-read block images	Transactional index changes and undo/CR preserve logical visibility	Undo retention and optional physical coalesce/rebuild
InnoDB	Clustered primary plus secondary B-trees	Old secondary records remain delete-marked until safe purge	Undo history and purge lag
WiredTiger	Per-key update chains and reconciled B-tree images	Older key values remain in update chains or the history-store B-tree	Reconciliation, eviction, cache pressure, and history cleanup

Oracle is similar in that it uses undo to construct a consistent view, but its block formats, index algorithms, and recovery machinery differ. It should not be described as rewinding an old root-to-leaf tree for every query.

WiredTiger is especially useful for comparison because it also keeps version history close to B-tree keys. Its in-memory update chains and history store optimize storage-engine keys. OrioleDB additionally ensures PostgreSQL table and secondary-index consistency across several trees.

Two research alternatives

Recent research shows that storing versions "in the B-tree" can mean different things.

MV-PBT writes changes to a current memory-resident partition, persists full partitions sequentially, and later merges immutable partitions. Version information in index records enables index-side visibility filtering. It trades OrioleDB-style page reconstruction for cross-partition search and a merge policy closer to LSM storage economics.

The cMVBT preprint represents historical trees explicitly as a partially persistent DAG. Snapshot scans traverse immutable committed nodes without latches, while writers perform proactive version and key splits and merges with optimistic latching. OrioleDB instead maintains a current topology and reconstructs historical leaves from page undo.

cMVBT is a valuable design comparison, not yet a production-engine comparison. Its reported implementation is in-memory, uses fixed-size keys and values, and supports single-operation write transactions. External storage, crash recovery, and arbitrary multi-operation ACID transactions remain outside the scope of that evaluation.

What OrioleDB is betting on

OrioleDB's claim is not just that undo operations are less costly than keeping old heap tuples. Instead, it argues that row undo, page undo, version-aware native B-trees, copy-on-write checkpoints, and row-level WAL can work together more efficiently than PostgreSQL's heap, index, and vacuum system.

The most indicative tests are not just current-key lookups. They include historical snapshots covering indexed-key modifications, long-range scans during split and merge processes, ongoing deletes and space reuse, checkpoint crashes within primary/secondary update windows, and bridged-index workloads with delayed vacuum.

OrioleDB is still a work-in-progress open-source project in beta, requiring a patched version of PostgreSQL. Its source code reflects an ambitious and well-structured architecture rather than a stable core PostgreSQL implementation. The effectiveness of the design should be evaluated based on how well it manages historical key ranges, maintenance, cleanup, and recovery processes under real-world mixed workloads.

The core concept is simple: an old row value is useful only if the old predicate can still locate it. OrioleDB incorporates this requirement directly into the B-tree and uses an additional bridge index to remain compatible with other PostgreSQL index types.