How search engines work

A search engine answers “which documents best match these words?”, a question an OLTP database answers badly. Instead of B-tree pages sorted by key, it normalises text into terms and stores an inverted index mapping every term to the documents that contain it, scores matches with formulas such as BM25, and keeps the index in immutable, sharded segments. It runs beside your primary database as a derived copy, not instead of it.

Picture it first: the lost-and-found counter

A busy railway station logs every lost item in a register, one line per item, numbered by ticket. Asked for “ticket 4512”, the clerk opens the right page at once. That is your primary database: perfect for lookups by key.

Then a passenger asks for “a blue tiffin bag”. Reading the whole register would take all day, so the clerk keeps word cards: blue lists tickets 12, 40 and 77; tiffin lists 40 and 91. She files words in a standard form (“Tiffins” and “TIFFIN” both go on tiffin), pulls the cards for the passenger’s words, ranks a match on the rare tiffin above one on the common blue, and only then walks to the shelves for the top few bags. New items go on a fresh stack of cards that she merges into the main box at night.

Map it back: the register is the primary database, the word cards are the inverted index, writing cards in standard form is analysis, rarity-aware ranking is BM25, walking to the shelves is the fetch phase, and the nightly merge is segment merging.

Why LIKE is not search

Take a 20-million-row products table and the query WHERE title LIKE '%kurta%'. A B-tree is sorted by the whole value from its first character, so a leading wildcard gives it nothing to seek on: the database reads every row. At about 500 bytes per row that is 20,000,000 × 500 B ≈ 10 GB scanned per query. A trigram GIN index (see indexes in practice) can find substrings fast, but it still doesn’t answer what users expect from a search box:

• Words, not substrings. “art” should not match “kurta”.
• Forms and case. “Kurtas”, “KURTA” and “kurta” are the same word.
• Typos and synonyms. “kurtha” and “tunic” should still find kurtas.
• Ranking. The best match first, not table order.
• Filters and facets. Size, price band and brand counts on the same result set.

Each needs structure a database index lacks; types of search maps out the kinds of query involved.

Analysis: turning text into terms

Before anything is indexed, an analyzer turns each text field into a stream of terms. In Elasticsearch an analyzer has three parts, applied in order: zero or more character filters that rewrite raw characters (strip HTML, map symbols), exactly one tokenizer that splits text into tokens and records each token’s position, and zero or more token filters that lowercase, remove stop words, reduce words to a stem, or add synonyms.

The golden rule is that the query is analysed the same way as the documents. If titles are stemmed at index time but the query isn’t, “kurtas” never meets “kurta”. Synonyms are the deliberate exception: query-time synonyms can change without a reindex, while index-time synonyms make queries cheaper but need one.

Indian-language text adds wrinkles. The same visible word can be typed as different Unicode code-point sequences, so normalise to one form first. Users mix scripts and transliterate (“kurta”, “कुर्ता”, “cotton kurta sasta”), so catalogues often index a transliterated field alongside the original. Elasticsearch ships Hindi and Bengali analyzers, but stemmer quality varies, so test with real queries. Typos are handled at query time by fuzzy matching within an edit distance of one or two.

The inverted index

An inverted index has two parts. The term dictionary is every distinct term in a field, sorted, with per-term statistics such as document frequency (how many documents contain it). Each term points to its postings list: the IDs of documents containing the term in ascending order, and for each one the term frequency and the positions where it occurs.

Intersection. For cotton AND kurta, the engine takes the next doc ID from the shorter list and asks the longer list to advance to the first ID at or beyond it. Lucene stores skip data at two levels, one entry per block of 128 documents and another every 32 blocks, so advancing jumps over whole blocks instead of reading every ID. An OR query is a merge of the lists instead of an intersection.

Compression. Because doc IDs are sorted, Lucene stores the gaps between them rather than the IDs, then bit-packs each block of 128 gaps at the width of the largest one; the leftover tail is written as variable-length integers. If the largest gap in a block is 90, each entry needs 7 bits: 128 × 7 = 896 bits = 112 bytes, against 512 bytes as plain 32-bit integers, about 4.6× smaller. Smaller postings mean more of the index fits in the page cache, and that matters more than CPU. Search data structures covers tries and the other structures around the postings.

Phrases. A phrase query such as "navy blue" first intersects the two lists, then checks positions: keep a document only if some position of blue is exactly one more than a position of navy. Reading positions costs extra I/O, which is why phrase queries are slower than plain term queries.

Doc values: the column store inside

The inverted index answers “which documents contain this term?”. Sorting by price or counting results per brand needs the opposite: “what is this field’s value for document 21?”. For that Elasticsearch builds doc values at index time, an on-disk columnar copy of each field, on by default for keywords, numbers and dates but not for analysed text. Matching uses the inverted index; sorting and aggregations read columns, much like an OLAP column store.

Segments: an index that never edits in place

Compressed, sorted postings are fast to read and terrible to update in place; inserting one document would rewrite thousands of lists. Lucene sidesteps the problem the way an LSM tree does: it never modifies data on disk. A Lucene index (one Elasticsearch shard) is a set of immutable segments, each a complete mini inverted index, plus a commit point listing them. A query searches every segment and combines the results.

Follow one write through it:

1. Index. The document is analysed into an in-memory buffer and appended to the shard’s translog, which by default is fsynced on the primary and every replica before the client is acknowledged. The async durability setting fsyncs every 5 s instead, risking those seconds of writes for throughput.
2. Refresh. The buffer is written as a new segment into the filesystem cache, without an fsync, and opened for search. Elasticsearch refreshes every 1 s by default, on indices searched in the last 30 seconds: hence near real-time.
3. Flush. A Lucene commit fsyncs the segments and starts a new translog generation, in the background, so the translog stays quick to replay; by default one is forced at 10 GB of uncommitted operations.
4. Merge. Every refresh adds a small segment, so a background policy combines them; Lucene’s default TieredMergePolicy merges segments of similar size and favours those with many deletions.

Deletes and updates. A segment can’t change, so a delete only marks the document dead in a per-segment bitmap of live documents, and an update is a delete plus a fresh insert. Space returns only when a merge rewrites the segment, which is why Elastic advises deleting whole indices rather than documents as data ages out, and why update-heavy indices pay a steady merge cost (more in disk I/O and durability for search).

Query execution and scoring

Matching finds the candidates; scoring orders them. Lucene’s default is BM25, from Robertson and colleagues’ probabilistic relevance framework. For each query term t in document d:

score(t, d) = IDF(t) × tf / (tf + k1 × (1 − b + b × dl / avgdl))
IDF(t)      = ln(1 + (N − n + 0.5) / (n + 0.5))

tf = occurrences of t in d     dl = length of d     avgdl = average length
N  = documents in the index    n  = documents containing t
k1 = 1.2 (saturation)          b  = 0.75 (length normalisation)

A document’s score is the sum over the query’s terms. Three ideas are packed in:

• Rare terms count more. In a catalogue of 1,000,000 products, kurta appears in 5,000: IDF = ln(1 + 995,000.5 / 5,000.5) = ln(200.0) ≈ 5.30. Cotton appears in 100,000: ln(1 + 9.0) ≈ 2.30. A match on kurta is worth over twice a match on cotton.
• Repetition saturates. For an average-length title, the term-frequency part is tf / (tf + 1.2): 0.45 for one occurrence, 0.63 for two, 0.81 for five and 0.94 for twenty. Stuffing kurta into a title twenty times gains about 2×, not 20×, and can never pass IDF itself.
• Long fields are discounted. With average title length 10, a single kurta in an 8-token title gives 1 / (1 + 1.2 × 0.85) = 0.495, but in a 40-token description only 1 / (1 + 1.2 × 3.25) = 0.204.

Put together for “cotton kurta”: a short 8-token title containing each word once scores 5.30 × 0.495 + 2.30 × 0.495 ≈ 3.76. A 40-token description with kurta twice and cotton once scores 5.30 × 2 / (2 + 3.9) + 2.30 × 0.204 ≈ 1.80 + 0.47 = 2.27. The concise title wins. (Lucene stores document lengths approximately, so real scores differ slightly.)

Top-k without scoring everything. The engine keeps a min-heap of the best k scores so far; its smallest entry is the bar a new document must clear. WAND uses each term’s maximum possible score to skip documents that cannot reach the bar. Block-max WAND, from Ding and Suel’s 2011 paper, stores each 128-document block’s best term frequency and length pairs in the skip data, so whole blocks are skipped when even their best document cannot qualify. It arrived in Lucene 8.0 and Elasticsearch 7.0, with term queries 3 to 7 times faster on Lucene’s benchmarks. The price: total hit counts are no longer exact by default.

Distributed search: shards and query-then-fetch

An Elasticsearch index is split into primary shards, each a full Lucene index, and each primary has replicas that serve reads and take over on failure. A document’s shard is chosen by routing: a hash of the routing value, the document’s _id by default, modulo the number of primary shards. Because the modulus is fixed when the index is created, changing the shard count means building a new index, the same problem database sharding has with hash-mod placement.

A search can’t know which shards hold the best matches, so it runs in two phases.

In the query phase the coordinating node sends the query to one copy of every shard. Each shard matches, scores and returns only its local top from + size document IDs with their scores. The coordinator merges them into a global ranking. In the fetch phase it asks just the shards that own the winners for the stored documents. Shipping IDs first keeps the network cheap; a search is as slow as its slowest shard.

Two consequences matter in practice:

• Scores use local statistics. Each shard computes IDF from its own documents. With many documents spread by hash this barely matters, but small or skewed shards can rank the same document differently; dfs_query_then_fetch first gathers global term statistics, at the cost of a round trip.
• Deep pages are expensive. To serve results 9,991 to 10,000 from 5 shards, every shard returns its top 10,000 and the coordinator sorts 5 × 10,000 = 50,000 entries to keep 10. That is exactly where Elasticsearch’s default cap on from + size sits. Go deeper with search_after, passing the last hit’s sort values with a unique tiebreaker, plus a point-in-time so refreshes don’t shuffle pages: keyset pagination for search.

Shard sizing. Elastic’s guidance is shards of 10–50 GB with under 200 million documents each. Every shard costs memory and CPU, and each search runs one thread per shard, so a thousand 50 MB shards are far more expensive to search than one 50 GB shard. For a 600 GB index, 600 / 30 = 20 primaries of about 30 GB, or 40 shard copies with one replica each. Elasticsearch in depth goes further into running a cluster.

Beyond BM25: relevance tuning and hybrid search

BM25 is a strong baseline, not a finished ranking. Production search usually layers on:

• Field boosts. A match in the title counts, say, three times a match in the description.
• Business signals. Function scores blend in recency, popularity, stock or margin, typically with decay curves.
• Learning to rank. A cheap first pass retrieves a few hundred candidates; a trained model reorders just those using click and conversion features.

How these fit into a full pipeline is the subject of search end to end, and real systems are compared in search case studies.

Vector search catches what words miss: “something to wear for a haldi function” shares no terms with “yellow cotton kurta”. An embedding model maps text to dense vectors, and Lucene indexes them in an HNSW graph per segment for approximate nearest-neighbour search; see embeddings and semantic search and vector databases. Hybrid search runs BM25 and kNN side by side and fuses the two ranked lists. Reciprocal rank fusion adds 1 / (k + rank) for each list a document appears in, with k = 60 by default. A product ranked 1st by BM25 and 3rd by kNN scores 1/61 + 1/63 ≈ 0.0323; one ranked 2nd and 1st scores 1/62 + 1/61 ≈ 0.0325 and edges ahead. Ranks fuse cleanly even though BM25 scores and cosine similarities live on different scales.

Running search beside your primary database

The search index is a derived, eventually consistent view of data whose source of truth lives elsewhere. Treat it that way: never accept a write only in the search engine, and make sure you can rebuild every index from the primary database.

Dual writes drift. Writing to the database and then to Elasticsearch from application code looks simple, but if the process dies between the writes, or two updates race and arrive in the opposite order, the index silently diverges. Change data capture fixes both: a connector tails the WAL or binlog and publishes each committed change, in commit order per row, to a log such as Kafka; an indexer consumes it and upserts by primary key, passing the row’s version so the engine can reject stale updates that arrive late. A transactional outbox works when you want to publish shaped events rather than raw rows.

Freshness is a budget. A new product becomes searchable after CDC lag, plus the indexer’s batching delay, plus up to one refresh interval. Healthy, that is typically a second or two; during an incident lag is unbounded, so alert on it. For read-your-writes, show the seller’s own edit from the database, or index that one request with refresh=wait_for.

Reindex behind an alias. Changing an analyzer or a field type needs a new index, because existing segments were built with the old rules. Create products_v2 with the new mapping, record the change stream’s current position, backfill from a database snapshot, then replay the stream from that position until v2 catches up. Compare counts and sample queries, then repoint the alias with one aliases API call, which swaps atomically. Keep v1 for a day as your rollback.

Postgres full-text search or a search engine?

PostgreSQL has its own inverted index: a GIN index over a tsvector column stores each lexeme with a compressed list of matching rows. For many products that is enough, and it removes a cluster and a sync pipeline from your design.

A sensible path: start with Postgres FTS, measure, and move to a dedicated engine when ranking quality, typo tolerance, facets or query volume start driving the roadmap. Choosing a search engine walks through the options.

Failure modes in production

• Mapping explosions. Dynamic mapping turns every new JSON key into a field, and a feature that indexes arbitrary attributes can create thousands. Elasticsearch rejects new fields beyond a default limit of 1,000 per index; use explicit mappings or the flattened type for open-ended keys.
• Hot shards. Custom routing by seller puts a mega-seller’s whole catalogue, and its traffic, on one shard. Route large tenants across several shards, or give them their own index.
• Too many small shards. Daily indices with five shards each, kept a year, mean 1,825 tiny shards whose overhead eats the heap. Size by data volume, not by calendar.
• Deep pagination. Bots crawling page 900 hit the 10,000-result window and multiply shard work; use search_after and cap UI depth.
• Refresh and merge pressure. A bulk backfill with a 1 s refresh writes a stream of tiny segments that immediately need merging. For an initial load, disable refresh and replicas, then restore them, as Elastic’s indexing-speed guide recommends.
• Split brain in old clusters. Before Elasticsearch 7.0, a wrong discovery.zen.minimum_master_nodes setting could let two nodes act as master and lose writes; version 7 replaced it with automatic quorum management.

Cheat sheet

How to say it in the interview

“I’d keep products in Postgres as the source of truth and put Elasticsearch beside it for search. Titles and descriptions go through an analyzer, lowercasing, stemming and synonyms, into an inverted index: each term points to a compressed, sorted list of product IDs with frequencies and positions. A query intersects those lists, scores candidates with BM25, which favours rare terms and short fields, and keeps a top-k heap. Lucene writes immutable segments, so new products show up after the one-second refresh, and the translog makes acknowledged writes durable. Shards are about 30 GB; a query fans out to every shard for IDs and scores, then fetches only the winners. I feed it with CDC rather than dual writes, version every upsert, and reindex behind an alias.”

Why not just use LIKE or a B-tree index? A leading wildcard can’t use a B-tree, so every query scans the table, and even a trigram index gives no stemming, synonyms or relevance ranking. An inverted index makes query cost depend on how many documents contain the terms, not on table size.

Why is a new product not searchable immediately? Writes become visible only when a refresh turns the in-memory buffer into a searchable segment, every second by default, plus CDC and indexer lag. If a user must see their own write, read it from the database or index it with refresh=wait_for.

How do you change an analyzer on a live index? You can’t edit existing segments. Build a new index with the new mapping, backfill it from the database and replay the change stream, verify it, then swap the alias atomically and keep the old index as a rollback.

Where to go next

• Search data structures: inverted indexes, tries and more, in depth.
• Elasticsearch in depth: running and tuning the most common engine.
• Search end to end: from crawl to ranked results.
• Disk I/O and durability for search: how search engines use the disk and stay durable.
• How Google search works: crawling and ranking at web scale.
• Elasticsearch: the technology card for quick reference.
• Change data capture: keeping derived stores in sync.
• Design product search for an online store: putting it together in a design round.

References and further reading

1. Apache Lucene 10.0: Lucene912PostingsFormatlucene.apache.orgTerm dictionary and postings files, delta-encoded doc IDs bit-packed in blocks of 128 with VInt tails, and two-level skip data carrying impacts.
2. Elasticsearch documentation: Near real-time searchelastic.coPer-segment search, what a refresh does, and the 1-second default refresh for indices searched in the last 30 seconds.
3. Elasticsearch documentation: Translog settingselastic.coLucene commits versus the translog, flush, request versus async durability, the 5 s sync interval and the 10 GB flush threshold.
4. Apache Lucene 10.0: BM25Similaritylucene.apache.orgDefault k1 = 1.2 and b = 0.75, and the IDF formula Lucene uses.
5. The Probabilistic Relevance Framework: BM25 and Beyond (Robertson and Zaragoza, 2009)staff.city.ac.ukWhere BM25’s term-frequency saturation and soft length normalisation come from, and typical parameter ranges.
6. Magic WAND: Faster Retrieval of Top Hits in Elasticsearch (Elastic blog, 2019)elastic.coMAXSCORE, WAND and block-max WAND in Lucene 8.0 and Elasticsearch 7.0, their speed-ups, and why hit counts became approximate.
7. Elasticsearch documentation: Paginate search resultselastic.coWhy from and size get expensive across shards, the 10,000-hit window, search_after and point-in-time.
8. Elasticsearch documentation: Size your shardselastic.coThe 10–50 GB and 200-million-document guidance, per-shard overhead, one search thread per shard, and deleting indices rather than documents.
9. Elasticsearch documentation: Reciprocal rank fusionelastic.coThe RRF formula for combining BM25 and kNN result lists, and its default rank constant of 60.
10. PostgreSQL documentation: Preferred Index Types for Text Searchpostgresql.orgGIN as an inverted index over tsvector lexemes, lossy GiST signatures, and ranking that uses only local information.