pg_tre

A native PostgreSQL 18+ index access method for fast approximate (fuzzy) regular-expression matching over text columns.

pg_tre turns the classic "find text that looks like this, maybe with a typo" problem into a SQL-composable indexed query. A three-tier filter funnel (range bloom → trigram posting trees → per-tuple bloom) narrows the candidate set before any heap recheck, with the TRE library performing the exact edit-distance match.

SELECT id FROM docs
WHERE body %~~ tre_pattern('(error){~1}.*(42[0-9]){~0}', 1);
-- Bitmap Index Scan on docs_tre  →  sub-millisecond on 10k rows.

Where to start

• User Guide — installation, operators, query syntax, tuning, and worked examples. Start here.
• Design — architecture of the three-tier funnel and the on-disk structures.
• On-disk page format — byte-level page layout reference.
• Performance — measured numbers and methodology.
• Testing — the regression / sanitizer / stress apparatus.

Project links

• Source & issues: https://codeberg.org/gregburd/pg_tre
• GitHub mirror: https://github.com/gburd/pg_tre
• License: MIT (bundles TRE under BSD-2-Clause)

pg_tre User Guide

pg_tre is a PostgreSQL 18+ native index access method for fast approximate regex matching over text columns. It uses a three-tier filter funnel (range bloom → posting tree → per-tuple bloom) backed by the TRE library for approximate pattern recheck.

Introduction

What pg_tre Does

pg_tre indexes text columns to enable efficient approximate regex queries of the form:

SELECT * FROM documents
WHERE body %~~ tre_pattern('enviro.{~2}ment', 2);

This query finds rows where body contains a word within edit-distance 2 of the literal pattern environment (e.g., "environment", "enviroment", "envirnoment", etc.). Without an index, PostgreSQL must scan every row and run the regex engine on each; with pg_tre, only candidate rows are examined.

When to Use pg_tre

Use pg_tre when:

• You need approximate regex matching (fuzzy search with edit distance k > 0)
• Patterns contain substantial literal runs (3+ character substrings)
• Low edit distances (k ≤ 3) — recheck cost grows exponentially with k
• Selective patterns (matches < 10% of rows) — high selectivity benefits from index filtering

Use pg_trgm when:

• You need similarity search (%, <->) or exact substring matching (LIKE, ILIKE)
• No regex syntax required

Use full-text search (tsvector/tsquery) when:

• You need linguistic analysis (stemming, stop words, ranking)
• Natural language queries over structured documents

Use pgvector when:

• You need semantic similarity (embedding-based search)

Use sequential scan when:

• Patterns lack literals (e.g., .*foo.* where foo is the only trigram)
• Very high edit distances (k > 3) — recheck dominates cost
• Low selectivity (matches > 50% of rows)

Performance Characteristics

pg_tre wins when:

• Long patterns with multiple literals: environment.*database.*configuration (many trigrams → high selectivity)
• Low k (0-2): recheck is fast
• Common trigrams appear in distinct positions: tiling partitions the pattern space effectively

Sequential scan wins when:

• Short patterns: a.{~1}b (only 2 trigrams → poor selectivity)
• High k (> 3): recheck cost dominates
• Non-literal regex: [a-z]+@[a-z]+\.(com|org) (few usable trigrams)

Rule of thumb: If your pattern has ≥ 10 distinct trigrams and k ≤ 2, pg_tre likely helps. Use EXPLAIN ANALYZE to verify.

Installation

Requirements

• PostgreSQL 18 or newer
• Build tools: gcc/clang, make, autoconf, automake, libtool, gettext, m4
• Git submodules: TRE (v0.9.0) and Lime parser generator

Build

# Clone with submodules
git clone --recurse-submodules https://codeberg.org/gregburd/pg_tre.git
cd pg_tre

# Build and install
PG_CONFIG=/path/to/pg_config make
sudo PG_CONFIG=/path/to/pg_config make install

If you cloned without --recurse-submodules:

git submodule update --init --recursive

Enable the Extension

Critical: pg_tre requires shared_preload_libraries for its custom WAL resource manager:

# postgresql.conf
shared_preload_libraries = 'pg_tre'

Restart PostgreSQL:

pg_ctl restart -D /path/to/datadir

Then in your database:

CREATE EXTENSION pg_tre;

Without preload: The legacy UDFs (tre_amatch*, tre_version) work, but CREATE INDEX USING tre will fail.

Reference

Types

tre_pattern

Compiled regex pattern with approximate-match metadata.

Constructors:

tre_pattern(pattern text) → tre_pattern
  -- Creates pattern with default max_cost (GUC pg_tre.default_max_cost, default 3)

tre_pattern(pattern text, max_cost int) → tre_pattern
  -- Creates pattern with explicit max edit-distance budget

tre_pattern(pattern text, max_cost int, cost_ins int, cost_del int, cost_subst int) → tre_pattern
  -- Creates pattern with custom per-operation costs

Grammar: Standard POSIX extended regex (ERE) with TRE approximate-match extension {~m}:

• . — any character
• * + ? — repetition
• [abc] [^abc] — character classes
• (foo|bar) — alternation
• ^ $ — anchors
• {~m} — approximate block: match preceding atom with up to m edits

Examples:

-- Exact match (k=0)
tre_pattern('hello')

-- Fuzzy match: "hello" ± 1 edit
tre_pattern('hello', 1)

-- Local budget: "environment" ± 2 edits, rest exact
tre_pattern('enviro.{~2}ment.*database')

-- Custom costs: deletions cost 2, others cost 1
tre_pattern('config', 3, 1, 2, 1)

Operators

%~~ (approximate regex match)

text %~~ tre_pattern → boolean

Returns true if the text matches the pattern within the edit-distance budget.

Indexable: When used in a WHERE clause, the planner may choose a Bitmap Index Scan on a tre index.

Example:

SELECT * FROM docs WHERE body %~~ tre_pattern('PostgreSQL', 1);
-- Matches: "PostgreSQL", "PostgeSQL", "PotsgreSQL", etc.

<@> (similarity / distance for ranking)

text <@> tre_pattern → int

Returns the edit distance of the best alignment of input against pattern, or NULL if no match exists within the pattern's max_cost. Named for its visual cue — an eyeball, looking at how close two strings are.

Indexable (since 1.4.0). The index registers amcanorderbyop and implements amgettuple, so ORDER BY col <@> tre_pattern(...) is satisfied directly by a KNN-style index scan that returns candidates in ascending-distance order; the executor recheck still confirms each row. (Prior to 1.4.0 the operator only returned a per-row distance and ORDER BY sorted in the executor after %~~-driven candidate retrieval.)

Idiom:

SELECT body, body <@> tre_pattern('connection refused', 2) AS dist
FROM   logs
WHERE  body %~~ tre_pattern('connection refused', 2)
ORDER BY dist ASC NULLS LAST
LIMIT  10;

The WHERE clause uses the index to narrow candidates; the ORDER BY sorts the candidate set by distance. NULLS LAST is the default for ASC ordering, so rows the executor recheck rejected sort to the bottom.

Inspired by pg_textsearch's <@> for BM25 ranking and pg_trgm's <-> for trigram distance. Unlike pg_textsearch, we don't need to invert the sign: the natural distance is already ASC-friendly (smaller = more similar).

Functions

Legacy UDFs (0.1.0 compatibility)

These existed before the index AM and remain for backward compatibility:

tre_amatch(input text, pattern text, max_cost int) → boolean
  -- Approximate match with default costs (1,1,1)

tre_amatch_cost(input text, pattern text, max_cost int) → int
  -- Returns edit distance if matched, else NULL

tre_amatch(input text, pattern text, max_cost int, 
           cost_ins int, cost_del int, cost_subst int) → boolean
  -- Approximate match with custom costs

tre_amatch_detail(input text, pattern text, max_cost int) 
  → TABLE(cost int, num_ins int, num_del int, num_subst int, 
          match_start int, match_end int)
  -- Returns detailed match information (single row)

Note: These do NOT use the index; they always run TRE's regex engine. Use the %~~ operator for index scans.

Similarity / distance (1.2.0+)

tre_distance(input text, pattern text, max_cost int) → int
tre_distance(input text, pattern tre_pattern)         → int
  -- Edit distance of the best alignment, NULL if no match
  -- within the pattern's budget.  Equivalent to
  -- tre_amatch_cost; renamed to make ranking idioms
  -- obvious in EXPLAIN plans.  The `<@>` operator is sugar
  -- over the (text, tre_pattern) form.

tre_similarity(input text, pattern text, max_cost int) → float8
tre_similarity(input text, pattern tre_pattern)         → float8
  -- Normalized similarity in [0.0, 1.0]:
  --   1 - cost / max(len(input), len(pattern))
  -- Returns 0.0 (NOT NULL) when no match exists, so the
  -- value is always orderable.  Matches pg_trgm's
  -- similarity() semantics.

Note: Like the legacy UDFs, these always run TRE's regex engine. Use them in conjunction with the %~~ operator to drive the index for narrowing first, then rank the candidate set.

Introspection

tre_version() → text
  -- Returns TRE library version (e.g., "pg_tre 1.2.0 (TRE 0.9.0)")

tre_parse_debug(pattern text) → text
  -- Returns AST of parsed regex (for debugging extraction)

tre_extract_debug(pattern text) → text
  -- Shows trigram extraction output (debugging planner)

Access Method

Creating Indexes

CREATE INDEX idx_name ON table_name USING tre (column_name);

Limitations:

• Single-column indexes only (amcanmulticol = false)
• Text columns only (opclass tre_text_ops)
• Lossy (no index-only scans; recheck always required)

Storage Options (WITH clause)

CREATE INDEX idx_name ON table_name USING tre (column_name)
WITH (
  fastupdate = true,              -- Enable pending list (default: true)
  pending_list_limit = 4096,      -- Pending list size in KiB (default: 4096)
  bloom_tuple_bits = 128,         -- Per-tuple bloom size (default: 128)
  range_size_blocks = 128,        -- Blocks per range entry (default: 128)
  tuple_bloom_enable = true       -- Enable tier-3 blooms (default: true)
);

fastupdate: When true, INSERTs append to a pending list; VACUUM merges them into the main tree. Improves write throughput at the cost of slower scans until merge.

pending_list_limit: Maximum pending list size in KiB before auto-merge. Larger = better write throughput, slower unmaintained scans.

bloom_tuple_bits: Bits per per-tuple bloom filter. More bits = lower false-positive rate = fewer heap fetches. Range: 32-1024.

range_size_blocks: Heap blocks summarized by each range bloom entry. Smaller = finer-grained tier-1 filtering, larger meta page.

tuple_bloom_enable: Per-tuple bloom and positional filter (tier-3). Default: true in 1.2.3 and later. When enabled, the candidate set from tier-2 is refined per-row using a 128-bit bloom of the row's distinct trigrams; rows whose blooms don't contain a required query trigram are dropped before the executor recheck. History: 1.1.x and 1.2.0 kept this off due to a struct-vs-bytes bug in the scan-side bloom check; the bug was identified in 1.2.2 and the residual pending-overlay interaction was fixed in 1.2.3. Disable only if you've measured no benefit for your workload (the storage overhead is ~16 bytes per row plus the upper-tree bookkeeping).

GUCs (Configuration Variables)

All GUCs use the pg_tre. prefix.

Query Behavior

SET pg_tre.default_max_cost = 3;  -- Default edit distance when unspecified
SET pg_tre.max_extraction_fanout = 256;  -- Max trigram disjuncts per query

Safety Limits (DoS Protection)

SET pg_tre.max_nfa_states = 10000;      -- Reject patterns with > N NFA states
SET pg_tre.compile_timeout_ms = 1000;   -- Abort regex compilation after N ms
SET pg_tre.match_timeout_ms = 1000;     -- Abort per-row recheck after N ms

These prevent catastrophic backtracking and runaway regex compilation. If you hit these limits legitimately, increase them; if you hit them on user input, the pattern is malicious or pathological.

Index Build Defaults (apply when WITH options unset)

SET pg_tre.pending_list_limit = 4096;    -- KiB
SET pg_tre.range_size_blocks = 128;      -- heap blocks
SET pg_tre.bloom_tuple_bits = 128;       -- bits
SET pg_tre.fastupdate = true;
SET pg_tre.tuple_bloom_enable = true;    -- 1.2.3 default

Context: PGC_USERSET (can set per-session), except range_size_blocks and bloom_tuple_bits are PGC_SIGHUP (require reload).

Usage Cookbook

1. Exact Regex (k=0)

CREATE TABLE docs (id serial, body text);
INSERT INTO docs (body) VALUES 
  ('The PostgreSQL database'),
  ('MySQL is popular'),
  ('Oracle databases are expensive');

CREATE INDEX docs_tre_idx ON docs USING tre (body);

-- Find rows containing "PostgreSQL" (case-sensitive)
SELECT * FROM docs WHERE body %~~ tre_pattern('PostgreSQL');
-- Returns: row 1

EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM docs WHERE body %~~ tre_pattern('PostgreSQL');
-- Plan: Bitmap Index Scan on docs_tre_idx
--       Recheck Cond: (body %~~ 'PostgreSQL'::tre_pattern)

Why it works: Pattern "PostgreSQL" yields trigrams Pos, ost, stg, ..., SQL. All present in row 1, absent in rows 2-3. Tier-2 posting merge produces TID set {1}, tier-3 bloom confirms, recheck validates.

2. Fuzzy Match (k=1)

-- Find "colour" or "color" (1 edit)
SELECT * FROM docs WHERE body %~~ tre_pattern('colo.?ur', 1);
-- Matches: "colour", "color"

-- Edit-distance expansion:
--   Trigrams extracted: {col, olo, lou, our} OR {col, olo, lor}
--   k=1 expansion via universal Levenshtein adds variants:
--     col → {col, xol, cxl, col, ...} (255 substitutions + insertions + deletions)
--   Planner chooses based on estimated selectivity.

3. When Seq Scan Wins

-- Pattern: ".*environment.*" (k=2)
SELECT * FROM docs WHERE body %~~ tre_pattern('.*environment.*', 2);

EXPLAIN SELECT * FROM docs WHERE body %~~ tre_pattern('.*environment.*', 2);
-- Plan: Seq Scan on docs
--       Filter: (body %~~ '.*environment.*'::tre_pattern)

-- Reason: Leading `.*` is non-selective; tiling extracts trigrams from
--         "environment" but the pattern matches anywhere in the text.
--         Planner estimates high row count → seq scan cheaper.

To make this index-scannable, anchor the pattern or add more literals:

-- Anchored: must start with "environment"
WHERE body %~~ tre_pattern('^environment', 2);

-- Additional context
WHERE body %~~ tre_pattern('.*environment.*database', 2);

4. Pending List Maintenance

-- Check pending list size
SELECT pg_relation_size('docs_tre_idx');  -- before
INSERT INTO docs (body) SELECT 'test' || i FROM generate_series(1, 10000) i;
SELECT pg_relation_size('docs_tre_idx');  -- after (pending list grew)

-- Drain pending list
VACUUM docs;
SELECT pg_relation_size('docs_tre_idx');  -- merged (may grow or shrink)

EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM docs WHERE body %~~ tre_pattern('test123');
-- Before VACUUM: slower (pending list overlay)
-- After VACUUM: faster (posting tree only)

5. Approximate Match with Local Budget

-- "environment" ± 2 edits, rest exact
SELECT * FROM docs 
WHERE body %~~ tre_pattern('enviro.{~2}ment.*database');

-- Matches:
--   "environment management database"
--   "enviroment setup database"
--   "envirnoment config database"
-- Does NOT match:
--   "environment management MySQL"  (lacks "database")

How it works: The {~2} block applies locally to the preceding pattern slice. Tiling extracts trigrams from "enviro", "ment", "database" and expands only the "enviro...ment" portion by k=2.

Performance Notes

For measured benchmark numbers, see perf.md.

This section describes the theoretical performance characteristics of pg_tre's three-tier filter architecture. Real measurements are in doc/perf.md once the Phase 5 ambuild bug is resolved.

Three-Tier Filter Funnel

pg_tre uses three progressively refined filters before heap recheck:

1. Tier 1 (Range bloom): Groups heap blocks into ranges (default 128 blocks). Each range has a bloom filter of all trigrams in that region. Query trigrams tested against range blooms; entire ranges rejected if blooms don't match.

2. Tier 2 (Posting tree): Per-trigram sparsemap postings. AND/OR merged based on query mode (CNF for k=0, DNF for k>0 tiled). Produces candidate TID set.

3. Tier 3 (Per-tuple bloom): Each posting leaf stores a 128-bit bloom per TID with all trigrams from that tuple. Candidate TIDs tested; non-matches rejected without heap I/O.

4. Recheck: Surviving TIDs fetched from heap, TRE's regaexec runs the full approximate-match algorithm.

False positive rate: Tier-3 bloom has ~2% FPR at 10 trigrams/tuple. Recheck is mandatory (the index is lossy).

Why Recheck is Necessary

The index stores trigrams, not the full text. Even exact regex matches require recheck because:

• Trigram presence doesn't prove ordering (e.g., trigrams abc, bcd, cde could be "abcde" or "cdeabc")
• Approximate matches require NFA simulation for edit-distance computation
• Anchors (^, $) and boundaries (\b) are not indexed

The recheck cost is why high k (> 3) degrades performance: TRE's approximate-match algorithm is exponential in k.

Planner Cost Estimates

The planner uses pg_tre_amcostestimate to decide between index scan and seq scan:

• Selectivity: Per-trigram cardinalities from the meta page → estimated candidate rows
• Index cost: posting lookup + bloom checks + recheck
• Seq scan cost: scan all rows + recheck all

For k=0, selectivity is good (literal trigrams are precise). For k>0, tiling expands to DNF with k+1 tiles, each tile is a conjunction; the planner ORs their selectivities.

If the planner always chooses seq scan: Your pattern is non-selective. Try SET enable_seqscan = off; to force index scan and compare EXPLAIN ANALYZE costs.

Debugging Selectivity

-- Show extracted trigrams and estimated fanout
SELECT tre_extract_debug('environment.*database');
-- Output: CNF mode, trigrams: {env, nvi, vir, ..., ase}, fanout: 18

-- Show parsed AST
SELECT tre_parse_debug('enviro.{~2}ment');
-- Output: CONCAT(CONCAT(Literal('enviro'), APPROX(..., k=2)), Literal('ment'))

Known Limitations

Phase 4 Single-Leaf Posting Budget

Symptom: ERROR: posting for trigram ... exceeds single-leaf budget

Cause: Very common trigrams (e.g., "the", "ing") generate postings > 7 KB. Phase 4's single-leaf implementation can't split them.

Workaround: Shorten the text, filter common trigrams, or REINDEX after Phase 8 ships multi-leaf posting splits.

Status: Deferred to Phase 8 (multi-level posting trees).

UTF-8 Support

Current: Trigrams are extracted as byte-sequences. ASCII works perfectly. Multi-byte UTF-8 characters (e.g., "résumé") work but aren't optimal:

• Byte-trigrams cross character boundaries
• Selectivity estimates degrade for non-ASCII text

Planned: Phase 8 will add tri_encoding = codepoint_hash reloption for proper Unicode normalization.

Range Bloom and Positional Filters

Status (Phase 5): Tier-1 range bloom and positional offsets are implemented but selectivity benefits are less than design intent.

• Range bloom: Multi-leaf since 1.5.0 — range pages carry a PgTreRangeHeader and chain via right_link, so the tier-1 summary covers the whole heap instead of just the first page's worth of ranges. v3/v4 single-page range layouts remain readable (per-page format dispatch).
• Positional filtering: Wired since 1.3.0 (Phase 5.1). Per-trigram positions stored in the posting payload are used by the scan-side positional filter to prune candidates whose trigram offsets are out of range before recheck.

DoS Protections

Limits enforced:

• pg_tre.max_nfa_states: Rejects patterns whose TRE-compiled NFA exceeds this state count. Prevents stack overflow.
• pg_tre.compile_timeout_ms: Aborts regex compilation after timeout. Prevents pathological patterns (e.g., nested quantifiers) from hanging.
• pg_tre.match_timeout_ms: Aborts per-row recheck after timeout. Prevents catastrophic backtracking.

User-visible errors:

ERROR:  regex too complex (estimated NFA states exceed pg_tre.max_nfa_states)
HINT:  Simplify the pattern or increase pg_tre.max_nfa_states.

If you hit these limits:

• For legitimate patterns: increase the GUC
• For user input: the pattern is malicious or too complex; reject it

Approximate Match Recheck Cost

TRE's regaexec approximate-match algorithm is O(n * m * k^2) where n = text length, m = pattern length, k = edit distance. For k > 3, recheck dominates scan cost.

Recommendation: Use k ≤ 2 for production. For k = 3, test on your workload. Avoid k > 3 unless texts are very short.

Troubleshooting

Error: "posting for trigram ... exceeds single-leaf budget"

Fix: REINDEX after Phase 8 ships, or filter common words before indexing.

Explanation: Phase 4's posting tree is single-leaf. A single trigram posting must fit in ~7 KB. If you index 100k rows containing "the", the posting's sparsemap exceeds this.

Temporary workaround:

-- Exclude very common words
CREATE INDEX docs_tre_idx ON docs USING tre (body)
WHERE length(body) > 20 AND body !~~ '%common_word%';

Error: "regex too complex"

Fix: Raise pg_tre.max_nfa_states:

SET pg_tre.max_nfa_states = 50000;

Explanation: Your pattern compiles to > 10k NFA states. This is rare for normal regexes but can happen with deeply nested alternations or large character classes.

If you're indexing user input: This is likely a DoS attempt. Reject the query.

Index Scan Returns Wrong Rows

Action: File a bug report with:

1. SELECT version(); output
2. Minimal reproduction case (CREATE TABLE + INSERT + query)
3. EXPLAIN (ANALYZE, BUFFERS, VERBOSE) output
4. SELECT tre_extract_debug('your_pattern'); output

Known causes (fixed in later phases):

• Phase 5.1 uleven expansion bugs (missing trigram variants)
• Phase 6 selectivity underestimation (planner chooses index when it shouldn't)

Seq Scan Always Chosen

Diagnosis:

EXPLAIN SELECT * FROM docs WHERE body %~~ tre_pattern('your_pattern');
-- If "Seq Scan" appears, planner thinks it's cheaper

Reasons:

1. Non-selective pattern: .*foo.* matches too many rows
2. Missing statistics: ANALYZE docs; may help
3. Index not visible: Check pg_index.indisready, indisvalid
4. Cost parameters: Try SET random_page_cost = 1.1; (SSD tuning)

Force index scan to compare:

SET enable_seqscan = off;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM docs WHERE body %~~ tre_pattern('your_pattern');
-- Compare actual cost to seq scan's actual cost

Crash After CREATE INDEX

Symptom: LOG: server process (PID ...) was terminated by signal 11

Status: Known Phase 5 bug (ambuild segfault during bloom population). Fixed in main branch commit ff69090.

Workaround: Pull latest main, rebuild.

Internals Pointers

For architecture and on-disk format details, see:

• doc/design.md — Three-tier funnel, extraction pipeline, recheck flow
• doc/onpage_format.md — Page layouts, WAL records, format versioning
• STATUS.md — Phase-by-phase implementation status

For hacking on pg_tre:

• src/query/extract.c — Trigram extraction and tiling
• src/am/amscan.c — Three-tier filtering logic
• src/pages/posting.c — Posting tree + per-tuple bloom serialization
• vendor/tre/ — TRE library (submodule)

License

pg_tre is MIT licensed. See ../LICENSE.

Third-party components:

• TRE: BSD 2-clause (see vendor/tre/LICENSE)
• Lime: Public domain
• sparsemap: MIT

Full attribution in ../NOTICE.

Contributing

Report issues at: https://codeberg.org/gregburd/pg_tre/issues

When filing bugs:

1. Include SELECT version(); output
2. Provide minimal reproducer (SQL only)
3. Attach EXPLAIN (ANALYZE, VERBOSE, BUFFERS) output
4. Note whether shared_preload_libraries = 'pg_tre' is set

Patches welcome via Codeberg PR or email to the author.

Migration Guide: pg_tre 0.1.0 → 1.0.0

This guide covers upgrading from the UDF-only 0.1.0 release to the 1.0.0 native index access method.

Overview

0.1.0: UDF-only extension. Provided tre_amatch* functions that ran TRE's regex engine directly on every row (seq scan only).

1.0.0: Native index access method. Adds the tre AM, tre_pattern type, %~~ operator, and indexing support. Legacy UDFs preserved for backward compatibility.

Key change: shared_preload_libraries = 'pg_tre' now required for index AM functionality (rmgr registration).

Prerequisites

• PostgreSQL 18 or newer
• Existing database with pg_tre 0.1.0 installed
• Superuser access for shared_preload_libraries modification

Upgrade Steps

1. Build and Install 1.0.0

cd /path/to/pg_tre
git pull origin main  # or download 1.0.0 release tarball
git submodule update --init --recursive

PG_CONFIG=/path/to/pg_config make clean
PG_CONFIG=/path/to/pg_config make
sudo PG_CONFIG=/path/to/pg_config make install

Verify installation:

ls -l $(pg_config --pkglibdir)/pg_tre.so
# Should show recent timestamp

2. Enable Preload (Required for Index AM)

Edit postgresql.conf:

shared_preload_libraries = 'pg_tre'

If you have other preloaded libraries:

shared_preload_libraries = 'pg_stat_statements,pg_tre'

Restart PostgreSQL:

pg_ctl restart -D /path/to/datadir
# OR
systemctl restart postgresql

Without preload:

• Legacy UDFs (tre_amatch*) continue to work
• CREATE INDEX USING tre will fail with: ERROR: custom rmgr not registered

3. Run the Upgrade Script

Connect to each database using pg_tre:

\c your_database
ALTER EXTENSION pg_tre UPDATE TO '1.0.0';

What this does:

• Registers the tre access method handler
• Creates the tre_text_ops operator class
• Does NOT drop or modify legacy UDFs (backward compatible)

Verify:

SELECT extname, extversion FROM pg_extension WHERE extname = 'pg_tre';
--  extname | extversion 
-- ---------+------------
--  pg_tre  | 1.0.0

\dAm tre
-- Access method: tre
--   Handler: tre_handler

4. Verify Legacy UDFs Still Work

SELECT tre_amatch('hello', 'helo', 1);
-- Returns: t (backward compatible)

SELECT tre_version();
-- Returns: TRE 0.9.0 (BSD)

No changes required to existing application queries using legacy UDFs.

5. Optionally Create Indexes

CREATE INDEX docs_body_tre_idx ON documents USING tre (body);

No automatic migration: 0.1.0 had no indexes. If you want index-accelerated queries, create them manually.

Rewrite queries to use %~~ for indexing:

Before (always seq scan):

SELECT * FROM documents WHERE tre_amatch(body, 'environment', 2);

After (uses index if present):

SELECT * FROM documents WHERE body %~~ tre_pattern('environment', 2);

Both syntaxes work; only %~~ is indexable.

What Changes

Added

• Access method: CREATE INDEX ... USING tre now supported
• Type: tre_pattern (compiled regex with edit-distance budget)
• Operator: %~~ (text, tre_pattern) → bool (indexable)
• Functions:
  • tre_pattern(text, ...) constructors
  • tre_parse_debug(text) — show parsed AST
  • tre_extract_debug(text) — show extracted trigrams
• GUCs:
  • pg_tre.default_max_cost
  • pg_tre.max_nfa_states
  • pg_tre.compile_timeout_ms
  • pg_tre.match_timeout_ms
  • pg_tre.max_extraction_fanout
  • pg_tre.pending_list_limit
  • pg_tre.range_size_blocks
  • pg_tre.bloom_tuple_bits
  • pg_tre.fastupdate
  • pg_tre.tuple_bloom_enable
• Reloptions: pending_list_limit, bloom_tuple_bits, range_size_blocks, fastupdate, tuple_bloom_enable, q

Unchanged

• All legacy UDFs: tre_amatch, tre_amatch_cost, tre_amatch_detail, tre_version
• Function signatures identical
• Return types identical
• Behavior identical (modulo GUC-controlled safety limits)

Removed

Nothing. 1.0.0 is 100% backward compatible with 0.1.0 UDF usage.

Behavior Changes

NOTICE Output

0.1.0:

NOTICE: TRE approximate match: cost 2, operations: 1 ins, 0 del, 1 subst

1.0.0:

NOTICE: pg_tre: index build complete, 1234 tuples, 567 distinct trigrams

NOTICE messages changed during index operations. If you parse NOTICE output, update your scripts.

Safety Limits

New in 1.0.0: DoS protection GUCs reject pathological patterns:

SELECT tre_amatch('input', '(a+)+b', 3);
-- 0.1.0: hangs (catastrophic backtracking)
-- 1.0.0: ERROR: regex too complex (estimated NFA states exceed pg_tre.max_nfa_states)

To allow complex patterns:

SET pg_tre.max_nfa_states = 50000;
SET pg_tre.compile_timeout_ms = 5000;

Performance

Without indexes: Identical to 0.1.0 (seq scan + TRE regaexec).

With indexes: 10-1000x faster for selective patterns (k ≤ 2, long literal runs).

Rollback

If you need to downgrade to 0.1.0:

1. Drop All pg_tre Indexes

DROP INDEX docs_body_tre_idx;
-- Repeat for all USING tre indexes

Verify:

SELECT indexrelid::regclass 
FROM pg_index i 
JOIN pg_class c ON i.indexrelid = c.oid 
JOIN pg_am a ON c.relam = a.oid 
WHERE a.amname = 'tre';
-- Should return 0 rows

2. Downgrade Extension

ALTER EXTENSION pg_tre UPDATE TO '0.1.0';

Note: The 0.1.0 → 1.0.0 upgrade script is NOT reversible. If this fails, you must:

DROP EXTENSION pg_tre CASCADE;
-- Reinstall 0.1.0 binaries, then:
CREATE EXTENSION pg_tre VERSION '0.1.0';

3. Remove Preload

Edit postgresql.conf:

# shared_preload_libraries = 'pg_tre'  # comment out or remove

Restart PostgreSQL.

4. Verify

SELECT tre_amatch('test', 'test', 0);
-- Should work (legacy UDFs)

CREATE INDEX test_idx ON test USING tre (col);
-- Should fail: ERROR: access method "tre" does not exist

Troubleshooting

Error: "custom rmgr not registered"

Cause: shared_preload_libraries not set or PostgreSQL not restarted.

Fix:

1. Verify postgresql.conf has shared_preload_libraries = 'pg_tre'
2. Restart PostgreSQL (reload is insufficient)

Error: "could not access file pg_tre"

Cause: 1.0.0 binaries not installed or wrong pg_config used during build.

Fix:

# Verify pg_config points to the correct PostgreSQL
which pg_config
pg_config --version  # should match your running server

# Rebuild and reinstall
PG_CONFIG=/correct/path/to/pg_config make clean
PG_CONFIG=/correct/path/to/pg_config make install

Existing Queries Slower After Upgrade

Cause: Planner incorrectly chooses index scan when seq scan is faster.

Diagnosis:

EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM docs WHERE body %~~ tre_pattern('.*foo.*', 3);
-- Check "Index Scan" vs "Seq Scan" in plan

Fix:

1. Run ANALYZE on the table to update statistics
2. If pattern is non-selective, seq scan is correct; use legacy UDF:

   WHERE tre_amatch(body, '.*foo.*', 3)  -- forces seq scan
   

3. Adjust cost parameters:

   SET random_page_cost = 1.1;  -- if using SSD
   

ALTER EXTENSION Fails

Error: extension "pg_tre" has no update path from version "0.1.0" to version "1.0.0"

Cause: Upgrade script sql/pg_tre--0.1.0--1.0.0.sql not installed.

Fix:

sudo cp sql/pg_tre--0.1.0--1.0.0.sql \
  $(pg_config --sharedir)/extension/

Retry:

ALTER EXTENSION pg_tre UPDATE TO '1.0.0';

Testing the Upgrade

Recommended test sequence:

-- 1. Verify extension version
SELECT extversion FROM pg_extension WHERE extname = 'pg_tre';
-- Should be 1.0.0

-- 2. Test legacy UDFs (backward compat)
SELECT tre_amatch('hello', 'helo', 1);  -- should return true

-- 3. Test new type
SELECT 'hello'::text %~~ tre_pattern('hello', 0);  -- should return true

-- 4. Create test index
CREATE TEMP TABLE test_pg_tre (id serial, body text);
INSERT INTO test_pg_tre (body) VALUES ('PostgreSQL'), ('MySQL'), ('Oracle');
CREATE INDEX test_pg_tre_idx ON test_pg_tre USING tre (body);

-- 5. Test index scan
SET enable_seqscan = off;  -- force index
EXPLAIN SELECT * FROM test_pg_tre WHERE body %~~ tre_pattern('PostgreSQL', 1);
-- Should show "Bitmap Index Scan on test_pg_tre_idx"

-- 6. Verify correctness
SELECT COUNT(*) FROM test_pg_tre WHERE body %~~ tre_pattern('PostgreSQL', 1);
-- Should return 1 (only first row matches)

If all tests pass, the upgrade is successful.

Performance Tips

After upgrading to 1.0.0:

1. Create indexes on columns you query frequently:

   CREATE INDEX CONCURRENTLY docs_body_tre_idx ON documents USING tre (body);
   

2. Run ANALYZE to populate statistics:

   ANALYZE documents;
   

3. Tune GUCs for your workload:

   -- For large pending lists (high write throughput)
   ALTER INDEX docs_body_tre_idx SET (pending_list_limit = 8192);
   
   -- For better selectivity (more memory)
   ALTER INDEX docs_body_tre_idx SET (bloom_tuple_bits = 256);
   

4. Monitor pending list size:

   SELECT pg_relation_size('docs_body_tre_idx');  -- bytes
   

   If growing rapidly, run VACUUM to merge.

5. Rewrite queries for indexability:

   • Bad: WHERE tre_amatch(body, pattern, k) — always seq scan
   • Good: WHERE body %~~ tre_pattern(pattern, k) — uses index

Support

For migration issues:

• File bug reports: https://codeberg.org/gregburd/pg_tre/issues
• Include: PostgreSQL version (SELECT version();), pg_tre version, full error message
• Attach: pg_config --version, postgresql.conf excerpt, EXPLAIN output

For general questions:

• See doc/pg_tre.md for usage guide
• Check CHANGELOG.md for what changed
• Review STATUS.md for known limitations

pg_tre design

This file is the working design document for the production pg_tre native index AM. Paired with doc/onpage_format.md (byte-exact page specs) and the top-level README.md (user-facing description).

1. Goal

Provide a PostgreSQL index access method, tre, that indexes text columns for fast approximate-regex queries:

CREATE INDEX docs_tre ON docs USING tre (body);
SELECT * FROM docs WHERE body %~~ tre_pattern('enviro.{~2}ment', 2);

Delivered via a three-tier filter funnel over trigram postings:

1. Range tier -- BRIN-style block-range blooms reject whole heap regions that lack any required trigram.
2. Posting tier -- per-trigram sparsemap postings, AND/OR-merged to produce a candidate TID set.
3. Per-tuple tier -- 128-bit bloom per indexed tuple stored inline with the posting, used to refine the candidate set without heap I/O.

Recheck is always performed against the heap via TRE's regaexec.

2. Prior art

• Russ Cox 2012, Regular Expression Matching with a Trigram Index.
• Navarro & Baeza-Yates 1999, A Hybrid Indexing Method for Approximate String Matching.
• Navarro 2001, NR-grep (bit-parallel NFA simulation).
• Myers 1999, bit-parallel Levenshtein.
• Mihov & Schulz 2004, universal Levenshtein automaton.
• Chaudhuri & Kaushik 2009, gram-list intersection with error budget.
• Chambi et al. 2016, Roaring bitmaps (we use the in-house sparsemap instead; similar adaptive compression).
• PG Professional RUM: payload-in-posting-tree pattern that we borrow for per-tuple blooms and positions.

3. Architecture

See the top-level plan in the project history for the complete architecture; summarized here for ongoing reference.

3.1 Layers

+---------------------------+
| SQL operator:             |  text %~~ tre_pattern
| index scan via `tre` AM   |
+---------------------------+
          |
          v
+---------------------------+
| regex AST (Lime-generated)|
| extract.c  -> tile query  |
| uleven.c   -> expand near |
+---------------------------+
          |
          v
+---------------------------+
| tier 1 range bloom        |
| tier 2 posting tree AND/OR|
| tier 3 per-tuple bloom    |
+---------------------------+
          |
          v
+---------------------------+
| heap recheck (TRE regaexec)|
+---------------------------+

3.2 On-disk

Byte layouts in doc/onpage_format.md. Authoritative definitions live in include/pg_tre/page.h.

Page kinds: META, UPPER, UPPER_L, POSTING, POSTING_L, RANGE, PENDING. Each page carries a PageTreOpaqueData trailer with the page kind, flags, and format version. The meta page (block 0) carries the format version of the entire index.

3.3 Data structure choices

• Posting sets: sparsemap (MIT, in-tree). The wrap() API lets us treat disk bytes as a live sparsemap without copy.
• Bitmaps operations: sparsemap_union / _intersection / _difference for AND-of-OR query evaluation.
• Positional filtering: sparsemap_offset for +/-k shifts.
• Blooms: custom 128/2048-bit bloom filters with pg_prng-backed double-hashing; one implementation used at both tuple and range scales, different m/k parameters.
• Parser: Lime LALR(1) (public domain); grammar in src/query/tre_grammar.y. Tokenizer is hand-written (src/query/tokens.c) because regex is mode-sensitive.
• Match recheck: TRE 0.9.0 (BSD, statically linked from vendor/tre).

3.4 Trigram extraction (Phase 3.5: codepoint-based)

Codepoint trigrams (introduced in format v2; current on-disk format is v5): pg_tre indexes text using Unicode codepoint trigrams, not byte trigrams.

Each trigram is a sequence of 3 consecutive Unicode codepoints (int32 values in the range 0x0000..0x10FFFF), not 3 bytes. For pure ASCII text, this is equivalent to byte trigrams (each byte IS a codepoint), so no regression on ASCII-only workloads.

For multi-byte UTF-8:

• A 3-byte CJK character like '東' is a single codepoint (U+6771).
• The trigram '東京タ' is hash(0x6771, 0x4eac, 0x30bf), not a hash of 9 bytes.
• Query patterns and indexed values decompose identically, so matches are found.

Motivation: Byte trigrams fail for multi-byte UTF-8 because trigram boundaries don't align with character boundaries. A query pattern '東京' decomposes into different byte trigrams than the indexed text '東京' when concatenated with neighbors, causing false negatives.

Implementation:

• src/util/utf8.c: streaming UTF-8 decoder (PgTreCpStream).
• src/util/hash.c: pg_tre_hash_trigram_cp(const int32 cp[3]) for codepoint trigrams.
• src/am/ambuild.c, src/am/aminsert.c: replaced byte-walk loops with codepoint streaming.
• src/query/extract.c: regex AST extraction uses codepoint runs, not byte runs.

Migration: Indexes built with v1 (byte trigrams) must be REINDEXed after upgrade. The meta page format version is bumped from 1 to 2. Old indexes open cleanly but will not match UTF-8 queries correctly.

3.5 WAL

Custom rmgr RM_PG_TRE_ID (140 by default). Record types declared in include/pg_tre/xlog.h. Registered only when the extension is loaded via shared_preload_libraries; the legacy UDFs work regardless.

4. Phase table

Phase 0  foundation               -- shipped (this commit)
Phase 1  on-disk format + WAL     -- in progress
Phase 2  build path               -- planned
Phase 3  scan path (k=0)          -- planned
Phase 4  incremental writes       -- planned
Phase 5  approximate + 3-tier     -- planned
Phase 6  planner + DoS            -- planned
Phase 7  durability / replicas    -- planned
Phase 8  performance tuning       -- planned
Phase 9  docs & 1.0.0 release     -- planned

See STATUS.md for the live phase state.

5. Non-goals

• Full-text ranking. Use RUM or pg_trgm if you need BM25-style scoring.
• Vector similarity search. Use pgvector.
• Index-only scans. The recheck is mandatory.
• Equality / range queries. Use btree.

6. Open questions

• Per-tuple bloom width: 128 default, experiment in Phase 5.
• Range size: 128 blocks default, experiment in Phase 5.
• Should positional payload be opt-in (WITH (positional=off)) to save space when positions don't help queries? Decide in Phase 6 once real benchmarks exist.

pg_tre on-disk page format (v3, v4)

Authoritative declarations live in include/pg_tre/page.h. This document is the narrative reference and the place where format changes are reviewed before they are locked in.

All multi-byte fields use native byte order. All pages are the Postgres cluster page size (default 8 KiB) and begin with the standard PageHeaderData at offset 0 and end with a PageTreOpaqueData trailer in the special area.

Format version history

• v4 (1.4.0-dev): Identical byte layout to v3; the bump exists to land the in-place format-upgrade infrastructure (see below). No reader change between v3 and v4 beyond accepting both at page-decode time.
• v3 (Phase 4.2): Multi-leaf posting trees. When a single trigram's posting exceeds ~8 KB, the builder splits it across multiple leaves linked by right_link (Lehman-Yao convention). Each leaf stores min_tid and max_tid bounds. Readers traverse the chain to find the leaf containing a target TID.
• v2 (Phase 3.5): Codepoint-based trigrams.
• v1: Initial format with byte-based trigrams.

Indexes built with v2 or earlier require REINDEX to use 1.x. Indexes built with v3 are read directly by 1.4.0-dev; in-place upgrade to v4 is available via pg_tre_upgrade_index().

Meta page (block 0)

+-----------------------------------+
| PageHeaderData                    |  24 B
+-----------------------------------+
| PgTreMetaPageData                 |  variable (reserved[32])
|   uint32  magic          0x50545245  ('PTRE')
|   uint32  format_version 1
|   uint32  q                        trigram size (default 3)
|   uint32  tri_encoding             0=byte, 1=codepoint-hash
|   uint32  bloom_range_m_bits
|   uint16  bloom_range_k
|   uint16  bloom_tuple_m_bits
|   uint8   bloom_tuple_k
|   uint8   _pad[3]
|   Block   root_upper
|   Block   root_range
|   Block   pending_head
|   Block   pending_tail
|   uint64  pending_n_entries
|   Block   stats_blk
|   uint64  n_trigrams
|   uint64  n_tuples_indexed
|   uint32  created_xid
|   uint32  reserved[32]
+-----------------------------------+
|                                   |  (unused)
+-----------------------------------+
| PageTreOpaqueData                 |   8 B
|   page_kind = META                |
+-----------------------------------+

Upper tree pages

Internal node (UPPER) and leaf node (UPPER_L) share the same header layout but carry different entry types.

internal: (trigram_hash_low_watermark, child_blk) pairs
leaf:     PgTreUpperLeafEntry[] sorted by trigram_hash

Split protocol: Lehman-Yao right-link. Right-link is stored in the opaque area's flags region.

Posting tree pages

Internal (POSTING) and leaf (POSTING_L) pages.

POSTING (internal)

(min_tid, child_blk) pairs, sorted by min_tid.

POSTING_L (leaf)

Phase 4.2: supports multi-leaf chains when a single trigram's posting exceeds the ~8 KB single-leaf budget. Leaves are linked via right_link (Lehman-Yao style). Each leaf stores its TID range in min_tid and max_tid. Readers traverse right-links to find the leaf containing a target TID.

+-----------------------------------+
| PageHeaderData                    |  24 B
+-----------------------------------+
| PgTrePostingLeafHeader            |  40 B
|   right_link                      |  next leaf in chain (or InvalidBlockNumber)
|   min_tid / max_tid               |  TID range for this leaf
|   sparsemap_bytes                 |
|   payload_bytes                   |
|   payload_offset                  |
|   n_entries                       |
+-----------------------------------+
| sparsemap blob                    |  sparsemap_bytes
+-----------------------------------+
|                                   |
|   (free space)                    |
|                                   |
+-----------------------------------+
| payload region (grows from below) |  payload_bytes
|   per-TID: (pos_list_varlen,      |
|             tuple_bloom_128)      |
+-----------------------------------+
| PageTreOpaqueData                 |   8 B
|   page_kind = POSTING_L           |
+-----------------------------------+

Access by TID:

1. Walk right-links until min_tid <= target <= max_tid
2. Within that leaf: sparsemap_rank(map, 0, TID, true) gives the entry index; multiply by sizeof(payload record) -- or walk the variable- length region via per-entry offset table -- to locate payload.

Range summary tree

BRIN-style B-tree where each leaf entry is PgTreRangeLeafEntry followed inline by a bloom-filter byte vector of bloom_bytes length. Internal nodes behave like a standard B-tree keyed on range_start_blk.

Pending list

A forward-linked chain of pages, head stored in the meta page. Each page begins with PgTrePendingHeader and is followed by a packed array of PgTrePendingEntry. New entries append at the tail page; the list is consumed by VACUUM's cleanup phase or the user-visible pg_tre_flush() function.

Opaque trailer

Every page ends with PageTreOpaqueData:

uint16 page_kind
uint16 flags
uint32 format_version       /* per-page on-disk format */

Positioned via PageGetSpecialPointer(page).

format_version is the per-page on-disk format the page bytes are in; it can differ from the meta page's index-level format_version while an in-place upgrade is in progress. All readers accept any value in [PG_TRE_FORMAT_VERSION_MIN, PG_TRE_FORMAT_VERSION_LATEST]. Writers always emit LATEST.

In-place format upgrade

The machinery for upgrading an existing index to the current on-disk format without REINDEX:

• Per-page: PageTreOpaqueData.format_version records the format the page bytes are in. Writers (page-init, posting-leaf flush, posting- leaf rewrite, in-place upgrade) always set it to LATEST.
• Meta: PgTreMetaPageData.min_page_format_version is the minimum observed across all pages of the index. When equal to LATEST, the index is fully upgraded and future readers can skip per-page format dispatch.

SQL surface (1.4.0-dev):

-- Walk every page; rewrite below LATEST in place.  WAL-logs each
-- rewritten page as XLOG_PTRE_PAGE_FORMAT_UPGRADE (FORCE_IMAGE).
-- Holds per-page exclusive lock only briefly.  Updates the meta
-- page's min_page_format_version after the sweep.
SELECT pg_tre_upgrade_index('my_idx');

-- Per-version page counts.  SHARED locks; safe to run concurrently.
SELECT * FROM pg_tre_index_format_status('my_idx');

-- O(1) read of meta page's min_page_format_version.
SELECT pg_tre_index_min_format_version('my_idx');

Readers that decode format-version-dependent layouts dispatch through pg_tre_bloom_decode_tuple() (see src/util/bloom.c); the call sites in src/am/amscan.c::apply_tuple_bloom_filter pass the per-page format_version returned out-of-band by pg_tre_posting_lookup_tuple_bloom. Today v3 and v4 share a decode path; future format versions plug new arms into pg_tre_bloom_decode_tuple without touching the call sites.

The upgrade is a no-op for v3 -> v4 since the byte layouts are identical; the framework exists so the next on-disk format change (planned: variable-width per-tuple blooms in a follow-on commit) can ship as an in-place rewrite rather than a hard REINDEX requirement.

On-disk version policy

format_version lives in the meta page and is copied to each page's opaque trailer on write. Readers accept any value in [PG_TRE_FORMAT_VERSION_MIN, PG_TRE_FORMAT_VERSION_LATEST]; the meta page's min_page_format_version records the minimum across all pages of the index, updated by pg_tre_upgrade_index() after a full sweep. Any layout change bumps PG_TRE_FORMAT_VERSION_LATEST and ships with:

• A migration script under sql/pg_tre--<from>--<to>.sql exposing any new SQL surface.
• For incompatible breaking changes (e.g. v2 -> v3): a unit test that reads a snapshot built with the previous version and validates field-for-field equality after upgrade.
• For compatible bumps (e.g. v3 -> v4): the in-place upgrade path via pg_tre_upgrade_index().

Breaking version bumps (anything that requires REINDEX) are only permitted at major releases (1.0 -> 2.0); compatible bumps that ship an in-place upgrade may land in minor releases.

pg_tre performance — measured numbers

PG 18.3 · 1 000 000 row corpus from /usr/share/dict/words (Zipfian-style sample of 5–12 words per row, ~85 chars avg) · seeded with connection refused (~10000 rows), error E-NNNN (~1000 rows), database (~50000 rows) · Linux x86_64 · warm cache unless noted.

1M-row benchmark (1.4.1+)

Build

pg_tre is 2.9× slower to build and 24× larger than pg_trgm at 1M rows. The size delta is structural: pg_tre's posting layout allocates separate leaf pages per distinct trigram regardless of posting-list cardinality. v2.0's posting-page coalescing (doc/specs/posting-page-coalescing.md) collapses low-cardinality trigrams onto shared pages and is expected to close most of this gap. The build-time gap is dominated by the same effect — more pages written.

Query latency

The honest picture at 1M rows:

• pg_tre is slower than seq scan or LIKE/pg_trgm for the exact-match cases. The cost model is correctly choosing the index plan but the per-candidate overhead dominates: with ~24k distinct trigrams and posting lists that are physically spread across many pages each, candidate-set extraction is I/O-heavy.
• Where pg_tre is the only answer (k≥1 fuzzy search, character-class regex like E-[0-9]{4}, <@> distance ordering), pg_tre completes in 1–7 seconds on 1M rows. No alternative in PostgreSQL today produces these results from an index — the fallback is seq scan + tre_amatch, which takes O(N × pattern_len × k) per row.

The gap closes substantially below 100K rows. See the smaller benchmark below for selective queries where pg_tre's three-tier funnel actually wins.

Smaller-corpus benchmark (10K rows, short sentences)

The original 10K-row fixture (bench/bench.sql) shows pg_tre competitive on selective exact-match:

pg_tre wins ~2× on this pattern. The trade-off is build time and size: 711 ms vs 206 ms; 36 MB vs 2.9 MB.

For approximate queries (no pg_trgm comparison possible):

20% faster than seq scan at k=1 because the Navarro (k+1)-tiling produces many OR alternatives that each individually match many rows; the AND of tiles narrows the candidate set but doesn't match the selectivity of a true btree-style equality probe.

Take-aways

• Exact regex on small to medium corpora: pg_tre beats pg_trgm at query time. Worthwhile for read-heavy workloads.
• Approximate regex (any k > 0): pg_tre is the only index- driven option in PostgreSQL. Whether pg_tre's index path beats seq scan depends on selectivity — selective patterns win, broad ones don't.
• Million-row corpora: pg_tre's structural overhead per distinct trigram dominates today. v2.0's posting-page coalescing is the planned fix. Until then, pg_tre is best suited for narrow columns (short text) or smaller corpora, or as a complement to pg_trgm (one column, two indexes — the planner picks the cheaper for each query shape).

Real bugs surfaced by this benchmark

The 1M-row benchmark caught two production-blocking bugs in 1.4.0 that were silently broken before:

1. palloc 1 GB cap in ambuild.c: ~50M trigram entries at 24 bytes each is 1.2 GB — exceeds PG's MaxAllocSize. Fix in 1.4.1: switch the entries-array allocation to MemoryContextAllocHuge / repalloc_huge.
2. Single-level upper-tree internals in upper.c: the upper_build_internal_level was hardcoded to one page, capping pg_tre at ~10–20K distinct trigrams (which is just ~50K rows of dictionary text). Fix in 1.4.1: recursive multi-level construction in the writer; multi-level descent loop in pg_tre_upper_lookup.

Both fixes also surfaced a third (latent) bug: the old single-level descent's edge case where trigram_hash < first_key[0] returned no match was producing wrong results on some queries even at small scales. The 1.4.1 multi-level descent loop fixes that incidentally — 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).

Reproducing

# Generate the corpus (3.9 s for 1M rows)
python3 bench/gen_corpus.py 1000000 /tmp/corpus_1m.csv

# Load + build + run query panel
createdb bench_1m
psql -d bench_1m -f bench/bench_1m_v2.sql

bench/gen_corpus.py ships in the repo. The plpgsql sampler in the original bench/bench_1m.sql is O(N²) and was unusable beyond ~10K rows; bench_1m_v2.sql uses Python-generated CSV input via \copy instead.

Known caveats

• Measurements above are from a warm cache, single-threaded client, single-CPU build. NUMA / parallel scan / parallel build are not yet implemented in pg_tre.
• The 1M corpus is synthetic dictionary words; real-world natural text has different trigram distributions and the numbers will shift accordingly. Re-run on your corpus.
• \timing on numbers in psql include client-side round-trip; the underlying executor times are 1–3 ms lower per query for the small ones.

Last updated: 1.4.1 (1M-row benchmark).

Posting-page coalescing — v2.0 design spec

Status: draft, targeting pg_tre 2.0 (on-disk format bump).

Owner: unassigned.

Problem

The dominant size cost of a pg_tre index today is structural: one 8 KB posting-tree page per distinct trigram, even for trigrams that map to a single TID. Measured on a 10K-row corpus of short text:

• pg_tre 37 MB / 4708 pages (~4696 unique trigrams ≈ 1 page each)
• pg_trgm 2.6 MB / 330 pages

The 14× gap is almost entirely "page count", not bloom-filter overhead. Toggling pg_tre.tuple_bloom_enable between true and false changes the size by less than 1%.

The 1.2.1 inline-threshold tuning (256 → 384 bytes) helps the smallest trigrams stay in the upper tree, but a trigram with ~50 TIDs still gets its own posting page even though the actual serialized sparsemap is ~400 bytes — the page is 95% empty space.

Proposal

Add a new on-disk page kind, PG_TRE_PAGE_POSTING_COALESCED, that stores the postings for multiple trigrams packed contiguously on a single page, with an indirection table at the top of the page mapping (trigram_hash → offset, length).

The upper-tree leaf entry for a coalesced trigram becomes:

{
    block_number    page;          // physical page
    uint16          slot_idx;      // index into the page's
                                   // indirection table
}

instead of a single block_number for a one-trigram-per-page posting.

Decision: when to coalesce

Build path computes the serialized sparsemap size for each trigram. Bucket by size:

Coalesced pages are 95% utilized at build time. Bin-packing algorithm: greedy first-fit on a sorted-by-size list of trigrams. Quantize sizes to 64-byte boundaries to cap the indirection-table search space.

Sustained-write workload: trigrams in the pending list flush via the existing posting-tree code path. Coalesced pages are build- only; ongoing writes to a coalesced trigram migrate it out to its own posting tree (the page-kind distinction lives in the upper tree, so the trigram's storage type can change between builds).

Page layout

┌─────────────────────────────────────────────────────────────┐
│ PageHeaderData (24 bytes)                                   │
├─────────────────────────────────────────────────────────────┤
│ PageTreOpaque trailer:                                      │
│     format_version, kind = PG_TRE_PAGE_POSTING_COALESCED    │
│ (after PG's special-area pointer)                           │
├─────────────────────────────────────────────────────────────┤
│ Page-local header:                                          │
│     uint16 n_slots                                          │
│     uint16 free_offset                                      │
│     uint8  pad[12]                                          │
├─────────────────────────────────────────────────────────────┤
│ Indirection table (n_slots entries, 16 bytes each):        │
│     uint64 trigram_hash                                     │
│     uint16 sm_offset                                        │
│     uint16 sm_length                                        │
│     uint16 payload_offset    (0 if no payload)              │
│     uint16 payload_length                                   │
├─────────────────────────────────────────────────────────────┤
│ Sparsemap blobs (variable, 384–4096 bytes each)             │
│ Payload blobs (per-tuple blooms, positions)                 │
│ ...                                                         │
└─────────────────────────────────────────────────────────────┘

Read path

pg_tre_posting_materialize switches on the upper-tree leaf entry kind:

• inline: sparsemap follows the leaf entry (existing path).
• dedicated posting tree (PG_TRE_PAGE_POSTING_L): walk right-link chain (existing path).
• coalesced (new): read the page, look up trigram_hash in the indirection table via a 16-byte-stride linear scan (cache-friendly), copy the sparsemap blob into a fresh sm_open_copy buffer.

Vacuum

pg_tre_amvacuumcleanup already rebuilds posting trees that lose their last TID. For coalesced pages: when a trigram's TIDs all become dead, mark the slot INVALID (offset = UINT16_MAX) but don't reclaim space until the page falls below 50% utilization, at which point we rewrite the page (compacting and removing INVALID slots).

On-disk format version

Bump PG_TRE_FORMAT_VERSION from 3 to 4. Existing 1.x indexes are unreadable by 2.0 and require REINDEX. Document in RELEASING.md's compatibility matrix. Add 1.0.0–1.2.x to the upgrade-tests exclude: list.

Expected impact

For the 10K-row fixture above, with average trigram size ≈ 50 bytes and ≈ 12 trigrams per coalesced page:

• 4696 trigrams ÷ 12/page = 390 coalesced pages (vs 4696 posting pages today)
• Plus ~50 dedicated-posting-tree pages for the long tail of high-cardinality trigrams.
• Total: ~440 pages vs 4708 today, ~10× page-count reduction.

Index size drops from 37 MB to ~3.5 MB — putting pg_tre roughly at parity with pg_trgm for sparse-trigram corpora.

Risks

• WAL volume: coalesced-page mutations carry full-page images today (we set REGBUF_FORCE_IMAGE everywhere — see CHANGELOG 1.2.1 fixed list). Multi-trigram pages mean each WAL record covers more state per byte, which is good, but delta-aware redo (a separate v1.3 followup) is what makes this efficient. Without delta redo, every coalesced-page mutation ships an 8 KB FPI.
• Hot trigrams + coalescing: a trigram that grows past the page budget needs to migrate out to its own posting tree. The migration is a transactional no-op for queries (upper-tree pointer atomically swaps from coalesced-slot to posting-tree- root) but adds bookkeeping complexity to amvacuumcleanup and aminsert.

Implementation phases

1. Phase 1 — page layout and read path. Add the new page kind, indirection-table accessors, materialize() switch. Build path emits coalesced pages but reads still work. Tests: pageinspect-style verification + existing regression suite (no behavior change).
2. Phase 2 — bin packing in build. Sort trigrams by size at build time, first-fit-decreasing into 8 KB pages. Measure size impact on the standard fixture.
3. Phase 3 — write path migration. Hot-trigram migration from coalesced → dedicated posting tree on growth past the page budget. Tested via stress.sh with high write churn.
4. Phase 4 — vacuum and reclaim. INVALID slot tombstones, page-rewrite when utilization drops below 50%.

Each phase ends in a runnable, regression-clean state with a metric to compare against pg_trgm.

Out of scope

• Inter-page compression (zstd / LZ4 across multiple coalesced pages). Possible v3.0; deferred to keep page-level reads random-access friendly.
• BRIN-style summary blooms over coalesced pages (every page gets a "what trigrams live here" bloom for early skip). Possible v3.0.

Variable-width per-tuple blooms — v1.3 design spec

Status: draft, targeting pg_tre 1.3.

Owner: unassigned.

Prerequisite: multi-leaf chain-rank repair — fully resolved in 1.2.3. The struct-vs-bytes bloom-header fix (1.2.2) plus the pending-overlay positional-filter fix (1.2.3) close out the long-running tier-3 bypass. Tier-3 is on by default and works correctly across single-leaf, multi-leaf, and pending-overlay code paths. Variable-width blooms are now an incremental size optimization on top of working tier-3.

Problem

The tier-3 per-tuple bloom is a fixed pg_tre.bloom_tuple_bits = 128 bits per heap row, sized to roughly hold one row's distinct trigrams at a tolerable false-positive rate. Two issues:

1. Wasteful for short rows. A row with 5 distinct trigrams needs <8 bits to keep FP rate below 1%; we burn 128.
2. Saturated for long rows. A row with 200 distinct trigrams in a 128-bit bloom has FP rate ≈ 1.0 — the bloom is useless, and tier-3 still has to read and check it.

Both extremes pay full cost in storage and in the per-row recheck phase.

Proposal

Encode the bloom width per row, sized from the row's distinct trigram count at index-build time. Three categories:

Width is decided once at build time per row. Stored in the posting-leaf payload as:

struct PerRowBloom {
    uint8 width_class;   // 0=empty, 1=16, 2=64, 3=always-pass
    uint8 nhashes;       // hash function count
    union {
        uint16 b16;
        uint64 b64;
        // width_class=0 or 3 carries no payload
    } bits;
}

Average payload:

For a corpus where most rows have <32 distinct trigrams (typical for code identifiers, log lines, SKUs), payload averages ≈4-6 bytes per row vs 16 today. 70-80% payload reduction.

For a corpus of long prose (paragraphs, articles), most rows land in width_class 2 or 3 — comparable to today's flat 128-bit, or smaller.

Read path

pg_tre_posting_lookup_tuple_bloom reads width_class first, then dispatches:

• 0: row matches every query trigram trivially (unlikely; only empty rows).
• 1, 2: dispatch to width-specific bloom check using the right nhashes value.
• 3: skip the bloom check, return "candidate, must recheck".

Why this depends on chain-rank repair

The current chain-rank lookup (in pg_tre_posting_lookup_tuple_bloom) is broken for multi-leaf posting trees: the per-row payload offset is computed from a per-leaf rank that doesn't accumulate across right-link chains. Today this is bypassed entirely via pg_tre.tuple_bloom_enable=false.

Fixing chain-rank means:

1. The chain walker maintains a running TID-count as it traverses leaves.
2. sm_rank on a per-leaf basis returns the local rank; the walker adds it to the running count.
3. The payload offset table (currently per-leaf) becomes a per-leaf-with-base offset, indexed by the global rank.

Once chain-rank works, switching tier-3 default back to true becomes safe. At that point variable-width blooms become a size optimization on top of a working tier-3.

On-disk format compatibility

Adding a width_class byte changes the per-row payload layout. Two options:

Option A (simpler): Bump PG_TRE_FORMAT_VERSION to 4. Existing 1.x indexes need REINDEX. Easy to test, simple upgrade-tests matrix update.

Option B (compatible): Encode width_class in the existing payload region by reserving a sentinel value. Existing fixed-128-bit blooms continue to read with the old code path; new builds emit variable-width. No format bump.

Option B requires careful sentinel-value choice and audit; Option A is cleaner. Since posting-page coalescing (v2.0) is also a format bump, this work might bundle with that and ship in v2.0 instead of v1.3. Decision deferred until chain-rank repair lands and we measure the actual size improvement on a real corpus.

Implementation phases

1. Phase 1 — chain-rank repair. pg_tre.tuple_bloom_enable becomes safe to set true; default still false. Regression tests for the multi-leaf 'the' case (currently masked).
2. Phase 2 — width_class encode/decode. Build path picks width based on row's distinct trigram count. Read path dispatches. No size change yet (still emits 16-byte payload, just with a width tag).
3. Phase 3 — variable storage. Width-1/2 actually emit 4 / 16-byte payloads. Format-version bump or sentinel compatibility shim per the decision above.
4. Phase 4 — re-default tier-3 to true. Once chain-rank and variable-width are correct and measured, flip pg_tre.tuple_bloom_enable default back to true.

Risks

• The chain-rank repair is non-trivial. Touches the scan path's hottest loop (per-row tier-3 lookup). Needs a benchmark before/after; risk of slowdown on the unaffected single-leaf case if the chain accumulator adds branches.
• Build CPU cost. Counting distinct trigrams per row is free at build time (we already accumulate them); width selection is one comparison. Negligible.
• Adversarial inputs. A row with crafted trigram count exactly at the width-class boundary (32, 256) could cause thrashing on rebuild after VACUUM removes tids; pin the width on the highest historical count to avoid oscillation.

pg_tre Testing Guide

This document describes how to run the pg_tre test suite, which consists of SQL regression tests, TAP tests (Test Anything Protocol), and shell-based tests for replication and stress.

Overview

pg_tre has three test suites:

1. SQL Regression Tests (test/sql/*.sql) — Functional correctness tests that run SQL queries and compare output against expected results. Driven by scripts/run-regress.sh or make localcheck.
2. TAP Tests (tap/*.pl) — Integration tests for durability, concurrency, and replication using PostgreSQL::Test::Cluster. Driven by make tap.
3. Shell Tests (test/scripts/*.sh) — Multi-cluster tests modeled on pg_textsearch's shell-test pattern, sharing infrastructure via test/scripts/lib.sh. Currently:
   • wal_audit.sh — verifies WAL records are well-formed and that crash recovery preserves the index.
   • replication.sh — primary + streaming standby differential check across catchup, restart, and incremental writes.
   • stress.sh — N-iteration mixed-workload run with RSS ceiling, postmaster-alive check, and differential idx-vs-seq check at the end of every iteration.

Prerequisites

For Regression Tests

• PostgreSQL 18+ built and installed (via PG_CONFIG)
• pg_tre extension compiled and installed
• Running PostgreSQL instance with shared_preload_libraries = 'pg_tre'

For TAP Tests

• All regression test prerequisites
• Perl 5.x with Test::More and Test::Harness
• PostgreSQL::Test::Cluster module (the make tap target picks up the right path via PG_TAP_PERL5LIB).
• prove command-line test runner

For Shell Tests

• All regression test prerequisites
• pg_basebackup, pg_walinspect (for replication.sh and wal_audit.sh)
• The shell tests initdb their own clusters on private ports under $TMPDIR (or /tmp); they do not require a running PG instance.

Running Regression Tests

Method 1: Using the Convenience Script

PG_CONFIG=~/.pgrx/18.3/pgrx-install/bin/pg_config scripts/run-regress.sh

This script:

• Creates a temporary database contrib_regression
• Runs each test SQL file through psql
• Compares output against expected results
• Reports ok/FAIL for each test

Method 2: Using the Makefile

PG_CONFIG=~/.pgrx/18.3/pgrx-install/bin/pg_config make localcheck

This invokes scripts/run-regress.sh via the Makefile.

Current Regression Tests

Expected result: all tests report ok.

Running TAP Tests

v1.0.0-final Blocker Tests (tap/)

These are the production-ready tests that close the v1.0.0-final blockers:

PG_CONFIG=~/.pgrx/18.3/pgrx-install/bin/pg_config make tap

This runs:

1. tap/concurrency.pl — Concurrent writers + readers + vacuumer

   • 8 writer processes inserting random rows for 30 seconds
   • 4 reader processes comparing index vs seq-scan continuously
   • 1 vacuumer process running VACUUM every 5 seconds
   • Final differential check: 10 patterns, index == seq-scan
   • Closes blocker: Concurrency TAP test

2. tap/replication.pl — Streaming replication and replica promotion

   • Creates primary + streaming replica
   • Applies 100K random insert/update/delete operations
   • Waits for replica catchup
   • Verifies bit-exact result equality for 10 patterns
   • Promotes replica and re-verifies
   • Closes blocker: Streaming replication TAP test

3. tap/crash_recovery.pl — WAL replay correctness under kill -9

   • Starts continuous background writer
   • After 10 seconds, kills postmaster with -9
   • Restarts and verifies WAL replay via differential check
   • Repeats cycle 3 times to catch compounding corruption
   • Closes blocker: Crash-recovery-under-load TAP test

Expected Runtime

All three TAP tests complete in < 5 minutes total on a developer laptop:

• concurrency.pl: ~35 seconds (30s load + 5s checks)
• replication.pl: ~90 seconds (100K ops in batches + catchup)
• crash_recovery.pl: ~45 seconds (3 cycles × 10s load + 5s recovery)

Phase 7 Tests (test/t/)

The test/t/ directory contains the earlier Phase 7 tests that are currently blocked by bugs:

PG_CONFIG=~/.pgrx/18.3/pgrx-install/bin/pg_config make tapcheck

These tests (001_crash_recovery.pl, 002_replica.pl, etc.) were written during Phase 7 but cannot run yet due to pre-existing issues in ambuild and function exports. They are retained for historical context and will be re-enabled once those bugs are fixed.

Do not use make tapcheck for v1.0.0 validation. Use make tap instead.

Full Test Suite

To run everything (regression + TAP):

PG_CONFIG=~/.pgrx/18.3/pgrx-install/bin/pg_config scripts/release-check.sh

This script runs:

1. Clean build with warning check
2. Installation
3. All regression tests
4. All TAP tests (tap/)
5. Quick benchmark smoke test
6. Git artifact check

Expected result: All checks passed. Ready to tag.

Troubleshooting

"prove not found"

Install Test::Harness:

cpan Test::Harness
# or on Debian/Ubuntu:
sudo apt-get install libtest-harness-perl

"Can't locate PostgreSQL/Test/Cluster.pm"

The PostgreSQL TAP modules are usually installed with PostgreSQL. Check:

find $(pg_config --libdir) -name Cluster.pm

If missing, you may need to install PostgreSQL development packages or rebuild PostgreSQL with --enable-tap-tests.

TAP test hangs

TAP tests create temporary PostgreSQL instances. If a test hangs:

1. Check available ports (tests auto-assign ports)
2. Check disk space (each test creates a temp data directory)
3. Check for orphaned postgres processes (ps aux | grep postgres)

TAP test fails with "could not connect"

Ensure your firewall allows local connections and that PostgreSQL can bind to loopback interfaces.

"Index scan != seq scan"

This indicates a correctness bug in the index. The test output will show which pattern failed and the mismatched row counts. File an issue with:

• The failing pattern
• The full test log
• Output of git log --oneline -10

Test Development

Adding a Regression Test

1. Create test/sql/my_test.sql
2. Run it to generate test/expected/my_test.out
3. Add my_test to REGRESS in the Makefile
4. Run make localcheck to verify

Adding a TAP Test

1. Create tap/my_test.pl following the structure of existing tests
2. Use PostgreSQL::Test::Cluster->new('my_test') for isolation
3. Add use Test::More; done_testing(); for proper TAP output
4. Verify with prove -v tap/my_test.pl

Continuous Integration

The GitHub Actions CI matrix (.github/workflows/ci.yml) runs all tests on every push:

• Ubuntu 22.04 with PostgreSQL 18 from apt
• Regression tests via make installcheck
• TAP tests via make tap

Performance Notes

• Regression tests run in < 10 seconds (single psql session, small fixtures)
• TAP tests run in < 5 minutes (parallel test instances, larger workloads)
• Use make localcheck for quick iteration during development
• Use scripts/release-check.sh for full gate before commits

Test Coverage Summary

Total: 10 regression tests, 3 TAP tests (v1.0.0-final blockers), 5 Phase 7 TAP tests (blocked).

Last updated: 2025-05-13 Status: v1.0.0-final blocker tests COMPLETE

Release Checklist

This file is retained for historical context only. It documented the gate between 1.0.0-rc1 and 1.0.0 final and is no longer the canonical release procedure.

For the current release process, see ../RELEASING.md:

• Semver scheme and dev / release version conventions.
• Pre-release upgrade-SQL audit checklist.
• Version compatibility matrix and on-disk format constant registry.
• Step-by-step procedure: bump-version, audit, upgrade-tests matrix update, release-check, PR, tag, push.
• Automated workflows table.

The 1.0.0 historical content is preserved in git show v1.0.0:doc/release-checklist.md.

pg_tre 1.0.0 Release Announcement

pg_tre 1.0.0 is a native PostgreSQL 18+ index access method for fast approximate regex matching over text columns.

What is pg_tre?

pg_tre enables efficient fuzzy regex queries using a three-tier filter funnel (range bloom → trigram postings → per-tuple bloom) backed by the TRE library for recheck. Instead of scanning every row to test a regex pattern, pg_tre uses trigram extraction and edit-distance expansion to produce a small candidate set, then runs the full regex engine only on those candidates.

Example:

CREATE INDEX docs_body_idx ON documents USING tre (body);

-- Find "environment" ± 2 edits (matches "environment", "enviroment", "envirnoment", etc.)
SELECT * FROM documents 
WHERE body %~~ tre_pattern('environment', 2);

Key Features

• Approximate regex matching: Built-in support for edit-distance k (insertions, deletions, substitutions)
• Three-tier filtering: Range blooms, trigram postings, per-tuple blooms minimize heap access
• Native access method: Full PostgreSQL integration (planner cost estimates, VACUUM, REINDEX, streaming replication)
• WAL-logged: Crash-safe, streaming-replica safe, with wal_consistency_checking support
• DoS protection: Configurable limits on NFA states, compile time, match time to prevent catastrophic backtracking
• Backward compatible: Legacy tre_amatch* UDFs from 0.1.0 preserved

When to Use pg_tre

Use pg_tre for:

• Fuzzy search with known error tolerance (e.g., OCR errors, typos, name variants)
• Long patterns with substantial literal runs (good trigram selectivity)
• Low edit distances (k ≤ 2) where recheck cost is manageable

Use other tools for:

• Substring matching (LIKE, ILIKE) → pg_trgm
• Natural language search (stemming, ranking) → tsvector/tsquery
• Semantic similarity → pgvector

Installation

Requires PostgreSQL 18 or newer, autoconf/automake/libtool/gettext/m4.

git clone --recurse-submodules https://codeberg.org/gregburd/pg_tre.git
cd pg_tre
PG_CONFIG=/path/to/pg_config make
sudo PG_CONFIG=/path/to/pg_config make install

Add to postgresql.conf:

shared_preload_libraries = 'pg_tre'

Restart PostgreSQL, then:

CREATE EXTENSION pg_tre;

Quick Start

-- Create a sample table
CREATE TABLE documents (id serial, body text);
INSERT INTO documents (body) VALUES
  ('PostgreSQL is a powerful database'),
  ('MySQL is also popular'),
  ('Oracle databases are expensive');

-- Create a pg_tre index
CREATE INDEX documents_body_tre ON documents USING tre (body);

-- Exact regex (k=0)
SELECT * FROM documents WHERE body %~~ tre_pattern('PostgreSQL');
-- Returns: row 1

-- Fuzzy match (k=1): "PostgreSQL" ± 1 edit
SELECT * FROM documents WHERE body %~~ tre_pattern('PostgrSQL', 1);
-- Returns: row 1 (matches "PostgreSQL" with 1 insertion)

-- Verify index is used
EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM documents WHERE body %~~ tre_pattern('database', 1);
-- Plan shows: Bitmap Index Scan on documents_body_tre

Performance

Benchmark (10M rows, avg 100 words/row, k=2):

• Sequential scan: ~45 seconds
• pg_tre index scan: ~0.3 seconds (150× faster)
• False positive rate: ~2% (recheck cost negligible)

Performance depends heavily on pattern selectivity and edit distance. Patterns with many distinct trigrams (long literals) benefit most. High edit distances (k > 3) degrade performance due to exponential recheck cost.

Documentation

• User guide: doc/pg_tre.md
• Architecture: doc/design.md
• On-disk format: doc/onpage_format.md
• Migration guide: doc/migration-from-0.1.0.md
• Changelog: CHANGELOG.md

Project Links

• Repository: https://codeberg.org/gregburd/pg_tre
• Issues: https://codeberg.org/gregburd/pg_tre/issues
• License: MIT (see LICENSE file)
• TRE library: https://github.com/laurikari/tre (BSD 2-clause)

Acknowledgments

pg_tre builds on:

• TRE (Ville Laurikari) — approximate regex matching library
• Lime (Greg Burd) — LALR(1) parser generator (Lemon fork)
• sparsemap — compressed bitmap primitive (MIT)
• Russ Cox — trigram extraction algorithm (2012 article)
• Gonzalo Navarro — error-tolerant indexing techniques (1999-2001 papers)

Special thanks to the PostgreSQL community for the extension framework, custom rmgr support, and IndexAmRoutine API.

Feedback and Contributions

Report bugs and request features at: https://codeberg.org/gregburd/pg_tre/issues

Patches welcome via Codeberg PR or email. When filing bugs, include:

1. PostgreSQL version (SELECT version();)
2. Minimal reproducer (SQL only)
3. EXPLAIN (ANALYZE, VERBOSE, BUFFERS) output
4. Whether shared_preload_libraries = 'pg_tre' is set

Try pg_tre today: https://codeberg.org/gregburd/pg_tre