Commentary: inverted-index

One boolean query, five matching documents, three ways to find them — and a 113× spread in cost that comes down to a single swapped variable. A study guide for inverted_index.py.

cd inverted-index
python3 demo.py                # the aha (§6)
python3 test_inverted_index.py # pins every number this page quotes

1. Orientation

This toy builds an inverted index over 10,000 documents and answers boolean AND queries two different ways. It counts, exactly, how many postings-list entries each query touches.

The index is the boring half — a dict from term to a sorted list of document ids, seven lines of loop. The interesting half is what happens next. Given two sorted lists of document ids and an AND between them, which list do you walk, and how? That question has more than one defensible answer, the answers agree on every result they return, and on one query in this demo they are 113× apart in cost.

By the end you should be able to:

• say what a boolean query's cost is actually proportional to, and why it is not the size of the corpus;
• look at two document frequencies and predict which intersection strategy wins, before running anything;
• explain why a real search engine keeps document frequency in the dictionary, and what it does with that number before it touches a single postings list;
• name the case where the clever algorithm is the slower one — which is the part that lets you place your own system.

2. The problem this mechanism exists to solve

The obvious way to store documents is the way they arrive: document 4,872 is a blob of text; scanning it tells you every word it contains. That structure answers "what is in this document?" — and nobody asks that question. The question people actually ask is the inverse: "which documents contain this word?" Answering it from the forward structure means reading all 10,000 documents, every time.

An inverted index is the transpose. It stores, per term, the list of documents containing it. That one flip is the whole idea, and everything interesting is a consequence of the goals it puts in tension:

• Read speed vs. write cost. The index is a second copy of your data, reorganised. Every write now has to update it, and the update touches one list per distinct term in the document. Search engines answer this by not updating in place at all — they write new immutable segments and merge later.
• Space vs. skip speed. A postings list is a sorted list of integers, so it compresses beautifully (store the gaps, not the ids). But compressed lists cannot be indexed randomly — and random access is exactly what the fast intersection in §5.5 depends on. Every real format is a negotiation between those two.
• Exactness vs. early exit. A ranked query can stop once it is certain no unseen document can crack the top 10. A boolean query cannot: every match is part of the answer.

That last tension is why this toy does boolean AND and no ranking at all. With ranking in the picture, "how much work is this query?" gets tangled up with scoring heuristics. Strip ranking out and the answer is fully determined — every strategy returns the identical document ids — so the only remaining variable is how much work you did to get there. The cost becomes the whole subject.

3. Background you need

None of this is deep, but the commentary below leans on it.

The two that carry the result are selectivity and exponential search. Selectivity skew is the thing the fast strategy is betting on; when the skew goes away, so does the win, and the bet turns into a loss (§6.5). Exponential search is the machinery that cashes the bet — and it is load-bearing: replace the doubling with bound += 1 and the headline query goes from 110 steps to 6,254 (§5.4).

4. The mental model

Before any code. Two pictures: what the index is, and what intersecting two of its lists looks like.

A postings list is sorted, ascending, always. That is not decoration: it is the precondition for everything below. Two sorted lists can be intersected without ever building a set, and a sorted list can be searched rather than scanned.

Now the same query, the AND obelisk, run two ways over those two lists:

5. Reading the source

The file is 176 lines. Read it in this order.

5.1 The unit of cost, declared in the docstring

"""A miniature inverted index: tokenize documents, build postings lists, and
answer boolean AND queries two different ways.

The index itself is the boring half. The interesting half is the
*intersection*: given two sorted lists of document ids, which one do you walk,
and how? Every function that touches a postings list is handed a `Steps`
meter, so the cost of a query is a number the demo can print rather than
something you have to profile for.

One step = one postings entry examined. That is the unit the whole toy is
denominated in.

The design decision that makes this toy work is here rather than in any algorithm: cost is counted, not timed. A Steps object is threaded through every function that touches a list, and one step means one postings entry examined.

Timing would have been easier to write and much worse to learn from. A wall-clock number on 8,526 integers is dominated by interpreter overhead and cache behaviour, varies run to run, and would make every claim on this page environment-specific in a way you could not check. A step count is exact, reproducible to the digit, and — this is the real payoff — it is the same quantity a production engine cares about, because on a real index each of those entries is a byte range that may have to be decompressed or read from disk. The toy counts the thing that would cost you I/O.

5.2 build_index — sorted by construction, not by sorting

    index = {}
    for doc_id, text in enumerate(docs):
        for term in tokenize(text):
            postings = index.setdefault(term, [])
            if not postings or postings[-1] != doc_id:
                postings.append(doc_id)
    return index

There is no sort() in this file, and no hashing of document contents anywhere. Document ids are handed out by enumerate, so they increase as the loop runs, so every append lands on the end of an already-ascending list. Sortedness is a free consequence of the iteration order rather than a step you pay for. Real indexers work hard to preserve exactly this property (they build in document order, per segment) precisely because the alternative is sorting millions of lists.

The guard postings[-1] != doc_id is the one judgement call in the function, and it is a correctness line, not an optimisation. Real text repeats words; so does this toy's corpus (demo.py:59-60 emits a term twice for the bottom 30% of its probability band). Without the guard, a document containing "the" twice contributes two entries:

The list stays non-decreasing, so both intersection algorithms still run happily and return a wrong answer quietly: document 4,872 appears twice in a list of 5 hits. This is the failure mode worth internalising — postings algorithms assume strictly increasing, and violating that doesn't crash, it corrupts.

tokenize is text.lower().split() and nothing else: no stemming, no stopword list. Dropping stopwords is what a real analyzer does, and it would have been fatal here — the entire demo depends on the being in the index with a df of 8,526.

5.3 intersect_linear — the symmetric one

    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        steps.tick()
        if a[i] == b[j]:
            out.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return out

This is the textbook algorithm, and it is genuinely good: one pass, no allocation beyond the output, perfectly sequential memory access, O(n + m). It is also the one everybody writes first, and it has a property that is easy to miss — it is completely indifferent to which list is shorter.

That indifference is the point of comparison for the whole page. There is no argument a and b could be swapped into that would change what this function costs. The loop advances one cursor per step regardless, so the cost is fixed by where the cursors end up, which is fixed by the data.

That gives an exact formula, worth having because it explains a number in §6 that looks wrong. The loop terminates when either list is exhausted, and a match advances both cursors in a single step, so:

For the AND obelisk: obelisk's last document is 7,267, which sits at index 6,203 of the, so the merge consumes 6,204 entries of the, all 5 of obelisk, and finds 5 matches. 6204 + 5 − 5 = 6,204, which is what the demo prints. Note this is less than df(the) = 8,526: the merge stops early because the rare term ran out at 73% of the way through the corpus. Linear merge is bounded by the position of the rare term's last posting — which is still, on average, half the long list.

5.4 gallop_index — search proportional to distance, not to length

    n = len(postings)
    if start >= n:
        return n
    steps.tick()
    if postings[start] >= target:
        return start

    bound = 1
    while start + bound < n:
        steps.tick()
        if postings[start + bound] >= target:
            break
        bound *= 2

    # Everything at or below start + bound//2 is known to be < target, and
    # the answer is at or below start + bound (or past the end of the list).
    lo = start + bound // 2 + 1
    hi = min(start + bound, n - 1)
    while lo <= hi:
        steps.tick()
        mid = (lo + hi) // 2
        if postings[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo

This answers one question: from cursor position start, where is the first document id at least as large as target? Semantically it is bisect_left starting at an offset — test_gallop_index_matches_bisect_left (test_inverted_index.py lines 114–123) checks that on 200 random lists against every target, because an optimisation that returns a different answer is not an optimisation.

Why not just call bisect_left on the whole list? Because binary search costs log₂(length) — about 13 probes into the — every single time, whether the answer is one entry away or four thousand. Galloping costs log₂(distance). The distinction does not matter for the headline query (where the hops genuinely are thousands of entries) but it matters enormously for the case where the two lists are similar sizes and every hop is a couple of entries: that is precisely the case where a plain binary search would turn a cheap sequential walk into 13 probes per element. §7.3 measures both.

The doubling is the whole mechanism, and it is load-bearing. Change bound *= 2 to bound += 1 — which is still correct, just a linear probe — and re-run the same queries:

Same hits, 57× the cost. Without the doubling, "skipping ahead" degenerates into walking — which is the linear merge again, plus the overhead of a binary search you no longer need.

The line lo = start + bound // 2 + 1 reuses the lower end of the bracket the doubling already established, so the binary search doesn't re-examine territory the probe phase already ruled out. It reads like it must matter. It barely does:

110 → 115. A 4.5% saving on the headline query, 12% on the worst case. Worth writing, not worth explaining — and worth knowing before writing a paragraph claiming that it is where the behaviour lives. It isn't. The behaviour lives in the doubling and in the next function.

5.5 intersect_gallop — the one line the headline rests on

    if drive_shortest and len(a) > len(b):
        a, b = b, a

    out = []
    j = 0
    for doc in a:
        steps.tick()
        j = gallop_index(b, j, doc, steps)
        if j == len(b):
            break
        if b[j] == doc:
            out.append(doc)
            j += 1
    return out

Read the loop and count what it costs: one iteration per entry of a, each costing a driving step plus a gallop into b. The length of b appears nowhere in that count except inside a logarithm. So the cost is O(|a| · log(|b|/|a|)) — set by the driving list.

Which makes the swap the entire algorithm. It is one line, it changes no result, and here is the same query with it and without it:

113×, same five documents. Drive from the 5-entry list and you do 5 jumps; drive from the 8,526-entry list and you do 8,526 iterations, each paying a probe into a 5-entry list to learn nothing.

The second row is the interesting one. Without the swap, obelisk AND the costs 110 and the AND obelisk costs 12,409 — the order you typed the terms in determines the cost by a factor of 113. The swap is what makes the API commutative in cost as well as in result. That is a small line doing a big job: it turns a performance cliff that users would fall off into something they cannot observe.

drive_shortest is a testing seam, not a feature. It exists only so demo.py can price the identical query with the line switched off; nothing in a real engine would ever pass False.

Two smaller decisions, both checked:

• if j == len(b): break — once the cursor runs off the end of b, no later (larger) driving id can match, so the loop stops rather than galloping fruitlessly off the end for every remaining driving entry.
• The swap also makes an unmatched term free rather than expensive: the AND nonexistent costs zero steps (test_inverted_index.py lines 126–130), because the empty list becomes the driver and for doc in a never executes a body.
• j += 1 after a match — advancing past a hit, since document ids are strictly increasing and the next target must be larger. It looks obviously necessary. For the headline query it does nothing at all:

Zero difference where there are 5 hits, 48% worse where there are 5,151. The line only pays when the intersection is dense, which is exactly the regime the headline query is not in. Two lines apart in the same function, one worth 113× and one worth nothing here — that asymmetry is the argument for running the variant instead of reasoning about it.

5.6 query — where a single term stops being free

    steps = Steps()
    lists = [index.get(term, []) for term in terms]
    if not lists:
        return [], steps.n
    if len(lists) == 1:
        steps.tick(len(lists[0]))
        return list(lists[0]), steps.n

    result = lists[0]
    for other in lists[1:]:
        result = intersect(result, other, steps)
    return result, steps.n

Two things are being asserted by this shape, and the opener in §6 depends on both.

A single-term query is charged for every posting. It has no intersection to do; its cost is the cost of handing back 8,526 document ids, one step each. That is an honest accounting — a real engine really does have to materialise or stream every one of those — but it is worth being blunt that this is mostly the price of producing results, not of searching. A query that matches 8,526 documents is expensive because 8,526 documents matched.

A multi-term query never materialises its first list. lists[0] is handed straight to intersect, which touches only the entries it needs. This is the asymmetry that produces the 164× in §6.1: adding a term swaps "emit everything" for "probe a little."

The chain is a plain left-to-right fold: ((a ∩ b) ∩ c). There is no query planner here, and that omission is visible in the cost — see §6.5 and Q6.

6. The demo, and what it proves

demo.py builds a synthetic corpus of 10,000 documents. Each term in a fixed vocabulary is sprinkled into each document with a fixed probability, drawn from one seeded RNG:

VOCAB = (
    ("the", 0.85),
    ("of", 0.60),
    ("and", 0.45),
    ("data", 0.30),
    ("ranking", 0.20),
    ("search", 0.12),
    ("index", 0.06),
    ("postings", 0.02),
    ("corpus", 0.008),
    ("relevance", 0.004),
    ("obelisk", 0.0003),
    ("quantum", 0.0002),
)

def make_corpus(n_docs=N_DOCS, seed=SEED):
    """One `random.Random(seed)`, one draw per (document, vocabulary term)."""
    rng = random.Random(seed)
    docs = []
    for _ in range(n_docs):
        words = []
        for term, p in VOCAB:
            r = rng.random()
            if r < p:
                words.append(term)
                if r < p * 0.3:
                    words.append(term)  # real text repeats terms; so does this
        docs.append(" ".join(words))
    return docs

This is not English, and it is worth saying so plainly: real vocabularies follow Zipf's law, terms co-occur in correlated clusters, and a real the appears in essentially 100% of documents rather than 85%. What the synthetic corpus buys is the one property the demo needs — document frequencies spanning four orders of magnitude, at values that are pinned, so test_document_frequencies_are_pinned (test_inverted_index.py lines 34–42) can assert df(the) = 8526 and df(quantum) = 2 and this page cannot drift from the code. One random.Random(42), one draw per (document, term), consumed in VOCAB order: the corpus is a pure function of the seed. The demo's output is byte-identical across runs and across PYTHONHASHSEED values.

Running it:

python3 demo.py

6.1 The opener: adding a term makes the query cheaper

Start with the thing that offends a SQL intuition. In a table scan, each extra AND predicate is extra work. Here it is the opposite:

8526 / 52 = 164× fewer steps for the more constrained query.

The arithmetic on both sides. the alone: df is 8,526, every posting is a result, one step each (§5.6) — 8,526. the AND quantum: quantum's postings are [3335, 6659], so intersect_gallop swaps and drives from those two entries, one gallop each:

26 + 26 = 52. Both hops are about 2,840 entries long, and both decompose the same way: 1 driving tick + 1 start-position check + 13 doubling probes (strides 1, 2, 4 … 4096, since 2¹² = 4096 is the first that overshoots 2,839) + 11 binary-search steps inside the resulting 2,048-wide bracket = 26. Document 3,335 doesn't contain "the", so the answer is one document, not two.

And the claim has a sharp limit, printed in the same block:

the AND search costs more than the alone — 8,570 vs 8,526 — while returning 1,059 hits instead of 8,526. Adding a term makes a query cheaper only when the added term is selective. search covers 12% of the corpus, which is not selective enough to pay for the probing. Pushed further, it gets worse rather than better:

Four terms, one hit, and 33% more work than the single-term query. This is the opener's boundary: "more terms is cheaper" is not a law, it is what happens when a selective term is available and you use it first.

6.2 The headline: intersection order, 113×

Same query. Same five documents, every time. One line different:

[4872, 5669, 6222, 6499, 7267] in all three cases — test_headline_intersection_order (test_inverted_index.py lines 45–53) asserts the exact list and the exact three step counts. What varies is only how you got there. 12409 / 110 = 112.8, call it 113×.

Where each number comes from:

110 — gallop, driving from obelisk. Five entries, five jumps:

Take the first: hop of 4,169 entries. One driving tick, one check of postings[start], then doubling probes at strides 1, 2, 4 … 8,192 — 14 of them, since 2¹³ = 8192 is the first stride that overshoots — then a binary search over the bracket (4097, 8192], width 4,096, which is 12 steps. 1 + 1 + 14 + 12 = 28. Every subsequent hop is shorter, so every subsequent gallop is cheaper. Note the shape: the cost of a jump grows with the logarithm of the distance, so five jumps across 6,200 entries cost 110 steps while walking those 6,200 entries costs 6,200.

6,204 — linear merge. By the formula in §5.3: obelisk's last document, 7,267, sits at index 6,203 in the, so the merge consumes 6,204 entries of the plus all 5 of obelisk, minus the 5 matches that advanced both cursors at once. 6204 + 5 − 5 = 6,204. Against gallop that is 56×.

12,409 — gallop with the swap removed. Now the drives: 8,526 iterations, one tick each, plus 3,883 probe steps into the 5-entry obelisk list. 8526 + 3883 = 12,409. It is worse than the linear merge, which is the joke — the "fast" algorithm pointed the wrong way is slower than the simple one, because it pays a search per element for the privilege of not finding anything.

6.3 Cost tracks postings length, not corpus size

The headline is about one query on one corpus. The claim underneath it — that a boolean query's cost is set by the lists it touches, not by how much text you own — needs the corpus itself to be the variable, so here is the same query on a corpus ten times larger:

Ten times the documents. The linear merge got 12.8× more expensive — it tracks the corpus, because it walks the common term's list, and that list grows with the corpus. The gallop got 5.3× more expensive, and all of that came from obelisk's own list going from 5 entries to 24 (4.8×); the log factor from the growing tenfold contributed the rest, which is to say almost nothing.

So the win is not fixed at 113×; it widens as the corpus grows, because it is a ratio between something linear in df and something logarithmic in it. That's the property the toy exists to make visible: you pay for the terms you asked about, not for the corpus you own.

6.4 The demo's numbers are pinned by tests

python3 test_inverted_index.py

test_both_strategies_always_agree (test_inverted_index.py lines 85–93) is the one that makes the rest meaningful: it runs all 21 pairs from a 7-term set through all three strategies and asserts identical results every time. The costs differ by two orders of magnitude; the answers never differ at all. Without that test, "113× faster" would be an unfalsified claim about a program that might simply be doing less work because it is wrong.

6.5 The boundary condition — where the effect doesn't just vanish, it inverts

This is the part to take to your own system.

The obvious way to state the result — "galloping beats merging" — is false, and the demo prints the counterexample. Two common terms:

of AND the: 6,064 and 8,526 entries, 5,151 hits. Galloping loses, by 1.9×.

The arithmetic says exactly why. Linear: 6064 + 8525 − 5151 = 9,438 (of runs out first, having consumed all but one entry of the). Gallop: 6,064 driving entries, plus 11,568 probe steps — 1.91 probes per driving entry on average. Every one of those driving entries needed a search to advance a cursor that, on average, only had to move one and a half entries. You paid a binary search to take a single step.

That is the mechanism in one sentence: galloping is a bet that the next match is far away. When one list is 1,705× longer than the other, the next match is thousands of entries ahead and doubling gets you there in about 22 steps. When the lists are the same length, the next match is right there, and the machinery you built to jump a long way is pure overhead.

The demo measures where the bet stops paying, by intersecting the against every other term in the vocabulary:

The crossover is between 4:1 and 7:1 skew on this corpus — test_galloping_loses_when_the_lists_are_the_same_size (test_inverted_index.py lines 69–82) asserts both sides of it. Below that, walking wins; above it, jumping wins, and the further above, the bigger the margin (1,705:1 buys you 56×).

Which is why production engines (Lucene, Postgres GIN) keep document frequency in the dictionary, next to the term — so the planner can read both dfs, in memory, and choose the strategy and the drive order before touching a postings list at all. The IR-book calls this the standard heuristic: process terms in order of increasing document frequency. This toy deliberately doesn't do it (§7.4), and you can see the hole it leaves:

Same three terms, same empty result, 215× apart — decided entirely by the order the user happened to type them in.

7. Design decisions and roads not taken

7.1 No ranking, at all — the biggest cut

No TF-IDF, no BM25, no scores, no top-k. This is the largest thing missing, and cutting it changes what the word "results" means: this toy returns the set of matching documents, where a search engine returns the ten best ones, and those are different problems with different cost structures.

It was cut because ranking would have destroyed the measurement. Once you score, the interesting algorithms are about early termination — WAND, block-max WAND, top-k pruning — where the engine proves that no unseen document can enter the top 10 and stops. That's a great mechanism, but its cost depends on score distributions, which depend on term statistics, which would make every number on this page a function of how realistic the synthetic corpus is. Boolean AND has a fully determined answer, so cost is the only variable, and the comparison is clean.

The honest consequence: in a real engine, "how many postings did we touch" is not the whole story, because a ranked query may legitimately touch far fewer than the boolean one would. See the Magic WAND link in §10.

7.2 Galloping instead of skip pointers

The textbook answer to "make intersection skip ahead" is skip pointers: store every √P-th entry as a shortcut inside the postings list itself. This toy computes the skips instead of storing them.

Galloping wins here for three reasons. It needs no extra structure, so build_index stays at seven lines and the postings list stays a plain list[int]. Its stride adapts to the distance actually being travelled, whereas skip pointers have one fixed spacing chosen when the list was written. And it is what modern engines actually do — Lucene's DocIdSetIterator.advance(target) is exactly gallop_index's contract, and the SIMD intersection literature is all galloping variants.

Skip pointers earn their place when random access is not free — on a compressed, on-disk postings list you cannot binary-search bytes, so the stored skip entries are how you avoid decompressing blocks you don't need. That is a real system's answer to a constraint this toy doesn't have (§8).

7.3 Galloping instead of a binary search per element

If you are going to search rather than walk, why not just bisect_left the long list for each entry of the short one? I wrote that variant and ran it, because the answer is not what I expected:

On the headline query the plain binary search is cheaper than galloping — 66 steps against 110 — and so it is on every extremely-skewed query. Galloping carries a constant-factor overhead (the doubling phase re-probes territory a binary search would have bisected straight past), and when the hops really are thousands of entries long, that overhead is pure loss.

It collects the bill at the other end of the range. A binary search costs log₂(8526) ≈ 13 probes every single time, including when the answer is the next entry along. On of AND the that is 78,869 steps: 4.5× worse than galloping and 8.4× worse than the naive linear merge. Galloping costs log₂(distance), so the same query settles at 1.91 probes per element (§6.5).

So the choice is not "which is faster" but which failure mode you want. Galloping gives up a factor of 1.7 at the skewed end to avoid a factor of 8 at the flat end, and — the part that actually decides it — its worst case is bounded by roughly the linear merge's, while per-element binary search's is not. Picking the algorithm that degrades gracefully beats picking the one that's marginally better at the extreme you designed for.

7.4 No query planner — left-to-right, deliberately

query folds the terms in the order given (§5.6). A real engine sorts them by document frequency first, and CF9 in §6.5 shows that costs this toy 215× on a three-term query.

The planner is absent because it would hide the mechanism. With reordering, every query in the demo would be automatically fast and the reader would never see that the order mattered — the lesson would be "search engines are fast," which teaches nothing. Leaving the fold naive makes the cost of the missing optimisation observable, and turns "engines reorder by df" from a piece of trivia into a number you watched.

Note the two-term case is already handled, but at a different layer: the swap inside intersect_gallop makes pairwise order irrelevant (§5.5). It is only from three terms up that the chain order — which intermediate result you build first — starts to matter, and that is a planner's job, not an intersection routine's.

7.5 A synthetic corpus rather than real text

The corpus is generated, not downloaded. That costs realism: no Zipf distribution, no correlation between terms, no morphology, twelve words total.

It buys reproducibility of a kind this page cannot do without. Every document frequency is asserted in a test, so the numbers in this commentary are pinned to the code rather than to a file you'd have to fetch — and the whole toy stays stdlib-only with no download step. The alternative (ship a text file) would have made the repository heavier and the demo dependent on a corpus whose statistics the reader can't see at a glance. Here you can read the entire generative process in fourteen lines and predict every df in your head.

What the synthetic corpus does not distort is the mechanism: galloping, merging, and the crossover between them depend only on the lengths of the lists and how the ids are distributed within them. It would distort a study of compression (real gap distributions are much more skewed) or of ranking (which needs real term statistics), which is another reason neither is in scope.

7.6 AND only — no OR, no NOT

OR is a merge, not an intersection, and it is fundamentally different: its output is at least as long as its longest input, so there is nothing to skip and galloping cannot help. That asymmetry is real and worth knowing (the IR-book's skip-pointer section makes the same point), but implementing it would add a function whose only lesson is "this one doesn't benefit."

NOT is worse: NOT quantum is 9,998 documents, so a query engine has to either materialise the complement or restrict NOT to appearing alongside a positive term. It is a genuinely interesting design problem and a completely different one.

8. What's simplified vs. the real thing

• Postings are in memory, as Python ints. In a real index they are compressed on disk: delta-encoded (store gaps, not ids) then variable-byte or bit-packed, so a list of 85,157 document ids might occupy well under one byte per entry. This changes the algorithm, not just the storage — you cannot binary-search a variable-length encoding, so the random access gallop_index relies on is replaced by block-level skip data. The "one step" this toy counts becomes "one entry decoded", and decoding is where the time actually goes.
• No I/O, so no block structure. The real cost unit is a page or block read, not an entry. That reshapes the trade-off: an algorithm that touches fewer entries but scatters them across more blocks can lose to one that touches more entries in sequence. Sequential access is why the linear merge survives in production despite everything on this page.
• The index is immutable and built once. Real engines cannot update postings lists in place — inserting a document id in the middle of a compressed list means rewriting it — so they write small immutable segments and merge them in the background, and a query runs against several segments at once and unions the results. Deletion is a tombstone bitmap, not a removal.
• No positions, so no phrase queries. This index stores that a term occurs in a document, not where. A positional index stores a list of offsets per posting, which is typically several times larger than the document list itself, and turns "quantum obelisk" as a phrase into a second intersection — this time over positions within each matching document.
• One process, no concurrency. No locking, no reader/writer separation, no segment refresh. A real engine has to hand a query a consistent view of the index while a merge is rewriting it underneath, which is a point-in-time-snapshot problem, not an indexing one.
• No dictionary structure. index is a Python dict, so term lookup is a hash. A real dictionary is a sorted structure or FST on disk (Lucene uses a finite-state transducer) because it must support prefix and wildcard queries and must not fit in memory. It also stores df beside each term — which, as §6.5 argues, is what makes planning possible before any postings are read.
• No analyzer. text.lower().split() versus stemming, stopwords, case folding, Unicode normalisation, language detection, synonyms. Analysis decides what the terms are, and therefore every df in the demo. Dropping stopwords, the most standard analyzer step of all, would have deleted this toy's headline query outright.

9. Check yourself

Answer before expanding. Each answer is derivable from the source, and each was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Introduction to Information Retrieval §1.3: Processing Boolean queries — Manning, Raghavan and Schütze's chapter on exactly this: the merge algorithm, its O(x+y) bound, and the standard heuristic of processing terms in increasing document frequency, "based on in-memory data before accessing any postings list." That sentence is §6.5 of this page, written better. Start here.
• Introduction to Information Retrieval §2.3: Faster postings list intersection via skip pointers — the stored-skip alternative from §7.2, including the √P spacing heuristic and the observation that skips help AND and do nothing for OR.
• Wikipedia: Exponential search — the algorithm behind gallop_index, due to Bentley and Yao (1976), with the proof that both the doubling phase and the binary search are O(log i) in the position of the key rather than the length of the list. That distinction is why §5.4's bound *= 2 is worth 57×.
• Lucene DocIdSetIterator — the production version of this toy's interface. advance(target) has gallop_index's exact contract ("advance to the first document whose number is ≥ target"), and the javadoc notes that the default implementation just calls nextDoc() in a loop and that real implementations are expected to do much better. Reading this after §5.4 is the moment the toy connects to a real system.
• Adrien Grand: Magic WAND — faster retrieval of top hits in Elasticsearch — what changes once you add the ranking this toy cut (§7.1): block-max WAND skips whole blocks that cannot contain a competitive score, for 3–15×, at the price of no longer knowing the exact total hit count. A good illustration that "how many postings did we touch" stops being the whole cost story.
• Lemire, Boytsov & Kurz: SIMD Compression and the Intersection of Sorted Integers — where this goes when you care about it professionally: SIMD galloping, bit-packed compression, and the interaction between the two (compression makes the random access galloping wants harder). The paper this toy's intersect_gallop is a hand-written cartoon of.
• PostgreSQL: GIN indexes — the same structure inside a relational database. GIN stores "(key, posting list) pairs", switches to a "posting tree" when a list outgrows one index tuple, and hits the same design questions from a different direction. Useful for seeing that an inverted index is not a search-engine thing, it is a data-structure thing.