LIKE '%term%' was scanning 20 million rows on every search keystroke

Our internal admin tool has a search box for orders. Support types part of a customer name, an email or an order reference, and results appear as they type. It worked fine for years. As the orders table passed 20 million rows, the search started taking 6 to 9 seconds per request, and because the box searched on every keystroke (with a short debounce), one agent typing a name could keep three or four of these queries running at once. On busy mornings the database CPU sat at 100 percent, and unrelated queries slowed down.

pg_stat_statements put it at the top by total time:

SELECT calls, round(mean_exec_time) AS mean_ms, round(total_exec_time/1000) AS total_s, left(query, 80)
FROM pg_stat_statements ORDER BY total_exec_time DESC LIMIT 3;

 calls | mean_ms | total_s |                                      left
-------+---------+---------+------------------------------------------------------------------------------
 41822 |    7310 |  305718 | SELECT id, reference, customer_name, email, total FROM orders WHERE customer_
  ...

The query:

SELECT id, reference, customer_name, email, total
FROM orders
WHERE customer_name ILIKE '%' || $1 || '%'
   OR email ILIKE '%' || $1 || '%'
   OR reference ILIKE '%' || $1 || '%'
ORDER BY created_at DESC
LIMIT 50;

The plan

EXPLAIN (ANALYZE, BUFFERS) SELECT ... WHERE customer_name ILIKE '%lindq%' OR ...;

Limit  (actual time=7104.551..7104.590 rows=50 loops=1)
  ->  Gather Merge  (actual time=7104.549..7104.580 rows=50 loops=1)
        Workers Launched: 2
        ->  Sort  (actual time=7091.20..7091.21 rows=38 loops=3)
              ->  Parallel Seq Scan on orders  (actual time=21.4..7090.8 rows=41 loops=3)
                    Filter: ((customer_name ~~* '%lindq%') OR (email ~~* '%lindq%') OR (reference ~~* '%lindq%'))
                    Rows Removed by Filter: 6914233
                    Buffers: shared hit=118220 read=1610455
Execution Time: 7104.9 ms

A parallel sequential scan of the whole table, reading 1.6 million pages from disk, to return 123 rows. There were B-tree indexes on all three columns. None was used.

Why a B-tree index cannot answer '%term%'

A B-tree index keeps values sorted. That makes it excellent for equality and for prefix searches: LIKE 'lind%' means "everything between lind and line", a contiguous range in sorted order. (In PostgreSQL this needs the text_pattern_ops operator class or the C collation for LIKE to use the index.)

LIKE '%lindq%' asks for values that contain lindq anywhere. Those values are scattered across the whole sorted order: "Ann Lindqvist" sorts under A, "Lindqvist AB" under L. There is no range to jump to, so the database has no choice but to check every value. ILIKE adds case-insensitivity and does not change anything here.

The same is true in MySQL: an index on customer_name is used for LIKE 'lind%' and ignored for LIKE '%lind%'.

Two different tools

There are two common ways to make "contains" searches fast, and they solve different problems.

Trigram indexes (PostgreSQL pg_trgm) break each value into every sequence of three characters: lindqvist becomes lin, ind, ndq, dqv, qvi, vis, ist (plus padding at the ends). A GIN index maps each trigram to the rows that contain it. A search for %lindq% looks up rows containing all of lin, ind and ndq, then checks only those rows. It supports LIKE/ILIKE with leading wildcards directly, plus similarity matching for typos. It works on any substring, which suits identifiers and emails.

Full-text search breaks text into words, normalises them (lowercase, stemming such as "shipping" to "ship"), and indexes the words. It is built for natural language: searching "shipped late" matches "late shipping". It does not do arbitrary substrings: searching lindq will not match lindqvist unless you use prefix matching (lindq:*).

Environment

We tested both approaches on a copy of production data before choosing.

Option A: trigram GIN index

CREATE EXTENSION IF NOT EXISTS pg_trgm;

CREATE INDEX CONCURRENTLY orders_name_trgm  ON orders USING gin (customer_name gin_trgm_ops);
CREATE INDEX CONCURRENTLY orders_email_trgm ON orders USING gin (email gin_trgm_ops);
CREATE INDEX CONCURRENTLY orders_ref_trgm   ON orders USING gin (reference gin_trgm_ops);

The same ILIKE query, unchanged, now plans as:

Limit  (actual time=18.2..18.3 rows=50 loops=1)
  ->  Sort  (actual time=18.2..18.2 rows=50 loops=1)
        ->  Bitmap Heap Scan on orders  (actual time=4.1..17.9 rows=123 loops=1)
              Recheck Cond: ((customer_name ~~* '%lindq%') OR (email ~~* '%lindq%') OR (reference ~~* '%lindq%'))
              ->  BitmapOr
                    ->  Bitmap Index Scan on orders_name_trgm
                    ->  Bitmap Index Scan on orders_email_trgm
                    ->  Bitmap Index Scan on orders_ref_trgm
Execution Time: 18.6 ms

From 7.1 seconds to 19 milliseconds, with no change to application code.

Caveats we measured:

• Search terms shorter than three characters produce no complete trigram, and the index cannot narrow anything; the query falls back to a scan. We now require at least three characters before searching.
• Index size: the three indexes took 3.1 GB in total, about a quarter of the table.
• Write cost: GIN indexes slow down inserts and updates. PostgreSQL's fastupdate (on by default) buffers new entries in a pending list to soften this. Insert latency on orders rose from 1.9 ms to 2.4 ms at p50, which was acceptable.

Option B: full-text search

ALTER TABLE orders ADD COLUMN search tsvector
  GENERATED ALWAYS AS (
    to_tsvector('simple', coalesce(customer_name, '') || ' ' || coalesce(email, ''))
  ) STORED;

CREATE INDEX CONCURRENTLY orders_search_fts ON orders USING gin (search);

SELECT id, reference, customer_name FROM orders
WHERE search @@ to_tsquery('simple', 'lindq:*')
ORDER BY created_at DESC LIMIT 50;

We used the simple configuration (no stemming) because names should not be stemmed. Adding the generated column rewrote the whole table, which we did in a maintenance window. Queries took 6 to 25 ms, and the index was 1.2 GB.

But full-text search missed things support needed: ORD-2026-0048 should match the reference ORD-2026-0048213, and searching @acme should match emails at that domain. The parser splits those strings in ways that make substring matches unreliable.

What we shipped

Plus two application changes: a minimum of three characters, and a 300 ms debounce with cancellation of the previous request, so a fast typist sends one query, not five.

On MySQL

For a MySQL-based service with the same problem, InnoDB FULLTEXT indexes with the ngram parser (built in since MySQL 5.7.6) give a comparable substring capability:

ALTER TABLE orders ADD FULLTEXT INDEX ft_orders_search (customer_name, email) WITH PARSER ngram;
SELECT id FROM orders WHERE MATCH(customer_name, email) AGAINST ('"lindq"' IN BOOLEAN MODE);

The default ngram_token_size is 2. It behaves differently from LIKE (stopwords, minimum token size, relevance ranking), so we tested result sets against LIKE before switching. Past a certain scale, a dedicated search engine is the next step, at the cost of keeping a second copy of the data in sync.

1. Same results as before. For 500 real search terms from the logs, we compared the IDs returned by the old scan and the new indexed query. They were identical, as expected, because the trigram index only narrows candidates and PostgreSQL rechecks the original ILIKE condition on each one.

2. Latency. Over a week of production traffic, search p50 went from 6.9 s to 21 ms and p99 from 14 s to 140 ms. Database CPU during the morning peak dropped from 100 percent to about 35 percent.

3. Plan regression check. A test runs EXPLAIN for the search query with a three-character term and fails if the plan contains Seq Scan on orders. It runs against a test database with a few hundred thousand rows so the planner prefers the index.

4. Security implications. Search terms go into the query as bound parameters, never concatenated. We also escape % and _ in user input before wrapping it in wildcards, so a user cannot turn their search into a match-everything pattern:

def like_pattern(term: str) -> str:
    escaped = term.replace("\\", "\\\\").replace("%", r"\%").replace("_", r"\_")
    return f"%{escaped}%"

Takeaways

• B-tree indexes handle equality and prefixes. LIKE '%term%' always scans unless you use another index type.
• Trigram indexes (pg_trgm) make substring and fuzzy matching fast with no query changes.
• Full-text search is for words in natural language, not substrings of identifiers.
• Require a minimum term length, debounce search-as-you-type, and escape wildcards in user input.

References: PostgreSQL pg_trgm, PostgreSQL full text search, PostgreSQL GIN indexes, MySQL ngram full-text parser.