Hi, On Saturday, we had a nice in-person conversation about the requirements that zedstore has for an undo facility vs. the requirements that zheap has vs. the current design of the undo patch set. The people present were: Heikki Linnakangas, Amit Kapila, Thomas Munro, Kuntal Ghosh, Andres Freund, and me. The remainder of this email consists of the notes that I took during that conversation, with some subsequent editing that I did to try to make them more broadly understandable.
zedstore needs a very fast way to determine whether an undo pointer is old enough that it doesn't matter. Perhaps we should keep a backend-local cache of discard pointers so that we can test an undo pointer against the discard horizon without needing to touch shared memory. zedstore needs a very fast way of obtaining the XID when it looks up an undo pointer. It seems inefficient to store the full XID (especially an 8-byte FullTransactionId) in every undo record, but storing it only in the transaction header makes getting the XID prohibitively expensive. Heikki had the idea of storing a flag in each undo record saying 'same X as first tuple as on the page', where X might be XID, CID, relation OID, block number, etc. That seems like a good idea. We'd need to decide exactly how many such flags to have and which fields they cover; and it's probably best not to depend on an undo record for another transaction that might be independently discarded. Another option is to put a "default" for each of these values in the page header and then store a value in individual undo records only if it differs from the value in the page header. We don't have a way to do similar optimization for whatever individual clients of the undo machinery choose to store in the undo record's payload, which might be nice if we had a good idea how to do it. zedstore intends to store an undo pointer per tuple, whereas the current zheap code stores an undo pointer per transaction slot. Therefore, zheap wants an undo record to point to the previous undo record for that transaction slot; whereas zedstore wants an undo record to point to the previous undo record for the same tuple (which might not belong to the same transaction). The undo code that assumes per-block chaining (uur_blkprev) needs to be made more generic. For either zedstore or zheap, newly-inserted tuples could potentially point to an XID/CID rather than an undo record pointer, because visibility checks don't need to look at the actual undo record. An undo record still needs to be written in case we abort, but we don't need to be able to refer to it for visibility purposes. zedstore and zheap have different batching requirements. Both want to process undo records in TID order, but zedstore doesn't care about pages. The current undo patch set calls the RMGR-specific callback once per page; that needs to be generalized. Is it possible that some other table AM might want to sort by something other than TID? Right now, zedstore stores a separate btree for each column, and an extra btree for the visibility information, but it could have column groups instead. If you put all of the columns and the visibility information into a single column group, you'd have a row store. How would the performance of that solution compare with zheap? Maybe zheap should forget about having transaction slots, and just store an undo pointer in each tuple. That would be worse in cases such as bulk loading, where all the tuples on the page are modified by the same transaction ID. We could optimize that case by using something like a transaction slot, but then there's a problem if, say, every tuple on the page is updated or deleted by a separate transaction: the tuples need to get bigger to accommodate separate undo pointers, and the page might overflow. Perhaps we should design a solution that allows for the temporary use of overflow space in such cases. Tuple locking is complicated for both zheap and zedstore. Storing the locker XIDs in the tuple or page is tempting, but you can run out of space; where do you put the extras? Writing an undo record per lock is also tempting, but that could generate a very large amount of undo if there are many transactions that are each locking a whole table, whereas the heap doesn't have that problem, because it uses MultiXacts. On the other hand, in the current heap, it's easily possible for N transactions to burn through O(N^2) MultiXactIds, which is worse than an undo record per lock. A perfect system would avoid permanently bloating the table when many transactions each take many locks, but it's hard to design a system that has that property AND ALSO is maximally compact for a table that is bulk-loaded and then never updated again. (Perhaps it's OK for the table to expand a little bit if we find that we need to make space for a MultiXactId pointer or similar in each tuple? Thomas later dubbed this doubtless-uncontroversial design non-in-place select, and we're all looking forward to review comments on noninplace_select.c.) Heikki proposed an out-of-line btree of tuple locks, with compression to represent locks on TID ranges via a single entry, stored in memory if small and spilling to disk if large. It could be discarded on startup, except for locks held by prepared transactions. Updates might not need to enter their own tuple locks in this btree, but they would need to propagate key share locks forward to new TIDs. Robert and Thomas came up with the idea of having a special kind of undo record that lives outside of a transaction; a backend could attach to an additional undo log, insert one of these special records, and the detach. These special undo records would have a special rule for when they could be discarded; an rmgr callback would decide when it's OK to discard one. This could serve as a replacement for MultiXactIds; you could store a collection of XIDs in the payload of one of these special records. (Andres was not very impressed by this idea.) Later, after Heikki left, we talked about perhaps also allowing these special undo records to have a special rule for when undo actions are executed, so that you could use the undo framework for un-commit actions. It doesn't seem desirable to have to perform on-commit actions frequently; one of the motivating ideas behind zheap is that commits should be as cheap as possible, even if that costs something in the abort case. But it might be useful to have the option available for use in rare or exceptional cases. After this discussion, Heikki is thinking that he might just allow each tuple in zedstore to store both an undo log pointer and a MultiXactId, elided when not needed. The MultiXact system would need to be updated to make MultiXactIds 64-bits in order to avoid needing to freeze. No one seemed keen to build a new storage engine that still requires freezing. When subtransactions are used, the undo system intends to use the toplevel XID for everything, rather than requiring additional XIDs for subtransactions. After some discussion, this seems like it should work well for both zheap and zedstore. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
