Search and Retrieval

The oldest search engine on record was finished in 1239, ran on about five hundred Dominican friars, and indexed one book. They built a concordance of the Bible: for every word in scripture, every place that word appeared, by book and chapter. A preacher who needed every passage containing mercy could find them without rereading the Bible. No quotations, just locations. It took nine years by hand.

That is an inverted index, and the data structure at the centre of every lexical search engine running today is seven centuries old. The friars had the whole trick: do not store, per document, the words it contains; store, per word, the places that contain it. Computers changed the scale and nothing about the idea.

A search system is a function from a query to a ranked list of documents. Stated that way it sounds like a sorting problem, and the reason it is not is that the corpus is large and the user is waiting. Those two facts together are what generate every structure in the rest of this material. If the corpus were small, you could score every document carefully and sort. If the user were patient, the same. Search is what the problem becomes when neither holds.

1. Build time and query time

A search system runs on two separate clocks.

  1. Build time runs on a schedule, ahead of any query, with minutes or hours available and the whole corpus in view. It produces artifacts: the index, the corpus statistics, the document vectors, whatever precomputed evidence ranking will need.
  2. Query time runs once per request with a few hundred milliseconds of budget and one query in view. It reads what build time produced and produces a ranked list.

Which clock a piece of work belongs on is the question most design arguments in search turn out to be. Term rarity statistics are build time because they require counting over the entire corpus. Reading the query is query time because the query did not exist earlier. The interesting cases are the ones that could go either way, and the cost asymmetry decides them: build time is cheap and stale, query time is expensive and current.

The split also creates one failure class. Build time and query time run in different processes, often in different languages, frequently written by different teams, and they have to agree about things. When they disagree, nothing crashes. The system returns plausible wrong answers, indefinitely, with no error anywhere.

2. Six stages of a search system

A document on disk becomes a ranked result along this path.

txt
BUILD TIME  (scheduled, whole corpus in view)

  documents ──▶ analyze ──┬──▶ inverted index + term statistics
                          ├──▶ embed ──▶ vector index
                          └──▶ document evidence (engagement, quality)


QUERY TIME  (per request, few hundred ms)

  query ──▶ analyze ──┬──▶ lexical retrieve ──┐
                      │                       ├──▶ fuse ──▶ rerank ──▶ results
                      └──▶ semantic retrieve ─┘

Six boxes, and each is a section below.

  1. Analyze turns text into tokens. It appears twice in the diagram, once on documents and once on queries, and it must produce identical output in both places or everything downstream is scored against a vocabulary the query is not speaking.
  2. Lexical retrieval matches literal terms, weighting rare ones far above common ones. It wins on error codes, product names, and anything whose meaning lives in its exact form.
  3. Semantic retrieval matches meaning by embedding text as points in a vector space and finding near neighbours. It wins when the user describes a problem in words the document never uses.
  4. Fusion merges two ranked lists whose scores live on incompatible scales.
  5. Reranking re-scores the top of the fused list with a model too expensive to run over the full candidate set.
  6. Document evidence is everything ranking knows about a document independent of the query: how often people click it, whether it is canonical, how fresh it is. It breaks ties that relevance alone cannot.

The stages are not equal, and the shape of the whole system falls out of their costs. Retrieval touches the whole corpus and must therefore be cheap per document. Reranking touches a few dozen documents and can afford to be expensive per document. That single asymmetry is why search is a funnel rather than one scoring pass: you cannot afford the good scorer everywhere, so you use a cheap scorer to find candidates and spend the expensive one only where the ordering matters.

The funnel has one property that causes real bugs. Every stage after retrieval can only remove documents. Deduplication, collapsing chunks into their parent document, similarity floors, reranking cutoffs: each one shrinks the candidate set and none can grow it. A pipeline that retrieves exactly as many candidates as the user asked for will return fewer, and nothing in it will report an error. Candidate pools need margin, and how much margin is a question about the filtering stages rather than about the retriever.

The ranking mathematics is settled. BM25 is thirty years old, embeddings are a solved product, and the fusion formula is four lines. The algorithm literature covers all of it and covers almost none of what building one of these costs, because the expensive parts are elsewhere. Three of them get proportional space here.

  1. Agreement between the clocks. Tokens computed at build time must match tokens computed at query time, exactly, across process and language boundaries. Violating it corrupts every weight and produces no error.
  2. Knowing whether a change helped. Relevance is not directly observable. Every method for measuring it is an instrument with a resolution limit, and an experiment whose effect is smaller than that limit returns nothing regardless of whether the change worked.
  3. The thinness of the evidence. Engagement signals, the obvious way to improve ranking with real data, are concentrated so heavily in a small part of a corpus that they carry no information for most of it.

The sections below build the machine in the order it runs, then close on measurement.