This lesson's interactive features are locked, please to keep using them

Boolean Search

Boolean search combines keyword matches with operations like AND, OR, and NOT. For example:

"bear AND wizard"
"bear NOT terror"
"bear OR cyborg"

Remember, thanks to our inverted index, each of these words maps to a set of document IDs:

bear → [1, 3, 5, 7, 9]
wizard → [2, 4, 6, 8]
terror → [7, 9]
cyborg → [2, 6]

So each boolean operation is really just a set operation on those document IDs:

AND = set intersection: keep IDs in both sets.
OR = set union: combine IDs from either set.
NOT = set difference: remove IDs from the first set.

These operations are fast because we're working with sets of numbers, not large text documents.

Boolean Operations in Detail

AND Operation (Intersection)

bear AND forest finds documents that contain both terms:

bear:   [1] [3]     [5] [7]     [9]
forest: [1]     [4] [5]     [8]
AND:    [1]         [5]             # Only overlapping documents

OR Operation (Union)

bear OR cyborg finds documents that contain either term:

bear:   [1]     [3] [5]     [7] [9]
cyborg:     [2]         [6]
OR:     [1] [2] [3] [5] [6] [7] [9] # All documents combined

NOT Operation (Difference)

bear NOT terror finds documents with bear, then excludes documents with terror:

bear:   [1] [3] [5] [7] [9]
terror:             [7] [9]
NOT:    [1] [3] [5]         # Bear docs minus terror docs

We aren't going to implement boolean operations by hand, since it's a lot of code that we'd quickly overwrite with more advanced techniques in the next chapter.