Inverted Index

Reading every document to answer each query works for 5 documents, not for 5 billion. Search engines instead build an inverted index ahead of time: for every term, the list of documents that contain it.

It's called inverted because a document maps to its words, while the index maps each word back to its documents, like the index at the end of a book. The terms come out of the text analysis pipeline.

DocumentsD1: The cat sat
→
Analyzecat sat
→
Posting listscat → D1, D3
→
Querycat AND sat → D1

1. Documents

Each document is lowercased, split into words, and (optionally) stripped of stop words.

2. The Index

Each term points to its posting list: the documents containing it, and the positions where it appears.

Learn more

Positions are counted before stop words are removed, so the cat keeps cat at position 1. That's what makes phrase queries work even with gaps.

Document frequency (DF) is just the length of the posting list. It comes for free with the index, and it's exactly what TF-IDF and BM25 need to compute IDF.

Real indexes store posting lists sorted by document ID and heavily compressed (storing the gaps between IDs instead of the IDs themselves), since they can hold millions of entries.

3. Query

Learn more

AND intersects posting lists. Engines start with the shortest list: every document missing from it can be skipped in the others. Because lists are sorted, intersecting is a single linear pass, like merging two sorted arrays.

OR merges the lists. This is how TF-IDF and BM25 find their candidates: only documents in at least one posting list get scored, and everything else is never looked at.

Phrase starts with an AND, then checks that the positions are consecutive: sat on the mat needs mat exactly 3 positions after sat.