Skip Pointers

The merge algorithm advances through two postings lists one entry at a time. When one list is short and the other long, nearly all of that work is wasted: the pointer in the long list walks past thousands of docIDs that cannot possibly match, because the short list contains nothing in their range. Skip pointers let the algorithm jump over such stretches. At intervals along a postings list, a skip pointer records a later position in the list and the docID found there. If that docID is still no larger than the docID being sought, everything in between can be skipped.

Skip pointers are added when the index is built and used during intersection. This article describes the algorithm, traces an example, derives the trade-off that determines where to place them and tests it by experiment, following Manning, Raghavan, and Schütze (2008, §2.3) and Moffat and Zobel (1996).

The algorithm

The skip-aware intersection is the ordinary merge with one change. When the pointer at the smaller docID is about to advance, it first checks for a skip:

1. If the docIDs at both pointers are equal, add the docID to the result and advance both pointers.
2. If the docID at pointer $p_1$ is smaller than the docID at $p_2$:
   • if $p_1$ has a skip pointer and the docID at the skip's target is no greater than the docID at $p_2$, follow the skip, and repeat while that remains true;
   • otherwise, advance $p_1$ by one entry.
3. Symmetrically, if the docID at $p_2$ is smaller, try $p_2$'s skip pointers before advancing one entry.

The condition "no greater than" is what makes skipping safe. If the skip's target docID is at most the docID being sought, every docID between the current position and the target is smaller still, so none of them can match. The target itself is not skipped: the pointer lands on it, and it is compared on the next iteration, so a target equal to the sought docID is still found.

A traced example

Take a long postings list containing every multiple of 3 from 3 to 147, which has 49 entries, and a short list containing 40, 41, 90, and 141. The intersection is 90 and 141. Place a skip pointer every 7 entries along the long list, so the skips run 3 → 24, 24 → 45, 45 → 66, 66 → 87, 87 → 108, and 108 → 129.

The plain merge needs 49 comparisons for this pair of lists. The skip-aware version makes 24 docID comparisons and 8 skip checks, 4 of which succeed, for 32 in all. (The failed checks at 24 and 87 are each made twice, once to end a run of skips and again before the single step.) The diagram lays the long list out in rows of seven, one row per skip span, so each skip pointer runs from the start of one row to the start of the next.

The demo runs the same intersection. Change the spacing to see how the counts move, or switch to the Brutus and Calpurnia lists of the previous article, which are too short for skips to help.

The saving here is modest because the long list is short. For a list of a million postings and a query term with a handful, the proportion skipped is far larger.

The example also shows a limitation. Skips can only be taken from positions that have skip pointers. At 42, the pointer is between skip positions, so the algorithm must step forward one entry at a time until it reaches one. Denser skips reduce this stepping but cover less ground each. Multi-level structures get both, combining short skips at the lowest level with long skips above them that span many short ones.

Where to place the skips

Placement involves a trade-off (Manning, Raghavan, and Schütze, 2008, §2.3):

• Many short skips give many opportunities to skip, but each skip covers little ground. They also cost more comparisons, since a skip check happens at every skip position, and more space to store.
• Few long skips are cheap to store and check, but a long skip is often unusable, because its target overshoots the docID being sought, and between skips the algorithm falls back to stepping one entry at a time.

Running the example with a range of spacings shows both effects:

A skip at every entry is worse than no skips at all: it saves docID comparisons but makes a skip check at every position. A skip every 24 entries is never usable, since each target overshoots, and only adds checks. The cheapest spacing for this query lies in between.

Deriving the square-root rule

A simple model explains where the minimum lies. Suppose a list of $L$ postings has a skip pointer every $s$ entries, so it has about $L/s$ skips, and suppose the intersection must move the pointer from the start of the list to a docID near the end. The pointer can follow skips until the next skip would overshoot, at a cost of about one check per skip, then must step through at most $s$ entries one at a time. The cost is therefore at most about

$$C(s) = \frac{L}{s} + s.$$

The first term falls as the skips get longer and the second rises. Setting the derivative to zero,

$$C'(s) = -\frac{L}{s^{2}} + 1 = 0 \quad\Longrightarrow\quad s = \sqrt{L},$$

and the minimum cost is $C(\sqrt{L}) = 2\sqrt{L}$. For $L = 10{,}000$, the best spacing is 100 entries, and reaching the end of the list takes about 200 operations instead of 10,000.

This is the heuristic Manning, Raghavan, and Schütze (2008, §2.3) recommend: place $\sqrt{L}$ evenly spaced skip pointers on a list of length $L$, so that each skip spans about $\sqrt{L}$ entries. The example above used $\sqrt{49} = 7$. They note that the heuristic ignores the distribution of query terms, and the model shows what that means.

When the other list has several docIDs

An intersection seldom looks for a single docID. If the short list has $x$ docIDs spread through the long list, the pointer makes $x$ separate searches, each over a gap of about $L/x$ entries. Each search begins wherever the previous match left the pointer, usually between skip positions, so it steps to the next skip position, and it ends by stepping from the last usable skip to the target. Each of the two stretches averages about $s/2$ entries, so a search costs about $s$ single steps on average, and the cost becomes about

$$C(s) = x\left(\frac{L/x}{s} + s\right) = \frac{L}{s} + x s,$$

which is minimized at $s = \sqrt{L/x}$ with cost $2\sqrt{Lx}$. More docIDs to find means more searches that each end with single steps, so shorter skips pay. The $\sqrt{L}$ rule is the case $x = 1$. In the traced example, $\sqrt{49/4} = 3.5$, and the cheapest spacing is indeed nearby: 5, at 28 operations, with 4 (not in the table) next at 31. The match is only rough, because two of the four docIDs, 40 and 41, are adjacent rather than spread out.

The experiment below tests the model. A list of $L = 10{,}000$ random docIDs from a collection of a million is intersected with $x = 1$, 10, or 100 random docIDs, for spacings from 1 to 5,000. The cost counted is docID comparisons plus skip checks, and each point is the median of 30 seeded runs, with the interquartile range shaded.

The measured minima fall where the model predicts. They are shallow, so the exact best spacing depends on which spacings are tried: for a single docID the median cost stays between 87 and 96 for every spacing tried from 63 to 110, and for ten docIDs spacing 30 costs 610, against 613 at 32. For a single docID the measured cost is about half the model's worst case, because a random docID lies on average halfway along the list, not at its end, and the final stepping averages $s/2$ entries rather than $s$. Its IQR is wide because that position varies from run to run. For 100 docIDs, keeping the $\sqrt{L}$ spacing of 100 costs three times as much as the best spacing. The script is tools/experiments/boolean/skip_pointers.py.

The spacing is fixed when the index is built, before any query is known, so no single spacing is best for every query. A long list is typically intersected with lists much shorter than itself, often after query optimization has reduced the other side to a few documents, which is the situation the $\sqrt{L}$ rule fits. More refined placements exist, but it is a reasonable default.

Space

Each skip pointer stores a docID and a position, and the $\sqrt{L}$ rule adds only $\sqrt{L}$ of them to a list of $L$ postings: 100 pointers for a list of 10,000, or 1,000 for a list of a million, a small fraction of the list's own size.

Limitations

Skip pointers have three further limitations:

• They do not help union. A union must output every posting from both lists, so there is nothing to skip. AND NOT can skip in the list being subtracted, but not in the list being kept.
• They are easiest to build in static indexes. Inserting postings into a list changes the positions skips point to. In a dynamic index, skip pointers are usually rebuilt when segments are merged rather than maintained continuously (see index construction).
• Their benefit depends on hardware. A skip saves comparisons but costs storage and memory traffic. If a whole postings list must be read from disk anyway, the time saved in comparisons may be small compared with the time spent reading. The benefit is largest when lists are in memory and the comparison work dominates.

Skip pointers also exist only on the stored postings lists. The intermediate result of a multi-term query is built on the fly and has none, so only the original lists can be skipped (Manning, Raghavan, and Schütze, 2008, §2.3).

Skipping in compressed indexes

In a real index, postings are compressed as sequences of gaps, and a gap can only be turned into a docID by adding up all the gaps before it. A skip pointer in a compressed list must therefore record two things: the docID at its target and the byte offset where decoding can resume. With both, the intersection can jump into the middle of a compressed list and continue decoding from there. Moffat and Zobel (1996) introduced this design, calling the result a self-indexing inverted file, and showed that it made queries substantially faster despite the extra space.

Modern systems store postings in fixed-size compressed blocks, typically of 128 docIDs, and keep for each block the largest docID it contains. Skipping then means skipping whole blocks: if a block's largest docID is smaller than the docID being sought, the block is never decompressed. Lucene has long used multi-level skip data over such blocks, and recent versions use a simpler two-level layout stored alongside the postings. Ranked retrieval extends the idea further. Block-max indexes also store, for each block, the highest score any document in it can receive, so a query that only needs the top results can skip blocks that cannot contain any of them (Ding and Suel, 2011). The basic principle of skip pointers is unchanged: store a little extra information so that most of a long list is never examined.

References

• Ding, S., and Suel, T. (2011). Faster top-k document retrieval using block-max indexes. In Proceedings of SIGIR 2011, 993–1002.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 2.3. Cambridge University Press.
• Moffat, A., and Zobel, J. (1996). Self-indexing inverted files for fast text retrieval. ACM Transactions on Information Systems, 14(4), 349–379.