Re: nbtree: opt-in leaf key prefix compression

Hello again,

v8 attached. This is the skip-decode follow-up I promised Yao, now
implemented and measured on bare metal.

Recap of the idea: a prefix leaf stores each data item's first key
column front-coded against a per-page prefix, and a scan decodes it
through _bt_getitem() on the way past. Yao pointed out (citing the
SIGMOD 2024 front-coding paper) that the decode CPU is the read-side
cost, and that a scan which only needs the heap TID (a plain IndexScan,
a BitmapIndexScan, COUNT(*)) shouldn't have to pay it. I agreed, with
one caveat: the tuple copy is already skipped for those scans, so the
cost that's actually left is the key *check*, and you can only skip that
where the scan keys are already known satisfied for the whole page.

What v8 does: _bt_readpage() now skips both the decode and the
_bt_checkkeys() call for a data item when all three hold:

- the scan is not an index-only scan (so->currTuples == NULL), so we
never materialize the tuple and need only its heap TID / posting
list -- both of which the coding leaves in place on the page; and
- every scan key is already proven satisfied for the whole page
(_bt_set_startikey advanced startikey to the end of the keys); and
- the scan has no array keys (array-key advancement reads the key
regardless of startikey).

In that state _bt_checkkeys()'s comparison loop starts past the last key
and reads nothing from the tuple, so the item is a guaranteed match and
continuescan is unchanged. We can take the TID straight from the
on-page tuple with no decode. I skip the whole _bt_checkkeys() call,
not just the decode: in an assert build it re-runs _bt_check_compare
from the first key to verify the startikey optimization, which would
read the still-coded key.

Index-only scans still decode, because they have to return the key. This
speeds up the "walking a known-matching run without returning the tuple"
case, not all scans.

Bare metal this time (c7i.metal-24xl, Xeon 8488C, performance governor,
turbo off, pinned to one core, THP off), 3M distinct keys sharing a
67-byte prefix, prefix index fully cached so this isolates decode CPU.
A/B is the same source built twice, once with the skip-decode gate and
once with it forced off, best-of-15 over two independent runs:

scan skip off skip on delta
------------------------ ---------- ---------- ------
bitmap index scan + count 304 ms 260 ms -14.6%
index scan + heap fetch 302 ms 241 ms -19.9%
index-only scan + count 277 ms 282 ms ~0 (gate off)

So it recovers most of the ~6-7% traversal cost I measured in the v5
read-side numbers, on exactly the scans that only want the TID, and the
index-only-scan path is unchanged within noise, the gate correctly never
fires there.

Yao's other two points (multi-column keys, and more than one prefix per
page for a leaf that straddles two groups) I still think are a separate,
larger piece of work. I'd rather land the first-column single-prefix
case first. No change to that position here.

best.

-greg