Introduction

Search engines do not scan every document for every query. They use an inverted index, which maps each term to a posting list of matching documents, and query processing becomes the problem of combining those posting lists efficiently and then ranking the surviving candidates.

Start with Posting Lists

An inverted index has two main pieces:

• a vocabulary of terms
• a posting list for each term

For example:

search  -> [1, 3, 7, 10]
engine  -> [3, 4, 7, 11]
index   -> [2, 7, 10]

These posting lists are usually sorted by document ID. That sorted order is what makes merging efficient.

Boolean Queries Use List Operations

For an AND query, the engine intersects posting lists. For an OR query, it unions them. For NOT, it subtracts one set from another.

Here is a simple intersection algorithm:

1def intersect(a, b):
2    i = j = 0
3    result = []
4
5    while i < len(a) and j < len(b):
6        if a[i] == b[j]:
7            result.append(a[i])
8            i += 1
9            j += 1
10        elif a[i] < b[j]:
11            i += 1
12        else:
13            j += 1
14
15    return result
16
17
18print(intersect([1, 3, 7, 10], [3, 4, 7, 11]))  # [3, 7]

This runs in linear time relative to the two list lengths, which is why sorted posting lists are so valuable.

A useful optimization is to intersect the shortest posting lists first. If a rare term eliminates most documents quickly, later merges become cheaper.

Ranking Happens After Candidate Merging

Modern search engines do more than Boolean filtering. They often:

1. find candidate documents by merging posting lists
2. compute scores such as BM25 or learned ranking features
3. return the highest-ranked results

That means merging does not usually produce the final order by itself. It produces the candidate set or partial scoring inputs.

Posting lists may also store more than document IDs. They can include:

• term frequency
• field information
• positions within the document

Positions are especially useful for phrase queries. A search for "search engine" is not just an intersection of documents containing both words. It also checks whether the terms occur at adjacent positions in the right order.

Why Engines Use Extra Optimizations

Real engines add optimizations such as:

• skip pointers to jump ahead in long posting lists
• compressed postings to reduce storage and I/O
• query planning that orders operations by estimated cost

Those ideas matter because large search systems are not CPU-bound only. Disk access, memory layout, and cache behavior can dominate performance.

So the conceptual answer is "merge sorted posting lists," but the production answer is "merge them with a lot of careful engineering around skipping, compression, and ranking."

Common Pitfalls

• Thinking the engine scans whole documents at query time instead of using the inverted index.
• Treating merge results as the final ranking rather than the candidate set for scoring.
• Ignoring term positions and assuming phrase queries are just plain intersections.
• Forgetting that query execution order matters; intersecting rare terms first is usually cheaper.

Summary

• Search engines use inverted indexes to map terms to posting lists of matching documents.
• Query processing merges those lists with set-style operations such as intersection and union.
• Sorted posting lists make these merges efficient.
• Real systems also use positions, scores, skip structures, and compression.
• Merging identifies candidate matches; ranking decides which results appear first.