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: - row-level undo reconstructs an older tuple value - 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: - search the secondary B-tree to find the primary key of the row - 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: - search the secondary index to find the bridge_ctid - search the bridge index to find the primary key of the row - 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: - reconstruct the old secondary range containing ('open', 42) - obtain primary key 42 - find row 42 in the primary tree at the same snapshot - apply row undo if the current row is too new - 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