Re: nbtree: opt-in leaf key prefix compression

On Tuesday, November 3rd, 2026 at 4:48 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:

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

Hey Peter,

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

Excellent, I think we've talked about this idea a few times in person. The
reason for my interest is related to my "HOT for Expression Indexes" patch
where I am trying to make it possible for JSONB updates in heap to be HOT.
Today that isn't possible because all indexes on JSONB are expressions and
expression indexes spoil HOT.

At that time I noted that it is very common with JSONB data to index using
nbtree far too many fields in a JSONB document. This is an especially easy
trap for people coming from a MongoDB background, which has been a trend
since JSONB was introduced (and likely a big part of the justification for
that type).

These JSONB paths are highly prefix-compressible and I don't imagine that
JSONB will be removed from core anytime soon, so I thought I'd take a
shot at improving that use case.

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

It is a new "age" and we're all adapting to it. I've been doing software
development for 35 years now and this is, hands down, the biggest shift
I've seen for this profession. Everyone will have to adjust to the new
norm once the dust settles, but we're not even at that stage yet.

Thanks for digging your patch out and dusting it off so that I could take
a look and run a comparison. Two differences jump out.

Composing with deduplication was a hard requirement for my work with
Claude.

The varlena-first-column restriction was an efficiency choice early on
that got lost in the process and should have been dropped a while ago.

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

Absolutely true, Claude can prototype just about anything quickly and
sometimes quite well. Feed it a problem, answer some questions and
wait while it burns a hole in your wallet.

I too am confused, but in this case a valuable feature (key-prefix
compression) can be worked out in a few weeks, not years, and deliver
a feature that many will benefit from.

But on this thread I think I let the LLM do the talking about the patch
instead of presenting this idea/work to the hacker community on its
merits.

I own that, it was the wrong order and your mail is a reasonable
reaction to it. But let's not lose sight of the fact that this idea
provides value to users of nbtree, I hope that you agree on that point.

While I'm owning things... you asked what src/backend/access/bark/
barkutils.c is. It's nothing that should be in this patch. BARK is a
separate index AM I've been working on out of tree; this code started
as a port of its leaf prefix coding, and two stale comments pointing
back at that file rode along. They reference a file that doesn't exist
in the tree, which is just confusing. Apologies.

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

You're right that the vibe-coded prototype patch shouldn't have led the
thread. Focusing on technical merit rather than process, the efficacy
here isn't in doubt. So the question isn't whether prefix compression
earns its place, it's whether this design is the right shape for it.

That's the conversation I want, along with code to demonstrate, test,
and evolve the idea into something we feel can be committed.

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

Yes, agreed. It's an obvious improvement that, like all things, has
trade-offs one of which is additional code complexity. But how is this
any different from other optimizations?

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

Fair point, can we rewind time a bit and do that now?

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

HEAVILY, they use nbtree nearly exclusively and you have to understand
that many are coming (as I said before) from MongoDB to Postgres where
it was standard operating procedure to have 10s, even 100s of indexed
fields within a particular document shape. Worse yet, sometimes when
mapping MongoDB-shaped use onto Postgres (as the open source documentdb
project does) there is a need for additional indexes beyond what the
user specified to enable a similar experience.

But you're right, I should have led with the problem. Talked over the
trade-offs and goals. Then prototype a solution. I skipped some steps.

Another use case is plain text/bytea keys with a long shared prefixes
such as URLs, reverse-DNS names, file paths, tenant-prefixed natural
keys, and the like.

Those are ordinary btree indexes today and the redundancy is obvious.
Most/all of these cases can easily be tested and I'll bet that the floor
for the compression is about 3x if we measured.

JSONB specifically, what I had in mind is a btree on an expression that
pulls a text path out of a document (btree on (doc->>'...'), or on a
materialized path column), not a GIN index.

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

Column-level compression is a great technique, and I'd like to see that
happen too. The time line for that is much longer primarily due to the
many ways that table/index/executor all implicitly agree on one shape
and one behavior defined by heap. If we can more cleanly separate and
define the boundaries between those three then we could potentially see
that in core at some point, but I'll bet that takes a few years to sort
out. In the mean time, let's compress some key prefixes and save some
bytes.

I think these two are not in competition, they are orthogonal and both
is the answer but the easier of the two in today's code base is the
prefix compression.

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

You've read it correctly this is the "actual keys currently held in
the node" variant, not the "key range from separator keys" one. The
per-page PREFIX item is the longest common byte prefix of the data
items that were on the page when it was written as a whole. It is not
derived from, and does not act as, a low key, and the parent/separator
keys are untouched.

Why that side of the taxonomy? The separator-key variant is the more
principled one IMO, it ties the compressible prefix to the page's key
space, so it's stable under inserts and composes with suffix truncation
but it's also the more invasive one. It wants the prefix to be a real
boundary key, which means the split and the downlink and _bt_compare
all have to understand it, and that's a much deeper change to nbtree
code than a per-page item that only the leaf read/write path knows
about.

The "actual keys held" variant buys most of the space win for a change
that stays inside the leaf. That was the trade I made that should have
been presented and discussed first is what I'm hearing from you. It's
the one worth arguing about. I made this decision for containment, not
because the separator-key variant is wrong.

> 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've got the right idea, a later insert whose first column doesn't
share the page's prefix is stored uncoded, in place, next to coded
neighbors (the coded length byte distinguishes them per tuple, so a page
is a mix). No decode-time ambiguity, no rewrite on insert.

Why is this generally okay? Good question, and there are places where
it might not be.

In my estimation, it is okay (read: the right choice) because the base
key is the common prefix of a sorted run, and btree order means the
tuples that share it are contiguous, so an insert landing in the page's
key space usually *does* share the prefix and so the page stays mostly
coded.

The case where it degrades is a page straddling a prefix boundary. The
http://example.com / http://sample.org example from Yao's branch of the
thread is a case where the base key collapses to the short common run and
the page compresses poorly. That's a genuine limitation of one prefix
per page. It's the same root cause as the multiple-prefixes-per-page
idea, I'm open to a format that could carry more than one base key per
page. This design trade-off was a simplification, not a requirement.

For now the answer is that the page is recompressed to the better base
the next time it's written as a whole (a split or a dedup pass), so a
straddling page is transient rather than permanent, and in the worst
case it's simply a plain page, never worse than today.

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

Agreed that split-availability is the real low-level question and WAL is
downstream of it. I'm pleased with the guarantee the representation
gives, I think it's one of the strongest parts of the design. I should
have presented this earlier on the thread rather than burying it under
the WAL text, another example of your point which is that a healthy
thread on a feature such as this starts with design discussion, not a
functional vibe-coded patch prototype. So here's that idea written up
for discussion:

A prefix page never holds more logical data than a plain page would: a
coded tuple is never larger than the plain one (coding only kicks in
when at least BTREE_PREFIX_MIN_SHARED bytes are shared, and it replaces
those with a single code byte), and any tuple can always be stored
uncoded. So any split point that is legal for a plain page is legal for
a prefix page, and the split chooser's existing leftfree/rightfree
feasibility still holds. The one thing coding changes is that a prefix
page can hold *more* tuples than a plain page, which is why the split
accounting is in coded bytes but that only ever makes more split points
feasible, never fewer.

The degenerate guard you can see in _bt_recsplitloc() exists for exactly
one coded-size artifact (a point that leaves the left page with zero
data items, which plain-size accounting rejects on its own), and the
forced-full-page-image fallback is the belt-and-suspenders for the one
case redo can't rebuild from logged plain items. There is no page a
prefix index can reach that a plain split can't resolve, because
"store it uncoded" is always available as the floor.

If that guarantee has a hole in it, that's the thing I most want found,
so please push on it.

The short version, I'll re-send with the architecture-first framing, the
string-key motivation instead of the JSONB lead, the bark comments gone,
and the split-availability argument up front where it belongs.

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

As stated earlier, the first iteration of this key prefix compression was
in the context of a separate vibe-coded exploration I'm doing. BARK is
the best name I could come up with that had B and "tree" combined into a
short word (CREATE INDEX using BARK). I'll do the clean up, sorry for
the confusion.

> --
> Peter Geoghegan

best.

-greg