The changes necessary in the Table\/Index AM API to support alternative MVCC implementations are examined with respect to the OrioleDB extension developed to eliminate the known shortcomings of PostgreSQL's built-in storage mechanism. The problem is that full integration of OrioleDB with PostgreSQL requires modifications to PostgreSQL's code, complicating project implementation and highlighting the need to modernize the current Table AM API. <\/p>\n
The Table AM API does not directly impose a method for implementing MVCC. However, the Table AM and Index AM APIs make the following assumption: every TID (Tuple\/row Identifier) is either indexed by all indices or not indexed at all. Even if the Index AM has multiple references to one TID (for example, GIN), all these references must correspond to the same indexed value.
![\"The](\"\/wp-content\/uploads\/2025\/04\/a2082618f49d887e6987a73c65091c59.png\")
<\/center> <\/p>\nThis principle has been criticized for increasing the number of write operations (\"write amplification\") \u2014 if one indexed attribute is updated, every index in the table must be updated. To fully leverage the benefits of the UNDO log or to build another storage method without \"write amplification\" (for example, the WARM method), this assumption needs to be violated.
![\"The](\"\/wp-content\/uploads\/2025\/04\/da5adbec63e0b4c139733c5775b317b9.png\")
<\/center> <\/p>\nThe Table AM based on UNDO, which will not violate this assumption, resembles the existing HOT (Heap-Only Tuples) method, except that older versions of rows are stored in the UNDO log and do not need to fit on the same page. However, the authors believe this advantage is not sufficient to justify the existence of a separate Table AM. <\/p>\n
Practical limitations of the existing API: <\/p>\n
- \n
- During the update of a table row, the indexes are updated on an \"all or nothing\" basis.\n
- The API Index AM currently lacks the capability for point deletion of specific tuples. Currently, tuples can be deleted from indexes in bulk using the ambulkdelete and amvacuumcleanup methods. Attempting to implement point deletion via this API would lead to low efficiency, as most current implementations need to scan the entire index. Additionally, the API does not allow specifying which of the tuples referencing the same TID should be deleted. It can only remove all of them.\n
- Indexes currently reference table rows by block number (32 bits) and offset number (16 bits). Only 11 bits of the offset number can be safely passed from the table TID to all indexing access methods. Meanwhile, alternative MVCC implementations might need to store additional payload along with the TID. For instance, OrioleDB requires one or more bits to implement \"delete-marking\" indexes or full visibility information. <\/ul>\n
Two approaches have been proposed to overcome the limitations in practice: <\/p>\n
- \n
Approach 1: The API Index AM provides capabilities for alternative MVCC implementation. <\/p>\n
While the Table AM continues to be responsible for all components of MVCC, the Index AM provides the necessary capabilities for alternative MVCC implementations, namely: storing user-defined payload along with TID, a point deletion method, and even a point update method (if the TID in the index cannot be changed, the user-defined payload can). Additionally, since multiple index tuples need to refer to the same TID, the API methods applied during index scanning also need to be updated. <\/p>\n
Approach 2: Indexes supporting MVCC. <\/p>\n
An alternative would be to allow indexes to support MVCC. That is, the \"executor\" (or possibly the Table AM) simply calls the insert() and delete() methods in the Index AM, while the Index AM provides the capability for MVCC-compliant scanning. This would significantly simplify scanning using only indexes (index-only). Even the entire Table AM could, in this case, become an intermediate layer that stores data in the index. <\/p>\n
The diagram below shows an example. The index value 2 is updated by transaction 11 from the value «A» to the value «B». Therefore, the value «A» is marked as xmax == 11, while the value «B» is marked as xmin == 11. Thus, index 2 can be scanned to retrieve only the visible tuples according to MVCC without heap checks. Garbage collection of index 2 can also be performed without using the heap.
![\"The](\"\/wp-content\/uploads\/2025\/04\/9103127cc51f83c824c6cdc22135b470.png\")
<\/center> <\/p>\nWhen implementing all the aforementioned innovations in the API of index access methods, it is unlikely that it would be possible to simultaneously revise all indexes to support all new features. It is more realistic to allow several implementations for one index access method. For instance, in addition to the standard B-tree, an extension could implement an alternative B-tree with MVCC support within the index and support for variable-length record identifiers.
![\"The](\"\/wp-content\/uploads\/2025\/04\/57e1c15ecdd08f7b8095f464b59523b9.png\")
<\/center> <\/p>\n