Full-Text Search and Inverted Indexes
How search finds words fast: an inverted index in Python, AND queries, phrase search, TF-IDF ranking, and SQLite FTS5 answering a rare-word search far faster than LIKE.
An inverted index maps each word to the list of documents, and positions, that contain it, so finding a word is one lookup instead of a scan of every row. Interviewers expect the query mechanics: an AND query intersects the posting lists, phrase search checks adjacent positions, and TF-IDF or BM25 ranks results by relevance.
A normal index maps a row to its words. An inverted index maps each word to the documents that contain it, so a word lookup reads one list instead of scanning every row. In a SQLite test over 50,000 rows, a search for a rare word was tens to hundreds of times faster with FTS5 than with LIKE.
- A LIKE '%term%' query cannot use a B-tree index because the match can start anywhere in the text, so the database scans every row.
- A multi-word AND query on an inverted index intersects the posting lists of each term.
- Phrase search on an inverted index works because positions are stored: the second word must appear at the position right after the first.
- TF-IDF scores a document by term frequency times inverse document frequency, so rare words count more; production engines use the BM25 refinement.
- In a SQLite test over 50,000 rows, an FTS5 MATCH for a rare word was tens to hundreds of times faster than LIKE, and the gap grows with the data.
01Why LIKE does not scale
WHERE body LIKE '%rareterm%' cannot use a B-tree index, because the match can start anywhere in the text. The database reads every row and scans every string. That is fine for a thousand rows and hopeless for millions. It also knows nothing about words, so it matches "cat" inside "concatenate", ignores case and spelling variants only if you add work, and cannot rank results by relevance.
Full-text search flips the structure so the work happens once, when documents are added, rather than at every query.
02The inverted index
import re
from collections import defaultdict
docs = {1: "the quick brown fox jumps over the lazy dog",
2: "a quick brown dog outpaces a quick fox",
3: "the lazy cat sleeps all day",
4: "foxes and dogs are not cats"}
STOP = {'the', 'a', 'and', 'are', 'not', 'all', 'over'}
def tok(t):
return [w for w in re.findall(r'[a-z]+', t.lower()) if w not in STOP]
idx = defaultdict(dict) # word -> {doc: [positions]}
for d, t in docs.items():
for p, w in enumerate(tok(t)):
idx[w].setdefault(d, []).append(p)The process, called analysis, lowercases the text, splits it into tokens and drops very common stop words. The index then holds, for example, quick: {1: [0], 2: [0, 3]}. Building it costs one pass over the documents. After that, finding every document with a word is a dictionary lookup.
03AND queries and phrases
def AND(*ws):
s = None
for w in ws:
ps = set(idx.get(w, {}))
s = ps if s is None else s & ps
return sorted(s)
def phrase(a, b): # b directly after a
return sorted(d for d in set(idx.get(a, {})) & set(idx.get(b, {}))
if any(p + 1 in idx[b][d] for p in idx[a][d]))
print(AND('quick', 'fox'), AND('lazy', 'dog'), AND('quick', 'cat'))
print(phrase('quick', 'brown'), phrase('brown', 'quick'))The first line gives [1, 2] [1] []: documents containing both "quick" and "fox" are 1 and 2, "lazy" and "dog" only 1, and no document has "quick" and "cat". The second gives [1, 2] []: "quick brown" appears in documents 1 and 2, but "brown quick" never does. Phrase search works because the index stores positions. One caveat: because stop words were removed before numbering positions, a phrase can match across a dropped word. Real engines keep original positions to avoid that.
04Ranking with TF-IDF
import math
N = len(docs)
def rank(q):
sc = defaultdict(float)
for w in tok(q):
if w not in idx: continue
idf = math.log(N / len(idx[w])) + 1 # rarer word, higher weight
for d, pos in idx[w].items():
tf = len(pos) / len(tok(docs[d])) # share of this doc's words
sc[d] += tf * idf
return sorted(sc.items(), key=lambda x: -x[1])
print(rank('quick fox')) # doc 2 scores 0.847, doc 1 scores 0.564Both documents contain "quick" and "fox", but document 2 says "quick" twice (both documents are six tokens long after stop-word removal), so it ranks higher. Term frequency rewards repetition, and inverse document frequency (IDF) rewards rare words: a word in every document tells you nothing. Production engines use a refinement called BM25, which adds saturation for repeated terms and length normalisation, but the idea is the same.
05Language problems: stemming and synonyms
Searching the index above for fox returns documents 1 and 2, and foxes returns only document 4. A person would expect all three to match. Stemming reduces words to a root form ("foxes" to "fox", "running" to "run") at both index and query time. Lemmatisation does it with a dictionary. Synonym lists can map "car" and "automobile". Language-specific analysers handle different scripts and rules, and search for languages without spaces, such as Chinese or Japanese, needs special segmentation.
Stemming also causes false matches, so most engines let you tune or disable it.
06The real thing: SQLite FTS5
CREATE VIRTUAL TABLE f USING fts5(body);
SELECT count(*) FROM f WHERE f MATCH 'rareterm';
SELECT highlight(f, 0, '[', ']') FROM f WHERE f MATCH 'needle rareterm';I loaded 50,000 rows of 30 random words each, planted one row containing "rareterm", and searched. LIKE '%rareterm%' scanned the whole plain table (a few milliseconds). The FTS5 MATCH took a few microseconds to well under a millisecond, tens to hundreds of times faster depending on the machine, and the gap widens as the table grows because LIKE grows linearly with the data while an index lookup barely moves. The highlight function marks matched terms in the result, which is useful for search result snippets.
PostgreSQL has tsvector columns with GIN indexes, and MySQL has FULLTEXT indexes. When you need typo tolerance, faceting and relevance tuning at scale, dedicated engines such as Elasticsearch, OpenSearch or Lucene are built on the same inverted-index core.
07Costs and limits
An inverted index takes extra storage, often a fraction of the size of the text itself. Inserting or changing a document means updating the posting lists of every word it contains, so heavy write traffic is more expensive than with a plain table. Large engines batch updates into immutable segments and merge them in the background, so a new document may not be searchable for a second or so (near-real-time search).
For a few thousand rows, a database LIKE or built-in full-text feature is usually enough. Add a search engine when scale, ranking quality or features justify running another system.
08Common interview questions
Q: What is an inverted index?
A: A map from each term to the list of documents (and positions) containing it.
Q: How does a multi-word AND query work?
A: Intersect the posting lists of each term.
Q: How does phrase search work?
A: Store positions, then check that the second word appears at the position right after the first.
Q: What is TF-IDF?
A: A relevance score: term frequency in the document times inverse document frequency across the collection, so rare words count more.
Q: Why is LIKE '%x%' slow?
A: It cannot use an ordered index and scans every row.
Q: What do stemming and stop words do?
A: Stemming maps word variants to a root. Stop words are very common words dropped from the index to save space.