Re: nbtree: opt-in leaf key prefix compression

Hello,

Thanks for v9, Greg.

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

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) where 50
rows
on a page all share (1001, 1). If row 1 is 'http://api.site.com/login' (25
bytes) and rows 2..50 are 'https://shop.com/pay/0001..0049' (29 bytes):
- Row 2 shares the 6 leading integer bytes with row 1, then stops at the
1-byte
varlena length header of order_url (since 25 != 29).
- Because shared_len == 6 > 0, row 2 joins group 0 instead of starting a new
group.
- Rows 3..50 also share those 6 integer bytes with row 1, so the entire page
gets locked to row 1's anchor.
- As a result, we miss the 22-byte prefix (1-byte varlena header plus
'https://shop.com/pay/') that rows 2..50 actually share with one another.

On the other hand, fixing the column count like Oracle's COMPRESS N has its
own
problems: it can bloat pages that cross key boundaries or have skewed data
(creating too many prefix tuples), and it cannot compress substrings inside
a
single text column at all.

Both extremes have clear downsides. How should we think about the trade-off
between explicit column selection and a dynamic/greedy approach?

> Open questions
> ...
> - Short keys. Packing coded items unaligned would let phone numbers,
> SSNs and similar keys compress, at the price of placing items by
> hand rather than through PageAddItem. Worth it?
> ...

2. On-disk layout and the 6-byte header overhead

As your benchmarks showed on (tenant_id, bigint, ts) and short keys, the
6-byte
BTPrefixCode combined with 8-byte MAXALIGN eats up the savings on small
leading
columns (for example, on (int4, int8, ts), saving 8 bytes of int4 plus
padding
leaves 16 residual bytes + 14B header = 30B, which MAXALIGN rounds right
back
to 32B). 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.

For what it's worth, here is another page layout I tried earlier in bpcauto
that avoids per-tuple headers:

+-----------------------------------------------------------------------+
| PageHeaderData |
+-----------------------------------------------------------------------+
| ItemId(1) -> [High Key] |
| ItemId(2..K+1) -> [Prefix Zone pointers] |
| ItemId(K+2..N) -> [Suffix Zone pointers] |
+-----------------------------------------------------------------------+
| ... Free Space ... |
+-----------------------------------------------------------------------+
| High Key : IndexTuple { ... } |
| Prefix Tuples : IndexTuple { t_tid.ip_posid = suffix offset, prefix } |
| Suffix Tuples : IndexTuple { t_tid = genuine Heap TID, suffix attrs } |
+-----------------------------------------------------------------------+
| Special Space (BTPageOpaqueData) |
+-----------------------------------------------------------------------+

Instead of a directory item and per-tuple headers, the page is split into a
prefix zone and a suffix zone:
- Prefix tuples sit at the start of the page as normal IndexTuples holding
only
the prefix columns. Since they don't point to the heap, t_tid.ip_posid in
the IndexTuple header stores the starting offset of the matching
contiguous
suffix range.
- Suffix tuples sit after them holding only the remaining columns, with
their
normal Heap TID in t_tid and no extra header bytes at all (just the
standard
8-byte IndexTupleData).

The downside is that the page needs a field (e.g. in BTPageOpaqueData) to
track the prefix count K so readers know where the suffix zone starts, which
changes the on-disk page structure, unlike your directory item approach.

Sharing this as another data point while weighing whether the 6-byte coded
header (or packing unaligned items) is the right trade-off here.

Curious to hear your thoughts.

Regards,
Yao