Re: Tepid: selective index updates for heap relations

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