Inverted Index & BM25 Search Lab (Interactive)
Type a query and watch tokenization, stemming, posting lists, and BM25 scores rank a live document corpus. A working Lucene-style analyzer and Okapi BM25 scorer: toggle stop words and the stemmer and see relevance re-order.
Inverted Index & BM25 Relevance Engine
A live Lucene-style analyzer + scoring engine over 8 documents: tokens, postings, and BM25.
Analyzed query tokens
shard · database · scal
AND intersection (bitset)
docs [1]
Edge N-Gram typeahead
scal
POSTING LISTS & IDF PER QUERY TERM:
BM25 RANKED RESULTS (3 of 8 docs matched; forward LIKE scan would read all 8):
#1 Sharding explained
score 4.671database sharding splits rows across servers and scaling writes requires a shard key
#2 Replication basics
score 2.394replicas stream the write ahead log of the primary database for read scaling
#3 Caching layers
score 0.940a cache stores hot keys in memory running cached searches reduces database load
The index maps Term → Posting List, so a lookup is O(log N) dictionary access plus a bitset intersection instead of an O(N) LIKE table scan. BM25 rewards rare terms (high IDF), saturates raw term frequency (k1 damping), and normalizes by document length (b) — toggle the stemmer and search “running queries” to see doc 5 jump up the ranking.
How It Works Under the Hood
SQL LIKE scans every row, linear in corpus size, so search engines invert the index: each unique token maps to a posting list of document ids and term frequencies, turning lookups into a dictionary fetch plus bitset intersection. Before indexing, an analyzer lowercases, strips stop words, and stems running to run so queries match grammatical variants. Elasticsearch then ranks with BM25, rewarding rare terms through IDF, damping repeated term frequency with k1, and normalizing field length with b.
Core Architectural Principles
- Term to posting-list mapping answers queries in O(log N) instead of O(N) table scans.
- Stemming and stop-word filters run identically at index time and query time.
- BM25 combines IDF rarity, saturating TF, and length normalization; edge n-grams power typeahead.
When adding search to any design, explain the inverted structure itself, terms to posting lists, then the analyzer pipeline and BM25 factors, to prove it is not just a black-box service. Mention near-real-time refresh latency, and note that exact-match autocomplete uses edge n-grams while fuzzy matching leans on n-gram or edit-distance automata.
Sub-50ms relevance-ranked full-text search versus JVM memory appetite, NRT indexing delay, and no ACID transactions.