Engineering Atlasby Abhishek Goyal
System design / Search & storage

Types of Search in System Design: Autocomplete, Fuzzy, Phrase, Geo, Faceted, Vector and Hybrid

The seven kinds of search behind one search box, for system design interviews: autocomplete with edge n-grams and FSTs, fuzzy search with Levenshtein automata, phrase search with positions, geo search with cells and BKD trees, faceted search and why counts are approximate across shards, vector search with HNSW, and hybrid search merged with Reciprocal Rank Fusion.

By Abhishek Goyal Read time ~16 min read Level Beginner → Senior Stack Elasticsearch, Lucene, Redis, PostgreSQL, pgvector, H3 Members
On this page
  1. One search box, seven questions
  2. Autocomplete (search-as-you-type)
  3. Fuzzy search (typo tolerance)
  4. Phrase search
  5. Geo search ("near me")
  6. Faceted search (filters with counts)
  7. Vector search ("more like this")
  8. Hybrid search (text and vectors, merged with RRF)
  9. How to say it in the interview

"Restaurants near me", "shoes under 2,000" and "photos like this one" all arrive through the same search box, so they feel like one feature. They aren't. They're three different kinds of search, backed by three different indexes, and a good design names the kinds it needs before it picks any technology.

Where this fits: Part of the Search & storage series. On the journey of a query, the request "hits the index". This blog shows that "the index" is really several indexes, one per kind of question.

Before you start: How search engines work (inverted index, analyzers, BM25) is required. Storage data structures explains the FST, geo cells and HNSW from the inside; here we only use them.

After reading this you will be able to

  • Split one search box into the seven kinds of question it might serve.
  • Pick between edge n-grams, search_as_you_type and a completion suggester for autocomplete.
  • Explain how typo tolerance and phrase search reuse the inverted index.
  • Explain why geo and vector search need their own indexes, and why facet counts drift across shards.
  • Merge text and vector results with Reciprocal Rank Fusion, and work out a score by hand.

For each type: what the user sees, how the index does it, what it costs, when to use it. Vendor comparisons wait for Choosing a search engine.

01One search box, seven questions

Picture a librarian at the front desk. Over one morning, people ask:

  • "Books starting with Har..." That's autocomplete.
  • "I think it's spelled Hary Poter." That's fuzzy search: matching despite typos.
  • "The exact line to be or not to be." That's phrase search: words in that order.
  • "Libraries within 2 km." That's geo search.
  • "Only paperbacks under 500 rupees, and how many?" That's faceted search: filters with counts.
  • "Something like this book." That's vector search: matching by meaning, not words.
  • "Both of those, mixed fairly." That's hybrid search.

One idea organises the whole blog: every type is either a smarter walk over the term dictionary, extra data in the postings, or a separate index next to the inverted one. The map shows which is which.

Fig. 1

Seven kinds of search and the index each one uses

Seven kinds of search and the index each one usesOn the left, a group of four types that reuse the inverted index: autocomplete by a prefix walk, fuzzy by an automaton walk, phrase by checking positions, and faceted by filters plus aggregations. In the middle, the inverted index. On the right, a group of two types that need their own index: geo with cells or a BKD tree, and vector with an HNSW graph. At the bottom, hybrid search merges text and vector results with RRF.Reuse the inverted indexNeed their own indexAutocompleteprefix walkFuzzyautomaton walkPhrasepositions in postingsFacetedfilters + aggregationsInverted indexterm -> docsGeocells (geohash, H3)or a BKD treeVectorHNSW graphover embeddingsHybridmerge text + vector with RRF
Four types reuse the inverted index; geo and vector need their own. Hybrid sits on top and merges results from both sides.

Seen this before?

The centre of that map is the inverted index (term → sorted list of documents) from How search engines work. The left side of the map is new ways to walk it.

02Autocomplete (search-as-you-type)

The user types "qui" and sees "quick start guide" before they finish. The catch: you run a query on every keystroke, so each must be cheap. Three ways:

1. Edge n-grams. An edge n-gram is a slice of a word anchored at its start. At index time, the edge n-gram tokenizer turns "Quick" into Qu, Qui, Quic, Quick, and indexes every slice. Now "qui" is an ordinary term lookup. The cost is a bigger index.

2. search_as_you_type. Easy mode: the search-as-you-type field type creates the prefix and shingle subfields for you (a shingle is a run of neighbouring words, like "quick start").

3. The completion suggester. A separate structure built purely for speed. The suggester docs say it is fast to query but "costly to build and are stored in-memory". It jumps to known entries and does no spell correction. Under the hood it's FST-shaped (a finite state transducer, which shares prefixes so a huge sorted list fits in little memory); McCandless's post on FSTs in Lucene shows why prefix lookups on one are fast.

Pitfall

Many candidates apply the edge n-gram analyzer at query time too. Then "qui" becomes q, qu, qui, and q matches almost everything. Use edge n-grams at index time only, and search with the raw typed terms.

Autocomplete
SeesSuggestions after 2 or 3 keystrokes
IndexEdge n-grams in the inverted index, or an in-memory FST (suggester)
CostIndex size (n-grams), or memory and rebuild time (suggester)
Use whenN-grams for a flexible search box; the suggester for "jump to this entity" lists

Seen this before?

The FST appears in Storage data structures, with Andrew Gallant's example of 1.6 billion URLs (134 GB of them) packed into one.

03Fuzzy search (typo tolerance)

The user types "elastcsearch" and still finds "elasticsearch". First, measure how wrong a word is.

Edit distance Definition

The number of single-character changes that turn one word into another. Elasticsearch's fuzzy query counts four kinds: change, remove, insert, or swap two neighbours. "elastcsearch" is one insert away from "elasticsearch".

The naive approach compares the query with every term in the dictionary: millions of comparisons per keystroke. Lucene instead builds a Levenshtein automaton, a small state machine that accepts only words within N edits of the query, and walks it together with the sorted dictionary, skipping whole ranges that can't match. McCandless tells the story in Lucene's FuzzyQuery is 100 times faster in 4.0: 100 times faster, from changing how the dictionary is walked.

How many edits? Per the common options docs, the default fuzziness: AUTO (AUTO:3,6) means terms of 0 to 2 characters must match exactly, 3 to 5 allow 1 edit, and longer terms allow 2. One edit on "cat" already gives "bat" and "car". Two knobs cap the cost: prefix_length (the first characters must match exactly, which shrinks the walk) and max_expansions (how many matching terms the query may expand into).

Fuzzy
SeesResults despite one or two typos
IndexThe normal inverted index, walked with a Levenshtein automaton
CostEach query expands into many terms
Use whenHuman-typed names, products, places. Never IDs or SKUs, where a near miss is a wrong answer

04Phrase search

The user types "new york" in quotes and wants "New York pizza", not "new shoes shipped from York". Both documents contain both words, so a plain inverted index can't tell them apart. It needs positions.

The tokenizer already numbers each word as it splits text, so the index can store where each term appears. The Stanford IR book's chapter on positional indexes writes a posting as docID: <pos1, pos2, ...>. A phrase match is two checks: both terms are in the document (the usual AND), and "york" sits at the position of "new" plus 1. Here's the check on one document.

Fig. 2

Phrase search is an AND plus a position check

Phrase search is an AND plus a position checkThe posting for the term new says document 7 at positions 3 and 18. The posting for york says document 7 at positions 4 and 30. Both terms are in document 7. Position 3 plus 1 equals 4, where york appears, so the phrase new york matches. Position 18 plus 1 equals 19, where there is no york, so that occurrence does not count.newD7: positions [3, 18]yorkD7: positions [4, 30]Both in D7?the usual AND13 + 1 = 4york is there: match218 + 1 = 19no york: skipSlop = how many position moves are allowed (default 0)
Phrase search is an AND plus a position check. "new" at 3 and "york" at 4 is a match; "new" at 18 has no "york" at 19.

Slop loosens the rule: how many position moves are allowed. In the match phrase query, slop defaults to 0, and swapped terms ("york new") need a slop of 2.

Positions make the index bigger and phrase queries read more data. A useful trick: use the phrase as a ranking boost rather than a hard filter, so users who forget the quotes still get the exact match first.

Phrase
SeesExact multi-word matches
IndexPositions stored inside each posting
CostA larger index; more data read per query
Use whenQuoted queries, names, and as a boost for multi-word queries

Seen this before?

Positions come from the analysis pipeline in How search engines work.

That's the text family, all on the index you already have. The next four types need more.

Members-only article

Keep reading with the Article Pass

You've read the free part. The other 5 sections of this guide, with every diagram and worked example, are for members. One Article Pass unlocks every members-only article on Engineering Atlas: the ones live today and every one I publish while your pass is active.

  • Geo search ("near me")
  • Faceted search (filters with counts)
  • Vector search ("more like this")
  • Hybrid search (text and vectors, merged with RRF)
  • How to say it in the interview
Become a member Sign in

From ₹49 · one-time payment, no auto-renewal · separate from course passes

Interview practice

Used in these design problems

Keep learning