Types of search

“Search” names several different problems. A lookup fetches a record by a key you already know, a filter returns every record that passes exact tests, and search ranks documents by how well they fit a vague, possibly misspelt request. Each needs different machinery, and a real search box blends several kinds at once.

This is part 1 of the eight-part search engines series: a map of the territory before part 2 builds the data structures. For a one-page tour of the pipeline, read How search engines work.

Picture it first: three errands in a market

You walk into a huge old market with three errands.

First, shop 214, where a tailor holds your order. A board at the gate lists every shop by number. There is exactly one right answer, or none.

Second, every shop in Lane 3 that sells silver and stays open after 9 pm. You walk the lane with a checklist. Each shop passes or fails, and all that pass are equally good answers.

Third, “a nice red cotton kurta, not too costly”. You ask an old shopkeeper. He understands “kurtha”, guesses that maroon might do, and names his three best bets first. Nobody can prove his list is correct; it can only be better or worse.

Map it back. The board is a primary-key index. The checklist is a filter, a SQL WHERE clause. The shopkeeper’s memory of which shop sells what is an inverted index (word → shops), and his judgement about whom to name first is a ranking function. Checking every shop in every lane for the word “kurta” is a full table scan: fine for a village haat, hopeless for 50 million stalls.

Lookup, filter or search?

Every search design starts by asking which of three things the user is doing. The difference is the shape of the answer.

Lookup. The user knows an exact key: an order ID, a product ID. The database follows one path through a B-tree (or one hash bucket) and returns zero or one row. With a few hundred keys per page, a B-tree over Bazaar’s 50 million products is about four levels deep (300³ = 27 million is too few, 300⁴ = 8.1 billion is plenty): four page reads, mostly from memory.

Filter. The user knows exact attributes: brand, size, price at most ₹500. The answer is a set whose members all pass every test, which the IR textbook by Manning, Raghavan and Schütze calls the Boolean retrieval model. Order appears only if you add ORDER BY.

Search. The user describes a need in loose words. The same book separates the information need (what the person cares about) from the query (the few words they typed). Because the query describes the need imperfectly, the system has two jobs: matching picks candidates and ranking orders them. Correctness is graded: one result list is better than another, but none is simply right.

A quick test: if a unit test can check the answer, it is a lookup or a filter; if sensible engineers could argue about the order, it is search. Bazaar’s search page is a ranked search wrapped in filters, while order history is just a filter that a plain database index serves well.

Why LIKE does not scale

The first thing many teams try is a pattern match:

SELECT id, title FROM products WHERE title ILIKE '%kurta%';

It works on day one with 5,000 products. At 50 million it fails three ways, and the PostgreSQL documentation names them itself: pattern operators have no linguistic support, no ranking and no index support, so they “must process all documents for every search”.

It scans everything. A B-tree can serve LIKE 'kurta%', because a prefix is a contiguous range of sorted keys, but only when the pattern is anchored to the start. A leading % discards the sort order, so every row is read. At about 1 KB per row, 50 million rows is 50 GB per query: about 50 seconds at 1 GB/s, and 5 TB/s of scanning for 100 queries per second. GitHub did this napkin maths for code in 2023: grepping 115 TB would occupy 2,048 cores for 96 seconds per query, about 0.01 queries per second.

It ranks nothing. If 200,000 products contain “kurta”, they arrive in scan order; the one the shopper wants may be row 140,000.

It knows no language and forgives nothing. %kurtis% misses every “kurti”, and %kurta% finds neither कुर्ता nor the typo “kurtha”. It also matches too much: %red% hits “embroidered” and “Fred Perry”.

The fix is to look words up instead of scanning for them. An inverted index maps each term to its postings list, the sorted IDs of the documents containing it. If 200,000 products contain “kurta”, their IDs are on average 50 million ÷ 200,000 = 250 apart, so each gap fits in a byte; with a term frequency, call it 2 bytes per posting, or about 400 KB in all. That is 125,000 times less data than the scan, and the work grows with the matches, not the catalogue. Part 2 builds this structure step by step.

PostgreSQL’s own full-text search may be all you need at first. It normalises text into lexemes (a tsvector), stores them in a GIN index, which is an inverted index, and ranks with ts_rank:

-- Once: a normalised, indexed copy of the searchable text
ALTER TABLE products ADD COLUMN search_vec tsvector
  GENERATED ALWAYS AS (to_tsvector('english',
    coalesce(title, '') || ' ' || coalesce(description, ''))) STORED;
CREATE INDEX products_search_idx ON products USING GIN (search_vec);

-- Per query: stemmed matching through the index, best first
SELECT id, title, ts_rank(search_vec, q) AS score
FROM products, websearch_to_tsquery('english', 'red cotton kurta') AS q
WHERE search_vec @@ q
ORDER BY score DESC
LIMIT 20;

The pg_trgm extension adds trigram indexes that make even LIKE '%kurta%' index-assisted, plus similarity matching for typos. When these stop being enough is the subject of part 4.

The kinds of search

A search box is a front door to several kinds of search. Here are the nine you will meet, each with what it costs. A real product runs several of them for one request.

Full-text (lexical) search

The workhorse. At index time an analyser splits text into tokens and normalises them: lowercase, strip punctuation, perhaps drop stop words, and stem so that “kurtas” and “kurta” become one term. The same analyser runs on the query, so both sides share a vocabulary. The engine looks up each query term, intersects or unions the postings lists (“all words” or “any word”) and scores the candidates. red cotton kurta matches “Kurtas in Red Cotton, Pack of 2” though the query string appears nowhere in it.

You gain speed, explainability and precise control over vocabulary. You pay with vocabulary mismatch: “tunic” will not find products listed only as “kurti” unless someone maintains synonyms. Analysers are also per language: Devanagari Hindi, Hindi typed in Latin script (“Hinglish”, as in paneer masala) and English each need their own.

Phrase and proximity search

Sometimes word order matters: “slim fit” should not match “slim” in a brand name plus “regular fit” in the description. A phrase query requires adjacent words in order; a proximity query allows a small gap (Lucene calls it slop). PostgreSQL’s fatal <-> error matches “fatal error” but not “error is not fatal”.

The postings must now store each word’s positions, which makes the index larger and phrase queries slower than term queries, since positions are compared for every candidate. Proximity also works as a ranking signal: documents where the query words sit close together usually deserve a higher score.

Prefix search and typeahead

Typeahead completes as the user types: kur → “kurta”, “kurti”, “kurta pyjama set”. Every keystroke is a query, and Jakob Nielsen’s long-standing rule of thumb is that 0.1 second is about the limit for a response to feel instantaneous, network included.

Prefixes are cheap on anything sorted, because all terms starting with kur sit together: a B-tree range, a trie, or a finite-state transducer (FST). Elasticsearch’s completion suggester uses structures “optimized for speed” but “costly to build and are stored in-memory”. The alternative is edge n-grams: index “k”, “ku”, “kur”, “kurt”, “kurta” at write time so a prefix becomes an ordinary term lookup.

You gain instant answers. You pay in memory and rebuild cost, and you rank suggestions by popularity rather than text relevance. The full design is Design typeahead.

Fuzzy, typo-tolerant search

Shoppers type “kurtha”, “panir” and “chapal”. Fuzzy matching accepts terms within a small edit distance. Elasticsearch’s fuzzy query counts single-character substitutions, insertions, deletions and adjacent transpositions, and AUTO scales tolerance with length: up to 2 characters must match exactly, 3–5 allow one edit, longer terms two. “kurtha” (six letters) is one deletion from “kurta”, so it matches. “panir” (five letters) gets one edit, but “paneer” is two away, so transliteration needs its own step.

The engine expands the misspelt term into real dictionary terms within that distance, then looks each one up. Elasticsearch caps the expansion with max_expansions (default 50) and warns that high values are slow, especially with prefix_length 0. Alternatively, pg_trgm treats strings sharing enough three-character groups (default threshold 0.3) as similar, which also powers “did you mean?”.

You gain forgiveness and pay with precision: one edit turns “red” into “bed” and “rod”. Defences: fix the first one or two characters, try exact matching first, and show “Showing results for kurta”.

Substring and n-gram search

Logs and code ignore word boundaries: people paste ullPointerExcep or user_id=48213. Code search, GitHub’s engineers note, also needs searchable punctuation, no stemming, no dropped stop words, and regexes.

The tool is an n-gram index: index every run of n characters, so with trigrams “limits” becomes lim, imi, mit, its. A substring query is split into trigrams, their postings are intersected, and each candidate is checked against the real pattern, because sharing the trigrams does not prove the substring is there (the IR book’s k-gram example: red* also returns “retired”). PostgreSQL’s pg_trgm GIN and GiST indexes serve LIKE '%foo%bar' and regexes this way. Elasticsearch’s wildcard field does the same for log lines: n-grams as a rough filter, then a check of the stored value.

You gain grep-like power at index speed. You pay with a larger index (every position emits a gram), a verification step, and bad worst cases: a pattern with no extractable trigram degenerates to a full index scan.

Structured and faceted search

Filters restrict results on exact, typed fields: size = M, price ≤ 500, in_stock = true. They do not affect the score, so engines cache them as bitsets. Facets are the counts beside each value, “M (1,204)”, “L (987)”, so shoppers see what is left before they click. Counting needs a column-oriented copy of each field (Lucene’s doc values) so the engine reads sizes without loading documents:

{
  "query": {
    "bool": {
      "must":   [{ "match": { "title": "cotton kurta" } }],
      "filter": [{ "range": { "price": { "lte": 500 } } }]
    }
  },
  "aggs": {
    "sizes":  { "terms": { "field": "size" } },
    "brands": { "terms": { "field": "brand" } }
  },
  "post_filter": { "term": { "size": "M" } }
}

The filter applies to hits and counts alike. The post_filter applies only to hits, after the counts are computed, so after the shopper picks size M the size facet still shows S, L and XL. You gain fast narrowing and fewer dead ends. You pay for counting, which grows with the number of matches and with distinct values per field; counts merged across shards can be approximate, as part 5 explains.

Geo and proximity search

Location is a filter (“delivers to 560034”), a ranking signal (closer first), or both. Engines offer distance, bounding-box, polygon and grid-cell geo queries. Underneath, points sit in a multi-dimensional tree such as a BKD tree (which Elasticsearch also uses by default for numeric ranges) or in grid cells such as geohash, S2 or H3, so “near me” becomes “in one of these cells”.

A Swiggy-style restaurant search filters to restaurants that deliver to you, then lets distance and delivery time pull nearer ones up. You pay when points move: riders reporting positions every few seconds would churn an on-disk index, so moving objects usually live in an in-memory geo store. See Geospatial indexes and Proximity search.

Semantic (vector) search

Lexical search matches words; semantic search matches meaning. An embedding model turns each product (text, even the photo) into a vector of hundreds or thousands of numbers, so that similar meanings land close together. The same model embeds the query, and the engine returns the k nearest vectors. “Something light to wear to office in May” then finds linen and cotton kurtas that share none of those words.

Per the Elasticsearch kNN docs, query and document vectors must come from the same model, and exact nearest-neighbour search “does not scale well for large datasets”, so production systems use approximate indexes such as HNSW that trade a little recall for a lot of speed.

You gain recall on paraphrases, other languages and images. You pay with weak handling of exact tokens (model numbers, sizes, “not leather”), hard-to-explain rankings, embedding compute and memory, and re-embedding everything when the model changes. See Embeddings and semantic search and Vector databases.

Hybrid search

Lexical and semantic search fail in opposite ways: one misses paraphrases, the other fumbles exact tokens. Hybrid search runs both and merges the lists. Their scores are not comparable (BM25 is an unbounded sum; cosine similarity lies between −1 and 1), so the robust fix is to fuse ranks. Reciprocal rank fusion (RRF), from Cormack, Clarke and Büttcher (2009), gives each document 1 / (k + rank) from every list it appears in and sums them. The paper found k = 60 near-optimal, and 60 is the default rank_constant of Elasticsearch’s RRF retriever.

You gain the strengths of both without tuning weights between incomparable scores. You pay for two retrievals per query (the slower one sets latency), two indexes to keep in sync, and a window size: each list contributes only its top N, so a product ranked 200th by both never gets a chance.

Search by domain

The same techniques appear everywhere in different proportions, because corpus size, freshness and the meaning of “relevant” change by domain.

Two consequences. Freshness costs money: an index is a copy that catches up with its source, and Elasticsearch makes new writes searchable through a refresh that defaults to one second. And relevance is domain-specific: links and authority for the web (How Google Search works), sales and stock for products, time for logs, permissions first for enterprise search (Design RAG search over company documents). Search case studies dissects real systems.

Query intent: why people search

Even inside one domain, people search for different reasons. In 2002 Andrei Broder, drawing on work done at AltaVista, argued that “information need” was too narrow a model for the web and proposed three intents in A taxonomy of web search:

• Navigational: reach a site the user already has in mind (“fabindia”, “bazaar returns”). One right answer; success means position 1.
• Informational: learn something (“how to wash a silk saree”). Several answers can be good, and a help article may beat any product.
• Transactional: do something, such as buy or download (“red cotton kurta size M under 500”). Success is a purchase, so stock, price and delivery matter as much as text.

In a 2001 pop-up survey of AltaVista users, 24.5% of searches were navigational. In 400 hand-inspected log queries, about 20% were navigational, 48% informational and 30% transactional, figures Broder himself called “very soft”. Treat them as one web engine’s snapshot; a shopping app is mostly transactional.

Intent decides the path: a navigational brand query can open the brand store, an informational one should also search help articles, and a transactional one needs filters and stock checks. Part 7 places intent classification in the query path.

Relevance basics

Matching versus ranking

Every engine does two jobs. Matching picks the candidate set; ranking orders it. Keep them apart when debugging: if the right kurta is missing altogether, an analyser, synonym or filter is wrong (matching); if it is result 87, scoring is wrong (ranking).

Precision and recall

The IR book defines precision as the fraction of retrieved documents that are relevant, and recall as the fraction of relevant documents that are retrieved. Accuracy is useless, because normally over 99.9% of documents are irrelevant to a query, so returning nothing would score almost perfectly. F1, 2PR / (P + R), is a harmonic mean that stays close to the weaker number.

Behind the lower chart: the strict setting returns 200 products, 180 relevant (P 90%, R 180 ÷ 400 = 45%); the loose one returns 900, 380 relevant (P ≈ 42%, R 95%).

Which measure matters depends on the user. The IR book contrasts web searchers, who want a first page of relevant results and ignore the rest, with paralegals and analysts, who wade through noise to find everything. A Bazaar shopper sees 20 results, so precision in the top 20 is what they feel, yet a zero-result page is a recall failure that costs a sale. In log search during an incident, recall is everything. The levers pull in opposite directions:

Ranked lists add precision at k, MRR and NDCG, which weigh the top positions more; part 7 uses them.

TF-IDF and BM25 in a nutshell

How does an engine decide which matching kurta wins? Term frequency (TF): a product mentioning “chikankari” five times is probably more about it than one mentioning it once. Inverse document frequency (IDF): rare terms tell you more than common ones; on Bazaar “kurta” is in 200,000 products and “chikankari” in a few thousand, so a “chikankari” match counts for more.

BM25 refines TF-IDF twice. Term frequency saturates: the tenth “kurta” in a stuffed title adds almost nothing. And scores are normalised by length: a match in a six-word title beats one buried in a 600-word description. BM25 is Elasticsearch’s default similarity, with k1 = 1.2 for saturation and b = 0.75 for length. Product search then layers popularity, stock and delivery speed on top. The formula and a worked example are in part 2; tuning is in part 5.

Choosing the machinery

The whole map in one table: each kind of search, an example, the structure behind it (built in part 2), typical engines (compared in part 4) and a rough latency budget.

Going deeper: traps that bite in production

Zero results are a recall bug the user can see. On a shopping app an empty page is a lost sale. Build a fallback ladder (all words, then most words, then fuzzy, then semantic) and say what you relaxed. Log zero-result queries: they are your best source of synonyms (“tunic” → “kurti”) and transliterations (“panir” → “paneer”).

Fuzzy and semantic matching can be too generous. Fuzzy turns “red” into “bed”; an embedding puts “iPhone 15 case” right next to “iPhone 16 case”, the wrong product for that shopper. Keep model numbers, sizes and SKUs on an exact or lexical path and let fusion decide the order.

One query can be expensive for everyone. Leading wildcards, regexes and wide fuzzy expansions walk large parts of the term dictionary. Elasticsearch lists fuzzy, regexp, prefix and wildcard among its expensive queries, which operators can block with search.allow_expensive_queries. Never expose raw wildcard syntax, and enforce a minimum pattern length.

Cheat sheet

How to say it in the interview

“I’d split the problem first. Lookups such as order history are exact and stay on the database’s B-tree indexes. Product search is ranked retrieval and needs an inverted index; LIKE '%kurta%' would scan about 50 GB per query and rank nothing. Here I’d combine BM25 full-text matching, fuzzy matching for typos, filters and facet counts for size, price and brand, a geo filter for serviceability, and a separate prefix index for typeahead, plus vector retrieval fused by RRF for vague queries. Shoppers see about 20 results, so I’d optimise precision at the top and treat the zero-result rate as my recall alarm.”

Why not just use LIKE? A leading wildcard defeats the B-tree, so every query scans the table. Results are unranked, word variants, other scripts and typos are missed, and “red” matches inside “embroidered”. PostgreSQL full-text search and pg_trgm fix much of this without a new system.

When is PostgreSQL full-text search enough? Start there when the corpus fits on one primary and you need stemming, ranking and filters: a tsvector with a GIN index, pg_trgm for typos, and search stays transactionally consistent with the data. Move to a dedicated engine fed by CDC for heavy relevance tuning, large facet counts, hybrid retrieval or search traffic that must scale on its own.

Does vector search replace keyword search? No. Vectors find paraphrases but blur exact tokens such as model numbers, sizes and negations, and their rankings are hard to explain. Run both retrievers and fuse the lists, for example with RRF.

How do you handle typos and Hinglish? Length-aware fuzzy matching with the first characters fixed, transliteration so “kurta” and कुर्ता share a term, synonyms mined from zero-result logs, and a “showing results for” banner when you rewrite. Exact first; fuzzy only when results are thin.

How do facet counts stay useful after a click? Compute each facet’s counts before its own selection applies: a post_filter, or one filtered aggregation per facet, so hits narrow while the size facet still shows S, L and XL.

Where to go next

• Next in the series: Search data structures: inverted indexes, tries and more, every structure in the decision table, built step by step.
• How search engines work: the one-page overview.
• Database indexes and Index scan vs full table scan: lookups, filters and why LIKE scans.
• Embeddings and semantic search and Vector databases: the semantic half of hybrid search.
• Design typeahead and Design product search for an online store: this map in an interview.
• Choosing a search engine: PostgreSQL, Elasticsearch, OpenSearch, hosted engines and vector stores, compared.

References and further reading

1. Introduction to Information Retrieval, ch. 1: Boolean retrieval (Manning, Raghavan and Schütze, 2008)nlp.stanford.eduGrepping versus indexing, the Boolean retrieval model, information need versus query, and why NEAR queries and ranking need an index.
2. Introduction to Information Retrieval, ch. 3: k-gram indexes for wildcard queriesnlp.stanford.eduHow k-gram indexes answer wildcard queries, and why candidates need a post-filter (the red* versus retired example).
3. Introduction to Information Retrieval, ch. 8: Evaluation of unranked retrieval setsnlp.stanford.eduDefinitions of precision, recall and the F measure, why accuracy misleads, and which users want which.
4. A taxonomy of web search (Broder, SIGIR Forum, 2002)sigir.orgNavigational, informational and transactional intent, with the AltaVista survey and query-log percentages.
5. PostgreSQL 18 documentation: Full text search, introductionpostgresql.orgWhy LIKE and regex lack linguistics, ranking and index support; tsvector, tsquery and the FOLLOWED BY phrase operator.
6. PostgreSQL 18 documentation: pg_trgmpostgresql.orgTrigram similarity, the 0.3 default threshold, and GIN/GiST indexes that accelerate unanchored LIKE and regular expressions.
7. Elasticsearch documentation: Fuzzy queryelastic.coLevenshtein edits including transpositions, max_expansions (default 50) and the prefix_length warning.
8. Elasticsearch documentation: Filter search results (post filter)elastic.coBoolean filters versus post_filter, and how faceted navigation keeps counts for the options a user has not picked.
9. Elasticsearch documentation: Reciprocal rank fusionelastic.coThe RRF formula, the default rank_constant of 60 and the retriever API for combining lexical and vector results.
10. The technology behind GitHub’s new code search (GitHub blog, 2023)github.blogWhy grep cannot serve code search at scale, n-gram indexes for substrings, and code-specific needs such as no stemming and searchable punctuation.