Almost every product eventually needs search, and almost every product starts by approximating it with the database it already has. WHERE description LIKE '%pattern%' works on the first thousand rows and then stops working for two separate reasons, and the two are worth separating because they have different fixes.

The first reason is performance. A leading wildcard defeats a B-tree, because a B-tree orders by prefix and there is no prefix to seek to, so the query degenerates to a scan of every row. That is a cost problem, and index design and query optimization explains the mechanics.

The second reason is that substring matching is not search, and this one has no fix within the relational model. A user typing running shoes wants documents containing "run", "runs", "ran", "sneakers", and "trainers", ranked so the most relevant appears first. LIKE finds documents containing the literal characters running shoes in that order, unranked. Even if it were instant, it would return the wrong answer.

The inverted index

A search engine stores the transpose of the table. Instead of a row pointing at its words, each term points at the list of documents containing it. That list is a postings list, and the mapping from terms to postings lists is an inverted index.

Answering running AND shoes becomes an intersection of two sorted integer lists rather than a scan of documents. The lists are stored sorted by document id precisely so that intersection is a linear merge, and real implementations add skip pointers so that a long list can jump forward when the short list has advanced past a run of ids. The practical consequence is that the cost of a conjunctive query is governed by the rarest term, since that list bounds how many candidates can survive. This is why adding a rare word to a query usually makes it faster, which is the opposite of the intuition people bring from SQL.

Postings lists also carry more than document ids. Term frequency within the document is needed for ranking, and term positions are needed for phrase queries, since "running shoes" as a phrase requires that the two terms appear at adjacent positions in the same document rather than merely both appearing somewhere in it.

The analyzer is the actual design decision

Before a term reaches the index, the text passes through an analysis pipeline, and this pipeline is where search quality is won or lost. A typical chain does five things.

Tokenization splits text into terms. Straightforward for English prose and immediately hard everywhere else: C++ and .NET lose their identity to a naive tokenizer, ISO-8601 becomes two tokens, [email protected] becomes three, and Chinese and Japanese have no spaces at all, so tokenization there requires a dictionary or a statistical model.

Lowercasing and character folding make Café match cafe and CAFE. Folding is not always wanted: in a code search product, case is meaningful.

Stemming or lemmatization reduces inflections to a common form so that running matches run. Stemmers are crude rule engines. The Porter stemmer maps university and universe to the same stem, and it maps organization to organ. Lemmatizers use a dictionary and are more accurate and much slower.

Stopword removal drops extremely common terms. This was essential when disks were small and is mostly a mistake now, because it destroys phrase queries: remove to and be and the query to be or not to be has nothing left. Modern ranking already gives common terms almost no weight, so removal buys little.

Synonym expansion maps sneakers to shoes. Done at index time it bloats the index and requires a full reindex to change. Done at query time it is editable but costs query latency and can interact badly with phrase matching.

1import re
2from collections import defaultdict
3
4STOP = {"the", "a", "an", "of"}
5
6def analyze(text):
7    """Tokenize, fold, and apply a deliberately crude stemmer."""
8    toks = re.findall(r"[a-z0-9][a-z0-9+#._-]*", text.lower())
9    out = []
10    for t in toks:
11        if t in STOP:
12            continue
13        for suf in ("ing", "ers", "er", "es", "s"):
14            if len(t) > len(suf) + 2 and t.endswith(suf):
15                t = t[: -len(suf)]
16                break
17        out.append(t)
18    return out
19
20def build_index(docs):
21    index = defaultdict(list)                  # term -> [(doc_id, tf, [positions])]
22    for did, text in enumerate(docs):
23        positions = defaultdict(list)
24        for pos, term in enumerate(analyze(text)):
25            positions[term].append(pos)
26        for term, ps in positions.items():
27            index[term].append((did, len(ps), ps))
28    return index
29
30def intersect(a, b):
31    """Linear merge of two postings lists sorted by doc id."""
32    i = j = 0
33    hits = []
34    while i < len(a) and j < len(b):
35        if a[i][0] == b[j][0]:
36            hits.append(a[i][0]); i += 1; j += 1
37        elif a[i][0] < b[j][0]:
38            i += 1
39        else:
40            j += 1
41    return hits

The mismatch that causes most search bugs

The same analyzer must run at index time and at query time, and when the two drift, the symptom is that a document containing a word cannot be found by searching for that word.

If the index stems running to run and the query analyzer does not, the query term running is looked up in an index that contains only run and matches nothing. If the index folds accents and the query does not, café is unfindable. If someone changes the synonym list and applies it only at query time when the existing index was built with index-time expansion, half the corpus behaves differently from the other half.

Two practices prevent almost all of this. Define the analyzer once as a named configuration and reference it from both sides rather than declaring it twice. And treat any analyzer change as requiring a full reindex, because the existing postings were produced by the old rules and there is no incremental way to fix them. That reindex requirement is what makes the analyzer a schema decision rather than a setting, and it is the reason the operational section of this lesson is mostly about reindexing.