Re: Tepid: selective index updates for heap relations

Here is v79, rebased on 1910daf98. It is the same 21 patches, but I'd like to
stop presenting them as one thing. They are two groups, and the first can be
reviewed and committed without the second.

First, some numbers. These are paired TPS medians against the merge base on a
FreeBSD m6id.metal, with all of 0001-0019 applied, from the v72 code:

updating 1 of 8 indexed columns +51.6% TPS
mixed 80/20 read/update +32.3%
plain index scan after churn -5.9% (more/longer unresolved chains)
index scan, untouched table -1.8%
index-only scan, untouched -1.9%
BitmapAnd, exact, untouched -2.0%
CLUSTER, 2 indexes, 300k rows +54% to +62% time
CLUSTER, 1 index +3%

With only 0001-0008 applied, every case was within 1.2% of baseline. I believe
the scan costs come from walking chains that may hold stale entries, but I
haven't profiled them, and I haven't found what makes multi-index CLUSTER
slower.

On-disk costs:
- one infomask2 bit (0x0800),
- a bitmap of ceil(natts/8) bytes on each HOT-indexed tuple,
- two new WAL flag bits,
- and a visibility map widened from 2 to 4 bits per heap page,
which pg_upgrade rewrites.

But the cost I most want to surface and work on mitigating in a later version
of this is: a page holding a HOT-indexed tuple, live or reduced to a stub by
prune, is never marked all-visible or all-frozen, because an index-only scan
there could return a stale entry's values. Those pages cost every vacuum a
visit and every index-only scan a heap fetch. In a quick test, updating an
indexed column in 10% of the rows kept all 11 pages out of the VM through four
vacuums and a later plain HOT update of those rows; only deleting them brought
the pages back. None of the benchmarks above measure this.

So there are trade-offs to discuss or creatively work around if we'd like to
someday commit this series or something like it.

0001-0008: making the table AM contract less heap-specific

Today the executor, index AMs and TM_FailureData assume heap: a TID names one
version, a row changes TID when updated, and failures are reported as
ctid/xmax/cmax. These patches name that contract (LocatorDesc) so a table AM
can declare something else: in-place updates, a wider locator, or blocks where
a BitmapAnd must union rather than intersect. TM_FailureData now carries the
facts the executor actually uses (modified_by_same_command and so on), with
heap's physical fields moving to a heap-private struct. Heap's behavior is
unchanged. The consumers I have in mind are undo-based and in-place AMs
(OrioleDB, zheap-style designs, my UNDO work in CF 7389) and indirect indexes,
not this feature.

0009-0019: HOT with selective index updates for heap

When an UPDATE changes some indexed columns, the new version stays on the page
as a HOT chain member, and only the indexes on changed columns get new entries.
The aim is the write amplification on wide, many-index tables where one or two
indexed columns churn.

0009 is just tests for existing HOT behavior, something I added to make all the
subtle cases more apparent before and after the changes; it can go in on its
own, as Bharath suggested. 0020 and 0021 (test AMs, benchmark harness) are not
for commit.

Bharath, Chao: answers to your open questions, in order.

> where to store the modified index bitmap

On the tuple, trailing its data, sized by the tuple's own natts so ADD COLUMN
doesn't break it. When prune collapses a chain, dead members whose columns
later hops don't cover become small xid-free stubs that keep only the bitmap
and a forward link; the rest are reclaimed.

> how bitmap scans and index scans produce correct results

An index scan unions the bitmaps of the hops it crosses and drops the entry if
any of them changed one of that index's columns; the entry for the current
value returns the row.

For BitmapAnd, the update sets a per-page bit in the visibility map, and on
such pages BitmapAnd unions the two pages and forces a recheck instead of
intersecting. That is Alexander's false negative; contrib/bloom and
pageinspect have tests for it.

> vacuum cost, heap vs index bloat, fewer rows per page

See above; I don't have a vacuum-time comparison yet, and the visibility map
problem is the part I expect to matter most. Index size after churn was 19%
smaller (47.5 MB to 38.4 MB) with equal heaps; WAL per updating transaction
fell from 885 to 384 bytes. The bitmap is one byte per eight columns, only on
HOT-indexed versions. An update that can't fit on the page falls back to a
normal update, as HOT does.

> upgrade, replication, tooling

pg_upgrade rewrites VM forks; --swap refuses when that's needed. Physical
replication uses the existing heap update and prune records, with new flag
bits; catversion and XLOG_PAGE_MAGIC bumps are left for commit time. Logical
apply is gated by a subscription option (patch 19). amcheck verifies chains
and index coverage; pageinspect understands the new tuples.

> why compute modified indexed attributes in the executor (and the
> concurrency question)

So the executor, not heap, decides which indexes get entries which is logically
a component of any table AM, not just heap. heap, or any other table AM, only
supplies the comparison. It runs before table_tuple_update(), on the version
the executor has, as heap_update() itself does today. If someone updates the
row first, table_tuple_update() fails, EPQ re-fetches the old version and
ExecUpdateAct() recomputes from it.

> the 0001/0002 test changes and the injection point rename

Those changes are now in 0012, the patch that needs them: deleting through
main_view and reading gtest1v and base_tbl came back in a different order once
the executor drives index maintenance. I'll drop them if someone shows they
can be avoided. The injection point didn't move: heap_update() keeps
heap_update-before-pin, and simple_heap_update() gets its own point before its
new fetch, which the syscache test now waits on.

> Chao: opt-in per table

Not now, I'm hopeful not ever. There is no reloption or GUC today, I feel this
is something that either works and is the default or doesn't go in.
Half-measures leave users confused, either you've solved the selective index
update problem or you haven't.

> Chao: exposing staleness to index_getnext_slot() callers

Agreed it's a contract change, but it's small: one boolean,
xs_entry_needs_recheck, set by the table AM. IndexScan, CLUSTER and
replica-identity lookup drop the entry; unique and exclusion checks need to see
it, since a stale entry can resolve to the row being checked. Filtering inside
the AM would hide it from them.

Changes since v74:

- VM counts no longer include the new bit;
- the pg_upgrade VM rewrite is now correct across segments, with a new test;
- pg_dump and pg_upgrade of a v19 cluster with subscriptions work again;
- pageinspect's tuple_data_split() no longer errors on the new tuples;
- CLUSTER drops the bitmap bytes;

and smaller fixes from review (prune assertions, a leaked bitmap, buffile error
handling, tests that could pass without testing anything). Every patch is
pgindented and perltidied, and passes regression and isolation on its own.

cfbot's last failure, a 009_twophase timeout on Windows, also showed up on CF
6854 and looks like the walreceiver reconnect hang Alexander Lakhin reported
[0]. I couldn't reproduce it.

best,

-greg

[0] https://postgr.es/m/93515d62-edce-9041-ec6e-7122f6e92bea%40gmail.com