Re: nbtree: opt-in leaf key prefix compression

Hello,

v2 attached to appease the cf-bot, master moved under me (notably Peter's
d42c5457e5, the multi-level page-deletion WAL fix, which touches nbtpage.c
right where this patch drops the PREFIX item on an emptied leaf). v2 is
rebased on top of that; the two changes don't actually overlap, and page
deletion of a prefix leaf still replays byte-for-byte under
wal_consistency_checking=all.

While rebasing I did a review pass of my own with Peter's nbtree
sensibilities in mind, since he's the obvious reviewer and I'd rather
not waste his time on things I can see coming.

To that end, three things changed:

1. One split-collection routine, not two.

v1 had the primary _bt_split() build the left/right plain-item
arrays with its own inline loop, while redo built them with
_bt_split_leaf_collect() -- two hand-maintained copies of the same
logic that have to agree exactly or a standby diverges with no
version bump to catch it. That's the classic footgun. v2 has
_bt_split() call _bt_split_leaf_collect() too, so the primary and
redo derive the identical plain-item sequence from one place and
then code it with the shared _bt_split_leaf_layout(). The incremental
path for internal pages is unchanged.

2. amcheck actually checks the new format.

v1 taught verify_nbtree.c to *decode* coded items (so the existing
checks run on real keys), but it validated none of the BTP_PREFIX
structure and the test suite never ran amcheck on a prefix index at
all. v2 adds structural checks -- the flag only on leaf pages, a
well-formed PREFIX item at the expected offset with a legal length --
and contrib/amcheck now builds a prefix-compressed index (shared
prefix + no-shared-prefix + NULL, enough rows to split and dedup) and
runs bt_index_check / bt_index_parent_check with heapallindexed over
it. amcheck is how "two formats coexist forever" stays true, so it
should carry its weight here.

3. Docs and comments matched to the code.

The README still described the first design, where split and dedup
pages were carried by full-page image; that's long gone (redo rebuilds
the coded bytes from logged plain items now), and it also still
claimed dedup and bottom-up deletion don't run on prefix pages, which
is also no longer true. Rewritten to match. A couple of stale
XLH_SPLIT_RPREFIX-era comments went with it. I also added the
"can't happen" bounds asserts on the WAL-data-driven item loops in
redo.

The one thing I deliberately did NOT change, because I think it's a
real design question rather than a cleanup, is how much nbtsplitloc.c
knows about the feature.

Right now _bt_findsplitloc()/_bt_recsplitloc() reason in coded (on-page)
bytes on a prefix page, and there's a small guard that rejects a split
point that would leave the left page with no data items. I know the
history here: when deduplication went in, the strong preference was for
nbtsplitloc.c to stay ignorant of posting lists and for _bt_split() to
fix up reality at one point just before WAL-logging. I tried to honor
that -- the split chooser still treats everything as plain tuples for
placement, and the "room for at least one heap TID" conservatism in
_bt_recsplitloc() is untouched. But I could not make the *space*
accounting pretend coding doesn't exist: a compressed leaf legitimately
holds more logical data than two plain pages, so feeding plain sizes to
the split chooser makes some splits look infeasible that are not. So
the accounting is in coded bytes, and the guard exists because coded-size
accounting can otherwise pick a degenerate point that plain accounting
never would.

I can see two ways to push the feature further out of nbtsplitloc.c and
I'd like an opinion before I build either:

(a) leave the coded-size accounting where it is but move the
degenerate-split guard into _bt_split() (reject/retry there), so
nbtsplitloc.c at least stops having a prefix-only early return; or

(b) have nbtsplitloc.c reason entirely in plain sizes and teach
_bt_split() to fall back to a plain (uncompressed) left/right half
when the chosen point doesn't fit coded -- i.e. the page just
doesn't get compressed this time, rather than the chooser knowing
about coding at all.

(b) is closer to the "nbtsplitloc.c knows nothing" ideal but gives up
compression on exactly the fullest pages; (a) keeps the space win but
leaves the accounting coded. I lean (a). Thoughts?

Two open items I flagged in v1 still stand: the forced-full-page-image
fallbacks (XLH_SPLIT_RFPI / XLH_DEDUP_RFPI) only fire for a page whose
plain payload would exceed a block, which I've never hit on real data,
I can either add a test that forces the path or demote it to a
can't-happen error if we decide it's unreachable; and I owe an
"alternatives considered" note on why this is a new on-disk format
rather than an extension of posting lists (short version: posting lists
collapse *equal* keys, this compresses *distinct* keys that share a
prefix, so they're complementary, which the dedup composition in the
patch relies on).

best.

-greg