nbtree: opt-in leaf key prefix compression

Hello Hackers,

This is a patch that adds leaf key prefix compression to nbtree, behind
a new per-index storage parameter, prefix_compression, off by default.
It's something I started a long time ago when primarily working on
JSONB-like data storage/indexing/etc. in Postgres when a colleague
pointed out that it didn't yet exist and his measurements showed that it
should. He wasn't wrong. It's a solid win for performance and overhead
IMO, but YMMV.

The motivation is simple: indexes on keys that share a long leading
prefix (URLs, reverse-DNS names, a leading JSONB path, a tenant-id
prefix) spend most of their bytes storing that prefix over and over.
Store it once per page and the index gets a few times smaller, which
means fewer pages to read and less WAL to write. All good things.

A URL index in my tests is about 3x smaller; an index with little shared
prefix is unchanged (the page is left alone when a prefix does not pay
off).

Overview:

When a leaf page is written as a whole (during an index build, as a
split half, or as the result of a deduplication pass) and its data items
share leading bytes in their first key column, the page is rebuilt in a
new BTP_PREFIX format: one PREFIX item after the high key holds the
shared bytes, and each data item is stored "coded", with its copy of the
shared prefix replaced by a one-byte length. Reads of a leaf data item
go through a single accessor, _bt_getitem(), that decodes on demand into
caller-supplied scratch; high keys and internal-page downlinks are never
coded and are read with the existing PageGetItem().

This is a per-page opt-in with no on-disk version change: BTREE_VERSION
and the catalog version are not touched. A page is converted only when
it is next written as a whole, never by an ordinary insert, VACUUM, or
key-range change. So an existing index "faults forward": old-format and
new-format pages coexist in the same index indefinitely. That is what
makes the feature safe across pg_upgrade, physical replication, and
standbys with no REINDEX: a replica that has not yet replayed a page's
conversion still reads the old format correctly, and turning the
parameter back off stops new conversions while existing coded pages stay
readable.

Performance:

Release builds (cassert=off), origin/master vs the patch, on a
c7i.4xlarge, pgbench, fsync and synchronous_commit off so the index
effects are not masked by WAL flush latency. "off" is the patch with
the parameter off (the default path), to show it is free when unused.

index size (pages), CREATE INDEX on ~500k rows:

shared prefix / key master patch=on
--------------------- ------ --------
URL-like, distinct 10531 7848 (-25%)
JSONB path, distinct 11636 5782 (-50%)
int (no shared prefix) (same) (same, page left uncompressed)

insert throughput (one row at a time into an existing index):

workload TPS master->on WAL/txn master->on
--------------- ------------------ ------------------
insert_random 143.7k -> 142.8k 292 B -> 226 B
insert_ascending 144.9k -> 139.4k 277 B -> 228 B

WAL per insert is slightly *below* master because the coded tuple logged
is full-page-image penalty. CREATE INDEX WAL is roughly half of
master's on these keys.

The "off" column tracks master within noise on every workload, so the
default path is not paying for a feature it is not using.

Deduplication composes with it:

Prefix compression and deduplication stack. A build deduplicates first
and then codes the finished page, so a duplicate-heavy prefix index is
no larger than a plain one: the posting lists collapse the duplicates,
and the prefix then front-codes the distinct keys that remain. Across a
duplication sweep the prefix index is <= plain everywhere, and smaller
once there is any shared prefix among the distinct keys. Without this
the earlier drafts were several times *larger* on duplicate-heavy data,
which is the trap to avoid if you try this yourself.

Bottom-up index deletion runs on coded pages unchanged, since it only
removes items and never rewrites survivors. A runtime deduplication
pass on a coded page decodes its items first, and because a coded page
can hold more logical data than fits plain, the pass aborts cleanly and
the page splits instead when the decoded set would overflow, it never
errors out.

WAL:

The part I most want eyes on. Replaying a coded page byte-for-byte is
the hard requirement (wal_consistency_checking has to pass on a
standby), and the obvious implementation (a forced full-page image on
every change to a coded page) costs a whole page of WAL per insert.

Instead redo reconstructs the coded bytes the way the primary did. The
catch is that redo has no relcache and cannot run the prefix-choosing
heuristic, so the primary logs the prefix it chose, and a single
Relation-free layout routine (_bt_split_leaf_layout) is shared by the
primary and redo so both emit identical bytes from the same inputs:

- an in-place insert logs the coded tuple; the standard insert redo adds
it verbatim;
- a split logs each half's chosen prefix plus the right half's plain
items, and redo lays each half out coded;
- a deduplication logs the chosen prefix plus the deduped plain items.

Each path keeps a bounded fallback to a forced image for a
pathologically compressible page whose plain payload would exceed one
block, so the logged payload can never exceed BLCKSZ.

What reviewers should know going in:

Things I already know are worth a hard look, so you don't have to find
them cold:

- A posting-list split on a coded page, and a deduplication pass whose
re-compression then declines, are the two fiddliest WAL paths. I
had bugs in both (a palloc inside a critical section on the first;
redo not decoding on the second) and have fixed them, but they are
where I would point a reviewer first. I could not turn the second
into a failing wal_consistency_checking case and would value a
second opinion on whether the path is actually reachable.

- Every read of a leaf *data* item must go through _bt_getitem(). I
audited the readers; the one I missed on the first pass was the
array-scan look-ahead in _bt_readpage(), now fixed. A reviewer's
instinct for "is this a data item or a pivot?" is exactly the check
I want applied to the rest.

- The split point is chosen on coded sizes, which breaks the usual
assumption that a leaf holds at most two pages' worth of data; there
is a guard against a degenerate split that would leave the left page
with no data items. nbtsplitloc.c is worth a read for that reason.

- Runtime deduplication on a coded page is the one place that can
decline and fall through to a split rather than reclaim space. That
is deliberate (the decoded set can exceed a page), but it means a
duplicate-heavy index populated by one-row-at-a-time inserts is less
compact than the same index built with CREATE INDEX. I think that
is an acceptable trade; it may warrant a doc note.

- amcheck decodes every leaf data item, including under heapallindexed.

Tested with wal_consistency_checking=all on a primary and a streaming
standby across insert, split, deduplication, delete and vacuum
workloads, through immediate-crash recovery, and across a pg_upgrade
that carries both page formats in one index. -Werror, --enable-cassert
and --enable-injection-points clean; make check, the isolation, amcheck,
pageinspect and pgstattuple suites, and 027_stream_regress all pass.

Open questions:

(a) Is a per-page opt-in with no version bump the right contract? I
chose it so the feature needs no REINDEX and is a no-op risk for
anyone who leaves it off, at the cost of old and new page formats
living in one index forever.

(b) Is the shared primary/redo layout routine the right factoring, or
would you rather the build, split and dedup paths share even more (a
common "code a leaf from plain items + prefix" helper)?

(c) The forced-image fallback threshold is "plain payload > one block".
It essentially never fires on real data; is that the right place to
draw the line?

The patch is one commit against master. I'd appreciate review of the
approach and the code, and I'm happy to work through whatever it turns
up.

best.

-greg