Engineering Atlas › System Design Fundamentals

How full-text search engines work

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Analysis

Before anything is indexed, text is turned into terms. A typical English analyzer splits "Running shoes, size 10!" into run, shoe, size, 10: split on word boundaries, lowercase, drop punctuation, stem plurals and verb forms. Other choices include n-grams for partial matching, synonyms, and language-specific tokenizers for Chinese or Japanese, which have no spaces. The query must go through the same analyzer, or "shoes" will never match the indexed shoe.

The inverted index

For each term, the index stores a postings list: the ids of documents containing it, in ascending order, plus optional term frequencies and positions. Ascending doc ids allow delta encoding (store gaps, not ids) and compact integer compression, so a postings list often costs 1 to 2 bytes per entry. The term dictionary itself is stored as a compressed prefix structure (Lucene uses a finite-state transducer) so that looking up a term costs a few memory accesses.

A query running AND shoes becomes an intersection of two postings lists. Because both are sorted, intersection walks them together and uses skip pointers to jump ahead, so its cost is close to the length of the shorter list. Phrase queries additionally check that positions are adjacent.

Ranking with BM25

BM25 scores each matching document by summing, for each query term, an IDF weight times a saturating function of term frequency (Robertson and Zaragoza, 2009):

Elasticsearch and Lucene default to k1 = 1.2 and b = 0.75 (Elasticsearch docs). Not every engine ranks this way: Postgres's ts_rank and ts_rank_cd use no corpus-wide statistics at all, so a rare term counts no more than a common one (Postgres docs).

Production relevance layers more on top: field boosts (title over body), freshness, popularity, personalization, and often a learned re-ranker or vector similarity applied to the top few hundred candidates. When keyword and vector results are merged, reciprocal rank fusion is the usual first step: each list contributes 1/(60 + rank), so no score calibration is needed (Cormack et al., SIGIR 2009).

Segments, refresh, and merges

Lucene does not update an index in place. New documents are buffered in memory and written as a small immutable segment on refresh. Elasticsearch defaults to every second (5 seconds on Elastic's Serverless offering), but a shard that has not been searched for 30 seconds stops refreshing in the background until the next search arrives (Elasticsearch docs). A search queries every segment and combines results. Deletes are recorded as bitmaps, and an update is a delete plus an add. A background merge policy combines small segments into larger ones, purging deleted documents. A separate translog provides durability between full commits.

This is the same immutable-files-plus-compaction idea as an LSM tree, and it carries the same costs: merge I/O, temporary disk overhead, and a short visibility delay.

Distribution

A cluster splits an index into shards, each a full Lucene index. A query fans out to one copy of every shard, each returns its top k, and a coordinator merges them. The primary shard count is set at index creation in Elasticsearch. The split API can multiply it, but only by copying into a new index while the source is read-only (Elasticsearch docs), so oversharding (thousands of tiny shards) and undersharding (shards that take hours to recover) are both common mistakes. Elastic's guidance is 10 to 50 GB and under 200 million documents per shard, well below Lucene's hard cap of about 2.1 billion documents, deleted ones included (Elasticsearch docs).

Down the stack

Layer 1The contract

Elasticsearch on Lucene promises two different things at two different times. A document is durable when the index call returns, because with the default index.translog.durability: request the translog is fsynced on the primary and every allocated replica before the acknowledgement (Elasticsearch docs). It is searchable only after the next refresh, by default within about a second on an active index. Results are the top k by score, but scores are computed per shard: IDF comes from each shard's own statistics, so the same document can rank differently on different shards unless you pay for dfs_query_then_fetch.

Layer 2The mechanism

A Lucene segment is a set of write-once files. The term dictionary lives in .tim, indexed by an FST in .tip small enough to keep in memory. Each term entry points into .doc (doc ids and term frequencies), .pos (positions for phrase queries), and .pay (offsets and payloads). Stored fields (.fdt) and column-oriented doc values (.dvd) sit alongside, and .liv is a bitmap of live documents, which is how deletes work without rewriting a segment. A segments_N file is the commit point listing the segments that make up the index.

Postings are encoded in blocks of 128 doc ids. Within a block, ids are delta encoded and then bit-packed with the minimum width that fits the largest delta, and a short tail is written as variable-length integers. Skip data lets advance(target) jump over whole blocks during an intersection without decoding them. Older formats kept it in a separate multi-level skip list; the current Lucene 10 format interleaves it with the postings in two levels, one entry before every 128-doc block and another every 32 blocks (4,096 docs), each holding the doc delta, file pointers and, since Lucene 8, impacts: the competitive term frequency and norm pairs for that range (Lucene docs). Block-max WAND uses them to compute an upper bound on any document's score in a block and skips blocks that cannot beat the current *k*th best result.

Layer 3The machine

Lucene opens index files with MMapDirectory on 64-bit platforms, so reading a postings block is a memory access into the page cache rather than a read() syscall. That is why Elasticsearch guidance is to give the JVM heap at most about half the RAM, and to stay below roughly 31 GB so the JVM keeps compressed object pointers, leaving the rest to the OS to cache index files. A cold index costs page faults and random reads; a warm one is bound by memory bandwidth.

Bit-packed blocks of 128 are chosen for the CPU. Decoding a fixed-width block is a branch-free loop the JVM can vectorise, and 128 ids at a few bits each fit in a handful of 64-byte cache lines. Refresh writes a new segment into the page cache without fsync, which is why it is cheap enough to run every second. A Lucene commit (an Elasticsearch flush) fsyncs segment files and writes a new segments_N, after which the translog can be trimmed. Merges rewrite whole segments sequentially; the default tiered merge policy caps merged segments at about 5 GB.

Why it's built this way

  1. Text queries are intersections and unions of term lists, so the index is inverted by term and kept sorted by doc id.
  2. Sorted ids have small gaps, so delta encoding plus bit-packing shrinks postings to a few bits per entry and lets more of the index live in RAM.
  3. Rewriting compressed sorted lists in place is impractical, so new data goes into new immutable segments and merges clean up.
  4. Fsyncing a segment every second is too expensive, so visibility (refresh) is separated from durability (translog and commit).
  5. Most queries need only the top results, so per-block score bounds let the engine skip data instead of scoring every match.

Diagram

flowchart LR
    D["Document"] --> A["Analyzer (tokenize, lowercase, stem)"]
    A --> B["In-memory buffer"]
    B -->|refresh| S1["Segment 1"]
    B -->|refresh| S2["Segment 2"]
    S1 --> M["Background merge"]
    S2 --> M
    M --> S3["Merged segment"]
    Q["Query"] --> QA["Same analyzer"]
    QA --> P["Postings lookup + intersect"]
    S3 --> P
    P --> R["BM25 rank, top k"]

Worked example

A marketplace indexes 50 million product listings, averaging 2 KB of text each, about 100 GB of source. After analysis, the inverted index plus stored fields and doc values comes to roughly 60 to 80 GB per copy. With one replica, that is 150 GB, which the team splits into 6 primary shards of about 12 GB each, small enough to relocate in minutes.

Peak traffic is 3,000 queries per second. Each query hits all 6 shards, so the cluster serves 18,000 shard-level searches per second. If one shard search takes 8 ms of CPU, that is 144 CPU-seconds per second, so about 12 nodes with 16 cores at 75% utilization. Adding shards would not add capacity here; adding replicas would, because each replica serves reads.

Indexing runs at 2,000 updates per second. With a 1-second refresh, each shard creates a new small segment every second, and merges rewrite each document several times over its life. Raising refresh to 5 seconds for the catalogue cuts segment churn sharply, while order-status search, which needs near-instant visibility, stays in a separate index with a 1-second refresh.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Elasticsearch or OpenSearchMature relevance, aggregations, horizontal scaleOperational load, JVM tuning, eventual visibilitySearch is a core product feature
PostgreSQL full-text (GIN index)No new system, transactional consistencyWeaker ranking, slower at large scaleUnder tens of millions of rows, modest relevance needs
Hosted search APIFast to ship, no cluster to runCost per query, less controlSmall team, standard needs
Vector search aloneFinds semantic matches without shared wordsMisses exact identifiers, SKUs, namesCombined with keyword search in a hybrid
Short refresh intervalNear-real-time visibilityMore segments, more merge I/OUser expects to search what they just wrote

Pitfalls in production

Leadership lens

Check yourself

  1. Why are postings lists stored in ascending doc-id order?

    Show answer

    Sorted lists compress well as gaps and can be intersected in linear time with skip pointers.

  2. A newly indexed document does not show up for about one second. Why?

    Show answer

    Documents become searchable only when a refresh writes the in-memory buffer as a new segment, which happens on an interval.

  3. Why does BM25 score a match in a short document higher than in a long one?

    Show answer

    Length normalization assumes a term in a short text is a larger share of its content, so it signals relevance more strongly.

  4. Adding shards does not raise query throughput. What does, and why?

    Show answer

    Adding replicas, because every query already hits every shard; more replicas spread those shard searches over more nodes.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →