pg_tre 1.1.1：PostgreSQL 18 的近似正規表達式索引存取方法，三層漏斗架構實現毫秒內模糊搜尋
PostgreSQL News · 2026-05-22
pg_tre 1.1.1 釋出，這是一個 PostgreSQL 18+ 的原生索引存取方法（Index Access Method），支援帶有 Levenshtein 距離預算的近似正規表達式比對——讓你可以用 SQL 查詢「與 error 最多相差一個字元的所有文字」並且索引加速，在百萬筆資料中達到毫秒級回應。
背景：近似正規表達式的需求
傳統正規表達式索引（如 PostgreSQL 的 pg_trgm）只支援精確字元比對，無法處理拼寫錯誤、OCR 錯誤或跨語言音譯的查詢場景。Levenshtein 距離模糊比對雖然可行，但在大型資料集上線性掃描代價過高。pg_tre 透過三層漏斗架構解決這個問題，底層使用 Ville Laurikari 的 TRE 函式庫執行 NFA-based 近似正規表達式比對。
三層漏斗架構
- BRIN-style range bloom filters：粗粒度範圍過濾，快速排除整個 page 範圍
- Sparsemap trigram postings：中間層 trigram 倒排索引，縮小候選集
- Per-tuple bloom filters：細粒度每行過濾，進一步排除
- TRE library heap recheck：對剩餘候選行執行精確 Levenshtein 驗證
規格細節
索引支援每子表達式獨立設定編輯距離預算，例如：
CREATE INDEX docs_body_tre ON docs USING tre (body);
-- 找出 body 中包含「最多 1 次編輯」的 error 的記錄
SELECT id FROM docs
WHERE body %~~ tre_pattern('(error){~1}', 1);功能包含：完整 WAL 覆蓋與 VACUUM 感知、REINDEX CONCURRENTLY 支援、UTF-8 正確處理（CJK、重音字元、emoji），以及針對 DoS 的可設定 NFA 狀態數量上限。對「從百萬筆資料中回傳少數幾行」的查詢，通常達到毫秒以下的回應時間。