Re: Tepid: selective index updates for heap relations

Hello,

I've tried to call out below all the issues that I think will need
discussion rather than ask you to identify them so as to make better
use of everyone's precious time. Thanks in advance.

Attached is a rebased patch set (v57, on 16a4b3ef8ee) for HOT-indexed
updates -- extending the HOT optimization so that an UPDATE which
changes an indexed column only maintains the indexes whose attributes
actually changed, rather than falling back to a full non-HOT update.
This is the mechanism the "HOT expression updates" thread and, before
it, WARM and PHOT were all circling.

Rather than lead with benchmarks, I want to put the contentious design
decisions on the table first, because if the core model is a non-starter
on principle I would much rather hear that now than after another round
of implementation.

I have tried to write this the way I would want to review it: every open
question stated as a question, with the options I considered and why the
patch currently chooses what it does, so the debate can be about the
choice and not about excavating what the choice even was.

I owe an obvious debt to Pavan Deolasee (HOT, WARM), to Nathan Bossart's
partial-HOT sketch, and to everyone who pushed back on those threads --
much of what follows is an attempt to answer objections that were raised
years ago and never adequately resolved.

== The one question that gates everything else ==

Q0. Is attribute-bitmap staleness -- as opposed to a value recheck -- an
acceptable foundation at all?

A HOT-indexed update writes the new version as a heap-only tuple and
appends, inline in the line-pointer item past the tuple's natts, a
fixed-size bitmap of which indexed attributes changed at that hop. A
reader arriving through a possibly-stale index entry walks the chain
and unions the bitmaps it crosses; if the union overlaps the scanned
index's attributes, the entry is stale and skipped. There is no
comparison of the leaf's stored key against the live tuple.

This is the decision that plagued WARM, so I want to be explicit about
why the patch does NOT recheck values:

- A value recheck is provably wrong under an ABA cycle. If an
indexed value goes X -> Y -> X, the live tuple's key equals BOTH
the old and the new leaf, so both pass a value recheck and the row
is returned twice. We hit exactly this. The crossed-attribute
bitmap gets it right because it is positional: the fresh entry
points at the version whose key it matched and crosses no later
key-changing hop, while the stale entry's walk does cross one --
even when the values coincide.

- Because the read side never reconstructs or compares a key, it is
access-method agnostic. btree, hash, GIN, GiST and SP-GiST all
work with no per-AM recheck logic (all exercised in the suite,
including the hash ABA case).

The cost of this choice, stated plainly: it adds a per-hop on-disk
bitmap and a chain-walk bitmap-union to the read path, and it weakens
the informal contract that "an index entry accurately reflects the
current indexed value." That contract-weakening is the real thing to
debate. My claim is that the contract is already softer than it looks
(kill_prior_tuple, bottom-up deletion and bitmap scans all tolerate
entries that no longer match), but I would like that challenged
directly.

Options if the list rejects bitmap-staleness:
(a) Value recheck instead -- rejected above (ABA), and it
reintroduces a per-scan leaf-materialize cost this design does
not have.
(b) Do nothing / keep HOT as-is -- the status quo; the
WARM/PHOT/expression threads exist because the write
amplification is real.
(c) A different staleness authority I haven't thought of, and I am
genuinely open to this.

== Is this WARM again? ==

Let's review the four objections that stalled it. If the answer to Q0
is "maybe," these are the specific WARM objections and how the patch
answers them. I would like to know whether each answer actually lands
or whether I am repeating history.

W1 -- Duplicate results from index scans. Answered by Q0: exactly one
entry per index survives the bitmap test; no duplicates, no lost
rows.

W2 -- Only one WARM update per chain (which crippled the benefit).
There is no chain-length cap here. A chain takes as many
HOT-indexed hops as fit on the page; growth is bounded by the
page (an update that no longer fits falls back to non-HOT) and
by prune/collapse reclaiming superseded members. (An early
draft had a fillfactor-derived cap; it measured from the wrong
end of the chain and bounded nothing, so it was removed. If the
list wants an explicit cap for predictability rather than
correctness, that is a knob we could add -- see Q3.)

W3 -- "Converting chains back" and its interaction with VACUUM was the
major sticking point. There is no convert-back step. Staleness
is decided at read time; prune collapses a dead chain prefix
into xid-free forwarding stubs that preserve each surviving
hop's bitmap, and VACUUM reclaims the stubs and re-points the
root redirect once the stale leaves are swept -- collapsing
naturally back to classic HOT. No alternating state machine, no
per-tuple flag to clear. Whether this collapse machinery is
actually simpler than WARM's, or just relocates the complexity,
is a fair question for reviewers of pruneheap.c / vacuumlazy.c.

W4 -- Recheck correctness across all index/scan kinds and opclasses.
Subsumed by the AM-agnostic read path in Q0.

== The on-disk format ==

Q1. Is the on-disk format acceptable to freeze?

Two new LP_NORMAL shapes carry one infomask2 bit
(HEAP_INDEXED_UPDATED, 0x0800, previously free):

- a data-bearing HOT-indexed tuple (natts >= 1) with a trailing
bitmap sized by the tuple's own write-time natts; and

- an xid-free collapse-survivor stub (natts == 0, a signature no
real tuple can produce) that stashes its write-time natts in the
block half of t_ctid and its forward link in the offset half.

Every consumer of LP_NORMAL items must tolerate both. I have audited
the in-tree consumers: visibility-gated paths (seqscan, bitmap,
ANALYZE, index build) are safe because stubs are XMIN_INVALID and the
bitmap is past natts; amcheck and prune/VACUUM are stub-aware;
pg_surgery skips stubs; pageinspect and pgstattuple are read-only and
merely imprecise.

Alternatives considered and rejected, with reasons, so the format
debate is concrete:

- separate relation fork: heavy, and the marker must be co-located
with the tuple for the chain walk;

- a separate adjacent "tombstone" line pointer per hop: doubles
line-pointer pressure; the inline 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 + one infomask2 bit.

The known-unknown I most want eyes on: is stealing an infomask2 bit
and overloading natts==0 as a stub sentinel acceptable, or does the
project want a cleaner (costlier) representation before this is worth
committing?

Q1a. The bit budget.

This is worth stating on its own because it is irreversible.
t_infomask2 has exactly two spare bits above the 11-bit natts mask:
0x0800 and 0x1000. This patch consumes 0x0800
(HEAP_INDEXED_UPDATED), leaving 0x1000 as the last free t_infomask2
bit in the heap format. I do not take that lightly.

The argument for spending one now: the feature is unimplementable
without a persistent per-tuple signal, and every alternative to a
bit (Q1's rejected list) costs more -- an lp_flags value, a fork,
or a second line pointer. The argument against: a bit is a scarce,
permanent resource and the list may want it reserved for something
the project already knows it wants. If the answer is "not this
bit," I need to hear it before the format freezes, because the
whole on-disk encoding hangs off it.

Q1b. Longer chains.

A chain here can be arbitrarily long within a page (Q3), which is a
real change from classic HOT's practical behavior and from WARM's
hard one-update cap (W2). The read cost is not free: a scan that
arrives through a stale-ish leaf walks the chain accumulating a
bitmap-union until it reaches the live tuple, so worst-case read
work is O(chain length) in bitmap-unions, and a page that
accumulates many preserved HOT-indexed members stays denser and
non-all-visible (Q1c) for longer.

My position: this is bounded in practice -- an update that no
longer fits the page falls back to non-HOT, and prune/collapse
reclaims superseded members and re-points the root redirect, so a
chain does not grow without bound and a hot row's chain is
continually shortened by the same VACUUM that would clean any other
bloat.

But "bounded in practice" is exactly the kind of claim WARM made,
so I want it challenged: is an uncapped chain length acceptable
given the O(length) read walk, or does predictability argue for the
cap discussed in Q3? The read_indexscan benchmark cell exists to
measure the walk cost on a stub-free table; I expect parity there
but will prove it on real hardware.

Q1c. The all-visible / index-only-scan interaction.

This one deserves an explicit debate because it is a visible
operational cost, not just an internal detail. A stale leaf can
resolve, through the chain, to a live tuple whose current key
differs from the leaf's stored key. If the page holding that chain
were marked all-visible, an index-only scan would take the
visibility-map fast path, skip the heap fetch, and return the
leaf's STALE key -- wrong results with no chance to detect it. The
patch closes that from the prune side: any page still carrying
something a stale leaf can resolve through -- a preserved live
HEAP_INDEXED_UPDATED member, an LP_REDIRECT forwarding into one, or
a collapse-survivor stub -- is deliberately kept OUT of the
visibility map (prune forces set_all_visible=false, re-applied in
heap_page_would_be_all_visible), and once forced to the heap the
IOS re-checks the arriving entry with the same bitmap test before
trusting xs_itup.

The consequence to debate: such a page is not all-visible until its
chains fully collapse, so index-only scans over hot,
recently-SIU-updated rows lose the VM fast path and pay a heap
fetch until VACUUM collapses the chains.

A conventionally-updated page reaches all-visible after one VACUUM;
an SIU page with a surviving stub needs the later VACUUM that
reclaims the stub and re-points the redirect.

I argue this is the correct conservative default (correctness over
an IOS micro-optimization on exactly the rows that are being
churned, and it self-heals as the chain collapses), and that IOS on
genuinely-stable all-visible pages is unaffected because such a
page cannot hold a live SIU chain. But it is a real regression for
an IOS-heavy workload on churned rows, and if the list considers
that unacceptable the alternative is a per-entry mechanism that
lets a page go all-visible while still forcing a fetch only for
stale leaves -- more complex, and I did not want to build it before
the model is accepted.

== Eligibility carve-outs: which are permanent vs provisional? ==

Q2. The patch is deliberately conservative about what takes the
HOT-indexed path. Some carve-outs are fundamental; others are "not
proven yet" and may be liftable. I want the list to tell me which
it considers permanent.

- System catalogs (permanent, I think):

Catalogs are reached through access paths -- systable scans,
SnapshotDirty unique checks, seqscans -- I have not proven safe,
so a catalog UPDATE stays classic HOT.

There is a second, mechanical reason this carve-out needs explicit
discussion: catalog tuples are not updated through the executor,
so the modified-indexed-attribute set that the executor computes
for a normal UPDATE (by diffing the old/new TupleTableSlots in
ExecUpdateModifiedIdxAttrs) simply does not exist on the catalog
path.

simple_heap_update -- the entry point CatalogTupleUpdate and
friends use -- therefore has to reconstruct an equivalent bitmap
itself: it fetches the old tuple by TID and diffs it against the
new one to derive modified_idx_attrs, duplicating in heapam.c the
logic the executor already performs. Today that duplicated path
deliberately keeps catalog updates on the classic-HOT track, so
the mirror only has to be correct enough to make the eligibility
decision, not to drive selective maintenance.

The debate: is a second copy of the "which indexed attributes
changed" computation -- one in the executor, one in
simple_heap_update -- acceptable, and is the right long-term
answer to (a) keep them separate and documented as mirrors, (b)
factor the diff into one shared helper both call, or (c) have the
catalog callers pass down the "replaces" array they already have
(most of them do) instead of re-deriving it?

The current code chooses (a) with a comment calling out the
repetition; I lean toward (c) eventually but did not want to churn
every catalog caller before the model is settled.

- Expression indexes (provisional):

The bitmap is attribute-granular and cannot tell whether the
expression's *value* changed, only whether an attribute it
references changed. This is precisely the "HOT expression
updates" thread's problem. I believe it is liftable the same way
the partial-index restriction was (predicate/expression-aware
maintenance), but it is not wired up and not tested, so it is a
carve-out for now.

Is attribute-granular the right initial granularity, or should
expression support be in the first committed version?

- Every indexed attribute changed (permanent, by construction):

Nothing can be skipped, so a plain non-HOT update is cheaper.
"Every" is an exact test -- there is deliberately no percentage
GUC. Q3 asks whether that is the right call (which I feel it is).

- The logical-replication apply path (per-subscription gate,
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
safely does only when the indexed attributes are a subset of the
replica identity.

Is a three-valued per-subscription option the right control
surface, or does replication safety want something
coarser/finer/entirely different?

== Smaller decisions worth a sentence each ==

Q3. No tuning knobs, which is a Good Thing (TM), right?

There is no chain-length cap and no "skip if < N% of indexes change"
GUC. My reasoning is correctness never needs them, and every knob
is a support burden and a planner-surprise. Counter-argument I take
seriously (and which Q1b sharpens): operators may want a
predictability cap even at some efficiency cost, precisely because
the read walk is O(chain length) and the all-visible loss (Q1c)
persists until collapse.

Add a cap, or hold the line and rely on page-fit + prune to bound
it?

Q4. Unique checks.

_bt_check_unique gains a value recheck (opclass comparator) used
ONLY to distinguish a real duplicate from a stale leaf during a
unique insert -- this is the one place a value comparison is
load-bearing, and it routes a genuine hit into the existing xwait
wait-and-recheck.

I believe this is both necessary and sufficient; I would like it
confirmed, since it is the subtlest correctness argument in the set.

Q5. catversion.

The patch adds a pg_subscription column, so it needs a catversion
bump; I have left a placeholder (value matching master, with an XXX
comment) rather than a real bump, so the series does not
rebase-conflict on catversion every time master moves.

== What is deferred, honestly ==

- Expression-index support (Q2). If even the first two commits in
this series land I'll revisit/finish this in the thread about
CF-5556.

- Broader concurrency / crash stress matrices beyond the current
isolation spec + crash-recovery TAP test under
wal_consistency_checking.

- I've done a representative-hardware benchmark sweep using a variety
of instance types in "the cloud" and found performance numers to be
stable and predictable. The A/B numbers show WAL update down ~23%
on a single-indexed-column update and up to ~59% on a wide table
where one of many indexes changes, throughput (TPS) is up ~18-26%,
and others are at parity. The results that matter (WAL and index
bloat on the write workloads; any read-path cost on a tombstone-free
table; net TPS on a mixed workload) are in a commit labled
DO-NOT-MERGE harness in the series so anyone can
reproduce/critique/etc.

== The ask ==

In priority order:

1. Q0 -- is bitmap-staleness acceptable in principle? Everything else
is wasted effort if this is a no.

2. W1-W4 -- do the answers actually address what sank WARM?

3. Q1 / Q1a -- can the on-disk format be frozen, and is spending one
of the two remaining t_infomask2 bits the right call?

4. Q1c -- is losing the index-only-scan all-visible fast path over
not-yet-collapsed chains an acceptable cost, or a blocker?

5. Q1b / Q3 -- is an uncapped, page-bounded chain length acceptable
given the O(length) read walk, or do we want an explicit cap?

6. Q2 -- which carve-outs are permanent; must expression indexes be in
v1; and is the duplicated catalog-path attr-diff the right
structure?

7. Benchmarking, where did I go wrong and/or what else would you like
to see qualified/tested empirically and under what conditions?

Thanks for reading this far, I look forward to constructive debate and
hope the community finds this valuable work.

best.

-greg

PS: Tepid is on the https://github.com/gburd/postgres/tree/tepid branch