Fuzzy search with pg_trgm

Draft

Users make typos. ILIKE and full-text search both need the right spelling: "postgress" finds nothing. The pg_trgm extension compares strings by how many 3-letter chunks, trigrams, they share, so a word with a letter missing or swapped still scores close to the original.

Same eight documents as the vectors lesson, without the embeddings.

The documents

-- CREATE EXTENSION also makes PGlite load pg_trgm for this database.
CREATE EXTENSION pg_trgm;

CREATE TABLE documents (
  id SERIAL PRIMARY KEY,
  title TEXT NOT NULL,
  body TEXT NOT NULL
);

Loaded Database:fuzzy-search.database-init

INSERT INTO documents (title, body)
VALUES
  ('SQL indexes', 'Indexes help PostgreSQL find rows without reading the whole table.'),
  ('JOIN patterns', 'Joins combine rows from related tables into one result.'),
  ('Query tuning', 'Slow queries get faster with the right index and a better plan.'),
  ('React components', 'Components split a user interface into small reusable pieces.'),
  ('CSS grid layouts', 'Grid and flexbox position elements on a web page.'),
  ('Neural networks', 'Neural networks learn patterns from training data.'),
  ('Chatbots', 'Language models answer questions written in natural language.'),
  ('Vector search', 'Embeddings let a database find documents with a similar meaning.');

Trigrams

pg_trgm lowercases a string, pads each word with spaces, and cuts it into every 3-letter chunk.

Loaded Database:fuzzy-search.database-init

SELECT show_trgm('Index')::text AS index, show_trgm('Indx')::text AS typo;

index	typo
{" i"," in",dex,"ex ",ind,nde}	{" i"," in","dx ",ind,ndx}

Result  (cost=0.00..0.02 rows=1 width=64)

Similarity

similarity() is the share of trigrams two strings have in common: 1 is identical, 0 is nothing shared. A search with two typos still finds the right document.

Loaded Database:fuzzy-search.database-init

SELECT title, round(similarity(title, 'nueral netwrks')::numeric, 3) AS score
FROM documents
ORDER BY score DESC
LIMIT 3;

title	score
Neural networks	0.400
Query tuning	0.038
JOIN patterns	0.000

Limit  (cost=35.86..35.87 rows=3 width=64)
  ->  Sort  (cost=35.86..37.99 rows=850 width=64)
        Sort Key: (round((similarity(title, 'nueral netwrks'::text))::numeric, 3)) DESC
        ->  Seq Scan on documents  (cost=0.00..24.88 rows=850 width=64)

The % operator

title % 'reakt componets' is true when the similarity is above pg_trgm.similarity_threshold, 0.3 by default. Use it in WHERE, and an index can help.

Loaded Database:fuzzy-search.database-init

SELECT title, round(similarity(title, 'reakt componets')::numeric, 3) AS score
FROM documents
WHERE title % 'reakt componets';

title	score
React components	0.500

Seq Scan on documents  (cost=0.00..20.68 rows=8 width=64)
  Filter: (title % 'reakt componets'::text)

A word inside longer text

similarity() compares whole strings, so one word against a sentence scores low. word_similarity() finds the best matching part of the text instead: 'postgress' is close to 'PostgreSQL'.

Loaded Database:fuzzy-search.database-init

SELECT
  title,
  round(similarity('postgress', body)::numeric, 3) AS whole,
  round(word_similarity('postgress', body)::numeric, 3) AS best_word
FROM documents
ORDER BY best_word DESC
LIMIT 3;

title	whole	best_word
SQL indexes	0.127	0.800
CSS grid layouts	0.057	0.300
Query tuning	0.014	0.100

Limit  (cost=42.24..42.24 rows=3 width=96)
  ->  Sort  (cost=42.24..44.36 rows=850 width=96)
        Sort Key: (round((word_similarity('postgress'::text, body))::numeric, 3)) DESC
        ->  Seq Scan on documents  (cost=0.00..31.25 rows=850 width=96)

Did you mean

<-> is the trigram distance, 1 - similarity. ORDER BY it with LIMIT 1 for a 'did you mean' suggestion.

Loaded Database:fuzzy-search.database-init

SELECT title AS did_you_mean
FROM documents
ORDER BY title <-> 'css grd layot'
LIMIT 1;

did_you_mean
CSS grid layouts

Limit  (cost=24.88..24.88 rows=1 width=36)
  ->  Sort  (cost=24.88..27.00 rows=850 width=36)
        Sort Key: ((title <-> 'css grd layot'::text))
        ->  Seq Scan on documents  (cost=0.00..20.62 rows=850 width=36)

Trigram indexes

Without an index, every function above scores every row. pg_trgm comes with two operator classes. The slow queries lesson uses the GIN one to fix a slow ILIKE search.

Loaded Database:fuzzy-search.indexed-database-init

-- GIN: speeds up %, <%, LIKE and ILIKE '%...%'.
CREATE INDEX documents_title_trgm_idx ON documents
USING gin (title gin_trgm_ops);

-- GiST: can also return rows ordered by <-> distance, nearest first.
CREATE INDEX documents_title_trgm_gist_idx ON documents
USING gist (title gist_trgm_ops);

An index for ILIKE

A B-tree can't answer ILIKE '%...%': the match can start anywhere. A trigram index can: it finds the rows containing every trigram of the pattern. Both trigram indexes support ILIKE; here the planner picks the GiST one.

Loaded Database:fuzzy-search.indexed-database-init

SELECT title
FROM documents
WHERE title ILIKE '%note 4711%';

title
Mysql search note 4711

Index Scan using documents_title_trgm_gist_idx on documents  (cost=0.15..8.17 rows=1 width=24)
  Index Cond: (title ~~* '%note 4711%'::text)

An index for nearest matches

A GiST trigram index returns rows already ordered by <-> distance, so a typo-tolerant autocomplete reads a handful of rows instead of scoring all 5,008.

Loaded Database:fuzzy-search.indexed-database-init

SELECT title
FROM documents
ORDER BY title <-> 'Redis chatbot note 42'
LIMIT 3;

title
Redis chatbots note 4223
Redis chatbots note 463
Redis chatbots note 4703

Limit  (cost=0.15..0.53 rows=3 width=28)
  ->  Index Scan using documents_title_trgm_gist_idx on documents  (cost=0.15..632.31 rows=5008 width=28)
        Order By: (title <-> 'Redis chatbot note 42'::text)

When to use it

Trigrams are good at short strings where spelling matters: names, titles, product names, tags, autocomplete, "did you mean". They know nothing about words or meaning: "running" and "ran" share few trigrams, which full-text search handles, and "car" and "vehicle" share none, which vector search handles.

Text search in Postgres compares all the approaches side by side.

What We Learned

pg_trgmcompares strings by the 3-letter chunks they share.
similarity() and %a 0-to-1 score for two whole strings, and a threshold test on it.
word_similarity() and <%the best match for a word anywhere inside a longer text.
<->trigram distance, for ORDER BY ... LIMIT "did you mean" lookups.
gin_trgm_ops, gist_trgm_opstrigram indexes: GIN for % and ILIKE, GiST also for ordering by distance.