Efficient Query Processing

A unit on what a search engine does to answer quickly and stay small. Answering a ranked query without scoring every posting, with MaxScore, WAND and block-max indexes proved safe; storing postings in block codes and in Elias–Fano; updating an index without rebuilding it; caching results and postings; and searching several engines that cannot be merged. Each result that can be derived is derived, and each method is measured on Reuters-21578, Cranfield or this site's own index.

The course built an inverted index, compressed it with two simple codes, ranked with it, and surveyed how engines are scaled. This unit takes the engine's side of those subjects to full depth. Its question is always the same. The answer is already defined, by a ranking function over an index. How little work, how little memory and how little rebuilding does it take to produce that answer, and what exactly is given up when a shortcut is taken? Each article answers for one part of the engine.

The unit assumes the course's units on text processing and indexing and probabilistic retrieval. In particular it builds on computing vector scores and implementing BM25 for document-at-a-time evaluation, on skip pointers and index compression for the layout of postings lists, on index construction for merging, and on search at scale, which surveyed caching, pruning and partitioning in a few paragraphs each. Those pages state results that this unit proves or measures, and the articles say at each point which page they continue. The course text behind them is Manning, Raghavan and Schütze (2008, chapters 4, 5 and 7). Two surveys cover the ground of the first three articles and are their main secondary sources: Tonellotto, Macdonald and Ounis (2018) for query processing, and Pibiri and Venturini (2021) for compression.

Three things are kept apart in every article, and each has a section that says so.

  • What is proved. That MaxScore, WAND and Block-Max WAND return exactly the top $k$ of exhaustive evaluation, with exact scores and with ties resolved the same way; the space bound of the Elias–Fano representation and its distance from the least any code can use; the cost of each merge strategy in postings written; the hit rate of a cache under a Zipf law of query popularity; and that shared collection statistics make a federated ranking identical to that of a single index.
  • What is cited. The designs of the published algorithms and codes, and every speed or saving measured on a large collection, each from the paper that reported it.
  • What is measured here. Counts that do not depend on the machine: postings scored, postings decoded, bits per posting, postings written, cache hits. They come from scripts in tools/experiments/query-processing/ that run on Reuters-21578, on Cranfield, on a synthetic query stream and on this site's own search index, described in How This Search Works. Timings are given rarely and labeled as one machine's.

The unit uses one notation. A collection has $N$ documents with docIDs 1 to $N$ and $M$ terms, and a term $t$ has document frequency $\mathit{df}_t$. A query asks for the top $k$. The contribution of term $t$ to the score $S(d)$ of document $d$ is $s_t(d)$, the largest contribution in the postings list of $t$ is $U_t$, and $\theta$ is the $k$-th best score found so far. The letters $k_1$ and $b$ are kept for the parameters of BM25.

Answering a query with less work

  • Dynamic Pruning with MaxScore and WAND: term upper bounds and the threshold set by the current top $k$, a safety lemma that covers ties, both algorithms stated in full and proved to return exactly the top $k$, traced on five Reuters postings lists, and counted on Reuters and on this site's index.
  • Block-Max Indexes: an upper bound for every block of a postings list, why the obvious use of it is unsafe, Block-Max WAND with its proof, what skipping needs from the layout of an index, and what the extra numbers cost.

Storing the index in less space

  • Modern Postings Compression: binary packing, patched coding with its choice of width derived, word-aligned and vector-friendly layouts, and Elias–Fano with its space bound proved, each measured in bits per posting on the Reuters postings of the course's compression page.

Keeping the index current

  • Updating an Index: merge strategies between never merging and always merging with their costs derived, immutable segments and deletion, and the log-structured merge tree.
  • Caching in Search Engines: result caches and postings caches, the hit rate under a Zipf law derived and bounded, replacement policies, and expiry.

More than one index

  • Federated Search: describing, selecting and merging across engines that cannot be combined into one index, with CORI and ReDDE, measured on Cranfield split into ten engines.

References

  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 4, 5 and 7. Cambridge University Press. record · 102 pages
  • Pibiri, G. E., and Venturini, R. (2021). Techniques for inverted index compression. ACM Computing Surveys, 53(6), article 125. record · 3 pages
  • Tonellotto, N., Macdonald, C., and Ounis, I. (2018). Efficient query processing for scalable web search. Foundations and Trends in Information Retrieval, 12(4–5), 319–500. record · 4 pages