4 - Index for Text Retrieval

By now we have most of the pieces of a text retrieval system. We can turn documents and queries into terms through tokenization and normalization, and we can say what a good result looks like using precision and recall. Chapter 1 gave us models that score how well a document matches a query, from Boolean matching to the vector space model and BM25. One practical question remains: how do we find the matching documents quickly when the collection holds millions of them? Scoring every document against every query, one after another, does not scale.

Fast retrieval is a balancing act between three competing goals: the quality of the ranked results, the latency of each query, and the storage the index consumes. The inverted index is the data structure that has held this balance for decades. It made full-text search practical on the modest hardware of the 1970s and 1980s, and it still sits at the core of today’s search engines. Its defining property is that the work per query grows with the number of query terms, not with the size of the collection. Only recently have dense vector methods reached comparable speed at large scale, and even then they are often paired with an inverted index rather than replacing it. We return to dense retrieval in later chapters.

This chapter opens up the mechanics. We start from a small example and build the inverted file, then show how the same structure serves the retrieval models from Chapter 1. From there we add metadata filters and faceted search, and we look at how compression keeps the index small. We close with practical, low-cost ways to run production-grade search: full-text search inside a database you may already operate, the Lucene library, and the distributed engines built on top of it.