skip to content

How do skip pointers inside a postings list speed up intersecting a rare term with a common one?

level: seniorimportance: should knowfreq 38%

answer

  1. Fifty postings against five million
  2. Drive the loop from the shortest list
  3. You need to jump, not to scan
  4. Checkpoints must hold absolute IDs
  5. Blocks can also be skipped on score

basics

~20 s

An AND query drives iteration from the rarest term and asks the other lists to advance to each candidate document. Skip pointers store absolute document IDs and byte offsets at intervals, so advancing jumps over whole blocks instead of decoding every posting.

solid answer

~50 s

A conjunction is executed as a **leapfrog**: take the shortest postings list, and for each of its document IDs ask every other list to *advance* to that ID or beyond. Without help, advance is a linear walk that decodes every intervening posting — catastrophic when the rare term has fifty postings and the common one has millions. A **skip index** fixes it: at regular intervals the postings store a checkpoint holding an absolute document ID plus the byte offsets at which decoding of postings (and of positions, when present) may resume. Advancing means scanning the checkpoints, seeking to the last one at or before the target, and decoding forward only inside that final block. Large lists carry multiple skip levels so the checkpoint search itself is logarithmic rather than linear. The same machinery powers phrase queries and top-k algorithms such as WAND and block-max WAND, which additionally store a maximum achievable score per block so entire blocks can be skipped when they cannot enter the top results.

code

python · 10 lines
python
# leapfrog AND: drive from the shortest list, jump the long one
def intersect(rare, common):
    hits = []
    for doc in rare:                  # tens of postings
        landed = common.advance(doc)  # uses skip checkpoints, not a linear walk
        if landed == doc:
            hits.append(doc)
        elif landed is None:
            break
    return hits

go deeper

for a junior

Recall that postings are sorted so lists can be walked together, and that engines store periodic checkpoints allowing a jump forward rather than reading every entry.

for a middle

Explain the leapfrog algorithm and the advance primitive, and be able to say why an unaided advance makes the whole conjunction cost as much as the longest list.

for a senior

Detail what a checkpoint holds — absolute document ID plus postings and positions offsets — and name the query shapes where skipping wins nothing, so the structure sounds like an engineering trade rather than a fact.

for a principal

Own the retrieval-strategy angle: dynamic pruning with per-block score bounds is what makes top-k affordable at scale, and custom scoring that violates those bounds silently removes the optimisation across the whole platform.

## The query shape that motivates skipping Consider a two-term conjunction where one term appears in fifty documents and the other in five million. The answer can contain at most fifty documents. Any execution that touches five million postings is doing four orders of magnitude more work than the result justifies, and this shape — one selective term beside one common one — is the ordinary case in real queries, not an edge case. ## Leapfrog intersection The standard algorithm drives from the shortest list. For each candidate document ID from the rare term, call `advance(target)` on every other list, which positions that list at the first document ID greater than or equal to the target. If every list lands exactly on the target, the document matches; otherwise the largest returned ID becomes the next target and the process repeats. Generalised to N terms this is the classic "leapfrog" or "zig-zag" join, and it is why postings must be sorted by document ID: `advance` is only meaningful on an ordered sequence. The algorithm is only as good as `advance`. Implemented as a linear scan, the total work is proportional to the *longest* list, and the sortedness has bought nothing. ## What a skip index is A skip index is a sparse, ordered set of checkpoints over the postings of one term. Each checkpoint records: - an **absolute document ID** — necessary because the postings themselves are gap-encoded and therefore meaningless without a starting point; - the **byte offset** into the postings where decoding may resume at that document; - often a **separate offset into the positions data**, since positions live in their own stream and must be resynchronised too; - in score-aware implementations, the **maximum score achievable** by any posting in the block that follows. Checkpoints are placed every k postings, or equivalently at block boundaries when postings are encoded in fixed-size blocks. To advance to a target, the engine binary-searches or scans the checkpoints, seeks to the last one not past the target, and then decodes forward through at most one block. ## Multiple levels For a list with millions of postings, even scanning the checkpoints linearly is expensive. Implementations therefore build several levels — checkpoints over checkpoints — so the structure is a skip list in the classical sense and locating the right entry is logarithmic in the list length. Deeper levels are tiny and stay resident in memory; only the bottom level touches the postings stream. ## Cost and when it does not help Skip data costs storage, and the interval is a tuning parameter: too dense and the index bloats and adds decode overhead, too sparse and each advance still decodes a long block. It also only pays when queries actually jump. A pure single-term query streams the whole list from start to finish and never advances past anything, so skipping is dead weight there; a disjunction that must visit every posting of every clause benefits far less than a conjunction. And when the two lists are of comparable length and heavily overlapping, a straight merge already touches nearly every posting, so there is little to skip over. ## Beyond boolean: score-aware skipping Most queries want the top k results, not all matches. That permits a stronger optimisation: if the maximum possible score of an entire block is below the score of the current kth-best result, the block can be skipped without decoding it at all. WAND and its block-max refinement build on exactly this — per-block or per-term score upper bounds plus the ability to advance cheaply — turning top-k retrieval from an exhaustive scan into a pruned one. This is the mechanism behind large, dynamically pruned retrieval, and it is why score upper bounds are stored beside skip data in modern postings formats. It is also why relevance functions that can produce unbounded or arbitrary scores can disable this optimisation and make queries dramatically slower — a real production trap worth naming. ## How to present it Start with the asymmetry — fifty postings against five million — because that is what makes the structure necessary. Describe leapfrog and the `advance` primitive. Then explain what a checkpoint stores, stressing the *absolute* document ID as the thing that makes resuming a gap-encoded stream possible. Close with the top-k extension, which shows you understand that real engines skip on score as well as on document ID.

  • Why must a skip checkpoint store an absolute document ID rather than a gap?
    Because the postings stream is delta-encoded: a value only means something relative to everything decoded before it. A checkpoint exists precisely so decoding can start in the middle, which is impossible without an absolute anchor. The checkpoint also carries byte offsets — into the postings and, when positions are indexed, into the positions stream — so both can resynchronise together.
  • For which query shapes does a skip index earn nothing?
    Anything that reads a list end to end. A single-term query streams its whole postings list and never jumps. A broad disjunction must visit nearly every posting of every clause. Two lists of similar length with heavy overlap merge through almost all their entries anyway. Skipping pays when one clause is far more selective than the others.
  • How does block-max WAND extend skipping from document IDs to scores?
    It stores an upper bound on the score any posting in a block can achieve. During top-k retrieval the engine tracks the current kth-best score, and any block whose upper bound falls below it can be skipped without being decoded. The result is correct top-k with a fraction of the postings read — but only if the scoring function respects the stored bounds.
  • How do you choose the skip interval?
    It is a space-versus-jump-distance trade. A dense interval makes each advance decode very few postings but inflates the index and adds per-jump overhead; a sparse interval is small but leaves long decodes after each seek. Implementations commonly tie checkpoints to the postings block size so the two align, and add higher skip levels for very long lists instead of shrinking the interval.

It is an express train over a local line. Every station is still there in order, but the express stops only at named checkpoints, so getting near your destination takes a few hops and only the last stretch is travelled station by station.

saying these in an interview costs you the question

  • Says the intersection should be driven by the longest list
  • Thinks skipping means postings are unsorted or hashed
  • Claims skip entries store gaps like the postings do
  • Believes skip lists help every query equally
  • Assumes top-k always requires reading every match

context

resolving links…