Re: nbtree: opt-in leaf key prefix compression

On Fri, 30 Oct 2026 19:52:00 +0800, Yao Feng <fengyao0087(at)gmail(dot)com> wrote:
> Hi Greg,

Hey Yao,

Quick list-etiquette note, don't top post. Add your reply within the
content of the message or after it. :)

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

Thanks for taking the time to read and review it! :)

> I think this is very worthwhile work.

Thanks, so do I.

> 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)?

Thanks for the careful read, and for the SIGMOD pointer. That
decompression-CPU-dominates finding matches what I see below, and it's
exactly the right thing to point out, these kinds of changes are
trade-offs. Rarely is there a free win. Yep, you're right that v4 only
reported size and write throughput, I should have considered CPU
overhead as an important metric earlier in my process. So, I went and
measured the read side to see where it bites.

Read-side numbers:

Release build, c7i.4xlarge, shared_buffers=4GB, everything warm, 3M
distinct URL keys (37-byte shared prefix, 10-digit distinct suffix),
prefix_compression off vs on in the same binary so this isolates the
decode cost, nothing else:

index size off 24855 pages on 22630 pages (-9%)
point lookup (IOS) off 180.3k tps on 178.3k tps (~1%, noise)
COUNT(*) index-only off 341 ms on 360 ms (+6%)
range scan, 100k keys off 10.9 ms on 11.7 ms (+7%)

So: a point lookup decodes one tuple and the cost vanishes into the
noise, but a scan that walks many tuples pays a real ~6-7%. That lines
up with the paper and with your instinct (that, the cost is proportional
to how many tuples you decode) so it shows up on traversal, not on
seeks. This is also with a fairly short 37-byte prefix; a longer shared
prefix decodes more bytes per tuple and would cost a bit more, which I
I'll guess grows with the size of the prefix, but I should measure and not guess.

Which leads straight into your question 1.

1. Skipping decode when the tuple isn't returned

This is the right instinct, and the optimization makes sense. The heap
TID lives in t_tid, which is never coded, so a scan that only needs the
TID (e.g. a plain IndexScan, BitmapIndexScan, COUNT(*)) genuinely does
not need the decoded key to *return* anything.

Two honest caveats on how far it reaches, though. The tuple copy is
already skipped: _bt_saveitem() only materializes into so->currTuples
when the scan asked for the index tuple (IndexOnlyScan), so a plain
IndexScan already doesn't pay the copy. What my eager _bt_getitem() in
_bt_readpage() still pays for is the *key check*, _bt_checkkeys() needs
the real key to decide whether a tuple satisfies the scan keys, and
that's true coded or not.

So the win is specifically only when a tuple is in the interior of a
matching range (the scan keys are already known-satisfied and we're not
returning the tuple), the decode feeds nothing.

That's exactly the COUNT(*) / full-range case above, which is where the
6% sits, so it's worth doing. I just don't want to claim it makes all
scans free, only the "walking a known-matching run without returning it"
ones.

I'll prototype and measure it as a follow-up in this thread. The "do I
need the key here?" signal (roughly, so->currTuples != NULL, or
key-check still required) into _bt_readpage() and keep the item coded
when neither holds.

2. Multi-column indexes

First-column-only was a deliberate line, not a fundamental limit. The
coding is defined on the leading key column's bytes; extending it to a
shared prefix that spans into later columns is possible but means the
per-page prefix has to describe a column boundary and the decode has to
reassemble a multi-attribute tuple, which is more format and more decode
CPU for (I suspect) a smaller marginal win than the first column already
captures. For (tenant_id int, url text) specifically the leading int is
fixed-width and usually low-cardinality, so you'd want to prefix-code
the *second* column within each leading-value run, which is really a
different feature (per-run prefixes, see 3). I'd rather land the
first-column case, which is the common shape (a single text/jsonb key,
or a leading key that's the long one), and treat multi-column as a
follow-on proposal when/if this lands. But I'm adding it to my list
because I'm optimistic on this patch.

3. Prefix boundaries within a page

Yes, this is the real limitation of one-prefix-per-page, and you have
hit on the right worst case: a page spanning example.com and sample.org
only gets to factor out "http://". _bt_prefix_choose() picks the single
longest prefix common to all data items on the page, so a page
straddling two groups keeps only what both share.

Two things soften it in practice but don't remove it: the keys are
sorted, so a straddling page is the boundary page between two runs. Most
pages sit entirely inside one run and get the full prefix. Also a page
that compresses poorly is simply left uncompressed (the int control in
the v4 numbers), so a bad straddle costs nothing rather than bloating.

The actual fix is multiple prefixes per page (a small prefix directory,
each data item pointing at its group's prefix), which is a natural v2 of
the on-disk format and also what would make the multi-column case in (2)
fall out.

I deliberately kept v4 to one prefix to get the format and the
WAL/replay story reviewed before adding that complexity. I think it's
the right thing to consider building next if the basic version is judged
commit-worthy, at minimum to benchmark it and see if it makes a
difference or not.

Here's a wild idea for another day: if the zstd-dict thread [1] lands or
the work from the thread started by Hannu [2] I might give adding
dictionary-based compression to the prefix compression algorithm and
measure that. Who knows...

I'll fold the read-side numbers into the next revision and prototype the
skip-decode path.

Thanks again, these were the right questions.

best.

-greg

[1] https://postgr.es/m/CAMT0RQQ+7bhiM9FtrZ7cdWxxFR=jtQCq6poDPs75oJuGMDdPKg@mail.gmail.com
[2] https://postgr.es/m/CAMT0RQQtJprWKdK4L_wsD++aQaQ972kRdGfGA+su3JfFdYuEmA@mail.gmail.com