Contents

• pg_tre User Guide
  • Introduction
    • What pg_tre Does
    • When to Use pg_tre
    • Performance Characteristics
  • Installation
    • Requirements
    • Build
    • Enable the Extension
  • Reference
    • Types
    • Operators
    • Functions
    • Access Method
    • GUCs (Configuration Variables)
  • Usage Cookbook
    • 1. Exact Regex (k=0)
    • 2. Fuzzy Match (k=1)
    • 3. When Seq Scan Wins
    • 4. Pending List Maintenance
    • 5. Approximate Match with Local Budget
  • Performance Notes
    • Scan Pipeline
    • Why Recheck is Necessary
    • Planner Cost Estimates
    • Debugging Selectivity
  • Known Limitations
    • Character encoding and collations
    • DoS Protections
    • Approximate Match Recheck Cost
  • Troubleshooting
    • Error: “regex too complex”
    • Index Scan Returns Wrong Rows
    • Seq Scan Always Chosen
  • Internals Pointers
  • License
  • Contributing

pg_tre User Guide

pg_tre is a native index access method for PostgreSQL 17, 18 and 19 that answers approximate regex queries over text columns. The index stores compressed trigram posting lists; a query’s trigram formula selects candidate rows, and the TRE library rechecks each one, so results are exact.

---

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 17, 18 or 19
• Build tools: gcc/clang, make, autoconf, automake, libtool, gettext, m4
• Vendored sources: TRE and the Lime parser generator (git submodules; included in release tarballs and the PGXN distribution)

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: bash git submodule update --init --recursive

Enable the Extension

Simply run: sql CREATE EXTENSION pg_tre;

Note: As of v4.0.0, shared_preload_libraries is no longer required. pg_tre now uses PostgreSQL’s generic WAL facility instead of a custom resource manager.

---

Reference

Types

tre_pattern

Compiled regex pattern with approximate-match metadata.

Constructors: ```sql 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: ```sql – 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: sql 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: sql 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)

pg_tre_index_check(idx regclass, samples int DEFAULT 20) → table
  -- Compares the index with a sequential scan for patterns cut from
  -- the column's own values; any row with ok = false is a bug (4.5.0+)

pg_tre_index_pending(idx regclass) → bigint
  -- Entries in the index's pending list, which every scan reads (4.5.0+)

pg_tre_index_tid_packing(idx regclass) → text
  -- 'dense' or 'legacy'; REINDEX converts legacy indexes (4.4.0+)

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 (
  pending_list_limit = 4096       -- merge the pending list on INSERT past 4 MB
);

pending_list_limit (KiB): every INSERT appends to the index’s pending list, which every scan reads. When an INSERT pushes the list past this size it merges the list into the index, as VACUUM does, unless another merge (or a VACUUM of the table) is running; then it does not wait, so a busy table can pass the limit until the next INSERT. -1 (the default) uses pg_tre.pending_list_limit; 0 means no limit: only VACUUM (or REINDEX) merges. A merge rewrites the upper tree and every posting the list touches, so the INSERT that triggers it takes as long as a VACUUM’s merge would; pick a limit that keeps scans fast without merging too often. Changing it takes a ShareUpdateExclusiveLock (concurrent reads and writes continue).

fastupdate: must be on (the default). Every insert goes through the pending list; fastupdate = off is refused by CREATE INDEX and ALTER INDEX ... SET (4.4 and earlier accepted and ignored it).

q, range_size_blocks: accepted for compatibility; q must be 3, and range_size_blocks is ignored since 3.2.0.

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.

Pending list

SET pg_tre.pending_list_limit = 0;       -- KiB; 0 (default) = only VACUUM merges
SET pg_tre.fastupdate = on;              -- must be on

pg_tre.pending_list_limit applies to indexes whose pending_list_limit storage parameter is unset (-1). Both are PGC_USERSET.

---

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. The posting merge produces TID set {1}, and the recheck confirms it.

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: ```sql – 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.

Measurements are in doc/perf.md.

Scan Pipeline

1. SuRF prefilter (anchored and prefix patterns): a succinct range filter over the indexed trigrams rejects a ^-anchored or LIKE 'foo%' scan outright when no indexed trigram falls in the prefix’s key range.

2. Posting lists: per-trigram sparsemap postings, AND/OR merged according to the query’s trigram formula (CNF for k=0, k+1 tiles OR-ed for k>0). This produces the candidate TID set.

3. Recheck: candidate rows are fetched from the heap and TRE’s regaexec runs the full approximate match. Recheck is mandatory: the index is lossy.

The per-tuple bloom tier was removed in 3.0.0 and the range-bloom tier in 3.2.0.

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 + 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

Character encoding and collations

Trigrams are built from characters of the database encoding (4.3.0+; UTF-8 only before), and TRE matches – including approximate matching, where an edit is one character – in the same unit, in every server encoding. Regex classes and case folding follow the collation of the expression (the index column’s for an index scan), as core’s ~ does; nondeterministic collations are refused, at index build and by the match functions. See LIMITATIONS.md.

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: sql 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²) 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: “regex too complex”

Fix: Raise pg_tre.max_nfa_states: sql 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

To check an index against a sequential scan, run SELECT * FROM pg_tre_index_check('your_index'); (4.5.0+).

Seq Scan Always Chosen

Diagnosis: sql 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: sql 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

---

Internals Pointers

For architecture and on-disk format details, see:

• doc/design.md — Extraction pipeline, posting lists, recheck flow
• doc/onpage_format.md — Page layouts, WAL records, format versioning
• STATUS.md — Release status

For hacking on pg_tre: - src/query/extract.c — Trigram extraction and tiling - src/am/amscan.c — Scan: SuRF prefilter, posting merge, recheck - src/pages/posting.c — Posting tree 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

Patches welcome via Codeberg PR or email to the author.