We assume everything fits into memory on one machine.

Boolean Retrieval

A query in this case is formed using Boolean operators (AND, NOT). We match the set of documents for which the query is true.

• note that a given set of documents could be sorted by document ID, but not necessarily by relevance to query - just a yes/no match

To execute a Boolean query:

Term-At-A-Time

• We can apply a similar algorithm as merge from merge sort
  • Efficient
  • Must carry over intermediate results ⇒ big memory footprint
• AND - only include a document if next doc from postings is equal
• OR - include documents once
• NOT - flag for inverting ⇒ modify merge

Document-At-A-Time

• For each document, see if it passes query
• Documents are in sorted order ⇒ modify merge operation will work
• Posting lists for each term need to be in memory simultaneously
• NOT query has complications