# 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](https://github.com/laurikari/tre) 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:

```sql
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

```bash
# 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)

```sql
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)

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

```sql
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+)

```sql
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

```sql
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

```sql
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)

```sql
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

```sql
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)

```sql
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

```sql
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)

```sql
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)

```sql
-- 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

```sql
-- 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

```sql
-- 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

```sql
-- "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](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

```sql
-- 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^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: "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](design.md)** — Extraction pipeline, posting lists, recheck flow
- **[doc/onpage_format.md](onpage_format.md)** — Page layouts, WAL records, format versioning
- **[STATUS.md](../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](../LICENSE).

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

Full attribution in [../NOTICE](../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.