The developers of OrioleDB analyzed the current state of the low-level API used for extensions to access tables and indexes in PostgreSQL (Table/Index Access Method (AM) API) and proposed ways to improve it. Since the introduction of such an API in PostgreSQL 12, developers have had the ability to create alternative data storage mechanisms. However, despite the existence of this API and the known limitations of the built-in storage mechanism, fully functional transactional storage engines implemented solely as extensions have yet to emerge.
The most sought-after features for alternative table engines in PostgreSQL are:
- Alternative MVCC implementations, such as UNDO log-based storage.
- Index-organized tables, where the index is not an optional supplement to the table that speeds up queries but serves as the primary data structure where table data is stored.
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.
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.
This principle has been criticized for increasing write amplification—if one indexed attribute is updated, every index in the table must be updated. To fully leverage the advantages of the UNDO log or to build another storage method without "write amplification" (for example, the WARM method), it is necessary to break this assumption.
The 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.
Practical limitations of the existing API:
- During row updates, table indexes are updated on an "all or nothing" basis.
- 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.
- Indexes currently refer to 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 index access methods. Alternative MVCC implementations may need to store additional payload along with TID. For example, OrioleDB requires one or more bits to implement "delete-marking" indexes or full visibility information.
Two approaches have been proposed to overcome the limitations in practice:
Approach 1: The API Index AM provides capabilities for alternative MVCC implementation.
While Table AM continues to handle all MVCC components, Index AM provides the necessary features for alternative MVCC implementation, namely: storing user payload along with TID, point deletion method, and even point update method (if TID in the index cannot be changed, the user payload can). Furthermore, since multiple index tuples must reference the same TID, the API methods used during index scanning also need updating.
Approach 2: Indexes supporting MVCC.
An alternative would be to allow indexes that support MVCC. In other words, the "executor" (or possibly Table AM) simply calls the insert() and delete() methods in Index AM, while Index AM provides the ability to scan considering MVCC. This would significantly simplify scanning using only indexes (index-only). Even the entire Table AM in this case could serve as an intermediary layer, storing data in the index.
The diagram below provides an example. The value of index 2 is updated by transaction 11 from "A" to "B". Therefore, the value "A" is marked as xmax == 11, while the value "B" is marked as xmin == 11. Thus, one can scan index 2 and retrieve only visible tuples according to MVCC without checking the heap. Garbage collection of index 2 can also be performed without using the heap.
When 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.
Thus, it is proposed to reconsider not only the API of Table AM but also the API of Index AM, which has faithfully served the PostgreSQL community for many years. Moreover, it is proposed to split Index AM into a logical layer and an implementation layer. This reimagined architecture would enable PostgreSQL to support various storage models.
Source: opennet.ru
