Partial Heap Only Tuples
Partial heap only tuples (or PHOT) is a proposed heap optimization for PostgreSQL that aims to improve the existing heap only tuples (or HOT) optimization by allowing us to skip updating indexes for unchanged columns even when other indexes require updates.
Today, HOT takes effect when there are only updates to non-indexed columns. Specifically, it allows you to skip updating any indexes in this case, reducing index size and improving performance. As soon as any indexed column is touched, the optimization is lost completely, and updates require adding new tuples to all indexes for the table. PHOT intends to improve performance and index size even further by removing this restriction, meaning we will only update indexes that have been changed during updates.
Basic Design
To implement PHOT, we will use one of the two remaining t_infomask2 bits as a "modifier" bit for HEAP_HOT_UPDATED and HEAP_ONLY_TUPLE. This bit will indicate that a tuple with the given HOT-related bit set is actually PHOT-updated or a partial heap only tuple.
When it is time to update a tuple on a page, we update the heap just like we do for HOT, given that there is enough space left on the page. Also, we add a "modified columns" bitmap to the tuple header. Then, we only add new index tuples for indexed columns that were modified.
When it comes time to scan through a PHOT chain, there are a couple of things to account for. Sequential scans work out-of-the-box thanks to the visibility rules, but other types of scans like index scans require additional checks. If you encounter a PHOT chain when performing an index scan, you should only continue following the chain as long as none of the columns the index indexes are modified (as determined by the modified columns bitmap mentioned earlier). If the scan does encounter such a modification, we stop following the chain and continue with the index scan. Even if there is a tuple in that PHOT chain that should be returned by our index scan, we will still find it, as there will be another matching index tuple that points us to later in the PHOT chain.
One open area of investigation is how to support other scans such as bitmap scans. Since we won't have followed the PHOT chains in the bitmap index scan, we must know how to follow them in the bitmap heap scan. Unfortunately, the bitmap heap scan has no knowledge of what indexed columns to pay attention to when following the PHOT chains. The proof-of-concept patch fixes this by having the bitmap heap scan pull the set of indexed columns it needs to consider from the outer plan. However, substantially more effort is likely needed in this area.
For cleanup, some amount of single-page vacuuming is possible, like HOT, although there is some added complexity. Also like HOT, there is little change to regular vacuum, but some additional improvements may be necessary. More information about cleanup is included in a later section.
Update Example
Updates are relatively straightforward. When there is space for a PHOT update on the page, only update indexes that are changed, and include a bitmap of modified columns in the tuple headers for the updated versions of the tuples. The following example demonstrates a high-level view of the table and its indexes after the following commands:
CREATE TABLE test (a INT, b INT, c INT); CREATE INDEX ON test (a); CREATE INDEX ON test (b); CREATE INDEX ON test (c); INSERT INTO test VALUES (0, 0, 0); UPDATE test SET a = 1, b = 1; UPDATE test SET b = 2, c = 2; UPDATE test SET a = 2; UPDATE test SET a = 3, c = 3;
Before PHOT
test_a_idx 0 1 1 2 3 test_b_idx 0 1 2 2 2 test_c_idx 0 0 2 2 3 lp 1 2 3 4 5 heap (0,0,0) (1,1,0) (1,2,2) (2,2,2) (3,2,3)
After these updates, there are 15 index tuples, 5 line pointers, and 5 heap tuples.
With PHOT
test_a_idx 0 1 2 3 test_b_idx 0 1 2 test_c_idx 0 2 3 lp 1 2 3 4 5 heap (0,0,0) (1,1,0) (1,2,2) (2,2,2) (3,2,3) bitmap xx- -xx x-- x-x
After these updates, there are 10 index tuples, 5 line pointers, 5 heap tuples, and 4 bitmaps.
Single-Page Cleanup
Like HOT, there are some opportunities for us to prune and defragment. However, PHOT has more restrictions than HOT. A strategy for single-page cleanup for PHOT is as follows:
- Starting at the root of the PHOT chain, create an OR'd bitmap of the modified columns in the chain until you reach a tuple that is not visible to all snapshots.
- Walk backwards, OR-ing the modified column bitmaps. Stop when the bitmap matches the one from step 1. As we walk backwards, identify "key" tuples, which are tuples where the OR'd bitmap changes as you walk backwards. If the OR'd bitmap does not include all indexed columns for the table, also include the root of the PHOT chain as a key tuple.
- Redirect each key tuple to the next key tuple.
- Mark all line pointers for all non-key tuples as dead. Storage can be removed for all tuples except the last one, but we must leave around the modified columns bitmaps for all key tuples except the first one (i.e., the new root of the chain).
For our previous example, once all tuples are visible to all snapshots, our PHOT page can be pruned to look something like this:
test_a_idx 0 1 2 3 test_b_idx 0 1 2 test_c_idx 0 2 3 lp X X 3->5 X 5 heap (3,2,3) bitmap x-x
This leaves us with 10 index tuples, 5 line pointers (3 dead), 1 heap tuple, and 1 bitmap. Before HOT, this intermediate state would have 15 index tuples, 5 line pointers (4 dead), and 1 index tuple.
Vacuum
When it comes time to vacuum indexes, we can reclaim the dead line pointers and remove the associated index tuples. This is very similar to vacuum today, but vacuuming must be prepared for some index tuples to be "missing" for partial heap only tuples.
test_a_idx 3 test_b_idx 2 test_c_idx 2 3 lp 3->5 5 heap (3,2,3) bitmap x-x
Without PHOT, this final state would have 3 index tuples, 1 line pointer, and 1 heap tuple. With PHOT, we have 4 index tuples, 2 line pointers, 1 heap tuple, and 1 bitmap.
Ideally, we would also remove unnecessary index tuples such as the "2" in test_c_idx. This would help us avoid breaking other optimizations such as index-only scans, but further investigation is needed to determine the feasibility of such index tuple cleanup. (Operations such as index-only scans may require additional work to continue working as expected.)
Index Operations
Index Creation and Deletion
As with HOT, additional work to support index operations will be required. This is another area that requires further investigation.
Index-Only Scans
One optimization that PHOT may complicate is index-only scans. Index-only scans largely depend on the visibility map, but with PHOT, index tuples are not guaranteed to be valid return results even when a page is marked all-visible. For the aforementioned PHOT example, even after vacuuming, there are multiple index entries in test_c_idx for the same heap tuple. For index-only scans to work, we either need a way to avoid skipping the heap page when PHOT was used (by either not updating the visibility map or by adding an additional map to track pages that use PHOT) or we need to remove unnecessary index tuples as part of vacuuming (e.g., we'd remove the "2" from test_c_idx in the example above). As with other index operations, this is another area that requires further investigation.
Interaction with HOT
It should be possible to "weave" between HOT and PHOT in a chain of updates. This leaves us with the following cases:
- HOT chain followed by PHOT chain: Here, the root tuple for the HOT chain should also be considered the root tuple for the PHOT chain. If all HOT tuples before the PHOT chain are visible to all snapshots, it is possible to prune the HOT chain entirely (the root tuple may still be needed for the PHOT chain).
test_a_idx 0 1 test_b_idx 0 1 lp 1 2 3 4 5 heap (0,0,0) (0,0,1) (0,0,2) (1,0,2) (1,1,2) bitmap x-- -x- test_a_idx 1 test_b_idx 1 lp 4->5 5 heap (1,1,2) bitmap -x-
- PHOT chain followed by a HOT chain: In this scenario, the last PHOT tuple should be considered the root of the HOT chain. Normal pruning rules for the HOT chain apply otherwise. Note that even though the tuple data storage for the root of the HOT chain can be reclaimed, we must preserve the modified columns bitmap.
test_a_idx 0 1 test_b_idx 0 1 lp 1 2 3 4 5 heap (0,0,0) (1,0,1) (1,1,2) (1,1,3) (1,1,4) bitmap x-x -xx test_a_idx 1 test_b_idx 1 lp 2->3 3->5 5 heap (1,1,4) bitmap -xx
- Intermediate HOT chain between PHOT chains: Here, the PHOT tuple just before the HOT chain is considered the root tuple. If all HOT tuples are visible to all snapshots, it is possible to prune the HOT chain entirely.
test_a_idx 0 1 test_b_idx 0 1 lp 1 2 3 4 5 heap (0,0,0) (1,0,0) (1,0,1) (1,0,2) (1,1,2) bitmap x-- -x- test_a_idx 1 test_b_idx 1 lp 2->5 5 heap (1,1,2) bitmap -x-
- Intermediate PHOT chain between HOT chains: In this case, the root of the HOT chain should be considered the root tuple for the PHOT chain. If all HOT tuples before the PHOT chain are visible to all snapshots, it is possible to prune the HOT chain entirely (the root tuple may still be needed for the PHOT chain). For the HOT chain after the PHOT chain, case 2 applies.
test_a_idx 0 1 test_b_idx 0 lp 1 2 3 4 5 heap (0,0,0) (0,0,1) (1,0,1) (1,0,2) (1,0,3) bitmap x-- test_a_idx 0 1 test_b_idx 0 lp 1->3 3->5 5 heap (1,0,3) bitmap x--
Performance Benchmarks
Early benchmarks show improvements of ~34% in TPS for a short pgbench run where each table had 5 additional text columns and indexes on every column. With additional indexes and columns, the TPS bump should theoretically be even higher. For a short pgbench run with no table modifications, a ~2% bump in TPS was observed with PHOT, showing that regular pgbench runs are not significantly affected.
As work on the project continues, many more benchmarking results will be added.
Tradeoffs
This feature makes the following tradeoffs:
- Index bloat for heap bloat: Fewer index tuples will need to be created an maintained, but additional heap bloat is incurred in the form of additional line pointers and tuple header bitmaps that cannot be removed for the lifetime of all tuples in the chain. However, aggressive single-page cleanup strategies should allow us to reduce this additional heap bloat to a minimum. This is a similar tradeoff that HOT makes, although PHOT requires us to keep some more information around (i.e., bitmaps and line pointers versus just line pointers).
- Read performance for update performance: For long chains, a read penalty may be incurred from traversing many tuples in the page. This performance penalty may be negligible for the vast majority of cases, but it is still an important thing to measure. On the other hand, update performance should improve greatly, especially when there are many indexes and columns for a table. As before, this is a similar tradeoff that HOT makes, although PHOT is much less restricted.
- Simplicity for complexity: The majority of the complexity for PHOT is added in the cleanup portion and the table scan portion. As before, this tradeoff is similar to HOT but probably slightly worse.
List of Patches
As of this writing, only the prototype patch for PHOT is available. This patch demonstrates a few basic pieces of PHOT and is primarily intended to help spark further discussion.
Roadmap
The current goal for PHOT is inclusion in PostgreSQL 15. To meet this goal, the code would need to be committed by approximately April 2022.
