What Lucene does that we didn't

Step 12 of 12, and the engine is finished. Steps 2 through 11 built an index that tokenises and stems, ranks with BM25 at Lucene’s constants, answers phrase and boolean queries, tolerates typos, serves JSON over HTTP, and grows without a rebuild — and the last of them measured all of it against a corpus with known answers. This step changes no engine code. It puts the finished project next to Lucene and names what the difference is, with step 11’s measurements as the baseline.

The starting state is tag search-ch11, the end of step 11: the engine in src/lib.rs — 2,228 lines, tests included — a thin binary in src/main.rs, and the benchmark in benches/. The repository’s only change in this step is the README’s status line, and it is tagged search-ch12; the engine itself stays at search-ch11.

cd search-engine
git checkout search-ch12
cargo run        # the demo
cargo test       # 98 tests

Segments: one file versus many

haystack keeps the whole index in one file. Step 4’s format serialises the dictionary and every postings list into one buffer and flushes it with a single write; step 10 made saves atomic with a temporary file and a rename, and taught the index to replace a document in place — but a save still rewrites the entire file. Adding one document to a two-thousand-document index re-serialises all two thousand. Readers see a consistent snapshot while that happens, because the snapshot is an RwLock guard held inside one process.

Lucene does not rewrite. It writes segments: each flush produces a new, immutable segment holding the documents added since the last one, and a delete is a bit set in a per-segment bitset rather than an edit to existing data. The space a deleted document occupies comes back only when a merge copies the survivors into a new segment and drops the old files, and the default TieredMergePolicy chooses which segments to merge, on background threads. A reader pins the segments it searches through reference counting, so a merge that finishes mid-query never disturbs the query: it finishes against the old files, which are deleted once the last reader lets go. A reader opened straight from the IndexWriter even sees changes that were never committed — that is Lucene’s near-real-time search.

The trade is not subtle. haystack’s save costs O(index size) and holds the process while it happens; Lucene’s costs O(new documents), with merge work paid in the background and competing with queries for I/O. For a folder of documents indexed once, the whole-file save is fine. For a write stream it isn’t. Lucene’s shape has costs of its own: deleted documents still occupy their postings until a merge reclaims them, and every search consults the delete bitset — Elastic’s measurements on a hundred-million-document index put the query throughput lost to 50% deleted documents at 18–46%, depending on the query type.

Compression: even versus smaller

Step 11’s last line is the storage measurement:

memory: 1796173 bytes of text, 1764944 bytes of index (1.0x)

The index comes out at 1.0x the text — slightly smaller, for reasons that belong to this corpus rather than to the format. Every occurrence position is stored explicitly, four bytes at a time, and nothing is compressed. The step 11 article said it plainly: this index is not a compression scheme.

Lucene’s is. Three places, three techniques:

Stored fields — the documents themselves — are compressed in blocks. LZ4 has been the default since Lucene 4.1; DEFLATE is the opt-in for a better ratio at a slower speed.
Postings lists are delta-encoded, so only the gap from the previous document id is stored, and then packed into fixed-size blocks at a bit width set by the block’s largest value. A term that appears in most documents spends a couple of bits per posting.
The term dictionary is sorted and indexed by a finite state transducer, a structure that shares prefixes and suffixes between terms, with a block-tree index on top that maps a prefix onto the handful of disk blocks holding its terms. Doc values — the columnar storage Lucene uses for sorting, faceting and aggregation — are compressed per column as well.

None of that is exotic. All of it is absent from haystack, and the 1.0x measurement is what its absence costs on disk.

Ranking: one exact model versus a shelf of them

haystack has one ranking function: BM25, with k1 = 1.2 and b = 0.75, the values Lucene ships, and the textbook idf, ln(n/df). Step 6 noted the difference: Lucene’s BM25Similarity uses a smoothed idf, ln(1 + (N − df + 0.5)/(df + 0.5)) — the same family, different weights. Every matching document is scored, and the top-k falls out of a full sort. Step 11’s numbers show what that costs: 17.8 µs for a mid-frequency term, 63.5 µs for a term that sits in all 2,000 documents. The cost follows the postings list, not the syntax.

Lucene has a shelf. BM25 is the default, and has been since Lucene 6.0 in 2016, but ClassicSimilarity — the TF-IDF vector space model, the default before it — is still there, alongside the divergence-from-randomness family of Amati and van Rijsbergen, the information-based models of Clinchant and Gaussier, language-model similarities with Dirichlet and Jelinek-Mercer smoothing, and the axiomatic F1/F2/F3 family. Different fields can even use different similarities. Each entry on that shelf is a different bet about what “relevant” means, and none of them wins everywhere; that is why the shelf exists.

Two pieces of Lucene’s machinery attack exactly the costs those numbers expose.

Block-max WAND. Postings are stored in blocks, and each block carries the maximum score any document in it can reach — stored as (term frequency, document length) pairs rather than as a score, so the optimisation survives switching similarity. At query time, a block whose ceiling cannot reach the current k-th-best score is skipped whole, without scoring the documents inside it. The technique is Ding and Suel’s, from 2011, and it has been in Lucene since 8.0. Where haystack scores all 2,000 documents for its common term, block-max WAND scores a fraction of them. The price is honesty about counts: with pruning on, the hit count is a lower bound rather than a number — Elasticsearch’s API returns it with a gte relation. haystack’s counts are exact, because every matching document is scored.

Fuzzy matching over the dictionary. haystack’s typo tolerance is a linear scan of the dictionary: step 11 measured 1.9 ms for a radius-2 query over 512 terms, and the cost grows with the dictionary. Lucene compiles the typo into a Levenshtein automaton and intersects it with the term dictionary’s FST, so the cost follows the number of matches rather than the size of the dictionary. The two implementations even disagree about what an edit is: Lucene counts a transposition as one edit by default, while haystack’s distance is the classic Levenshtein, where “teh” is two steps from “the” — a difference step 8’s article pointed out.

What the measurements say

measured at `search-ch11`	the machinery that targets it
`query/common` 63.5 µs — a term in every document	block-max WAND skips blocks that cannot reach the top-k
`query/fuzzy` 1.91 ms — a linear dictionary scan	an automaton intersected with the FST
`memory` 1.0x — nothing compressed	LZ4 stored fields, bit-packed postings, an FST dictionary
a 35.9 ms build, and every save rewrites the file	immutable segments and background merges
`brute/tokenise` 17.9 ms per query	already beaten 1,433x — the index itself

The last row is the one to keep in proportion. Against the scan a program without an index actually runs, haystack is already three orders of magnitude faster at two thousand documents, and step 11 measured its ranked lists identical to the brute-force answer for all 24 labelled queries, with recall@10 of 1.00 for the exact terms. The machinery above is what stands between this engine and a hundred million documents. Nothing above stands between it and a folder of files.

What this engine keeps

Simplicity, and the exactness that comes with it. One file, no background threads, no merge policy, no lock file. The index, the ranker and the query grammar are one library file that a reader of this track has read line by line, the format can be inspected with a hex editor, and hit counts are exact because nothing is pruned.

Its limits are the mirror of Lucene’s design: one writer, in-process snapshots — two processes writing one index file is still out of scope, as step 10 said — a whole-file save, one ranking function, no faceting or sorting except by score, and one small rule-based stemmer where Lucene runs a chain of character filters, tokenizer and token filters. None of that is a defect at this scale. All of it is the bill that comes due at the next one.

Run it

cd search-engine
git checkout search-ch12
cargo run

The track overview — the full list, now complete
Benchmarking against a real corpus — the measurements this article uses as its baseline
Ranking with BM25 — where the two constants came from