Re: index prefetching

Hi Peter,

As you know I appreciate all your work, and I find this latest work on
index prefetch interesting, I've been following along since you started.

I'm jumping in now because I've been working on a number of things that
intersect with these contracts between the table, index, and executor
with two goals in mind: adding more table and index types, and making
the contract between these pieces more explicit and yet leaving room for
innovation.

To that end I've read and studied the v38-0001 and 0004 patches and
compared those against two out-of-tree branches whose index scans don't
behave like heap's that I've been working on:

- FLUX, a table AM that updates rows in place and keeps prior versions
in UNDO (CF 7389), and
- heap with selective index updates (Tepid, CF 6968).

Both have been working on ddce1da5's slot interface for a while now.
FLUX's xs_getnext_slot owns its visibility and key recheck, and FLUX
didn't touch nodeIndexscan.c or nodeIndexonlyscan.c at all. What follows
is from porting those to v38 in my head; I'll port FLUX for real this
week and report more on that when finished.

IIRC, last November you agreed with the criticism of heap TIDs in the
table AM interface [1]. In December you said replacing them isn't
something "we're in any way obligated to fix within the scope of this
project" [2], agreed. Scope creep is a hard, I'm not asking for that,
but 0001 makes nbtree choose amgetbatch over amgettuple. So a few
details of the new interface now decide whether a table AM like FLUX can
do index scans at all. I've identified two that are potentially
blocking.

1. A table AM without the batch callbacks.

With v38 nbtree has amgettuple = NULL. tableam_index_getnext_tid()
calls amgettuple, and GetTableAmRoutine() now asserts
index_scan_batch_init, index_scan_markpos and index_scan_restrpos. So
an out-of-core table AM that worked on master fails that assertion when
it loads, and a release build ends up calling a NULL amgettuple on its
first btree scan. That may be the right trade, but it should be stated
in tableam.sgml.

I'd also like a generic implementation in tableam_indexscan.c: an
xs_getnext_slot, markpos and restrpos built from the ring-buffer helpers
plus tuple_fetch_row_version.

A simple table AM could point at those and get correct batch scans
before it does anything clever. I'm happy to write that and test it with
FLUX if you'd take it.

2. Per-item recheck from nbtree.

0001's indexam.sgml says xs_recheck "must be set consistently for an
entire scan". 0004 adds amgettransform and a per-item dynamic area so
GiST can set it per item. nbtree can't use that route. An AM that
provides amgettransform must produce xs_hitup for index-only scans,
because heapam only sets xs_itup when amgettransform is NULL, and the
docs call the two paths "mutually exclusive".

The FLUX table AM currently would need a per-item recheck from nbtree.
An in-place UPDATE of an indexed column keeps the row's TID, inserts
(k_new, tid), and delete-marks (k_old, tid), so that older snapshots
still reach the row under k_old. A scan arriving through a
delete-marked entry has to recheck against the version it finds. On my
branch that's about fifteen lines of changes in nbtree: _bt_saveitem
sets a per-item bit and _bt_returnitem copies it into xs_recheck. FLUX
also asks nbtree to keep xs_itup on plain scans (a new
xs_want_itup_recheck flag), so its xs_getnext_slot can compare the
entry's key with the visible version.

Under v38 the bit has nowhere to go, and the key comparison would need
the batch's tuples workspace on a plain scan. 0001 sizes that workspace
only when xs_want_itup is set, and xs_want_itup also selects the
index-only unguard policy and xs_getnext_slot variant.

So concretely I'm asking two things of 0001:

- Let an index AM report recheck per item without taking over the
index-only tuple. The dynamic opaque area moved into 0001 would do
it, as would separating "set xs_recheck" from "produce xs_hitup" in
amgettransform. So would a flag in BatchMatchingItem. That's 10
bytes with no padding, but indexOffset's high bit is free.

- Let a table AM ask for index tuples on a plain scan without being
treated as an index-only scan.

3. A verdict other than "dead".

deadItems[] plus amkillitemsbatch replaces kill_prior_tuple as the way
the table AM reports back on an entry. For an AM that keeps a row's TID
across updates, two more answers are useful:

- "this entry reached a live row but is stale for every snapshot",
which deletion could reclaim;

- "this entry returned the row", so that an index with several
entries per row (a multikey btree) can skip the rest.

On another branch I have a per-entry UNKNOWN/VALID/INVALID verdict that
xs_getnext_slot leaves on the scan descriptor for the next amgettuple
call. It doesn't need to be in the first commit. I'd just like the
deadItems interface not to rule it out.

4. Equal TIDs within a scan.

You stated the rule that "the same TID must never exist in any 2 index
tuples in the same index simultaneously" [3] as an index guarantee.
FLUX's delete-marking breaks it on purpose: (k_old, tid) and (k_new,
tid) coexist until VACUUM. Nothing in 0001 depends on the rule. If a
later patch dedups TIDs, for prefetching or for locking and pinning each
heap page exactly once [2], I'd like it to depend on something the table
AM declares rather than on the rule. The Tepid series has a declaration
that could serve: its 0001 adds a per-table locator descriptor (stable
across UPDATE? old version retained? largest offset?), with heap's
answers as the default. I'll raise that on its own thread rather than
here dive too deep into it here.

For 1 and 2 I can send patches against v38, or tests, whichever you'd
rather have.

Branches:
FLUX + nbtree delete-marking https://github.com/gburd/postgres/tree/undo
locator descriptor (0001-0008) https://github.com/gburd/postgres/tree/tepid

best.

-greg

[1] https://postgr.es/m/CAH2-Wzk9=x=a2TbcqYcX+XXmDHQr5=1v9m4Z_v8a-KwF1Zoz0A@mail.gmail.com
[2] https://postgr.es/m/CAH2-WzkWjKTpV1RnPcwMewyGtYdbEcdpp6vYM3=9dnS3w5PHEw@mail.gmail.com
[3] https://postgr.es/m/CAH2-WzmJau+tBTPEEYt9O61uRx3_ohW_tHfVCoECsZ7rUsj5rA@mail.gmail.com