The Retrieval Problem — Finding the Needle in Billions of Haystacks

This series is the classical-retrieval companion to the vector-search material this blog already covers: before embeddings and semantic search, there is the foundational problem of matching queries to documents at scale, and the elegant structures (the inverted index, BM25) that solved it. Understanding classical IR is understanding what RAG retrieval is built on — and why modern systems blend the old and the new. Post 1 frames the problem.

Two problems hiding in “search”

“Search” sounds like one task but is really two, and conflating them causes most confusion about how search engines work:

• The matching problem — which documents are relevant to this query? Out of billions, which ones should even be considered? This is about finding candidates.
• The ranking problem — in what order? Once you have thousands of matching documents, which ten go at the top? Relevance isn’t binary; it’s a graded judgment, and getting the order right is most of what makes search feel good.

Both are hard, for a reason that defines the field: scale meets relevance. You must search enormous collections (billions of documents) fast (milliseconds), while returning results that are actually relevant (a human-judgment quality). Speed pulls toward simple, precomputable structures; relevance pulls toward nuanced understanding of meaning. The entire field is the tension between these two, and every technique — the index (post 2), the ranking functions (post 4), the evaluation metrics (post 5) — is a move in that tension.

Why the obvious approach fails

The naive idea — scan every document for the query terms — fails immediately and instructively:

• It’s impossibly slow. Scanning billions of documents per query, even at high speed, takes far too long. Search must answer in milliseconds, so you cannot look at the documents at query time at all. This single constraint forces the central idea of the field: precompute an index so that at query time you consult a data structure, never the raw documents (post 2).
• Exact matching misses relevance. Even if speed weren’t an issue, literal term matching is a poor proxy for relevance. A query for “car” should match documents about “automobiles” and “vehicles”; a search for “running shoes” shouldn’t rank a document that merely contains both words far apart above one actually about running shoes. The gap between the words in the query and the meaning the user wants is the deep problem of IR, and it’s why matching alone was never enough.

These two failures map to the field’s two great inventions: the inverted index (post 2) solves the speed problem by precomputing where every term appears, and ranking functions plus text analysis (posts 3–4) attack the relevance problem by scoring how well documents match and by bridging vocabulary gaps. Modern semantic/vector search (post 7) attacks the relevance problem from the other side, matching by meaning rather than words — but it stands on the same framing this post sets up.

The classic IR pipeline

Putting it together, a search system is a pipeline with an offline half and an online half — a structure worth holding in mind for the whole series:

Offline (indexing time), done once per document: - Ingest and parse documents from the collection. - Analyze the text — break it into terms and normalize them (post 3), so “Running,” “running,” and “runs” are treated consistently. - Build the index — construct the inverted index (post 2) mapping each term to the documents containing it, so lookups are instant.

Online (query time), done per search: - Analyze the query the same way the documents were analyzed (critical — the query and documents must speak the same normalized vocabulary). - Retrieve candidates — use the inverted index to instantly find documents containing the query terms. - Rank the candidates by a relevance score (post 4), and return the top results.

This offline-index / online-retrieve split is the architectural heart of search, and it’s exactly why search is fast: the expensive work (reading and indexing every document) happens once, ahead of time, so queries only touch a compact precomputed structure. It’s also the same shape as RAG retrieval — index your documents offline, retrieve relevant ones at query time to feed an LLM — which is why classical IR is suddenly foundational knowledge again. The vocabulary and structures this series builds are precisely what a retrieval system, classical or neural, is made of.

The throughline: information retrieval is finding relevant information in a large collection, and “search” is really two problems — matching (which documents are relevant?) and ranking (in what order?) — unified by the field’s defining tension, scale meets relevance (search billions of documents in milliseconds while returning genuinely relevant results). The naive scan fails twice: too slow (forcing a precomputed index so queries never touch raw documents) and too literal (exact term matching is a poor proxy for the meaning the user wants). Those failures birthed the field’s inventions — the inverted index (speed) and ranking + text analysis (relevance), with semantic/vector search attacking relevance by meaning. It all runs on the offline-index / online-retrieve pipeline that makes search fast and that RAG retrieval reuses directly.

Key takeaways

• Information retrieval finds relevant information in a large collection; “search” is two problems — matching (which documents are relevant?) and ranking (in what order? — relevance is graded, not binary, and order is most of perceived quality).
• The field’s defining tension is scale meets relevance: search enormous collections fast (milliseconds) while returning relevant (human-judgment) results — speed pulls toward precomputed structures, relevance toward understanding meaning.
• The naive scan-every-document approach fails twice: impossibly slow (→ you must precompute an index and never touch raw documents at query time) and too literal (exact term matching poorly approximates the meaning the user wants — the vocabulary gap).
• These failures map to the field’s inventions: the inverted index (post 2, for speed), text analysis + ranking functions (posts 3–4, for relevance), and semantic/vector search (post 7, relevance by meaning).
• Search runs on an offline-index / online-retrieve pipeline — analyze and index every document once offline; at query time analyze the query the same way, retrieve candidates from the index, and rank them — which is why search is fast and exactly the shape of RAG retrieval.

Further reading

• Information retrieval — the science of finding relevant information
• Full-text search — searching the complete text of documents