Boolean Query Operators
You'll learn how search engines combine multiple search terms using AND, OR, and NOT operators by merging their inverted-index posting lists in different ways.
What Are Boolean Operators in Search?
When users search for "java AND programming" or "python NOT snake," they're using Boolean operators to combine terms. Behind the scenes, your search engine fetches the posting list for each term from the inverted index, then performs set operations to produce the final result.
Think of posting lists as guest lists at different parties. AND finds people at both parties, OR finds people at either party, and NOT finds people at the first party but not the second.
How Each Operator Works
AND Operation: Intersect posting lists
- Query: "machine AND learning"
- Fetch posting list for "machine":
[doc1, doc5, doc7, doc9] - Fetch posting list for "learning":
[doc5, doc7, doc12] - Result:
[doc5, doc7](only documents containing both terms) - Implementation: merge-join sorted lists in
O(n + m)time
OR Operation: Union of posting lists
- Query: "cat OR dog"
- Result: all documents containing either term
- Implementation: merge both lists, keeping all unique document IDs
NOT Operation: Set difference
- Query: "apple NOT fruit"
- Result: documents with "apple" minus those with "fruit"
- Warning: NOT alone (without a positive term) would return nearly everything!
Optimization Notes
When processing complex queries like (A AND B) OR (C AND NOT D), execute in order of smallest posting list first to minimize intermediate results. Modern search engines also skip ahead using techniques like skip pointers rather than scanning entire lists.
Key Takeaway: Boolean operators transform text queries into posting-list set operations—AND intersects, OR unions, and NOT subtracts—enabling precise multi-term document retrieval.