From: Greg Burd <greg@burd.me>
To: fengyao0087@gmail.com
Cc: pgsql-hackers@lists.postgresql.org
Cc: pg@bowt.ie
Subject: Re: nbtree: opt-in leaf key prefix compression
Date: Wed, 04 Nov 2026 18:08:07 +0000
Message-ID: <autsFaeXkMImMsY5@floki> (raw)
In-Reply-To: <CAAU0Mh1X95Ou7fDUxGVtFq5-HSd9wdfDH_8kR0s=RiTUf_9U6w@mail.gmail.com>
References: <at-01F1wsXLRH0qo@floki>
<iMzeiKz_iFUwu8k8FTdo2CJ1Qp_x7SkvdLxEtYPhM3y_XfFY8mNM1fpSKoWimjR9ZKTz_4XT8BNCYKJWSq9w087DmY29cvnVrmvKCzLplnk=@burd.me>
<y8lIX15Mjse_ALeMMfsK1oakyoxjIU4p2HLHF8sQArBsYgFDvAZz7vVCW26vl6IP7AEMWQArSkqBxvyCa4OKdXe8eiZ6OxqgvIC0FnJEM7c=@burd.me>
<auN2SdTLllCuHksC@floki>
<CAAU0Mh1X95Ou7fDUxGVtFq5-HSd9wdfDH_8kR0s=RiTUf_9U6w@mail.gmail.com>
On Fri, 30 Oct 2026 19:52:00 +0800, Yao Feng <fengyao0087@gmail.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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: greg@burd.me, fengyao0087@gmail.com, pgsql-hackers@lists.postgresql.org, pg@bowt.ie
Subject: Re: nbtree: opt-in leaf key prefix compression
In-Reply-To: <autsFaeXkMImMsY5@floki>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox