# nbtree leaf prefix compression: two designs compared

Branches compared, both built on the same master base commit:

* `greg-prefix-compression`: one commit, "nbtree: opt-in leaf key prefix
  compression" (Greg Burd).  Per-page byte prefix of the first key column,
  enabled by a reloption.
* `prefix-compression`: three commits, "Add prefix compression to nbtree leaf
  pages", "amcheck: verify prefix-compressed nbtree leaf pages", "pageinspect:
  decode compressed follower TIDs in bt_page_items" (Peter Geoghegan).
  Anchor/follower groups that omit the leading key columns, enabled
  automatically for eligible indexes.

Both branches were read in full, built with assertions, and measured on the
same data (section 9).  Every number below comes from those runs; every
reading-based claim is marked as such.


## 1. Summary

The two designs remove different redundancy, so each wins where the other
does nothing:

| Workload (1M rows)                         | master | greg-prefix-compression | prefix-compression |
|--------------------------------------------|-------:|------------------------:|-------------------:|
| `(url)` 1M distinct 45-byte keys, built    |  8286  |  7544 (leaf density 34%)|  8286 (ineligible) |
| `(url)` same keys, random-order inserts    | 10769  |  3889                   | 10769 (ineligible) |
| `(k, id)` 1000 keys x 1000 rows, built     |  9462  |  8580 (leaf density 42%)|  2796              |
| `(k, id)` same rows, random-order inserts  | 12398  |  4863                   |  3763              |
| `(a, b, c)` int4, built                    |  3853  |  3853 (first col not varlena) | 2865         |
| `(a, b)` int4, 10 rows per key, built      |  1157  |  1157 (deduplicated)    |  2749 (no dedup)   |

Sizes are in 8 KB pages.  The master column is the greg branch with the
reloption off, which leaves nbtree unchanged.

Strongest point of each design:

* greg-prefix-compression: a coded tuple is self-contained given the page
  prefix.  Coding needs no catalog, keeps `t_tid` and posting lists intact,
  never forces a page rewrite on insert or delete, composes with
  deduplication, and is a per-page opt-in with no metapage or version change.
* prefix-compression: a follower has zero bytes of overhead, pages are dense
  from CREATE INDEX on, groups adapt per page ("drift"), and it covers the
  multi-column shape (TPC-C style keys) that the other design cannot touch.

Weakest point of each design:

* greg-prefix-compression: CREATE INDEX does not shrink the index.  A built
  leaf holds one plain page of tuples, then gets coded, so built leaves are
  34-42% full and the page count drops only by the relaxed fillfactor.  The
  no-image split redo is bypassed whenever the on-page compression ratio
  exceeds 2x: in the URL workload 1540 of 1564 splits carried a forced
  full-page image.  Every index-only scan on every btree reserves 144 KB
  instead of 16 KB.
* prefix-compression: it is automatic with no opt-out, it turns off
  deduplication for the whole index and bottom-up deletion for every
  compressed page, so a two-int4-column index with duplicates grows 2.4x
  against master.  Deleting an anchor forces a full-page image at VACUUM or
  simple-deletion time (3.0 MB of images against 0.25 MB of master records
  for a scattered delete of 1/7 of the rows).  The split-time promotion can,
  in principle, fail to fit; the branch says so.


## 2. What is compressed

greg-prefix-compression codes the bytes of the first key column against one
prefix per leaf page.  Requirements: the reloption is on and the first key
column is a varlena (`attlen == -1`).  The prefix is the first data item's
leading bytes, cut to the longest run any later item shares, capped at
`BTREE_PREFIX_MAX` (126) bytes, and taken only when items share at least 4
bytes on average.  Later key columns, INCLUDE columns and posting lists are
moved, not coded.  A key that shares nothing still pays the one-byte share
count.  Deduplicated (posting) tuples are coded too.  Nothing happens for an
int4 first column, or for shared bytes in a second column.

prefix-compression omits the leading `nkeyatts - 1` key columns of a tuple
when they are byte-equal to those of the nearest plain tuple to its left on
the page (the anchor).  Requirements: at least two key columns, every leading
column's opclass equalimage, decided once at build time.  The last key column
is always stored, so `(url, id)` with all-distinct URLs saves nothing (every
tuple is its own anchor), and `(customer_id, url)` saves only the int4.  A
single-column index is never eligible.

Neither design handles shared bytes of a non-first column, or a shared prefix
of distinct values in a leading column.  On `(k, id)` with repeated `k` both
apply, but not equally.  A follower is 16 bytes against a 64-byte anchor.  The
coded tuple is 24 bytes, because the catalog-free coding keeps the trailing
`id` at its original alignment phase and pads to get there; on `(url)` alone a
coded tuple is 16 bytes against 56 plain.  That padding, not per-group
adaptivity, is most of the 4863 against 3763 page gap for the insert-grown
`(k, id)` index.

The equalimage gate on prefix-compression is required, not conservative: a
plain tuple inserted inside a group becomes the anchor of the followers after
it.  Sort order makes its leading columns opclass-equal to theirs; equalimage
makes them byte-equal, which is what inheritance needs.  greg-prefix-
compression has no opclass dependency because each coded tuple records its
own share count against an immutable page prefix and decodes byte for byte.


## 3. On-disk representation

| Aspect                   | greg-prefix-compression                                   | prefix-compression                                          |
|--------------------------|-----------------------------------------------------------|-------------------------------------------------------------|
| Page flag                | `BTP_PREFIX` (1 << 9), per page                           | `BTP_HAS_PREFIX_COMPRESSION` (1 << 9), every leaf of the index |
| Metapage                 | unchanged                                                 | new `btm_prefix_compression`, carried in `xl_btree_metadata` |
| Extra items              | one PREFIX item at `P_HIKEY`/`P_FIRSTKEY`; `P_FIRSTDATAKEY` shifts by one | none                                           |
| Tuple marking            | none; first column's payload starts with a share count    | `INDEX_ALT_TID_MASK` + `BT_IS_COMPRESSED` (0x4000) in `t_tid` |
| `t_tid` of a data tuple  | intact                                                    | heap offset packed in the low 12 bits; `BTreeTupleGetHeapTID` returns NULL |
| Per-tuple overhead       | 1 byte count (+ varlena header recomputed)                | 0 bytes                                                     |
| Random access to a tuple | O(tuple) decode from the page prefix                      | O(group length) walk left to the anchor, then deform/form   |
| Pivots, high keys        | plain                                                     | plain                                                       |
| NULL in the coded column | stored plain                                              | NULL leading columns can be shared                          |
| Posting lists            | allowed, coded                                            | forbidden on the whole index                                |
| Status bits consumed     | none                                                      | one of the two remaining `t_tid` status bits                |
| Version bump             | none                                                      | none                                                        |

The PREFIX item is a non-tuple in the line pointer array.  Everything that
walks items must know about it: `P_FIRSTDATAKEY`, the "emptied leaf holds
only its high key" test in page deletion (handled by dropping the item), and
all external tools.  The follower representation keeps every item a real
tuple, in the style of posting lists, but at the cost of a status bit and of
a `t_tid` that no longer is a heap TID.

Neither design bumps `BTREE_VERSION`.  An older binary cannot detect either
format: it would read the PREFIX item as a data tuple, or classify a follower
as a pivot.  Both branches only ever write the new format from the new
binary, so this matters for downgrade only.  The greg reloption changes only later
whole-page writes, so `ALTER INDEX ... SET` takes `ShareUpdateExclusiveLock`.


## 4. Readers

greg-prefix-compression routes every read of a leaf data item through
`_bt_getitem()`, which decodes into a caller-supplied `BTItemBuf` (a
`PGAlignedBlock`, 8 KB).  On a page without the flag the cost is one
predictable branch.  On a coded page every item read is a copy: header,
prefix bytes, suffix, rest of the tuple.  `_bt_compare` carries an 8 KB stack
buffer and decodes on every probe of a coded page.  Heap TIDs, posting lists
and `BTreeTupleIsPosting` work on the raw item, so `_bt_killitems`, the
VACUUM callback, simple deletion, bottom-up deletion and unique checking
read TIDs without decoding; only key comparisons decode.  The array-key
look-ahead decodes the look-ahead tuple.

prefix-compression reconstructs a follower by deforming the anchor (cached per
page in `BTPrefixPageState`), deforming the follower with a trailing-columns
`TupleDesc`, and calling `index_form_tuple`.  Costs as written:

* `_bt_compare` on a follower: `palloc` of a scratch tuple, a fresh
  `BTPrefixPageState`, a leftward walk to the anchor, a `TupleDesc` built with
  `CreateTemplateTupleDesc` and freed again, two `index_deform_tuple` calls and
  one `index_form_tuple` (another `palloc`).  This runs for every binary-search
  probe that lands on a follower, so a descent into a one-group page does this
  about `log2(n)` times and walks about `n/2` items per probe.
* `_bt_readpage`: one `TupleDesc` and one scratch buffer per page, one
  deform/form per follower.
* `_bt_insertonpg`: builds and frees a `TupleDesc` per compressed insert.

Every consumer of a follower's `t_tid` had to be patched: `_bt_check_unique`,
`_bt_killitems`, `btvacuumpage`, `_bt_simpledel_pass`,
`_bt_bottomupdel_finish_pending`, `_bt_delitems_delete_check`,
`_bt_afternewitemoff`, amcheck and pageinspect.  A missed consumer reads a
heap offset with bit 0x4000 set.  In the other design a missed decode site
reads a wrong key, which comparisons catch, never a wrong TID.

Index-only scans: greg-prefix-compression sizes `currTuples`/`markTuples` with
`BTTupleStorageSize`, 73,728 bytes each, for every btree index regardless of
the reloption, because a `BTP_PREFIX` page can outlive `ALTER INDEX ... SET
(prefix_compression = off)`.  That is 144 KB per index-only scan against 16 KB
on master.  prefix-compression starts at 8 KB per buffer and grows with
`repalloc` on demand.

The array-key look-ahead optimization is kept (with decode) on one branch and
disabled on compressed pages on the other.


## 5. Writers: build, insert, split

CREATE INDEX.  greg-prefix-compression fills each leaf with plain tuples, then
`_bt_prefix_compress_page()` rewrites the finished page in place.  The
fillfactor test is relaxed by the predicted saving, but the hard fit test is
not, so a built leaf never holds more than one plain page of tuples.  This is
why built indexes come out at 34-42% leaf density and only 9% fewer pages.
The savings appear only after retail inserts fill the free space, or after a
split re-lays the halves.  prefix-compression emits followers inside
`_bt_buildadd`, so a built leaf is 90% full of compressed tuples (2796 pages
against 9462 for `(k, id)`).

Retail insert.  greg-prefix-compression encodes the new tuple against the
page's fixed prefix (one `palloc`), sizes the fit test by the coded size, and
logs the coded bytes.  A posting-list split on a coded page replaces the
posting tuple in place and forces a full-page image.  prefix-compression
finds the anchor by walking left from the insert position, compresses the
tuple if its leading columns match, and logs the follower bytes verbatim.  A
tuple that does not match is inserted plain and starts a new group; the old
anchor to its right stays plain.

Page split.  greg-prefix-compression rebuilds both leaf halves as whole
pages: `_bt_split_leaf_collect()` decodes the original page into plain item
arrays, `_bt_split_leaf_half()` chooses a prefix for each half and lays it out
through `_bt_split_leaf_layout()`, trying the half's own prefix, then none,
then the original page's prefix, and raising ERROR if none fits.  The split
point chooser works in on-page (coded) bytes.  prefix-compression keeps
`_bt_split()` nearly unchanged: if the split lands inside a group it
reconstructs `firstright` into plain form so the right page starts with an
anchor, and reconstructs `lastleft` for suffix truncation.  The split point
chooser reconstructs candidate boundary tuples for `_bt_keep_natts_fast()`,
and the uniform-tuple-size gate in `_bt_afternewitemoff()` is disabled with
`#if 0`.

Both branches have an unproven "the split layout fits" argument, and both
fail with ERROR before the critical section (the new right page is leaked,
nothing is corrupted):

* prefix-compression says so: `nbtsplitloc.c` does not reserve the growth of
  promoting `firstright`, which is the size of the omitted leading columns.
* greg-prefix-compression claims the original prefix "fits by construction",
  but (reading) `_bt_recsplitloc()` charges the left page's new high key at
  `firstrightsz`, the coded on-page size, while the high key is formed from
  the decoded tuple.  Suffix truncation never cuts inside a column, so for a
  single-column index the plain high key can exceed that estimate by up to
  the shared byte count, at most `BTREE_PREFIX_MAX` plus alignment.  The
  default split strategy leaves far more slack than that; the fillfactor
  strategies leave less.  Several thousand splits in the measurements raised
  no error.


## 6. VACUUM and deletion

greg-prefix-compression needs nothing on delete: items are independent.  The
only rewrite is dropping the PREFIX item when a leaf empties, so page
deletion still sees a page that holds only its high key.

prefix-compression must promote the first surviving follower when its anchor
is deleted.  `_bt_prefix_vacuum_plan()` reconstructs the survivors outside the
critical section, `_bt_prefix_vacuum_apply()` overwrites them in place after
`PageIndexMultiDelete()` inside it, and PANICs if the overwrite fails.  The
space argument (the deleted anchor is at least as large as the growth) reads
correctly.  The page is then logged as a forced full-page image, in both
`_bt_delitems_vacuum()` and `_bt_delitems_delete()`, so simple deletion during
inserts pays it too.


## 7. Deduplication and bottom-up deletion

greg-prefix-compression composes with both.  A build deduplicates and then
codes.  A runtime `_bt_dedup_pass()` on a coded page decodes every item, lays
the deduplicated result out plain, and re-codes it; because a coded page can
hold more logical data than fits plain, the pass may overflow, in which case
it aborts cleanly and the page splits instead.  Bottom-up deletion decodes
for key comparisons and removes items without rewriting survivors.

prefix-compression makes the two mutually exclusive per index
(`btm_prefix_compression` implies `!btm_allequalimage`), asserts no
compressed page ever reaches `_bt_dedup_pass()`, and skips bottom-up deletion
on compressed pages because `_bt_keep_natts_fast()` cannot take followers.
Because the opt-in is automatic, every multi-column index whose leading
columns are equalimage loses both mechanisms with no way back.  The
`select_distinct` expected output changed for that reason (a parallel worker
count flipped because `distinct_tbl`'s index is no longer deduplicated).  For
`(a, b)` int4 with ten rows per key the index is 2749 pages against 1157 on
master, and two-int4-column followers save nothing at all after MAXALIGN
(8 + 4 bytes rounds to 16, the same as 8 + 8).


## 8. WAL and redo

greg-prefix-compression:

* Insert: the coded tuple, replayed verbatim by the existing insert redo.
* Split: `XLH_SPLIT_LEAFPREFIX`.  The record carries each half's chosen
  prefix, the left high key and new item, and the right half's plain items.
  Redo re-derives the left half from the pre-split page with the same
  collect/layout routines the primary used, so the coded pages come out byte
  for byte without an image.  When the right half's plain payload exceeds
  `BLCKSZ`, `XLH_SPLIT_RFPI` carries the coded right page as a forced image.
  That threshold is crossed whenever the coded page holds more than two plain
  pages of items, i.e. whenever the compression ratio exceeds 2x.  In the
  URL workload 1540 of 1564 splits took the image path.
* Deduplication of a coded page: the chosen prefix plus the deduplicated
  plain items, a page's worth, with the same `BLCKSZ` image fallback.  Master
  logs only the intervals.
* VACUUM: unchanged, plus dropping the PREFIX item on an emptied leaf.
* Adds about 300 lines to `nbtxlog.c`, including a second split-redo path
  that duplicates the sibling-link fix-up.

prefix-compression:

* Insert and split: follower bytes travel verbatim; `xl_btree_split` gains
  `origflags` so replay carries the page flag to both halves; `_bt_restore_page`
  needs no change.
* New root: replay reads the metadata block to set the flag.
* VACUUM and simple deletion with a promotion: forced full-page image.
* `xl_btree_metadata` gains the opt-in flag.

Neither branch updates `nbtdesc.c`, so `pg_waldump` shows none of the new
fields.


## 9. Measurements

Setup: both branch tips built with `-Dcassert=true -Dinjection_points=true`,
one cluster each (`shared_buffers=512MB`, `fsync=off`,
`max_parallel_maintenance_workers=0`).  The master column is the greg branch
with the reloption off.  Every index passed `bt_index_parent_check(...,
true, true)` afterwards; index-scan, index-only-scan, backward, array-key and
merge-join (mark/restore) probes matched sequential-scan digests on both
branches.  Scripts and raw output:
`/mnt/nvme/postgresql/patch/claude_work/pcmp-rig/`.

Index size in pages, 1M rows, 45-byte URL keys where text is involved:

| Index                                           | master | greg on       | pc             |
|-------------------------------------------------|-------:|--------------:|---------------:|
| `(url)` distinct, CREATE INDEX                  |  8286  | 7544 (34.4%)  | 8286           |
| `(url, id)` distinct, CREATE INDEX              |  9449  | 8567 (42.1%)  | 9449 (90.0%)   |
| `(k)` 1000 keys x 1000, CREATE INDEX            |   902  |  902 (86.8%)  |  902           |
| `(k, id)` 1000 keys x 1000, CREATE INDEX        |  9462  | 8580 (42.1%)  | 2796 (90.5%)   |
| `(a, b, c)` int4, CREATE INDEX                  |  3853  | 3853          | 2865 (90.0%)   |
| `(a, b)` int4, 10 per key, CREATE INDEX         |  1157  | 1157          | 2749 (90.1%)   |
| `(url)` distinct, random-order inserts          | 10769 (69.8%) | 3889 (65.3%) | 10769   |
| `(url)` distinct, key-order inserts             |  8354 (89.8%) | 2764 (91.2%) | 8354    |
| `(k, id)` 1000 x 1000, random-order inserts     | 12398 (69.1%) | 4863 (73.0%) | 3763 (69.2%) |
| `(a, b, c)` int4, random-order inserts          |  4786 (72.3%) | 4786         | 4117 (67.2%) |

Percentages are `pgstatindex` leaf density.  A `pc` entry equal to master
means the index was ineligible or gained nothing.

btree WAL for 300k random-order inserts into `(k, id)` (1000 keys), with
`full_page_writes=off` so only each design's own records count, from
`pg_waldump --stats` restricted to the btree rmgr:

| Record        | master              | greg on                                   | pc                 |
|---------------|--------------------:|------------------------------------------:|-------------------:|
| INSERT_LEAF   | 33.2 MB / 296,292   | 21.5 MB / 298,456                         | 19.4 MB / 298,886  |
| SPLIT_L + R   | 15.3 MB / 3,751     | 6.8 MB / 1,564, of which 6.4 MB images    | 4.1 MB / 1,125     |
| Total         | 48.9 MB             | 28.5 MB                                   | 23.6 MB            |

btree WAL for DELETE of every seventh row (anchors and followers alike) plus
VACUUM, on those indexes:

| master                 | greg on               | pc                                        |
|-----------------------:|----------------------:|------------------------------------------:|
| 246 KB / 3,373 records | 148 KB / 1,419 records | 3.07 MB / 1,082 records, 2.98 MB images  |

A delete that removed whole key runs (every tenth key) never deleted an
anchor with survivors, and cost 138 KB / 92 KB / 75 KB respectively.

btree WAL for 300k random-order inserts of 100 distinct keys into a
single-column index (deduplication active; prefix-compression is ineligible):

| Record      | master              | greg on             |
|-------------|--------------------:|--------------------:|
| INSERT_LEAF | 31.2 MB             | 19.2 MB             |
| DEDUP       | 0.6 MB / 10,355     | 14.8 MB / 2,276     |
| Total       | 32.3 MB             | 34.7 MB             |

Both end at 305 pages.  On a duplicate-heavy key the option adds WAL and CPU
and saves nothing, because deduplication already removed the key redundancy.


## 10. Gaps and risks found while reading

greg-prefix-compression:

* Built indexes are sparse (section 5).  The fix is to code during the build,
  as the other branch does, or to re-run the page finish against the coded
  layout.
* The no-image split redo is the uncommon path for the data the feature
  targets (section 8).  The bound is still `BLCKSZ`, so volume is fine, but
  the elaborate redo path mostly does not run, and the commit message's claim
  that realistic data never reaches the fallback is wrong.
* 144 KB per index-only scan on every btree (section 4).  A smaller bound, or
  growth on demand, would remove the cost from indexes that never use the
  option.
* The left high key is under-charged in the split point chooser (section 5).
* A posting-list split on a coded page forces an image on every such insert.
  Posting-list splits are not rare on tables whose heap TIDs are reused after
  VACUUM.
* `pageinspect` is not taught the format: `bt_page_items` shows the PREFIX
  item as a tuple with ctid `(0,0)` and the coded bytes as the key.
* The file comment says the design is modeled on
  `src/backend/access/bark/barkutils.c`, which is not in the tree.
* No change to `nbtdesc.c`, so the new split and dedup fields are invisible
  in `pg_waldump`.

prefix-compression:

* Automatic opt-in with no reloption and no opt-out, and deduplication plus
  bottom-up deletion gone for every eligible index (section 7).  This is a
  regression against master for any multi-column index with duplicates or
  with non-HOT update churn, and it is undocumented.
* The split-time promotion fit is open; the commit message says so.
* `t_tid` bit-stealing: nine consumers patched by hand; `BTreeTupleGetHeapTID`
  returns NULL for a follower and `BTreeTupleGetMaxHeapTID` returns the masked
  pointer, so any new caller must know.
* Per-probe `TupleDesc` construction and `palloc` in `_bt_compare`, and an
  O(group) anchor walk per probe (section 4).  A relcache-cached trailing
  `TupleDesc` and a direct byte-splice reconstruction would remove most of
  it.
* Full-page image per promotion (section 6), on VACUUM and on simple
  deletion.
* The uniform-tuple-size gate in `_bt_afternewitemoff()` is disabled for all
  indexes with `#if 0`, not only for compressed pages.
* Tests: one regression file, no amcheck or pageinspect test, no WAL
  consistency run mentioned.  No user documentation.
* No change to `nbtdesc.c`.


## 11. What a combined design could take from each

* From prefix-compression: coding during CREATE INDEX, so built pages are
  dense; zero-overhead followers; per-group adaptivity within a page.
* From greg-prefix-compression: a self-contained coded tuple (no dependence
  on a neighbor item, no rewrite on delete, `t_tid` intact, catalog-free
  decode usable by redo and amcheck); a reloption that is off by default and
  takes a weak lock; coexistence with posting lists.
* Both branches should settle the split-fit argument in `nbtsplitloc.c`
  rather than in the layout fallback, and both need `nbtdesc.c` and
  `pageinspect` support.
* A byte-prefix scheme that covers the concatenated leading key columns
  (type-aware, so that an int4 first column and a shared varlena second
  column both benefit) would cover the union of the two target workloads
  with the per-page prefix mechanics of the greg branch.