Lesson 14 · Intersecting postings - Build a Search Engine

Intersecting postings

Today you merge two sorted postings lists to find the documents they share. This intersection is exactly what a two-word AND query needs.

The goal

Intersect two sorted postings lists into the documents common to both.

Start here - the target

TO DO

Scenario: Documents common to two terms

Giventhe postings ["d1", "d2", "d4"] and ["d2", "d3", "d4"]

Whenthey are intersected

Thenthe result is ["d2", "d4"]

Andintersecting with an empty list gives []

Background

A query for cat AND dog wants documents containing both terms - the intersection of their postings lists. Because both lists are sorted, you do not need to compare every pair: walk two pointers forward together, and whenever they point at the same id, record it and advance both. When they differ, advance the one pointing at the smaller id.

This linear merge is the beating heart of boolean retrieval, and the reason you kept postings sorted back on lesson 9. It runs in time proportional to the sum of the list lengths, not their product - the difference between a search engine that scales and one that does not.

Make it work

def intersect(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        # advance the smaller; on a tie, keep it
        ...
    return out