Re: nbtree: opt-in leaf key prefix compression

On Tuesday, November 10th, 2026 at 12:01 AM, Yao Feng <fengyao0087(at)gmail(dot)com> wrote:

> Hello,
>
> Thanks for v9, Greg.

Hello Yao, you're welcome I appreciate your help on this thread. I can
tell that you've given it a good deal of thought.

> I went through the patch and have a couple of thoughts on prefix
> selection and the on-disk layout.

Thanks, both of these are good catches.

> 1. Prefix selection: greedy byte-level vs. specifying columns
>
> In _bt_prefix_choose_groups(), a new group only starts when shared_len
> == 0 against the current anchor. On composite indexes where leading
> fixed-width columns are low-cardinality and a later varlena column has
> long prefixes, this greedy check can get stuck in a bad grouping.
>
> For instance, take (tenant_id int4, status int2, order_url text) [...]
> Because shared_len == 6 > 0, row 2 joins group 0 instead of starting a
> new group. [...] the entire page gets locked to row 1's anchor.

You're right. An index on (tenant_id, status, url) where each page
starts with one odd short URL followed by a long run that shares a long
prefix among itself did not compress at all, because the whole run
stayed anchored to the odd first row's 6-byte prefix.

The rule is now that a new group also starts when a tuple shares
strictly more with its immediate predecessor than with the current
anchor, by at least one MAXALIGN quantum. The predecessor is already
the better anchor for the run, so the run breaks off into its own group.
The rule looks only backwards, which keeps the CREATE INDEX size
estimate exact (it has to make the same grouping decisions one tuple at
a time as the real layout does, or the build misjudges when a page is
full).

On your shape it's the difference between no compression and about half
the size. A single-tenant leaf (one odd URL + 150 shop URLs) goes from
1.00x to 0.50x; a mixed table (100 tenants, a few api URLs and many shop
URLs each) from 119 to 68 pages. There's a regression test for it now
(btree_index.sql, "groups_compress").

> On the other hand, fixing the column count like Oracle's COMPRESS N has
> its own problems [...] Both extremes have clear downsides. How should
> we think about the trade-off between explicit column selection and a
> dynamic/greedy approach?

I'd keep it dynamic. A fixed column count has the two problems you name
(skewed data makes too many tiny prefixes, and it can't share inside a
column, which is most of the URL/JSONB win), and it needs the user to
know their data's shape up front. The byte-level rule adapts per page
with no knob. I'm a big fan of keeping the number of knobs low so there
are fewer foot-guns.

If a real workload later wants to force or cap the prefix, a
COMPRESS-N-style hint could be added as a reloption on top, but I'd
rather not add that.

> 2. On-disk layout and the 6-byte header overhead
>
> [...] the 6-byte BTPrefixCode combined with 8-byte MAXALIGN eats up the
> savings on small leading columns [...] Also, because retail inserts
> can't add new anchors to the directory, an inserted key that shares 0
> bytes with its neighbor ends up storing the full key plus the 6-byte
> header.

Both true. MAXALIGN is the bigger cost of the two: a coded item is
still a PageAddItem item, so even a 3-byte header wouldn't help a short
key that's already padded up to the next 8 bytes. The header itself can
shrink (the group number is one byte on any realistic page, and I think
the original t_info can be derived rather than stored), but that only
pays off once items are packed without alignment, which is the open
question from my last mail. Coded items are only ever copied out, never
read in place, so packing them is possible; it just means placing them
by hand instead of through PageAddItem.

The non-sharing retail insert is the honest wart. Today such a tuple is
stored coded against its neighbor's group with shared=0, so it's the
full key plus the header: larger than plain. It's transient (the next
whole-page write regroups the page), and the worthwhile check keeps a
page from going coded in the first place unless it saves overall, but on
an already-coded page a single odd insert does cost those few bytes. An
insert could instead append a new anchor to the directory; redo can
repeat that deterministically, it's just more WAL and more code, so I've
left it for now.

> For what it's worth, here is another page layout I tried earlier in
> bpcauto that avoids per-tuple headers: [prefix zone / suffix zone, with
> prefix tuples' t_tid.ip_posid pointing at the suffix range]

I like that it drops the per-tuple header, and holding the prefixes as
ordinary IndexTuples is clean. The reason I went the other way is the
maintenance cost of the zone offsets.

With a prefix zone addressed by line-pointer ranges, every retail insert
and every VACUUM that adds or removes a line pointer shifts the suffix
offsets, so the prefix tuples' stored ranges have to be rewritten, and
redo has to repeat that.

A per-tuple group number costs 2 bytes but survives line-pointer motion
untouched, which is what lets the coded page compose with deduplication,
bottom-up deletion and posting-list splits without any of them knowing
about prefixes. It also needs the count K in BTPageOpaqueData as you
note, which is an on-disk change I was trying to avoid.

So it's a real trade: your layout is denser per page, mine is cheaper to
maintain in place. For a feature whose main use is write-heavy
JSONB/URL indexes I leaned toward the maintenance side, but I don't
think either is obviously right, and it's worth having both sketched on
the thread.

v10 also fixes two things cfbot found in v9 (an unused helper that only
clang's -Werror flagged, and a recovery test that needed a replication
slot). Same design otherwise.

best.

-greg