A query of three terms joined by AND can be evaluated in three different orders, and they do not cost the same. Suppose the terms have document frequencies of 1,000, 100,000, and 500,000. Intersecting the two common terms first means merging lists of 100,000 and 500,000 postings, only to throw almost all of the result away when it meets the rare term. Starting with the rare term keeps every intermediate result at no more than 1,000 documents. With an intersection algorithm that searches rather than scans, the difference is more than an order of magnitude.
Query optimization chooses an evaluation order that produces the same answer with less work. The ideas are those of database query optimization, applied to postings lists: use statistics about the data to estimate the size of intermediate results, and keep them small. This article follows Manning, Raghavan, and Schütze (2008, §1.3), with extensions.
Conjunctions: rarest first
For a query of terms joined only by AND, the rule is simple:
- Look up each term's document frequency, $\mathit{df}$, stored in the dictionary. It is the length of the term's postings list.
- Sort the terms by increasing $\mathit{df}$.
- Intersect the two shortest lists, then intersect the result with each remaining list in order.
The rule works because an intersection is never longer than its shorter input. Starting with the rarest term bounds every intermediate result by that term's document frequency. Each later step then intersects a short list with a long one, which is exactly the case where skip pointers and search-based intersection save the most. Storing document frequency in the dictionary, next to the pointer to each postings list, is what makes the plan cheap to compute before any postings are read.
The effect of the order can be bounded for the frequencies above, $\mathit{df}_a = 1{,}000$, $\mathit{df}_b = 100{,}000$, and $\mathit{df}_c = 500{,}000$:
| Plan | Linear merge, upper bound on comparisons | With binary search, approximately |
|---|---|---|
| $(b \cap c) \cap a$ | $(100{,}000 + 500{,}000) + (100{,}000 + 1{,}000) = 701{,}000$ | $100{,}000 \log_2 500{,}000 + 1{,}000 \log_2 100{,}000 \approx 1{,}910{,}000$ |
| $(a \cap b) \cap c$ | $(1{,}000 + 100{,}000) + (1{,}000 + 500{,}000) = 602{,}000$ | $1{,}000 \log_2 100{,}000 + 1{,}000 \log_2 500{,}000 \approx 35{,}500$ |
With a plain linear merge, the order changes the worst case only modestly, because every long list is scanned to the end in either plan. The large gain comes from combining the order with intersection by search: once the intermediate result is small, each of its few documents can be looked up in the long list in logarithmic time. With search, the two orders differ by a factor of about fifty. Ordering and search-based intersection work together. Neither achieves much without the other.
The bounds in general
The same reasoning gives bounds for any conjunction. Sort the $t$ terms so that $f_1 \le f_2 \le \dots \le f_t$, where $f_i$ is the document frequency of the $i$-th, and write $r_i$ for the size of the intermediate result after the first $i$ terms have been intersected. Every $r_i \le f_1$, since an intersection is no longer than its shorter input. Step $i$ intersects a result of size $r_{i-1}$ with a list of size $f_i$, so
$$\text{merge cost} \le \sum_{i=2}^{t} (r_{i-1} + f_i) \le (t - 1)\, f_1 + \sum_{i=2}^{t} f_i,$$
$$\text{search cost} \approx \sum_{i=2}^{t} r_{i-1} \log_2 f_i \le f_1 \sum_{i=2}^{t} \log_2 f_i.$$
The merge bound is dominated by the sum of all the list lengths, which no order can avoid, since each list is read to the end. The search bound is proportional to the shortest list, $f_1$, and only logarithmic in the others, so it is the search bound that the choice of first term controls. A third saving applies to both: if any intermediate result is empty, evaluation stops, because nothing can survive later intersections. Manning, Raghavan, and Schütze's algorithm (2008, Figure 1.7) stops in this way, and starting with the rarest terms makes an early empty result more likely.
Measured on random postings
The bounds assume the worst intermediate sizes. The actual sizes depend on how the terms co-occur. If terms occur independently, a document contains both $a$ and $b$ with probability $(\mathit{df}_a / N)(\mathit{df}_b / N)$, so the expected size of their intersection in a collection of $N$ documents is
$$|a \cap b| \approx \frac{\mathit{df}_a \, \mathit{df}_b}{N}.$$
With $N = 1{,}000{,}000$ and the frequencies above, that gives $|a \cap b| \approx 100$, $|a \cap c| \approx 500$, $|b \cap c| \approx 50{,}000$, and $|a \cap b \cap c| \approx 50$. To check the plans against these sizes, each term's documents were drawn at random from a million, and each plan was run with the merge, binary search, and galloping search of intersecting postings lists, counting docID comparisons. In each step, the shorter of the two inputs is searched for in the longer. The table gives medians over 30 seeded runs; the interquartile ranges are within 2 percent of the medians for the costs.
| Plan | First result (median) | Final result (median) | Merge | Binary search | Galloping |
|---|---|---|---|---|---|
| $(a \cap b) \cap c$ | 104 | 51 | 598,260 | 17,082 | 15,117 |
| $(a \cap c) \cap b$ | 498 | 51 | 600,315 | 25,182 | 24,576 |
| $(b \cap c) \cap a$ | 49,972 | 51 | 600,906 | 1,784,374 | 464,593 |
Four things stand out. The merge costs about 600,000 comparisons whatever the order, as the bound predicts. The rarest-first plan, $(a \cap b) \cap c$, is the cheapest with search, and the plan that starts with the two common terms costs about a hundred times as much with binary search. The rarest-first plan with binary search costs about half its bound of 35,500, because the intermediate result is about 100 documents, not the 1,000 the bound allows. And galloping softens the penalty of a bad plan, cutting the cost of $(b \cap c)$ by a factor of almost four over binary search, because intersecting 100,000 entries with 500,000 is a case of similar lengths, where galloping behaves like a merge. The script is tools/experiments/boolean/query_optimization.py.
Real terms are not independent. San and Francisco co-occur far more often than their frequencies predict, and two words from unrelated fields far less. The rarest-first rule does not depend on the estimate, since it uses only the guaranteed bound $r_i \le f_1$, which is one reason it is the standard heuristic.
Mixed queries: estimating OR clauses
Queries in conjunctive normal form, an AND of OR clauses, are common in practice. Their clauses must be ordered too, but the size of an OR clause's result is not stored anywhere. It must be estimated. The size of A OR B lies between $\max(\mathit{df}_A, \mathit{df}_B)$, if one term's documents include all of the other's, and $\mathit{df}_A + \mathit{df}_B$, if the two never co-occur. The usual estimate is the sum, a conservative upper bound (Manning, Raghavan, and Schütze, 2008, §1.3). If the collection size $N$ is known and the terms are assumed independent, inclusion and exclusion give a closer estimate, $\mathit{df}_A + \mathit{df}_B - \mathit{df}_A \, \mathit{df}_B / N$, which subtracts the documents expected to contain both. For rare terms the correction is negligible, and the sum serves as well.
An exercise in Manning, Raghavan, and Schütze (2008, §1.3) uses the query
(tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)
with document frequencies tangerine 46,653, trees 316,812, marmalade 107,913, skies 271,658, kaleidoscope 87,009, and eyes 213,312. The estimated clause sizes are:
| Clause | Estimated size |
|---|---|
| kaleidoscope OR eyes | 87,009 + 213,312 = 300,321 |
| tangerine OR trees | 46,653 + 316,812 = 363,465 |
| marmalade OR skies | 107,913 + 271,658 = 379,571 |
The plan evaluates kaleidoscope OR eyes first, intersects it with tangerine OR trees, and intersects that result with marmalade OR skies. The estimates here are close, so the order matters less than in the pure conjunction above. When one clause is much smaller than the others, choosing it first matters as much as choosing the rarest term in a conjunction.
Where to apply NOT
An AND NOT can only remove documents, so it never makes a result larger. The question is when to apply it. Subtracting a common term's list early means reading that whole list, while subtracting it last, from a small intermediate result, lets the algorithm search the NOT list for just the few remaining documents. A reasonable plan therefore evaluates the positive part of a query first, in increasing order of size, and applies AND NOT clauses to the small result at the end. A standalone NOT, or an OR NOT, requires a complement against the whole collection, as explained in intersecting postings lists, and is best avoided or rewritten.
Rewriting queries
Boolean identities can turn a query into an equivalent one that is cheaper to evaluate:
- De Morgan's laws.
NOT (A OR B)equalsNOT A AND NOT B. Inside a conjunction, the right-hand form becomes two AND NOT operations applied to an existing result, which avoids computing a complement. - Factoring.
(A AND B) OR (A AND C)equalsA AND (B OR C). The factored form reads A's list once instead of twice, and intersects it with one union instead of performing two intersections. - Flattening. Nested ANDs, such as
A AND (B AND C), can be flattened into one conjunction, so that all its terms are ordered together by document frequency.
These rewrites are applied to the query tree produced by the parser, before evaluation (see parsing and evaluating Boolean queries). Database systems apply far more elaborate rewriting with cost models, but for most Boolean queries ordering by document frequency and applying NOT last capture most of the available gain.
Beyond a single query
Several further optimizations apply across queries rather than within one:
- Caching stores the results of frequent queries, and of frequent subexpressions such as a common OR clause, so that they are computed once (see search at scale).
- Adaptive intersection decides as it goes whether to merge or to search, depending on how far apart the matches in the two lists turn out to be (Demaine, López-Ortiz, and Munro, 2000; Culpepper and Moffat, 2010).
- Evaluating all lists simultaneously, rather than pairwise, avoids storing intermediate results at all. Ranked query processing generalizes this into document-at-a-time evaluation.
The principle behind all of them is the one this article began with: use what the index knows about its own contents, especially the lengths of its postings lists, to avoid work whose result would be thrown away.
References
- Culpepper, J. S., and Moffat, A. (2010). Efficient set intersection for inverted indexing. ACM Transactions on Information Systems, 29(1), article 1.
- Demaine, E. D., López-Ortiz, A., and Munro, J. I. (2000). Adaptive set intersections, unions, and differences. In Proceedings of SODA 2000, 743–752.
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 1.3. Cambridge University Press.