用于模糊匹配的三元组索引

概念概述

用于模糊匹配的三元组索引（Trigram Indexes for Fuzzy Matching）指的是：三元组索引把文本拆成三字符序列，使 LIKE、ILIKE 与相似度查询无需扫描每行，但过短的搜索词仍会退化为全表扫描。

从更严格的定义看，A trigram index indexes overlapping three-character substrings of a text value, enabling the planner to translate pattern and similarity predicates into index conditions. 该概念在工程实践中的价值，在于它能帮助团队用统一的语言描述一个具体的质量属性或设计约束，从而在评审与协作中减少歧义。

为什么需要它

It is used for substring search, autocomplete, and typo-tolerant matching where exact equality is too strict. 它与 Full-Text Search Vectors、Advisory Locks、Cost-Based Query Optimization 等概念经常一起出现，用于解决相近的工程问题。理解它的适用场景，有助于在多种备选方案之间做出有依据的取舍，而不是凭直觉选择技术方案。

常见误解

• trigram indexes only help with equality comparisons
• they replace the need for a real full-text search engine

需要避免的反模式

• indexing a very short column where trigrams carry little information
• expecting a trigram index to accelerate leading-wildcard scans on unrelated data

实践要点

1. The extension splits text into trigrams and stores them in a GIN or GiST index, so a pattern that contains at least one literal three-character sequence can be partly satisfied by the index.
2. Patterns with no usable trigram, such as a very short search term, force a full scan, which is why short inputs should be handled or rejected explicitly.
3. The similarity operator returns a score and relies on the same index, letting a query rank near matches by how many trigrams they share.

参考来源

https://www.postgresql.org/docs/current/pgtrgm.html

代码示例

fn find_all(haystack: &str, needle: &str) -> Vec<usize> {
    let hay: Vec<char> = haystack.chars().collect();
    let pattern: Vec<char> = needle.chars().collect();
    if pattern.is_empty() || pattern.len() > hay.len() {
        return Vec::new();
    }

    const BASE: u64 = 257;
    let mut highest = 1u64;
    for _ in 1..pattern.len() {
        highest = highest.wrapping_mul(BASE);
    }

    let mut pattern_hash = 0u64;
    let mut window_hash = 0u64;
    for index in 0..pattern.len() {
        pattern_hash = pattern_hash
            .wrapping_mul(BASE)
            .wrapping_add(pattern[index] as u64);
        window_hash = window_hash
            .wrapping_mul(BASE)
            .wrapping_add(hay[index] as u64);
    }

    let mut matches = Vec::new();
    for start in 0..=hay.len() - pattern.len() {
        if window_hash == pattern_hash && hay[start..start + pattern.len()] == pattern[..] {
            matches.push(start);
        }
        if start + pattern.len() < hay.len() {
            window_hash = window_hash
                .wrapping_sub((hay[start] as u64).wrapping_mul(highest));
            window_hash = window_hash
                .wrapping_mul(BASE)
                .wrapping_add(hay[start + pattern.len()] as u64);
        }
    }
    matches
}

fn main() {
    assert_eq!(find_all("abracadabra", "abra"), vec![0, 7]);
    assert_eq!(find_all("aaaa", "aa"), vec![0, 1, 2]);
    assert_eq!(find_all("short", "longer pattern"), Vec::<usize>::new());
    assert_eq!(find_all("anything", ""), Vec::<usize>::new());
    println!("{:?}", find_all("abracadabra", "abra"));
}

-- PostgreSQL 软删除表：业务查询永远附加 deleted_at IS NULL
CREATE TABLE documents (
  id bigserial PRIMARY KEY,
  owner_id bigint NOT NULL,
  title text NOT NULL,
  deleted_at timestamptz
);

-- 部分索引只覆盖活行：体积与热数据成正比
CREATE INDEX idx_documents_owner_live
  ON documents (owner_id, created_at DESC)
  WHERE deleted_at IS NULL;

-- 命中部分索引：条件必须与索引谓词精确匹配
SELECT id, title
FROM documents
WHERE owner_id = 42
  AND deleted_at IS NULL
ORDER BY created_at DESC
LIMIT 10;

-- 归档查询走另一条路：不占热索引的空间
SELECT id, deleted_at
FROM documents
WHERE owner_id = 42
  AND deleted_at IS NOT NULL
ORDER BY deleted_at DESC
LIMIT 100;

-- 唯一性也按活行生效：同 owner 的活文档标题唯一
CREATE UNIQUE INDEX idx_documents_title_live
  ON documents (owner_id, title)
  WHERE deleted_at IS NULL;