Full text search and the inverted index

Every search feature starts the same way:

SELECT * FROM products
WHERE name ILIKE '%laptop%'
   OR description ILIKE '%laptop%';

At five thousand rows this returns in 50ms and nobody thinks about it again. At five million rows it takes 30 seconds, and when you go looking for the reason you find that there is no index that can help you. A B-tree index on name sorts by prefix. '%laptop%' has no prefix — the leading wildcard means any row could match, so Postgres reads all of them and does character-by-character pattern matching on every text field.

That is the first problem. The second one is worse, and it does not go away no matter how fast you make the query.

The database has no idea what is relevant

Say the query matches two rows: a product titled "MacBook Pro 14-inch laptop" and a laptop bag whose description mentions the word "laptop" once, at the end, in a compatibility note. ILIKE says both are matches. It has no opinion about which one the user wanted. You get them back in whatever order the planner felt like, and unless you invent your own ordering, the bag can land first.

This is the librarian problem. A librarian who knows exactly where every book is shelved, but when you ask for books about machine learning, walks the stacks checking one spine at a time — Harry Potter, no; Game of Thrones, no; Introduction to Machine Learning, yes — and keeps going to the end of the library. Slow, and when it finally hands you a stack, a book that mentions machine learning once on the last page sits on top of the one with it in the title.

Both problems come from the same thing: the search goes from documents to terms.

Invert it

The fix, worked out in information retrieval research going back to the 1960s, is to build the mapping in the other direction ahead of time. When a document arrives, break it into terms and record, for each term, every document it appears in and where:

machine  → intro-to-ml (p1, p15, p23)
           the-machine-age (p5, p89)
           coffee-machine-manual (p1)
learning → intro-to-ml (p1, p16, p24)
           learning-to-cook (p4, p31)
           deep-learning-fundamentals (p2, p8, p40)

That is an inverted index. A search for machine learning is now two hash lookups and a set intersection. You never touch a document that does not contain the terms. The cost of the query stops scaling with the size of the corpus and starts scaling with the size of the matching posting lists.

This is what Apache Lucene implements, and Lucene is what Elasticsearch is built on. It is also what Postgres tsvector / GIN is doing, and what every other full text search tool is doing underneath. The technique is old and shared; the products differ in what they wrap around it.

"Elasticsearch is fast" is the wrong mental model. Elasticsearch is a distributed, operationally opinionated wrapper around an inverted index. The index is the fast part.

Relevance falls out of the same structure

Look at the index again. It already knows how many times machine appears in each document, how many documents contain machine at all, and — if you record fields — whether the hit was in the title or in the body. That is enough to score.

BM25, the default scoring function, combines roughly these:

• Term frequency — how often the term appears in this document. Three hits beat one.
• Document frequency — how many documents contain the term at all. A term in every document tells you nothing, so it is worth almost nothing. This is why the does not dominate your results.
• Document length — three hits in a 200-word document is a stronger signal than three hits in a 400-page book. Normalise for it.
• Field boosting — a hit in the title counts more than a hit in the description, which counts more than a hit in the body.

Field boosting is the one you will actually configure, and it is not fixed. You declare the weights per query. If your data has a summary field that is more meaningful than the title, boost the summary.

Typo tolerance is a separate mechanism (edit-distance matching over the term dictionary), but it is the same trick: because you have the full list of indexed terms sitting there, you can find the terms near the one the user typed. Type "what is treading today" into Google and you get results for "trending" — that behaviour is unreachable with ILIKE.

What the numbers look like

The comparison worth running: 50,000 review records loaded into both a Postgres instance and an Elasticsearch index, both in us-west so distance is not a factor, both queried with an equivalent case-insensitive substring search, streamed to the client so neither waits on the other.

Searching laptop: Elasticsearch ~1s, Postgres ~3s. Searching a common term matching about 8,000 rows: Elasticsearch 500ms, Postgres 7.5s. Same result count both sides — the criteria were kept deliberately equivalent. The gap is entirely the scan.

And 50,000 rows is nothing. That is the shape of the curve at the very bottom of it.

Which one to reach for

If you already run Elasticsearch — and a lot of teams do, because it arrived through the ELK stack for log management rather than for product search — use it. The index is already operational, and log search and product search are the same primitive.

If you do not, Postgres full text search is genuinely good and it is one fewer system to run, back up, and keep in sync with your source of truth. That last part is the real cost of a separate search cluster: every write now has two destinations and they can drift.

Either way this is arsenal knowledge, not mastery knowledge. Databases you have to actually understand, down to how the indexes work, because that is 99% of your backend. Full text search you can get most of the way with the docs and a snippet. Recognising that a query has become a search problem is the part worth having.