# Changelog All notable changes to pg_tre are documented in this file, organized by development phase. The format follows [Keep a Changelog](https://keepachangelog.com/en/1.0.0/). --- ## 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 ``, 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 `_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(N^2 / 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; `(?=..)`, `(?!..)`, `(?<=..)`, `(?= 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_timeout`s 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--.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 2^32-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(N^2)). 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(N^2) 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(N^2) 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(N^2) (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(N^2) -> 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(N^2) 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(N^2) 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`](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`](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 >= 2^32**. pg_tre packs heap TIDs as `(block << 16) | offset`, so **any heap larger than ~512 MB** (> 65536 blocks) reaches indices >= 2^32 -- 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 ```sql 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 >= 2^32 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, `VACUUM`s, 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(N^2) 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(N^2). 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(N^2). 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 `.codeberg.page//`. 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. --- ## Links - **Repository:** https://codeberg.org/gregburd/pg_tre - **Design:** [doc/design.md](doc/design.md) - **On-disk format:** [doc/onpage_format.md](doc/onpage_format.md) - **User guide:** [doc/pg_tre.md](doc/pg_tre.md) - **License:** MIT (see LICENSE) - **TRE library:** https://github.com/laurikari/tre (BSD 2-clause)