Problem. An inverted index maps each term to its posting list: the sorted ids of the documents containing it.
"attention" → [2, 5, 9, 14, 20, 31]
"kv" → [5, 14, 31, 40]
"cache" → [1, 5, 14, 31, 33]
Answer two kinds of query over k terms:
- OR (any term): the union, in sorted order, each id once →
[1, 2, 5, 9, 14, 20, 31, 33, 40] - AND (all terms): the intersection →
[5, 14, 31]
Posting lists for common terms hold millions of ids, so the cost depends on how much of each list you must touch.
Why it matters. Keyword search (BM25) still sits in front of or beside vector search in most RAG systems ("hybrid
retrieval"), and it's built on exactly these merges. Search engines, log search (find every request with
model=x AND status=500) and dataset filtering all run AND / OR over sorted id lists. The two operations need different
tools: a heap for the union, the shortest list for the intersection.