# pg_tre on-disk page format (v3, v4) Authoritative declarations live in `include/pg_tre/page.h`. This document is the narrative reference and the place where format changes are reviewed before they are locked in. All multi-byte fields use native byte order. All pages are the Postgres cluster page size (default 8 KiB) and begin with the standard `PageHeaderData` at offset 0 and end with a `PageTreOpaqueData` trailer in the special area. ## Format version history - **v10 (3.2.0)**: SuRF (Succinct Range Filter) tier. Adds a new page kind `PG_TRE_PAGE_SURF` holding the serialized SuRF-Base image (a LOUDS-Sparse trie over the order-preserving trigram key `pg_tre_trigram_key_cp`) across a chain of pages, each led by a `PgTreSurfHeader` (`next_page`, `chunk_bytes`, `total_bytes`), rooted at the new meta field `root_surf` (with `surf_n_keys`). Purely ADDITIVE: no existing page kind changes layout, `PG_TRE_FORMAT_VERSION_MIN` stays 6, and a v6-v9 index has `root_surf = InvalidBlockNumber` so it reads unchanged with NO REINDEX (the scan simply runs without the prefilter). Because the SuRF is a whole-index structure it is NOT synthesized by the in-place page-stamp upgrade; REINDEX populates it. The same version REMOVES the never-read BRIN-style range-bloom tier: `PG_TRE_PAGE_RANGE` is no longer emitted and `root_range` is a reserved meta field pinned to `InvalidBlockNumber`. The freed WAL opcode `XLOG_PTRE_RANGE_UPDATE` (0x70) is reused as `XLOG_PTRE_SURF_UPDATE`. - **v8 (2.0.0-dev)**: Posting-page coalescing. Adds a new page kind `PG_TRE_PAGE_POSTING_COALESCED` that packs the postings of multiple trigrams onto one page, addressed by a slot index carried in the upper-tree leaf entry's `inline_bytes` field (high bit `PG_TRE_COALESCED_FLAG`). Purely ADDITIVE: no existing page kind changes layout, `PG_TRE_FORMAT_VERSION_MIN` stays 6, and a v6/v7 index never sets the coalesced flag, so it reads unchanged with NO REINDEX. The new page kind appears only in indexes built or rebuilt at v8. See `doc/specs/posting-page-coalescing.md`. - **v7 (2.0.0-dev)**: Run/level catalog (Phase B1). Adds the `PG_TRE_PAGE_RUN_CATALOG` page kind and meta-page run fields. Additive: a v6 index reads as one implicit run, no REINDEX. - **v6 (1.6.0)**: Sparsemap 4.0.0 wire format (64-bit chunk offsets). BREAKING -- v<6 indexes require REINDEX (the old 32-bit format is not backward-readable and silently lost data on large heaps). - **v5 (Phase 8)**: Multi-leaf range tier (`PgTreRangeHeader` + `right_link` chain). Only RANGE pages differ from v4; readers handle v<5 range pages for back-compat. - **v4 (1.4.0-dev)**: Identical byte layout to v3; the bump exists to land the in-place format-upgrade infrastructure (see below). No reader change between v3 and v4 beyond accepting both at page-decode time. - **v3 (Phase 4.2)**: Multi-leaf posting trees. When a single trigram's posting exceeds ~8 KB, the builder splits it across multiple leaves linked by `right_link` (Lehman-Yao convention). Each leaf stores `min_tid` and `max_tid` bounds. Readers traverse the chain to find the leaf containing a target TID. - **v2 (Phase 3.5)**: Codepoint-based trigrams. - **v1**: Initial format with byte-based trigrams. Indexes built with v2 or earlier require REINDEX to use 1.x. Indexes built with v3 are read directly by 1.4.0-dev; in-place upgrade to v4 is available via `pg_tre_upgrade_index()`. ## Meta page (block 0) +-----------------------------------+ | PageHeaderData | 24 B +-----------------------------------+ | PgTreMetaPageData | variable (reserved[32]) | uint32 magic 0x50545245 ('PTRE') | uint32 format_version 1 | uint32 q trigram size (default 3) | uint32 tri_encoding 0=byte, 1=codepoint-hash | uint32 bloom_range_m_bits | uint16 bloom_range_k | uint16 bloom_tuple_m_bits | uint8 bloom_tuple_k | uint8 _pad[3] | Block root_upper | Block root_range | Block pending_head | Block pending_tail | uint64 pending_n_entries | Block stats_blk | uint64 n_trigrams | uint64 n_tuples_indexed | uint32 created_xid | uint32 reserved[32] +-----------------------------------+ | | (unused) +-----------------------------------+ | PageTreOpaqueData | 8 B | page_kind = META | +-----------------------------------+ ## Upper tree pages Internal node (UPPER) and leaf node (UPPER_L) share the same header layout but carry different entry types. internal: (trigram_hash_low_watermark, child_blk) pairs leaf: PgTreUpperLeafEntry[] sorted by trigram_hash Split protocol: Lehman-Yao right-link. Right-link is stored in the opaque area's flags region. ## Posting tree pages Internal (POSTING) and leaf (POSTING_L) pages. ### POSTING (internal) (min_tid, child_blk) pairs, sorted by min_tid. ### POSTING_L (leaf) Phase 4.2: supports multi-leaf chains when a single trigram's posting exceeds the ~8 KB single-leaf budget. Leaves are linked via `right_link` (Lehman-Yao style). Each leaf stores its TID range in `min_tid` and `max_tid`. Readers traverse right-links to find the leaf containing a target TID. +-----------------------------------+ | PageHeaderData | 24 B +-----------------------------------+ | PgTrePostingLeafHeader | 40 B | right_link | next leaf in chain (or InvalidBlockNumber) | min_tid / max_tid | TID range for this leaf | sparsemap_bytes | | payload_bytes | | payload_offset | | n_entries | +-----------------------------------+ | sparsemap blob | sparsemap_bytes +-----------------------------------+ | | | (free space) | | | +-----------------------------------+ | payload region (grows from below) | payload_bytes | per-TID: (pos_list_varlen, | | tuple_bloom_128) | +-----------------------------------+ | PageTreOpaqueData | 8 B | page_kind = POSTING_L | +-----------------------------------+ Access by TID: 1. Walk right-links until `min_tid <= target <= max_tid` 2. Within that leaf: `sparsemap_rank(map, 0, TID, true)` gives the entry index; multiply by sizeof(payload record) -- or walk the variable- length region via per-entry offset table -- to locate payload. ## Range summary tree (REMOVED in 3.2.0) Historical (v5-v9): a BRIN-style tree of `PgTreRangeLeafEntry` + inline bloom vectors, keyed on `range_start_blk`. It was built on every index but never consulted at scan time, so 3.2.0 stopped emitting it. `PG_TRE_PAGE_RANGE` is no longer written and `meta.root_range` is a reserved field pinned to `InvalidBlockNumber`. ## SuRF filter tier (v10) The serialized SuRF-Base image (a LOUDS-Sparse succinct trie over the order-preserving trigram key) is stored across a chain of `PG_TRE_PAGE_SURF` pages, rooted at `meta.root_surf`. Each page begins with `PgTreSurfHeader` (`next_page`, `chunk_bytes`, `total_bytes`) followed by that page's slice of the image; the reader concatenates the slices and deserializes. Point queries are exact (SuRF-Base indexes the full 8-byte key); range queries have a one-sided error (no false negatives). Consulted only for `^`-anchored / prefix / `LIKE 'foo%'` patterns to reject a scan when the prefix's trigram-key range is empty. ## Pending list A forward-linked chain of pages, head stored in the meta page. Each page begins with `PgTrePendingHeader` and is followed by a packed array of `PgTrePendingEntry`. New entries append at the tail page; the list is consumed by VACUUM's cleanup phase or the user-visible `pg_tre_flush()` function. ## Opaque trailer Every page ends with `PageTreOpaqueData`: uint16 page_kind uint16 flags uint32 format_version /* per-page on-disk format */ Positioned via `PageGetSpecialPointer(page)`. `format_version` is the *per-page* on-disk format the page bytes are in; it can differ from the meta page's index-level `format_version` while an in-place upgrade is in progress. All readers accept any value in `[PG_TRE_FORMAT_VERSION_MIN, PG_TRE_FORMAT_VERSION_LATEST]`. Writers always emit `LATEST`. ## In-place format upgrade The machinery for upgrading an existing index to the current on-disk format without REINDEX: - Per-page: `PageTreOpaqueData.format_version` records the format the page bytes are in. Writers (page-init, posting-leaf flush, posting- leaf rewrite, in-place upgrade) always set it to LATEST. - Meta: `PgTreMetaPageData.min_page_format_version` is the minimum observed across all pages of the index. When equal to LATEST, the index is fully upgraded and future readers can skip per-page format dispatch. SQL surface (1.4.0-dev): -- Walk every page; rewrite below LATEST in place. WAL-logs each -- rewritten page as XLOG_PTRE_PAGE_FORMAT_UPGRADE (FORCE_IMAGE). -- Holds per-page exclusive lock only briefly. Updates the meta -- page's min_page_format_version after the sweep. SELECT pg_tre_upgrade_index('my_idx'); -- Per-version page counts. SHARED locks; safe to run concurrently. SELECT * FROM pg_tre_index_format_status('my_idx'); -- O(1) read of meta page's min_page_format_version. SELECT pg_tre_index_min_format_version('my_idx'); Readers that decode format-version-dependent layouts dispatch through `pg_tre_bloom_decode_tuple()` (see `src/util/bloom.c`); the call sites in `src/am/amscan.c::apply_tuple_bloom_filter` pass the per-page `format_version` returned out-of-band by `pg_tre_posting_lookup_tuple_bloom`. Today v3 and v4 share a decode path; future format versions plug new arms into `pg_tre_bloom_decode_tuple` without touching the call sites. The upgrade is a no-op for v3 -> v4 since the byte layouts are identical; the framework exists so the next on-disk format change (planned: variable-width per-tuple blooms in a follow-on commit) can ship as an in-place rewrite rather than a hard REINDEX requirement. ## On-disk version policy `format_version` lives in the meta page and is copied to each page's opaque trailer on write. Readers accept any value in `[PG_TRE_FORMAT_VERSION_MIN, PG_TRE_FORMAT_VERSION_LATEST]`; the meta page's `min_page_format_version` records the minimum across all pages of the index, updated by `pg_tre_upgrade_index()` after a full sweep. Any layout change bumps `PG_TRE_FORMAT_VERSION_LATEST` and ships with: - A migration script under `sql/pg_tre----.sql` exposing any new SQL surface. - For incompatible breaking changes (e.g. v2 -> v3): a unit test that reads a snapshot built with the previous version and validates field-for-field equality after upgrade. - For compatible bumps (e.g. v3 -> v4): the in-place upgrade path via `pg_tre_upgrade_index()`. Breaking version bumps (anything that requires REINDEX) are only permitted at major releases (1.0 -> 2.0); compatible bumps that ship an in-place upgrade may land in minor releases.