Contents

Changelog

All notable changes to pg_tre are documented in this file, organized by development phase.

The format follows Keep a Changelog.

Unreleased

Fixed

  • The 4.4.0, 4.5.0 and 4.5.1 release tarballs did not build. make dist appended both vendored submodules with one tar --concatenate, and GNU tar 1.35 appends only the first, so vendor/lime was empty (“No rule to make target ‘vendor/lime/lime.c’”). Building from the git tags was not affected. make dist now appends them one at a time and fails if either is missing.

Added

  • pg_tre is on PGXN (pgxn install pg_tre), from 4.5.1. Each v* tag on the GitHub mirror publishes the release (.github/workflows/pgxn-release.yml).

[4.5.1] - 2026-10-18 - Security: pg_tre_index_check pins its search_path

No on-disk change; no REINDEX either way. Upgrade from 4.5.0 with ALTER EXTENSION pg_tre UPDATE.

Security

  • pg_tre_index_check() (new in 4.5.0) ran with the caller’s search_path. It called format(), upper(), substr() and other functions unqualified, so a function with a matching signature in a schema ahead of pg_catalog on the caller’s path ran in their place, with the caller’s privileges – typically a superuser checking an index after an upgrade. The function now pins search_path to pg_catalog, pg_temp and qualifies every function and operator. Anyone who can create functions in a schema on a superuser’s search_path could exploit it on 4.5.0; nothing else in pg_tre is affected. Reported by pgspot in CI.

[4.5.0] - 2026-10-17 - Two wrong-results fixes; pending_list_limit works; pg_tre_index_check

No on-disk format change; no REINDEX to upgrade or to downgrade to 4.4.x – but REINDEX any tre index built with pg_tre.min_trigram_freq above 1 (see below), and REINDEX any index to turn its SuRF prefilter back on. Field report 2026-10-17 (solnix.io).

Fixed

  • Anchored patterns missed rows inserted after CREATE INDEX (since 3.2.0). The SuRF prefilter, which returns an empty result when no indexed trigram falls in an anchored prefix’s range, was built once by CREATE INDEX and never learned trigrams that later rows brought. So col ~ '^warn' (any k=0 anchored prefix of 3+ characters, also %~~ tre_pattern('^warn', 0)) returned no rows from the index when “war” first appeared after the build, before and after VACUUM, while a sequential scan found them. LIKE 'warn%', ~* and ILIKE were not affected. The prefilter is now used only while it still covers every key and the pending list is empty; on an index built before 4.5.0 it is off (correct results immediately, no REINDEX needed; REINDEX turns it back on).
  • pg_tre.min_trigram_freq above 1 made the index miss rare words (since 1.2.1): the build dropped the postings of rare trigrams, and a missing trigram reads as “in no row” to every scan. Values above 1 are now refused. REINDEX any index built with one.
  • fastupdate and pending_list_limit were accepted and did nothing (documented since 4.2.3). See Changed.
  • The “exceeds single-leaf budget” error advised waiting for multi-leaf postings, which shipped long ago; the error is unreachable and internal now, and the stale doc entries are gone.

Changed

  • pending_list_limit works: the INSERT that pushes the pending list past the limit merges it into the index, as VACUUM does, unless a merge is already running (it does not wait). Merges are serialized by a lock that scans and inserts never take. The default is 0, no limit, so nothing changes unless you set it – per index (WITH (pending_list_limit = 4096), KiB) or with pg_tre.pending_list_limit. An index created with an explicit pending_list_limit before 4.5.0 starts merging at that size. The INSERT that triggers a merge pays for it.
  • fastupdate = off is refused at CREATE INDEX and ALTER INDEX, and pg_tre.fastupdate = off is rejected: every insert goes through the pending list. An index that already stores fastupdate=off still opens.

Added

  • pg_tre_index_check(regclass, samples int DEFAULT 20): for patterns cut from the column’s own values, counts matching rows by sequential scan, bitmap index scan and plain index scan for %~~ (k=0 and 1), ~, ~*, anchored ~/~*, LIKE and ILIKE, and returns one row per check (ok false where the index disagrees). A closing NOTICE (WARNING on disagreement) reports the page formats – flagging a mix – TID packing and pending-list size. Run it after every upgrade; it found both fixes above on its first runs. Costs about 8 sequential scans per sample.
  • pg_tre_index_pending(regclass): entries in the pending list.
  • tap/pending_limit.pl, test/sql/pending_limit.sql, and a late-prefix section in surf_prefix.

[4.4.1] - 2026-10-17 - PostgreSQL 19

No on-disk change; no REINDEX to upgrade from 4.4.0 or to downgrade to it. Nothing changes on PostgreSQL 17 or 18 except the tests.

Fixed

  • pg_tre did not build on PostgreSQL 19 (reported against 19rc1). Three API changes: table_beginscan() and table_beginscan_parallel() take a ScanOptions flags argument, utils headers no longer include <limits.h>, and pg_locale_t lost its provider field and info union. 19 also builds with -Wimplicit-fallthrough; pg_tre’s fall-throughs are annotated.

Changed

  • On PostgreSQL 19, character classes and (?i) call core’s own ctype functions (pg_iswalpha(), pg_towupper() and friends, new public API in 19), exactly as core’s regex engine does. Under an ICU collation pg_tre now follows libicu like ~ does, so the one documented class difference from core (ICU collations classified with PostgreSQL’s Unicode tables) applies to 17 and 18 only.

Tests and CI

  • CI builds and tests PG 19 (gcc and clang, -Werror) from PGDG’s testing suite. macOS stays on 17 and 18 (Homebrew has no postgresql@19), and the flake on 17 and 18 (nixpkgs has no postgresql_19).
  • encoding_matrix skips MULE_INTERNAL on 19, which removed the encoding. It also no longer counts against pg_tre an ILIKE check that core’s own ILIKE gets wrong: on 19rc1, 'xÆy' ILIKE '%Æ%' is false in a LATIN1, WIN1252 or KOI8R database with a C ctype (a core bug, from 1e493158d3d). The index agrees with core either way.
  • scripts/run-regress.sh accepts <test>_N.out alternative outputs as pg_regress does, and prints FAIL and the diff for a failing test instead of exiting silently.

[4.4.0] - 2026-10-16 - Smaller indexes (dense TID packing); UNLOGGED indexes survive a crash; FreeBSD

On-disk format v11. Upgrading needs no REINDEX: an index built by 4.3.x or earlier keeps working as it is. REINDEX (or REINDEX CONCURRENTLY) rebuilds it in the new, smaller layout, and pg_tre_index_tid_packing() says which layout an index has. Downgrading to 4.3.x needs a REINDEX of every tre index 4.4.0 has written to: 4.3.x refuses those pages (“format version 11, supported range is [6, 10]”) rather than misread them.

Changed

  • Indexes are 1.5-1.8x smaller on heap tables. A posting packed each heap TID as block << 16 | offset, so every heap block a posting touched cost a whole sparsemap chunk, however few of its rows matched. New indexes pack block * 292 + offset (MaxHeapTuplesPerPage + 1), so several blocks share a chunk. Measured on PostgreSQL 18.6, FreeBSD 15.1, i4i.8xlarge (index, 4.3.1 -> 4.4.0, pg_trgm GIN for scale):

    corpus rows per heap block 4.3.1 4.4.0 pg_trgm
    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 1.32 GB 0.87 GB (1.52x) 0.35 GB
    1.3 GB prose kept in the heap, 300 k rows 1.4 9.4 GB 5.5 GB (1.71x) 0.84 GB

    Build time is unchanged (within 5%); query times are the same or slightly better. The gap to pg_trgm remains: the next step is a sparsemap chunk encoding for one or two rows per block (doc/design/dense-tid-packing.md). An index on a table access method other than heap keeps the old packing.

  • Vendored sparsemap v5.8.3 (tag 5b7860c, verbatim): decoding is 1.8-1.9x faster than v5.8.2, small-set and SIMD kernels are alignment-safe, and the unused __sm_small_bytes_for() that failed -Werror builds with clang (the macOS CI jobs) is gone. 4.3.0 and 4.3.1 vendored the untagged release/5.8.2 branch (89a9aa9), not the v5.8.2 tag their notes named. The wire format is unchanged.

Fixed

  • An UNLOGGED tre index failed every query after a crash. Crash recovery resets an UNLOGGED relation from its init fork, which must be WAL-logged; pg_tre wrote it through generic WAL, which logs nothing for an UNLOGGED relation. A crash before the next checkpoint left a zeroed template: every scan of the reset index failed “meta page magic mismatch (got 0x00000000)” and an INSERT hung on its own meta-page lock. Since 4.0.0. The init fork’s meta page is now logged as GIN’s is (tap/unlogged_crash.pl). An affected index is repaired by REINDEX.
  • (?i) folds the way ~* does on every ctype. TRE folded a character only when isupper()/islower() classified it; core takes the case images from toupper()/tolower(). Titlecase letters (Dž) under ICU and builtin collations folded differently (a documented limitation, now gone), and on FreeBSD’s libc so did letter numbers and circled letters ((?i)Ⅻ did not match ⅻ). New TRE patch patches/tre-icase-allcases.patch.
  • Two clang warnings in src/util/surf.c (an unused function, a self-assignment) that FreeBSD’s clang reports.

Added

  • FreeBSD: builds with gmake and clang, and passes the regression suite (PostgreSQL 17 and 18, C and C.UTF-8) and the TAP and stress suites on FreeBSD 15.1. tap/build_memory.pl is skipped there (it reads /proc).
  • pg_tre_index_tid_packing(regclass) returns 'dense' or 'legacy'; pg_tre_upgrade_index() points a legacy index at REINDEX.
  • test/sql/tid_packing.sql (legacy and dense on the same rows: build, pending list, VACUUM, slot reuse, offsets up to 290, REINDEX) and tap/unlogged_crash.pl.

CI

  • The Sanitizer job ran nothing since it was added: initdb died “stack depth limit exceeded” under ASan’s fake stack (on by default in the runner’s libasan). scripts/asan-check.sh sets detect_stack_use_after_return=0.
  • The nightly stress job never passed. test/scripts/wal_audit.sh looked for the pg_tre resource manager removed in 4.0.0; it now attributes generic WAL records to the index by relfilenode (and its init-fork check found the UNLOGGED bug above). The asan leg loaded an instrumented pg_tre.so into the stock server, which the runner’s kernel cannot do; it now runs inside the ASan-built PostgreSQL (ASAN_STRESS=1 scripts/asan-check.sh) and gates.
  • The Makefile no longer re-applies a TRE patch that is already in (it checked each patch on its own, and later patches touch the same files).

[4.3.1] - 2026-10-15 - CREATE INDEX on large tables: bounded memory, parallel posting build, far faster; regex and fuzzy queries the index could not serve

No on-disk format change; no REINDEX to upgrade or to downgrade to 4.3.0. Rebuilding an index built by 4.3.0 gives the same index faster; nothing in an existing index is wrong. Field report: Codeberg issue #1 and the depesz.com review of pg_tre (2026-08-25) – a 30 GB text column whose build ran 7 hours (and in a later attempt grew to 33 GB RSS), plus regex syntax the index rejected.

Fixed

  • CREATE INDEX leaked every compressed row’s text for the whole heap scan. The build detoasted each value in the statement’s memory context and never freed it, so the backend grew by the size of the toasted text: 33 GB RSS and climbing on a 30 GB column (issue #1), and on a 30 GB / 10.5 M-row corpus with about half its rows compressed, +5 MB/s to 5.8 GB at 41% of the scan. Each heap tuple now runs in a per-row memory context, as nbtree and GIN do; the same build stays at ~200-600 MB. tap/build_memory.pl pins it. Present since 3d45b8d (2026-05).
  • A posting that spans many leaf pages cost O(N2 / page) to build. Every leaf re-encoded the whole remainder of the posting to size itself, so the hot trigrams of a large table kept the build in one loop for hours. Leaves are now cut with one cursor pass, and a posting that cannot fit a page is no longer encoded whole just to find that out. Leaves fill slightly better (index ~4% smaller).
  • Looking up a hot trigram copied its posting once per leaf page. A posting chain was unioned leaf by leaf into one growing map, O(N * L); on a 30 GB table one lookup spent 37 s before reading the heap. It is merged like a binary counter now, O(N log L): 0.66 s.
  • 'ab+c' dropped rows from the index (index != seq scan, for ~ and %~~): a repetition with a minimum of one (b+, b{1,3}) carried the literal run through a single copy, so the index required the trigram abc and lost rows holding only abbc.
  • Patterns core regex accepts failed on the index path with pg_tre: invalid regex pattern: and an empty message: lazy quantifiers (x*?), empty alternatives ((|a), a||b), director prefixes (***=), a{,3}. pg_tre’s pattern parser only finds trigrams; when it cannot read a pattern the scan is now lossy and the recheck’s engine matches it or raises its own error. depesz hit this with a lookbehind.
  • EXPLAIN showed Index Searches: 0 and pg_stat_user_indexes.idx_scan stayed at zero: pg_tre never counted an index search.
  • A backslash inside a bracket ([\é]) means an escape to core regex and a literal backslash to TRE; the index now treats such a bracket as one unknown character for both.

Changed

  • The posting-tree phase of a parallel build runs on every participant. It used to merge the sorted stream and write every posting tree on the leader alone, while the workers sat idle. Trigrams now go to one of several hash-range sorts; each participant claims ranges, merges them and writes their posting trees; the leader builds the upper tree and the SuRF filter from the ranges' results in hash order. The index content is the same as a serial build’s. See doc/design/parallel-posting-build.md.
  • Lookarounds and (?:...) no longer make a pattern unindexed. (?:X) is a group; (?=..), (?!..), (?<=..), (?<!..) stand for an optional character, so the literals around them still give trigrams. Embedded options ((?i)) remain lossy.
  • Small character classes are indexed. aa[bc]c requires (aab | aac) AND (abc | acc) instead of giving up on the pattern (a class of at most 8 characters, at most 64 combinations per trigram).
  • Fuzzy matches (k >= 1) filter on exact pieces of the pattern. The pattern’s literals are cut into k+1 pieces of at least three characters; a match within k edits keeps one piece intact, so the filter is the OR of each piece’s trigrams ANDed. The old filter unioned every trigram’s edit neighbourhood, which in a UTF-8 database could not narrow 'postgresql' at k=1 at all.

Measured on PostgreSQL 18.6, i4i.8xlarge (32 vCPU, NVMe), synthetic prose:

4.3.0 4.3.1
30 GB / 10.5 M rows, depesz’s settings (maintenance_work_mem 64 MB, 2 participants) cancelled at 18 min: 5.8 GB RSS, +5 MB/s, scan 41% done; with only the leak fixed, still building postings at 1 h 52 min 1 h 33 min, peak RSS 300 MB
30 GB / 10.5 M rows, maintenance_work_mem 4 GB, 8 participants – 30 min (pg_trgm GIN at 64 MB: 52 min)
30 GB table: ~ 'aa[bc]c[b-d]' every row rechecked 0.78 s (pg_trgm 0.28 s)
30 GB table: ~ '(su){3}' / ~ 'quick brown' – 12.4 s / 6.7 s (pg_trgm 36 s / 26 s)
2 GB / 702 k rows, serial, 1 GB leak fixed only: posting phase cancelled after 90 min 216 s
2 GB / 702 k rows, 1 GB, 5 participants – 154 s (posting phase 53 s)
2 GB subset: %~~ tre_pattern('postgresql', 1) 190 s (every row rechecked) 5.4 s (4.7 k candidates)
2 GB subset: ~ 'aa[bc]c[b-d]' every row rechecked 229 candidates, 0.2 s
~ '(?<=e.)aa[bc]c[b-d]' ERROR: pg_tre: invalid regex pattern: 229 candidates, 0.4 s

Added

  • Tests: rep_extract, regex_groups_index, class_pieces, and tap/build_memory.pl. regex_class_index’s pattern helper set only one side of the planner settings with SET LOCAL, which lasts across calls in one SELECT, so its sequential side could compare the index with itself; it now sets all three every call (results unchanged).
  • doc/design/dense-tid-packing.md: why a tre index over long documents is several times larger than pg_trgm’s (each heap block a posting touches costs a whole sparsemap chunk) and the proposed 4.4.0 format change.

[4.3.0] - 2026-10-07 - every server encoding; character classes and case folding follow core regex; PostgreSQL 17; index false negatives fixed

No on-disk format change. UTF-8 databases: no REINDEX (trigram hashes are unchanged). Non-UTF-8 databases (SQL_ASCII, LATIN1, WIN1252, EUC_*, …): REINDEX every tre index that holds non-ASCII text. Before 4.3.0 the tokenizer decoded every database as UTF-8. Text that was not valid UTF-8 raised invalid UTF-8 sequence, but bytes that happened to form valid UTF-8 (e.g. é in LATIN1, or raw UTF-8 in SQL_ASCII) were indexed as Unicode code points. 4.3.0 reads them as characters of the database encoding, so their trigrams differ, and exact searches through such an index miss those rows until it is rebuilt. A pure-ASCII index needs nothing. Behaviour changes are listed below; all of them are corrections.

Added

  • Every server encoding. Text is decoded in the database encoding, in the trigram tokenizer and inside TRE (patches/tre-mbdecoder.patch), with PostgreSQL’s own per-encoding tables. Before, the tokenizer hard-coded UTF-8: non-ASCII text in a LATIN1, WIN1252, KOI8R, EUC_* or other database failed with invalid UTF-8 sequence. TRE decoded with mbrtowc() under the backend’s LC_CTYPE. The 4.2.2 uselocale() workaround is gone. Fuzzy edits count characters in every encoding.
  • PostgreSQL 17 support (CI already built it; it now compiles, runs and passes the full suite on 17.x as on 18.x).
  • Tests: encoding_nonutf8, encoding_matrix (one generic check per server encoding), regex_class_index, regex_syntax_edges, collation_guard, collation_matrix, tre_ctype_strategies, tre_collation_classes, tre_upstream_fixes, and tap/sm_short_len.pl.

Changed

  • Regex character classes ([[:alpha:]], \w, \s, \d and their negations) and case folding ((?i)) now follow PostgreSQL’s regex engine (regc_pg_locale.c) for the call’s collation, through TRE ctype hooks. Before, TRE asked iswalpha()/towlower() under the backend’s LC_CTYPE. Under a C ctype, [[:alpha:]] and (?i) ignored every non-ASCII letter; under a real locale they followed that locale regardless of the column’s collation. Now:
    • the answer equals core ~ / ~* with the same collation, including core’s fixed blank / cntrl / xdigit sets and its (?i)[[:upper:]] = alpha rule (patches/tre-icase-class.patch);
    • functions use the expression’s collation (COLLATE in the query or the column’s); the ordered index scan uses the index column’s collation;
    • the compiled-pattern cache is keyed by collation.

    Behaviour change: class and (?i) answers over non-ASCII text can differ from 4.2.x; they now match core. One documented difference remains: ICU collations classify with PostgreSQL’s Unicode tables, not libicu, because pg_tre.so does not link ICU. See LIMITATIONS.md.

  • Nondeterministic collations are refused at CREATE INDEX, REINDEX and any ALTER that rebuilds the index (an ICU level1 collation makes =/LIKE match strings that share no trigrams, so the index silently under-returned). Regex functions raise core’s errors for an indeterminate or nondeterministic collation.
  • Vendored sparsemap v5.8.0 -> 5.8.2 (the untagged release/5.8.2 branch, 89a9aa9, not the v5.8.2 tag; corrected in 4.4.0): O(1) sm_validate check (f) (5.8.1’s version cost every posting read about 75%), short buffers in sm_open/sm_init, and set-operation fixes pg_tre does not reach. The wire format is byte-identical.

Fixed

  • Index scans silently dropped matching rows (index != sequential scan):
    • [[:class:]], [=e=] and [.c.] brackets were read as literal character sets. [[:alpha:]] became {[, :, a, l, p, h} plus ].
    • \d \w \s raised “not yet implemented”, and (?i) raised an empty “invalid regex pattern”, on the index path only.
    • Approximate (k >= 1) scans lost rows in which a non-ASCII character was edited, and rows where ./a class/a repetition sat between literals (“xq.zw” demanded trigrams no match contains). Tiling now separates literal runs and goes lossy when spine_n <= 3k with exact-only trigrams.
    • A randomized index-vs-seq differential over 750 queries: 4.2.2 disagreed on 35, 4.3.0 on none.
  • TRE matcher bugs (patches/tre-upstream-fixes.patch, from gburd/tre PRs #1 and #2):
    • multibyte back-references never matched ((éa)\1) or reported offsets past the end of the string;
    • \< \> ^ right after a back-reference failed in every encoding;
    • approximate matching could not insert before a failed $ / \> (^caf$ was not 1 edit from 'cafe');
    • a class mismatch was not costed as a substitution in multibyte mode.
  • A stored sparsemap length under 8 bytes (page corruption) raised a sparsemap over-read; it is now a DATA_CORRUPTED error with a REINDEX hint.
  • PostgreSQL 17:
    • an unfilterable query cost exactly disable_cost, so PG17 tied it with a disabled seq scan;
    • sm_short_len.pl passed a PG18-only initdb flag (fsm_stale.pl was fixed in 4.2.3);
    • PG17’s pg_newlocale_from_collation(DEFAULT) returns NULL for libc.

[4.2.3] - 2026-10-07 - backend crash on an ERROR during a pending-list scan

No on-disk format change; no REINDEX to upgrade or to downgrade to 4.2.2. Recommended for every installation that builds pg_tre with clang, which includes the flake (nix build .#pg18).

Fixed

  • Backend crash (free(): invalid pointer / munmap_chunk(): invalid pointer, sometimes a later SIGSEGV) when an ERROR was raised during an index scan of a tre index with a non-empty pending list. Every connection was dropped and the cluster went through crash recovery. Common triggers are statement_timeout, a query cancel, or a corrupt-page error, on a %~~ ... ORDER BY ... LIMIT plain index scan of an insert-heavy table that VACUUM rarely visits. The scan kept its pending-list overlay in a non-volatile stack struct and read it in PG_CATCH after siglongjmp. C leaves such an object indeterminate, and the clang -O2 -flto build (the flake’s) called overlay_free() with stale argument registers, freeing a saved register out of the jump buffer. gcc builds and plain clang PGXS builds keep the struct in memory and did not crash. Present since 1.5.2, which added the PG_CATCH; observed in production on 4.2.0-4.2.2 (field report 2026-10-06, reproduced with the released v4.2.2 flake build). The overlay and the crack cache now live in palloc’d memory. The candidate maps are volatile objects (sm_t *volatile, not volatile sm_t *, which had also let clang drop their cleanup free() and leak them on every error). overlay_free() is idempotent. The parser’s Lime handle had the same declaration and is fixed too.
  • Docs: fastupdate and pending_list_limit are accepted but not implemented. Every INSERT goes to the pending list and only VACUUM merges it; fastupdate = false does not bypass it, and nothing caps its size. doc/pg_tre.md described an insert-time auto-merge that does not exist. LIMITATIONS.md now explains the scan cost of a long list and the autovacuum_vacuum_insert_threshold workaround.

Added

  • tap/scan_cancel.pl: 120 statement_timeouts landing inside the overlay scan. It asserts no backend crash, no glibc heap report, and index == seq scan afterwards.
  • CI job nix-clang-tap: runs that test against exactly what nix build .#pg18 ships, the only build in which the bug reproduced. Dry-run of the job’s steps: v4.2.2 fails (crash on the first query), 4.2.3 passes.

[4.2.2] - 2026-09-30 - fuzzy matching counts characters under any locale; vendored sparsemap v5.8.0

No on-disk format change; no REINDEX to upgrade or to downgrade to 4.2.1. Index pages written by 4.2.1 and by 4.2.2 are byte-identical.

Fixed

  • Fuzzy matching counted bytes instead of characters on UTF-8 databases with a C/POSIX LC_CTYPE. TRE picks its unit from the backend’s ctype, so 'cafe' was 2 edits from 'café' (é is 2 bytes) and キ was 3 edits from ス. The same k=1 query returned different rows on a C and a C.UTF-8 cluster, and the byte answer disagreed with the index, whose trigrams are built from characters. On UTF-8 databases pg_tre now runs TRE under a thread-local C.UTF-8 ctype, so edits are always counted in characters. Other encodings are unchanged; match offsets from tre_amatch_detail stay byte offsets. Behaviour change: on a UTF-8 database with a C ctype, fuzzy (k>0) queries over non-ASCII text can return more rows than before – the rows they always should have. No REINDEX: the index already worked in characters.
  • test/expected/utf8_fuzzy.out had recorded the byte behaviour, so the test failed on every C.UTF-8 cluster. 3.1.0 committed the character answer; 3.2.0 regenerated the file on a C cluster and silently turned it into the byte answer. It now expects characters again, pinned by tre_amatch_cost checks that give different numbers for bytes. CI runs the suite a second time in a C.UTF-8 database (run-regress.sh honours CREATEDB_OPTS), so a locale-dependent expected file can no longer land.

Changed

  • Vendored sparsemap v5.7.0 -> v5.8.0, verbatim apart from the include path. Fixes a heap over-read in __sm_coalesce_map, shared by every set operation pg_tre uses (results were already correct; the read was undefined behaviour). sm_add_many_grow, which builds every posting, now merges sorted runs instead of inserting bit by bit: VACUUM of 200,000 short rows went from 18.4 s to 15.7 s and a fresh CREATE INDEX from 18.6 s to 16.1 s (medians of 3, same pg_tre source). Source-file workloads, INSERT and query latency are unchanged. sizeof(sm_t) grows from 24 to 32 bytes; pg_tre never embeds it by value, so this is a recompile only.

Qualified

Debian 12 / gcc 12.2 / PostgreSQL 18.6, EC2 c7i.4xlarge, --enable-cassert: 49/49 regression tests under both --no-locale and --locale=C.UTF-8, with identical output across the two; all tests other than utf8_fuzzy match 4.2.1’s output in both. Also 49/49 with the database locale set per-database each way on the opposite cluster. TAP 22/22 (fsm_stale 5, concurrency 2, replication 5, crash_recovery 10). ASan-instrumented server: 49/49, 0 reports. Upstream sparsemap suite against the vendored copy: 21/21, 0 warnings. An index built by 4.2.1 and read by 4.2.2 gives identical results on 9 queries, and index = seq-scan. Zero compiler warnings.

[4.2.1] - 2026-09-30 - INSERT wedge on LWLock:BufferContent; dead TIDs left by VACUUM

Three write-path fixes from one field report, plus a VACUUM warning. Full write-up: doc/reports/insert-wedge-and-ghost-tids-2026-09.md.

No on-disk format change; upgrading needs no REINDEX. But upgrading does not repair an index an earlier version already damaged: REINDEX any tre index that has raised could not read blocks ... read only 0 of 8192 bytes, or that is far larger than a fresh build. Downgrade to 4.2.0 needs no REINDEX (and brings the bugs back).

Fixed

  • INSERT could wait forever on its own buffer lock (since 1.5.5). pg_tre_extend_fork took an unconditional lock on each block the index FSM offered, while the caller held the meta page and the full pending tail. The FSM is not WAL-logged, so after a crash it can offer a page that is in use – including that tail. Symptoms: LWLock:BufferContent, pg_blocking_pids() = {}, immune to pg_cancel_backend and pg_terminate_backend, every writer and the checkpointer queued behind it, and it came back after every restart. The lock is now conditional and a busy block is skipped, as nbtree’s _bt_allocbuf does. This was not caused by pages from an older version, and installing 4.2.1 is enough to stop it.
  • VACUUM left dead TIDs from the pending list in the index. ambulkdelete checked only the base posting tree. A row inserted and deleted between two VACUUMs was still in the pending list, so it survived, was merged into the tree, and stayed there after the heap freed or truncated its block. Scans then read past the end of the heap (the reported error). VACUUM now merges the pending list before removing dead TIDs, as GIN does, and checks every live run, which also covers pg_tre.flush_to_run.
  • aminsert wrote one pending entry per trigram occurrence, not one per distinct trigram as the bulk build does. The position is never read. On source files the pending list was ~9x larger than necessary: 3,749 files went from 1,504 MB to 165 MB of pending list, INSERT from 12.5 s to 2.9 s, and VACUUM from 74 s to 15 s. Short rows (mail subjects) are unchanged.

Added

  • VACUUM WARNING when pages freed by an earlier VACUUM are still held by an old snapshot and make up half the index (and at least 128 MB). Each merge’s old copy can only be reused once no snapshot can see it, so a long or idle transaction pins one copy per merge. One held snapshot over six ingest rounds took an index to 1.6 GB against 75 MB of heap, with no message. LIMITATIONS.md documents it.
  • tap/fsm_stale.pl reproduces the wedge; 4.2.0 hangs with the field signature. test/sql/vacuum_pending_dead.sql covers the read-past-EOF error, directly and via flush_to_run; 4.2.0 fails both cases. test/sql/pending_distinct.sql covers the per-occurrence entries: 89 pending pages drop to 1.

Qualified

Debian 12 / gcc 12.2 / PostgreSQL 18.6, EC2 c7i.4xlarge, --enable-cassert: 49/49 regression tests, TAP 22/22 (fsm_stale 5, concurrency 2, replication 5, crash_recovery 10), zero compiler warnings (-O1 cassert and -O2). concurrency.pl takes ~640 s on both 4.2.0 and 4.2.1, dominated by its quiesced check over an unmerged ~94,000-page pending list. A/B benchmark against 4.2.0 (three alternating runs, medians) is in the report.

Not reproduced

The report’s 137 GB index over 163 MB of source files. The last two fixes and the snapshot warning each reproduce part of it and together explain its shape. A fresh CREATE INDEX over the same kind of data is 269 MB and agrees with a seq-scan.

[4.2.0] - 2026-09-27 - similarity-family backend abort fixed; vendored sparsemap v5.7.0

Upgrade needs no REINDEX. A downgrade to 4.1.0 does – see below.

Fixed

  • Backend abort in the trigram-similarity functions (every release since 1.9.0). SELECT tre_trgm_similarity('foo','foobar') could terminate the backend with stack smashing detected / SIGABRT and force server recovery, on plain ASCII input with no table or index involved. trgm_set() and pos_trgm() decoded each character into a single pg_wchar, but pg_mb2wchar_with_len() always appends a terminating zero, so every decoded character wrote one pg_wchar past the variable. Whether that is harmless or fatal depends on the compiler’s frame layout – it never fired on the qualification rig, and fired every time on the reporter’s. Fixed by decoding into a MAX_MULTIBYTE_CHAR_LEN + 1 buffer.

    Confirmed, not inferred: against a PostgreSQL built with -fsanitize=address, the reporter’s exact statement on the unfixed code kills the backend with an ASan stack-buffer-overflow in pg_utf2wchar_with_len <- trgm_set (trgm_similarity.c:94), and tre_word_similarity('foo','foo bar') hits the second site in pos_trgm (:343) the same way. The fixed build is ASan-clean. Stock -O2 builds, with or without -fstack-protector-all, did not reproduce – nor did ASan applied to the extension alone, because the offending store is in the server’s code.

    Affected: tre_trgm_similarity, tre_trgm_distance, tre_trgm_sim_op, tre_word_similarity, tre_strict_word_similarity, tre_word_sim_op, tre_word_dist_op, tre_strict_word_sim_op, tre_strict_word_dist_op. Not affected: the index access method, regex / LIKE / ILIKE matching, Levenshtein. Full write-up: doc/reports/similarity-stack-overwrite-2026-09.md.

  • test/expected/pending_reclaim.out was never committed, so run-regress.sh regenerated it every run and the test asserted nothing. Now committed, after checking that index and seq-scan agree in it.

Changed

  • Vendored sparsemap v5.6.0 -> v5.7.0, verbatim apart from the include path. Upstream fixes, all pre-existing in 4.1.0: sm_split could emit a structurally invalid map; sm_offset had a signed-integer overflow on large offsets; sm_equals / sm_hash / sm_compare mis-compared logically-equal maps built differently (pg_tre does not call these three, so this one was latent); a crafted length-1 RLE chunk reported a full-capacity run.
  • New small-set encoding. v5.7.0 can store a map confined to the low 1024 bits as a bare word array (PostgreSQL’s Bitmapset layout) when that is the smallest of its three encodings. pg_tre packs a TID as (blk << 16) | off, so postings on heap block 0 – small tables – start being written this way as soon as 4.2.0 is installed.

Upgrade and downgrade

  • Upgrade: no REINDEX. The wire format is unchanged. Bytes written by 5.6.0 and reopened by 5.7.0 through both of pg_tre’s read paths return identical cardinality across ten shapes chosen to straddle the 1024-bit cap (10/10).
  • Downgrade to 4.1.0: REINDEX required. 5.6.0 does not know the small-set flag. Reading 5.7.0-written maps with 5.6.0: 4 of 10 shapes are rejected, 6 read correctly, 0 are silently misread. 4.1.0’s corruption guard catches all 4 rejections as ERROR: pg_tre: corrupt inline sparsemap ... HINT: REINDEX, so a rollback gives loud, fixable errors rather than missing rows. Anything older than 4.1.0 lacks that guard and would read those postings as empty – do not downgrade past 4.1.0 without a REINDEX.
  • The 4.1.0 guard itself does not false-positive on the new encoding: sm_get_size() matches the serialized length for all 10 shapes, 4 of them genuinely small-mode. That was checked first, since getting it wrong would make every small index raise a spurious corruption error.

Added

  • test/sql/similarity_multibyte.sql: the reporter’s statement, empty/identical/disjoint controls, 1- to 4-byte UTF-8 through all nine similarity entry points, and a 10,000-character input. In a normal build it cannot see the overwrite, which is silent there. It is load-bearing against an ASan server, which is how it was validated.
  • test/sql/sparsemap_smallset.sql: pure small-mode, promote/demote across the cap through VACUUM, and the RLE-run encoding, each checked against seq-scan truth through both amgettuple and amgetbitmap. It passes identically on a 5.6.0 control, so it does not detect the version. What it does catch is a size mismatch in the new encoding tripping the 4.1.0 guard (simulated against the library: the guard fires on it and stays quiet on healthy maps).

Qualified

Debian 12 / gcc 12 / PostgreSQL 18.0, EC2 c7i.4xlarge:

  • 47/47 regression tests; clean build, zero warnings (two pre-existing gcc 12 -Wshadow / unused-variable warnings removed).
  • TAP 17/17 – concurrency 2/2, crash recovery 10/10 across two kill -9 cycles plus Hanoi merge, replication 5/5 with standby promotion (8,187 s). The first attempt was killed by a 7,800 s harness timeout. That was not a hang: crash_recovery.pl checks each of ~1,060 committed batches with an indexed probe over a pending list of ~13,000 pages (3.5-4.9 s each), and the run needs about 2h15m on this EBS-backed rig. Timed per probe; the file is unchanged since 4.0.2. 4.1.0 took 5,379 s on the same instance type and the cause of the gap is not isolated – the sparsemap swap alone measured +2% per probe, too small to explain it.
  • Upstream sparsemap suite against the vendored copy: all 17 suites, including the five new in 5.7.0 – test_smallset_api (70,909 checks), test_rle_transitions (17,639), test_smallset_transitions (15,250, 8 mode crossings), test_equals_hash, test_offset_overflow – plus 175,543 coverage expectations. Upstream’s zero-warnings claim reproduced under -Wall -Wextra -Wpedantic -Wconversion -Wsign-conversion -Wshadow. SPARSEMAP_PREFIX: 85 prefixed symbols, 0 leaks.
  • Pending-list scan latency, sparsemap 5.6.0 vs 5.7.0 on the same pg_tre source: 415 ms vs 423 ms per probe on a 4,452-page pending list (+2%).

Acknowledgements

  • The downstream qualification team, for a report that named the exact call sites, was careful to label its root-cause lead as unvalidated, and asked for the multibyte and sanitizer coverage this release adds.

[4.1.0] - 2026-09-27 - vendored sparsemap v5.6.0 (security hardening) + corruption detection

Library-refresh release. The vendored sparsemap goes from v5.5.0 to v5.6.0, an upstream security-hardening release, and pg_tre gains the corruption detection that hardening makes necessary.

No on-disk format change and NO REINDEX required. The sparsemap wire format is unchanged (still version 2); every existing posting page is read identically.

Changed

  • Vendored sparsemap v5.5.0 -> v5.6.0, verbatim apart from the include path. Upstream fuzzed every decode and mutation path with untrusted input. What matters for pg_tre, in order:
    • sm_open / sm_open_copy now validate and reject malformed input, where before they trusted the bytes and a crafted chunk could crash a later sm_add. pg_tre reopens raw on-page bytes through both on every posting read, so this is the consequential change.
    • sm_validate is stricter: it rejects an RLE chunk whose length exceeds its capacity, a chunk start not aligned to the chunk width, start + capacity overflowing uint64_t, overlapping chunk spans, and a stored chunk count that disagrees with the walk.
    • Termination and amplification. A 24-byte input can legitimately declare a two-billion-bit run. sm_xor, sm_extract_range, sm_hash, the *_cardinality family, sm_jaccard_index, sm_equals, sm_compare and sm_subset_compare were O(set bits) and would hang for seconds on such input; they are now run-based and finish in microseconds.
    • Memory safety on valid-but-adversarial maps: a source over-read in sm_split, a non-terminating per-bit loop, a destination over-write, an out-of-range shift, plus two short-RLE mutation bugs found in upstream’s own qualification.
    • One NULL-map contract: nineteen public functions previously segfaulted on NULL and now return their documented failure value with errno = EINVAL.

Fixed

  • A corrupt on-page sparsemap is now detected instead of read as zero TIDs. sm_open() returns void and cannot report failure, so for bytes v5.6.0 rejects it substitutes an empty map. Unchecked, that turns a damaged posting into silently-wrong results — and if VACUUM reaches the leaf it repacks it as though it truly held no TIDs, making the loss permanent.

    All three read paths that use sm_wrap()+sm_open() now cross-check and raise ERRCODE_DATA_CORRUPTED with a REINDEX hint: the inline posting blob (the common case — most postings live inline in an upper leaf and never occupy a posting_leaf page), the out-of-line leaf serve path, and the vacuum repack path.

    The predicate is sm_get_size(map) != the length handed in, not sm_validate(). The sm_validate version was written first and measured useless: the substituted empty map is itself structurally valid, so sm_validate returns true on every corruption (0 of 4 detected). The size cross-check catches 4 of 4 — inflated chunk count, misaligned chunk start, RLE length > capacity, truncated mid-chunk — with 0 false positives across all nine map shapes pg_tre emits.

    Scope, stated plainly: with data_checksums on (the PG18 default) PostgreSQL reports on-disk damage first as invalid page in block N, so these guards are defence-in-depth. They were only observed to fire after explicitly running pg_checksums --disable; they cover checksums-off clusters and damage arising in memory after the checksum was verified.

Added

  • test/sql/sparsemap_corrupt_guard.sql asserts that a healthy index never trips the guard — across singleton, dense/RLE, sparse and multi-leaf postings, through the scan, the vacuum repack and the right-link walk. That is the property protecting the upgrade: if a future sparsemap tightens validation in a way that rejects pg_tre’s own output, this fails in CI rather than erroring in production.

Qualified

On a Debian 12 EC2 instance (gcc 12, PostgreSQL 18.0) — a different distribution and compiler from the usual Amazon Linux rig, which is itself useful coverage:

  • 45/45 regression tests; clean build, zero warnings.
  • TAP 17/17 — crash recovery across two kill -9 cycles, Hanoi merge, replication with standby promotion.
  • Cross-version read compatibility, the actual upgrade path: bytes written by the vendored v5.5.0 and reopened by v5.6.0 through both of pg_tre’s paths return identical cardinality across ten map shapes (single, 64/65 boundaries, dense, strided, wide-sparse, long-RLE, gapped, 20k dense).
  • Every map shape pg_tre produces passes the stricter validator (32 checks), so the new rejection cannot fire on our own output.
  • Upstream’s suite against the vendored copy: 44/44 API/scale tests, 175,541 coverage expectations, and the four new hardening suites — NULL contract (69 functions), S1 validate invariants, S3 split safety, S4 amplification (46 comparison pairs, 0 mismatches).
  • SPARSEMAP_PREFIX renaming intact: 85 prefixed symbols, zero unprefixed leaks.
  • The guard verified firing end-to-end in the server (checksums disabled), and silent on healthy data with checksums on.
  • Stress C/D/G/H/I/J: zero accuracy-oracle mismatches, scenario G still PASSing at 1.98x, parallel==serial hit counts (59,167), SuRF anchored-absent reject 0.070 ms, 0 stuck spinlocks.

Acknowledgements

  • The sparsemap project for the v5.6.0 hardening release.

[4.0.2] - 2026-09-13 - Index Scan dropped HOT-updated rows

Correctness fix. Upgrade if you use ~* or ILIKE on a table that gets UPDATEs. Scan-path only: no on-disk format change, no REINDEX (the index contents were always correct – REINDEX never helped). Loading the new .so corrects the answers.

Fixed

  • A plain Index Scan (amgettuple) silently under-returned rows, and the loss grew with heap churn.

    The always_true path – taken by ~* / ILIKE, which cannot be trigram-accelerated – streams every live heap TID and lets the executor recheck. It took those TIDs from heap_getnext(), which returns the current tuple version; after a HOT update that version is a HEAP_ONLY_TUPLE successor, not the chain root. heap_hot_search_buffer walks forward from the TID it is given and bails immediately if that TID is itself heap-only, so every HOT-updated row was handed over as an unreachable TID and discarded:

    heap state rows lost
    fresh index none
    1 no-VACUUM UPDATE t SET c = c pass 1 of 3
    3 passes 16 of 1,473
    reporter’s production heap (27.2M lifetime updates) 169 of 185

    Fixed as heapam_index_build_range_scan does it: a per-page HOT root map from heap_get_root_tuples(), translating each heap-only tuple to its chain root before emitting. The map is rebuilt if a tuple maps to InvalidOffsetNumber, since this scan holds only AccessShareLock and a concurrent HOT update can extend a chain underneath it. An unreachable root emits the tuple’s own TID rather than dropping it — the executor rechecks regardless, and a false positive is recoverable where a lost row is not.

    Bitmap Index Scans and sequential scans were never affected. amgetbitmap calls tbm_add_page() — whole blocks, no TIDs — so the index’s tuple-level decisions never reach the executor. If you worked around this by steering queries onto the Bitmap plan (e.g. lower()-ing the pattern), that is no longer necessary.

    Reported by the solnix.io infra team, who retracted two earlier framings of their own and then delivered a self-contained reproducer that localised it to scan path plus heap state. Both were right.

Added

  • test/sql/churned_heap_scan.sql, pinning the two axes the reporter asked for across three separate reports:
    1. scan path — every case runs under forced amgettuple and forced amgetbitmap, each required to equal the sequential-scan ground truth;
    2. heap state — the same index is checked fresh and after no-VACUUM UPDATE churn, with an assertion that relallvisible really dropped to 0 so the test cannot silently stop exercising the churned case.

    Verified load-bearing: with the translation compiled out the committed test reports 0 where the expected output says 3, and fails.

    This is the gap that let three rounds of the same class through. The casing-parameterised cases added in 3.2.5 all planned as bitmap scans, so they passed while the tuple-at-a-time path stayed broken — exactly what the reporter predicted would happen.

Qualified

EC2 c7i.4xlarge, PostgreSQL 18.0, no shared_preload_libraries:

  • 44/44 regression tests; clean build, zero warnings; flake builds pg_tre-4.0.2 on pg17 and pg18.
  • The reporter’s reproducer: ^git, ^GIT, ^gi, ^g, unanchored git all agree with the sequential scan on a 3x-churned heap (^g 1457 → 1473), and still agree after 13 total UPDATE passes with 72k dead tuples and relallvisible = 0.
  • TAP 17/17 — crash recovery, Hanoi merge and replication with promotion.
  • Stress C/D/G/H/I/J: zero accuracy-oracle mismatches, scenario G still PASSing at 1.98x, parallel==serial hits (59,167), SuRF reject 0.054 ms.

[4.0.1] - 2026-09-13 - merges abandoned the whole pre-merge tree (scenario G)

Storage fix. No on-disk format change, no REINDEX required.

Fixed

  • A pending-list merge abandoned every page of the pre-merge upper tree. A merge rebuilds the whole tree (snapshot_existing_upper + pg_tre_upper_bulkload) and swaps meta.root_upper to the new one, which makes the old tree’s upper leaves, coalesced pages and out-of-line posting chains unreachable. Nothing freed them, so every merge abandoned a full copy of the posting tier.

    The growth was unbounded rather than gradual. Churning 1% of a 60k-row table, index pages per round:

    round before after
    0 6,526 6,526
    1 13,150 13,150
    2 19,649 13,236
    3 26,115 13,236
    4 32,621 13,242
    5 39,113 13,245
    6 45,596 13,262

    Occupancy stayed flat at ~67% throughout, which is what identifies the extra pages as orphaned copies rather than data. After the fix: one orphaned copy from the first merge, reclaimed and reused thereafter, then flat. Five further churn rounds added 39 pages total, against ~6,500 per round before.

    This is the long-standing stress-scenario-G finding, and the harness’s own check now flips from CHECK: index >2x baseline — investigate reclaim to PASS: index within 2x baseline (bounded) at 1M rows (4,149 MB → 2,146 MB, 3.83x → 1.98x). The 3.2.6 pending-page fix addressed a different and much smaller leak; this is the one that produced the scenario-G number.

    Pages leaked by earlier versions are not retroactively reclaimed (nothing recorded which blocks they were). The next merge stops adding to the pile; REINDEX recovers the historical waste.

Added

  • DEBUG1 instrumentation on the plain Index Scan (amgettuple) path, which had none. That absence is why a field report of “plain Index Scan returns 0 rows while Bitmap on the same index returns 3” could not be localised from outside the process: EXPLAIN’s Index Searches: 0 is expected on this path (a case-insensitive predicate goes always_true and never descends the tree), so it carries no signal. The new lines report whether always_true was taken, the candidate cardinality and how many TIDs were emitted, separating “no candidates” from “empty heap stream” from “recheck filtered everything”. See doc/reports/amgettuple-2026-09.md.
  • test/sql/merge_page_reclaim.sql, asserting that growth is bounded (≤2.5x) and stops (later rounds add <5% of baseline). Verified load-bearing against a control build with the reclaim compiled out, which fails both invariants.
  • A scan-path axis in test/sql/surf_prefix.sql: every ~* / ILIKE case now runs under enable_bitmapscan=off (forcing amgettuple) and enable_indexscan=off (forcing amgetbitmap), both required to equal the sequential-scan ground truth. All 12 combinations pass. The casing cases alone could have stayed green while one scan path was broken — which is exactly what the reporter pointed out.

Still open

The amgettuple report itself does not reproduce. Eight axes were varied — casing, the reporter’s exact table shape, realistic nixpkgs-style names, their second index, a fully-merged pending list, long posting chains, in-place version upgrades, ILIKE — and the plain Index Scan matched the sequential scan every time. The DEBUG1 output above is what should localise it; doc/reports/amgettuple-2026-09.md says exactly which line means what.

Qualified

EC2 c7i.4xlarge, PostgreSQL 18.0, no shared_preload_libraries, wal_consistency_checking = 'all':

  • 43/43 regression tests; clean build, zero warnings; flake builds pg_tre-4.0.1 on pg17 and pg18.
  • TAP 17/17, All tests successful. Result: PASS — mandatory here because the fix touches the merge path’s WAL: crash_recovery 10/10 across two kill -9 cycles (821 catalog runs surviving replay), replication 5/5 including promotion.
  • Stress C/D/G/H/I/J: zero accuracy-oracle mismatches, G now PASSing, parallel==serial hits (59,167), SuRF reject 0.054 ms, 0 stuck spinlocks.

[4.0.0] - 2026-09-12 - no custom resource manager; no shared_preload_libraries

pg_tre now stores and WAL-logs its pages the way every other PostgreSQL index does: through the generic WAL facility (access/generic_xlog.h), instead of a custom resource manager.

The shared_preload_libraries = 'pg_tre' requirement is gone. That requirement never had anything to do with the index itself – it existed solely because RegisterCustomRmgr() must run during preload. CREATE EXTENSION pg_tre; is now sufficient.

The on-disk page format is unchanged and no REINDEX is required.

Breaking changes

  1. WAL written by 3.x cannot be replayed by 4.0.0, and vice versa. The records are no longer RM_PG_TRE_ID; they are generic-WAL records. For a normal upgrade of a cleanly shut down server this is a non-event, but:

    • shut the server down cleanly before swapping the library, so no 3.x pg_tre WAL is left to replay;
    • a physical standby cannot run a different pg_tre major than its primary. Upgrade the primary, then rebuild the standby from a fresh base backup. There is no rolling-upgrade path. Logical replication is unaffected.

  2. wal_consistency_checking = 'pg_tre' is now a FATAL startup error (“Unrecognized key word”), because that resource-manager name no longer exists. Use wal_consistency_checking = 'all'; generic WAL records are checked under the generic resource manager. Anything still setting the old value will prevent the server from starting, so this is not optional cleanup – every test, script and CI workflow in the tree was updated.

Removed

  • src/wal/xlog.c (327 lines of redo / desc / identify / startup / cleanup / mask), include/pg_tre/xlog.h, all XLOG_PTRE_* opcodes, RM_PG_TRE_ID, the RmgrData and its registration, and the redo-only pg_tre_pending_redo_apply_delta helper.
  • The hand-rolled pending-insert delta record. Generic WAL computes its own compact page diff, which is precisely what that record existed to do by hand.

Changed

  • WAL volume for insert-heavy workloads dropped 43%. Measured on 20k rows inserted in 1k batches (the pending-append path), median of three runs each: 1,054 bytes/row on 4.0.0 vs 1,863 on 3.2.6. This was the one thing the conversion plan flagged as a risk – removing a purpose-built delta encoder in favour of a generic one – and it went the other way. Generic WAL’s diff is simply better than the bespoke one, which only special-cased the tail page and shipped full-page images for everything else.
  • pg_tre_amvacuumcleanup honours info->analyze_only (a plain ANALYZE no longer performs a WAL-logged pending merge).

Fixed

Four bugs of one class were found during the conversion, every one of them “page written through the shared buffer instead of the generic scratch copy”, which makes generic WAL diff a page against its own already-mutated contents and ship an incomplete or empty record:

  • pg_tre_run_catalog_replace populated a freshly extended catalog page in the shared buffer before registering it – crash recovery would have silently lost the entire run catalog.
  • pg_tre_run_catalog_append wrote the catalog header before registration.
  • acquire_tail (full-tail path) page-init’d a new pending tail and wrote the old tail’s next_page link into shared buffers.
  • acquire_tail (first-page path) wrote pending_head/pending_tail outside any record. This one shipped an index that returned zero rows after crash recovery – 566,050 rows inserted, index empty, sequential scan fine.

Worth recording honestly: reading the code caught none of the four. The 42-test regression suite passed with the last and worst of them present. Only tap/crash_recovery.pl (kill -9 mid-write, then verify every committed batch through both the index and a sequential scan) found it, deterministically across three runs. Also fixed: gating the meta-page init on wal_log and calling GenericXLogAbort in the false branch, which discards the scratch page and left an all-zero meta page on temp/unlogged indexes.

Qualified

EC2 c7i.4xlarge, PostgreSQL 18.0, no shared_preload_libraries, wal_consistency_checking = 'all':

  • 42/42 regression tests; clean build, zero warnings; nix build .#pg17 and .#pg18 both produce pg_tre-4.0.0; nix flake check passes.
  • 17/17 TAP tests: All tests successful. Result: PASS – concurrency.pl 2/2, crash_recovery.pl 10/10 (two kill -9 cycles, 397 and 756 catalog runs surviving replay), replication.pl 5/5 including standby promotion.
  • Stress C/D/G/H/I/J: zero accuracy-oracle mismatches, identical parallel-vs-serial hit counts (59,167), DoS guards holding, SuRF anchored-absent reject 0.063 ms, 0 stuck spinlocks.
  • Verified that a cluster which never preloaded the library can CREATE EXTENSION, build an index and query it.

Scenario G’s churn bloat (3.83x) is unchanged and remains a separate, pre-existing issue – real posting_leaf growth at 91% occupancy, not leaked pages. Documented in LIMITATIONS.md.

[3.2.6] - 2026-09-12 - VACUUM leaked every consumed pending-list page

Storage fix. No on-disk format change, no REINDEX required.

Fixed

  • A pending-list merge freed nothing. VACUUM -> amvacuumcleanup -> pg_tre_pending_merge drained the pending list into the posting/upper trees, then advanced (or cleared) meta.pending_head and abandoned every page it had just consumed. The code was explicit about it – “Pages before it are orphaned (the pre-existing ‘rely on REINDEX to reclaim’ policy)” – which under steady insert traffic leaks the entire pending list on every merge.

    Reported by the solnix.io infra team while investigating something else: their index held 716 pending pages that VACUUM would not remove (5176 kB vs 1600 kB for identical data freshly built), and they asked how to drain it, assuming operator error. It was not: the entries merged correctly every time, the pages were simply never released.

    Consumed pages now go to the deferred free log – the same XID-gated path posting-leaf recycling already uses – and return to the FSM for reuse.

  • pg_tre_amvacuumcleanup ignored info->analyze_only, so a plain ANALYZE performed a full WAL-logged pending merge. PostgreSQL’s contract is that analyze_only means do not modify the index.

Added

  • test/sql/pending_reclaim.sql. Verified to fail with 319 leaked pages when the reclaim is disabled and pass with 0 after each of two merge cycles – a test that cannot fail on its target bug is not a test. It also asserts index-vs-sequential agreement after the merge, since freeing a page that is still reachable would be worse than the leak it replaces.

Not fixed by this

The churn bloat in stress scenario G is essentially unchanged (3.87x -> 3.83x) and is a separate problem. That growth is 522,346 posting_leaf pages at 91% occupancy – genuinely used pages produced by delete+reinsert churn, not leaked pending pages (only 1,387 of those, all from live traffic). Still documented in LIMITATIONS.md; REINDEX reclaims it.

Pages leaked by earlier versions are not retroactively reclaimed – there is no record of which blocks they were. The next merge stops adding to the pile; REINDEX recovers the historical waste.

Qualified

EC2 c7i.4xlarge, PostgreSQL 18.0: 42/42 regression tests, clean build with zero warnings, stress C/D/G/H/I/J with zero accuracy-oracle mismatches, identical parallel-vs-serial hit counts (59,167), DoS guards holding, SuRF anchored-absent reject at 0.066 ms.

[3.2.5] - 2026-09-11 - literal ‘-’ in a bracket expression was rejected

Scan-path fix. No on-disk format change, no REINDEX: patterns that previously ERRORed start working once the new .so is loaded.

Fixed

  • A literal - first or last in a bracket expression was rejected with pg_tre: invalid regex pattern instead of matching. POSIX makes - a range operator only between two members; first or last it is a literal, so [-_.], [abc-], [-] and [^-x] are all valid. The tokenizer emitted TOK_DASH unconditionally inside a bracket, leaving the grammar unable to reduce them.

    Found while reproducing a field report about casing: the reporter’s production word-boundary pattern is (^|[-_.])git([-_.0-9]|$), which contains two such classes, so every query in their regex ranking tier ERRORed on the index path. They had not isolated this and their report was about something else – it is a distinct bug, and the one actually affecting them on 3.2.4.

    Fixed in the tokenizer, where the positional context lives; a leading negating ^ is accounted for, and ranges are unaffected.

Changed

  • test/sql/surf_prefix.sql now parameterises the ~* / ILIKE cases over pattern casing (lower / UPPER / Title / mIxEd), per the reporter’s ask. The prior cases used only '^error' and '^ERROR'; their point that a casing-blind suite could stay green while a casing bug survives is correct in general, and cheap to close.

  • Assert(!st->q.always_true) added in the SuRF prefilter. A rejection is only sound because always_true was checked, so asserting it makes a future regression fail loudly in an assert-enabled build instead of silently returning an empty result set.

    Deliberately not an ereport(ERROR) (their ask #3): a genuinely absent prefix must still return zero rows, so erroring there would break correct queries. “Empty” is the right answer when the range is trustworthy; the bug was ever trusting it for a case-folded comparison.

Not a bug in 3.2.4

The reported symptom – ~* '^GIT' returning zero rows while ~* '^git' works – does not reproduce on 3.2.4, and the guard that prevents it has been present since 3.2.3. Reproduced their full index history (built and REINDEXed under a real 3.2.2 build, then ALTER EXTENSION to 3.2.4) and all four casings agree with sequential scan. Removing the 3.2.3 guard from the source reproduces their matrix exactly – lowercase OK, uppercase MISMATCH – which identifies what they are running: a binary without the fix.

Their infra/k8s/pg18-image/flake.nix pins pg_tre as git+https://codeberg.org/gregburd/pg_tre?submodules=1 with no ref, and its flake.lock holds b8bb8bb – pg_tre 3.0.1, from before the SuRF tier existed. Their pg18-exts-image correctly pins v3.2.4 (686d84b). Two images, two versions; the stale one serves the queries they tested. nix flake update pg_tre in that image, or pin it to a tag, resolves it.

[3.2.4] - 2026-09-11 - v3.2.3 could not be built via the flake

Packaging fix. Take this instead of 3.2.3. v3.2.3 fails to build via the Nix flake, so the correctness fix it shipped could not be consumed at all by Nix-based deployments. A make build from a git checkout was unaffected – which is exactly why it got past me.

No C, SQL, WAL, or on-disk change from 3.2.3; no REINDEX. If you are already running 3.2.3 this changes nothing functionally. If you could not install it, this is that release plus a buildable package.

Fixed

  • nix build .#pg18 failed in patchPhase on v3.2.3: the vendored TRE progress-hook patch no longer applied (lib/tre-compile.c hunk #2, lib/tre-match-approx.c hunk #2). Reported by the solnix.io infra team, who established it was our bug rather than their packaging by building our flake standalone.

    The patch was not stale – refreshing it, the obvious reading of the symptom, would have been the wrong fix. The flake avoids ?submodules=1 by pinning each vendored source as its own flake input, so every vendored rev has two sources of truth. The 3.2.3 TRE bump moved vendor/tre to upstream master and rebased the patch onto it, but left tre-src at the old v0.9.0 rev – so make used the real submodule and built fine while the flake fed the patch a tree the patch was never generated against. Now synced (and flake.lock updated).

  • The derivation was named pg_tre-3.0.2 on every release since 3.0.2. flake.nix hard-coded the version, so a failing 3.2.3 build reported pg_tre-3.0.2.drv and sent the reporter hunting a 3.0.2 problem that did not exist; it also made store paths collide across releases. The version is now parsed from pg_tre.control, so it cannot drift again.

Added

  • scripts/flake-check-revs.sh compares every flake input against the submodule gitlink it shadows and rejects a hard-coded version literal. Verified to fail on v3.2.3 and pass here – a check that cannot fail on the bug it targets is not a check.
  • scripts/release-check.sh now runs that comparison and nix build .#pg18. Building via PGXS is not evidence the flake builds: the two take different routes to the vendored tree and apply the patch with different tools (git apply vs patch(1)). This is the gate that was missing, and its absence is the whole reason 3.2.3 shipped broken.
  • The Codeberg (Forgejo) CI gained the flake-drift check. The GitHub mirror already had an equivalent one that would have caught this, but GitHub is a push-mirror and mirror syncs do not fire push events, so it never ran on the release – a limitation documented in that workflow’s own comments. The check now lives where CI actually executes.

Qualified

  • nix build .#pg18 and .#pg17 both succeed and produce pg_tre-3.2.4; nix flake check passes.
  • The reporter’s own reproducer was run against the nix-built artifact in an overlay-pkglibdir cluster: the extension loads (tre_version() -> pg_tre 3.2.4), and name ~* '^GIT' returns 3 via Index Scan using packages_name_tre, matching the forced sequential scan. Verifying the package builds and that the shipped fix works through that package is the step 3.2.3 lacked.

[3.2.3] - 2026-09-10 - SuRF prefilter returned zero rows for ~* / ILIKE

Correctness release. Upgrade if you use ~* or ILIKE with an anchored pattern. No on-disk format change and no REINDEX required: the bug is entirely in the scan path, so loading the 3.2.3 .so is what corrects the answers. If you already REINDEXed to work around it, that index is fine as-is.

Fixed

  • Index scans could silently return ZERO rows for case-insensitive anchored patterns (~* / ILIKE on a ^prefix). No error, no warning – just an empty result set for a query with real matches. Reported by the solnix.io infra team against 3.2.2; the defect dates to the v10 SuRF tier in 3.2.0 and affected every release since.

    amrescan marks the case-insensitive strategies always_true (the index stores trigrams case-sensitively, so these cannot be trigram-accelerated and must fall through to a lossy bitmap plus the executor’s recheck), but it does so after extraction has already recorded an anchored-prefix trigram-key range – and the SuRF prefilter consulted only that range. The range is built from the pattern’s literal codepoints with no case folding, so name ~* '^GIT' carried the key for "GIT" while the index legitimately stored only "git"; the filter correctly answered “no such key” and the scan returned nothing. Fixed in the shared prefilter, so both the bitmap and KNN paths are covered by one guard; extraction also no longer publishes a range it cannot justify. Read-path only: no on-disk change, no REINDEX.

    The acceleration is preserved rather than disabled – case-sensitive absent prefixes still short-circuit in ~0.06 ms.

    test/sql/surf_prefix.sql only ever exercised %~~ (case-sensitive), which is why CI stayed green through two releases; it now checks every ~* / ILIKE variant against its sequential-scan ground truth.

  • pg_tre_upgrade_index() now emits a NOTICE when it completes with no SuRF filter, explaining that a per-page walk cannot derive whole-index structures and pointing at REINDEX INDEX CONCURRENTLY. It previously returned cleanly and reported a uniform v10 format while leaving the filter unbuilt, which reasonably reads as “fully upgraded”.

Changed

  • Vendored TRE bumped to upstream master f864ed0, 18 commits past v0.9.0 (still the newest tag), for upstream’s hardening work: integer overflow on inputs past INT_MAX that could crash or return incorrect results, a hard regex-length limit and exponential stack growth, a backref backtracking-restart fix, and a bad xcalloc element size. patches/tre-progress-hook.patch – which is pg_tre’s compile/match timeout enforcement – was rebased onto the rewritten tree and its hooks verified still live (a silently orphaned hook would defang the DoS guards while leaving every test green). Upstream’s own suite passes with the patch applied: 107,091/107,091, no leaks.
  • tre_version() now reads the TRE version from the library at runtime instead of a hard-coded literal, which had kept reporting “TRE 0.9.0” as the submodule moved past that tag.

Qualified

Qualified on an AWS i4i.8xlarge (32 vCPU, 256 GB, NVMe RAID-0), PostgreSQL 18.0, built from a clean recursive clone of the tag. Full results in bench/stress/RESULTS-stress-3.2.3.md.

The primary gate is the reported scenario itself, not a synthetic test: an index was built with the actual released 3.2.2 (cloned from Codeberg at v3.2.2), the bug confirmed live on it (name ~* '^GIT' returned 0 via index vs 3 via sequential scan), then the 3.2.3 .so loaded and ALTER EXTENSION ... UPDATE run with no REINDEX against that same on-disk index: 0 -> 3, matching the sequential scan, with subsequent writes into the still-old-format index also correct.

  • 41/41 regression tests; clean build with zero warnings.
  • Every case-insensitive anchored shape agrees exactly with sequential scan at 1M rows (~* '^GOVERNMENT', ~* '^GoVeRnMeNt', ILIKE 'GOVERNMENT%' all 71,968; a genuinely-absent prefix still 0 – the fix is not “stop filtering”).
  • The acceleration is preserved, not disabled: anchored-absent reject p50 stays 0.060 ms at 1M rows, identical to the 3.2.2 baseline, and case-sensitive absent prefixes still short-circuit.
  • Stress C/D/E/G/H/I/J: zero accuracy-oracle mismatches throughout, identical parallel-vs-serial hit counts (59,167), 0 stuck spinlocks, compile bomb rejected in 0.00 s.
  • TRE’s timeout hooks counted rather than assumed (a silently orphaned hook would disable pg_tre.compile_timeout_ms while leaving every test green): compile abort honored, both matchers reached at 200,000 calls, abort short-circuits 200,000 -> 1. Upstream TRE’s own suite passes with our patch applied: 107,091/107,091, no leaks.

Note: ILIKE 'GIT%' did not reproduce the failure on 3.2.2 – its extraction reaches the prefilter differently – so an operator smoke-testing only with ILIKE would have seen a clean bill of health on a broken build.

The two pre-existing findings (super-linear build throughput; posting-leaf bloat under churn that REINDEX reclaims) reproduce unchanged and are unrelated to this release.

[3.2.2] - 2026-09-09 - vendored sparsemap v5.5.0 (upstream correctness release)

Library-refresh release. The vendored sparsemap goes from v5.1.1 to v5.5.0, an upstream correctness release. No SQL-surface, WAL, or on-disk-format change: the sparsemap wire format is unchanged (still version 2), so ALTER EXTENSION pg_tre UPDATE TO '3.2.2' is a metadata-only bump and no REINDEX is required. Existing indexes remain readable byte-for-byte.

The vendoring is verbatim: the only local delta is the include path (sm.h -> pg_tre/sparsemap.h). All seventeen sm_* entry points pg_tre consumes keep their v5.1.1 signatures, so no call site changed.

Fixed

Upstream fixed seven bugs, three of them data loss or corruption on ordinary inputs. Reachability from pg_tre’s own usage, honestly scoped:

  • sm_select returned an index that was not set at every multiple-of-64 rank on a dense range – the skip-ahead guard tested n > 64 instead of n >= 64, so n = 64 returned a position one past the slot it had just declined to leave. pg_tre does not call sm_select on the read path today, so no shipped query was affected.
  • sm_offset produced structurally corrupt maps: five independent append sites each chose their own chunk start, so maps could carry duplicate chunk starts, breaking the ascending-start invariant every reader assumes. Such a map failed sm_validate, could not be deserialized from its own serialized bytes, and a related defect could widen an RLE run over a later one, turning a gap into spurious set bits. pg_tre does not call sm_offset; the fix matters because “survives its own serialize/deserialize round trip” is exactly the property the on-page posting format depends on.
  • sm_difference silently discarded every surviving bit when both chunks were RLE (union and intersection each had an explicit both-RLE branch; difference did not). pg_tre uses sm_union and sm_intersection, not sm_difference, so no shipped result set was wrong – but this is the defect class a future posting-set subtraction would have inherited.
  • Big-endian hosts computed wrong answers for every counting and navigation operation since sparsemap v1.0.0. Ten sites read a packed 64-bit chunk descriptor by aliasing it with a uint8_t * and incrementing, which walks the 2-bit flags in reverse on big-endian. sm_contains was unaffected (it shifts the word directly), so the bug hid behind a working membership test while sm_cardinality, sm_minimum, sm_maximum, sm_rank, sm_select and sm_scan were all wrong. This does not affect pg_tre’s supported x86_64/aarch64 targets, but pg_tre leans on sm_cardinality and sm_next_member, so it removes a latent blocker for any big-endian port.
  • Also fixed upstream: sm_split overflowed a too-small destination instead of returning ENOSPC; sm_locator_rank / sm_locator_select crashed on a NULL locator; and sm_minimum / sm_maximum / sm_select disagreed with sm_contains about where a SM_PAYLOAD_NONE slot sits on maps opened from a foreign buffer.

Qualified

Re-qualified on an AWS i4i.8xlarge (32 vCPU, 256 GB, 2x3.75 TB Nitro NVMe RAID-0), Amazon Linux 2023, PostgreSQL 18.0 (-O2, no cassert). See bench/stress/RESULTS-stress-3.2.2.md.

  • Regression suite: 41/41 pass.
  • Upstream sparsemap suite run against pg_tre’s vendored copy: 44/44 API/scale tests pass, plus 175,530 coverage expectations with zero failures, and clean under ASan + UBSan. Targeted checks confirm all three data-loss fixes are present in the vendored file and absent in v5.1.1.
  • Accuracy oracle (index result set EXCEPT seq-scan result set, both directions): zero mismatches on every query in every scenario, including all 8 planted-token queries cold and warm against a 10M-row / 12 GB index with shared_buffers at 4 GB.
  • Adverse conditions: clean build-limit error (no PANIC), CIC under concurrent writes valid with 0 mismatches, cancellation honored in 0.08 s with no orphaned valid index, SIGKILL mid-build recovers via WAL replay with 0 PANIC/corruption and the heap fully intact, compile-bomb rejected in 0.01 s, and parallel vs serial builds returning identical hit counts (59167) with zero stuck spinlocks.
  • Upgrade path verified end-to-end, not just assumed: an index built under 3.2.1 (sparsemap v5.1.1) was read after ALTER EXTENSION pg_tre UPDATE TO '3.2.2' with no REINDEX, returning identical counts and zero oracle mismatches against a sequential scan, and then written to (insert + delete + VACUUM) with correct results. A clean from-source build produced zero warnings.

CORRECTION (2026-09-10). The “no REINDEX required / readable byte-for-byte” statement above is accurate about the sparsemap wire format, and the upgrade verification really was run – but it did not cover case-insensitive queries, and a pre-existing bug made ~* / ILIKE on an anchored prefix return zero rows on any index whose SuRF filter lacked the (unfolded) prefix key. Operators upgrading to 3.2.2 could therefore see silently empty results, which is what the claim was meant to rule out. The bug is a read-path defect dating to 3.2.0, not a format change: 3.2.2 neither introduced nor worsened it, and REINDEX “fixed” it only by building a SuRF containing the queried keys. See the Unreleased ### Fixed entry. The verification gap was mine: I A/B’d the sparsemap wire format thoroughly and treated “the upgrade” as synonymous with it, when the release’s actual risk surface was every query shape against an old index.

The two non-blocking findings from 3.2.1 (super-linear build throughput at scale; posting-leaf bloat under sustained churn that REINDEX reclaims) reproduce unchanged and remain documented in LIMITATIONS.md. They are pre-existing and unrelated to sparsemap.

Acknowledgements

  • The sparsemap project for the v5.5.0 correctness release.

Also in this release

  • bench/stress/stress-suite.sh: scenario F (SIGKILL mid-build) cleaned up orphaned processes by matching postgres.*$PGDATA, which misses parallel workers – they retitle to postgres: ... CREATE INDEX and carry no data-directory path. A surviving worker held the shared-memory segment and blocked the restart, so F reported a bogus recovery failure and every scenario ordered after it saw a refused socket. Cleanup is now by process group, and F runs last.

[3.2.1] - 2026-08-28 - at-scale stress qualification; sizing/maintenance findings

Qualification + documentation release. No C, SQL-surface, WAL, or on-disk-format change; ALTER EXTENSION pg_tre UPDATE TO '3.2.1' is a metadata-only bump (no REINDEX).

The 3.2 line was put through a full adverse-conditions stress suite (bench/stress/) on an AWS i4i.8xlarge (32 vCPU, 256 GB, 2x3.75 TB Nitro NVMe RAID-0), PostgreSQL 18, at 250k-10M rows. See bench/stress/RESULTS-stress-3.2.0.md.

Qualified

  • Correctness: the index-vs-sequential-scan accuracy oracle passed with zero mismatches on every query in every scenario at every scale.
  • Crash safety: SIGKILL mid-(parallel-)build recovers cleanly via WAL replay – heap 100% intact, no corruption, no orphaned valid index.
  • Graceful cliffs: temp-disk exhaustion, NFA/compile/statement-timeout, and cancellation all produce clean, cancellable errors – never a PANIC or hang. Build memory stays bounded by maintenance_work_mem even at 10M rows / 16 MB mwm.
  • Parallel builds: no stuck-spinlocks under saturation; parallel and serial builds produce identical results.
  • SuRF: anchored-absent reject stays ~O(1) (sub-millisecond) regardless of table size.

Documented (LIMITATIONS.md) – non-blocking sizing/maintenance findings

  • Build throughput is low and super-linear at scale (2M medium rows ~7 min, 10M >20 min): only the scan+sort phase parallelizes; posting/ upper/SuRF construction is serial and dominates. Budget build time, prefer the CONCURRENTLY variants, keep maintenance_work_mem generous.
  • Posting-leaf bloat under sustained churn: with row count held flat, a delete+reinsert workload grew the index ~3.9x; VACUUM reclaims only fully-emptied leaves (nbtree-style), so partially-empty leaves accumulate. REINDEX returns to baseline. Correctness is never affected; churn-heavy deployments should schedule periodic REINDEX INDEX CONCURRENTLY.

Added

  • bench/stress/ – committed, reproducible at-scale stress harness (provision NVMe EC2, generate scalable corpora, run scenarios A-J with an accuracy oracle), so future releases can re-qualify verbatim.

[3.2.0] - 2026-08-28 - SuRF range filter for anchored/prefix scans; range-bloom tier removed

Feature release. On-disk format bumps v9 -> v10 but stays backward-readable (PG_TRE_FORMAT_VERSION_MIN = 6), so ALTER EXTENSION pg_tre UPDATE TO '3.2.0' needs no REINDEX: a v6-v9 index reads unchanged and simply runs without the new filter. REINDEX (or a rebuild) populates the SuRF filter on an existing index.

Added

  • SuRF (Succinct Range Filter) tier for anchored / prefix scans. A from-scratch C reimplementation of SuRF-Base (Zhang et al., SIGMOD 2018) as a LOUDS-Sparse succinct trie – no external dependency, links only libc/libm and PG’s own popcount. It indexes an order-preserving trigram key (pg_tre_trigram_key_cp, 3 x 21-bit codepoints packed big-endian) so that a ^-anchored / LIKE 'foo%' pattern’s leading trigram maps to a contiguous key range. When that range contains no indexed trigram, a scan is rejected outright – without descending the posting tier or touching the heap. Measured on a 500k-row index: an absent anchored prefix returns in ~0.7 ms vs ~400 ms for a full anchored scan (~570x). The filter has a one-sided error contract (no false negatives), and the heap recheck remains authoritative, so it can never drop a true match. Validated with a 2.4M-check property test plus crash-recovery, parallel build, and differential (index vs seq-scan) tests on an assertion-enabled build.
  • tre_surf_stats(regclass) introspection: SuRF key count, trie node count, on-disk page count, and serialized image size.

Removed

  • The BRIN-style per-block-range bloom tier. It was built on every index but never consulted at scan time (the posting tier already yields exact candidate TIDs), so it was pure build-time and space overhead. The pg_tre.range_size_blocks GUC and the range_size_blocks reloption are retained but ignored (deprecated) so existing DDL/config keeps working. root_range remains a reserved meta field (always InvalidBlockNumber) to avoid a disruptive struct change.

Notes

  • The SuRF is a whole-index structure, so pg_tre_upgrade_index() (the in-place page-stamp upgrade) does not synthesize it; REINDEX to populate. Format-version dispatch now covers v3-v10.
  • The order-preserving key rides through the build’s coordinated tuplesort (the sort tuple grew from 20 to 24 bytes, reusing the dead position field), so serial and parallel builds produce an identical SuRF.

[3.1.0] - 2026-08-27 - recheck-cost fidelity, UTF-8 fuzzy correctness, AM hardening

Correctness + robustness release on the 3.0 lineage. On-disk format is unchanged (v9, PG_TRE_FORMAT_VERSION_MIN = 6); ALTER EXTENSION pg_tre UPDATE TO '3.1.0' is a version bump with no REINDEX.

Fixed

  • %~~ / <@> recheck now honors per-edit cost weights. A pattern built with tre_pattern(pattern, max_cost, cost_ins, cost_del, cost_subst) previously rechecked through the unit-cost path when driven by the index, so an indexed scan could return different rows than the equivalent tre_amatch(..., ci, cd, cs) function call. The operator recheck (tre_match_scalar) and the KNN distance pipeline now thread the pattern’s real costs through, so indexed and sequential results match for non-uniform-cost patterns.
  • Approximate (k>0) matching is UTF-8 codepoint-correct. The k>0 tiling spine slid a trigram window over raw UTF-8 bytes and dropped codepoints > 0xFF, producing trigram hashes that did not match how the index hashed the text (codepoint-based) — silently missing matching rows on CJK / accented text. The spine is now codepoint-based (pg_tre_uleven_expand_cp + pg_tre_hash_trigram_cp), so fuzzy queries over multibyte text agree with a sequential scan. (Soundness was always backstopped by the authoritative heap recheck; this fixes false negatives in the candidate set.)
  • PG18/PG19 build compatibility: run_catalog.c now includes utils/tuplestore.h and pg_tre/amapi.h now includes nodes/execnodes.h explicitly (both were transitive includes that newer/other PG builds dropped), fixing implicit-declaration and unknown type name 'IndexInfo' build errors.

Added

  • Real opclass validation (amvalidate). Replaces the previous always-true stub with checks that the opclass indexes text, every operator uses a known strategy (1 %~~, 2 <@> ORDER BY, 3–7 LIKE/ ILIKE/regex/iregex/eq) with the correct amoppurpose, order-by members name a valid sort family, and search operators return boolean.
  • KNN ORDER BY <@> mark/restore. ammarkpos/amrestrpos are implemented as an O(1) save/restore of the materialized result cursor, so plans that rewind over the distance-ordered output (e.g. a merge join) work correctly.

  • Parallel CREATE INDEX (amcanbuildparallel = true, pg_tre.enable_parallel_build on by default). A leader plus background workers divide the heap scan + trigram extraction + sort into one coordinated tuplesort; the leader merges every participant’s run and builds the posting/upper/range trees serially. Works for plain builds and CREATE INDEX CONCURRENTLY; the worker count is bounded by max_parallel_maintenance_workers. Two coordination bugs found and fixed under a debugger before enabling: the leader-wait loop held the DSM spinlock across ConditionVariableSleep (a self-deadlock that surfaced as a “stuck spinlock” PANIC at scale), and the CONCURRENTLY path passed the wrong scan snapshot / ii_Concurrent to the workers (an OldestXmin assertion in heapam). Verified on a 16-vCPU host: repeated 200k/300k/1M-row builds, concurrent builds, and CIC all produce byte-for-byte the same candidate sets as a serial build and a sequential scan.

  • Online format upgrade covers the full v6–v9 range. pg_tre_upgrade_index()’s per-page dispatch handled v3–v7 but errored (“page format upgrade from v8 not implemented”) on a v8 page from a 2.x coalescing-era index. v3–v9 non-range pages are byte-identical apart from the version stamp, so v8 is now handled like the rest; an in-place, no-REINDEX upgrade to v9 works from any supported prior format.

Changed

  • WAL critical-section consistency. The meta, upper, posting, and range page writers now wrap their MarkBufferDirty → XLogInsert → PageSetLSN sequences in START_CRIT_SECTION/END_CRIT_SECTION, matching the free-log / coalesced / run-catalog writers. No behavior change today; removes a latent torn-write hazard for future edits.
  • Removed dead code: the unreferenced pg_tre_upper_insert “Phase 4” stub (incremental upper-tree insert was never wired; the build uses bulk rebuild-on-flush).

Documentation

  • README, doc/design.md, and STATUS.md corrected to describe the actual scan path: a trigram posting tier (authoritative) plus a build-time BRIN-style range-bloom summary that is not consulted at scan time, and no per-tuple bloom tier (removed in 3.0.0). The prior “three-tier funnel” wording and the stale “in-memory build / will OOM” performance note (fixed by the 1.8.0 tuplesort build) were removed.

[3.0.2] - 2026-07-06 - installable extension packages in the flake

Packaging + documentation release. No C, WAL, SQL-surface, or on-disk-format change; ALTER EXTENSION pg_tre UPDATE TO '3.0.2' is a version bump with no REINDEX.

Added

  • The Nix flake now exposes the built extension per PostgreSQL major, mirroring pg_fts: nix build github:gburd/pg_tre#pg18 (also #pg17, #extension, #default) yields a PGXS-layout $out: $out/lib/pg_tre.so $out/share/postgresql/extension/pg_tre.control $out/share/postgresql/extension/pg_tre--<ver>.sql (+ upgrade scripts) The .so links only libc + libm (the vendored TRE is static), so it is ABI-portable into an official postgres:NN Docker image (overlay the three files into $(pg_config --pkglibdir) / .../extension/, then set shared_preload_libraries = 'pg_tre'). Requested by a downstream deployer running pg_tre alongside other extensions in a Kubernetes PG18 image.
  • The vendored TRE and Lime submodules are pinned as flake = false inputs at the same revs as the git submodules, so nix build works from a plain flake ref without ?submodules=1. Building the extension previously failed because flakes do not fetch submodules (empty vendor/tre made TRE’s ./configure die with a misleading “C compiler cannot create executables”, its stderr being redirected to /dev/null upstream), and because the Makefile’s git -C vendor/tre apply patch step needs a .git dir the Nix source lacks. Both are handled in the flake’s postPatch.
  • A CI lint step guards against the flake-pinned submodule revs drifting from the .gitmodules gitlinks.

Notes

  • README documents the flake build and the container-overlay deploy pattern.
  • Match the extension’s PostgreSQL major to the image’s PostgreSQL major.

[3.0.1] - 2026-07-06 - make %~~ scans cancellable

Code-only patch release. No SQL-surface, WAL, or on-disk-format change; ALTER EXTENSION pg_tre UPDATE TO '3.0.1' is a version bump with no REINDEX.

Fixed

  • %~~ tre_pattern(...) index scans now respond to query cancellation. A broad candidate scan over a large index ignored statement_timeout, client disconnect, and pg_terminate_backend, running for minutes stuck in heap I/O – on a busy host these un-cancellable scans piled up into a load spiral and a site-wide outage (reported from production, pg.ddx.io). Root cause: the per-candidate-row recheck (and the candidate-set build and bitmap-emit loops) had no CHECK_FOR_INTERRUPTS(), and PostgreSQL cancellation is cooperative. Added interrupt checks at the choke points – pg_tre_match_guarded() (every match on a heap value routes through it), the CNF/DNF conjunct loops in the candidate build, and the bitmap emit loops. Verified: an 8.5 s fuzzy %~~ scan now aborts at ~0.3 s under statement_timeout='300ms'. This makes statement_timeout – the standard mechanism – effective for tre scans, which is the right lever for bounding an expensive scan (no bespoke scan-budget GUC is needed).

Notes

  • Operator gotcha carried into the 3.0.0 -> 3.0.1 upgrade script: the per-tuple bloom removed in 3.0.0 means CREATE INDEX ... USING tre (...) WITH (tuple_bloom_enable=...) (and bloom_tuple_bits) is no longer accepted and will error – drop the clause from index-build scripts.
  • Selectivity for exact-substring (edit distance 0) still estimates from the rarest single required trigram, so a long literal whose trigrams intersect to near-nothing can be over-estimated and produce a broad candidate scan (the intersection is not modelled without co-occurrence stats). Tracked as a follow-up; with this release such a scan is at least cancellable. Wiring the already-built range-bloom tier into the scan (still unused) is the other lever tracked for candidate-set narrowing.

Acknowledgements

  • The pg.ddx.io / agora operator, whose production incident report and clean reproduction drove this fix.

[3.0.0] - 2026-06-25 - sparsemap v5, drop per-tuple bloom, coexist with pg_trgm

Major release. Three changes, two of them breaking the SQL surface or the fast-update payload layout; on-disk format bumps v8 -> v9 but stays backward-readable (PG_TRE_FORMAT_VERSION_MIN = 6), so ALTER EXTENSION pg_tre UPDATE TO '3.0.0' works with no REINDEX – old v6/v7/v8 indexes read unchanged.

Changed

  • Vendored sparsemap upgraded to v5.1.1 (verbatim from upstream). v5.0.0 shrinks sm_t from 32 to 24 bytes (the read cursor moved out of the struct into an explicit, optional sm_cursor_t * argument on sm_contains / sm_next_member / sm_prev_member; the allocation-lineage tag folds into m_capacity’s low bits); v5.1.0 widens the internal chunk count to 64-bit (removing the 232-chunk ceiling); v5.1.1 restores the O(N) bulk-insert guarantee (the v5.0 cursor-out-of-struct rewrite had reset the bulk cursor on every new chunk, which made building a large posting O(N2)). The on-disk wire format is unchanged (SM_WIRE_VERSION still 2), so serialized postings are byte-compatible – no REINDEX from the sparsemap bump. pg_tre uses sm_t only by pointer, so the struct shrink is transparent. Also picks up upstream sm_rank chunk-walk fixes and consumer-overridable intrinsics.

  • Index build is now O(N log N) instead of O(N2) on large/dense postings. The posting serializer fed TIDs to the sparsemap one at a time (re-walking the chunk directory per insert), and the member-iteration loops (range-tier bulkload, scan emitters, pending drains, vacuum repack) passed NULL read cursors (re-walking per member). With the per-tuple payload gone, dense postings pack far more TIDs per leaf, which tipped these into multi-minute CREATE INDEX hangs. The build now bulk-loads via sm_add_many_grow, sizes multi-leaf slices by a proportional estimate (a few probes, not a full binary search), and threads a read cursor through every hot member-iteration loop. Measured on a 40-hot-trigram corpus (index == seq-scan at every scale): 10k 0.6s, 30k 4.5s, 60k 10s, 100k 19s – previously a hang past ~60k.

  • pg_tre no longer creates the (text,text) similarity operators %, <->, <%, <<->, <<%, <<<->. They collided with pg_trgm’s operators of the same name/arg-types, which made the two extensions mutually exclusive in one database (the second CREATE EXTENSION failed). pg_tre and pg_trgm can now be loaded together. The behavior is still available through the distinctly-named functions that remain (tre_trgm_similarity(a,b), tre_word_similarity(a,b), tre_strict_word_similarity(a,b), and the tre_*_op / tre_*_dist_op helpers), or by loading pg_trgm for its % / <-> / etc. pg_tre’s own distinctive operators – %~~ (approximate regex) and <@> (edit-distance ORDER BY) – do not collide and are unchanged. The 2.1.0 -> 3.0.0 upgrade script drops the six operators from an existing install.

Removed

  • The per-tuple positional bloom / posting-leaf payload path is gone. Each posting-leaf entry previously stored, per (trigram, TID), the trigram positions plus a 128-bit bloom of the row’s trigrams, feeding a lossy tier-3.1 positional pre-filter. It is removed entirely: it never changed results (the executor recheck is authoritative), it saturated to a ~1.0 false-positive rate on document/body columns (every bit set), it was the majority of the index by bytes on such columns, and its build-time per-row-bloom hash table caused multi-hundred-second build timeouts at ~500k rows. Removing it:
    • GUCs pg_tre.tuple_bloom_enable and pg_tre.bloom_tuple_bits, and the matching index reloptions, are gone.
    • New posting leaves are sparsemap-only (payload_bytes = 0); the on-disk format bumps to v9. Old v8 payload-bearing leaves still read correctly (the payload is simply ignored).
    • Builds are dramatically faster and indexes much smaller on text-heavy columns; the >500k build timeout is resolved. The range bloom (per heap-block range, tier-1 skip) is kept.

Notes

  • Known, pre-existing: the range-bloom tier is built but not yet probed at scan time (pg_tre_range_lookup is unused) – tracked for a follow-up; it is not a regression (the scan never used it).
  • Upgrade from 1.6.0 / 1.12.0 / 2.0.4 / 2.1.0 is CI-verified; no REINDEX.

Acknowledgements

  • The pg.ddx.io / agora operator, whose 500k-row build timeout drove the bloom removal, and who needs pg_tre and pg_trgm co-loaded.
  • The sparsemap project for the v5.1.1 release.

[2.1.0] - 2026-06-22 - Phase 3: inline postings migrate out-of-line on vacuum

Minor release: a posting whose inline slot can no longer hold it after a dead-TID removal now MIGRATES to a dedicated posting leaf, instead of keeping the stale blob (2.0.4) or erroring (pre-2.0.4). No on-disk format, WAL, or SQL change; ALTER EXTENSION pg_tre UPDATE TO '2.1.0' is a no-op-for-data catalog upgrade (no REINDEX).

Changed

  • VACUUM repack now self-heals via out-of-line migration. Removing a TID from the interior of an RLE run can split it, so a sparsemap with fewer members can serialize a few bytes larger than the original. 2.0.4 made that safe by keeping the original inline blob (removing nothing) – correct, but the posting never shrank (the split is deterministic), so its dead TIDs were stuck until REINDEX. 2.1.0 instead writes the survivors to a dedicated posting leaf (full 8 KB budget, so the growth fits) and repoints the upper-tree entry out-of- line (posting_root = leaf, inline_bytes = 0). The dead TIDs are genuinely reclaimed; no REINDEX dependency.

    This is the inline analogue of the coalesced -> dedicated migration the merge path already performs, and a migrated entry is the ordinary out-of-line posting that every reader / vacuum / merge path already handles – hence no format change. Crash-safe: the new leaf is WAL’d (full-page image) before the upper-leaf entry-rewrite image; a crash between leaves the leaf orphaned (a harmless leak, reclaimed like any deferred-recycle page) and the entry still inline (correct), so a re-VACUUM migrates again.

    Verified on PG18: build with tuple_bloom_enable = off, churn with interior deletes to force the overflow, VACUUM -> the affected postings migrate to dedicated leaves (0 -> 21 in the test corpus), index results equal seq-scan across repeated churn+VACUUM cycles (no longer stuck). This fully closes the 2.0.4 known limitation: a dense, update-heavy index (built payload-off for size) reclaims dead TIDs on VACUUM.

Notes

  • Only the rare overflow postings migrate; each then occupies a dedicated leaf, a bounded size trade for correct, self-healing reclaim.

[2.0.4] - 2026-06-22 - fix vacuum repack overflow (clears the 2.0.3 limitation)

Bug-fix patch. No on-disk format, WAL, or SQL change; ALTER EXTENSION pg_tre UPDATE TO '2.0.4' is a no-op-for-data catalog upgrade (no REINDEX).

Fixed

  • VACUUM no longer errors with “inline vacuum repack overflow” / “vacuum repack overflow on block N”. Removing a dead TID from the interior of an RLE run can split it in two, so a sparsemap with fewer members can serialize a few bytes larger than the original. Both the inline (upper-leaf) and dedicated-leaf vacuum repack paths asserted “repacked <= original” and aborted VACUUM on violation, leaving the index unusable. This was the 2.0.3 known limitation: it is hit most easily by indexes built with the per-tuple payload off (pg_tre.tuple_bloom_enable = off), which removed the slack that masked it, but it was latent for payload-on indexes too.

    Fix: on overflow, leave the posting unchanged (keep the original blob / skip the in-place leaf rewrite) instead of erroring. Correctness-safe – the executor recheck is authoritative, so a retained now-dead TID is only a candidate that recheck filters (a superset, never a missed match); the dead TIDs are reclaimed on a later VACUUM or by REINDEX. The overflow check runs before any page mutation, so the bail-out leaves a consistent page. So a dense, update-heavy index (built with the payload off for size) is now safe to VACUUM.

  • Verified on PG18: build with tuple_bloom_enable = off + coalescing, then DELETE + VACUUM twice – no error; index results equal seq-scan across both cycles. New vacuum_repack regression locks this in.

[2.0.3] - 2026-06-21 - density blowup root-caused: per-tuple payload now controllable

Bug-fix patch for the v2.0.2 retest’s >10k-row density blowup. No on-disk format, WAL, or SQL-surface-removing change (one diagnostic function added); ALTER EXTENSION pg_tre UPDATE TO '2.0.3' is a no-op-for-data catalog upgrade (format stays v8, no REINDEX).

Root cause

The ~50x density blowup on a few-trigram / high-cardinality corpus was the per-tuple positional payload (positions + optional bloom) stored in posting leaves: ~22 bytes per (trigram, TID), uncompressed. On the field-report 30k-row corpus it was 13.3 MB of a 22.9 MB index (58%). It is a lossy tier-3.1 pre-filter – the executor recheck is authoritative, so it never affects query results – yet it was ON by default and gated by a PGC_SIGHUP GUC, so it could not be disabled per build. The “bimodal” 10k-vs-30k jump is just this payload crossing from inline into multi-leaf storage. (Localized with the new tre_page_kind_histogram() + a per-leaf payload tally on a real PG18 build.)

Changed

  • pg_tre.tuple_bloom_enable is now PGC_USERSET (was PGC_SIGHUP), so it can be toggled per session before CREATE INDEX. An operator who does not need the positional pre-filter can now build a dense index:

    SET pg_tre.tuple_bloom_enable = off;
CREATE INDEX ... USING tre (col);

    Verified on PG18: the field-report 30k corpus drops 22.9 MB -> 573 KB (763 -> 19 bytes/row, ~40x; denser than the pg_trgm GIN’s ~2,315 B/row), 10k vs 30k bytes/row stays bounded, and index results equal seq-scan. Default stays on for compatibility.

  • Multi-leaf posting partition packs by serialized size. Leaves were filled by a fixed tids = target / 8-bytes-per-TID estimate, which under-filled well-compressing postings (a dense trigram’s TIDs compress to <1 B/TID, leaving leaves ~2-6% full). Now each leaf is packed until its real serialized sparsemap reaches the target.

Added

  • tre_page_kind_histogram(regclass): read-only per-page-kind tally (count + used bytes + fill %) to localize where an index’s size lives.
  • density_scaling regression: builds a fixed-alphabet corpus at 10k and 30k with the payload off and asserts bytes/row stays bounded.

Known limitation

  • VACUUM of an index built with tuple_bloom_enable = off can hit inline vacuum repack overflow (an inline posting’s sparsemap, rebuilt after dead-TID removal, can exceed its original slot when it had no payload slack). Until the next increment migrates such a posting out-of-line instead of erroring, prefer building dense indexes that are not heavily updated, or keep the payload on for update-heavy indexes. Default builds (payload on) are unaffected.

Acknowledgements

  • The pg.ddx.io / agora operator, whose v2.0.2 retest pinpointed the

    10k-row blowup with a precise, reproducible repro.

[2.0.2] - 2026-06-19 - density, compaction reclaim, and the O(N2) flush fix

Bug-fix / performance patch addressing the two blockers from the v2.0.0 production field report. No on-disk format, WAL, or SQL-surface change; ALTER EXTENSION pg_tre UPDATE TO '2.0.2' is a no-op catalog upgrade (format stays v8, no REINDEX). All three v2.0 LSM/coalescing GUCs remain default-off; default behavior is byte-identical to 2.0.1.

Fixed

  • Flush/merge was O(N2) (the 50 s / 10k-row flush). materialize_merged_postings built each trigram’s sparsemap by inserting TIDs in pending-list / heap-scan order – effectively random per trigram. The sparsemap’s tail-chunk cursor only accelerates ascending inserts; random inserts fall back to a full chunk walk + byte-shift each, making the build quadratic. Fixed at the library level: sm_add_many now sorts a private copy ascending, and a new sm_add_many_grow is the growable bulk-build entry point the merge path uses. Microbench: 78x-623x faster, the gap growing with N (the O(N2) -> O(N) signature). Results identical (a sparsemap is a set).
  • Latent coalesced-page data corruption (false negatives). Widening the coalesce band (below) exposed a v2.0 bug: the single-ended coalesced-page writer placed slot 0’s blob where slot 1’s table entry would land, clobbering it, so a coalesced trigram could return 0 rows. Rewrote the writer to a two-ended (heap-page-style) layout; the reader is offset-driven so pages stay self-describing and v8-compatible.
  • VACUUM compaction grew the index instead of bounding it. Hanoi merge / collapse bounded the run count but orphaned the dropped runs' pages, which leaked until REINDEX. Added a crash-safe, XID-gated deferred page-free log (PG_TRE_PAGE_FREE_LOG, meta.free_log_head carved from reserved[] – meta size unchanged): a merge records dropped pages there after the catalog swap; amvacuumcleanup drains entries whose XID has aged past all scans.

Changed

  • Coalescing engages broadly now (denser index). The coalesce band was a narrow fixed (2048, 3072]; most medium/high-cardinality trigram postings fell through to one dedicated 8 KB leaf each (the ~26x size gap vs pg_trgm the report measured). The cap is now derived (pg_tre_coalesce_max(), ~4056 B = the “>=2 slots fit a page” boundary), so those postings pack 2-3 per coalesced page: 18-40% smaller index (corpus-dependent), still behind pg_tre.coalesce_enable.

Notes

  • The O(N2) fix lives in the vendored sparsemap (sm_add_many / sm_add_many_grow); it was made in the canonical sparsemap library too, which tracks a TODO to port it to the Rust sparsemap.
  • Throughput beyond the O(N2) fix (e.g. the structural Hanoi-merge cost on very large run counts) remains future work; the quadratic build was the dominant per-flush cost and is now linear.

Acknowledgements

  • The pg.ddx.io / agora operator, whose v2.0.0 evaluation pinpointed both the density and compaction blockers with exact reproductions.

[2.0.1] - 2026-06-19 - field-report fixes (reloptions, parallel build, run accounting)

Bug-fix patch from a v2.0.0 production evaluation. No on-disk format, WAL, or SQL-surface change; ALTER EXTENSION pg_tre UPDATE TO '2.0.1' is a no-op catalog upgrade (same format v8, no REINDEX). Query results are unchanged.

Fixed

  • Index reloptions were silently ignored. _PG_init() never called pg_tre_init_reloptions(), so the reloption kind stayed unregistered: every index storage parameter (fastupdate, pending_list_limit, q, bloom_tuple_bits, range_size_blocks, tuple_bloom_enable) was dropped with a WARNING: pg_tre: reloptions requested but not initialized, even under shared_preload_libraries. Per-index tuning now works. New reloptions regression test; p6_safety expected output updated to drop the obsolete warnings.
  • make -j race. The LLVM bitcode (.bc) targets did not depend on the vendored TRE ./configure step, so a parallel build could fail with tre-config.h: No such file or directory. Every object and its bitcode sibling now order-depends on the generated TRE config and the Lime grammar.
  • tre_run_catalog_status accounting. Flushed runs reported n_tuples = 0 because the value was assigned after the catalog record was written. The run’s distinct-TID count is now computed (union of the per-trigram TID sets) before the append; the Hanoi merge already sums source-run counts, so promoted runs report correctly too.
  • Nix flake pg_config resolution. On current nixpkgs pg_config is a split passthru output (postgresql_18.pg_config), so the hard-coded ${postgresql}/bin/pg_config did not exist; the dev shell now resolves it via the split output with a PATH fallback.

Acknowledgements

  • The pg.ddx.io / agora operator for a detailed v2.0.0 production evaluation that pinpointed all four issues with exact reproductions.

[2.0.0] - 2026-06-18 - adaptive-LSM substrate + posting-page coalescing

North star: pg_tre is a REGEX index with edit distance. Every change in this release is on-disk layout, write-path, or scan mechanics; none of it changes what the index matches. The executor recheck contract is untouched and query results are byte-identical (verified against sequential scan on Linux/x86_64 and FreeBSD/amd64).

Major version bump for the on-disk format change, but the format bump is v7 -> v8, ADDITIVE: NO REINDEX. v6/v7 indexes read unchanged (PG_TRE_FORMAT_VERSION_MIN stays 6; a coalesced page kind only appears in indexes built/rebuilt at v8, and old indexes never set the coalesced flag). ALTER EXTENSION pg_tre UPDATE from 1.6.0 or 1.12.0 is verified by the upgrade-tests CI matrix: the old-format index returns identical results after the upgrade with no REINDEX.

All three new behaviors ship off by default behind GUCs (pg_tre.flush_to_run, pg_tre.crack_on_read, pg_tre.coalesce_enable). The default build is byte-for-byte equivalent to 1.12.0. A/B benchmarking (bench/RESULTS-v2.0-ab.md) found them performance-neutral when enabled (no regression) but without a measured benefit on single-run workloads, so they remain gated until a multi-run workload demonstrates the LSM/crack upside.

Added

  • Adaptive-LSM substrate (Phase B1) – the foundation for “cracking” the index on the composable unit (the trigram), modeled on Hanoi leveling + adaptive collapse. All additive over format v7 (v6 reads as one implicit run, no REINDEX).
    • Run/level catalog: PgTreRun records (monotonic run_id, Hanoi level, roots, [min,max] trigram-hash run-skip filter), PG_TRE_PAGE_RUN_CATALOG page kind, meta fields next_run_id/run_catalog_head/n_runs/max_levels. Introspection via tre_run_catalog_status(regclass).
    • Multi-run scan: per-run posting resolution unioned with the pending overlay, gated by the run-skip filter; a single implicit run is byte-identical to the pre-v7 scan.
    • Crash-safe catalog writer (pg_tre_run_catalog_append, REGBUF_FORCE_IMAGE, one critical section) and flush_to_run GUC: drain the pending list into a new LSM run instead of merging into the base. Crash-validated by tap/crash_recovery.pl.
    • Adaptive compaction at VACUUM: incremental Hanoi level-merge (pg_tre_hanoi_merge) folds the shallowest over-capacity level into a promoted run; pg_tre_collapse_runs is the full-collapse backstop. Bounds run growth without an all-at-once fold. TAP-validated: 10 runs -> 2 after VACUUM, results unchanged.
    • Read-side crack cache (pg_tre.crack_on_read): per-scan, in- memory memoization of each query trigram’s union across runs. Result-identical, standby-safe, no disk write-back (durable crack deferred).
  • Posting-page coalescing, Phase 1 (pg_tre.coalesce_enable). See doc/specs/posting-page-coalescing.md.
    • New page kind PG_TRE_PAGE_POSTING_COALESCED (tag 9) packing multiple medium-cardinality trigram postings onto one page with an indirection table (PgTreCoalescedHeader + PgTreCoalescedSlot), addressed by a slot index in the upper-tree leaf entry’s inline_bytes (PG_TRE_COALESCED_FLAG).
    • Coalesced-page writer/reader (src/pages/coalesced.c), WAL- logged as a full-page image (validated run-catalog pattern).
    • The build path packs the medium bucket (PG_TRE_INLINE_POSTING_MAX < serialized sparsemap <= PG_TRE_COALESCE_MAX) when enabled; the read path resolves a coalesced slot at the single upper-tree lookup chokepoint, so materialize / scan / cardinality / lookup are unchanged.
    • tre_coalesced_page_count(regclass) diagnostic.
  • Format version bump v7 -> v8; pg_tre_upgrade_index accepts v7 and stamps v8 (no-op rewrite, byte-identical non-coalesced pages).
  • Self-contained A/B benchmark harness (bench/ab-bench.sh): builds pg_tre at HEAD and a prior release from source, runs its own ephemeral PG18 cluster (no root, no system install), and compares pg_tre-new vs pg_tre-old vs pg_trgm on build time, index size, latency, and an accuracy oracle (index result set == seq-scan). Realistic-corpus generator (bench/gen_corpus_realistic.py).
  • Regression coverage: flush_to_run, crack_on_read, run_catalog, coalesce, coalesce_vacuum, plus the crash_recovery.pl TAP for WAL-critical catalog/merge paths.

Fixed

  • Coalescing maintenance safety: ambulkdelete / posting_leaf_inline_delete / the merge snapshot path are now coalesced-aware. A coalesced upper-tree entry stores the coalesced-page block in posting_root and a (flag | slot) marker in inline_bytes; the prior code read those as a posting- tree root / blob length and would corrupt under VACUUM or merge with coalescing on.
  • Coalesced-page read crash: pg_tre_posting_materialize resolves the coalesced marker centrally (via pg_tre_coalesced_resolve_slot with a HASH_ANY sentinel), fixing a “page has kind 9, expected 5” error at CREATE INDEX in the range-tier build path.
  • Build temp-disk blow-up on repetitive text: per-row (trigram, tid) dedup in extract_trigrams collapses the sort input ~200x on repetitive corpora; build_max_entries_mb now meters real per-tuple cost. Added tre_estimate_index_build.
  • Regression suite was not actually gating in CI (shell/pipefail + missing superuser role + a || make check fallback); the suite now genuinely runs and gates on PG17 and PG18.
  • Upgrade-tests harness rebuilt: recursive clone of old tags (the source tarball carried no submodules) and a meaningful matrix (1.6.0, 1.12.0).

Deferred (not in this release)

  • Coalescing Phase 2-4: build-side bin packing (evaluated and skipped – ~2-3 slots/page, no FFD win), flipping the default, write-path slot-growth migration, and VACUUM reclaim of orphaned/dead coalesced slots (the maintenance paths are coalesced-aware but do not yet reclaim space).
  • B1.5 durable crack write-back (persisting the coalesced run so the next scan touches fewer runs): needs the lock-safe writer + standby/crash gate.
  • Phase B2: the gated 2-D visibility LSM.

Upgrade

  • From 1.6.0 / 1.12.0: ALTER EXTENSION pg_tre UPDATE TO '2.0.0'; no REINDEX (format additive, MIN stays 6). CI-verified.
  • From 1.0.x-1.5.x: those are format v3-v5; the sparsemap v5->v6 break (1.6.0) requires REINDEX after upgrading the SQL.
  • Restart the postmaster fully after installing the new .so (shared_preload_libraries = 'pg_tre').

Acknowledgements

  • TRE (Ville Laurikari) for the approximate-regex matcher.
  • The sparsemap design (Christoph Rupp) underlying the posting tiers.

[1.12.0] - 2026-06-05 - accurate selectivity (Phase A / A3)

North star: pg_tre is a REGEX index with edit distance. A3 makes the planner cost regex/LIKE predicates correctly so it stops choosing the index when a seq scan wins.

No on-disk format change; no REINDEX.

Fixed

  • %~~ selectivity was always rows=1, so the planner chose a pg_tre index for every predicate – including patterns matching most of the table, where a seq scan is far cheaper. This was the root cause of the field-report slowdown on non-selective queries.

Changed

  • tre_pattern_sel now reads real per-trigram posting cardinalities from the index (a new pg_tre_posting_cardinality walks the posting leaf chain, capped to bound plan-time I/O on hot trigrams) instead of a single global mean density.
  • For an exact (k=0) pattern, the trigrams of a literal co-occur, so the AND selectivity is the rarest required trigram’s selectivity (min_sel), not an independence product (which under-estimated by orders of magnitude). On the test corpus the estimates are now exact: common_tok -> 5000, rare_tok -> 100, unique_zzz -> 1, and the planner seq-scans the 50%-match pattern while index-scanning the 1-row pattern.
  • The duplicated estimator in the cost-estimate path is unified onto the shared pg_tre_estimate_trigram_selectivity.

Notes / honest limits

  • Fuzzy (k>0) selectivity is conservative, biased toward a seq scan. Edit-distance tiling expands a short pattern into thousands of variant trigrams that genuinely defeat pruning, so the estimate over-states matches rather than risk a slow index scan on a non-selective fuzzy query. Precise k>0 estimation is future work.
  • 25/25 regression (new test/sql/selectivity.sql asserts the plan-choice contract; planner_auto estimates improved from rows=1 to accurate counts).

[1.11.0] - 2026-06-05 - word_similarity / strict_word_similarity (Phase A / A2)

North star: pg_tre is a REGEX index with edit distance. A2’s Jaccard similarity exists only so a user can drop pg_trgm and keep its cheap similarity operators with the SAME numbers.

No on-disk format change; no REINDEX.

Added

  • tre_word_similarity(text, text) and tre_strict_word_similarity(text, text) – pg_trgm-compatible asymmetric word-boundary similarity. word_similarity(a, b) is the greatest trigram Jaccard similarity of a against any contiguous trigram extent of b; the strict variant pins extents to word boundaries. Faithful port of pg_trgm’s iterate_word_similarity over pg_tre’s codepoint trigrams.
  • Operators: <% (word_similarity >= threshold), <<-> (1 - word_similarity, distance), <<% (strict variant), and <<<-> (strict distance) – mirroring pg_trgm.
  • The % family honors pg_tre.similarity_threshold (1.9.0).

Verified

  • Numerically identical to pg_trgm across 15 varied pairs (substrings, multibyte café, case-folding, digits, empty strings, multi-word): zero mismatches. Examples: word_similarity('cat','category')=0.75, word_similarity('word','two words here')=0.8, strict_word_similarity('word','two words here')=0.5714286.
  • 24/24 regression (new test/sql/word_similarity.sql).

Notes

  • These are functional/operator semantics only; KNN over Jaccard (index-assisted ORDER BY col <-> 'x') is a later item.
  • Combined with A1 (1.10.x) and A2 similarity (1.9.0), a single pg_tre index now backs LIKE/~/=, and the full pg_trgm similarity operator set (%, <->, <%, <<->, <<%, <<<->) is available. Remaining Phase A: accurate {~k} selectivity (A3).

[1.10.1] - 2026-06-05 - LIKE/ILIKE/regex/= index acceleration (Phase A / A1)

North star: pg_tre is a REGEX index with edit distance. A1 lets the planner use a pg_tre index for the operators people actually type – LIKE, ~, = – by lowering them into the SAME trigram engine %~~ already uses. No new matcher; the executor rechecks with the built-in operator.

No on-disk format change; no REINDEX.

1.10.0 was tagged on an incomplete commit; 1.10.1 re-ships the complete A1 release under a clean tag. There is no catalog or format difference between a correctly-installed 1.10.0 and 1.10.1.

Added

  • LIKE / ~ / = are now index-accelerated. The tre_text_ops operator family binds the built-in text pattern operators as strategies 3-7 (~~, ~~*, ~, ~*, =). A query like col LIKE '%foo%', col ~ 'fo+o', or col = 'foo' now plans as an index scan on a pg_tre index. Each pattern is lowered to the trigram engine at k=0 (LIKE -> regex via % -> .*, _ -> ., escape handling; = -> anchored literal regex); the executor rechecks with the built-in operator (textlike/textregexeq/texteq), so the index is a lossy candidate filter and results are exact. Verified index-result == seq-scan ground truth.
  • New src/query/like_translate.c (LIKE/literal -> regex) and the strategy-dispatched pattern acquisition in amrescan and amcostestimate.

Notes / honest limits

  • ILIKE and ~* are correct but not accelerated. The pg_tre index stores case-sensitive trigrams, so a case-insensitive query would miss real matches if trigram- filtered. These strategies force the always-true (full recheck) path: correct, but no faster than a seq scan. A case-folded index that would let them accelerate is future work.
  • Sub-trigram patterns (e.g. LIKE '%xy%') fall back to full recheck, identical to pg_trgm’s behavior.
  • This is A1 of the pg_trgm-replacement roadmap; combined with A2’s similarity (1.9.0), a user can now drive LIKE/~/=, %, and <-> off a single pg_tre index. Remaining Phase A: word_similarity and accurate {~k} selectivity (A3).

[1.9.0] - 2026-06-05 - pg_trgm-compatible similarity (Phase A / A2)

North star: pg_tre is a REGEX index with edit distance. This release adds capability parity with pg_trgm’s cheap similarity so users can drop pg_trgm and keep %, <->, and the similarity threshold – it does not change what pg_tre is.

No on-disk format change; no REINDEX. ALTER EXTENSION pg_tre UPDATE TO '1.9.0' adds the new functions/operators.

Added

  • Trigram-set (Jaccard) similarity, numerically identical to pg_trgm: tre_trgm_similarity(text,text) -> float4, tre_trgm_distance(text,text) -> float4 (1 - similarity), the text % text threshold operator, and the text <-> text distance operator. These replicate pg_trgm’s exact trigram model (lowercase, alnum-word split, 2-leading/1-trailing-space padding per word, deduplicated set) over UTF-8 codepoints. Verified numerically equal to pg_trgm.similarity() across a range of inputs (foo|foobar=0.375, hello|hallo=0.333, abc|xyz=0, cat|category=0.3, …).
    • These are cheap and stateless and distinct from pg_tre’s edit-distance tre_similarity / <@>. A user porting col % 'x' or ORDER BY col <-> 'x' from pg_trgm gets the same numbers.
    • By design these operators collide with pg_trgm’s own %/<-> if both extensions are installed: pg_tre replaces pg_trgm; the two are not meant to co-exist.
  • pg_tre.similarity_threshold GUC (PGC_USERSET, default 0.3, range 0..1), mirroring pg_trgm.similarity_threshold; the % operator honors it.

Notes

  • This is the first piece of the documented pg_trgm-replacement roadmap (doc/specs/roadmap-pg_trgm-replacement.md). Still to come in Phase A: LIKE/ILIKE/~/= index acceleration (A1) and accurate {~k} selectivity (A3). Index-side acceleration of <->/% is a later refinement; A2 delivers the functional and operator semantics.

[1.8.2] - 2026-06-05 - green CI on tags (release-publish permission)

No extension/format/behavior change from 1.8.0/1.8.1; no REINDEX. Continues closing the tag-CI gap: after 1.8.1 fixed make dist, the tag release-artifacts job built the tarball but the GitHub release-publish step 403’d because the default GITHUB_TOKEN is read-only. Grant permissions: contents: write and make the publish step best-effort (this repo’s canonical releases are the Codeberg tags; GitHub is a mirror). The tarball build remains the packaging gate.

[1.8.1] - 2026-06-04 - release-pipeline fix (green CI on tags)

No extension code, on-disk format, or behavior change from 1.8.0 (the compiled .so is byte-identical apart from the version string); no REINDEX. This patch exists solely to make the tag-triggered release pipeline pass.

Fixed (CI)

  • The tag-only release-tarball job (make dist) aborted on Makefile:157: pg_tre requires PostgreSQL 17 or newer; found 16 because that job’s runner pg_config is PostgreSQL 16 and the Makefile’s version guard runs on every target. Every tag push (1.6.1, 1.7.0, 1.8.0) therefore showed a red CI run even though the build/test matrix, sanitizers, and pgspot were all green on the corresponding main push. make dist is pure git archive + tar + gzip and needs no PostgreSQL, so the version guard is now skipped when every requested goal is PG-independent (dist/clean/distclean); a bare make build and make install still enforce PG17+.

Process note: 1.6.1/1.7.0/1.8.0 were tagged with local qualification green but the tag CI red (this packaging job). That gap is what this release closes; going forward a release is not considered done until the tag’s CI is green.

[1.8.0] - 2026-06-04 - tuplesort-based build: bounded memory at scale

No on-disk format change (still v6); same indexes, no REINDEX. The structural fix for the field-report OOM: index builds no longer hold the whole trigram-emission set in RAM.

Changed

  • ambuild now sorts trigram tuples with PostgreSQL’s tuplesort instead of an in-memory array + qsort. Each (trigram_hash, tid, position) tuple is encoded as a fixed 20-byte big-endian bytea whose memcmp order reproduces the historical (hash, packed_tid, position) order exactly, then fed to tuplesort_begin_datum(BYTEAOID, ...). Peak build memory is now bounded by maintenance_work_mem (tuplesort spills to temp files), not by corpus size.
    • Measured: a 200k-row / ~80M-emission body corpus builds under maintenance_work_mem = 32MB with peak backend RSS 231 MB; the same corpus at half the size (100k / ~40M emissions) peaks at 219 MB – i.e. flat across a 2x corpus, where the old in-memory build would have grown from ~960 MB to ~1.9 GB of resident entries[] alone. Correctness verified (index result == seq-scan ground truth, exact and k=1).
    • This directly resolves the field-report failure where a body-column build OOM-killed the postgres cgroup. Set maintenance_work_mem to taste; larger values trade RAM for fewer merge passes / faster builds.
  • pg_tre.build_max_entries_mb default changed 4096 -> 0 (disabled). Its original job – prevent the in-memory OOM – is now done structurally by tuplesort, and a non-zero default would wrongly block large-but-legitimate builds (e.g. the 500k-body case from the field report). The GUC remains as an optional temp-disk safety valve: set it to cap the emitted-tuple count (x24 bytes) and fail cleanly with ERRCODE_PROGRAM_LIMIT_EXCEEDED rather than filling the temp tablespace.

Notes

  • The remaining build-time per-row memory is the tid-bloom hash (one entry per distinct TID, ~56 B/row), which is O(rows) not O(emissions) – ~12 MB of the 219->231 MB delta above. It is far smaller than the former entries[] term and only matters at very high row counts; bounding it is a possible future refinement, not a blocker.
  • CREATE INDEX CONCURRENTLY / REINDEX CONCURRENTLY (verified in 1.7.0) compose with the bounded-memory build: a concurrent rebuild of a large body column is now both lock-light and memory-safe.

Verified

  • 21/21 regression; wal_audit.sh 3/3; replication.sh 4/4.
  • 80M-emission build under 32 MB maintenance_work_mem; peak RSS flat across a 2x corpus; result correctness vs seq scan.

Qualified locally; GitHub CI verification still pending at tag time (1.7.0 had a CI failure that needs a separate look) – do not treat this as CI-green until confirmed.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.7.0] - 2026-06-04 - cancellable builds, memory ceiling, CIC verified

No on-disk format change (still v6); same indexes, no REINDEX. Directly addresses the two operational failures from the 1.6 field report (see LIMITATIONS.md).

Added

  • pg_tre.build_max_entries_mb (PGC_USERSET, default 4096, GUC_UNIT_MB, 0 = unlimited). The build’s in-memory trigram-entry array grows with total trigram emissions, not distinct trigrams, so large natural-text columns could exhaust memory and get the postgres process SIGKILLed by the OOM killer. When the array would exceed this ceiling the build now fails with ERRCODE_PROGRAM_LIMIT_EXCEEDED and an actionable hint – the server stays up. The ceiling is enforced at both the initial allocation and every doubling. Verified: a 4 MB cap on a 20k-row build errors cleanly; the default lets normal builds through.

Changed

  • Index builds are now cancellable throughout. The sort over the entries array uses qsort_interruptible (PG18) instead of qsort; combined with the existing CHECK_FOR_INTERRUPTS in the per-TID sm_add_grow loops and multi-leaf write paths, pg_cancel_backend() / SIGINT during a build is honored within ~a second on any phase. Previously the pg_qsort step (5-60s on a large corpus) and the posting-build loops were uncancellable, which is why a stuck REINDEX held its lock for minutes in the field report.

Fixed (documentation)

  • CREATE INDEX CONCURRENTLY / REINDEX CONCURRENTLY are supported and verified. CIC/RIC are generic in PostgreSQL (no per-AM flag gates them); pg_tre’s build is correct under the two-phase MVCC-snapshot protocol, confirmed by a CIC-result == seq-scan-ground-truth cross-check and a RIC round-trip. The 1.6.1 docs incorrectly said “not yet supported” (based on a mis-diagnosed, non-existent amcanbuildconcurrently flag); README and LIMITATIONS.md are corrected. Using the CONCURRENTLY variants avoids the heavy build lock that stalled ingest in the field report – this is the recommended path for rebuilding pg_tre indexes on a live table.

Still pending (v1.8.0)

  • A tuplesort-based build that bounds peak memory by maintenance_work_mem (disk-spill, like btree/gin/gist). 1.7.0 makes the OOM a clean error and the lock avoidable; 1.8.0 makes large body-corpus builds actually fit in bounded memory.

Verified

  • 21/21 regression; wal_audit.sh 3/3; replication.sh 4/4.
  • CIC + RIC correctness cross-check.
  • Bounded-memory guard fires cleanly without OOM; server survives.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.6.1] - 2026-06-04 - documentation honesty about scale limits

Documentation-only release. No extension code changes; same on-disk format as 1.6.0; no ALTER EXTENSION work; no REINDEX.

What and why

A production user (501 k-row email-archive, see LIMITATIONS.md for the field report) hit two operational failures on the 1.6.0 REINDEX path:

  1. Lock-hung REINDEX on a 501 k-row text column for ~6 minutes, blocking ingest – the build path has uncancellable stretches inside pg_qsort, the inner sm_add_grow loops, and the multi-leaf write paths.
  2. OOM-killed the postgres cgroup while building a body-text index – ambuild collects every trigram emission in memory (bstate->entries[], repalloc_huge-grown), so peak RSS scales with total_emissions, not distinct_trigrams. ~6 GB is normal for 500 k email bodies. The 1.6.0 sparsemap fix removed the silent data-loss overflow, but does not address the resident-set model.

Neither failure is a 1.6.x regression; both have been latent since at least 1.4.x. But the README and CHANGELOG implied production-readiness at scales where the build is not viable, and the user reasonably tried it. This release closes that gap in words; 1.7.0 addresses cancellability and a bounded-error build ceiling, 1.8.0 introduces a tuplesort-based build that actually scales.

Documentation

  • New LIMITATIONS.md at the repo root: explicit sizing table, upgrade/REINDEX guidance, and the verbatim field report.
  • README: prominent Scale limits callout under Features, build-memory note + Deployment recommendations under Performance, and a corrected feature claim – the bullet that said REINDEX CONCURRENTLY safe was wrong (amcanbuildconcurrently is false today; CIC/RIC fall back to the lock-heavy form).
  • doc/perf.md: new “Build memory model” section with the per-emission formula and a sizing table.

Operator guidance

For heaps where 1.6.0’s REINDEX is not viable, the recommended path is DROP INDEX + recreate during a maintenance window with generous maintenance_work_mem – and first reconfirm whether the column actually warrants pg_tre at all. Email-archive style workloads are typically better served by pg_trgm GIN + tsvector BM25 with pg_tre reserved for true edit-distance/regex fuzzy matching over an already-narrowed subset. See LIMITATIONS.md for details.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.6.0] - 2026-06-04 - sparsemap 4.0.0: data-loss fix (REINDEX REQUIRED)

Breaking, correctness-critical release. On-disk format bumped to v6; indexes built by pg_tre < 1.6 must be REINDEXed.

Why this is mandatory

The vendored sparsemap is updated to 4.0.0, which widens the per-chunk start offset in the serialized format from 32 to 64 bits (sparsemap SM_WIRE_VERSION 1 -> 2). The 32-bit offset silently lost data for sparsemap indices >= 232. pg_tre packs heap TIDs as (block << 16) | offset, so any heap larger than ~512 MB (> 65536 blocks) reaches indices >= 232 – meaning pg_tre indexes on large tables under pg_tre < 1.6 could silently miss rows. 4.0.0 fixes the bug; REINDEX regenerates correct index data.

Upgrade

ALTER EXTENSION pg_tre UPDATE TO '1.6.0';   -- after installing the new .so
REINDEX TABLE your_table;                    -- rebuild every pg_tre index

The sparsemap 4.0.0 wire format is intentionally not backward-readable (sm_deserialize returns NULL on the old format), so there is no online in-place migration: REINDEX is the migration and the data-loss remedy. pg_tre_read() rejects pre-v6 pages with ERRCODE_FEATURE_NOT_SUPPORTED and a REINDEX hint, so an un-rebuilt index fails loudly on first scan rather than returning wrong rows.

Changed

  • Vendored sparsemap 4.0.0 (sm.c/sm.h) via the upstream contrib/pg_tre_sync.sh. Adopted the new public type name sm_t at all pg_tre call sites (sparsemap 4.0.0 renamed sparsemap_t -> sm_t); no compatibility alias.
  • Namespaced the embedded sparsemap with -DSPARSEMAP_PREFIX=__tre_ so every public sparsemap symbol is emitted as __tre_sm_* (76 functions). This prevents link-time collisions if another library in the same backend also vendors sparsemap. Compile-time only; the serialized wire format is unchanged.
  • PG_TRE_FORMAT_VERSION_LATEST and ..._MIN are both 6.

Verified

  • 21/21 regression tests pass.
  • wal_audit.sh 3/3; replication.sh 4/4.
  • New indexes report on-disk format v6 (pg_tre_index_format_status).
  • The >= 232 data-loss fix is covered at the sparsemap layer by upstream tests/test_large_index.c; a full >512 MB pg_tre large-heap test is recommended for the nightly lane (too slow for the regression suite).

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.5.8] - 2026-06-03 - sparsemap 3.0.1, version-string fix, CI green

Maintenance release. Same on-disk format as 1.5.7 (PG_TRE_FORMAT_VERSION = 5); the vendored sparsemap update is wire-compatible (byte-identical serialized format), so existing indexes built by 1.3.0 .. 1.5.7 remain readable. Upgrade is online and needs no reindex:

ALTER EXTENSION pg_tre UPDATE TO '1.5.8';

(after installing the new shared library). Verified end-to-end: an index built under 1.5.6 returns identical results after ALTER EXTENSION ... UPDATE TO '1.5.8' with no reindex.

Changed (library)

  • Vendored sparsemap updated to 3.0.1 (from the upstream ports/rust branch’s consolidated C library, sm.c/sm.h). The portability shims that previously lived in sm_portability.h / popcount.h are now folded into the implementation, so include/pg_tre/sm_portability.h is removed. Synced via the upstream contrib/pg_tre_sync.sh. The serialized format is unchanged (wire-compatible), so no index rebuild is required.
    • NOTE: 3.0.1’s sm.h renamed the public type sparsemap_t -> sm_t. All 82 sm_* functions are unchanged. pg_tre keeps the historical spelling working with a one-line typedef struct sparsemap sparsemap_t; compatibility alias in the vendored header (reported upstream: the branch’s own pg_tre_sync.sh advertises a clean drop-in, which the rename breaks).

Fixed

  • tre_version() reported the wrong version. PG_TRE_VERSION_STRING in include/pg_tre/pg_tre.h had drifted to "pg_tre 1.5.6" and scripts/bump-version.sh only rewrites it when the current string matches the OLD version, so the constant was never corrected across the 1.5.6 -> 1.5.7 bump. Shipped 1.5.7 therefore reported tre_version() = 'pg_tre 1.5.6'. Corrected to 1.5.8; future bumps now track it via the existing common-files substitution.

Fixed (CI)

  • pgspot Security Check was red on four PS017 (“unqualified object reference”) warnings for pg_tre’s own %~~ / <@> operators and the tre_pattern type, referenced inside the extension’s own install script. These resolve at CREATE EXTENSION time and operators cannot be schema-qualified in operator-class / cast DDL, so PS017 is a false positive here. Added --ignore PS017 to both pgspot invocations.
  • Nightly stress died at dependency install with E: Unable to locate package postgresql-18-pgwalinspect. pg_walinspect is a contrib module bundled in the postgresql-NN server package on PGDG; there is no separate -pgwalinspect apt package. Removed the bogus name; CREATE EXTENSION pg_walinspect still resolves.
  • Sanitizer build failed at vendor/tre/configure ... Error 127: TRE’s autogen.sh calls autopoint(1), which on Ubuntu is a separate package from gettext. Added autopoint to the sanitizer and nightly apt lists (the main CI job already had it).
  • Added vm.mmap_rnd_bits=28 + kernel.randomize_va_space=0 to the ASan jobs for the Ubuntu 24.04 runner ASLR/ASan shadow-memory interaction.

Changed (CI)

  • The two ASan workflows (the from-source PG-with-ASan build, and the nightly asan matrix leg) are now continue-on-error (informational). Both fail in the ASan/PostgreSQL toolchain environment – the instrumented postgres aborts in initdb’s own bootstrap, and a stock server cannot start with an ASan-instrumented module preloaded – not in pg_tre, and they have never passed. The blocking CI (main CI matrix + regression tests, pgspot, nightly plain leg) is green. A proper ASan+PG recipe is tracked as a follow-up.

Verified

  • 21/21 regression tests pass on the release tree.
  • wal_audit.sh 3/3; online upgrade 1.5.6 -> 1.5.8 returns identical results with no reindex.
  • Main CI workflow and pgspot green on GitHub.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.5.6] - 2026-06-01 - multi-level pending merge, posting-merge speedup, compile-timeout enforcement

Robustness + DoS-hardening release on the 1.5.0 lineage. No on-disk format change (remains v5); no REINDEX required. Upgrade script 1.5.5--1.5.6 is a no-op stub that only bumps the recorded extension version.

Fixed

  • Pending-list merge now supports a multi-level upper tree. Once an index accumulated enough distinct trigrams that VACUUM had to build an upper internal page (page_kind=2) fanning out to many upper leaves, the next pending merge raised ERROR: pg_tre: pending-list merge on multi-level upper tree not yet supported and demanded a REINDEX — the merge snapshot could read back only a single upper leaf. The snapshot path (snapshot_existing_upper) now descends the whole upper subtree recursively (collecting child blocks under lock, releasing, then recursing — never holding more than one upper buffer locked), so subsequent inserts merge cleanly with no REINDEX. The bulk-load and lookup paths already handled multi-level trees; this was a read-side gap in the merge snapshot only.
  • materialize_merged_postings no longer spins O(TID-range). The on-disk-leaf merge branch probed every integer in [min_idx, max_idx] with sm_contains, burning ~100% CPU for minutes when a trigram’s TIDs spanned a wide range. It now iterates set members in rank order via sm_next_member (O(cardinality)).

Security

  • pg_tre.compile_timeout_ms is now enforced. The GUC was previously defined but never honored — only match_timeout_ms and max_nfa_states bounded cost, and max_nfa_states is checked only after the automaton is built, so a pathological nested bounded repetition (e.g. a{80}{80}{80}) could expand for seconds before any cap applied. A progress hook woven into TRE’s NFA-build loops (the bounded-repetition AST expansion and the tag/copy/compile worklists) now compares wall-clock time against a deadline armed around compilation and aborts with a query_canceled error (pg_tre: regex compilation exceeded pg_tre.compile_timeout_ms). The compile and match deadlines use independent progress hooks so arming one never perturbs the other. See SECURITY.md.

[1.5.5] - 2026-06-01 - posting-leaf FSM reclamation (deferred page deletion + recycle)

Storage-reclamation release on the 1.5.0 lineage. No on-disk format change (remains v5); no REINDEX required. Upgrade script 1.5.4--1.5.5 is a no-op stub that only bumps the recorded extension version.

Fixed

  • VACUUM now physically frees emptied posting leaves to the index FSM (the residual left open in 1.5.4). Previously an out-of-line posting leaf that VACUUM emptied was repacked to a zero-entry leaf but never reclaimed: the block stayed allocated forever and the index only shrank under a full REINDEX. 1.5.5 adds an nbtree-style deferred page-deletion and recycle protocol:

    • When ambulkdelete empties a non-head posting leaf it splices the leaf out of its right-link chain (the predecessor’s right_link is advanced past it) and marks it PG_TRE_LEAF_DELETED, stamping a deletion FullTransactionId just past an empty sparsemap. The page is left as a coherent empty waypoint (preserved right_link) so a concurrent scan holding a stale right_link still terminates correctly – posting scans copy right_link without lock coupling. The chain head is never unlinked (it is addressed from the upper-tree leaf entry).
    • amvacuumcleanup runs a recycle pass that sweeps the main fork and, for each PG_TRE_LEAF_DELETED leaf whose deletion XID has aged past the global visibility horizon (GlobalVisCheckRemovableFullXid – nbtree’s safexid gate), re-initializes the page and records it free (RecordFreeIndexPage + IndexFreeSpaceMapVacuum).
    • pg_tre_extend_fork now reuses FSM pages (GetFreeIndexPage), re-validating each candidate under its buffer lock before claiming it (nbtree _bt_allocbuf discipline) so a lost extend race falls through safely to a physical extension.

    The unlink and recycle operations are WAL-logged as full-page images (XLOG_PTRE_POSTING_UNLINK, XLOG_PTRE_POSTING_RECYCLE) replayed through the generic FPI path. amvacuum now reports pages_deleted / pages_free. New regression test posting_recycle builds a multi-leaf posting chain, empties an interior band, and verifies the leaves are unlinked, recycled into the FSM, and reused without the index growing – while the index continues to agree with the heap throughout.

[1.5.4] - 2026-05-31 - inline-posting vacuum cleanup, NFA-count hardening

Correctness/hardening release on the 1.5.0 lineage. No on-disk format change (remains v5); no REINDEX required. Upgrade script 1.5.3--1.5.4 is a no-op stub that only bumps the recorded extension version.

Fixed

  • ambulkdelete now cleans INLINE postings (C2 residual): small posting lists stored directly in upper-tree leaf entries (rather than out-of-line posting trees) were previously skipped by VACUUM, leaving their dead TIDs to be filtered only by heap MVCC recheck until the next REINDEX. The leaf’s inline region (concatenated sparsemap + payload blobs) is now repacked in place under an exclusive lock, each entry’s inline_bytes is refreshed, pd_lower is shrunk, and the page is WAL-logged as a full-page image (XLOG_PTRE_VACUUM).
  • Exact num_index_tuples: because both out-of-line posting trees and inline postings are now fully traversed during ambulkdelete, the reported live-tuple count is exact; estimated_count is no longer set on the bulkdelete path.
  • NFA-state-count guard (H5): pattern_cache now rejects a compiled regex whose internal NFA state count reads back negative (corruption / overflow), which would otherwise slip past the pg_tre.max_nfa_states > comparison and silently disable the DoS cap.

Added

  • test/sql/vacuum_inline.sql regression: deletes rows from a table whose postings stay inline, VACUUMs, and verifies the index-scan row set still equals the seq-scan row set (including a fully-emptied inline posting), guarding the in-place inline rewrite against corruption.

Build

  • Bumped the vendored lime parser-generator submodule to v0.8.7. The generator (build-time LALR(1) codegen only; not linked into pg_tre.so) was restructured upstream so the Rust output feature now lives in src/emit_rust.c; the lime binary build rule now compiles that translation unit alongside lime.c. Regenerates src/query/tre_grammar.c; verified by a full clean rebuild + 18/18 regression pass.

Known limitations

  • Emptied posting leaves are repacked but not physically freed to the free-space map. Safe physical reclaim requires an nbtree-style page deletion / recycle protocol (half-dead marking, right-link re-routing, XID-gated recycling) because VACUUM runs concurrently with lock-coupling-free right-link scans. Tracked as future work; pages_deleted / pages_free remain 0.

[1.5.3] - 2026-05-31 - version-consistency patch

Documentation/version-consistency patch. No on-disk format change (remains v5); no REINDEX required. No C-level or SQL-level behavior change. Upgrade script 1.5.2--1.5.3 is a no-op stub that only bumps the recorded extension version.

Changed

  • STATUS.md and scripts/release-check.sh brought in line with the shipped version (both still referenced 1.5.0 / a stale tag example). All version strings now consistent at 1.5.3.

[1.5.2] - 2026-05-31 - production-readiness audit hardening

Patch release addressing findings from three independent code-review audits. No on-disk format change (format remains v5); no REINDEX required. Upgrade scripts 1.5.0--1.5.1 and 1.5.1--1.5.2 are no-op stubs that only bump the recorded extension version.

Security

  • pg_tre.match_timeout_ms is now enforced (was defined but never read). A plain-C progress hook is compiled into the vendored TRE matcher loops (approx, parallel, and backtrack paths) via patches/tre-progress-hook.patch, applied idempotently at build time. The hook compares GetCurrentTimestamp() against a per-query deadline armed around each match and aborts pathological matches that would otherwise hang a backend uninterruptibly. SECURITY.md rewritten to describe the actual guarantees. compile_timeout_ms remains advisory-only (bounded by the 64KB pattern-length ceiling and max_nfa_states), now documented honestly.

Fixed

  • ambulkdelete no longer a no-op (C2): posting trees are now walked from the upper tree and dead TIDs removed in place, with real tuples_removed / num_index_tuples / num_pages statistics reported. Indexes reclaim space on VACUUM instead of growing until REINDEX. (Residual: INLINE postings are still reclaimed only by REINDEX.)
  • Atomic pending-list merge (C3): merge captures a watermark and finalizes under a single WAL record in one critical section, eliminating a torn-merge window.
  • WAL record ordering (H1): MarkBufferDirty now precedes XLogRegisterBuffer in upper.c (2 sites) and meta.c.
  • Scan-path memory safety (H2/H3/H4): pattern cache entries are pinned/refcounted across a scan with longjmp-safe release; per-call position buffers are palloc’d instead of using a shared static buffer.
  • Bloom filter guards against m_bits == 0.

Changed

  • All version strings unified at 1.5.2 (control, META.json, README, spec, Makefile). Note: v1.5.1 shipped with default_version still at 1.5.0; the full upgrade-script chain is now consistent through 1.5.2.

[1.5.0] - 2026-05-26 - range-tier multi-leaf, query-time hoist

Minor release on the 1.x line. On-disk format bump from v4 to v5 for range pages (right-link chained); existing v4 indexes remain readable, no REINDEX required. Use pg_tre_upgrade_index() to lazy-rewrite v4 range pages in v5 format if you want them to benefit from the multi- leaf feature without a rebuild.

Added

  • Multi-leaf range tier: PgTreRangeHeader (8 bytes) at the start of each range page chains pages via right_link. Build path emits multiple range pages when entries don’t fit on one; read paths walk the chain. Per-page format dispatch keeps v3/v4 range pages (no header) readable for back-compat.
  • 1M-row natural-text corpus now reports built range tier with 118 ranges across 4 pages (was: 30 captured + 88 silently truncated, with a warning). Tier-1 selectivity now applies to 100% of the heap instead of the first 25%.

Changed

  • Hoist pg_tre_upper_lookup out of tier-3 inner loop. apply_tuple_bloom_filter and the Phase 5.1 positional filter previously called pg_tre_upper_lookup once per (candidate, query-trigram) pair (3.6M probes for the 1M reproducer). A per-scan trigram_hash -> upper-tree leaf cache is now built once at scan setup and consulted in the inner loop.
    • 1M 'connection refused' cold-cache: ~66 s -> ~36 s (1.84x speedup).
    • Buffer-hit reduction is small (~1.5%): the dominant structural cost is pg_tre_posting_materialize for high-cardinality trigrams, not upper_lookup. Skip- pointer style intersection short-circuit for that path is queued for a future cycle.
  • Critical implementation detail: cached entries hold no buffer pin or LWLock across the scan (the inline blob is copied out and the leaf released immediately). An earlier iteration that held SHARE LWLocks was 2x slower.
  • PG_TRE_FORMAT_VERSION_LATEST = 5.

Honest performance status

Variable-width per-tuple blooms were prototyped on branch variable-width-v6 (commit 4bbbc38). Wire format, build-side two-pass restructure, and decoder dispatch all work; 17/17 regression passes; wal_audit and replication clean. But on the test corpus (1M rows of /usr/share/dict/words Zipfian samples, ~83 trigram emissions/row, 24,269 distinct trigrams), the variable- width output is 3 MB larger than the fixed-128 baseline (every row landed in the 256-bit bucket; the bucket thresholds were calibrated for distinct-count, not emission-count). Branch is parked; not merged. The win materializes for short-text corpora (URLs, error codes, IDs); the natural-text 1M case is bottlenecked elsewhere.

At 1M rows on this corpus, exact-match queries via the index remain ~2 orders of magnitude slower than pg_trgm GIN. The remaining gap lives in the trigram posting-list intersection cost in pg_tre_posting_materialize. Closing it requires skip-pointer-style early termination, which is a multi-week structural change deferred to a future release.

Where pg_tre is the only PostgreSQL answer (k>0 fuzzy, character-class regex, ORDER BY <@>), it stands alone at any scale.

Verified

  • 17/17 regression tests pass.
  • test/scripts/wal_audit.sh: 3/3 pass.
  • test/scripts/replication.sh (default): 4/4 pass.
  • test/scripts/replication.sh with TRE_WAL_CONSISTENCY=1: 4/4 pass.
  • 1M-row CREATE INDEX completes in ~80 s (no truncation warning); index size ~3.8 GB; 'connection refused' query 36 s cold / 33 s warm.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.4.1] - 2026-05-26 - 1M-row scaling fixes

Patch release on the 1.4 line. Same on-disk format as 1.4.0; ALTER EXTENSION pg_tre UPDATE TO ‘1.4.1’ has no SQL work to do; no re-index required.

Fixed

  • palloc 1 GB cap in ambuild.c: the build path collected (trigram_hash, tid, position) entries for every trigram emission during heap scan. At ~85 trigrams/row x 1M rows that is ~83.5M entries x 24 bytes = ~2 GB, exceeding PG’s MaxAllocSize. Switched the entries-array allocation to MemoryContextAllocHuge / repalloc_huge. CREATE INDEX on 1M+ rows previously failed with invalid memory alloc request size 1610612736.
  • Single-level upper-tree internals in upper.c: the old upper_build_internal_level was hardcoded to a single internal page (max ~506 entries). This capped pg_tre at ~10-20K distinct trigrams - which maps to roughly 50K rows of dictionary-style natural text. Beyond that the build failed with pg_tre: upper-tree internal level overflow. Now the writer is recursive: when the input doesn’t fit on one page it builds ceil(N / fanout) sibling pages and recurses on those pages' first-keys. The reader’s descent in pg_tre_upper_lookup is refactored from an if/else (root-is-leaf vs root-is-internal-with-one-descent) into a loop that walks any number of internal levels until it hits a leaf.
  • Latent correctness bug surfaced by the multi-level descent: the previous single-level descent’s first_key <= trigram_hash rightmost-match returned no match when the query trigram’s hash was less than the leftmost first_key on the internal page. Most queries' hashes land in the middle of the distribution so the bug was masked, but a few selective queries against indexes built with multiple leaves silently dropped rows. test/expected/utf8.out and test/expected/order_by.out were refreshed to reflect the now-correct behavior (rows that the index used to drop are now returned).

Verified

  • 17/17 regression tests pass.
  • test/scripts/wal_audit.sh: 3/3 pass.
  • test/scripts/replication.sh (default): 4/4 pass.
  • test/scripts/replication.sh with TRE_WAL_CONSISTENCY=1: 4/4 pass.
  • 1M-row CREATE INDEX now completes in 80 s (was: ERROR at invalid memory alloc 1.5 GB or upper-tree internal overflow).

Benchmark infrastructure

  • bench/gen_corpus.py: Python CSV generator using /usr/share/dict/words. Produces 1M rows in 3.9 s.
  • bench/bench_1m_v2.sql: \copy-based driver replacing the O(N2) plpgsql sampler in the original bench_1m.sql (which was unusable beyond ~10K rows).
  • doc/perf.md rewritten with 1M-row numbers. pg_tre is structurally larger (24x) and slower (3x build) than pg_trgm GIN at 1M rows because of per-trigram page allocation; v2.0’s posting-page coalescing is the planned fix. Where pg_tre is the only answer (k>0 fuzzy, character-class regex, ORDER BY <@>), it completes in 1-7 seconds at 1M rows.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.4.0] - 2026-05-25 - ORDER BY index-side, delta WAL, format-upgrade framework

First minor release on the 1.4 line. Same on-disk format as 1.3.x: existing indexes are read transparently. Forward-compatible format-upgrade framework lands so future format bumps (variable- width per-tuple blooms in v2.0) can be applied in place via pg_tre_upgrade_index() without REINDEX.

Added

  • Index-side ORDER BY <@> via amcanorderbyop and a new amgettuple implementation. SELECT ... WHERE body %~~ p ORDER BY body <@> p ASC LIMIT N now produces an Index Scan with Order By: and no Sort node. 10k-row LIMIT 10 measured at 23 ms (was 40 ms with executor sort). tre_text_ops operator class adds strategy 2 for the ordering operator; pg_tre--1.3.0--1.4.0.sql registers it. Honest caveat: true streaming early-termination requires per-tuple distance proxies stored in the index — followup for v2.0 alongside variable-width blooms.
  • Delta-aware WAL redo for pending_insert. The hottest WAL emit path (per-row inserts into a fastupdate index) now ships a delta (~24 bytes header + entries) instead of two ~8 KB full-page images. Measured on a 10k-row INSERT: ~370x reduction in FPI bytes on the pending_insert path, ~30x reduction in total pg_tre WAL volume. wal_consistency_checking='pg_tre' still passes — standby bytewise comparison agrees after delta replay. Other call sites still on FORCE_IMAGE; pattern is established and replicable for them.
  • In-place format-upgrade infrastructure. Three new SQL surfaces:
    • pg_tre_upgrade_index(idx regclass): walks every block, rewrites pages below the current format version, WAL-logs each rewrite, updates the meta page’s min_page_format_version after a complete sweep. Per-page exclusive lock held only for the brief rewrite + WAL emit.
    • pg_tre_index_format_status(idx regclass) returns (format_version int4, page_count bigint). SHARED locks; safe to run alongside reads/writes.
    • pg_tre_index_min_format_version(idx regclass) -> int4 returns the meta page’s tracked minimum. Today’s pg_tre_upgrade_index is a structural no-op (v3 and v4 are byte-identical); the framework is in place so v2.0’s variable-width-bloom format change can ship with zero-downtime upgrades.
  • PostgreSQL 17 build compatibility. PG18-only IndexAmRoutine fields (amconsistentequality, amconsistentordering, amtranslatestrategy, amtranslatecmptype) are guarded by #if PG_VERSION_NUM >= 180000. PG17 added to the GitHub Actions CI matrix.

Changed

  • PG_TRE_INLINE_POSTING_MAX raised from 256 to 2048 bytes. At 2048 most natural-language trigrams' posting lists stay inline; index size drops modestly on real corpora. v1.3’s build/scan perf fixes confirmed safe at this threshold across the regression matrix.
  • PG_TRE_FORMAT_VERSION_LATEST = 4, PG_TRE_FORMAT_VERSION_MIN = 3. v3 indexes still readable (byte-identical layout); meta-page min_page_format_version tracks the minimum across all pages.
  • fuzz/memutils_stub.c removed. Fuzz harness now links libpgcommon.a + libpgport.a and uses real palloc / MemoryContext / StringInfo. Limitation: cross-context UAF detection requires running as a backend extension (separate refactor).

Fixed

  • Three not-yet-implemented WAL redo PANICs (XLOG_PTRE_POSTING_DELETE, XLOG_PTRE_POSTING_SPLIT, XLOG_PTRE_VACUUM) replaced with FPI-fallthrough. These ops are not emitted by today’s page layer, so the routes were unreachable — but a stale PANIC in the redo dispatch was a footgun for future work. The unknown-op default arm correctly remains a PANIC (corrupt WAL).

Repo hygiene

  • .mailmap collapses prior Greg Burd (pi agent) commits to canonical Greg Burd for git log, GitHub, Codeberg. History is unchanged; mapping is non-destructive.
  • Agent-tooling ignore patterns moved from public .gitignore to .local-gitignore.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.3.0] - 2026-05-24 - performance: 1000x scan, 100x build

First minor release on the 1.x line. Same on-disk format as 1.2.x; ALTER EXTENSION pg_tre UPDATE TO ‘1.3.0’ has no SQL work to do; no re-index required. Substantial performance wins on high-cardinality workloads.

Added

  • pg_tre.tier3_max_candidates GUC (PGC_USERSET, default 50000): cardinality safety belt for the tier-3 per-tuple bloom and Phase 5.1 positional filter. When the candidate set exceeds this threshold, both filters are skipped and the executor recheck handles correctness.
  • PostgreSQL 17 build compatibility. PG18-only IndexAmRoutine fields are guarded by #if PG_VERSION_NUM >= 180000. Added to GitHub Actions CI matrix.
  • Real rm_mask callback for the pg_tre custom rmgr. Allows wal_consistency_checking = 'pg_tre' to run clean on a primary+standby pair: masks pd_lsn, pd_checksum, hint bits, and the page hole between pd_lower and pd_upper.

Fixed

  • Multi_leaf scan hang on high-cardinality queries. Single-trigram queries (e.g. body %~~ tre_pattern('the', 0) on a 100k-row corpus where ‘the’ appears in every row) previously hung for 10+ minutes. Root cause: tier-3 cannot prune any candidates when the query is a single trigram H, because the candidate set IS H’s posting list and every candidate’s per-tuple bloom contains H by construction. Now we skip tier-3 in that case; recheck handles correctness. Combined with replacing the idx++ walks with sm_next_member iteration, the 100k ‘the’ scan now completes in 107 ms (5000x speedup).

  • CREATE INDEX hang on high-cardinality data. A 100k-row build with the trigram ‘the’ in every row previously hung past 10 minutes. Two causes fixed: (a) src/am/ambuild.c had an O(N) linear-scan TID-bloom registry called once per trigram emission (~5M times for 100k rows), making the build O(N2). Replaced with a simplehash hash table. (b) src/util/sparsemap.c’s chunk locator __sm_get_chunk_offset walked all chunks linearly per call. For ~100k chunks this made every sm_add O(N), and N sm_adds O(N2). Added an in-memory tail-chunk cursor; ascending-order operations are now O(1) amortized. Combined: 100k build went from >10 min hung to 5 seconds (>120x speedup). The cursor patch is being upstreamed to sparsemap.

  • CHECK_FOR_INTERRUPTS coverage in build path. The heap-scan callback and inner build loops were uncancellable. Added CHECK_FOR_INTERRUPTS so a stuck CREATE INDEX can be killed normally.

Performance summary (100k-row corpus, ‘the’ in every row)

Operation 1.2.4 1.3.0 Speedup
CREATE INDEX hung 10+ min 5 s >120x
scan all-matching hung 10+ min 0.107 s >5000x
scan selective (1k matches) 1.5 s 0.291 s 5x

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.2.4] - 2026-05-22 - expected-output refresh + cascade fix

Patch release on the 1.2 lineage. Same on-disk format as 1.2.3; no re-index required; ALTER EXTENSION pg_tre UPDATE TO '1.2.4' has no SQL work to do.

Fixed

  • Cardinality + pending-overlay interaction. The 1.2.3 pending-overlay positional-filter fix cascades to the path that handles trigrams dropped by pg_tre.min_trigram_freq: high-cardinality predicates that previously returned an empty index set now return the correct row set (regression test cardinality.out: SELECT 0 -> SELECT 200, counts_agree=t, row_sets_agree=t).
  • Regression test expected outputs refreshed to track the upstream changes from 1.2.2 / 1.2.3: tre_version string, range-tier built range tier with N ranges NOTICE, the cost-model update, and the tier-3 default-on flip.

Known issues

  • multi_leaf regression test takes 1-3 minutes of CPU on typical hardware and >10 minutes on slower workstations (100k-row high-cardinality build). Test still runs by default; a v1.3 follow-up will trim its working set.

[1.2.3] — 2026-05-22 — tier-3 re-enabled by default

Patch release on the 1.2 lineage. Same on-disk format as 1.2.2; no re-index required; ALTER EXTENSION pg_tre UPDATE TO '1.2.3' has no SQL work to do.

Fixed

  • Pending-overlay regression that kept tier-3 disabled in 1.2.2. Root cause: the positional filter in pg_tre_amgetbitmap silently dropped TIDs whose conjunct trigrams were all in the pending list (not yet flushed to posting trees). Mechanism: for each conjunct, the positional filter loops over disjuncts and calls pg_tre_upper_lookup(trigram); when the trigram isn’t in the upper tree (because it’s only in the pending list), the loop does continue. If NONE of the disjunct’s trigrams are in the upper tree, the loop finishes with conj_pass=false (initialized) and the TID is dropped.

    Fix: track whether any disjunct was actually evaluated. If none were (all pending-only), conservative-pass the conjunct so the candidate falls through to the executor recheck. This matches the tier-3 bloom branch’s pre-existing conservative-pass semantics.

Changed

  • pg_tre.tuple_bloom_enable default flipped back to true. With the bloom-header fix from 1.2.2 plus the positional-filter fix above, tier-3 works correctly on both posting-tree-resident candidates and pending-list candidates, at all scales (tested 50 / 5K / 100K rows). Multi-leaf chain walking, per-leaf rank computation, and the pending overlay all interact correctly. This resolves the long-running “chain-rank lookup repair” v1.3 followup that’s been carried since 1.0.0.

Verified

  • 15/15 regression tests pass two consecutive runs with tier-3 default ON.
  • wal_audit.sh: 3/3 tests pass.
  • replication.sh: 4/4 tests pass (Test 2 was the reproducer for the pending-overlay regression).
  • Build clean with -Werror.
  • ALTER EXTENSION pg_tre UPDATE TO '1.2.3' from 1.0.0, 1.1.0, 1.1.1, 1.2.1, and 1.2.2 verified working.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.2.2] — 2026-05-22 — tier-3 bloom-header fix

Patch release on the 1.2 lineage. Same on-disk format as 1.2.1; no re-index required; ALTER EXTENSION pg_tre UPDATE TO '1.2.2' has no SQL work to do.

Fixed

  • Tier-3 per-tuple bloom — partial fix. Identified and fixed the long-standing struct-vs-bytes mismatch in the scan-side bloom check that has been masquerading as the “chain-rank lookup repair” v1.3 followup since 1.0.0. Build path serializes only the bit array of each per-row bloom into the posting-leaf payload (no header). Scan path read those bytes into a stack buffer and cast them to (PgTreBloom *), then accessed b->m_bits and b->k — reading garbage from the bit array as if it were the header. With random m_bits values, the bloom-position calculation pos = (h1 + i*h2) % m produced unrelated bits, and the bloom check rejected every legitimate match.

    Fix: src/am/amscan.c reserves space for the PgTreBloom header at the start of the scratch buffer. The lookup writes bit data past the header (into the bit-array region). After the lookup, set bloom_view->m_bits and bloom_view->k directly — NOT via pg_tre_bloom_init(), which calls memset(bits, 0, bits_bytes) and would wipe the bits we just read.

    This makes tier-3 work correctly on posting-tree-resident candidates: verified at 50, 5K, and 100K row scales. Multi-leaf chain walking and per-leaf rank computation were already correct.

  • pg_tre.tuple_bloom_enable default kept at false in 1.2.2 — a residual pending-overlay regression surfaced during the bloom-header investigation: when candidate TIDs come from the pending list (post-INSERT, pre-flush) and tier-3 is enabled, all such TIDs are rejected by apply_tuple_bloom_filter. Every disjunct’s pg_tre_upper_lookup returns false for trigrams that are only in the pending list, which should fall through to the conservative-pass branch — but empirically it doesn’t. Root cause not yet identified. Setting the GUC to on for stable / post-VACUUM workloads works correctly; the limitation is fastupdate-active state. Tracked as v1.3 followup.

Changed

  • PG_TRE_INLINE_POSTING_MAX kept at 256 bytes. Earlier in the 1.2 cycle we explored bumping the inline threshold to 384 for ~30-50% page-count reduction on sparse-trigram corpora, but two regressions surfaced: wal_audit.sh’s post-crash differential check fails at 384 (WAL-redo path interaction with larger inline blobs), and at ≥ 448 the multi-leaf 100K-row test returns 0 rows for Row 12[0-9][0-9][0-9] (chain-walker interaction). Both reverted; tracked as v1.3 followups. See doc/specs/posting-page-coalescing.md for the longer-term structural fix that closes the gap to pg_trgm by packing multiple trigrams per page.

Verified

  • 15/15 regression tests pass two consecutive runs (no flake), with the bloom-header fix in place and the GUC default at false.
  • wal_audit.sh: 3/3 tests pass.
  • replication.sh: 4/4 tests pass.
  • Build clean with -Werror.
  • scripts/release-check.sh passes end-to-end.
  • ALTER EXTENSION pg_tre UPDATE TO '1.2.2' from 1.0.0, 1.1.0, 1.1.1, and 1.2.1 verified working.

Inspired by https://github.com/timescale/pg_textsearch (Tiger Data, PostgreSQL License).

[1.2.1] — 2026-05-21 — testing, hardening, similarity ranking, size tuning

Minor release on the 1.0.0 lineage. Same on-disk format as 1.1.x; existing indexes work as-is via ALTER EXTENSION pg_tre UPDATE TO '1.2.1'.

This cycle is split into five logical commits on main:

  1. Adopt pg_textsearch’s release-engineering and CI bar: RELEASING.md, CONTRIBUTING.md, SECURITY.md, .clang-format, .pre-commit-config.yaml, scripts/bump-version.sh, GH Actions workflows (upgrade-tests, pgspot, formatting, sanitizer-build-and-test, nightly-stress), and Makefile targets for format / coverage / shell tests.
  2. Shell-test infrastructure (test/scripts/lib.sh, wal_audit.sh, stress.sh, test/lsan.supp). These caught two real bugs that landed in the same commit: the UNLOGGED-fork assertion crash and the tuple_bloom_enable default mismatch.
  3. Similarity / distance helpers and the <@> operator.
  4. replication.sh + three real WAL-redo bugs caught and fixed (loop bound off by one, REGBUF_WILL_INIT suppressing the FPI we depend on, missing FPI on subsequent records per checkpoint cycle). The same fixes also tightened single-node crash recovery.
  5. Size-tuning measurement and follow-up: bloom-overhead reduction phases, to_tsvector framing, CIC support verification, Forgejo Actions parity with .github/, and the v1.3 / v2.0 design specs for the deferred bloom-size work.

Fixed

  • Tier-3 per-tuple bloom — partial fix. Identified and fixed the long-standing struct-vs-bytes mismatch in the scan-side bloom check: build serialized only the bit array (no header), but scan cast the bytes to (PgTreBloom *) and read garbage m_bits / k from the bit data. Real fix: read the bloom bits past the header region in the scratch buffer, then write the correct m_bits / k directly into the header (without calling pg_tre_bloom_init, which would re-zero the bit array). This makes tier-3 work correctly for posting-tree-resident candidates on both single-leaf and multi-leaf trees — verified at small (50-row), medium (5K-row), and large (100K-row) scales.

    However, a separate pending-overlay regression surfaced in the same investigation: when candidate TIDs come from the pending list (post-INSERT, pre-flush) and tier-3 is enabled, all such TIDs are rejected by apply_tuple_bloom _filter even though every disjunct’s pg_tre_upper_lookup returns false (which should fall through to the conservative pass branch). Root cause not yet identified. pg_tre.tuple_bloom_enable default kept at false for 1.2.1 to preserve correctness; full re-enablement deferred to v1.3 once the pending-overlay interaction is understood. The bloom-header fix itself stays in; flipping the GUC to on post-flush works correctly.

Added

  • pg_tre.min_trigram_freq GUC (default 1, no behavior change). Build-time filter that drops posting trees for trigrams appearing in fewer than min_trigram_freq rows. Rare trigrams aren’t useful candidate filters anyway — the recheck path remains authoritative for correctness, and queries that would have relied on dropped trigrams fall back through the existing lossy-bitmap path. At min_trigram_freq=5 on a 100-row fixture: 95 of 120 posting trees skipped (~80% page-count reduction in the test). PGC_SIGHUP; effective on the next CREATE INDEX / REINDEX.
  • New regression test test/sql/cardinality.sql covering the GUC-default behavior and asserting the index-vs-seqscan differential remains correct when rare trigrams are dropped.
  • New regression test test/sql/concurrently.sql covering CREATE INDEX CONCURRENTLY and DROP INDEX CONCURRENTLY. Verified that the build path under the dual-snapshot CIC protocol returns the same row sets as the non-concurrent build path.
  • README section explicitly framing pg_tre vs pg_textsearch. Different problem domains — BM25 ranked keyword search (tokenized tsvector input) vs approximate regex over raw character sequences — with a recipe for the combined-index hybrid pattern.
  • doc/specs/posting-page-coalescing.md (v2.0 design) and doc/specs/variable-width-blooms.md (v1.3 design) for the deferred bloom-overhead work.

Changed

  • PG_TRE_INLINE_POSTING_MAX — attempted bump 256 → 384, reverted. Higher inline thresholds let more trigrams stay in the upper-tree leaf entries (one 8 KB page per trigram is the dominant size cost), and 384 promised ~30-50% page-count reduction on sparse-trigram corpora. Two regressions surfaced in testing: (a) wal_audit.sh’s post-crash differential check fails at 384 (index returns 0 for a pattern that seq-scan finds 1000 of); (b) at ≥ 448 the multi-leaf 100K-row test returns 0 rows for Row 12[0-9][0-9][0-9]. The interactions between larger inline blobs, WAL redo, and the chain walker need investigation; reverted to 256 for 1.2.1. Tracked as a v1.3 followup; see doc/specs/posting-page-coalescing.md for the longer-term structural fix that closes the gap to pg_trgm by packing multiple trigrams per page.
  • Forgejo Actions workflow (.forgejo/workflows/ci.yml) brought to parity with .github/workflows/: -Werror builds, 3x flake detection, wal_audit.sh and replication.sh shell test runs, pgspot security scan job, format-check on changed files, fixed STATUS.md staleness check. The publish-pages job continues to push docs to a pages branch, which Codeberg Pages serves at <user>.codeberg.page/<repo>/. Now also publishes RELEASING.md, CONTRIBUTING.md, and SECURITY.md.

Verified

  • CIC works for pg_tre today via the standard PG machinery; the AM doesn’t need amcanbuildparallel for CIC (that flag is for parallel-worker index build, a separate axis). Documented in STATUS.md. Parallel scan (amcanparallel) and parallel build (amcanbuildparallel) remain false; tracked as v2.0 followups.

v1.3 followups added by this cycle

  • Inline-data scan-path bug at PG_TRE_INLINE_POSTING_MAX > ~448 bytes (multi-leaf chain interaction with larger inline blobs). Once fixed, raise the threshold to 1024+ for further size reduction.
  • Multi-leaf chain-rank repair (was already tracked). Variable-width per-tuple blooms (doc/specs/variable- width-blooms.md) depend on this.

v2.0 followups added by this cycle

  • Posting-page coalescing (doc/specs/posting-page- coalescing.md). The structural change that closes most of the remaining gap to pg_trgm size: pack 4-20 low-cardinality trigrams onto a single page instead of one page per trigram. Format-version bump.

Added

  • Similarity / distance ranking helpers for approximate-match result sets:
    • tre_distance(text, text, int) and tre_distance(text, tre_pattern) return the edit distance (insertions + deletions + substitutions, each weighted 1) of the best alignment, or NULL if no match exists within max_cost. Equivalent to the existing tre_amatch_cost but renamed to make ranking idioms obvious in EXPLAIN plans.
    • tre_similarity(text, text, int) and tre_similarity(text, tre_pattern) return 1 - cost / max(len(input), len(pattern)) in [0.0, 1.0], with 0.0 (not NULL) for inputs that don’t match within max_cost. Matches pg_trgm’s similarity() semantics.
    • The <@> operator (text <@> tre_pattern) is the ergonomic spelling for ranking: returns the integer distance, NULL if no match. Inspired by pg_textsearch’s <@> for BM25 and pg_trgm’s <-> for trigram distance.
    • Idiom: WHERE body %~~ pattern ORDER BY body <@> pattern ASC NULLS LAST LIMIT N — the index narrows candidates, the executor sorts the top-N in memory. Index-side ORDER BY support is v2.0 work; today the sort is done by the executor after recheck.
    • New regression test test/sql/similarity.sql.
  • Project-infrastructure overhaul modeled on Tiger Data’s pg_textsearch (PostgreSQL License). See the dedicated release commits for the full list:
    • RELEASING.md, CONTRIBUTING.md, SECURITY.md, .clang-format + .clang-format-ignore, .pre-commit-config.yaml, .codecov.yml, .github/ISSUE_TEMPLATE/{bug_report,feature_request}.md.
    • The coverage job in .github/workflows/ci.yml runs make coverage and uploads coverage.info to Codecov via the codecov/codecov-action. Marked continue-on-error: true and informational: true in .codecov.yml’s patch policy until we hit a baseline we want to enforce. Public-repo uploads work without CODECOV_TOKEN; private-repo uploads need the secret.
    • scripts/bump-version.sh: mode-aware (dev bump vs. release), validates clean working tree, targeted regexes that don’t mangle legacy upgrade-chain entries.
    • Makefile targets: format, format-check, format-changed, format-diff, format-single, coverage, coverage-build, coverage-clean, coverage-report, test-wal-audit, test-stress, test-shell, test-all.
    • .github/workflows/upgrade-tests.yml: ALTER EXTENSION UPDATE matrix against every shipped release, on PR + weekly.
    • .github/workflows/pgspot.yml: extension SQL security scan on every push and PR.
    • .github/workflows/formatting.yml: clang-format check on changed files (gating) plus tree-wide check (informational until a one-shot reformat lands).
    • .github/workflows/sanitizer-build-and-test.yml: ASAN + UBSAN against PG18.3 + regression suite on every push to main. Without the PG memory-context instrumentation patch (deferred): catches direct UAF, OOB, double-free, and undefined behavior.
    • .github/workflows/nightly-stress.yml: runs stress.sh
      • wal_audit.sh nightly under both plain and ASAN+UBSAN builds.
  • Shell-test infrastructure under test/scripts/:
    • lib.sh: shared library with cluster init/teardown, psql_check, psql_capture, psql_count, wait_for_lsn, pg_init_primary, pg_init_standby, primary_lsn, create_basic_table, diff_idx_vs_seq.
    • wal_audit.sh: three tests (UNLOGGED indexes emit only init-fork META_UPDATE records; LOGGED inserts produce decodable rmgr-149 records; crash + restart preserves the index and its differential idx-vs-seq invariant).
    • replication.sh: primary + streaming standby; verifies that index state replicates correctly (Test 1: built index reaches standby identical row counts; Test 2: incremental writes stream to standby; Test 3: wal_consistency_checking = 'pg_tre' clean (opt-in via TRE_WAL_CONSISTENCY=1); Test 4: standby stop / start catchup preserves the index). Caught three real WAL-redo bugs on first run — see Fixed below.
    • stress.sh: N-iteration mixed insert / parallel-SELECT / DELETE / VACUUM / REINDEX workload with RSS ceiling, postmaster-alive check, per-iteration differential check, and a clean shutdown + restart at the end.
  • test/lsan.supp: leak suppressions for known-benign cases.

Changed

  • .github/workflows/ci.yml: builds enforce -Werror; the regression suite runs three times per matrix cell to surface flakes.
  • scripts/release-check.sh: runs the regression suite via scripts/run-regress.sh against the active pgrx cluster instead of the broken make localcheck path; TAP tests default-skipped (set RELEASE_CHECK_TAP=1 to run; takes ~6 min); fixed the STATUS.md staleness check.
  • Makefile: make tap target now uses PG_REGRESS, PG_TAP_PERL5LIB, PG_TAP_TMPDIR overrides for the pgrx layout, with optional nix-shell wrapper for IPC::Run.
  • pg_tre_extend retained as a thin wrapper over the new pg_tre_extend_fork; existing callers unaffected.
  • pg_tre_build_empty retained as a thin wrapper over the new pg_tre_build_empty_fork; existing callers unaffected.

Fixed

  • pg_tre_ambuildempty previously called pg_tre_build_empty, which extended MAIN_FORKNUM. This crashed with an assertion when BufferGetBlockNumber(metabuf) != PG_TRE_META_BLKNO because ambuild had already populated block 0 of the main fork before ambuildempty ran. Result: CREATE INDEX ... USING tre on an UNLOGGED table failed with TRAP: failed Assert("BufferGetBlockNumber(metabuf) == PG_TRE_META_BLKNO"). Fixed by adding pg_tre_build_empty_fork(forknum) and pg_tre_extend_fork(forknum); ambuildempty now extends INIT_FORKNUM. WAL logging fires unconditionally for the init fork (the init fork is the WAL-logged template that gets copied to the main fork during crash recovery, so it must be replayable even on UNLOGGED indexes where RelationNeedsWAL returns false). Caught by the new test/scripts/wal_audit.sh.
  • pg_tre.tuple_bloom_enable defaulted to TRUE in src/module.c but was documented and tested as defaulting to FALSE (per the v1.1 followups in STATUS.md, the per-tuple bloom and positional filter are bypassed until the chain-rank lookup is repaired). Default flipped to FALSE to match documented intent.
  • Streaming-replication correctness. Three real bugs in the custom-rmgr redo path, all caught by the new test/scripts/replication.sh:
    • pg_tre_redo_fpi’s loop bound was off by one: blkno < XLogRecMaxBlockId(record) should have been blkno <= XLogRecMaxBlockId(record). XLogRecMaxBlockId returns the maximum block_id, NOT the count. For a record that registered buffers with IDs 0 and 1 (typical: meta page + page-being-modified), the max is 1, and our loop iterated only blkno=0. Block 1 — the actual page being modified — was silently dropped from every redo, which surfaced on a streaming standby as “could not read blocks 52..52: read only 0 of 8192 bytes” the next time the primary tried to extend the relation past the unreplayed range.
    • All XLogRegisterBuffer callers passed REGBUF_WILL_INIT | REGBUF_STANDARD. REGBUF_WILL_INIT suppresses the FPI (PG assumes the redo callback will reconstruct the page from delta data); our redo only restores from FPI. Result: PANIC “block with WILL_INIT flag in WAL record must be zeroed by redo routine” on every standby replay. Fixed by dropping REGBUF_WILL_INIT everywhere; the FPI is what makes the FPI-only redo work.
    • All XLogRegisterBuffer callers now pass REGBUF_FORCE_IMAGE | REGBUF_STANDARD. Without REGBUF_FORCE_IMAGE, PG only emits an FPI on the first record per buffer per checkpoint cycle; subsequent records carry deltas and our FPI-only redo skips them, leaving the standby with a stale page. Caught by the test where inserting 3 rows on the primary resulted in only 1 row visible to the index on the standby (heap was correct; only the index was missing 2 entries). REGBUF_FORCE_IMAGE forces an FPI on every record, which is wasteful but correct; delta-aware redo is a v1.2 follow-up.

[1.1.1] - 2026-05-14

Hardening release. Same on-disk format as 1.1.0; no re-index required.

Changed

  • Vendored sparsemap upgraded from 2.2.0 to 2.3.0. v2.3.0 is defensive-bounds-checking only; the on-disk byte layout, public API, and behavior on well-formed input are byte-identical to 2.2.0. Specifically:

    • __sm_chunk_get_position clamps bv to the physical chunk capacity so an sm_open of attacker-controlled bytes with a wildly-wrong start offset can no longer walk past the chunk header word.
    • sm_contains rejects indices >= SM_CHUNK_MAX_CAPACITY instead of computing a wrapped bv, and now returns false on a NULL map (cheap insurance for callers passing the result of sm_intersection / sm_difference / sm_xor unchecked, which legitimately return NULL on empty results).
    • __sm_get_size_impl now walks chunks bounds-safely against m_capacity, truncating the on-disk chunk count to the largest valid prefix when a chunk would extend past the buffer. Behavior is unchanged on well-formed input; the walker matters only when sparsemap consumes a corrupt buffer.
    • Stub coalesce paths in sm_remove initialize offset = SM_IDX_MAX so the no-op branches don’t read uninitialized chunk metadata.
    • UBSan-clean fix in the diagnostic chunk-formatter (loop bound was off-by-one and shifted by 64 on a 64-bit value).

    None of these are observable from pg_tre under correct operation. They harden sparsemap against corrupt or malicious input.

[1.1.0] - 2026-05-14

Maintenance release. Same on-disk format as 1.0.0; no re-index required.

Fixed

  • Multi-leaf posting trees: the right-link chain walker in pg_tre_posting_materialize had inverted success/failure logic on sm_union (treating the success path as failure), which silently dropped every leaf past the first. Index scans on tables with any posting tree wide enough to split across leaves returned only the rows from the root leaf; on a 100K-row test case that meant the index returned 0 rows for matches that the seq-scan returned 100,000 rows for. Fixed and covered by a new differential index-vs-seqscan equivalence check in test/sql/multi_leaf.sql.
  • Per-tuple bloom (tier-3) and positional filter are now gated on pg_tre.tuple_bloom_enable. Both filters key their per-TID payload offset off a per-leaf rank that does not accumulate across right-link chains, so any TID past the first leaf reads the wrong payload slot and is rejected. Until the chain-rank lookup is repaired the GUC bypasses both filters; the executor recheck remains authoritative for correctness.

Changed

  • Vendored sparsemap upgraded from 2.0.0 to 2.2.0. v2.2.0 adds sm_open_copy (deserialize-into-fresh-buffer convenience), sm_add_grow (auto-doubling add), allocator hooks (sm_set_allocator / sm_create_with_allocator), and is otherwise drop-in compatible.
  • Adopted sm_open_copy at every materialize site (src/pages/posting.c), sm_add_grow in the overlay accumulator and the tier-3 refine path (src/am/amscan.c), and sm_next_member in the bitmap emit loop. The emit loop is now O(cardinality) rather than O(span); on a 100K-row test the previous loop took minutes, the new one returns in milliseconds.
  • sm_union callers in pg_tre_posting_materialize use sm_free rather than free, matching the lineage contract for sparsemap-allocated maps.

Acknowledgements

  • The 2.2.0 sparsemap release added the four APIs requested in the integration feedback at the close of the 1.0.x cycle (allocator hooks, sm_open_copy, sm_add_grow, documentation of breaking-change history).

[1.0.0] - 2026-05-13

First production release. Native PostgreSQL 18+ index access method for approximate regex matching with a three-tier filter funnel.

Highlights vs the v0.1.0 UDF-only version

  • Native AM (USING tre) with the %~~ operator and the tre_pattern(P, k) constructor. Indexed bitmap heap scans replace seq-scan-only tre_amatch calls.
  • Three-tier filter funnel: range bloom → sparsemap posting trees → per-tuple bloom → TRE recheck.
  • Multi-leaf posting trees with Lehman-Yao right-links; no per-trigram size cap in practice.
  • WAL-logged custom rmgr; crash recovery and streaming replication implemented (TAP tests in tap/).
  • UTF-8 codepoint trigrams; multibyte-safe extraction.
  • DoS hardening: NFA state cap, compile/match timeouts, fanout cap on extraction.
  • Cost-model integration with the planner; selectivity estimator backed by index meta page statistics.
  • 12 differential regression tests gating every commit.
  • Packaging: Debian, RPM, Homebrew, Docker, PGXN.
  • CI on GitHub and Codeberg (Forgejo Actions).
  • Dependabot (GitHub) + Renovate (Codeberg) for automated dependency updates.
  • Mermaid architecture diagrams that render on both GitHub and Codeberg.

Known limitation

A residual sparsemap heap-corruption path fires under sustained heavy concurrent insert + read load. Single-writer and read-only workloads are unaffected. Fix in flight with the sparsemap maintainer; will land in 1.0.1.

See STATUS.md for the v1.1 followup list.

[1.0.0-dev] - Pre-release

Phase 4.2: Multi-leaf Posting Trees (2026-05-13)

Goal: Eliminate the ~8 KB single-leaf posting limit that prevented indexing large corpora.

Shipped: - Multi-leaf posting chains: When a trigram’s posting exceeds the single-leaf budget, the builder partitions TIDs across multiple leaves linked via right_link (Lehman-Yao convention) - Right-to-left allocation: Leaves are written from rightmost to leftmost, with each leaf storing min_tid and max_tid bounds - Reader updates: pg_tre_posting_materialize unions all leaves in the chain; pg_tre_posting_lookup_tuple_bloom and pg_tre_posting_lookup_positions walk right-links to find the leaf containing the target TID - Format version bump: PG_TRE_FORMAT_VERSION 2 → 3 (BREAKING: requires REINDEX) - Test coverage: test/sql/multi_leaf.sql exercises 100K-row builds with high-frequency trigrams

Status: - ✅ Build path: Handles overflow by splitting into ~70% budget chunks - ✅ Materialize path: Unions sparsemaps across chain - ✅ Tuple bloom lookup: Locates correct leaf via TID range check - ✅ Positions lookup: Same right-link traversal as bloom - ✅ Documentation: Updated doc/onpage_format.md with multi-leaf layout

Testing: - Existing 11 regression tests pass (single-leaf cases unaffected) - New multi_leaf test validates 100K-row corpus with common trigrams (‘the’, ‘ing’)

Next Steps: - Run multi_leaf test on live cluster to verify performance at scale - Measure B-tree height and chain lengths in production workloads

Benchmark Harness (2026-05-12)

Goal: Build reproducible benchmark infrastructure for pg_tre vs pg_trgm performance comparison.

Shipped: - bench/fetch-corpus.sh — Generates deterministic synthetic corpus (configurable size, fixed seed=42) - bench/load-and-index.sh — Loads data into bench_tre/bench_trgm tables, builds indexes, measures build time/size - bench/run-queries.sh — Executes query matrix (exact regex, k=1, k=2, multi-phrase, non-selective), captures p50/p95/p99 latencies - bench/report.sh — Aggregates results into doc/perf.md with markdown tables - bench/README.md — Usage instructions and corpus description - doc/perf.md — Performance report documenting benchmark infrastructure and Phase 5 ambuild blocker

Query Matrix: - Exact regex: government, electrification, natural (vs pg_trgm) - Approximate k=1: govrnment, natrual (pg_tre only, seq-scan baseline) - Approximate k=2: govrment (pg_tre vs seq-scan) - Multi-phrase: (system){~1}.*(program){~1} (pg_tre unique capability) - Non-selective: the (tests planner cost estimation) - Rare/no-match: xyzabc (tests index rejection speed)

Status: - ✅ Infrastructure complete: corpus generation, data loading, query runner, report generator - ✅ pg_trgm baseline works: index builds successfully, queries execute - ❌ Measurements blocked: pg_tre index creation fails with “invalid memory alloc request size 1610612736” - ❌ Root cause: Phase 5 ambuild bug (same as STATUS.md item #1: ambuild.c segfault/memory error)

Testing: - Corpus generation: ✅ Generates 1k/10k/100k rows with deterministic vocabulary and typos - Data loading: ✅ COPY loads 1k rows in ~2.7s per table - pg_trgm index build: ✅ Completes in ~35ms for 1k rows - pg_tre index build: ❌ Fails regardless of corpus size (1k, 10k, 100k all trigger same error)

Next Steps: 1. Fix ambuild.c memory allocation bug (likely arithmetic overflow in buffer size calculation) 2. Re-run benchmark with 10k rows 3. Update doc/perf.md with measured p50/p95/p99 numbers 4. Compare pg_tre speedup vs seq-scan for k=1/k=2 queries

Documentation: - doc/pg_tre.md Performance Notes section now references doc/perf.md - doc/perf.md honestly documents blocker and includes complete reproduction steps - All scripts follow project conventions: zero shellcheck warnings, idempotent, structured output

Phase 0 — Foundation (Complete)

Goal: Establish build system, submodules, and basic AM registration.

Commits: - a89d4bf: Initial import (0.1.0 legacy UDF-only extension) - b324173: Phase 0 + Phase 1 scaffolding — native index AM skeleton

Shipped: - TRE (v0.9.0) and Lime parser generator as git submodules - New source tree layout: src/am/, src/pages/, src/wal/, src/query/, src/util/ - Makefile orchestrates TRE autotools + Lime codegen + PGXS build - CREATE ACCESS METHOD tre registers successfully - CREATE INDEX ... USING tre creates empty stub index - Legacy UDFs preserved: tre_amatch, tre_amatch_cost, tre_amatch_detail, tre_version - Regression test suite framework (test/sql/pg_tre.sql) - LICENSE (MIT), NOTICE (third-party attributions), .gitignore, CI workflow

Tested: - Builds cleanly on PG18+ (gcc + clang, Linux + macOS) - Existing 0.1.0 UDF tests pass (backward compatibility) - AM registration verified via \dAm in psql

Deferred: None (Phase 0 complete as designed)

Phase 1 — On-Disk Format & WAL (Partial)

Goal: Define page layouts, WAL records, and meta page R/W with crash recovery.

Commits: - 0c31b55: Phase 1 partial — meta page R/W with WAL, posting/AST contracts - fcda316: STATUS update — mark Phase 1 partial complete, fold remainder into Phase 2 worktree

Shipped: - Page layout declarations (include/pg_tre/page.h): META, UPPER, POSTING, RANGE, PENDING - WAL record types (include/pg_tre/xlog.h): XLOG_PTRE_META_UPDATE, XLOG_PTRE_POSTING_INSERT, etc. - Custom rmgr registration (RM_PG_TRE_ID = 140) via RegisterCustomRmgr during preload - Meta page read/write (src/pages/meta.c) - WAL redo for meta page (full-page image replay) - End-to-end verification: CREATE INDEX emits META_UPDATE record, crash recovery replays cleanly

Tested: - pg_ctl stop -m immediate + restart preserves index metadata - WAL record appears in pg_waldump output

Deferred to Phase 2: - Upper-tree Lehman-Yao splits - Posting-leaf sparsemap serialization - Pending-list page chain - TAP test for crash recovery (test/t/001_crash_empty.pl)

Phase 2 — Build Path (Complete)

Goal: Tuplesort-backed ambuild, posting tree bulk load, parallel build.

Commits: - 8bea2bd: Phase 2 complete — posting tree + fix tre_parse symbol collision

Shipped: - Tuplesort-backed ambuild (src/am/ambuild.c) - Posting tree bulk loader: sparsemap serialization into POSTING_L pages - Upper tree B-tree builder: routes trigrams to posting leaves - Meta page stats: n_trigrams, n_tuples_indexed - Posting tree reader helpers (src/pages/posting.c) - Buffer management utilities (src/pages/buffer.c) - Symbol collision fix: tre_parse renamed to avoid conflict with TRE library

Tested: - 10k-row fixture builds without error - pg_relation_size(index) within expected bounds (~200 KB for test data) - Posting tree structure verified via meta page inspection

Deferred: - Parallel build (amcanbuildparallel) — Phase 8 performance work - Posting tree splits (Phase 8; single-leaf per trigram in Phase 2-4)

Phase 3 — Scan Path, Exact Regex (k=0) (Complete)

Goal: Enable index scans for exact regex (k=0) with trigram extraction and amgetbitmap.

Commits: - 502cadc: Phase 3 — Build infrastructure, regex parser, and AST - d9fb519: Phase 3 — tre_pattern type, %~~ operator, stub extract - 4804d81: Phase 3 — Add debug UDFs for parser testing - a9ce946: Phase 3 — Module links successfully - 1637c66: Phase 3 — Add parser test and update STATUS - fa6ed1e: Phase 3 — Add progress summary document - 6c77b2b: Phase 3 complete — real extraction + amgetbitmap for exact regex

Shipped: - Lime-generated regex parser (src/query/tre_grammar.y → tre_grammar.c) - Hand-written tokenizer (src/query/tokens.c) with mode-sensitive lexing - Regex AST (src/query/regex_ast.c): node types for LITERAL, CONCAT, ALT, REP, APPROX - tre_pattern type: in/out/recv/send/make functions - %~~ operator: text × tre_pattern → bool, wired into tre_text_ops opclass - Russ-Cox-style trigram extraction (src/query/extract.c): - Literal runs → direct trigrams - CONCAT → pass-through child sets - ALT → intersection (common trigrams only) - REP (m ≥ 1) → inline once - APPROX treated as sub-expression (k>0 support deferred) - ANY/CLASS → break the run - amgetbitmap: per-conjunct OR via sparsemap_union, AND across conjuncts via sparsemap_intersection, emit to TIDBitmap - Debug UDFs: tre_parse_debug(), tre_extract_debug() - amscan: ambeginscan/amrescan/amendscan stubs - amcostestimate: trivial stub (always prefer index)

Tested: - Differential test (test/sql/scan_exact.sql): 13 patterns × 10-row fixture - Index scan row counts match seq scan for all patterns - EXPLAIN confirms “Bitmap Index Scan on pg_tre index” - Parser test (test/sql/parser.sql): AST correctness for 20+ regex patterns

Deferred: - k > 0 approximate matching (Phase 5) - Cost estimation (Phase 6) - Positional constraints (Phase 5.1)

Phase 4 — Incremental Writes (Complete)

Goal: Fast-update pending list for INSERT, VACUUM drains to posting tree.

Commits: - 2507f1e: Phase 4 complete — incremental writes via fast-update pending list

Shipped: - Pending list page chain (src/pages/pending.c): single-entry and batch append APIs - WAL-logged pending inserts: XLOG_PTRE_PENDING_INSERT - aminsert: tokenize text → trigrams, batch-append to pending list - amvacuumcleanup: drains pending list via pg_tre_pending_merge() - Collects entries into in-memory hash - Unions with existing posting sparsemaps - Rebuilds upper tree from scratch (simple but correct) - amgetbitmap: overlays pending-list TIDs onto posting tree results (scans see fresh inserts) - Meta page tracks: pending_head, pending_tail, pending_n_entries - WAL ordering fix: MarkBufferDirty must precede XLogRegisterBuffer (PG18 requirement)

Tested: - test/sql/incremental.sql: pre-VACUUM and post-VACUUM scans match seq scan - Sustained INSERT workload (1000 rows): index size grows, VACUUM merges cleanly - Crash recovery: pg_ctl stop -m immediate mid-workload → pending entries preserved

Limitations: - Single-leaf posting budget (~7 KB): very common trigrams exceed this, emit ERROR - Pending merge rebuilds entire upper tree (Phase 8 will optimize)

Deferred: - pg_tre_flush() function (VACUUM covers the need) - fastupdate storage option (Phase 6 reloptions) - ambulkdelete: dead TID removal (Phase 7)

Phase 5 — Approximate Regex & Three-Tier Funnel (Complete)

Goal: Enable k > 0 approximate matching with three-tier filter (range bloom, posting, per-tuple bloom).

Phase 5 WRITE — Tier 1 & Tier 3 Infrastructure

Commits: - 29f437f: Phase 5 WRITE Steps 1-2 — Bloom filter + posting payload - 2d0e652: Phase 5 WRITE Step 3 — Ambuild bloom population - 0a240ee: Phase 5 WRITE Step 4 — BRIN-style range tier - fb3678c: Phase 5 WRITE Step 6 — WAL support for RANGE_UPDATE - b1bed11: Phase 5 WRITE — Final documentation + STATUS update - 4323d62: Phase 5 WRITE follow-up — fix NULL repalloc + upper leaf entry count

Shipped: - Bloom filter primitive (src/util/bloom.c): double-hashing (h1 + i*h2) % m - Per-tuple bloom payload in posting leaves (tier 3): - Payload region: (n_positions uint16, positions[] uint32, bloom_bits[] uint8) - Grows downward from page end before opaque - pg_tre_posting_lookup_tuple_bloom() reader helper - BRIN-style range summary tier (tier 1): - Single-leaf range tree (PG_TRE_PAGE_RANGE) - Groups TIDs by heap block range (default 128 blocks) - Unions trigrams into range bloom (2048 bits, k=7) - pg_tre_range_lookup() and pg_tre_range_scan() APIs - Ambuild bloom population: - Tracks trigram positions (byte offsets) during tokenization - Computes per-tuple bloom by OR-ing all tuple trigrams - Passes positions + bloom_bits to posting builder - WAL correctness: XLOG_PTRE_RANGE_UPDATE routed to FPI replay - GUCs: pg_tre.tuple_bloom_enable (bool), pg_tre.bloom_tuple_bits (int), pg_tre.range_size_blocks (int) - Bug fixes: NULL repalloc crash, upper leaf entry count overflow

Tested: - Builds cleanly with zero warnings - Bloom filters populated during ambuild (verified via meta page n_trigrams) - Range tree serialization + WAL replay correct

Phase 5 READ — Tier 2 & Query Expansion

Commits: - ef46695: Phase 5 — register p5_read regression test + baseline expected - 3a039f8: Phase 5.1 — Wire universal Levenshtein expansion into tiling

Shipped: - Navarro tiling (src/query/tiling.c): (k+1)-way pattern partitioning - Extracts trigram spine from literal runs - Partitions into disjoint tiles with +/- k positional slack - Outputs DNF TrigramQuery (OR across tiles, AND within each) - Universal Levenshtein expansion (src/query/uleven.c): - k=0: identity (no expansion) - k=1: 3 positions × (255 substitutions + 256 insertions + 1 deletion per position) - k=2: similar with 2-edit combinations - Deduplication and fanout capping (pg_tre.max_extraction_fanout) - Extraction with edit budget (src/query/extract.c): - k > 0: calls pg_tre_tile_query() for global-budget patterns - Fallback to always_true when tiling fails (conservative) - CNF/DNF query mode dispatch (src/am/amscan.c): - CNF (k=0): AND across conjuncts, OR within each - DNF (k>0 tiled): OR across tiles, AND within each - Tier-3 per-tuple bloom filtering (apply_tuple_bloom_filter()): - For each candidate TID, fetch tuple bloom - Test required trigrams against bloom - Reject TIDs where required trigrams absent - Pending-list overlay: integrated for both CNF and DNF modes

Tested: - test/sql/p5_read.sql: 21 differential test cases (k=1, k=2) - Patterns: hello, goodbye, colour, approximate, environment, PostgreSQL - Differential verification: index scan COUNT == seq scan COUNT

Known Limitations (Phase 5): - Tier-1 range bloom: single-leaf linear lookup (Phase 8 will add binary search) - Positional filtering: positions stored but not yet used in tier-2 (Phase 5.1 wired uleven but not positional offsets) - Inline postings: no payload support (only on-disk leaves have blooms) - Local {~m} budget: treated conservatively (global-budget tiling only)

Phase 5.1 — Positional Filtering & Uleven Integration (Complete)

Commits: - 27dc722: Phase 5.1 — Positional filtering

Shipped: - pg_tre_posting_lookup_positions() API stub (ready for Phase 8 implementation) - Positional offset expansion in tiling: each tile’s trigrams have min_offset/max_offset widened by +/- k - Universal Levenshtein wired into extraction pipeline (but trigram bytes not yet stored for full expansion)

Tested: - Positional API compiles; stub returns 0 positions (filtering disabled) - Tiling generates correct positional ranges

Deferred to Phase 8: - Store trigram bytes alongside hashes in posting metadata - Full uleven expansion per-tile (currently expansion is stubbed)

Phase 6 — Planner & DoS Hardening (Complete)

Commits: - ffe189d: Phase 6 — Per-match deadline (CHECK_FOR_INTERRUPTS) - 40a8601: Phase 6 — Safety hardening (pieces 1-3)

Shipped: - Cost estimation (src/am/amcost.c): - Uses metapage per-trigram cardinalities - Estimates candidate rows via trigram selectivity - Compares index path cost vs seq scan cost - Selectivity function (src/am/sel.c): - tre_pattern_sel(): restriction selectivity estimator - Registered as operator %~~ selectivity function - Falls back to conservative 0.1 when stats unavailable - DoS protection: - pg_tre.max_nfa_states: reject patterns with > N states (default 10k) - pg_tre.compile_timeout_ms: abort regex compilation after timeout (default 1s) - pg_tre.match_timeout_ms: abort per-row recheck after timeout (default 1s) - Per-match deadline: CHECK_FOR_INTERRUPTS in recheck loop - Reloptions (src/am/amoptions.c): - pending_list_limit, q, bloom_tuple_bits, range_size_blocks, fastupdate, tuple_bloom_enable - Accessors with GUC fallback: pg_tre_get_*() functions - pg_tre_init_reloptions() called from _PG_init - amvalidate: basic stub (returns true; full validation deferred)

Tested: - test/sql/planner.sql: verifies cost estimation chooses index scan for selective patterns, seq scan for non-selective - test/sql/p6_safety.sql: catastrophic backtracking patterns rejected cleanly - Cost estimates reasonable (within 2x of actual for test workloads)

Limitations: - Selectivity estimation is coarse (per-trigram independence assumption) - NFA state count is estimated (not exact TRE NFA size) - Timeout enforcement relies on CHECK_FOR_INTERRUPTS (not hard real-time)

Phase 7 — Durability, Replicas, VACUUM (Infrastructure Complete)

Commits: - 4733a73: Phase 7 — Add TAP tests for durability

Shipped: - pg_tre_mask() for wal_consistency_checking='pg_tre' (src/wal/xlog.c) - Masks LSN, checksum, hint bits, unused space - Follows btree_mask pattern from nbtxlog.c - Meta page: all fields deterministic, no additional masking - TAP test suite (test/t/*.pl): - 001_crash_recovery.pl: immediate shutdown during build/insert/VACUUM - 002_replica.pl: streaming replication + cascading standby + wal_consistency_checking - 003_reindex_concurrent.pl: REINDEX CONCURRENTLY with concurrent writes - 004_pg_upgrade.pl: dump/restore cycle (pg_upgrade placeholder for PG18-only) - 005_soak.pl: sustained mixed workload (INSERT/DELETE/VACUUM) + crash recovery - Bash test runner (test/durability-tests.sh): Perl-free alternative - Build system integration: - make tapcheck: runs bash durability tests - make tapcheck-perl: runs Perl TAP tests (when deps available)

Tested: - Masking function compiles with zero warnings - Test infrastructure wired into Makefile - Tests written following PostgreSQL::Test::Cluster conventions

Blocked: - Tests cannot run due to pre-existing bugs: 1. Segfault in ambuild.c during CREATE INDEX (Phase 5 bloom code) 2. Missing tre_pattern_sel symbol export (Phase 6) 3. tre_amatch signature mismatch (Phase 3/5) - Once bugs fixed, tests will verify crash safety, replication correctness, REINDEX, dump/restore

Deferred to Phase 8: - ambulkdelete: dead TID removal from posting trees - VACUUM FULL / CLUSTER: TID remap handling - Long soak with CLOBBER_CACHE_ALWAYS

Phase 8 — Performance Tuning (Planned)

Not yet implemented. Planned features: - ReadStream-based posting prefetch - Parallel index scan (amcanparallel = true) - Multi-level posting trees (split single-leaf budget) - Binary search in range bloom tree - Published benchmarks (bench/ directory) - Optional WAL deltas for sparsemap in-place edits (reduce WAL volume) - Store trigram bytes for full uleven expansion - Position-based filtering via sparsemap_offset

Phase 9 — Docs & Release (In Progress)

Commits: - 04956d2: Phase 9 — Add comprehensive user-facing documentation (doc/pg_tre.md) - (this commit): Phase 9 — Add CHANGELOG.md

Shipped: - User-facing reference: doc/pg_tre.md (20 KB, 590 lines) - Installation instructions - Types, operators, functions, GUCs, reloptions - Usage cookbook (5 query patterns with EXPLAIN output) - Performance notes (three-tier funnel, selectivity, debugging) - Known limitations (Phase 4 posting budget, UTF-8, DoS) - Troubleshooting guide - CHANGELOG.md: this file

In Progress: - Migration guide (doc/migration-from-0.1.0.md) - Release checklist (doc/release-checklist.md) - Announcement draft (doc/announcement.md) - README.md update (reflect 1.0.0-rc1 status) - PGXN META.json + packaging templates

Version History

[0.1.0] - 2024-05-07 (Initial Import)

UDF-only extension (no index AM). Provided: - tre_amatch(text, text, int) — approximate match with default costs - tre_amatch_cost(text, text, int) — return edit distance - tre_amatch(text, text, int, int, int, int) — approximate match with custom costs - tre_amatch_detail(text, text, int) — detailed match info - tre_version() — TRE library version

No indexing support. All functions use TRE’s regaexec directly (always seq scan).

Upgrade Notes

0.1.0 → 1.0.0

  • Breaking: shared_preload_libraries = 'pg_tre' now required for index AM functionality
  • New: CREATE INDEX ... USING tre now supported
  • New: tre_pattern type and %~~ operator for indexable queries
  • Preserved: All legacy UDFs work unchanged (backward compatible)
  • Migration: ALTER EXTENSION pg_tre UPDATE TO '1.0.0'; (see doc/migration-from-0.1.0.md)

No on-disk format change (0.1.0 had no indexes). Upgrade is SQL-only.