Date: Wed, 04 Nov 2026 18:08:07 +0000
To: fengyao0087@gmail.com
From: Greg Burd <greg@burd.me>
Cc: pgsql-hackers@lists.postgresql.org, pg@bowt.ie
Subject: Re: nbtree: opt-in leaf key prefix compression
Message-ID: <autsFaeXkMImMsY5@floki>
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>
Feedback-ID: 2668248:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://www.postgresql.org/message-id/autsFaeXkMImMsY5%40floki>
Precedence: bulk

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.
>=20
>  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 co=
st
> tends to be the main bottleneck for queries on modern hardware. Looking a=
t
> the v4 benchmarks, they mostly cover index size and write throughput -- d=
id
> you have a chance to measure read-side performance (e.g. index scans, poi=
nt
> lookups)?
>=20
> A few quick questions from having played with something similar a while
> back:
>=20
> 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 a=
nd
> only care about the heap TID -- such as a plain IndexScan, BitmapIndexSca=
n,
> or COUNT(*) -- could we skip decompression?
>
> 2. Multi-column indexes:
> The patch requires column 0 to be a varlena. I'm curious if you considere=
d
> supporting subsequent columns (e.g. for something like `(tenant_id int, u=
rl
> 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 cas=
e?

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.
>=20
> --=20
> Yao Feng

thanks for the ideas,

-greg