Zalando search fundamentals: Lucene and Elasticsearch 12 questions in 4 chapters

Instead of storing each document's words, an inverted index maps each term to the documents that contain it, often with frequencies and positions. A query looks up its terms and combines their postings lists instead of scanning documents. Lucene writes it as immutable segments, each with a terms dictionary, postings, stored fields, doc values and a live-documents file for deletes.

Postings are sorted by document ID, so AND is a merge-like intersection: compare the heads, advance the smaller one, keep matches. Start with the rarest term so the candidate set shrinks fast. OR is a merge that keeps every ID once. Skip pointers let AND jump ahead in long lists, and phrase queries also need positions, not just document IDs.

Analysis turns text into the terms that are indexed and searched: character filters clean the text, a tokenizer splits it, and token filters lowercase, stem, remove stop words or add synonyms. A query only matches if it produces the same terms as the document did, so the analysis at index time and search time must be compatible. Stemming and synonyms raise recall but can hurt precision.

A finite-state transducer is a compact automaton that maps keys to outputs. It shares common prefixes and suffixes, so a large sorted set of terms fits in little memory. Lucene's BlockTree terms dictionary groups terms into blocks by shared prefix and keeps that prefix trie in memory as an FST, which points to the right block on disk.

BM25 scores a document for each query term from three things: how rare the term is, how often it appears in the document, and how long the document is. Unlike raw TF-IDF, repeated occurrences saturate, so the tenth mention adds little, and long documents are normalised. In Lucene, k1 controls the saturation and b the length normalisation, defaulting to 1.2 and 0.75.

A clause in query context contributes to the relevance score. A clause in filter context only decides yes or no and is not scored. Exact constraints such as size, brand, in stock or price range belong in filters. They skip scoring, Elasticsearch can cache frequently used filters, and they keep the score about text relevance rather than about whether a filter matched.

Keep a min-heap of size K while iterating matches: compare each score with the smallest in the heap and replace it if larger. That costs n log K instead of n log n and needs memory only for K. Search engines go further and skip documents that cannot beat the current Kth score, using per-block maximum scores, so many matches are never fully scored.

First I separate matching from ranking. If the product does not match, I check analysis with the analyze API, the mapping, and any filters or redirects that excluded it. If it matches but ranks low, I read the explain output to see which clauses, field weights and term statistics produced the score, then look at boosts and later ranking stages. I fix the cause and add the query to a judgment set.

A segment is an immutable mini index written once. Lucene never edits it: an update writes a new version of the document into a new segment and marks the old one deleted in the live-documents bitset. Searches read every segment and skip deleted documents. Background merges combine small segments into larger ones and drop deleted documents, which costs I/O and CPU.

New documents become searchable only after a refresh opens a new segment, which by default happens every second, but only for indices searched in the last thirty seconds. A flush is about durability: it commits segments to disk and trims the translog. Refreshing more often makes updates visible sooner but creates more small segments and merge work, so bulk loads often relax it.

An index is split into primary shards, and each document lives on one of them. A search without routing goes to one copy of every shard, each shard scores locally, and the coordinating node merges the top hits and then fetches the documents. Replicas add read capacity and availability but cost disk and indexing work. Too many small shards adds overhead to every query.

Less than you might think. Elastic's guidance is to set the minimum and maximum heap equal, at no more than half the node's memory, and below the compressed object pointer threshold, which is about 26 gigabytes on most systems. Lucene reads its immutable segment files through memory mapping, so the rest of the memory serves as the operating system's file cache, which is what keeps searches fast.