How Search Engines Work: Inverted Index, Text Analysis, TF-IDF and BM25

Flip to the back of any textbook. That list of words with page numbers next to them is an inverted index, and it is the same idea that powers Elasticsearch, Lucene and Postgres full-text search. Once you see the book index inside a search engine, the rest (analysis, postings, TF-IDF, BM25, segments, refresh) becomes a series of small, sensible decisions.

For this blog, we'll stay on one machine, one index, text only. Shards, replicas and clusters wait for the Elasticsearch blog. Typos, autocomplete, geo and vectors wait for Types of search.

01Why LIKE '%shoe%' falls over

Picture a shop with 10 million products in a table. A user types "shoe" into the search box, and the first version of the code looks like this:

SELECT id, title
FROM products
WHERE title LIKE '%shoe%';

Fine on your laptop, painful in production. A normal database index is a sorted list (a B-tree), which helps only when you know how the value starts. LIKE 'shoe%' can jump to the "shoe" part of the sorted list, the way you jump to "S" in a phone book. LIKE '%shoe%' can't, because "shoe" might sit anywhere inside the title. So the database does a full table scan: it reads every single row and checks it. An index exists to avoid that scan, and a leading wildcard throws it away.

And even when the scan is fast enough, the answer is wrong:

• It misses "Shoes" and "SHOE" unless you lowercase everything, and it treats "running shoe" and "shoes for running" as unrelated.
• It matches "shoehorn", which is not a shoe.
• It can't rank. "Trail running shoe" and a phone case that mentions "shoe" once come back in random order.

Postgres does have a fix for the speed part: its pg_trgm extension builds trigram indexes where, unlike B-tree searches, the search string does not need to be anchored at the start. That fixes speed, but not plurals or ranking.

So we have two separate problems, and they give this blog its shape. First, find the matching documents without reading everything. That is the index. Second, order them so the best ones come first. That is scoring.

02The book index: what an inverted index is

The back of a textbook maps word → page numbers. A search engine does the same thing, except it maps term → list of document IDs. That's the core data structure behind almost every search box you've used.

A few words we'll use for the rest of the series, one line each:

• Document: one thing you can return as a result. A product, a web page, a chat message.
• Field: a named part of a document, like title or body.
• Term: a cleaned-up word from a field, after analysis (next section). "Running" might become the term run.
• Dictionary: the sorted list of every distinct term in the index.
• Postings list: for one term, the sorted list of document IDs that contain it. One entry is a "posting".
• Forward index: the opposite direction, document → its terms.

Let's build one by hand. Take three tiny product titles:

• D1: "Red running shoes"
• D2: "Blue shoe rack"
• D3: "Running in the rain"

Lowercase each word, cut "running" to "run" and "shoes" to "shoe", skip "in" and "the" for now, note which documents each term came from, and sort the terms. The textbook Introduction to Information Retrieval describes exactly these four steps: collect the documents, tokenise, normalise, then build the dictionary and postings. Here is the result next to an ordinary book index.

Now the query "running shoe" is easy. Look up run: D1, D3. Look up shoe: D1, D2. Only D1 has both. We never touched D2's or D3's text. With 10 million products, that difference is the whole game: the work depends on how many documents match, not on how many exist. Elastic's Elasticsearch from the Bottom Up builds another one from three tiny documents.

03Text analysis: turning messy text into terms

Notice what I did quietly above: "Running" became run. That step is called analysis, and it decides what counts as a match. If "Running", "runs" and "RUN!" become three different terms, a user who types "run" misses two of them.

Analysis runs twice: once at index time on the document, and again at query time on what the user typed. Both sides must produce the same terms, or they never meet in the dictionary. It's like a filing cabinet: if one person files under "Shoes" and another looks under "shoe", the paper is there but nobody finds it.

Here are the steps, in the order they run:

• Character filter: cleans the raw text before it is split. It might strip HTML tags or turn "&" into "and".
• Tokenisation: splits text into tokens, usually on spaces and punctuation. It also records each token's position and character offsets, used later for phrase search and highlighting.
• Normalisation: lowercasing, and folding accents so "café" becomes "cafe".
• Stop words: very common words like "the" and "a". A stop-word filter drops them.
• Stemming: crude suffix chopping by rules. Elastic's docs show an algorithmic stemmer turning both "jumping" and "jumpiness" into jumpi. Not a real word, and it doesn't need to be.
• Lemmatisation: the dictionary-based cousin of stemming. It knows "better" comes from "good".

Let's walk one messy product title through the chain, step by step.

The tokenizer splits "The Runners' NEW shoes!" into four tokens, lowercasing gives the runners new shoes, the stop-word filter drops the, and the stemmer leaves runner, new, shoe.

The trade-offs inside analysis

Every step makes more things match. That's good for recall (did we find all the relevant documents?) and can be bad for precision (are the documents we found actually relevant?). Aggressive stemming can fold "university" and "universe" together. IIR's stemming and lemmatization page is a short tour of this tension.

Stop words have their own trade-off. The classic approach, described in IIR's stop words section, is to sort terms by how often they appear and drop the most common ones. But a query like "to be or not to be" is all stop words. Many teams now keep them. In fact, Elasticsearch's standard analyzer does not remove stop words by default; its stop list defaults to none. Scoring already gives common words a tiny weight anyway.

Some fields should barely be analysed at all: a SKU like AB-1234-XL should match exactly. Elastic's stemming guide repeats the core rule: same stemmer at index and search time.

04Postings lists and boolean queries: finding the matches

Here's the trick that makes everything fast: every postings list is sorted by document ID. Two sorted lists can be combined by walking both from the front with two pointers, never going back.

Boolean queries map onto simple list operations:

• AND = intersect the lists (docs in both).
• OR = union (docs in either).
• NOT = subtract (docs in the first, not the second).

Take running AND shoe. After analysis it becomes run AND shoe. Say run has postings [1, 3, 7, 12] and shoe has [3, 5, 12, 40]. Compare the two heads, move the smaller one forward, and record a match when they're equal:

One plain-words optimisation is worth saying out loud: start with the rarest term. The result of an AND can't be longer than the shortest list, so if trail appears in 500 docs and shoe in 2 million, you walk the 500 and jump ahead in the long list.

What else lives in a posting

A posting usually stores more than the doc ID:

• Term frequency: how many times the term appears in that document. Scoring needs it.
• Positions: where in the field the term appears. Phrase search ("running shoes" as an exact phrase) needs them. We use these in Types of search.

Making postings small

Postings for common terms hold millions of IDs, so engines compress them. The first trick is to store the gaps between IDs instead of the IDs themselves: [3, 12, 40, 41] becomes [3, 9, 28, 1]. Small numbers need fewer bits. Lucene packs gaps in blocks (Frame of Reference). For cached filters it uses Roaring bitmaps: doc IDs are split into blocks of 65,536, and a block with fewer than 4,096 values is stored as a sorted array, otherwise as a bitmap. Adrien Grand's post Frame of Reference and Roaring Bitmaps explains both.

Finding the term itself

And how do you find shoe among millions of terms? Lucene keeps a compact index into its term dictionary, built as an FST (finite state transducer: an automaton that shares common prefixes and suffixes between terms, so a huge sorted term list fits in little memory). For the rabbit hole, Andrew Gallant's Index 1,600,000,000 Keys with Automata and Rust is the friendliest FST explainer I know.

05Scoring, part 1: TF-IDF in plain words

Matching gives a set. Users want an ordered list. Scoring answers one question: which match is the best match?

Start with two everyday hunches.

Term frequency (TF). A product page that says "trail" five times is probably more about trail gear than one that says it once. So more mentions of a query term should push the score up.

Inverse document frequency (IDF). Not all terms are equally useful. If the query is "new trail shoe", the word new appears in half the catalogue, so matching it tells you almost nothing. trail appears in a few hundred products, so matching it tells you a lot. Document frequency (DF) is the number of documents containing a term; IDF flips it so rare terms weigh more.

Multiply the two and add them up over the query terms, and you have TF-IDF. In the simplest form from the IIR chapter on inverse document frequency, with N documents in total:

idf(t)        = log( N / df(t) )
tf-idf(t, d)  = tf(t, d) × idf(t)
score(q, d)   = sum of tf-idf(t, d) for every term t in the query

In words: "how much this document talks about the term" times "how rare the term is", summed over the query. It works surprisingly well, but it has two flaws, and BM25 exists to fix them.

1. TF grows without limit. A page that repeats "trail" 50 times scores 10 times higher than one that says it 5 times. Keyword stuffing wins.
2. Long documents win by being long. A 5,000-word blog post mentions almost everything a few times. A 6-word product title can't compete, even when the title is exactly what the user wanted.

06Scoring, part 2: BM25, the default everywhere

BM25 keeps IDF and fixes both flaws with two knobs. It comes from the probabilistic relevance framework of information retrieval research, and the canonical write-up is Robertson and Zaragoza's The Probabilistic Relevance Framework: BM25 and Beyond (Foundations and Trends in Information Retrieval 3(4), 2009, pp. 333-389). Today it is the default similarity in Elasticsearch, and the scorer you should assume unless told otherwise.

Knob 1: TF saturation (k1)

Think about restaurant tips. The first friend who says "the biryani is great" changes your mind. By the tenth, you've stopped counting. BM25 treats term frequency the same way: the 10th mention adds much less than the 2nd.

k1 is "how quickly extra mentions stop helping". A low k1 saturates fast; a high k1 lets repetition count for longer. Here's the shape.

To put rough numbers on it (my own arithmetic, for a document of average length with k1 = 1.2), the term-frequency part of BM25 is 1.0 for one mention, about 1.38 for two, about 1.77 for five and about 1.96 for ten. It can never pass k1 + 1 = 2.2. Ten mentions earn roughly twice what one earns, not ten times.

Knob 2: length normalisation (b)

A match in a 10-word title says more than one in a 5,000-word page. BM25 compares each field's length with the average for that field, and scales the TF part down for long fields and up for short ones.

b is "how much we punish long fields". At b = 0, length doesn't matter at all. At b = 1, it fully counts.

The defaults are worth memorising: Elasticsearch's similarity settings give k1 = 1.2 and b = 0.75. Elastic's Practical BM25, Part 2 walks through each part with a four-document example.

A worked example, in words

The user searches for "trail". Two documents match:

• Doc A: a product titled "Trail running shoe", 3 words long, with "trail" once.
• Doc B: a 1,000-word blog post about a holiday, which mentions "trail" three times in passing.

Under raw TF-IDF, Doc B wins: three mentions beat one, with the same IDF. Under BM25, saturation shrinks B's extra mentions, and length normalisation punishes B for being far longer than average while rewarding A for being short. With a 200-word average and the default knobs, my rough arithmetic gives a TF part of about 1.66 for A and 0.85 for B. The short title wins roughly two to one, which is what a shopper wants.

score(D, Q) = sum over each query term q of
    IDF(q) × ( f(q, D) × (k1 + 1) )
             / ( f(q, D) + k1 × (1 - b + b × |D| / avgdl) )

IDF(q) = ln( 1 + (N - n(q) + 0.5) / (n(q) + 0.5) )

07Real systems: Lucene, and everything built on it

Apache Lucene is a Java library, not a server. It does everything we've covered so far: analysis, the inverted index, postings, BM25, segments. Most of the famous search servers wrap it:

• Elasticsearch adds a cluster, a REST API and sharding around Lucene.
• OpenSearch is a community fork, announced in April 2021 and derived from Elasticsearch 7.10.2, so it shares the same Lucene core.
• Solr is a search server built on Apache Lucene.
• MongoDB Search (formerly Atlas Search) is, per MongoDB's product page, built on Apache Lucene too.

Learn Lucene's ideas and you've learned the core of all of them.

Databases you already run have the same idea built in. Postgres stores analysed text as a tsvector and indexes it with GIN, which literally stands for Generalized Inverted Index. Redis Search describes itself as using compressed, inverted indexes, and is built into Redis starting with Redis 8. We compare them properly in Choosing a search engine.

For a real story, LinkedIn's post Did you mean "Galene"? explains how LinkedIn's search started on Lucene, grew layers on top, and was eventually rebuilt as a system called Galene. It explains inverted and forward indexes in plain terms; we summarise it in Search case studies.

One teaser: when the index outgrows one machine, you split it into shards, send the query to every shard, and merge their top results. That's scatter-gather.

08Segments: why Lucene never edits a file

So far the index has been one neat structure. In reality, it's a pile of smaller ones.

Here's the life of a document:

• Add: the new document waits in an in-memory buffer. When the buffer is flushed, it becomes a brand-new small segment.
• Delete: the old segment is not touched. The document is only marked as deleted in a separate small file, and searches filter it out.
• Update: a delete plus an add. The old version is marked deleted; the new version goes into a new segment.

Why not edit files in place? Elasticsearch from the Bottom Up says Lucene's files are immutable, never updated, unlike a B-tree's pages. That buys a lot:

• No locks for readers. A file that never changes can be read by any number of searches at once.
• Great caching. The OS page cache can hold hot files without them ever going stale.
• Better compression. Frozen data is packed tightly once.

The cost is clutter: many small segments slow searches, and deleted documents waste space. So Lucene runs merges: a background job that combines several small segments into one bigger segment and leaves the deleted documents behind. Elasticsearch's merge settings describe exactly this, including that merges are IO-throttled.

The picture looks like a staircase:

Merging isn't free. Every merge rewrites data that was already on disk. Lucene committer Mike McCandless made a lovely video of this in Visualizing Lucene's segment merges. He indexed English Wikipedia (29 GB of plain text) into a 10.87 GB index, and merging copied 67.30 GB in total along the way. That's a write amplification of 6.19: each byte of the final index was written about six times.

09Near-real-time: why a new doc isn't searchable instantly

A classic production puzzle: "I indexed the product, the API said OK, why can't I find it?"

Because the document is still in the in-memory buffer, and searches only read segments. To make it searchable, Lucene has to write a new segment and open a reader that can see it. There are two ways, at very different costs.

• Commit: write the segment files and fsync them (force them from the operating system's memory onto the physical disk), then record the new set of segments. Durable, but fsync is slow, so you can't do it every second.
• Near-real-time (NRT) reopen: write the new segment into the filesystem cache (the operating system's memory copy of the file) and open it for search, without fsync. Cheap, so you can do it often. McCandless explains how it works in Lucene's near-real-time search is fast!; NRT has existed since Lucene 2.9.

Elasticsearch calls the NRT reopen a refresh. According to its near real-time search docs, the default refresh runs every 1 second, but only on indices that have received at least one search in the last 30 seconds. That's why documents become searchable "within 1 second", and why it's called near real-time.

Notice the gap: after a refresh, a document is searchable but not fsynced. If the power dies, what saves it? A write-ahead log: every change is appended to a log on disk before it is acknowledged, and replayed after a crash. Elasticsearch calls its log the translog, and we cover it in the write path of the Elasticsearch blog.

10Relevance tuning basics

Start with the defaults (BM25, a standard analyzer), measure, then change one thing at a time, cheapest first:

1. Pick the right analyzer per field. Stem descriptions; don't stem SKUs, IDs or brand names.
2. Boost fields. A match in the title should usually beat a match in the body.
3. Boost phrases and proximity. "running shoes" next to each other beats the two words far apart. We cover it in Types of search.
4. Add business signals (popularity, rating, recency) on top of the text score.
5. Tune k1 and b only if you have a test set to prove it helped.

To measure, build a small judged set: real queries, each with documents marked good or bad. Track two numbers. Precision: of the results we showed, how many were good? Recall: of all the good documents, how many did we show?

Bigger teams add a learned ranking stage. Slack's Search at Slack describes a two-stage design: Solr retrieves candidates with a few cheap features, then the application re-ranks them with a learned model.

11How to say it in the interview

When I ask "how would you add search to this product?", I'm listening for three things: an inverted index, an analyzer that runs on both sides, and BM25 as the default ranker.

Then expect these follow-ups.

Pitfalls that cost points: forgetting query-time analysis, calling TF-IDF the modern default, and promising real-time search without the refresh cost.