Re: nbtree: opt-in leaf key prefix compression

Hi Greg,

Thanks for working on this, took a look at the v4 patch.

I think this is very worthwhile work. FWIW, a recent SIGMOD paper on
B-tree compression (https://dl.acm.org/doi/10.1145/3654972) noted that
while front-coding saves a lot of space for strings, decompression CPU cost
tends to be the main bottleneck for queries on modern hardware. Looking at
the v4 benchmarks, they mostly cover index size and write throughput -- did
you have a chance to measure read-side performance (e.g. index scans, point
lookups)?

A few quick questions from having played with something similar a while
back:

1. Skipping decompression when index tuples aren't returned:
Right now _bt_readpage() eagerly calls _bt_getitem() to decode every leaf
tuple. That's necessary when the scan actually needs to return the index
tuple (like IndexOnlyScan), but for operations that don't return tuples and
only care about the heap TID -- such as a plain IndexScan, BitmapIndexScan,
or COUNT(*) -- could we skip decompression?

2. Multi-column indexes:
The patch requires column 0 to be a varlena. I'm curious if you considered
supporting subsequent columns (e.g. for something like `(tenant_id int, url
text)`), or if keeping it strictly to the first column was just a natural
place to draw the line on complexity for now?

3. Prefix boundaries within a page:
With one prefix per page, if a page spans two different domains (say, a
bunch of `http://example.com/1` <http://example.com/1>, `.../2` followed by
`http://sample.org/1` <http://sample.org/1>, `.../2`), the second group
only shares "http://". Just curious if you've considered this kind of case?

Curious to hear your thoughts.

--
Yao Feng

Greg Burd <greg(at)burd(dot)me> 于2026年10月30日周五 00:43写道：

> Hello,
>
> v4 attached, rebased on current master (cfbot had gone stale on a
> not-applying from the v3 window; the patch applies clean on HEAD, so
> this mostly just gives the bot a fresh version to chew on). No code
> changes from v3.
>
> I did say I'd run more benchmarks for fun, so here they are. Release
> builds (cassert=off), master vs the patch, c7i.4xlarge, fsync and
> synchronous_commit off so the WAL numbers aren't buried under flush
> latency. "off" is the patch with prefix_compression left off, to show
> the default path is free.
>
> The headline is that the size win shows up where the keys are actually
> distinct-but-prefixed, which is the case the feature is for. One row at
> a time into an existing URL index (37-byte shared prefix, distinct
> suffixes):
>
> workload index pages (master -> on) WAL/txn (master -> on)
> ---------------- ------------------------- ----------------------
> insert_random 22177 -> 7506 (-66%) 292 -> 226 bytes
> insert_ascending 19036 -> 5429 (-71%) 277 -> 227 bytes
>
> TPS is within noise either way (random 138k -> 136k, ascending 134k ->
> 131k). WAL per insert drops because a coded tuple is smaller than the
> plain one it replaces. The split/dedup redo rework from the earlier
> versions is what keeps that from turning into a full-page-image tax.
>
> CREATE INDEX on 2M rows is a more mixed bag, because how much a prefix
> buys depends entirely on the key shape:
>
> shape index pages (master -> on) build WAL (master ->
> on)
> ------------------ -------------------------
> ------------------------
> url (g % 1e6) 10531 -> 9538 (-9%) 80 -> 48 MB
> code (ACCT-...) 7140 -> 6495 (-9%) 48 -> 32 MB
> md5 (random hex) 14420 -> 13026 (-10%) 99 -> 109 MB
> jsonb (tenant+path) 11636 -> 10657 (-8%) 71 -> 28 MB
> int (control) 5487 -> 5487 (0%) 32 -> 32 MB
>
> Two things worth calling out there. The build-time size wins look
> smaller than the insert ones only because these build shapes use lots of
> near-duplicate keys (g % 1e6) with a short shared run; deduplication
> already collapses most of that, so prefix coding is adding a few percent
> on top rather than doing the heavy lifting.
>
> The insert workload above, with genuinely distinct keys, is the fairer
> picture of what the feature does. And the int control is exactly
> unchanged. A page whose keys share nothing is left alone, so there's no
> cost to carrying the option on a table where it doesn't pay.
>
> md5 is the one that surprised me a little: even random hex strings share
> enough of a leading nibble run across a page to shave ~10% off, though
> the build WAL ticked up slightly there (109 vs 99 MB), which I want to
> look at. Probably the recompression churn on a shape that barely
> benefits. Not a blocker, but I'd rather understand it than wave it off.
>
> Update churn (indexUnchanged UPDATEs, 8 clients) is within noise on TPS
> and WAL, and the index stays flat at 186 pages before and after on all
> three variants, which is bottom-up deletion doing its job on coded pages.
>
> Everything else stands from v3.
>
> best.
>
> -greg
>
>