Trigram Indexes for LIKE and ILIKE #

A customer-lookup box runs WHERE name ILIKE '%hans%'. On 40 million customers it scans the table every keystroke. There is an index on name, and it cannot help: a B-tree orders strings from the left, and a search that may match anywhere in the string has no starting point in that order.

Access-method selection is covered in specialized index types (GIN/GiST). This page covers the extension that makes substring search indexable.

The Index Condition #

pg_trgm decomposes text into trigrams — overlapping three-character sequences, with padding at word boundaries. hans becomes h, ha, han, ans, ns . A search string is decomposed the same way, and the index finds rows sharing enough trigrams, after which the executor rechecks the original condition.

That makes these indexable:

Two operator classes:

What trigrams cannot do: help patterns whose literal part is shorter than three characters (LIKE '%an%' yields no usable trigram), and they are lossy, so every candidate row is rechecked — visible as a Recheck Cond and, for GiST, sometimes many removed rows.

When the pattern is anchored at the start — LIKE 'hans%' — a trigram index is unnecessary: a B-tree with text_pattern_ops (or a database in the C collation) serves prefix searches directly, and lower(name) text_pattern_ops handles the case-insensitive variant.

Which index does this pattern need? Three cases. A prefix pattern anchored at the start is served by a B-tree with text_pattern_ops. A substring or case-insensitive pattern needs a trigram index, GIN for filtering. A ranked nearest-match search needs a GiST trigram index for distance ordering. what shape is the search? LIKE 'term%' (prefix) btree text_pattern_ops no extension needed LIKE '%term%' / ILIKE gin_trgm_ops lossy, rechecked ORDER BY name <-> 'term' gist_trgm_ops distance ordering patterns with fewer than three literal characters cannot use trigrams

Annotated EXPLAIN Evidence #

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, name FROM customers WHERE name ILIKE '%hans%' LIMIT 20;

Before:

Limit  (actual time=0.4..4120.6 rows=20 loops=1)
  ->  Seq Scan on customers  (actual rows=20 loops=1)
        Filter: (name ~~* '%hans%'::text)
        Rows Removed by Filter: 8204110
        Buffers: shared hit=41022 read=182044
Execution Time: 4120.9 ms

After:

CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX CONCURRENTLY customers_name_trgm_idx ON customers USING gin (name gin_trgm_ops);
Limit  (actual time=8.2..8.4 rows=20 loops=1)
  ->  Bitmap Heap Scan on customers  (actual rows=20 loops=1)
        Recheck Cond: (name ~~* '%hans%'::text)
        Rows Removed by Index Recheck: 112
        Heap Blocks: exact=1840
        ->  Bitmap Index Scan on customers_name_trgm_idx  (actual time=6.1..6.1 rows=1952 loops=1)
              Index Cond: (name ~~* '%hans%'::text)
Execution Time: 8.5 ms
-- 1,952 candidates from trigrams; 112 rejected by the recheck

A short pattern, where trigrams cannot help:

EXPLAIN (ANALYZE) SELECT id FROM customers WHERE name ILIKE '%an%' LIMIT 20;

Limit → Seq Scan on customers  Filter: (name ~~* '%an%'::text)
-- two literal characters: no trigram can be extracted, so the index is unusable
Reading a trigram search plan Three lines are annotated. A Bitmap Index Scan on the trigram index producing candidate rows. Rows Removed by Index Recheck showing the lossy match being verified. A sequential scan for a two-character pattern, which yields no trigrams. Bitmap Index Scan … (rows=1952) trigram candidates Rows Removed by Index Recheck: 112 lossy match, rechecked on the heap '%an%' → Seq Scan fewer than 3 literal characters candidate count versus final rows shows how selective the trigrams were

Step-by-Step Resolution #

  1. Classify the patterns your application sends. Prefix, substring, case-insensitive, regular expression, or ranked similarity — each has a different answer.

  2. For prefix-only searches, avoid the extension:

    CREATE INDEX CONCURRENTLY customers_name_prefix_idx ON customers (lower(name) text_pattern_ops);
-- query: WHERE lower(name) LIKE lower('hans') || '%'

  3. For substring or case-insensitive searches, create a GIN trigram index. ILIKE works directly; there is no need to index lower(name) as well.

  4. For ranked “closest match” results, use GiST and order by distance:

    CREATE INDEX CONCURRENTLY customers_name_trgm_gist ON customers USING gist (name gist_trgm_ops);
SELECT name FROM customers ORDER BY name <-> 'hans' LIMIT 10;

  5. Enforce a minimum search length in the application — three characters — so short patterns never reach the database as unindexable scans.

  6. Tune the similarity threshold when using %: SET pg_trgm.similarity_threshold = 0.4 trades recall for candidate count.

  7. Check size and write cost. Trigram indexes are large; on ingest-heavy tables, consider indexing only the rows that are searchable with a partial index.

Search cost by index type The sequential scan takes 4,121 milliseconds. The GIN trigram index takes 8.5 milliseconds and occupies 6.2 gigabytes. The GiST trigram index takes 41 milliseconds for the same filter and occupies 9.4 gigabytes, but supports distance ordering. The prefix B-tree takes 0.1 milliseconds and occupies 1.8 gigabytes but only serves anchored patterns. Seq Scan 4,121 ms GIN trigram 8.5 ms, 6.2 GB GiST trigram 41 ms, 9.4 GB prefix B-tree 0.1 ms, 1.8 GB the prefix index is fastest but only for anchored searches

Before and After #

-- BEFORE: ILIKE '%hans%' with no trigram index
Seq Scan on customers  Rows Removed by Filter: 8204110  Buffers: read=182044    Execution Time: 4120.9 ms

-- AFTER: gin (name gin_trgm_ops)
Bitmap Heap Scan  Recheck Cond: (name ~~* '%hans%')  Heap Blocks: exact=1840     Execution Time: 8.5 ms

Trigrams versus full-text search #

Trigram search matches character sequences; full-text search matches words after stemming and stop-word removal. They answer different questions. “Find the customer whose name contains this fragment, including misspellings” is a trigram problem. “Find documents about billing errors” is a full-text problem, and a tsvector column with a GIN index is both smaller and more accurate for it.

The two can coexist: a support system might use full-text search on ticket bodies and trigram search on customer names in the same schema. What does not work well is using trigrams as a general document search, because index size grows with text length and candidate sets become large, making the recheck step dominant.

For multi-column searches — name, email and phone in one box — index each column separately and combine with OR, letting the planner build a BitmapOr, as described in BitmapOr and BitmapAnd plans. A single index on a concatenation is tempting but loses the ability to search one field precisely.

Keeping the candidate set small #

A trigram search’s cost has two parts: finding candidates in the index, and rechecking them against the heap. The recheck is where a badly chosen search degrades. A term made of common trigrams — son in a table of Scandinavian surnames — produces hundreds of thousands of candidates, and the plan spends its time reading heap pages only to reject most of them. The plan shows this as a large Rows Removed by Index Recheck next to a small final row count.

Three mitigations help. Combine the trigram condition with a selective equality where one exists, so the bitmap intersects with a smaller set. Add LIMIT and let the bitmap heap scan stop early, which works well for type-ahead search. And where the application searches structured fields, prefer an exact or prefix condition when the user’s input looks like one — an email fragment containing @, or a numeric customer id — reserving substring search for genuinely fuzzy input.

Common Pitfalls #

Short search terms. Fewer than three characters yield no trigrams. Diagnostic signal: sequential scans for short queries only. Fix: enforce a minimum length in the UI.

Indexing lower(name) for ILIKE. Unnecessary with trigrams, which handle case-insensitive matching. Diagnostic signal: duplicate trigram indexes. Fix: one index on the column.

Choosing GiST for filtering. It is slower and larger than GIN for plain matching. Diagnostic signal: high recheck counts and long index scans. Fix: GIN unless distance ordering is needed.

Trigram indexes on huge text columns. Index size explodes with document length. Diagnostic signal: an index several times the table size. Fix: full-text search for documents.

Frequently Asked Questions #

How do I make LIKE ‘%text%’ use an index in PostgreSQL? #

Install the pg_trgm extension and create a GIN index with gin_trgm_ops on the column. Trigram matching turns substring and case-insensitive patterns into index conditions, with a recheck against the heap.

Should I use GIN or GiST for trigram indexes? #

GIN for filtering: it is usually smaller and faster for matching. GiST when you need distance ordering, such as ORDER BY column <-> ‘term’ for ranked nearest matches.

Why does my trigram index not help short search terms? #

Trigrams are three characters long, so a pattern with fewer than three literal characters produces none and the index cannot be used. Require at least three characters before querying.

Up: Specialized Index Types (GIN/GiST)