Course contentsShow
← System Design
Lesson 1749 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Query Processing and Term Intersection

Efficiently finding documents matching multiple query terms using posting list intersection algorithms.

Query Processing and Term Intersection

You'll learn: How search engines efficiently find documents that match multiple query terms by intersecting their posting lists.

When a user searches for "system design interview," the search engine must find all documents containing all three terms. The naive approach—scanning every document—would be impossibly slow at scale. Instead, we use the inverted index's posting lists and intersect them intelligently.

The Core Challenge

Each query term has its own posting list (a sorted list of document IDs). For a multi-term query, we need documents that appear in all posting lists. This is a set intersection problem.

Intersection Algorithms

Simple Linear Merge: Walk through all posting lists simultaneously, comparing document IDs. Since lists are sorted, when IDs match across all terms, that document is a result. Time complexity: O(n) where n is the total length of all lists.

Optimized Strategy: Start with the shortest posting list (the rarest term—least documents). For each document ID in this list, check if it exists in the other lists using binary search or skip pointers. This drastically reduces comparisons.

Analogy: Imagine finding friends who like pizza, sushi, and hiking. Instead of checking everyone for all three interests, start with the smallest group (say, hikers), then check only those people for the other two interests.

Skip Pointers Optimization

Posting lists can include skip pointers—shortcuts that jump ahead in the list, letting you skip large chunks of non-matching document IDs during intersection. This turns O(n) traversal into something closer to O(√n) in practice.

Practical Considerations

  • Process terms from shortest to longest posting list
  • Use skip pointers for large lists
  • Cache intermediate results for common query patterns
  • Early termination when one list is exhausted

Key Takeaway: Efficiently processing multi-term queries relies on posting list intersection algorithms that leverage sorted order, starting with the rarest terms, and using skip pointers to avoid scanning every document ID.