Building the Index

A search engine answers a query in a few hundred milliseconds, which is far too little time to read a corpus. It succeeds only because almost everything it needs was computed in advance by a scheduled batch job and written to disk. That job is the subject here.

What it produces, and these are the terms the rest of the page uses:

• Tokens, the normalized words a document is chopped into. Not the words as typed: Running and runs both become run, so a search for one finds the other.
• The inverted index, a map from each token to the list of documents containing it. Searching means looking up a few of those lists instead of reading the corpus.
• Term statistics, chiefly how many documents contain each token. Rare tokens identify a document and common ones do not, so the scoring function needs these counts to weight a match, and counting them requires seeing the whole corpus at once.
• Document vectors, each document’s meaning as a list of numbers, so documents can be matched by meaning rather than by shared words.
• Document evidence, facts about a document that do not depend on the query, such as how often people click it.

Producing these is not a search problem. It is a batch data-engineering problem with the ordinary concerns of one: memory, runtime, schema, cadence, and how output reaches a live consumer without breaking it. The ranking mathematics that consumes these artifacts is thirty years old and settled; this job is where a working system costs what it costs, and it gets the most space here for that reason.

1. The analyzer

Every structure in a lexical search engine takes a term as a primitive. The inverted index maps terms to documents. Document frequency counts documents per term. BM25, the standard scoring function, weights term matches. None of it says where a term comes from.

Splitting on whitespace does not produce terms. Take the fragment The user’s refunds were running late. Split on spaces and you have The, user's, refunds, were, running, late. A user searches refund and matches nothing: not refunds, which is plural. The answer is in the document and the match fails on grammar. Separately, The and the are different strings, so one word occupies two index entries with two document-frequency counts, and both are wrong.

An analyzer is a pipeline turning surface forms into normalized tokens. A representative chain:

raw text
  ─▶ tokenize          split on more than spaces: punctuation, contractions, scripts
  ─▶ lowercase         "The" and "the" become one token
  ─▶ ASCII-fold        "café" and "cafe" become one token
  ─▶ strip possessive  "user's" ─▶ "user"
  ─▶ remove stopwords  drop function words carrying no signal
  ─▶ stem              "refunds", "refunding", "refunded" ─▶ "refund"
normalized tokens

The fragment becomes roughly user, refund, run, late. The query refund now matches, because the query passes through the same pipeline and becomes refund too.

The purpose is to erase differences between surface forms a human would call the same word, so matching and counting happen over words rather than spellings. Each stage merges distinct surface forms into one token, which shrinks the vocabulary and puts more documents into each term’s bucket, giving a more stable rarity estimate.

Measured over one real corpus, adding stages in sequence:

Nearly forty percent of the naive vocabulary was surface-form duplication: the same words in different casings and inflections, counted as different terms, each splitting a term’s document frequency across several keys and corrupting its weight. The analyzer is not cleanup. It is what makes corpus statistics mean what they claim to.

Stemming carries a real cost alongside the gain. It is heuristic, and it overstems: a light stemmer collapsing compress, compressed, compressing to compres is mangling the word, and production stemmers like Porter are more careful but still occasionally merge unrelated words. Stemming trades precision for recall, usually worth it, and it is a trade rather than a free improvement.

One refinement scopes the requirement: the analyzer is chosen per field, not per system. A body field wants full stemming and stopword removal for recall. An identifier or error-code field wants a keyword analyzer that does almost nothing, because stemming an error code is destructive and the exact string is the entire point. Which analyzer a field uses is a schema question.

2. The parity requirement

The analyzer runs in at least three places, and they must produce identical tokens.

It runs when corpus statistics are computed, because document frequency is a count over tokens. It runs when documents are indexed, because postings are keyed by token. It runs at query time, because the query must be turned into the same tokens to look anything up.

If any two disagree by one rule, the token the query produces is not the token the index stored. The lookup misses, or the weight is fetched from the wrong bucket, and the result is a wrong score with no error anywhere. Nothing crashes. The query returns something, ranked by weights computed against a vocabulary the query is not speaking.

The size of the damage is measurable. Taking a real corpus and asking what fraction of query tokens would be looked up under the wrong key if the index used a full analyzer including stemming while the query path used the same analyzer without stemming:

A quarter of all query terms, from one stage of disagreement. Not a quarter of edge cases: a quarter of all tokens, because inflected words are ordinary.

Running indexed as run will never be found by a query producing running, though they are the same word. The user types a word that is in the corpus and gets nothing, and no log line records that anything went wrong.

The exact percentage is corpus- and stemmer-specific. What generalizes is the order of magnitude: a large fraction, not a rounding error.

3. The cross-runtime analyzer decision

Parity is easy when one process holds one analyzer object. It becomes genuinely difficult when the analyzer and the statistics job live in different runtimes, and that split is the common case rather than an unlucky one.

The canonical analyzer in most search stacks is JVM code, because the indexing and serving engine is Lucene-based. The pipeline computing corpus statistics is usually Python, because it is a batch data job and that is where the data tooling lives. So the tokens are defined by Java and must be reproduced by Python, faithfully enough that the statistics table is keyed by byte-identical tokens to the ones the engine produces at index and query time.

That is the decision hiding behind the phrase “wire in the analyzer,” and it has four options with different costs.

1. Reimplement the chain in the second runtime. The most fragile: every rule is a chance to diverge, and divergence is exactly the failure measured above at 25.7%. It also drifts silently over time, because the canonical analyzer can change and nothing forces the copy to follow.
2. Call the real analyzer across a runtime boundary, running the actual JVM chain from the pipeline. Correct by construction, at the cost of a JVM inside a data job, a build dependency, and tests that need the real artifact available.
3. Use a binding or embedded library wrapping the canonical implementation, when one exists for the pipeline’s language.
4. Move the statistics computation into the analyzer’s runtime, so only one analyzer exists.

There is no free option. My own read is that the reimplementation is almost never the right call despite being the easiest to start, because the cost is paid later and invisibly, while every other option pays its cost immediately and visibly. A silent 25% corruption discovered in six months is worse than a JVM in a data pipeline, and that comparison is not close.

Whichever is chosen, the parity test is the part that actually holds the system together: run a sample of real text through both analyzers and assert identical token streams, so a divergence fails a build rather than degrading production. The agreement is a contract, and the test is what stops the contract from rotting.

4. The artifact contract

The build produces files a different system reads, usually owned by a different team, and the interface between them is a contract whether or not anyone writes it down.

The contract covers more than a schema. Three terms it has to state:

• Which weighting variant produced these numbers. The consumer applies a formula, and it must match the one the producer used.
• What a lookup miss should do. A query term absent from the statistics needs a defined fallback rather than a zero that silently removes the term from scoring. Shipping a sentinel value in the artifact itself is the clean way to do it.
• What identifies a document. If the same upstream identifier is reused across source files, the identifier alone is not unique, and the choice of key determines whether two distinct documents collide or both count.

Getting these wrong produces the same failure as a parity break. Plausible numbers, no error, degraded relevance.

5. The streaming counter

A document-frequency count is conceptually trivial: for each document, the set of distinct terms it contains, incremented into a counter. It stops being trivial at corpus scale, for a reason that recurs across batch pipelines.

Counting distinct terms per document requires holding a document’s token set until the document is finished. If the storage format scatters a document’s pieces rather than grouping them, a counter cannot finish any document early, because the next piece could be the last row in the file. The counter therefore holds every document’s token set simultaneously, and as live strings in a high-level language that is roughly fifteen to twenty times the on-disk size. A corpus that is comfortable on disk does not fit in a typical build runner’s memory.

Three ways out, and the choice illustrates how these decisions actually get made:

1. Sort the input so each document’s pieces are contiguous, after which the counter finishes documents as it goes and holds almost nothing. This is an out-of-core sort, so it moves the spill into the sort rather than removing it. If the format is a shared contract with another team, reordering it to suit one consumer also reshapes an interface, and the coupling is silent: a future change to the producer that reorders rows would split documents and emit wrong counts with no error.
2. Stream into an on-disk store keyed by document, dedupe there, aggregate at the end. Peak memory becomes one batch plus the final vocabulary counter. Costs disk and a dependency.
3. Approximate, using a sketch structure for cardinality. Cheap and wrong in a bounded way, which is acceptable for monitoring and not for weights that determine ranking.

The general shape: when a batch job does not fit memory, the fix is usually to give up random access and stream, and the cost is disk plus complexity. The version worth avoiding is the one that appears to fix it by depending on an ordering nobody has promised to preserve.

6. Atomic promotion

The build finishes and the artifacts have to reach the serving layer, which is reading the previous version continuously and cannot be stopped.

Writing into the live location is the obvious approach and it is wrong. The serving layer will read a half-written index: some terms updated, some not, some files present and others still being written. It will not error. It will serve queries against an inconsistent state for the duration of the write.

The pattern is build into staging, then promote atomically. The job writes everything into a location nothing reads, verifies it, and switches the serving layer over in one operation that either happens or does not.

# wrong: readers see a partial index for the duration of the build
build_index --out /serving/current

# right: build into staging, then flip in one atomic step
build_index --out /staging/build-2026-06-06
verify /staging/build-2026-06-06
ln -sfn /staging/build-2026-06-06 /serving/current.tmp
mv -T /serving/current.tmp /serving/current

What counts as atomic depends on the storage. A rename or a symlink swap on a filesystem. A pointer update in a metadata store for object storage, which has no atomic directory rename.

The same problem appears when the consumer discovers builds by scanning for the newest timestamped folder, which is common, and there the fix is a completion sentinel: a marker file written last, with the consumer ignoring any folder lacking it. Without it, ingestion can begin on a folder that is still being written.

The cost of getting this wrong is measurable and large. On one production system, adding sentinel gating took refresh-aligned underfill from peaks of 23 to 32% lasting hours down to a peak of roughly 0.5%, averaging well under 0.1% in the following hours at comparable traffic. Same index, same queries, same code everywhere except the gate. Every one of those short results was a query answered from thinner evidence than intended, and nothing anywhere reported an error.

Promotion also needs a way back. A build can be complete, valid, and worse, and the fastest fix is repointing at the previous build, which requires keeping it.

7. Full rebuild and incremental update

Two ways to keep an index current, and they are the answer to the freshness cost the build/query split imposes.

1. Full rebuild reprocesses the corpus and produces a fresh index. Simple, self-correcting, and expensive, with freshness bounded by the build interval.
2. Incremental update applies only what changed. Fast and cheap, and it drifts: deletions are awkward, and corpus-wide statistics are the real problem. Document frequency and average document length are properties of the whole corpus, so every added document changes, slightly, the correct weight of every term. Incremental systems tolerate this by letting statistics go slightly stale and rebuilding periodically to resynchronize.

Most production systems run both: incremental updates for freshness, periodic full rebuilds to correct drift. The rebuild is not redundant, it is what bounds how far the incremental path is allowed to wander.

A worked example

The corruption is easiest to see when it is only a few lines. Here is a staged analyzer and the specific mistake that produces the 25.7% figure.

import re

STOPWORDS = {"the", "a", "an", "and", "of", "to", "in", "is", "for"}

def split_naive(text):
    return re.findall(r"[A-Za-z][A-Za-z]+", text)      # A0: keeps case and everything else

def fold_and_stop(text):                               # A1: lowercase, strip possessive, drop stopwords
    out = []
    for w in split_naive(text):
        w = w.lower()
        if w.endswith("'s"): w = w[:-2]
        if w in STOPWORDS:   continue
        out.append(w)
    return out

def analyze(text):                                     # A2: A1 plus a light stemmer
    return [light_stem(w) for w in fold_and_stop(text)]

Both analyze and fold_and_stop are correct functions. The bug is not in either one. It is that the index was built with analyze and the query path calls fold_and_stop, one stage apart:

query_tokens = fold_and_stop(corpus_text)
misrouted = sum(1 for w in query_tokens if light_stem(w) != w)
print(misrouted / len(query_tokens))                   # 0.257

Nothing here raises. Both functions return lists of strings, both lists look reasonable, and every test that checks either function in isolation passes. The failure exists only in the relationship between two call sites, which is why the defence has to be a test that runs both and compares:

def test_analyzer_parity(sample_texts):
    for text in sample_texts:
        assert index_time_analyzer(text) == query_time_analyzer(text)

That test is the entire safety net for the largest correctness risk in a lexical system, and it fits in three lines. When the two analyzers live in different languages it is more work to run and it is the same assertion, which is the argument for paying whatever the cross-runtime call costs.