Skip to content

The title contains the word. Why is the database reading every row?

Search Returned an Answer. Was It the Right One? · Part 1 of 6 · 5 min read

Read the worked explanation ↓

Interview question. A marketplace stores 80 million listings in PostgreSQL. The product team changes its search box from exact product codes to arbitrary words inside descriptions. An engineer adds a B-tree index on title and expects LIKE '%camera%' to become fast. The query still examines enormous amounts of data. Explain why and design the next version without simply moving every request to a bigger database.

The first thing I would ask is what the search box promises. Does it match a whole word, a prefix, a phrase, or any sequence of characters? Those are different problems with different indexes. An ordinary B-tree orders complete field values. It can help a supported left-anchored prefix query such as camera%, with the appropriate operator class and collation considerations. With %camera%, the beginning of the string is unknown, so the usual ordered search range is unavailable.

You can build an index without building one that answers your question. That's the failure here.

Imagine three titles: "Camera battery", "Travel camera kit", and "Thermal camera mount". A B-tree places them according to their full starting strings, not near one another because they contain camera. A search operator may need to inspect many candidates or scan broadly. The remedy is not just choosing a more powerful index. First decide what constitutes a term.

An ordinary B-tree orders complete values, while a text index maps each analyzed token to a postings list of matching document identifiers.
An ordinary B-tree orders complete values, while a text index maps each analyzed token to a postings list of matching document identifiers.
Think first

A marketplace offers exact SKU lookup, English descriptions, Hindi product names, and infix matches for part numbers. Design field mappings, analyzers, indexes, routing and search behavior. Explain what you would keep inside PostgreSQL and what would live in a search service.

Take a few minutes to form an approach, then compare it with the worked explanation.

Reveal the worked explanation

Turn documents around

A full-text engine analyzes a document into terms, then builds an inverted index. Instead of storing just document → words, it stores term → documents. For the three titles, the postings for camera contain all three document IDs. Postings may also carry term frequency and positions, allowing ranked and phrase queries. Compression can make sorted postings economical, although the term dictionary, postings and auxiliary metadata still cost storage.

The first query plan now looks different. Analyze the input in a way compatible with the indexed field, find the term dictionary entry, visit its postings, apply filters, rank candidates, and retrieve the winning documents. A two-term query can intersect or combine postings before fetching all document bodies. That's the actual reason an inverted index helps. It avoids repeatedly reading the full text of unrelated documents for common query shapes.

But analysis changes semantics. A tokenizer might split punctuation. Lowercasing may normalize Camera and camera. Stemming might make running and run related, while a language-specific analyzer might behave differently. None of that guarantees literal substring matching. A user who types mera expecting to match camera is asking for infix matching, not ordinary word search. N-grams or a trigram index can support that, at meaningful index-size and false-candidate cost. PostgreSQL's pg_trgm is one practical alternative when the use case is substring matching inside a relational database, not a full search product.

Make the product requirements explicit

Suppose users want "red waterproof camera bag" and should see products with those concepts even if the title order differs. A text analyzer and relevance ranking make sense. Exact SKU matching should usually be a separate boosted or filtered path. Typo tolerance may require fuzzy term expansion, controlled to prevent explosive work on popular prefixes. Phrase search needs positions or another field representation, not just a set of words. And a user searching a restricted catalog must never see unauthorized documents merely because they matched a term.

I would keep the source database authoritative for listing updates and commercial rules. Indexing can happen through a bounded pipeline, with stable document IDs, version information and explicit freshness targets. This does not mean search needs to re-fetch all rows on every request. It means the application has to decide which fields can be served from the derived index and which decisions, such as purchase eligibility or current price, demand authoritative validation.

There is a temptation to call the index "eventually consistent" and move on. That hides a real product decision. A five-second visibility delay for new listings may be acceptable. A five-second delay for removing a prohibited listing may not be. Revoked visibility can need query-time authorization or exclusion even when indexing lags. Later lessons will address index refresh and controlled migrations. Here the essential decision is that the query's semantics determine the index structure.

Show that the index actually helped

My proof would use a representative query set, not one search for camera. Include common terms with enormous postings, rare terms, phrases, SKU lookups, prefix input, misspellings, and unauthorized candidates. Measure candidate documents examined, dictionary lookups, postings work, fetch cost, p50/p99, memory, and indexing throughput. Run the same queries on warm and cold caches. Account for the cost of indexing new and updated documents too.

With 80 million listings, an inverted index does not magically make the most common term selective. If sale appears in 60 million documents, a naive full postings traversal is still expensive. The engine needs conjunction ordering, top-K retrieval, filters, and sometimes precomputed features. A ranking query can be fast without materializing every matching document because it only needs a small set of competitive candidates.

The interview distinction I want to hear is not "use Elasticsearch". It is what access pattern became expensive, which data structure changes that cost, and which semantics the new structure still cannot promise. If you can make those three statements precisely, choosing PostgreSQL full-text search, trigram indexing, Lucene, or a managed service becomes a reasoned design decision rather than a brand preference.

Go deeper

PostgreSQL supports full-text search with tsvector and tsquery and can index expressions with GIN. pg_trgm indexes can help similarity and substring searches, depending on operators and query shape. Lucene builds per-segment term dictionaries and postings and may include positions and offsets based on field configuration. Analyzer changes often require reindexing because the stored tokens differ. Prefix and leading-wildcard expansion can both be expensive, so treat syntax, analysis and query budgets as independent decisions.

Check your reasoning

  • Distinguish left-anchored prefix and leading-wildcard query costs.
  • Explain term-to-document postings, token normalization and candidate retrieval.
  • Differentiate whole tokens from arbitrary infix substring matches.
  • Choose GIN full text, pg_trgm, or external search for specific requirements.
  • Preserve authoritative rules, visibility and query tests.

Common mistake: Any inverted index automatically supports matching arbitrary substrings.

A search box must support both whole-word queries and arbitrary infix part-number matches. Which indexing approach fits?

Read the answer explanation

Choose full-text postings for words and n-grams or trigrams for arbitrary substrings — Word postings retrieve documents containing analyzed terms. Arbitrary substrings require a different tokenization and index contract.

Apply it elsewhere

An internal source-code search product must find identifier fragments, quoted phrases and exact symbol names across 200 million code lines. Choose which queries need positional postings, prefix structures or n-grams, then describe how you avoid exposing private repositories.

Compare your approach

Separate prefix from leading-wildcard access, illustrate an inverted postings lookup, distinguish token search from arbitrary substrings, preserve source authority and authorization, and test representative high-frequency terms rather than one favorable query.

One more constraint

Does adding an inverted index for whole-word search guarantee that typing `mera` finds documents containing `camera`?

Quick revision

A B-tree orders complete values, so a leading wildcard generally cannot use an ordinary left-anchored range lookup. An inverted index flips the mapping to term-to-document postings and supports fast candidate retrieval, filters and text ranking. It does not automatically provide arbitrary substring matching, which may require n-grams or a trigram strategy. Start with query semantics, choose analyzers and field types deliberately, then measure high-frequency terms, updates, authorization and freshness before selecting the system.

References