Intersecting Postings Lists

To answer Brutus AND Calpurnia, a search engine looks up both terms in the dictionary, fetches their postings lists, and finds the documents that appear in both. With the lists from Manning, Raghavan, and Schütze (2008, §1.3),

Brutus     1, 2, 4, 11, 31, 45, 173, 174
Calpurnia  2, 31, 54, 101

the answer is documents 2 and 31. Finding it efficiently is the central operation of query processing. AND queries in the Boolean model need it, and so do ranked systems that require all query terms to be present, as web search engines have traditionally done. This article gives the standard algorithms for intersection and the other set operations, traces each on the same pair of lists, and measures their cost.

The merge algorithm

Postings lists are sorted by document identifier, as described in the inverted index. Sorting lets two lists be intersected in a single pass, by walking through both at once:

1. Place a pointer at the start of each list.
2. Compare the docIDs at the two pointers.
   • If they are equal, the document is in both lists. Add it to the result and advance both pointers.
   • Otherwise, advance the pointer at the smaller docID. That document cannot appear in the other list, because everything from the other pointer onward is larger.
3. Stop when either pointer passes the end of its list.

The reasoning in step 2 is the whole algorithm. Suppose the pointers show 4 in Brutus and 31 in Calpurnia. Every Calpurnia docID still ahead is at least 31, and every one already passed was matched or ruled out earlier, so 4 cannot be in Calpurnia. It is safe to discard 4 and move on. The pointer at the larger docID must stay where it is, because 31 might still appear further along Brutus, as it does.

In Python:

def intersect(p1, p2):
    i = j = 0
    answer = []
    while i < len(p1) and j < len(p2):
        if p1[i] == p2[j]:
            answer.append(p1[i])
            i += 1
            j += 1
        elif p1[i] < p2[j]:
            i += 1
        else:
            j += 1
    return answer

The trace for Brutus and Calpurnia:

Eight comparisons produce the answer 2, 31. The last two Brutus postings, 173 and 174, are never examined, because the shorter list ran out first.

The demo below steps through the same merge. Each press of Step performs one comparison. Compared entries are outlined, matches are filled, and the triangles mark the two pointers. The skip setting belongs to the next article, skip pointers; leave it at "no skips" for the plain merge.

Cost

Each comparison advances at least one pointer, so the number of comparisons is at most the sum of the list lengths. More precisely, a merge of lists of lengths $x$ and $y$ makes at most $x + y - 1$ comparisons, because the loop stops as soon as one list is used up, and at least $\min(x, y)$, because every entry of the list that runs out first must be passed. The merge therefore takes $O(x + y)$ time. This bound is a main reason postings are kept sorted. Intersecting unsorted lists would require sorting them first or building a hash table of one list, and neither approach suits lists stored on disk and read sequentially.

The result of an intersection is never longer than the shorter input. That property is what makes the order of operations matter in multi-term queries, the subject of optimizing Boolean queries.

The other operations

Union and difference use the same two-pointer walk, differing only in which documents they output.

OR (union). Output every docID from either list, once, in order. When the docIDs at the pointers are equal, output it once and advance both. Otherwise, output the smaller and advance its pointer. When one list is exhausted, copy the rest of the other. On the example lists:

The result is 1, 2, 4, 11, 31, 45, 54, 101, 173, 174. The comparisons are the same eight as for AND, but the copying step means every posting of both lists is touched. The cost is again $O(x + y)$, and unlike intersection the result can be as long as both inputs combined, $x + y$ when the lists share nothing.

AND NOT (difference). For Brutus AND NOT Calpurnia, output the docIDs of the first list that do not appear in the second:

The result is 1, 4, 11, 45, 173, 174, again in $O(x + y)$. The operation is not symmetric: a docID found only in Calpurnia, such as 54, is passed over without being output.

OR NOT. Brutus OR NOT Calpurnia matches every document that contains Brutus or lacks Calpurnia, which is nearly the entire collection. Computing it requires the complement of Calpurnia's list, a list of every document in the collection except a few, so its cost is proportional to the collection size $N$, not to the lengths of the postings lists. NOT on its own has the same problem. Systems therefore usually evaluate NOT only as part of AND NOT, and many reject or warn about queries whose result is dominated by a complement. A standalone NOT is computed by subtracting from a list of all documents, which is how my course assignment handled it (see parsing and evaluating Boolean queries).

Multi-term queries

A query A AND B AND C is evaluated as a sequence of pairwise intersections. Intersect two lists, then intersect the result with the third, and so on. Since every intermediate result is no longer than the shortest list so far, starting with the shortest lists keeps all intermediate results small. An alternative evaluates all the lists at once, advancing a pointer in each and outputting a docID when all pointers agree. This avoids materializing intermediate results, and it is the form used by document-at-a-time query processing in ranked systems, where each candidate document is scored completely before moving to the next.

When one list is much shorter

The merge examines every posting of both lists in the worst case. That is wasteful when one list is short and the other long, for example a rare term with 4 postings and a common term with a million. Almost all of the long list's postings are passed over without matching anything.

Binary search

The alternative is to search instead of scan. For each posting of the short list, search for its docID in the long list. Binary search finds each in about $\log_2 y$ comparisons, so the intersection costs $O(x \log y)$. For $x = 4$ and $y = 1{,}000{,}000$, that is about 80 comparisons instead of up to a million. Each search can begin where the previous one ended, since the short list is sorted too, which trims the range a little.

Galloping search

Binary search spends the same $\log_2$ of the remaining list on every lookup, even when the next match is only a few entries ahead. Galloping, or exponential search, starts from the current position and probes 1, 2, 4, 8, and so on postings ahead until it passes the target, then performs a binary search within the last step. If the target lies $d$ entries ahead, the doubling phase takes about $\log_2 d$ probes and the binary search about $\log_2 d$ more. When the $x$ short-list docIDs are spread evenly through the long list, consecutive targets are about $d = y/x$ entries apart, so the total is about

$$2x \log_2 \frac{y}{x}$$

comparisons. Galloping therefore adapts to how the lists are distributed, costing little when matches are close together and little more than binary search when they are far apart (Bentley and Yao, 1976; Demaine, López-Ortiz, and Munro, 2000).

On the small example, searching for each Calpurnia docID in Brutus:

Both use more comparisons than the 8 of the merge. With lists of similar length there is nothing to skip, and searching only adds overhead. Searching pays off when the length ratio is large.

Measuring the three methods

The figure measures where each method wins. A list of $x = 100$ random docIDs is intersected with lists of $y = 100$ to $y = 1{,}000{,}000$ random docIDs drawn from a collection of ten million, and the docID comparisons are counted. Each point is the median of 30 seeded runs, with the interquartile range shaded, though the bands are too narrow to see at most points.

The medians follow the formulas. The merge makes close to $x + y$ comparisons, slightly fewer because it stops when the short list runs out, typically within 1 percent of the end of the long one. Binary search makes about $x \log_2 (y/2)$, since on average half of the long list remains to be searched (for $y = 10^{6}$, $100 \times \log_2 500{,}000 \approx 1{,}890$). Galloping makes about $2x \log_2(y/x)$ (for $y = 10^{6}$, $200 \times \log_2 10{,}000 \approx 2{,}660$). Galloping is never far from the better of the other two: it matches the merge when the lists are of similar length, and costs at most about 40 percent more than binary search when they are very unequal here, because random docIDs are spread evenly. When matches cluster, galloping's short searches make it cheaper than binary search. The script is tools/experiments/boolean/postings_intersection.py.

Searching in a real index

Two practical points limit pure search. Postings are usually compressed as sequences of gaps, which must be decoded sequentially, so arbitrary positions in a list cannot be reached directly. And lists stored on disk are cheapest to read in long sequential runs. Skip pointers solve the first problem by storing, at intervals, the docID and position needed to resume decoding partway through a list, which lets an intersection jump ahead without decoding everything it skips. Culpepper and Moffat (2010) compare these approaches in detail.

Summary

These operations are the building blocks of every query processor in the course. The next articles speed them up with skip pointers, order them with query optimization, and extend them to positions for phrase queries.

References

• Bentley, J. L., and Yao, A. C.-C. (1976). An almost optimal algorithm for unbounded searching. Information Processing Letters, 5(3), 82–87.
• 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.