Pencocokan Fuzzy dengan Kemiripan pg_trgm

Users misspell things. They type jonh instead of john, or postgers instead of postgres. A plain = or even LIKE comparison returns nothing for these typos.

Fuzzy matching finds rows that are close enough to the search term, not just exact matches. PostgreSQL ships this capability in the pg_trgm extension, which powers:

• Typo-tolerant search — match despite small spelling errors
• Autocomplete — suggest as the user types
• Deduplication — find near-duplicate names or addresses

The key idea is measuring similarity rather than equality.

A trigram is a group of three consecutive characters in a string. pg_trgm breaks every string into its set of trigrams, padding the start and end with spaces.

For the word cat, PostgreSQL produces the trigrams: " c", " ca", "cat", "at ". You can inspect this yourself with show_trgm().

Two strings are considered similar when they share many trigrams. Because trigrams overlap, a single typo only damages a few of them, so similar words still share most of their set.

The core measure is similarity(a, b). It returns a real between 0 (no shared trigrams) and 1 (identical strings).

Internally it is the count of shared trigrams divided by the count of the union of both trigram sets (a Jaccard-style ratio). The closer the spelling, the higher the score.

Notice how a single typo only drops the score a little, while an unrelated word scores near zero.

Writing similarity(a, b) > threshold everywhere is verbose, and more importantly it cannot use a trigram index directly. Instead, pg_trgm gives you the % operator.

a % b returns true when the similarity of the two strings exceeds the current similarity threshold. This operator is index-aware, so a GIN or GiST trigram index can accelerate it.

The default threshold is 0.3. You read the session value with show_limit() (legacy) or the GUC pg_trgm.similarity_threshold.

The threshold controls the trade-off between recall (catching more matches) and precision (avoiding junk matches).

• Lower threshold (e.g. 0.2) → more permissive, more results, more false positives
• Higher threshold (e.g. 0.5) → stricter, fewer results, risk of missing real typos

Set it per session with SET pg_trgm.similarity_threshold. The % operator immediately respects the new value, and any index scan stays valid.

Without an index, % forces a sequential scan that computes similarity for every row — fine for hundreds of rows, painful for millions. pg_trgm supports two index types:

• GIN (gin_trgm_ops) — faster lookups, smaller-to-build for read-heavy search; usually the default choice.
• GiST (gist_trgm_ops) — supports distance ordering for KNN (<->) and can be cheaper to update.

For typical typo-tolerant search you want GIN. Build it on the column you search.

A trigram GIN index does more than help %. Because PostgreSQL can extract trigrams from a LIKE or ILIKE pattern, the same index also speeds up wildcard searches like '%board%' — including leading wildcards that a normal B-tree cannot use.

Run EXPLAIN ANALYZE and look for a Bitmap Index Scan on your trigram index instead of a Seq Scan. That confirms the planner is using it.

Matching is only half the job — users expect the best match first. Filter with % (index-friendly) and then sort with similarity() in ORDER BY.

Keep the WHERE name % :q predicate so the index narrows candidates, then rank the survivors. Computing similarity() only on the filtered set is cheap.

For pure "give me the N closest names" queries, pg_trgm offers the distance operator <->, defined as 1 - similarity(a, b). Smaller distance means more similar.

When you ORDER BY column <-> :q, a GiST trigram index can return rows in distance order directly (a KNN index scan) — no sort step, no explicit threshold needed. This is ideal for autocomplete and "closest match" lookups.

Plain similarity() penalizes length differences: matching the short query app against the long string apple smartphone pro scores low because most trigrams belong to the longer text.

word_similarity(a, b) fixes this by finding the best-matching contiguous portion of b. It has its own operator <% and its own GUC pg_trgm.word_similarity_threshold (default 0.6) — perfect for autocomplete where the query is a prefix or single word.

A few things commonly trip people up with pg_trgm:

• Very short queries (1-2 chars) have almost no trigrams, so similarity is unreliable — gate autocomplete on a minimum length.
• Case and accents: trigram matching is case-insensitive for similarity, but normalize accents (e.g. via unaccent) if your data needs it.
• Index choice: don't reach for GiST unless you need <-> KNN ordering; GIN is usually faster for %.
• Threshold per use case: search, autocomplete, and dedup often want different thresholds — set them per session, not globally.

Test your understanding of trigram search performance.

You can now build fast, typo-tolerant search in PostgreSQL with pg_trgm:

• Trigrams split strings into 3-character chunks; shared chunks mean similarity.
• similarity() scores 0-1; the % operator filters by the pg_trgm.similarity_threshold (default 0.3) and is index-aware.
• Build a GIN index (gin_trgm_ops) to accelerate %, LIKE, and ILIKE — including leading wildcards.
• Filter with %, then rank with similarity() in ORDER BY; or use <-> distance with a GiST index for KNN ordering.
• Use word_similarity / <% for autocomplete, and tune thresholds per use case.

Always confirm with EXPLAIN ANALYZE that you get a Bitmap (or KNN) Index Scan rather than a Seq Scan.