Typo Tolerant Search With pg_trgm in PostgreSQL Queries

A user types "postgress" or "adress", the full text search returns nothing, and the page says "no results". Stemming cannot fix spelling. The extension pg_trgm can: it compares strings by the three-letter pieces they share, so near-misses score high. It is bundled with PostgreSQL, works with ordinary indexes and also speeds up LIKE '%term%'. This article shows the mechanism, the operators and thresholds, the indexes and how to combine it with full text search. It is one of the pieces of the cluster introduced by full text search in PostgreSQL before you add Elasticsearch.

What a trigram is

A trigram is three consecutive characters. PostgreSQL lowercases the string, treats non-alphanumeric characters as word separators, pads each word with two spaces in front and one behind, then takes all three-character windows:

CREATE EXTENSION IF NOT EXISTS pg_trgm;
SELECT show_trgm('cat');
-- {"  c"," ca","cat","at "}

Similarity is the number of trigrams two strings share divided by the number of distinct trigrams in either:

SELECT similarity('postgres', 'postgress'),   -- high, about 0.7
       similarity('postgres', 'mysql');       -- low, near 0

A typo changes at most three trigrams, so a long word with one error still shares most of its trigrams, and a short word loses a larger share. The score runs from 0 (nothing in common) to 1 (identical trigram sets).

The operators

A basic typo-tolerant lookup:

SELECT name, similarity(name, 'postgress') AS sim
FROM product
WHERE name % 'postgress'
ORDER BY sim DESC
LIMIT 10;

The % operator filters by the threshold, and the ORDER BY puts the closest first. Using ORDER BY name <-> 'postgress' lets a GiST index return nearest neighbors directly, which is faster for "top 10 closest" queries over large tables.

Indexes

Without an index, trigram search scans the table. Two index types support the operators:

CREATE INDEX product_name_trgm_gin  ON product USING gin  (name gin_trgm_ops);
CREATE INDEX product_name_trgm_gist ON product USING gist (name gist_trgm_ops);

GIN is faster for lookups, bigger and slower to update. GiST is smaller and quicker to update, and it supports ordering by distance (<->), which GIN does not for plain similarity. For a table that is mostly read and queried with % or LIKE, choose GIN. For nearest-neighbor ordering on a large table, choose GiST. The same index also accelerates LIKE '%term%', ILIKE and regular expression matches, because those patterns can be answered through trigrams:

SELECT name FROM product WHERE name ILIKE '%postg%';

That removes the main problem with substring search, a full scan, although a query shorter than three characters has no trigrams and still scans. See GIN versus GiST and the tradeoffs for the comparison.

Choosing the threshold

The default 0.3 is a compromise. Lower values find more candidates and more noise, higher values are stricter. Set it per session or per query:

SET pg_trgm.similarity_threshold = 0.4;
SELECT name FROM product WHERE name % 'postgress';

Tune it with data: collect real misspelled queries and the products they should find, then check the recall and the noise at 0.2, 0.3, 0.4 and 0.5. The threshold interacts with string length: for 5-letter strings, one typo drops similarity a lot, and for 20-letter strings it barely moves. A single global threshold is a rough fit for both; use a higher threshold when you can require longer input, or compute the threshold from the query length.

Words inside longer text

similarity compares whole strings, so a short query against a long title scores low even if the title contains the word. word_similarity(query, text) finds the best-matching stretch of the text:

SELECT title, word_similarity('postgress', title) AS ws
FROM article
WHERE 'postgress' <% title
ORDER BY ws DESC
LIMIT 10;

The operator <% returns true when the word similarity exceeds its threshold (0.6 by default). This is the right tool for finding a term inside a sentence-length title. There is also strict_word_similarity, which respects word boundaries, for stricter matching. For documents longer than a title, trigram search becomes impractical; the index is large and the match is vague, so use full text search and use trigrams on short fields only.

Combining with full text search

The two techniques solve different problems, and a good search uses both. The pattern: run the full text query. If it returns enough results, show them. If it returns few or none, try the trigram query on titles to find corrections or near matches, and either show those results labeled "similar matches" or offer "Did you mean ...".

A suggestion query for corrections draws on the words in your corpus:

CREATE MATERIALIZED VIEW search_word AS
SELECT word FROM ts_stat('SELECT search FROM article');
CREATE INDEX search_word_trgm ON search_word USING gin (word gin_trgm_ops);

SELECT word FROM search_word
WHERE word % 'postgress'
ORDER BY word <-> 'postgress'
LIMIT 3;

ts_stat lists every lexeme in the corpus, so the view holds the vocabulary of what the site actually contains. Suggestions come from words that exist, not from a general dictionary. Because lexemes are stems, show the stem only as a hint, or keep a second view of original words from a tokenization of the text. Refresh the view on a schedule. This is the basis of "did you mean" without an external service.

Performance and cost

GIN trigram indexes are large, often larger than the column: every string contributes many trigrams. A 100-character name yields about 100 trigrams. For millions of rows, that is gigabytes, so index only the fields you search this way, and not entire body columns. Updates touch many index entries, like other GIN indexes, with the same pending list behavior covered in indexing full text search with GIN.

Short queries are the failure mode. A two-letter query has too few trigrams to be selective, and % on a very short string matches many rows. Enforce a minimum length (three or four characters), and for shorter input use a prefix match, as in prefix search and autocomplete in PostgreSQL.

Case, accents and normalization

Trigrams are computed on lowercased text, so matching is case-insensitive. They do not remove accents. similarity('cafe', 'café') is lower than you may want; combine with unaccent by indexing unaccent(name) with an immutable wrapper function, since the extension's function is only stable. Normalize both sides the same way, and index the same expression you query.

When trigram matching returns too much noise

Trigram similarity struggles with several kinds of data. Very short strings, such as three-letter codes, have so few trigrams that unrelated strings overlap. Long text produces middling scores for nearly everything. Strings that share common affixes ("international", "intercontinental") look similar though they are not. Data where order matters, like phone numbers, benefits from exact or prefix matching and not similarity. And a typo at the start of a word is as costly as anywhere else for similarity but ruins prefix matching, so autocomplete needs separate handling.

When noise is a problem, raise the threshold, require a minimum length, rank by a mix of similarity and popularity, or restrict matching to a field of reasonable length. If quality remains insufficient, specialized fuzzy matching in a search engine, which uses edit-distance automata with prefix constraints, is the next step, as discussed in when PostgreSQL search stops being enough.

What to do next

Create the extension on a copy, add a GIN trigram index on one short column and run twenty misspelled queries from your logs at thresholds 0.2 to 0.5. The manual documents the module in pg_trgm, including the operators, indexes and the threshold settings, and describes the vocabulary function in text search statistics. For more uses of the same extension, see pg_trgm beyond search.