Tepid: selective index updates for heap relations

I've create cf-6869 and rebased to fix conflicts due to a single conflict, the usual catversion.h bump.

-greg

Rebased onto 51cd5d6f052.

The only interesting changes were in patch 0008:

- origin/master gained a new feature between v49 and v50 ("Allow logical replication conflicts to be logged to a table"), which touches the exact same subscription-option plumbing ours does. The rebase conflicted in 6 files; I resolved by making both features coexist:

- alter_subscription.sgml / create_subscription.sgml: the "alterable options" doc list now enumerates conflict_log_destination alongside hot_indexed_on_apply instead of standing alone.

- pg_subscription.c: GetSubscription() now also copies subconflictlogrelid (their field) next to our subhotindexedonapply copy — independent lines, both needed.

- system_views.sql: the pg_subscription GRANT SELECT column list now includes their subconflictlogrelid/subconflictlogdest in catalog-struct order alongside our column.

- subscriptioncmds.c — the one genuine bug fix: both features had independently claimed bit 0x00080000 for their SUBOPT_* flag. Real collision. Resolved by moving ours, SUBOPT_HOT_INDEXED_ON_APPLY, to 0x00100000; kept their SUBOPT_CONFLICT_LOG_DEST at 0x00080000. Also merged the else if option-parsing chain, the CREATE/ALTER SUBSCRIPTION supported-opts bitmasks, and the tuple-update logic so both options parse and apply independently (verified live: CREATE SUBSCRIPTION ... WITH (hot_indexed_on_apply='always', conflict_log_destination='table') sets both fields correctly).

- catversion.h: bumped past current master (202607023).

I validated the benchmark claims again, this time in EC2 on larger "metal" instance: m6id.metal - 128 vCPU, 512 GB RAM, 4×1.7 TB local NVMe (RAID0), Amazon Linux 2023. PG 20devel release build (cassert=off).

Result (origin/master vs tepid v50, scale 50, 32c/32t, 120s/cell):

workload TPS master->tepid WAL/update master->tepid
simple_update (control; HOT both) 132.9k -> 131.9k ( -1%) 448 -> 448 B ( +0%)
hot_indexed_update (1 of 4 idx) 172.4k -> 195.0k (+13%) 556 -> 422 B (-24%)
hot_indexed_mixed (80r/20w) 333.4k -> 346.8k ( +4%) 574 -> 438 B (-24%)
read_indexscan (read-only) 812.2k -> 803.5k ( -1%) n/a (read-only)
wide, 0 of 17 (control) 214.2k -> 213.6k ( -0%) 141 -> 143 B ( +1%)
wide, 1 of 17 indexes 93.8k -> 164.6k (+76%) 1649 -> 668 B (-59%)
wide, 4 of 17 indexes 93.7k -> 147.1k (+57%) 1783 -> 978 B (-45%)
wide, 8 of 17 indexes 98.8k -> 132.7k (+34%) 1967 -> 1494 B (-24%)
wide, 16 of 17 indexes 106.3k -> 106.8k ( +0%) 3222 -> 3219 B ( -0%)

best.

-greg

Rebased onto 617c7574055 and removed the changed catversion bump.

-greg

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

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

Hi, Greg!

Thank you for your work. It looks huge.

On Tue, Jun 30, 2026 at 8:21 PM Greg Burd <greg@burd.me> 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.

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.

------
Regards,
Alexander Korotkov
Supabase

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 <greg@burd.me> 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

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]/messages/by-id/CA+TgmoZS4_CvkaseW8dUcXwJuZmPhdcGBoE_GNZXWWn6xgKh9A@mail.gmail.com 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]/messages/by-id/CAPpHfdtiLK55eT9uJu6U=g12q+mNMkegvtGhz0Qdic5H+kuSzA@mail.gmail.com

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]: /messages/by-id/CA+TgmoZS4_CvkaseW8dUcXwJuZmPhdcGBoE_GNZXWWn6xgKh9A@mail.gmail.com
[2]: /messages/by-id/CAPpHfdtiLK55eT9uJu6U=g12q+mNMkegvtGhz0Qdic5H+kuSzA@mail.gmail.com

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

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 <secondary index> 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 <gist index>) 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

Hello,

Attached is v64, rebased onto current master (3ed29c42a40), this time as
a .tar.gz attachment to avoid getting moderated. What changed vs v63
(posted hours ago... apologies for the churn)?

Three patches changed in content; the other seven differ only by rebase-
induced hunk offsets. All three changes address findings from an automated
review of v63, each verified against the code (reproduced before accepting)
rather than taken on faith. Two were real and are fixed; one was declined
with reasoning below.

0005: BitmapAnd/BitmapOr false negative -- amcheck false positive fixed

bt_index_check(..., heapallindexed => true) could raise a spurious "heap
tuple ... lacks matching index tuple" on an index maintained by HOT-indexed
(SIU) updates, when nbtree deduplication had merged the fresh entries into a
posting list.

A HOT-indexed fresh entry is inserted with the may-be-stale marker
(ItemPointerSIUMaybeStaleFlag, bit 14 of the offset) set on its heap TID.
verify_nbtree already strips that marker before fingerprinting a plain leaf
tuple, so its bloom image matches the unflagged heap TID from the heap scan.
But when many such entries share one key, deduplication copies the flagged
heap TIDs verbatim into a posting list's heap-TID array, and the posting
branch fingerprinted each element without stripping -- so a flagged element
never matched the plain heap TID and heapallindexed reported a false
positive. (My earlier belief that only plain leaf tuples carry the marker
was wrong; the fix and a corrected comment reflect that.)

Fix: strip the marker per element on the palloc'd plain tuple that
bt_posting_plain_tuple() produces, mirroring the existing plain-tuple strip.
Deterministic reproducer (fails before, passes after): a two-index table,
fillfactor=10, all rows UPDATEd to a single key value twice so the SIU fresh
entries dedup into one posting list of flagged live TIDs, then
bt_index_check(heapallindexed => true). Added as a regression test in 0008.

0007: amcheck HOT-indexed chain recognition -- over-broad exemption tightened

verify_heapam's "HOT chains should not intersect" check exempts the case
where several redirects legitimately converge on one live tuple (a collapsed
SIU chain: the root and each entry-bearing dead member become a redirect to
the survivor). v63 keyed that exemption on the target merely carrying
HEAP_INDEXED_UPDATED, which is set on any SIU-produced HOT tuple -- so a
genuinely corrupt page where two unrelated redirects converge on such a
tuple would have been silently accepted, defeating exactly the check amcheck
exists to make.

The fix was to exempt only the actual collapse shape -- the target is a
heap-only HOT-indexed survivor (heap-only was already verified) AND the
other predecessor forwarding to it is itself a redirect or a collapse
stub. An ordinary tuple converging there, or a non-HOT-indexed target, is
still reported. Verified this does not regress legitimate collapse: a
multi-redirect-to-survivor page still passes verify_heapam cleanly.

0008: statistics + comprehensive test suite

- Adds the posting-list-dedup heapallindexed regression test for the 0005
fix above (section 34).

best.

-greg

Rebased onto 3cf5264557b to address conflicts, no other changes.

-greg