Denser TID packing for posting sparsemaps (implemented in 4.4.0)

Problem

A pg_tre index over long documents is several times larger than pg_trgm’s GIN index on the same column:

corpus rows text tre (4.3.1) pg_trgm GIN
depesz, explain.depesz.com plans (blog, 4.x) 1.6 M 33 GB 21 GB 1.67 GB
synthetic plans (EC2, 2026-10) 160 k 2.7 GB 1349 MB 358 MB
synthetic prose, 2 GB subset 702 k 2.1 GB 7326 MB 1040 MB

Postings encode the TID packed as (block << 16) | offset in a sparsemap. A sparsemap chunk covers 2048 bits, but one heap block takes 65536 bits. So every heap block a posting touches pays for a full chunk (start offset, descriptor, bit vector), however few of its rows are in the posting. Long documents leave only about 1–14 rows per heap page; depesz’s table has about 1.7. Measured with the vendored sparsemap (a standalone encoder over synthetic postings, 2026-10):

rows/block density <<16 B/TID blk*292+off B/TID
1 0.9 24.0 10.5
4 0.9 6.7 3.0
4 0.3 15.2 7.0
30 0.3 2.7 1.5
120 0.05 5.2 3.4

Proposal

Pack TIDs as block * MaxHeapTuplesPerPage + offset, i.e. 291 + 1 for 8 KB pages and 32-bit blocks. The packed value stays below 241. Sort order is unchanged (the mapping is monotonic), so the build, merge and scan algorithms stay as they are. This alone gives 2–2.3x smaller postings on long-document tables, and therefore fewer pages to build, WAL-log and read.

This is an on-disk format change:

  • record the packing in the meta page (new field, carved from reserved[]; 0 = legacy <<16). Every pack/unpack (about 20 sites: build, scan, pending list, vacuum, posting leaf min_tid/max_tid) reads it through the relation;
  • new builds use the dense packing. Old indexes keep working unchanged, and REINDEX (or pg_tre_upgrade_index) converts them;
  • bump PG_TRE_FORMAT_VERSION_LATEST, so an older binary refuses a new index instead of misreading it;
  • tests: the CI in-place upgrade job from 4.3.x, a mixed-packing pending list, VACUUM across both packings, and a seq-vs-index differential on an old-format index after the upgrade.

Beyond that, a per-chunk sparse encoding tuned for 1–2 set bits per block would close most of the remaining gap to GIN’s varbyte posting lists. Measure it after this change.

As built (4.4.0)

  • PgTreMetaPageData.tid_packing (PgTreTidPacking: 0 legacy, 1 dense), read once per relcache entry into rd_amcache by pg_tre_tid_packing() (src/pages/meta.c) without the content lock – the field never changes after the relfilenode is created, and the caller may already hold the meta buffer. pg_tre_build_empty_fork() writes it and primes the cache.
  • The stride is MaxHeapTuplesPerPage + 1 (292 for 8 kB pages); packing an offset at or above it raises an ERROR instead of aliasing the next block.
  • The build’s sort key keeps legacy packing (lossless for any offset, same order) and the posting builder repacks.
  • pg_tre_upgrade_index() does not convert; it points a legacy index at REINDEX. A non-heap table AM is built legacy.
  • test/sql/tid_packing.sql runs the same rows through both packings.

Measured (PostgreSQL 18.6, FreeBSD 15.1, i4i.8xlarge; 4 GB maintenance_work_mem, 8 participants):

corpus rows / heap block 4.3.1 4.4.0 ratio pg_trgm GIN
4.1 GB prose, 1.4 M rows 8.9 14.2 GB 8.0 GB 1.77x 2.0 GB
2.5 GB EXPLAIN plans, 160 k rows 13.6 1349 MB 886 MB 1.52x 358 MB
1.3 GB prose kept in the heap, 300 k rows 1.4 9.4 GB 5.5 GB 1.71x 864 MB

The ratios fall short of the 2–2.3x the synthetic postings predicted: a real corpus’s postings mix dense trigrams (many rows per block, where both packings already pack well) with sparse ones. Build time is unchanged (757 s vs 786 s at 64 MB / 1 participant on the prose corpus, 319 s vs 336 s at 4 GB / 8). Average sparsemap bytes per TID on a full posting leaf went from 9.4 to 5.3 on the prose corpus.