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, I wanted to follow-up again on a suggestion you made.

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

This is a good idea and if I dismissed it earlier I apologize. But it
will be tricky to do. Each column used to form a key may need a
different key prefix, or maybe more than one can share a key prefix on a
page.

I'll have to think about this and do some research to find out how this
has been approached by other databases in the past.

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

I have not, in that case you'd ideally like multiple prefixes for the
same column. Then you have a different set of issues to manage, which
prefix belongs to a tuple? I'll have to dig on this one too.

> Curious to hear your thoughts.
>
> --
> Yao Feng

thanks for the ideas,

-greg