Re: nbtree: opt-in leaf key prefix compression

On Mon, Oct 26, 2026 at 4:25 PM Greg Burd <greg(at)burd(dot)me> wrote:
> This is a patch that adds leaf key prefix compression to nbtree, behind
> a new per-index storage parameter, prefix_compression, off by default.
> It's something I started a long time ago when primarily working on
> JSONB-like data storage/indexing/etc. in Postgres when a colleague
> pointed out that it didn't yet exist and his measurements showed that it
> should. He wasn't wrong. It's a solid win for performance and overhead
> IMO, but YMMV.

I also have a vibe-coded patch adding prefix compression to nbtree,
from back in April. I had completely forgotten about it until you
reminded me. I attach it here now.

In the spirit of the age, I also had Claude do a comparative review of
both of our patches. I also attach that here. I skimmed it a bit,
which helped me to remember bits and pieces about the prompt I used
back in April. Apparently my patch doesn't compose with deduplication,
while yours does. On the other hand, your patch cannot handle prefixes
unless the prefix column is of a varlena type. So there are cases
where one performs much better than the other, and vice-versa. That's
what I would have guessed.

> The patch is one commit against master. I'd appreciate review of the
> approach and the code, and I'm happy to work through whatever it turns
> up.

We're now living in a world where the cost of producing a prototype
like this has plummeted. The community's culture hasn't figured out
how to deal with this yet. I personally don't have much of a clue what
to do about it, but I am sure that certain things need to be assessed
very differently now. Generating a patch that, in some technical and
superficial sense, converges on being a complete implementation of
some complicated optimization means very little now.

Posting a huge AI generated patch that nobody will read could still
make sense if there were doubts about the general efficacy of a
particular technique, as a kind of informal proof of its feasibility,
but I don't think that applies here. It's fairly obvious that prefix
compression can cut the storage overhead of indexes by 3x or more in
sympathetic cases, at the cost of CPU overhead for decompression, and
lots of complexity.

The best feedback I can offer is that I think you should have started
with a very high level discussion of the architectural trade-offs. You
said "indexes on keys that share a long leading prefix (URLs,
reverse-DNS names, a leading JSONB path, a tenant-id prefix) spend
most of their bytes storing that prefix over and over", which is
obviously true, but you neglected to mention why you felt that was the
use case to target. Do users actually use nbtree indexes for JSONB
paths? I have to admit that I didn't know that.

It seems likely that a design such as yours, which omits column-level
compression, will never incorporate it later on once committed. Why do
you think that's the best trade-off? I personally tend to doubt that
it is, but I've given it little thought so who knows?

More generally, can you paint a detailed picture of what motivated you
to work on this? I wouldn't expect that kind of background with an
optimization that was an unalloyed good, and required no changes to
the on-disk format. But for something like this, which would commit us
to supporting its compressed representation forever, a detailed
picture of how it affects users is completely essential. A really
solid understanding of the trade-offs and the entire design space is
hugely important.

There are complex trade-offs around whether and to what extent prefix
compression works by compressing things in terms of the index key
space versus on a more ad-hoc basis. As Modern B-Tree Techniques puts
it: "Code simplicity argues for truncating the same prefix from all
entries in a B-tree node. Moreover, one can apply prefix truncation
based on the actual keys currently held in a node or based on the
possible key range as defined by the separator keys in parent (and
possibly other ancestor) pages."

Where does this design fit under his taxonomy? It looks like you're
not relying on the compressed prefix to act like a low key. Why was
that? What's the trade-off around picking a base key from the tuples
present when the page is "written as a whole"? What happens if, later
on, more tuples are inserted that are within the page's key space but
not compressible using its base key? Obviously you just don't compress
those tuples, but why is that generally okay?

You placed a lot of emphasis on your WAL logging strategy, and how
prefix compression needs to work during recovery, but I don't think
that's the place to start. When it comes to lower-level details I'd be
much more concerned about guarantees that a legal page split will
always be available, even in extreme pathological cases. But that's
really a facet of the on-disk representation itself, and the design as
it relates to that.

BTW, what is src/backend/access/bark/barkutils.c?

--
Peter Geoghegan