How Do You Design a Full-Text Search System?
Learn how full-text search systems use inverted indexes, tokenization, and BM25 ranking to search millions of documents fast.
Expected Interview Answer
A full-text search system is built around an inverted index — a mapping from each normalized term to the list of documents (and positions) containing it — populated by an ingestion pipeline that tokenizes, lowercases, removes stop words and stems or lemmatizes text, and queried by intersecting posting lists and ranking matches with a relevance function like TF-IDF or BM25, all scaled by sharding the index across nodes and replicating for availability.
Documents are first run through an analysis pipeline: tokenization splits text into terms, normalization lowercases and strips punctuation, stop-word removal drops common low-signal words like “the”, and stemming/lemmatization reduces words to a root form so “running” and “run” match the same query. Each resulting term is written into an inverted index as a posting list of document IDs (often with term positions and frequencies for phrase queries and relevance scoring). A query is analyzed the same way, then its terms’ posting lists are intersected or unioned, and matching documents are ranked using a relevance function — TF-IDF weights terms by how rare they are across the corpus, while BM25 additionally accounts for document length and term saturation for better ranking. At scale, the index is sharded by document ID or term across nodes, queries fan out to all shards and merge/re-rank results, and each shard is replicated for availability and read throughput; systems like Elasticsearch and Apache Solr (both built on Lucene) implement exactly this architecture, adding near-real-time indexing, faceting, and typo-tolerant fuzzy matching on top.
- Inverted indexes turn “find documents containing this word” into a fast posting-list lookup instead of scanning every document
- Relevance ranking (TF-IDF/BM25) surfaces the most useful matches first, not just any match
- Sharding and replication let full-text search scale horizontally across a document corpus
- The analysis pipeline (stemming, stop words) makes search resilient to word variation and phrasing
AI Mentor Explanation
Full-text search is like a cricket almanac’s back-of-book index that lists, for every player’s name, the exact pages where they are mentioned, instead of forcing a reader to flip through every page looking for the name. Building that index means scanning every page (tokenizing), normalizing name spellings (stemming), and skipping common filler words. When someone searches "Kohli," the index instantly returns the relevant pages (posting list), and pages mentioning Kohli many times in a shorter chapter get ranked higher, mirroring how relevance scoring favors dense, focused mentions. That page-lookup-instead-of-page-flipping approach is exactly what an inverted index gives full-text search.
Step-by-Step Explanation
Step 1
Analyze documents at ingest
Tokenize, normalize, remove stop words, and stem/lemmatize the text of each document.
Step 2
Build the inverted index
Write each term into a posting list of document IDs (with positions/frequencies) it appears in.
Step 3
Analyze and execute the query
Analyze the query the same way, then intersect/union the relevant terms’ posting lists to find candidate documents.
Step 4
Rank and shard for scale
Score candidates with TF-IDF/BM25, and shard/replicate the index across nodes with fan-out queries and result merging.
What Interviewer Expects
- Describes the inverted index and posting lists as the core data structure
- Explains the analysis pipeline: tokenization, normalization, stop words, stemming
- Names a relevance ranking function like TF-IDF or BM25 and what it accounts for
- Discusses sharding/replication and real systems: Elasticsearch, Solr, Lucene
Common Mistakes
- Proposing a LIKE %term% scan over a relational table as “full-text search”
- Forgetting the analysis pipeline (stemming/stop words), causing exact-match-only search
- Not mentioning relevance ranking, treating all matches as equally good
- Ignoring how the index is sharded and queries fan out and merge at scale
Best Answer (HR Friendly)
“A full-text search system works by building an index that maps every word to the documents it appears in, similar to the index at the back of a book, so a search does not need to scan every document. It also processes text to handle variations like plurals and skips common filler words, then ranks results so the most relevant matches show up first, and at large scale that index is split across many machines to keep search fast.”
Code Example
import re
import math
from collections import defaultdict
STOP_WORDS = {"the", "a", "an", "and", "is", "in", "of", "to"}
def tokenize(text):
words = re.findall(r"[a-z0-9]+", text.lower())
return [w for w in words if w not in STOP_WORDS]
class InvertedIndex:
def __init__(self):
self.postings = defaultdict(dict) # term -> {doc_id: term_freq}
self.doc_lengths = {}
self.total_docs = 0
def add_document(self, doc_id, text):
terms = tokenize(text)
self.doc_lengths[doc_id] = len(terms)
self.total_docs += 1
for term in terms:
self.postings[term][doc_id] = self.postings[term].get(doc_id, 0) + 1
def search(self, query, k1=1.5, b=0.75):
query_terms = tokenize(query)
avg_len = sum(self.doc_lengths.values()) / max(1, len(self.doc_lengths))
scores = defaultdict(float)
for term in query_terms:
posting = self.postings.get(term, {})
if not posting:
continue
idf = math.log(1 + (self.total_docs - len(posting) + 0.5) / (len(posting) + 0.5))
for doc_id, freq in posting.items():
doc_len = self.doc_lengths[doc_id]
norm = 1 - b + b * (doc_len / avg_len)
scores[doc_id] += idf * (freq * (k1 + 1)) / (freq + k1 * norm)
return sorted(scores.items(), key=lambda x: x[1], reverse=True)Follow-up Questions
- How does BM25 improve on plain TF-IDF, particularly around document length and term saturation?
- How would you support phrase queries like “exact phrase” using an inverted index?
- How does a fuzzy/typo-tolerant search feature work on top of an inverted index?
- How do Elasticsearch and Solr shard and merge search results across a cluster?
MCQ Practice
1. What is the core data structure behind full-text search engines?
Full-text search relies on an inverted index: for each term, a posting list of the documents that contain it, enabling fast term-based lookup.
2. What does stemming/lemmatization accomplish in the search analysis pipeline?
Stemming/lemmatization normalizes word forms so morphological variants of a term still match the same search query.
3. What does BM25 additionally account for compared to plain TF-IDF?
BM25 extends TF-IDF by normalizing for document length and dampening the effect of very high term frequency, improving ranking quality.
Flash Cards
What is an inverted index? — A mapping from each term to the list of documents (posting list) that contain it.
What does the analysis pipeline do? — Tokenizes, normalizes, removes stop words, and stems/lemmatizes text before indexing or querying.
TF-IDF vs BM25? — BM25 improves on TF-IDF by normalizing for document length and saturating term frequency contribution.
Name two real full-text search systems. — Elasticsearch and Apache Solr (both built on Apache Lucene).