Boolean Queries: AND, OR, NOT

The simplest query model: combine terms with set operations on posting lists.

"cat AND dog"   -> intersection of postings(cat) and postings(dog)
"cat OR dog"    -> union
"cat AND NOT dog" -> postings(cat) - postings(dog)
"(cat OR dog) AND fast" -> intersect(union(cat, dog), fast)

Two-pointer intersection is the workhorse. Posting lists are sorted; walk both with two pointers:

O(|a| + |b|). For very long lists with rare terms, skip lists speed this up further: jump ahead in the larger list when the smaller list has a higher value.

Optimization: process the SHORTEST posting list first. If a has 5 docs and b has a million, intersecting them in a-first order checks 5 lookups in b (with binary search) instead of walking all million.

Boolean retrieval used to be the standard (Lexis-Nexis, early library systems). Today it's complemented by ranked retrieval (next chapter) — but Boolean filters are still everywhere ("date range", "category", facets).