FINDING NEEDLES · CHAPTER 01

How search works

A search engine does not read every document when you type a word. It has already stored, for each word, the list of documents that contain it.

~12 min read3 documentsTested Python

What you'll learn

  • Why the index runs from word to documents, not the other way
  • How a stop word disappears before any list is stored
  • How AND walks two sorted lists in one pass
  • Why the query must be cut into words the same way the documents were

Before you start

  • Nothing earlier in this series
  • A sorted list, and the idea of a set intersection

The card catalog, flipped

A shelf of books is a forward list. Each book points at the words inside it. Finding every book that says “cedar” means opening all of them. A card catalog does the opposite. The card for “cedar” already names the books.

That flipped list is an inverted index. The word is the key. The value is a posting list: the document ids, kept in order. Lookup is one hop to the list. Scanning the whole corpus is what you no longer do.

Search starts by deciding which documents are even candidates. Ranking, which asks which candidate is better, comes after. This chapter stops at the candidate step: yes or no.

Three notes from a roofing workshop

Small enough to finish by hand. The same three strings are in search_index.py.

catalog · pipeline · invert · latency

MANIM Search flips the catalog: query hits an inverted index, then ranks.
IdTextTerms that get stored
1cedar shingles shed raincedar, shingles, shed, rain
2slate tiles shed snowslate, tiles, shed, snow
3cedar beams hold the roofcedar, beams, hold, roof

Document 3 contains the word “the”. The index does not. “the” is a stop word: so common that a list of every document containing it is almost the whole corpus, and it rarely changes which document you wanted. The tokenizer lowercases, splits on spaces, and drops stop words. Document 3 contributes four terms, not five.

Across the three documents that is 10 terms. Each term is stored once per document, even if a note had repeated it.

Word, then the documents

TermPosting list
cedar[1, 3]
shed[1, 2]
roof[3]
shingles, rain[1]
slate, tiles, snow[2]
beams, hold[3]

The lists are sorted by document id. That order is the whole trick in the next section. A forward index would have been “document 1 contains cedar, shingles, shed, rain”. Useful if you are displaying the note. Useless if the question is “who said cedar?”.

Interactive · Look up a term

Which documents mention this word?

Two pointers, one pass

A Boolean query has no score. A document matches or it does not. AND is the intersection of two posting lists. OR is the union. NOT is everything except a list, which needs a list of all document ids.

Take “cedar AND shed”. The lists are [1, 3] and [1, 2].

  1. Both pointers sit on 1. The ids match, so 1 is a hit. Advance both pointers.
  2. Now the pointers sit on 3 and 2. 2 is smaller, so advance only the shed pointer. That list is finished.
  3. Stop. The hit list is [1]. Document 1 is the only note that says both words. Two comparisons, not a scan of all three documents.

each step throws away one id, so you never look at an id twice. Here |A| and |B| are both 2.

Document 3 has cedar and not shed, so it falls out. Document 2 has shed and not cedar, so it falls out too. Ranking would ask whether document 1 is a good match. Boolean retrieval refuses that question. The next chapter starts it.

Why the ids are stored as jumps

A real posting list is millions of ids long. Sorted ids are turned into gaps: keep the first id, then how far to the next one. The list [8, 11, 14] becomes the gaps 8, 3, 3. The jumps are smaller integers than the raw ids, and smaller integers compress. You add the jumps back up when a query needs the real ids. Compression here is a way to make the walk faster, not a way to archive the index.

The index you can re-run

search_index.pycedar AND shed → [1]
"""A three-document inverted index and a Boolean AND.

The corpus is a roofing workshop, not a textbook fox sentence.
"the" is a stop word, so it never gets a posting list.
"""

# Three short documents. Ids are 1, 2, 3 so the lists stay easy to read.
DOCS = {
    1: "cedar shingles shed rain",
    2: "slate tiles shed snow",
    3: "cedar beams hold the roof",
}

# Dropped before anything is written into the index.
STOP = {"the"}

# A longer sorted list, used only to show gap encoding.
GAP_IDS = [8, 11, 14]


def tokenize(text):
    """Lowercase, split on spaces, drop stop words.

    The same function must run on documents and on queries.
    A query that keeps "the" will look up a term the index never stored.
    """
    return [word for word in text.lower().split() if word not in STOP]


def build_index(docs=None):
    """Map each term to the sorted document ids that contain it.

    One posting per document, even if the word is repeated.
    Lists stay sorted by id so intersection can walk them once.
    """
    docs = DOCS if docs is None else docs
    postings = {}
    for doc_id in sorted(docs):
        seen = set()
        for term in tokenize(docs[doc_id]):
            if term in seen:
                continue
            seen.add(term)
            postings.setdefault(term, []).append(doc_id)
    return postings


def intersect(left, right):
    """Documents in both sorted lists. One pass, no nested scan."""
    i = 0
    j = 0
    hits = []
    while i < len(left) and j < len(right):
        if left[i] == right[j]:
            hits.append(left[i])
            i += 1
            j += 1
        elif left[i] < right[j]:
            i += 1
        else:
            j += 1
    return hits


def gaps(doc_ids):
    """Store the first id, then the jumps between sorted ids.

    [8, 11, 14] becomes [8, 3, 3]. The jumps are smaller than the
    raw ids, which is why posting lists compress.
    """
    if not doc_ids:
        return []
    jumps = [doc_ids[0]]
    for previous, current in zip(doc_ids, doc_ids[1:]):
        jumps.append(current - previous)
    return jumps

Mistakes learners make

A different tokenizer at query time. If the documents dropped “the” and the query keeps it, AND looks up a term with no list and returns nothing. The analyzer is part of the index, not a cosmetic step.

Expecting a “best” document. [1] means “mentions both words”. It does not mean the note answered you. A document that says “cedar” once and one that says it in the title look the same to Boolean AND.

Unsorted lists. The one-pass merge is wrong if either list is out of order. You would miss matches or have to fall back to scanning every id against every other id.

What to remember

  • An inverted index maps a term to sorted document ids. The roofing corpus stores 10 terms.
  • cedar is [1, 3]. shed is [1, 2]. cedar AND shed is [1].
  • “the” is not in the index. The query pipeline has to drop it too.
  • The gaps of [8, 11, 14] are 8, 3, 3. That is how long posting lists stay small.

Check yourself

1. Why does cedar AND shed return only document 1?

Document 1 is the only id that sits in both lists. Document 3 has cedar but not shed. Document 2 has shed but not cedar.

2. What happens if the query is “the roof” and you forget to drop stop words?

“roof” would hit [3]. “the” hits nothing, because it was never stored. AND of a missing list is empty, so you lose document 3.

3. Why sort the posting lists?

So intersection advances the smaller id and never goes backwards. Two lists of length n and m cost n + m steps.

4. Does [1] mean document 1 is a good answer?

No. It means both words occur. How well they match is a score, which this chapter does not compute.

Go to the source

Keep going