← Back to Village

Nebula v2

Scaling the search engine to ~10,000 Project Gutenberg books with a persistent, partitioned inverted index — and putting BM25 head-to-head against naive TF‑IDF

View on GitHub

Where v1 left off

The first version of Nebula built its whole inverted index in memory, from scratch, on every run. That was fine for a few hundred books, but indexing ~1,000 books took anywhere from 5 to 30 minutes and the index lived and died with the process. The two "what's next" items at the end of v1 became the two goals of v2:

  1. Scale up. Make the index persistent so it can grow toward the full ~80,000-book Gutenberg catalog without ever needing to fit in RAM.
  2. Rank better. Implement BM25 and measure it against TF‑IDF and its TF-only / IDF-only ablations on the same precision/recall benchmarks.

Going in, I wrote down three hypotheses: BM25 would improve precision and recall, partitioning would improve query time, and index size would scale linearly with corpus size.

information retrieval inverted index hash partitioning BM25 TF-IDF tries Python

Pipeline

Indexing now happens in waves of ~1,000 books, each one appended to partitions on disk. Queries only ever open the partitions their terms hash to:

Batch 1k books→ Hash words → partitions→ Update manifest of files processed
Parse query→ Hash match partitions→ BM25 score→ Heap top-k

Scaling the hardware first

The first attempt at 10k documents overwhelmed my laptop's hard drive. The Gutenberg corpus is roughly 100 GB of plain text at 80k books, so the books themselves moved onto a NAS mounted over a local network, freeing local disk for the index — which is the thing that actually needs to be fast to read.

Before going further, I measured how big the index gets as the corpus grows:

Scatter plot of inverted index size against number of documents: 48 MB at 30 docs, 1.2 GB at 1000, 2.2 GB at 2000, 10 GB at 10000
30 docs → 48 MB · 1k → 1.2 GB · 2k → 2.2 GB · 10k → 10 GB

That hypothesis held up: the index grows linearly, at about 1 GB per 1,000 books. That's a clean rule of thumb, and it's also the bad news — the full catalog would be an ~80 GB index. Loading that into memory isn't an option, so the index had to be split up and persisted.

A persistent, partitioned index

A PartitionedInvertedIndex is just a list of ordinary v1-style InvertedIndex objects. Every word is routed to one of them by a small polynomial string hash, so a given word always lands in the same partition, in every wave:

def hash_string(s, modulus): mult = 997 return functools.reduce(lambda v, c: (v*mult + ord(c)) % modulus, s, 0) hash_id = hash_string(word, self.num_partitions) self.partitions[hash_id].index[word][(doc, line_number)] += 1

Each partition is persisted as a flat, append-only TSV file (1of500.tsv, 2of500.tsv, …), one posting per line. Appending is what makes waves work: a new batch of books builds small temporary partitions in memory, then each one is appended onto its matching file on disk.

word doc line count treasure 120 935 1 treasure 120 3845 1 voyage 1342 210 2

Alongside the partitions sits a manifest — one (dataset, book, length) row per indexed book. It's small enough to always live in memory, where it does two separate jobs: it stops a book from being indexed twice if a wave is re-run, and it holds every book's word count, which TF and BM25 both need. Two different purposes in memory, but convenient to persist together. The full index itself is never entirely in memory at any point.

Query time vs. number of partitions

At query time, each query term is hashed to find its partition, and only those files are read. The benchmark: a 10k-book (~10 GB) index, the 5-term query treasure voyage adventure pirates swords, run 10 times per configuration, with mean run time to execute the search query against the partitioned index as the benchmark measurement.

First, a slow start

The very first run with 5 partitions took 534 seconds — almost nine minutes for one query. My first guess was that the manifest was being reloaded every time a partition was read, since I was reusing the full loader. Fixing that changed nothing (536 s). The real problem was that loading a partition rebuilt its entire index in memory just to look up a handful of words. A loader that skips irrelevant line fixed the issue:

for line in f: word, doc, line_number, count = line.rstrip("\n").split("\t") if word not in query_words: continue index.index[word][(doc, int(line_number))] = int(count)

That brought the 5-partition query down to ~142 s. Then the real study began:

Scatter plot of query runtime against number of partitions, falling from 141 seconds at 5 partitions to 1.6 seconds at 500
Mean of 10 runs, 5-term query over a 10k-book index
Partitions5102050100200500
Mean query time141.3 s60.2 s30.3 s13.4 s5.3 s2.9 s1.6 s

I expected a "V": more partitions means smaller files to scan, until the overhead of opening and closing lots of files takes over and query time climbs back up. With a single 5 word query, that behavior never manifested. Query time kept falling roughly in proportion to partition size all the way to 500 partitions, where a 5-term query takes about a second and a half — so I stopped there.

Even though the graph doesn't show it, but V shape behavoir still exists, but only with long queries. A stem$ wildcard can expand into dozens of terms via the trie, and each term can hit a different partition. With enough terms, a query touches most of the files and can take 30+ minutes. The CLI now warns and asks for confirmation when a wildcard expands to more than a certain number of terms; capping query length at the UI is a quick fix that doesn't need more thought at least for now.

The trie, now with document frequency

I'm hoping to build not just a search engine, but a services that helps with understanding unstructured data. One of the key insights I had during v1 was how important document frequency is when understanding, which search terms are useful and which search terms will pull you into the weeds. Really crafting your search terms to search high value words is a good starting place. In v2 each node in the trie carries a df counter, and a new /trie <stem> command lists every indexed word under a stem along with its count — handy for checking how common a term is before querying it.

class TrieNode: __slots__ = ("children", "is_word", "df")

At 10k books the trie is large but still fits in memory, so it's pickled to disk and loaded at startup. __slots__ drops each node's per-instance __dict__, which adds up across millions of nodes, and it seemed to speed up loading and saving the trie.

BM25

During my literature reivew of information retrieval algorithms, I started with what we will call naive TF-IDF. This represents most basic implementation of combining the term frequency metric (TF) of "A Statistical Approach to Mechanized Encoding and Searching of Literary Information" (1957-Luhn) with the weighting by specificy metric now called inverse document frequency metric (IDF) of "A statistical interpretation of term specificity and its application in retrieval" by Karen Spärck Jones (1972-Jones). Naive TF-IDF just calculates the two metrics individually and multiplies them together. For Nebula_v1, that was the calculation.

By the 90s, there were many different types of TF-IDF metrics, and what is now called BM25 or Okapi BM25 seems to be the most referenced, so that is what was implemented in Nebula_v2. The three papers that seemed to most clearly explain this algorithm to the world are:

Naive TF‑IDF has two weaknesses. TF grows without limit, so a book that says "voyage" 400 times scores twice as high as one that says it 200 times, even though both are clearly about voyages. And dividing by document length is a blunt way to correct for long books. BM25 changes both pieces:

tf = f·(k+1) / ( f + k·(1 − b + b·doclen/avgdoclen) ) k = 1.2, b = 0.75 idf = log( (N − n + 0.5) / (n + 0.5) + 1 )

The average document length is computed once from the manifest, so BM25 costs about the same as naive TF‑IDF at query time.

Precision & recall: BM25 vs. naive TF‑IDF

For relevance labels I used Gutenberg's own bookshelf metadata instead of tagging books by hand. Any book on the "Adventure" shelf counts as relevant to the adventure query, and any book on "Science Fiction" counts for the sci-fi query. The third query targets a single book: Treasure Island (book #120), but with some bad query terms mixed in to show the benefit of the BM25 calculation. Every query was scored four ways (BM25, TF‑IDF, TF only, IDF only) against the same 9,456-book index, measuring precision and recall in the top 20.

Bar chart of precision and recall at 20 for the adventure query: BM25 55%, TF-IDF 60%, TF only 30%, IDF only 20% precision
Adventure: treasure voyage adventure pirates swords (957 relevant)
Bar chart of precision and recall at 20 for the sci-fi query: BM25 10%, TF-IDF 15%, TF only 25%, IDF only 15% precision
Sci-fi: spaceship future technology alien planet (114 relevant)
Bar chart for the Treasure Island query: BM25 and IDF only reach 100% recall, TF-IDF and TF only reach 0%
Treasure Island: voyage yo-ho-ho travel weapons (1 relevant)
Precision@20AdventureSci-fiTreasure Island
(found #120?)
BM2555%10%yes
TF‑IDF60%15%no
TF only30%25%no
IDF only20%15%yes

Treasure Island is where BM25 shows its value

The Treasure Island query doesn't name the book. It describes it with three generic words and one very specific one: yo-ho-ho. Naive TF‑IDF and TF-only both miss the book completely, because the top 20 fills up with books that say "voyage" and "travel" over and over, and nothing limits how much that repetition counts. BM25's saturation caps the reward for repeating common words, which lets the rare, high-IDF term decide the ranking, and Treasure Island makes it into the top 20.

IDF-only finds it too, for the same reason: it scores almost entirely on rarity. But on the broader adventure query IDF-only falls to 20% precision, while BM25 holds 55%, close to TF‑IDF's 60%.

BM25 was the only scoring method that found the single relevant book and stayed competitive on a broad topical query. Every other method did well on one kind of query and badly on the other.

The result isn't a clean sweep, though. The sci-fi query was hard for every method, and BM25 scored lowest on it at 10%. Words like "future" and "technology" are common across the whole corpus, and only 114 of ~9.5k books are on the sci-fi shelf. Bookshelf labels are also a rough measure of relevance: a book can be about pirates without being shelved as "Adventure." So the honest conclusion is that BM25 is the better general-purpose default, not that it beats TF‑IDF on every query. It's now the scorer the Nebula CLI uses.

What I took away

What's next: testing new data structures and algorihtms

From here, I've implemented what is commonly considered the best algorithms and practices for information retrieval. There are many optimizations available in the literature that deserve exploration. Two that I noticed that could be very helpful are inverted index compression and creating multiple inverted indexes, where the query parser chooses between the inverted indexes when deciding how to execute the query. For the next version, I'm not limiting myself to exploring these research directions, but leaving the option open if they help research goals. For the actual goals, I want to explore a few:

As the size of the corpus and index grow, the project should be subject to a few constraints. A document bundle cannot increase the size of the corpus by copying documents. This would result in an explosion in the size of the corpus. Additionally, indexing three word phrases will likely 3x the size of the inverted index, and because of the scaling study above, I know that would be about 60GB. Certain phrases that only include stopwords can be eliminated from this index like "is of the". Stopwords can be chosen algorithmically based on DF score (using the trie), rather than a hand-typed list.