Re: nbtree: opt-in leaf key prefix compression

Hello,

This is the design write-up I promised, with a vibe-coded working
prototype of it I used to test some ideas as v9. It is offered as a
proof of concept for the design below something concrete to discuss no
as something to commit. It replaces the single-column, varlena-only
patch (v1-v8) completely.

I'd like agreement on the design and trade-offs before anyone spends
time reviewing the code line by line.

The earlier proposal (v8) had a design that closed off the multi-column
case (the "column-level" compression he asked about). The most
contentious bit of this will be the on-disk format change which we'll
all have to live with for a while.

The design takes into account:

- Bayer/Unterauer "Prefix B-trees" and Graefe's "Modern B-Tree
Techniques": entries in a node share a common leading prefix of the
key, stored once. Graefe separates a prefix taken from the keys
actually in the node from one derived from the node's key range
(the separator keys above it).

- Oracle: COMPRESS n factors out n whole leading columns, with a
per-block table of distinct prefixes that rows point into, so a
block can hold several prefixes. Advanced Index Compression picks
the scheme per block and adds partial-column prefixes.

- SQL Server page compression: a per-page anchor value per column;
each cell stores how many leading bytes of the anchor it reuses,
plus its own bytes. A dictionary step then dedups whole values.

From that research, "complete" for this feature means:
- a prefix can cover one or more whole leading columns,
- a prefix can end partway through a column,
- a page can hold more than one prefix,
- prefixes are chosen per page, not fixed at CREATE INDEX, and
- nothing depends on the column's data type.

My earlier patches (v8 and earlier) did one prefix over part of the
first column. This v9 design attempts to be "complete."

Where does this sits in Graefe's taxonomy, and the equality rule?

It compresses against the keys actually on the page, chosen each time
the page is written as a whole. The prefix doesn't act as a low key;
separators and internal pages are untouched. That keeps the feature
inside the leaf read and write paths, which is why it can be a per-page
opt-in with no BTREE_VERSION change.

This is because, as in other places, bytes are shared only when they are
identical as stored, *never* on the strength of opclass equality. As
I've learned working on the Tepid and Hot for Expressions patches an
index-only scan (IoS) returns the bytes the index stored, so a value can
only be rebuilt from another tuple's copy if the two were identical to
begin with. Equal-but-different encodings (numeric 1.0 and 1.00,
nondeterministic collations, plenty of user-defined types) must not be
merged.

If that holds true, then two things follow:

- It's correct for every type, including user-defined ones, with no
equalimage requirement. Deduplication needs equalimage because it
merges tuples the comparator calls equal and keeps one copy; this
never merges anything. Search stays correct because identical
bytes always compare equal.

- It needs no new opclass support function.

Which makes it both correct and slightly less complicated.

I'd planned to compare column by column (shared whole columns plus a
byte count into the next one). The prototype takes the longest common
prefix of the two tuples' data areas instead. That covers whole leading
columns, part of the first differing column, and NULL bitmaps that
happen to match, and it needs no tuple descriptor at all. That turned
out to matter a lot for WAL (section 6).

This spoils some types. Sharing is by stored bytes, and integers and
timestamps are stored in native byte order, which is little-endian on
the machines most people run. Two bigints or timestamps that differ
only in their low-order part differ in the *first* byte stored, so
nothing after them is shared.

So, an index on (bigint, timestamptz, text) gains almost nothing. The
same values as text compress by 45%. Leading integer columns that are
*equal* (the low-cardinality tenant_id case) are shared in full. Doing
better for fixed-width types needs either an order-preserving byte
encoding of the key (Graefe's normalized keys, below) or type-aware
coding, which would give up the catalog-free property.

I've not expored normalized keys as yet, but I could if that's of
interest. What to do about this is an open question, let me know your
thoughts.

On-disk format

A leaf of an index with prefix_compression on may carry a new page flag,
BTP_PREFIX (bit 9 of btpo_flags). BTREE_VERSION, the catalog and
BTPageOpaqueData don't change. A page takes the format only when it's
next written as a whole, so old and new pages coexist, and pg_upgrade,
replicas and turning the option back off all keep working.

A BTP_PREFIX page has one extra item, a PREFIX DIRECTORY, at the offset
where the first data item would otherwise be. The data items follow it
in key order. P_FIRSTDATAKEY therefore depends only on the page flags,
binary search over the data items is untouched, and all the code that
locates the first data item stays as it is.

The prefix directory holds:

- one or more GROUPS of consecutive data items, each with an ANCHOR:
a copy of the key part of the group's first member. A new group
starts when an item shares no leading byte with the current anchor.
Several groups per page let a page that straddles (tenant, region,
url) boundaries compress each run, rather than collapsing to the
short prefix the whole page has in common.

- a cache of the decoded size of the page's items (their total and
the largest), which the split-fit rule in section 5 needs on every
insert. Every change to the page keeps it exact, and we can use
amcheck to enforce it.

A coded item is an ordinary IndexTupleData header followed by a 6-byte
code header (group, number of shared bytes, the original t_info), the
original null bitmap, and the bytes after the shared prefix. Its t_tid
is its real heap TID. A posting list stays uncoded, in the standard
posting-tuple layout, so everything that only reads heap TIDs (VACUUM,
LP_DEAD hinting, deletion, posting list splits) works on coded items
unchanged. Pivot tuples are never coded. Decoding copies the anchor's
shared bytes back in front of the residual, which gives the original
tuple byte for byte.

Two things differ from the two prototypes already in the thread. Unlike
the follower design, a coded tuple doesn't use a t_tid status bit, so a
reader that forgets to decode gets a wrong key, never a wrong TID. And
unlike my earlier patch, there's more than one prefix per page and it
isn't limited to the first column.

There are trade-offs to be sure, the code header plus alignment means
short keys don't gain. A plain item is a 4-byte line pointer, an 8-byte
tuple header and the key rounded up to 8 bytes; a coded item adds the
6-byte code header. A 12-byte SSN or phone-number key takes 28 bytes
plain and 28 coded, however much it shares.

Pages that wouldn't save at least a sixteenth stay plain, so such
indexes aren't hurt, but they don't benefit either. A narrower code
header alone doesn't fix this; the 8-byte alignment of every item does
most of the damage. Coded items are only ever copied out, never read in
place, so they could be packed without alignment, but PageAddItem aligns
every item, so that means placing them by hand. I'd like an opinion on
whether that's worth it, I'm leaning toward 'no'.

Reading

The proposal said the hot path would compare a search key against a
coded item without rebuilding it. The v9 prototype rebuilds into a
fixed per-backend buffer instead (a few memcpy calls, with no palloc or
index_form_tuple).

I did try/profile the compare-without-rebuilding path. It saves less
than it looks like it should because most of the cost of a comparison
in a binary search is the cache miss on the item, which a plain page
pays too. So I'd like to keep the simple form unless measurements on
the wider set of key shapes force our hand.

Scans that need only heap TIDs (plain index scans, bitmap scans,
count(*)) don't decode at all once every scan key is already satisfied
for the page, which is the skip-decode change Yao suggested earlier in
the thread (great idea, thanks!).

The split-fit guarantee

Building out the prototype helped immensely on this one. A coded page
legitimately holds *more* than a plain page's worth of decoded data
(that's the point of it), so its decoded items can't always be laid out
on two plain pages, and splitting requires exactly that.

After much trial and error the rule the prototype enforces instead:

A coded page keeps: T + H + 2M + heap TID <= 2 * U

where T is the decoded size of its items (with line pointers), M the
largest of them, H the high key and U the usable space on a page. I
believe that under that bound a legal split point always exists.

Take the leftmost point whose right half fits a page. The point before
it didn't fit, so the left items before it total less than T - (U - H).
Adding one more item and the new high key (a truncated copy of an item
plus a heap TID) gives a left half under T - U + H + 2M + heap TID,
which the bound keeps under U.

An insert splits the page before it would break that bound, which is
what the cached decoded size in the directory is for. A split decodes
the page, picks the point by plain sizes (the stock _bt_findsplitloc
when the decoded items fit one page, otherwise a size-checked balanced
point), writes both halves plain, and then codes each one. Any tuple
can always be stored uncoded, and a page that won't compress stays
plain, so AFAICT the floor is always "exactly as today".

There is one addition case to consider, when a large incoming tuple
(close to BTMaxItemSize) arriving at a page that is already dense.
There may be no point that places the new tuple too. The prototype
handles it by splitting the existing items alone and retrying the insert
from the top, the same way an insert that has to wait on another
transaction already restarts, including redoing the uniqueness check.
I'd especially like this argument/idea checked by others.

WAL

Because coding needs only the page and the tuple (no tuple descriptor,
no relcache), redo can run the same routines the primary ran:

- An insert logs the coded tuple; redo adds it and updates the
directory's cached size.

- A split record gains a flags byte saying whether the original page
and each half were coded. Redo decodes the original page, collects
the left half's items exactly as _bt_split did, and lays them out
with the same routine. The right half arrives as its coded items,
which _bt_restore_page places exactly as the primary did.

- Deduplication and posting list splits on a coded page are replayed
by repeating the primary's steps.

So no record on a coded page needs a full-page image. My earlier v8
patch forced one on most splits of compressible pages, so this is a good
discovery.

The records are also smaller than plain ones, since items and right
halves travel coded. The flags byte is a WAL format change, so it needs
an XLOG_PAGE_MAGIC bump. I added a new recovery test that replays every
coded-page record type on a standby with wal_consistency_checking on,
and I checked that it fails when the split redo is deliberately broken.

Composition with deduplication

They stay composable, not mutually exclusive. Deduplication collapses
tuples whose whole key is equal into one key plus a TID list. Prefix
grouping factors out a leading run shared by distinct keys. On one page
a posting tuple is coded like any other, with its TID list carried after
the residual. Runtime deduplication and bottom-up deletion work on
decoded copies of a coded page's items. Deduplication then re-codes the
result against the page's existing directory, so the page can only
shrink and nothing has to abort.

Performance numbers

Measured on a bare-metal c7i.metal-24xl (one Xeon 8488C socket, turbo
and deep C-states off, server pinned to 12 cores), release build, C
collation, 2 million rows per key shape, the same binary with the
option on and off. 4 reps with the arms interleaved; reads are 20
samples per arm; the figure is the change in the median. An A/A run
(the binary against itself) stayed within 1% on everything but VACUUM
and the shortest range scans (3%). Harness, data generator, raw CSV
and per-cell confidence intervals are attached.

% change, on vs off size build insert WAL warm warm cold cold
point IOS point IOS
URLs -35 +10 +10 -17 0 +13 -30 -6
file paths -27 +8 +9 -12 -2 +5 -18 -8
tenant-prefixed keys -18 +9 +11 -7 +5 +17 -11 +4
(tenant_id, region, -33 +4 +9 -12 . +12 . -5
status, name)
JSONB (status, placed) -24 +4 +8 -4 . -1 . 0
reverse-DNS names -3 +10 +6 -4 +5 +8 +7 +3
JSONB sku -2 +2 +6 -1 . 0 . 0
JSONB (city, street) -1 0 +3 0 . 0 . 0
phone numbers (E.164) 0 +5 0 +2 0 0 0 0
SSN-format ids 0 +10 0 +2 -1 0 0 -1
JSONB email 0 +5 +1 0 . 0 . 0
(tenant_id, bigint, ts) 0 +4 +2 -1 . 0 . -1
(ts, tenant_id, text) 0 +20 +1 -1 . 0 . 0

"insert" is a 2M-row bulk insert into an indexed empty table; "warm
IoS" a full index-only scan (an ordered index scan for the JSONB
expression indexes); "point" 20,000 lookups; "." marks queries that
don't apply. Single-row insert throughput was within 1% for every
shape, VACUUM 2-9% faster on the compressible ones, bitmap range scans
1-2% faster.

Take-aways:

- The design does what it should where keys share real prefixes:
18-35% smaller, less WAL, cold point lookups 11-30% faster.

- It costs CPU: 6-11% on inserts and 4-10% on CREATE INDEX where it
compresses, and 5-17% on warm index-only scans, which have to
decode every tuple (about 9 ns each). Cold full scans gain less
than the size suggests, because gp3 reads sequential pages fast
enough that decoding dominates; on tenant keys the scan is 4%
slower even cold.

- The short-key shapes you'd might expect to benefit (phone numbers,
SSNs, emails, SKUs) don't. Under ~20 bytes the code header and
8-byte alignment eat the shared bytes. Those pages stay plain, so
they lose nothing, but the build still pays to find that out (up to
20% on CREATE INDEX) and that's something that might push us to
consider an opt-in strategy or push us to find some clever way to
avoid that 20% (maybe by avoiding trying compression on well known
types or having a way to record columns that aren't compressing
after trying a few, I don't know on this one).

- Fixed-width integer and timestamp columns that differ don't share
much, so those multi-column indexes are unchanged and here's another
reason we may want to skip well known types.

I didn't benchmark working sets larger than memory or collations other
than C. I don't see those as necessary, stop me if I'm wrong.

Open questions

- Opt-in or automatic. I've kept it an off-by-default reloption,
since the format commits us forever and has a real insert cost. It
could become the default later without an on-disk change.

- Fixed-width types. Is an order-preserving key encoding (Graefe's
normalized keys) the right long-term answer for integer and
timestamp prefixes, or is the byte-level form enough for the
workloads people actually have?

- A separate anchor in the directory vs. making each group's first
tuple its anchor. I chose separate anchors so deleting a group's
first tuple never forces a re-code (or the full-page image that
would come with it). The cost is one extra copy of a key per
group.

- Short keys. Packing coded items unaligned would let phone numbers,
SSNs and similar keys compress, at the price of placing items by
hand rather than through PageAddItem. Worth it?

- The read cost. Warm index-only scans pay 5-17% to decode.
Decoding straight into the scan's tuple workspace would save one
copy per tuple; beyond that, is a cost of this size acceptable for
an opt-in feature, or does it need to be closer to zero?

- The split-fit bound and the retry path in, thoughts?

Peter, Yao: the on-disk format, WAL change, and split-fit are sections
where I could use your detailed feedback.

best.

-greg