Re: Tepid: selective index updates for heap relations
Re: Tepid: selective index updates for heap relations
От:
"Greg Burd" <greg@burd.me>
Дата:
I should have checked and rebased before I posted v59, apologies. Here's v60 which should be clean against 1c4b1de8885. Also fixed the following oversights: 1. CLUSTER / VACUUM FULL data loss + index staleness on SIU tables — the heap rewrite left the stale HEAP_INDEXED_UPDATED bit on flattened tuples, so readers ran the staleness test against a now-meaningless inline bitmap and dropped live rows (and returned nothing via index). Fixed by clearing the marker in reform_tuple. Hit any SIU table after a routine VACUUM FULL. 2. amcheck heapallindexed false positive — its bloom-filter fingerprint of a flagged leaf TID never matched the plain heap TID it re-derives, raising a spurious "lacks matching index tuple." Fixed by stripping the marker while fingerprinting in verify_nbtree. 3. Tooling - pageinspect 1.14 — bt_page_items now reports the real offset in ctid/htid (was showing an inflated offset) and adds a hot_indexed column exposing the marker. - Sentinel-safe strip — ItemPointerGetOffsetNumber/ItemPointerCompare strip bit 14 but leave the SpecToken/MovedPartitions offset sentinels untouched (a self-inflicted regression caught during development). best. -greg
Re: Tepid: selective index updates for heap relations
От:
"Greg Burd" <greg@burd.me>
Дата:
I've create cf-6869 and rebased to fix conflicts due to a single conflict, the usual catversion.h bump. -greg
Re: Tepid: selective index updates for heap relations
От:
Chao Li <li.evan.chao@gmail.com>
Дата:
> On Jul 21, 2026, at 05:34, Greg Burd wrote:
>
>
> On Fri, Jul 17, 2026, at 4:12 PM, Bharath Rupireddy wrote:
>> Hi,
>>
>> On Thu, Jul 16, 2026 at 3:05 AM Greg Burd wrote:
>>>
>>> Rebased onto 3cf5264557b to address conflicts, no other changes.
>>
>> Thanks for working on this. I previously played around with PHOT and
>> WARM a bit and built some context, but I need to refresh my memory and
>> give things a re-read.
>
> Thanks for looking at it!
>
>> The patches cover a lot. Reducing the diff to the core and posting the
>> stats, amcheck, and logical replication patches later would make
>> review easier. I managed to get through 0001 and 0002 so far.
>
> Yes, the 0001 and 0002 work is really a direct re-posting of the same two patches on my cf-5556 work that moves HeapDetermineColumnsInfo() into the executor. That was necessary work for the "HOT for Expression Indexes" but even more so for this work because this involves changing the contract between the table AM and the index AM as goverened by the executor to allow for cases other than TU_All/Summarizing/None.
>
> Yes, it is dense and I should try to chop it up a bit more. I think at this stage it the viability of the idea hinges on the format changes and their long term implications. If those aren't accepted (and I'm on the fence myself on the "bit14" idea) then I have to get other foundational changes in before this could fly so I wasn't super concerned about having the final patch layout.
>
> The tight integration of the TID abstraction across the table AM, the index AM and the executor is something that is hard to ignore and hard to work around. The TID abstraction is a heap specific thing (IMO) that works very well but is a very leaky and at times a highly limiting one.
>
>> I would be more interested in focusing the initial discussion on the
>> key design decisions. Where to store the modified index bitmap (it is
>> per-row version). How we get vacuuming right. How bitmap scans and
>> index scans produce correct results. How on-disk row format changes
>> are acceptable. How upgrades work for migrating existing databases.
>> How replication (logical and streaming) works and any impact on
>> downstream systems (replicas, subscribers, etc.). How it impacts
>> tooling (in-core like amcheck, pg_upgrade, pageinspect, and external
>> ones).
>
> Yes, all good topics.
>
>> Most importantly, the trade-offs. We are going to have more heap bloat
>> at the cost of less index bloat, which is fine since most OLTP
>> workloads go via indexes, but does it impact analytical workloads that
>> scan the heap? How does it impact vacuum performance? Do we know how
>> many customers in practice modify indexed columns (not exact numbers,
>> but some data points to keep the motivation up for this feature)? The
>> fact that the modified index column bitmap is now stored per tuple
>> version means fewer rows fit per page, which means more pages per
>> relation, and does it also mean fewer HOT updates because updated rows
>> cannot fit in the same page since some space is used for storing the
>> bitmap, causing more index maintenance in turn?
>
> Yes, there are trade-offs to call out. The heap pages will a) have more meta-data on them in the form of the bitmaps on UPDATE that collapse into dead tuples and b) yes there will be longer redirect chains that are harder to fully collect during vacuum and they will prevent pages from being marked frozen more frequently. That is true, and that has a cost.
>
>> Also, the naming (SIU, Tepid, HOT-INDEXED, HEAP_INDEXED_UPDATED, and
>> previously PHOT, WARM) is a bit confusing to me. Could we simplify the
>> names and use them consistently?
>
> I agree, and naming is hard. Happy to take on any ideas here. I've been calling it "tepid" and explaining it as "selective index updates" and in a way that is "partially HOT (PHOT)" but in other ways the tepid model isn't a "heap-only tuple (HOT)" at all, it's not heap-only it is heap and SOME indexes but not ALL. IDK what to call it, but maybe that's something to work out if/when the idea(s) and trade-offs are accepted and we're finalizing the code for commit?
>
>> Some quick comments on the patches.
>>
>> 0001:
>>
>> 1/ Can 0001 be discussed in a separate thread? It seems to provide
>> good coverage for HOT updates on its own and is worth discussing and
>> perhaps getting committed separately.
>
> This was pre-amble for changes that I'd planned for the HOT for Expressions patches. It's not strictly necessary in tepid, I should just drop it.
>
>> 2/
>>
>> +SELECT id FROM hot_xml_test WHERE xpath('/person/name/text()', doc) =
>> ARRAY['Alice2'::text];
>> +ERROR: operator does not exist: xml[] = text[]
>> +LINE 1: ..._xml_test WHERE xpath('/person/name/text()', doc) = ARRAY['A...
>> + ^
>> +DETAIL: No operator of that name accepts the given argument types.
>> +HINT: You might need to add explicit type casts.
>>
>> +INSERT INTO hot_xml_test VALUES
>> + (1, 'Alice30'),
>> + (2, 'Bob25');
>> +ERROR: could not identify a comparison function for type xml
>> +SELECT * FROM get_hot_count('hot_xml_test');
>>
>> Are these expected?
>
> Yeah no, my mistake. The more I looked at the XML tests the more they didn't really add value so I've removed them.
>
>> 0002:
>>
>> 1/
>> -SELECT * FROM base_tbl;
>> +SELECT * FROM base_tbl ORDER BY a;
>>
>> ERROR: cannot insert a non-DEFAULT value into column "b"
>> DETAIL: Column "b" is a generated column.
>> -SELECT * FROM gtest1v;
>> +SELECT * FROM gtest1v ORDER BY a;
>>
>> -DELETE FROM main_view WHERE a IN (20,21);
>> +DELETE FROM main_view WHERE a = 20 AND b = 31;
>> NOTICE: main_view BEFORE DELETE STATEMENT (before_view_del_stmt)
>> NOTICE: main_view INSTEAD OF DELETE ROW (instead_of_del)
>> -NOTICE: OLD: (21,10)
>> -NOTICE: main_view INSTEAD OF DELETE ROW (instead_of_del)
>> NOTICE: OLD: (20,31)
>> +NOTICE: main_view AFTER DELETE STATEMENT (after_view_del_stmt)
>> +DELETE 1
>>
>> The commit message says this fixes nondeterministic behavior in
>> existing tests due to row ordering. I think these are unrelated to
>> this work and could be discussed and committed separately.
>
> Sure, possibly. The instability became apparent when working on the first two patches.
>
>> 2/ ExecUpdateModifiedIdxAttrs() replaces HeapDetermineColumnsInfo().
>> Why do we need to move modified index attribute computation to the
>> executor and make every TTS and table AM pay that cost? HOT and
>> modified index attributes are purely heap AM specific. If the executor
>> ever needs the list of modified index attributes, why not let the AMs
>> provide it as an out parameter (similar to how we pass the HOT hint in
>> TU_UpdateIndexes format)?
>
> The contract between the index and table AMs is governed by the the executor, or it should be (IMO), and the TU_All/Summarizing/None model that exists now is very much a heap-ism (leaky, too heap-MVCC specific) and so breaks down in the face of any table AM that has a different MVCC model. IMO the executor should be defaulting to only updating the indexes that are impacted by an update as a rule but allow for table AMs to influence that. Why? Because a table-agnostic executor should have as a goal not updating indexes unless those updates are required by the modifications underway. Doing more than that amount of work as a rule is assuming things the executor shouldn't know about in the table and/or index implementations. So, the executor (after patch 0002) will only update indexes that overlap with the modified attributes.
>
>> I read the commit message saying that finding this set of attributes
>> is not heap-specific but more general to all table AMs and could
>> inform other decisions about when index inserts are required. But is
>> it needed for this feature? If not, I think it can be discussed
>> separately.
>
> Yes, how else is the heap supposed to be able to communicate which subset of indexes to update in a generic manner? I tried other methods and they all felt (to me) like they were working around a leaky abstraction rather than fixing the root cause. Your view may differ.
>
>> 3/
>> - SELECT FROM injection_points_detach('heap_update-before-pin');
>> - SELECT FROM injection_points_wakeup('heap_update-before-pin');
>> + SELECT FROM injection_points_detach('simple_heap_update-before-pin');
>> + SELECT FROM injection_points_wakeup('simple_heap_update-before-pin');
>>
>> Once we find the need for 0002, can we just leave the injection point
>> name as-is to reduce the mechanical diff?
>
> I can re-try and find out if it matters.
>
>> 4/ Nits.
>> Typos.
>> + * are in the UPDATE statment and are known to be referenced by at least one
>> + * ExecGetAllUpdatedCols(). Desipte the name it provides the set of
>
> Fixed.
>
>> No need to specify test names in the comments, because they can change anytime.
>
> I disagree this time because the comment calls out a very very subtle hidden issue that is induced by that test and I felt should be documented so the next hacker could understand and avoid it earlier in the process than I did.
>
>> * heap_modifiy_tuple(). There is one test in tsearch.sql that does just
>> + * that, modifies an indexed attribute that isn't specified in the SQL and
>>
>> 5/
>> + /* attidx is zero-based, attrnum is the normal attribute number */
>> + AttrNumber attrnum = attidx + FirstLowInvalidHeapAttributeNumber;
>>
>> Is every TTS implementer expected to support all system columns that
>> FirstLowInvalidHeapAttributeNumber implies? Asking because 0002 moved
>> this code to the executor in ExecCompareSlotAttrs.
>
> Interesting point. Yes, I did move a heap-ism into the executor (facepalm), something I claim to be against. :)
>
> I'm going to take the abstraction critique seriously and move the mechanism of "which attributes changed" behind the slot/table-AM boundary, while keeping the policy "only maintain indexes whose attributes overlap the change" in the executor.
>
> Concretely: ExecCompareSlotAttrs() as written leaks heap assumptions upward (it enumerates over FirstLowInvalidHeapAttributeNumber and hand-handles system columns like tableoid), which is fair to call out. The comparison of two versions of a row is something the AM should answer for its own attributes and its own notion of "a version changed"; the executor should only collect that changed-set and intersect it with each index's attribute set to decide which indexes need fresh entries. That split is the honest form of "the executor governs the table-AM/index-AM contract, the table AM owns its storage mechanics."
>
> The reason I can't instead adopt the suggested out-parameter model, have the AM return modified_attrs from table_tuple_update(), is a matter of ordering, and I think it's the same ordering that a couple of the concurrency questions in the thread are also tripping on, so it's worth stating plainly:
>
> modified_attrs is an input to table_tuple_update(), not a byproduct of it. The heap AM reads it during the update to decide, before it writes anything, (a) whether the update can stay HOT / selectively-indexed vs. must update all indexes (HeapUpdateHotAllowable), (b) the tuple lock mode (HeapUpdateDetermineLockmode), and (c) whether the replica-identity key changed. The executor then uses the same set after the update to drive which indexes get fresh entries. A value returned from the update call would arrive after every one of those decisions had already been made it's structurally too late to inform them. So the changed-attribute set has to be available to, and passed into, the table AM, not produced by it.
>
> The clean way to satisfy both constraints that comes to mind is a slot/AM-level comparison the executor calls to build the set (AM owns "what changed"), then passes into the update (executor owns "which indexes"). That keeps the decision points in the right order and removes the heap-ism from the executor. To that end I've added to the table AM: table_modified_attrs() callback in an updated 0002 and in heap heapam_modified_attrs() in a new 0003 patch.
>
> (Separately and related to that: this is also why the "reduces buffer-lock hold time" line in the 0002 commit message is both wrong and misleading the computation was always pre-lock and I'm dropping it.)
>
>> 6/ The commit message says that having ExecUpdateModifiedIdxAttrs() in
>> the executor reduces the time the buffer lock is held by computing
>> modified index columns before table_tuple_update(). How is this
>> correct from a concurrency perspective? If another transaction
>> modifies the same tuple between when the executor compares columns and
>> when heap_update acquires the buffer lock, what happens? The executor
>> locks the old tuple explicitly only when it detects concurrent updates
>> or deletes to the same tuple, but does not hold the tuple lock the
>> first time.
>
> Good catch, and the commit message is misleading here I'll reword it. The "reduces the time the buffer lock is held" line oversells a benefit that isn't real and, worse, invites exactly the concurrency worry you raised. In today's tree HeapDetermineColumnsInfo() already runs before heap_update() takes the buffer lock (it's computed up front from oldtup/newtup), so moving the computation into the executor doesn't change when, relative to the buffer lock, the comparison happens. The motivation for the move is the table-AM/index-AM contract, not lock-hold latency; I'll drop that paragraph so it stops implying otherwise.
>
> On the concurrency correctness itself, there's no window to exploit:
>
> - ExecUpdateAct() computes modified_attrs from (oldSlot, newSlot) and immediately calls table_tuple_update() in the same function, with no lock dropped and no yield between the two. There is no "compare, then later acquire the buffer lock" gap — the comparison is not protected by, nor waiting on, any buffer lock, in either the old or new arrangement.
>
> - Concurrency is still detected exactly where it always was: inside heap_update(), under the buffer lock, via the xmax/visibility check. If another transaction updated the row first, heap_update() returns TM_Updated (unchanged by this patch).
>
> - On TM_Updated, ExecUpdate() runs the normal EPQ path: table_tuple_lock() the latest version, EvalPlanQual(), re-fetch the latest oldSlot and rebuild the new slot, then goto redo_act — which re-enters ExecUpdateAct() and recomputes modified_attrs against the fresh versions.
>
> - modified_attrs is consumed only in ExecUpdateEpilogue() (the index-insert step), which runs only on the TM_Ok path. A modified_attrs computed against a version that lost the race is discarded and recomputed before any index maintenance happens.
>
> So the set of indexes we maintain is always derived from the same (old, new) pair the update was actually applied to; a concurrent update forces a re-read and recompute before index inserts, identical in effect to how HeapDetermineColumnsInfo() behaves today. The executor doesn't need to hold a tuple lock across the comparison for the same reason it doesn't today — the AM's TM_Updated/EPQ protocol is the serialization point.
>
> I'll fix the injection-point/comment nits and drop the misleading commit-message paragraph in the next revision.
>
>> I will continue reading the other patches in the coming weeks.
>>
>> --
>> Bharath Rupireddy
>> Amazon Web Services: https://aws.amazon.com
>
> best.
>
> -greg
Thanks for the patch.
I have spent some time reviewing v67 0001-0009. git am failed at 0010, so a rebase is needed.
I think I have only got a rough idea of what this feature does and how it works so far. I believe I will still need much more time to understand the details.
I just want to raise a few design comments I have so far:
* Does it make sense to add a table-level option to make this feature opt-in? From my understanding, this feature will benefit tables that have many indexes across multiple fields. Although benchmarks are attached, I am afraid they may not be able to simulate all users' data models. Making it opt-in would allow users to easily evaluate the feature with their own tables and enable it only on tables that really benefit from it. I realize that turning it on is easy, but turning it off may require table rewritten and index rebuilds. However, I think that is acceptable, as many other ALTER TABLE operations may also require so.
* When an index entry points to a stale tuple chain, it still returns the entry and sets xs_hot_indexed_stale, which means callers of index_getnext_slot() need to check this new state. This seems to weaken the current index scan API contract. Is there any thought behind exposing this state to callers instead of filtering stale entries internally?
I need to stop here to handle some other work. I will come back with more comments later.
Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/
Re: Tepid: selective index updates for heap relations
От:
"Greg Burd" <greg@burd.me>
Дата:
On Thu, Jul 9, 2026, at 7:26 AM, Alexander Korotkov wrote:
> Hi, Greg!
>
> Thank you for your work. It looks huge.
Thanks for looking at it, it is.
> On Tue, Jun 30, 2026 at 8:21 PM Greg Burd wrote:
>> Write path. heap_update gains a third mode (HEAP_SELECTIVE_INDEX_UPDATE)
>> alongside HEAP_UPDATE_ALL_INDEXES and HEAP_HEAP_ONLY_UPDATE. It keeps the
>> new tuple heap-only with its inline bitmap, and the executor inserts fresh
>> entries only into the indexes whose attributes changed (ExecSetIndexUnchanged);
>> the fresh entry points at the new heap-only tuple, not at the chain root.
>> If the page can't fit the new tuple, the update is downgraded to a normal
>> non-HOT update.
>
> I didn't yet read the whole design nor the whole patches. But this is
> the point that raises questions for me. How could this work with the
> present Bitmap Scans? I didn't find the direct answer in this thread.
> As you describe, entries to the indexes whose attributes changed are
> pointing to the new heap-only tuple (that effectively makes the tuple
> not heap-only, but that's just terminology question). For instance,
> you have old tuple T1, "new heap-only tuple" T2, unchanged index I1,
> and changed index I2. Both T1 and T2 have values V11 for I1. T1 and
> T2 have values V21 and V22 for I2 correspondingly. So, in this
> example according the paragraph above the logical contents of I1 is:
> V11 => T1, logical contents of I2 is V21 => T1, V22 => T2. Imagine,
> user searches for the tuple containing V11 for I1 and V22 for I2 with
> BitmapAnd. I1 side of BitmapAnd will return ctid of T1, while I2 side
> of BitmapAnd will return ctid of T2. That gives nothing in the
> intersection, while T2 is obviously matches the criteria.
You're right, and it's a real bug, not a theoretical one. I totally overlooked
it. I reproduced your exact scenario against the current tree:
CREATE TABLE t (id int PRIMARY KEY, c1 int, c2 int) WITH (fillfactor=50);
CREATE INDEX i1 ON t(c1); -- unchanged by the update
CREATE INDEX i2 ON t(c2); -- changed by the update
INSERT INTO t VALUES (1, 11, 21);
UPDATE t SET c2 = 22 WHERE id = 1; -- HOT-indexed: only c2/i2 changes
SET enable_indexscan = off; SET enable_seqscan = off; -- force BitmapAnd
SELECT id, c1, c2 FROM t WHERE c1 = 11 AND c2 = 22;
-- (0 rows) <-- wrong; (1, 11, 22) matches both
The leaf TIDs are exactly as you describe:
i1 (unchanged): c1=11 -> (0,1) [chain root]
i2 (changed): c2=21 -> (0,1), c2=22 -> (0,2) [fresh entry at new tuple]
So BitmapAnd intersects {(0,1)} with {(0,2)} and gets nothing. The heap
side of the scan does resolve both TIDs to the live tuple and does run the
recheck -- but that all happens *after* the TID-bitmap intersection, which
has already thrown the row away. A false negative, and Bitmap Scans can't
tolerate those.
I had this covered for plain index scans and index-only scans, where the
per-entry crossed-attribute recheck runs on the way to the heap, and I missed
that BitmapAnd makes its decision before any of that machinery gets a turn.
Thank you for catching it before it went any further.
> As you mention downthread, Bitmap Scan can tolerate false positives,
> but it can't tolerate false negatives. Bitmap Scan assumes CTIDs to
> be independently indexed pointers, and therefore corresponding bitmaps
> could be freely overlapped. I think Bitmap Scans was one of the
> critical weakness in WARM, and it is the question to be address in any
> further attempt in this direction.
I'm going to sit with it rather than fire back a half-formed fix; if you already
see why this is or isn't surmountable, I'd much rather hear that reasoning now.
> ------
> Regards,
> Alexander Korotkov
> Supabase
I'll publish v58 (rebased onto d3a10f3e128) and then hold the patch set where it
is until this is resolved -- no point polishing something with a hole in the
read path until I can plug it. I'll add a test case that captures this and
include it in future patches.
One other fix since v57: the macOS cfbot failure was a flaky regression test, not
a code bug. The hi_reclaim case in hot_indexed_updates.sql (via 002_pg_upgrade's
old-instance run) asserted a post-VACUUM state — chain collapsed to a redirect,
member count back to zero — but both of those outcomes depend on the deleted
tuple falling below the global xmin horizon, which a concurrent snapshot
elsewhere in the regression cluster can pin back indefinitely. So the test
passed or failed on timing. My v55-era attempt at this only traded one
horizon-dependent assertion for another; I confirmed the flakiness by
reproducing it under a held-open REPEATABLE READ snapshot.
The test now asserts only horizon-independent invariants: a HOT-indexed member
is always present (the live version can't be pruned), the live row still
resolves through the secondary index by its current key, and none of the
superseded keys surface. Collapse and snapshot-gated reclaim stay in the
hot_indexed_adversarial isolation spec, where transaction ordering — hence the
horizon — is controlled, and the collapse is validated by reader consistency
across it. Verified the new assertions hold under a deliberately held-back
horizon.
Thanks again; this is exactly the kind of review I was hoping the
design-questions-first post would draw out.
best.
-greg
Re: Tepid: selective index updates for heap relations
От:
"Greg Burd" <greg@burd.me>
Дата:
Hello, I've rebased Tepid (e994f956e48) and done a bit of minor cleanup. No new features, no design changes. Same nine commits, same structure. Two commits are unchanged (the HOT-behavior test commit and the benchmark harness). * pg_surgery now understands SIU stubs. heap_force_freeze/heap_force_kill skip xid-free HOT-indexed stubs instead of erroring or corrupting them, with a regression test that builds a real stub. (This was the one substantive gap the macOS reviewer flagged against v48.) * Prune/vacuum correctness — the most important fixes: - Restored upstream's hard elog(ERROR, "dead heap-only tuple … not linked to from any HOT chain") guard for the classic-HOT case. v48 silently reclaimed such a tuple, which would have masked real heap corruption; SIU's legitimate stub handling is now cleanly separated from that error path. - Fixed a primary/standby divergence bug: the lazy_vacuum_heap_page WAL record must always log a hardcoded false cleanup-lock flag (that call site never re-points redirects/stubs), and v48 was passing the runtime-variable value. - Added bounds checking (Assert(bmnatts <= relnatts) plus a defensive clamp) before the stub-bitmap union/subset operations, closing a stack-buffer-overflow risk from a corrupt or unbounded stub natts. * Executor / index-scan: - Fixed an out-of-bounds read in ExecCompareSlotAttrs (missing continue after the system-attribute branch). - RelationGetIndexedAttrs now parses raw catalog text directly rather than going through RelationGetIndexExpressions/Predicate, which could const-fold away Var references and under-report indexed attributes. - Removed dead code (an unused idx_attrs fetch in simple_heap_update, an empty branch in index_delete_check_htid) and corrected an inaccurate "must mirror heap_multi_insert" comment. * amcheck now reports corruption on out-of-range or self-referential stub forward links, matching the existing redirect-link check. * Statistics: the n_hot_indexed counter and the matched/skipped pgstat counters now exclude stubs and fire only after the partial-index predicate check (v48 over-counted). * Logical replication: rebased over upstream's new conflict_log_destination feature (a subscription bit-flag collision resolved, 0x00080000->0x00100000), and the subscription field/option renamed hotindexedmode→hotindexedonapply for clarity, with a matching psql \dRs+ display fix (shows the word, not the raw char code). * Tests: hardened the count-sensitive tables against an autovacuum lock-steal race (autovacuum_enabled = false), and replaced a relpages-based assertion (only updated by VACUUM/ANALYZE, so trivially true) with a real pg_relation_size check. * Plus routine cleanups — removed a few redundant/unused includes, fixed typos. best. -greg
Re: Tepid: selective index updates for heap relations
От:
"Greg Burd" <greg@burd.me>
Дата:
Rebased onto 3cf5264557b to address conflicts, no other changes. -greg
Tepid: selective index updates for heap relations
От:
"Greg Burd" <greg@burd.me>
Дата:
Hello Hackers,
This is a set of patches that extend the heap-only tuple (HOT) update optimization model such that only those indexes directly impacted by the update need be updated. The motivation is simple, reduce "bloat" (read: reduce VACUUM overhead) and speed up heap updates by avoiding unnecessary index updates. I call this "tepid" because it is decidedly not Heap-only (HOT), nor is it "WARM", nor is "partially HOT (PHOT)"... it's "Tepid" :)
This is a long one. Thank you in advance for any time you dedicate to this, I appreciate your help and look forward to working together to finish this feature.
Overview
========
HOT keeps an UPDATE off the indexes only when no indexed column changes. Any
update that touches an indexed column today becomes a non-HOT update: a new
heap tuple (often on a new page) plus a fresh entry in *every* index, with the
attendant WAL, bloat, and index write amplification.
Selective Index Updates (SIU, internally "HOT-indexed") lets such an update
stay a heap-only tuple on the same page and insert a fresh entry only into the
indexes whose attributes actually changed. The pre-update index entries are
left in place and become potentially *stale*: an entry for an old key still
chain-leads to the live tuple, whose current key differs.
The new tuple records, inline in its own tail, a small bitmap of which indexed
attributes changed at its hop. A scan that walks the chain to the live tuple
unions the bitmaps of the hops it crossed; if that union overlaps the arriving
index's key columns, the entry is stale and is dropped, and the row is
re-supplied by the fresh entry the same update planted. The crossed-attribute
bitmap -- not a value recheck -- is the staleness authority.
This is, deliberately, the same family of idea as WARM and PHOT.
Performance
===========
A/B run of two release (cassert=off) builds -- origin/master vs the SIU
series -- on a single Apple Silicon laptop (macOS), pgbench, scale 5
(siu_table = 500k rows with 3 secondary indexes; wide_table = 5k rows with 16
secondary indexes + PK), 8 clients / 4 threads, 20 s per cell. pgbench runs
for a fixed time, so each variant completes a different number of updates; the
write-amplification signal is therefore reported as WAL bytes per update.
workload (indexed cols changed) TPS master->tepid WAL/update master->tepid
--------------------------------- -------------------- ------------------------
simple_update (control; HOT both) 32.6k -> 32.1k ( 0%) 265 -> 265 B ( 0%)
hot_indexed_update (1 of 4) 58.2k -> 68.6k (+18%) 636 -> 487 B (-23%)
wide, 1 of 17 indexes 33.6k -> 41.7k (+24%) 1466 -> 598 B (-59%)
wide, 8 of 17 indexes 37.4k -> 47.3k (+26%) 1498 -> 1015 B (-32%)
wide, 16 of 17 indexes 36.3k -> 37.3k ( +3%) 1530 -> 1490 B ( -3%)
read_indexscan (read-only) 164.4k ->161.3k ( -2%) n/a (no writes)
Design overview
==================
On-disk marker. A HOT-indexed update makes the new version a heap-only tuple
(HEAP_ONLY_TUPLE) and additionally sets the new infomask2 bit
HEAP_INDEXED_UPDATED (0x0800, previously free). Appended after the tuple's
attribute data, in the final ceil(natts/8) bytes of its line-pointer item, is a
fixed-size bitmap of the indexed attributes that changed at this hop (relative
to the prior chain member). Tuple deforming stops at natts and never sees it.
The bitmap is sized by the tuple's OWN attribute count at write time
(HeapTupleHeaderGetNatts), not the relation's current natts: ADD COLUMN raises
the relation's natts without rewriting existing tuples, so a chain can hold
hops whose bitmaps were sized for different (smaller) natts, and every consumer
locates a hop's bitmap from that hop's own write-time natts. The bitmap is
inline in the data-bearing tuple -- there is no separate "tombstone" line
pointer.
Write path. heap_update gains a third mode (HEAP_SELECTIVE_INDEX_UPDATE)
alongside HEAP_UPDATE_ALL_INDEXES and HEAP_HEAP_ONLY_UPDATE. It keeps the
new tuple heap-only with its inline bitmap, and the executor inserts fresh
entries only into the indexes whose attributes changed (ExecSetIndexUnchanged);
the fresh entry points at the new heap-only tuple, not at the chain root.
If the page can't fit the new tuple, the update is downgraded to a normal
non-HOT update.
Read path. heap_hot_search_buffer walks the chain to the live tuple and unions
the per-hop modified-attrs bitmaps of every hop crossed *after* the arriving
entry's own tuple (its own producing hop does not count -- a fresh entry is
never stale for its own index). The index-access layer tests that union
against the arriving index's key columns: overlap => stale, drop; disjoint =>
current, return. No value comparison and no leaf key are needed, so scans
never have to materialize the leaf IndexTuple for staleness purposes, and the
mechanism is identical for every access method.
Prune / collapse. A dead mid-chain HOT-indexed tuple cannot be reclaimed to
LP_UNUSED while stale btree entries still point at its LP, and its bitmap is
what later readers union. prune collapses a dead prefix: each preserved dead
key tuple is rewritten in place as an xid-free "stub" (LP_NORMAL,
HEAP_INDEXED_UPDATED, natts == 0, frozen, t_ctid.offnum forwarding to the next
survivor, carrying the same inline bitmap), and a dead member whose attributes
are wholly subsumed by later hops is reclaimed instead. The root is redirected
to the first survivor. VACUUM's index cleanup sweeps the stale leaves, then a
later prune reclaims the stubs and re-points the redirect, collapsing back to
classic HOT. The collapse rides the existing prune/freeze WAL; logical
decoding sees an ordinary UPDATE.
On-disk format commitment
=========================
This is a permanent format addition and we want explicit agreement before
freezing it:
- One infomask2 bit (0x0800). pg_upgrade is unaffected (clusters predating
SIU have no such items); a pg_upgrade test carries chains, an ABA-cycled
column, a TOASTed indexed column, and collapsed stubs across an upgrade.
- A new interpretation of an LP_NORMAL item:
* a data-bearing HOT-indexed tuple (HEAP_INDEXED_UPDATED, natts >= 1)
with a trailing modified-attrs bitmap sized by the tuple's own natts;
and
* an xid-free collapse-survivor stub (HEAP_INDEXED_UPDATED, natts == 0) --
a signature no real tuple can produce. Because the stub overwrites
natts with the 0 sentinel, it preserves its write-time natts (needed to
size/locate the bitmap) in the otherwise-unused block-number half of
t_ctid; the offset half holds the forward link.
Every consumer of LP_NORMAL heap items must tolerate both. We have audited
the in-tree consumers; visibility-gated paths (seqscan, bitmap, ANALYZE,
index build) are inherently safe because stubs are XMIN_INVALID and the
trailing bitmap is past natts; amcheck and VACUUM/prune are stub-aware;
pg_surgery skips stubs (forcing a freeze/kill on one would corrupt the
heap); pageinspect and pgstattuple are read-only and merely imprecise.
- The bitmap is sized per-tuple by write-time natts, so ADD COLUMN over a
relation with live chains is safe even when it crosses an 8-attribute
boundary (which changes ceil(natts/8)); a regression test exercises
CREATE INDEX / DROP INDEX / ADD COLUMN (boundary-crossing) / DROP COLUMN
after a chain exists and reads back through it.
Alternatives considered and rejected: a separate relation fork (heavy, and the
marker must be co-located with the tuple for the chain walk); a separate
adjacent "tombstone" LP per hop (doubles line-pointer pressure; the inline
trailing bitmap needs no extra item); "redirect-with-data" LP_REDIRECT carrying
the bitmap (LP_REDIRECT has no storage for a payload); a new line-pointer flavor
(consumes scarce lp_flags space and touches far more code than reusing
LP_NORMAL + an infomask2 bit).
Eligibility
===========
A non-summarizing indexed attribute changing -- under any access method --
yields HEAP_SELECTIVE_INDEX_UPDATE unless a carve-out (6.1) applies. The cases
that DO work and are covered by tests are in 6.2; the distinction is deliberate,
because several restrictions an earlier (value-recheck) draft needed turned out
to be unnecessary once the crossed-attribute bitmap became the staleness
authority.
Carve-outs (deliberately conservative)
--------------------------------------
- System catalogs. A catalog UPDATE that changes a non-summarizing indexed
attribute stays classic HOT but never takes the HOT-indexed path: catalogs
are reached through access paths (systable scans, SnapshotDirty unique
checks, seqscans) we have not proven safe.
- Expression indexes: an UPDATE that changes an attribute an expression index
references. The bitmap is attribute-granular and cannot tell whether the
expression's VALUE changed; expression-aware selective maintenance is not
wired up. (This restriction may be liftable the same way the partial-index
one was -- see 6.2 -- but is kept until tested.)
- Every indexed attribute changed. Nothing can be skipped, so a plain
non-HOT update is cheaper (it avoids the chain-walk and bitmap overhead).
"Every" is an exact test; there is no percentage GUC.
- The logical-replication apply path, gated per subscription by
hot_indexed_on_apply (off / subset_only (default) / always): a HOT-indexed
update of a replica-identity attribute leaves a stale leaf the apply
worker's RI lookup must tolerate, which it does only when the indexed
attributes are a subset of the primary key.
State model: classic HOT and the HOT/SIU state changes
=========================================================
This section catalogs every relevant state and traces the outcomes, because the
correctness argument is entirely about which states a chain and its index
entries pass through. Notation: LP[n] is the line pointer at offset n; "{a,b}"
is a modified-attrs bitmap; "->" in t_ctid is the same-page successor offset.
8.1 Line-pointer (ItemId) states
--------------------------------
LP_UNUSED Free slot, no storage.
LP_NORMAL Points to an item (lp_off, lp_len). In SIU this item is one of:
- a real tuple (classic);
- a HOT-indexed tuple (HEAP_INDEXED_UPDATED, natts >= 1, with
a trailing bitmap); or
- a collapse-survivor stub (HEAP_INDEXED_UPDATED, natts == 0,
xid-free, forwarding via t_ctid.offnum). [NEW in SIU]
LP_REDIRECT Points to another offset; no tuple. Created by prune when a
chain root dies but heap-only members remain. (Unchanged by
SIU, but now there may be more than one redirect forwarding to
the same live tuple after a collapse.)
LP_DEAD Dead, reclaimable, no storage.
Tuple flag states (t_infomask2) and chain roles
------------------------------------------------
HEAP_HOT_UPDATED This tuple was HOT-updated; its t_ctid successor is a
heap-only tuple on the same page. (classic)
HEAP_ONLY_TUPLE No index entry points *directly* at the chain root for
this tuple's sake; it is reached by walking t_ctid.
(classic)
HEAP_INDEXED_UPDATED [NEW] This heap-only tuple belongs to a HOT-indexed
chain and carries an inline trailing modified-attrs
bitmap of the attributes that changed at this hop (the
bitmap is empty for a classic-HOT update promoted to keep
a HOT-indexed chain uniform). With natts == 0 the same
bit marks a collapse-survivor stub.
Root tuple First tuple in the chain; the tuple classic index entries
point at. Not heap-only.
Heap-only tuple A chain member reached via t_ctid. Under SIU a heap-only
tuple may ALSO be pointed at directly by a fresh
HOT-indexed index entry (this is the key departure from
classic HOT, where only the root is pointed at).
Index-entry states
------------------
Fresh entry Points at the heap-only tuple version whose indexed key it
matched at insertion. Its walk to the live tuple crosses no
later hop that changed its index's key, so the crossed union is
disjoint from its key columns: kept.
Stale entry A pre-update entry whose key the live tuple no longer holds (or
holds again only by coincidence after a cycle). Its walk
crosses a hop that changed its index's key: the union overlaps,
so it is dropped. The live row is re-supplied by the fresh
entry.
Read-side transient state (per scan, not on disk) [NEW]
-------------------------------------------------------
xs_hot_indexed_recheck The chain walk crossed a HOT-indexed hop after the
arriving entry's own tuple.
xs_hot_indexed_crossed The union of those crossed hops' modified-attrs
bitmaps (complete -- see Section 7).
xs_hot_indexed_stale Verdict: xs_hot_indexed_crossed overlaps the
arriving index's key columns. The executor (and
CLUSTER, IOS, and the apply RI lookups) drop the
tuple.
State transitions
-----------------
INSERT LP_NORMAL root tuple, not heap-only. One entry per index.
Classic HOT UPDATE (no indexed col changed) old tuple: +HEAP_HOT_UPDATED,
t_ctid -> new; new tuple: HEAP_ONLY_TUPLE. No new index
entries.
HOT-indexed UPDATE (some, not all, indexed cols changed; eligible) old
tuple: +HEAP_HOT_UPDATED, t_ctid -> new; new tuple:
HEAP_ONLY_TUPLE + HEAP_INDEXED_UPDATED + inline bitmap of
the changed attrs; fresh entries inserted only into the
changed indexes, each pointing at the new tuple;
unchanged indexes are untouched (their existing entries
still resolve through the chain).
Non-HOT UPDATE (ineligible, or page full) new tuple on a (possibly new)
page; a fresh entry in *every* index.
Prune/collapse dead prefix members -> reclaimed (bitmap subset of later
hops) or rewritten to xid-free stubs (forwarding,
bitmap-preserving); root -> LP_REDIRECT to first survivor.
VACUUM ambulkdelete sweeps stale leaves; a later pass reclaims
stubs and re-points the redirect -> classic HOT.
Worked example 1 -- selective maintenance and a stale drop
-----------------------------------------------------------
t(id PK, a, b, c), indexes t_a(a), t_b(b), t_c(c), fillfactor 50.
INSERT (1,10,20,30); UPDATE a=11; UPDATE b=21; UPDATE c=31.
Chain (the bitmap on a tuple = attrs changed on the hop INTO it):
LP[1] v1(a=10,b=20,c=30) root, HEAP_HOT_UPDATED, ->2 dead
LP[2] v2(a=11,b=20,c=30) heap-only, INDEXED_UPDATED{a}, ->3 dead
LP[3] v3(a=11,b=21,c=30) heap-only, INDEXED_UPDATED{b}, ->4 dead
LP[4] v4(a=11,b=21,c=31) heap-only, INDEXED_UPDATED{c} live
Index entries (fresh point mid-chain at the tuple they matched):
t_a: (10)->LP[1] stale (11)->LP[2] fresh
t_b: (20)->LP[1] stale (21)->LP[3] fresh
t_c: (30)->LP[1] stale (31)->LP[4] fresh
Scan a=11 via t_a -> LP[2]:
arrive AT LP[2] (own hop {a} not counted); cross ->3 {b}, ->4 {c}.
crossed = {b,c}; t_a keys = {a}; {a} & {b,c} = {} => fresh => return v4. OK
Scan a=10 via t_a -> LP[1] (stale):
cross ->2 {a}, ->3 {b}, ->4 {c}.
crossed = {a,b,c}; {a} & {a,b,c} = {a} => stale => drop. OK
(v4 is supplied once, by the fresh (11)->LP[2] entry.)
Scan b=21 via t_b -> LP[3]: crossed ->4 {c}; {b} & {c} = {} => return v4. OK
Worked example 2 -- ABA (the case a value recheck gets wrong)
-------------------------------------------------------------
INSERT (1,10,...); UPDATE a=11; UPDATE a=10. (a cycles 10 -> 11 -> 10)
LP[1] v1(a=10) root ->2 dead
LP[2] v2(a=11) {a} ->3 dead
LP[3] v3(a=10) {a} live
t_a: (10)->LP[1] stale (11)->LP[2] stale (10)->LP[3] fresh
Scan a=10 finds TWO entries with key 10 (LP[1] and LP[3]):
via LP[3]: zero hops crossed => fresh => return v3. OK
via LP[1]: cross ->2 {a}, ->3 {a}; crossed={a}; {a}&{a}={a} => drop. OK
Returned exactly once. A value recheck would compare leaf key 10 against
live a=10 for BOTH entries and keep both -> duplicate. The bitmap drops the
ancestor because a *changed* after LP[1], regardless of the coincident value.
Worked example 3 -- REINDEX over the chain
------------------------------------------
REINDEX t_a after example 2 rebuilds one entry, pointing at the live tuple
mid-chain: (10)->LP[3]. Zero hops crossed => fresh => returned once. OK
(The rebuild points at the live member, not the root, so it is never seen as
stale -- this is required for "drop on overlap" to be safe; a build that
pointed at the root carrying the live value would be wrongly dropped.)
Worked example 4 -- collapse to xid-free stubs
-----------------------------------------------
From example 1, VACUUM finds LP[1..3] dead, LP[4] live. Walking the dead
prefix from the live end, accumulating the union of later hops (laterattrs):
seed laterattrs from the live remainder LP[4]: {c}.
LP[3] {b}: {b} not-subset {c} -> still has a live fresh entry (21)->LP[3]; keep as
stub forwarding ->4. laterattrs |= {b} => {b,c}.
LP[2] {a}: {a} not-subset {b,c} -> keep as stub forwarding ->3. laterattrs => {a,b,c}.
LP[1] root -> LP_REDIRECT ->2 (first survivor).
Result:
LP[1] redirect ->2
LP[2] stub{a} forward ->3
LP[3] stub{b} forward ->4
LP[4] live v4
Scan a=11 via t_a (11)->LP[2]:
arrive AT LP[2] stub (own segment {a} not counted); forward ->3 stub {b},
->4 {c}; crossed={b,c}; {a}&{b,c}={} => fresh => return v4. OK
Scan a=10 via t_a (10)->LP[1] redirect ->2:
follow redirect to LP[2] (now a crossed segment) {a}, ->3 {b}, ->4 {c};
crossed={a,b,c}; {a}&{a,b,c}={a} => stale => drop. OK
Had a dead member's attributes been fully subsumed by later hops (e.g. a
second a-changing hop after LP[2]), LP[2] would be reclaimed (LP_DEAD) rather
than stubbed: its entries are already superseded, so no live entry references
it, and its {a} is still carried by the later survivor the reader crosses.
Once every entry pointing into the chain is swept by ambulkdelete and the
whole chain is dead, VACUUM reclaims the stubs to LP_UNUSED and re-points the
root redirect straight at the live tuple -- the page is back to classic HOT.
Worked example 4a -- prune and vacuum, step by step
----------------------------------------------------
A fuller trace of the same chain, separating what PRUNE does (the collapse)
from what VACUUM does (the index sweep and final reclaim). Note there is no
"redirect-with-data": the root becomes a plain LP_REDIRECT and the per-hop
bitmaps live on the stubs, which the reader crosses one by one.
Table siu_collapse(id, a, b, c), indexes siu_coll_a(a), siu_coll_b(b),
siu_coll_c(c):
INSERT (1,10,20,30); UPDATE a=11; UPDATE b=21; UPDATE c=31;
(0) Chain after the three HOT-indexed updates, before any prune. Each new
version is a heap-only tuple carrying the bitmap of what changed at its
hop; each changed index got a fresh entry at the new tuple's own TID,
and the pre-update entries remain (now stale).
LP[1] v1(a=10,b=20,c=30) root, HEAP_HOT_UPDATED, ->2 dead
LP[2] v2(a=11,b=20,c=30) heap-only, {a}, ->3 dead
LP[3] v3(a=11,b=21,c=30) heap-only, {b}, ->4 dead
LP[4] v4(a=11,b=21,c=31) heap-only, {c} live
siu_coll_a: (10)->LP[1] stale (11)->LP[2] fresh
siu_coll_b: (20)->LP[1] stale (21)->LP[3] fresh
siu_coll_c: (30)->LP[1] stale (31)->LP[4] fresh
(1) PRUNE (on-access heap_page_prune_opt, or VACUUM's first pass) finds
LP[1..3] dead and LP[4] live, and collapses the dead prefix. Walking
from the live end, accumulating laterattrs (the union of later hops):
seed laterattrs = LP[4] {c}
LP[3] {b}: {b} not subset of {c} -> keep as stub ->4; laterattrs={b,c}
LP[2] {a}: {a} not subset of {b,c} -> keep as stub ->3; laterattrs={a,b,c}
LP[1] root -> LP_REDIRECT ->2 (first survivor)
A dead member is reclaimed outright (LP_DEAD) instead of stubbed only
when its bitmap is a subset of the later hops -- then no live entry
references it and a later survivor still carries its attributes. Here
none qualify, so all three are kept. Result:
LP[1] redirect ->2
LP[2] stub {a} forward ->3 (xid-free: XMIN/XMAX_INVALID, natts==0)
LP[3] stub {b} forward ->4 (xid-free)
LP[4] live v4
The page is kept non-all-visible while a stub remains, so index-only
scans heap-fetch through it. The stale leaves (10/20/30 ->LP[1]) and
the fresh leaves still point where they did; only the heap changed.
(2) Reads against the collapsed page:
Query a=11 via siu_coll_a, fresh entry (11)->LP[2]:
arrive AT LP[2] stub (its own {a} is the entry's own hop, not counted);
cross ->3 {b}, ->4 {c}; crossed={b,c}; siu_coll_a key {a};
{a} & {b,c} = {} => current => return v4. OK
Query b=21 via siu_coll_b, fresh entry (21)->LP[3]:
arrive AT LP[3] stub; cross ->4 {c}; crossed={c}; {b}&{c}={}
=> current => return v4. OK
Query a=10 via siu_coll_a, STALE entry (10)->LP[1]:
LP[1] is a plain redirect -> follow to LP[2]; now crossing the
collapsed segment: LP[2] {a}, ->3 {b}, ->4 {c}; crossed={a,b,c};
{a} & {a,b,c} = {a} => stale => drop (v4 is supplied once, by the
fresh (11)->LP[2] entry). OK
(3) VACUUM index cleanup (ambulkdelete) removes the now-removable stale
leaves (10/20/30 ->LP[1]); kill_prior_tuple / bottom-up deletion also
remove them opportunistically. VACUUM's heap second pass
(lazy_vacuum_heap_page) does NOT collapse or re-point anything; it only
turns LP_DEAD line pointers into LP_UNUSED.
(4) Final reclaim. Once every entry into the chain has been swept and the
whole chain is dead, a later PRUNE reclaims the stubs to LP_UNUSED and
re-points the root redirect straight at the live tuple:
LP[1] redirect ->4 (or reclaimed if no entry references the root)
LP[2] LP_UNUSED
LP[3] LP_UNUSED
LP[4] live v4
No SIU metadata remains on the page; it is indistinguishable from a
classic-HOT chain that has been pruned.
Worked example 5 -- ADD COLUMN across a bitmap-size boundary
-------------------------------------------------------------
The bitmap is ceil(natts/8) bytes, sized by the tuple's natts AT WRITE TIME.
ADD COLUMN raises the relation's natts but does not rewrite existing tuples,
so a chain can hold hops sized for different natts. The sharp case is
crossing an 8-attribute boundary, where ceil(natts/8) grows by a byte; a
reader that sized the bitmap from the relation's *current* natts would read
the wrong trailing bytes. Every consumer instead uses the hop's own
write-time natts (HotIndexedTupleBitmapNatts: HeapTupleHeaderGetNatts for a
live tuple, the stub's stashed natts otherwise).
t(c1 PK, c2, ..., c7, payload), exactly 8 attrs; indexes t_c2(c2), t_c7(c7).
INSERT (...,c7=70,...); UPDATE c7=71; UPDATE c7=72.
LP[1] v1(c7=70) root ->2 dead
LP[2] v2(c7=71) {c7} ->3 dead bitmap 1 byte (natts=8)
LP[3] v3(c7=72) {c7} live bitmap 1 byte (natts=8)
Now ALTER TABLE t ADD COLUMN c9 int; -- relation natts 8 -> 9; ceil 1 -> 2
A subsequent UPDATE c7=73 appends a hop sized for natts=9 (2 bytes):
LP[1] v1(c7=70) root ->2 dead (1-byte bitmap)
LP[2] v2(c7=71) {c7} ->3 dead (1-byte bitmap)
LP[3] v3(c7=72) {c7} ->4 dead (1-byte bitmap)
LP[4] v4(c7=73) {c7} live (2-byte bitmap)
Scan c2= via t_c2 -> LP[1] (stale):
cross ->2 {c7}, ->3 {c7}, ->4 {c7}; each located by its own write-time
natts (1 byte for LP[2,3], 2 bytes for LP[4]) and OR-ed into the
relnatts-sized accumulator. crossed={c7}; {c2} & {c7} = {} => the c2
entry is current => return v4. OK
(Sizing the LP[2,3] bitmaps with the relation's current natts=9 would read
one byte of attribute data as bitmap and could spuriously set a bit,
wrongly dropping the current c2 entry -- which the per-hop sizing avoids.)
Scan c7=72 via t_c7 -> LP[3] (now stale): cross ->4 {c7}; {c7}&{c7}={c7}
=> drop. c7=73 via the fresh (73)->LP[4] entry => return v4. OK
Collapse preserves this: a stub records its write-time natts in the unused
block half of t_ctid (the offset half is the forward link), so a stubbed
1-byte hop and a live 2-byte hop coexist in one collapsed chain and each is
read at its own size. DROP COLUMN keeps the attnum slot (no renumber), so
bit positions and natts are unchanged and existing bitmaps stay aligned.
Open questions for the list
===========================
(a) Is the crossed-attribute-bitmap staleness model acceptable in principle?
It adds a per-hop on-disk bitmap and a chain-walk union to the read path,
and weakens the "an index entry accurately reflects the indexed value"
contract.
(b) Is the on-disk format (Section 5) acceptable?
Fin
===
I hope (some of) you made it this far. :)
I'd appreciate feedback or review of the code and/or approach. I'm sure (I hope!) there will be debate and constructive feedback. This patch start with the ideas from another thread [1] and may eventually end up addressing that thread's specific goal (expanding HOT for expression indexes), but does not do that yet. For those inclined, there's also a wiki page [2] where I hope to fully capture this idea for posterity.
best.
-greg
[1] https://commitfest.postgresql.org/patch/5556/
[2] https://wiki.postgresql.org/wiki/Heap_HOT_Selective_Index_UpdatesRe: Tepid: selective index updates for heap relations
От:
"Greg Burd" <greg@burd.me>
Дата:
Hello.
TL;DR, Patch 5 is new, it works around the bitmap scan issues by encoding
a flag into the TID using the unused bit 14 to signal "may be stale,
recheck on bitmap scan". Wiki page updated with more information on the fix.
Another long one, apologies... but worth the time! ;-)
Alexander found a real correctness bug (thanks!); chasing it took me through
a systemic issue in how indexes address heap rows that is bigger than this
patch, older than this patch, and shared with other projects (OrioleDB in
particular). I want to lay out the whole path -- the bug, the abstraction
tension, why the clean fix is out of scope, and the narrower fix I actually
shipped -- because the reasoning matters more than the diff, and because the
path there ran through a design goal I thought I'd have to give up and then,
thanks to some digging, got back.
== The bug ==
A HOT-indexed (SIU) update's fresh entry in a *changed* index points at the
new heap-only tuple, not at the chain root the way every other index entry
for that row does. That positional distinction is deliberate: it is what
lets the read side decide staleness from the crossed-attribute bitmap
without a value recheck (and thus survive the ABA case that a value recheck
fails).
BitmapAnd/BitmapOr combine two indexes' TID sets in tidbitmap.c at raw
block+offset granularity, *before* either side touches the heap. So for a
row matched by one predicate on an unchanged index (entry -> root) and
another on a changed index (fresh entry -> new tuple), the two sides feed
different TIDs for the same logical row, the exact-mode intersection finds
nothing in common, and the row is dropped. A false negative. Bitmap scans
tolerate false positives but not false negatives, so this is a correctness
bug, not a performance wart. Reproduced, confirmed, and it is exactly the
class of weakness that sank WARM.
== The tension: TID is a leaky abstraction, and not just for us ==
Digging into why the obvious fixes don't work, I kept hitting the same wall,
and it is worth naming because it is not really about this patch.
An index has exactly one channel to say "which row this points to": a 6-byte
block+offset ItemPointer. That is not an interface abstraction that happens
to be implemented with TIDs -- it is the physical shape of an index tuple's
header, inherited from before pluggable table AMs existed, and tidbitmap.c's
whole fast path is literally dimensioned by it (TBM_MAX_TUPLES_PER_PAGE is
#defined to MaxHeapTuplesPerPage). When pluggable table AMs landed, the
index side of that contract was not actually made table-AM-agnostic; it was
left exactly as heap needs it, and every non-heap table AM has to be
block+offset- addressable or fake it.
Let me stress this point again, what indexes store (see: tidbitmap.c) and
what the executor sometimes assumes and uses (see: BitmapAnd/Or) and
optimizes for is not table-AM-agnostic, it is HEAP-shaped. IMO, this is a
leaky abstraction and should someday be corrected without losing the
performance gains associated with it, but that's a different ocean to boil
for a different day. This has bitten Zedstore, OrioleDB, and Tepid (and
likely more I don't even know about).
HOT sidesteps this by enforcing a stronger invariant instead -- only the
chain root is ever indexed -- which costs nothing until you want to skip
maintaining some indexes on an update, which is precisely when it starts
costing. WARM tried to maintain this invariant, and ran afoul of the ABA
and other issues.
This is not a new observation. Robert Haas's 2016 "UNDO and in-place
update" thread [1] is the clearest prior discussion. Alexander proposed,
nine years ago, the clean fix:
"Imagine that heap is TID => tuple map and index is index_key => tuple
map... Imagine you can select between heap-organized table and
index-organized table (IoT) just by choosing its primary access method.
If you select heap for primary access method, indexes would refer TID. If
you select [OrioleDB/btree] on could_id as primary access method, indexes
would refer id_could." [2]
That is the real solution: let the table AM define what an index stores to
identify a row, instead of hardcoding block+offset. It has never been built
in core. OrioleDB works around the same gap today with "bridged indexes" --
a tid => pkey bridge that translates a synthetic TID to its real (index-
organized) row identity before the bitmap combine, using its own custom-scan
node and its own PK-keyed bitmap (o_keybitmap, an rbtree) rather than
tidbitmap.c -- because rather than wait for the core contract to change,
they kept TID as the wire format and inserted a translation shim scoped
entirely inside their own AM.
So: this is systemic, it predates Tepid, and it has actively shaped how more
than one serious out-of-core table AM has been built. I think it deserves
its own thread someday, not today, but someday.
But redefining the index-to-row contract touches the heap tuple header, the
table-AM and index-AM interfaces, tidbitmap.c's core data structure,
WAL/redo, and SQL-visible ctid semantics, and it must migrate every existing
AM including heap. It is emphatically not something to smuggle into a
HOT/SIU project, and I am not going to try.
So I have no choice but to find another way or abandon this effort... and
I'm not giving up yet.
== What I developed for v59 ==
I have a few important design goals, one of them being: no changes to index
AMs. WARM needed per-AM recheck logic, and I considered that one of the
things that made it unpalatable. My first cut of this fix did miss it -- I
put the check in each amgetbitmap -- but after further review I found a way
to around this too, and I can keep Tepid functional with zero index-AM
changes required.
The fix reserves one otherwise-unused bit (bit 14) in a stored TID's offset
field, ItemPointerSIUMaybeStaleFlag. MaxOffsetNumber never needs more than
14 bits even at the largest configurable BLCKSZ, so the bit is free for any
real offset (feel free to disagree on this point). It is set only on the
local TID copy handed to a HOT-indexed fresh entry's index_insert() (never
on the tuple's own tts_tid, never on a classic-HOT or plain entry).
ItemPointerGetOffsetNumber and ItemPointerCompare strip it by default via a
sentinel-safe helper -- so every ordinary consumer keeps seeing the real
offset -- while ItemPointerGetOffsetNumberNoCheck still exposes the raw
value for the handful of sites that need it.
(A note on the sentinels, because it bit me: the two reserved offset values
SpecTokenOffsetNumber (0xfffe) and MovedPartitionsOffsetNumber (0xfffd) sit
at the very top of the offset range, far above any real offset -- a flagged
offset maxes out at 0x6000 even at 32KB BLCKSZ, so it can never collide with
a sentinel, and the three interpretations (real offset, flagged real offset,
sentinel) partition the value space cleanly. The catch is only in the
stripping direction: 0xfffd/0xfffe happen to have bit 14 set within their
all-high-bits encoding, so unconditionally clearing it corrupts them (0xfffd
-> 0xbffd) and breaks their recognition. My first cut masked
unconditionally and silently broke cross-partition-UPDATE conflict
detection; the isolation suite caught it immediately. The strip is now
range-gated to leave anything at or above the sentinel range untouched.)
Detection lives at one choke point: tbm_add_tuples(), which every
amgetbitmap funnels exact heap TIDs through. It tests the raw flag (before
the offset is stripped) and, when set, adds the whole page as lossy
(tbm_add_page) instead of the single exact offset. Per tbm_intersect_page's
own case analysis a lossy page survives any AND/OR against an exact-mode
page and forces a recheck, so BitmapHeapScan resolves the chain and the
existing heap-side crossed-attribute test makes the final, correct call.
Because this lives in tbm_add_tuples and not in each access method, NO index
AM needs to know about HOT-indexed chains. There is no per-AM code at all:
btree, hash, GIN, GiST, SP-GiST are untouched, contrib/bloom is correct with
no bloom-specific code, and any out-of-tree AM that feeds a TIDBitmap is
correct automatically. A TID that never carries the flag takes the
identical path it always did. GIN's own unrelated page-level lossy sentinel
is untouched.
The only cross-cutting surface that remains is the one design choice I do
want to flag for debate (see the ask): the marker lives in the generic
ItemPointer offset and the universal
ItemPointerGetOffsetNumber/ItemPointerCompare strip it. That strip is
required regardless of the bitmap fix -- a plain index scan resolves a fresh
entry's TID to a live line pointer, and the unique check compares TIDs -- so
it is not something the tbm_add_tuples placement lets me avoid. It is a
tiny, branch-predictable mask on a hot path; I'll bring a microbenchmark.
Tooling: amcheck's heapallindexed fingerprints leaf TIDs and compares them
to the plain heap TIDs it re-derives, so verify_nbtree strips the marker
while fingerprinting or a fresh entry raises a spurious "lacks matching
index tuple". pageinspect 1.14's bt_page_items reports the real offset in
ctid/htid (earlier versions showed the marker as an inflated offset) and
adds a hot_indexed column exposing the marker.
Correctness: a regression test (hot_indexed_updates.sql section 32) now
covers BitmapAnd across a changed+unchanged index for every access method
SIU exercises -- btree+btree, hash+btree, GIN+btree, GiST+btree,
SP-GiST+btree -- plus a BitmapOr case, each verifying the previously-dropped
row is returned and an unrelated row is unaffected.
== Performance ==
The one real cost is that when a page carrying an SIU fresh entry is added
lossy, that page's *other*, unrelated tuples also lose exact-mode precision
on that bitmap contribution (extra heap recheck) until the SIU chain
collapses. So I measured the workload most likely to expose it: a mixed 80%
BitmapAnd reads across two unchanged indexes / 20% HOT-indexed updates on a
third index of the same table, A/B alternating the tree with the fix against
the identical tree with only that one commit reverted, 5 iterations each.
bit14 off (unfixed): 30650.6 TPS median
bit14 on (fixed): 30552.1 TPS median
delta: -0.32%, inside the ~0.2% run-to-run noise band
No measurable overhead, in the shape built to provoke it. (EC2 c7i.4xlarge,
scale 10, 16 clients, 60s cells). The general SIU A/B is unchanged by this
fix, as expected -- it only touches the bitmap read path.
== The ask ==
Two separate things, and I'd like them kept separate:
1. For this patch set:
Is bit14 an acceptable fix? It spends one free bit in a very
load-bearing struct (the last spare offset bit; bit 15 is held by the
SpecToken/MovedPartitions sentinels), which I do not do lightly, but it
needs zero index-AM code, benchmarks at no measurable cost, and closes
a real correctness hole. The one cross-cutting surface is that the
universal ItemPointerGetOffsetNumber/ItemPointerCompare strip the bit
(required for plain scans and TID comparison regardless of the bitmap
path) and the marker is persisted on-disk in index tuples (now shown
transparently by pageinspect 1.14). If the objection is "not that
bit," "not a TID bit at all," or "not in the universal accessors," I
need to hear it -- the whole encoding hangs off that choice.
2. Independently: the leaky TID-as-row-identity contract is real and worth
a thread of its own, but it is out of scope here and I am not proposing
to solve it in this series. I raise it only so the narrow fix is
understood as a deliberate accommodation of that leak, not a claim to
have addressed it.
v59 attached with this fix as patch 5, best.
-greg
[1] https://www.postgresql.org/message-id/flat/CA%2BTgmoZS4_CvkaseW8dUcXwJuZmPhdcGBoE_GNZXWWn6xgKh9A%40mail.gmail.com
[2] https://www.postgresql.org/message-id/CAPpHfdtiLK55eT9uJu6U%3Dg12q%2BmNMkegvtGhz0Qdic5H%2BkuSzA%40mail.gmail.com
Re: Tepid: selective index updates for heap relations
От:
Bharath Rupireddy <bharath.rupireddyforpostgres@gmail.com>
Дата:
Hi,
On Thu, Jul 16, 2026 at 3:05 AM Greg Burd wrote:
>
> Rebased onto 3cf5264557b to address conflicts, no other changes.
Thanks for working on this. I previously played around with PHOT and
WARM a bit and built some context, but I need to refresh my memory and
give things a re-read.
The patches cover a lot. Reducing the diff to the core and posting the
stats, amcheck, and logical replication patches later would make
review easier. I managed to get through 0001 and 0002 so far.
I would be more interested in focusing the initial discussion on the
key design decisions. Where to store the modified index bitmap (it is
per-row version). How we get vacuuming right. How bitmap scans and
index scans produce correct results. How on-disk row format changes
are acceptable. How upgrades work for migrating existing databases.
How replication (logical and streaming) works and any impact on
downstream systems (replicas, subscribers, etc.). How it impacts
tooling (in-core like amcheck, pg_upgrade, pageinspect, and external
ones).
Most importantly, the trade-offs. We are going to have more heap bloat
at the cost of less index bloat, which is fine since most OLTP
workloads go via indexes, but does it impact analytical workloads that
scan the heap? How does it impact vacuum performance? Do we know how
many customers in practice modify indexed columns (not exact numbers,
but some data points to keep the motivation up for this feature)? The
fact that the modified index column bitmap is now stored per tuple
version means fewer rows fit per page, which means more pages per
relation, and does it also mean fewer HOT updates because updated rows
cannot fit in the same page since some space is used for storing the
bitmap, causing more index maintenance in turn?
Also, the naming (SIU, Tepid, HOT-INDEXED, HEAP_INDEXED_UPDATED, and
previously PHOT, WARM) is a bit confusing to me. Could we simplify the
names and use them consistently?
Some quick comments on the patches.
0001:
1/ Can 0001 be discussed in a separate thread? It seems to provide
good coverage for HOT updates on its own and is worth discussing and
perhaps getting committed separately.
2/
+SELECT id FROM hot_xml_test WHERE xpath('/person/name/text()', doc) =
ARRAY['Alice2'::text];
+ERROR: operator does not exist: xml[] = text[]
+LINE 1: ..._xml_test WHERE xpath('/person/name/text()', doc) = ARRAY['A...
+ ^
+DETAIL: No operator of that name accepts the given argument types.
+HINT: You might need to add explicit type casts.
+INSERT INTO hot_xml_test VALUES
+ (1, 'Alice30'),
+ (2, 'Bob25');
+ERROR: could not identify a comparison function for type xml
+SELECT * FROM get_hot_count('hot_xml_test');
Are these expected?
0002:
1/
-SELECT * FROM base_tbl;
+SELECT * FROM base_tbl ORDER BY a;
ERROR: cannot insert a non-DEFAULT value into column "b"
DETAIL: Column "b" is a generated column.
-SELECT * FROM gtest1v;
+SELECT * FROM gtest1v ORDER BY a;
-DELETE FROM main_view WHERE a IN (20,21);
+DELETE FROM main_view WHERE a = 20 AND b = 31;
NOTICE: main_view BEFORE DELETE STATEMENT (before_view_del_stmt)
NOTICE: main_view INSTEAD OF DELETE ROW (instead_of_del)
-NOTICE: OLD: (21,10)
-NOTICE: main_view INSTEAD OF DELETE ROW (instead_of_del)
NOTICE: OLD: (20,31)
+NOTICE: main_view AFTER DELETE STATEMENT (after_view_del_stmt)
+DELETE 1
The commit message says this fixes nondeterministic behavior in
existing tests due to row ordering. I think these are unrelated to
this work and could be discussed and committed separately.
2/ ExecUpdateModifiedIdxAttrs() replaces HeapDetermineColumnsInfo().
Why do we need to move modified index attribute computation to the
executor and make every TTS and table AM pay that cost? HOT and
modified index attributes are purely heap AM specific. If the executor
ever needs the list of modified index attributes, why not let the AMs
provide it as an out parameter (similar to how we pass the HOT hint in
TU_UpdateIndexes format)?
I read the commit message saying that finding this set of attributes
is not heap-specific but more general to all table AMs and could
inform other decisions about when index inserts are required. But is
it needed for this feature? If not, I think it can be discussed
separately.
3/
- SELECT FROM injection_points_detach('heap_update-before-pin');
- SELECT FROM injection_points_wakeup('heap_update-before-pin');
+ SELECT FROM injection_points_detach('simple_heap_update-before-pin');
+ SELECT FROM injection_points_wakeup('simple_heap_update-before-pin');
Once we find the need for 0002, can we just leave the injection point
name as-is to reduce the mechanical diff?
4/ Nits.
Typos.
+ * are in the UPDATE statment and are known to be referenced by at least one
+ * ExecGetAllUpdatedCols(). Desipte the name it provides the set of
No need to specify test names in the comments, because they can change anytime.
* heap_modifiy_tuple(). There is one test in tsearch.sql that does just
+ * that, modifies an indexed attribute that isn't specified in the SQL and
5/
+ /* attidx is zero-based, attrnum is the normal attribute number */
+ AttrNumber attrnum = attidx + FirstLowInvalidHeapAttributeNumber;
Is every TTS implementer expected to support all system columns that
FirstLowInvalidHeapAttributeNumber implies? Asking because 0002 moved
this code to the executor in ExecCompareSlotAttrs.
6/ The commit message says that having ExecUpdateModifiedIdxAttrs() in
the executor reduces the time the buffer lock is held by computing
modified index columns before table_tuple_update(). How is this
correct from a concurrency perspective? If another transaction
modifies the same tuple between when the executor compares columns and
when heap_update acquires the buffer lock, what happens? The executor
locks the old tuple explicitly only when it detects concurrent updates
or deletes to the same tuple, but does not hold the tuple lock the
first time.
I will continue reading the other patches in the coming weeks.
--
Bharath Rupireddy
Amazon Web Services: https://aws.amazon.com
Re: Tepid: selective index updates for heap relations
От:
"Greg Burd" <greg@burd.me>
Дата:
Hello, Attached is v63 which has a few fixes and is rebased (0b3e646fd7f) as well. What changed vs v60? Eight of the ten patches changed in content since v60; only 0001 (heap HOT-update tests) and 0007 (amcheck) are unchanged apart from rebase-induced hunk offsets. The headline is the CLUSTER data-loss fix (0004, with its regression test in 0008); the rest are correctness, robustness, and consistency fixes found in review, plus a test relocation. The headline: CLUSTER data loss on HOT-indexed (SIU) tables CLUSTER ... USING silently dropped live rows. On a table with an SIU chain where the clustering column changed (or ABA-cycled) in an earlier hop and a different indexed column changed in the last hop, with the chain left uncollapsed (no VACUUM), CLUSTER returned 14 of 20 rows; six live rows gone from the heap (seqscan-verified). Row count depending on which index you cluster by is an unambiguous correctness bug. Root cause: CLUSTER-by-index copies the heap via an index scan under SnapshotAny, trusting the clustering index to reach every live tuple directly. On an uncollapsed SIU chain, a live tuple whose last hop changed a different column has no clustering-index entry pointing at it, so it's unreachable through that index -> never copied -> lost. This affects any clusterable index AM, not just btree. Both btree and GiST (the only two amclusterable core AMs) lose the same rows, and a btree-only fix would have left GiST (and any out-of-tree clusterable AM) exposed. The fix (patch 0004): In the heap AM (heapam_relation_copy_for_cluster, heapam_handler.c). The copy routes through the relation_copy_for_cluster tableam callback, so the heap AM -- the layer that actually creates index-unreachable live tuples -- refuses the lossy index-scan copy path itself when it holds SIU chains (heap has >1 index): - btree clustering index -> switch to seqscan+sort (cluster order preserved); - any other clusterable AM (GiST, or out-of-tree) -> plain seqscan copy (order dropped, no row lost). Both direct-scan paths visit every heap tuple, the same way VACUUM FULL already does. No index AM (core or out-of-tree) needs any change; the heap guarantees its own invariant regardless of which index drove the CLUSTER. (An earlier iteration carried a btree-only guard in repack.c; that is reverted to pristine and the guard now lives in the heap AM.) The regression test (patch 0008, hot_indexed_updates.sql): reproduces the actual losing shape (a-ABA early, b in the last hop, fillfactor=40, autovacuum_enabled=false, no VACUUM before CLUSTER), asserting all 20 rows survive and remain findable, plus bt_index_check(heapallindexed => true). A GiST case (CLUSTER ... USING ) proves the fix is AM-agnostic -- a guard a btree-only fix would miss. Both cases lose 6 rows without the fix and pass with it. Changes since v60 0002: identify modified indexed attributes in the executor - Comment-only; the code is unchanged from v60. Documents why ExecCompareSlotAttrs (used by ExecUpdateModifiedIdxAttrs on the executor path) compares slots with datum_image_eq while the non-executor path (simple_heap_update -> HeapUpdateModifiedIdxAttrs -> heap_attr_equals) uses datumIsEqual. The difference is intentional: at the executor stage the slot values are logical and cannot be TOASTed (TOAST is a heapam storage detail applied later), the executor must stay agnostic of how a table AM stores variable-length data, and datumIsEqual would force a needless slot->Datum transform on a hot path. - Also notes on heap_attr_equals and HeapUpdateModifiedIdxAttrs that they are not public API -- their only consumer is simple_heap_update(), and they are targeted for eventual removal once catalog-tuple updates track their own changed columns. 0003: on-disk format - Comment corrections only. (1) The inline attribute bitmap is located using the tuple's own write-time attribute count, not the relation's current natts -- after ADD COLUMN a chain can hold tuples whose bitmaps were sized for a smaller natts, and sizing from the relation's current natts would read past the tuple's data. (2) A new README.HOT-INDEXED section spells out the datum_image_eq-vs-datumIsEqual rationale described under 0002. 0004: selective index maintenance and reads, beyond the CLUSTER fix above - Ordered/distance index scans (GiST/SP-GiST, ORDER BY <->) now drop stale HOT-indexed entries, which the non-ordered scan path already did; the ordered path (IndexNextWithReorder) was the one remaining gap. - The HOT/SIU chain walk in heap_hot_search_buffer is bounded by a per-page hop guard and now calls CHECK_FOR_INTERRUPTS. A corrupt page whose forward links form a cycle among valid in-range offsets would otherwise spin forever under a buffer share-lock. - The unique-insert self-check tolerates the legitimate repeat self-arrival (the canonical direct entry plus stale chain-walk entries resolving to the same TID, in either arrival order) while still raising on a genuine duplicate TID. - In _bt_check_unique, the right-sibling buffer is kept pinned while scanning equal tuples on the HOT-indexed skip paths: page, opaque, and curitup may point into it, so releasing it early would dereference a freed buffer. - The palloc'd per-row modified-attrs bitmap is freed after the index inserts consume it (a bulk UPDATE previously accumulated one Bitmapset per updated row for the statement's lifetime), and the "update all indexes" sentinel is accepted on input for an index whose expression references a whole-row Var. 0005: BitmapAnd/BitmapOr false negative - Assert that the stale marker (ItemPointerSetSIUMaybeStale) is only ever set on a genuine in-range offset, not a sentinel offset. 0006: collapse dead chains to xid-free stubs - Bound the stub-forward walk in heap_prune_chain with a per-page hop guard, so a corrupt stub->stub cycle cannot spin forever (mirroring the guard heap_prune_chain_find_live already has). - Drop the got_cleanup_lock plumbing through lazy_vacuum_heap_page; rely on heap_page_would_be_all_visible()'s own SIU-redirect and stub guards to refuse marking a page all-visible while an unreclaimed HOT-indexed member is still present. 0008: statistics + comprehensive test suite - The SIU regression tests that depend on pageinspect/amcheck/btree_gist moved from src/test/regress into contrib/pageinspect (core "make check" does not install contrib, so those CREATE EXTENSION calls would fail under a standard build; contrib/pageinspect is the idiomatic home and pulls the other two in via EXTRA_INSTALL). The suite gained the CLUSTER and GiST-CLUSTER cases described above, plus a KNN case for the ordered-scan fix in 0004. 0009: gate HOT-indexed updates on the logical-replication apply path - Derive the apply mode directly from MySubscription instead of caching it in a worker.c static, removing a second copy that had to be kept in sync across subscription reloads. 0010: benchmark harness - DO NOT MERGE. Script-only robustness/comment fixes (results-dir creation, early validation of the resolved base revision, skipping failed pgbench iterations rather than recording NA rows, and a workload that actually changes the indexed value); no change to what it benchmarks. best. -greg
