Somewhere behind almost every search box you have ever typed into, a curious machine is at work. It takes in text, chops it into pieces, files every piece away in several filing systems at once, and then answers questions in milliseconds, best answers first. This essay follows one document into Elasticsearch and one query back out. Every figure is interactive; the essay works best if you play with all of them.
Everything begins with a document: a piece of JSON. Here is a log line from an imaginary payment service. It looks like one thing, but Elasticsearch will not store it as one thing. Guided by a schema called the mapping, each field's value is copied into one or more specialized structures, each built to answer a different kind of question. Hover over the fields:
text field is analyzed into the inverted index; a keyword like service is indexed whole and also columnar; numbers, dates and IPs get range trees; vectors join the neighbor graph.This is the first big idea, and it explains half of everything downstream: Elasticsearch pays generously at write time to make read time almost free. One incoming document might be written five different ways. That sounds wasteful until you remember the asymmetry of the workload: a log line is written once and queried, aggregated, sorted, and dashboarded thousands of times.
The mapping figure showed message going to the inverted index and service going there and to doc values. There is a deeper distinction hiding in that: a string can be indexed as text, analyzed into tokens for full-text search, or as a keyword, one exact opaque value for filtering, sorting and aggregating. They answer different questions, and choosing wrong is the most common mapping mistake there is:
message as text plus message.keyword alongside it.Let's follow the message field, mapped as text. Computers are poor readers; to a computer, payment, Payment, and payments are three unrelated byte sequences. So before text is indexed it passes through analysis, an assembly line that normalizes raw text into tokens. Edit the sentence:
standard analyzer only splits and lowercases; the english one also drops a short list of stop words and runs the Porter stemmer, whose stems need not be words: retrying becomes retri.The stages are humble: split on punctuation, lowercase, discard glue words, and trim words to a root so payments and payment collapse together (stemmers are blunt: paying becomes pai, and meets neither). Crucially, queries pass through the same pipeline, so document and query meet in the middle, in normalized token space. Elasticsearch ships dozens of analyzers, for English, Japanese, file paths, email addresses, and lets you compose your own from tokenizers and filters, including synonym filters that make error and failure meet in the middle too.
Tokens now need to be stored so they can be found without reading everything. Elasticsearch borrows the oldest trick in publishing, the index at the back of a book: precompute, for every token, the list of documents that contain it, called a postings list. Below, four documents and the real index built from them. Try the search box, and hover the index rows:
payment timeout, then checkout error, then Payments.Watch what the query actually does: it never reads a document. It looks up tokens, walks posting lists, intersects them. The documents are touched only at the very end, for display. The cost of search was paid when the index was built.
Real questions are rarely one word. They look like: messages matching "timeout", from the checkout service, slower than two seconds. Elasticsearch composes such questions with a bool query, and it draws a distinction that shapes everything about how the machine spends its effort: some clauses score, and some merely filter.
A must clause asks "how well does this match?" and contributes to relevance. A filter clause asks a yes/no question, contributes nothing to the score, and, because a yes/no answer never changes for a given segment, a filter that keeps coming back can be cached as a bitset and reused by later queries. Toggle the clauses:
This division of labor, cheap yes/no filters that never score, expensive scoring only for the survivors, is the quiet workhorse optimization of nearly every production query. The range filter, incidentally, is answered by the BKD tree from chapter one: numbers organized so that "≥ 2000" is a walk down a tree, not a scan.
Humans misspell. A search engine that returns nothing for paymnet has failed at its one job, so Elasticsearch can match terms approximately, within a budget of single-character edits (insertions, deletions, substitutions, and by default swaps of two neighbors), called edit distance. Type a misspelling:
AUTO, the usual setting: exact for words of one or two letters, one edit up to five, two beyond, because a typo budget that is generous on cat matches half the dictionary. The engine doesn't compare your word against each term one by one; it compiles your word into a small automaton and walks the term dictionary with it.The other human habit is not finishing words. Search-as-you-type works by indexing prefixes: at write time the term payment is also indexed as p, pa, pay, and so on, the familiar bargain of paying at write time, so that each keystroke is an ordinary exact lookup:
One thing the inverted index of chapter 4 quietly threw away: order. It knows which documents contain payment and which contain timeout, but "payment timeout" and "timeout before payment" are different facts. So the postings actually store more than document ids: they store positions, each term's spot in each document. A phrase query walks two posting lists at once and checks the arithmetic of positions; slop is the budget of moves it is allowed to spend making the positions line up:
Positions also help highlighting: once the engine knows where the match happened, carving the snippet around it is bookkeeping. Both cost index space, which is why positions are part of what a text field pays for and a keyword field doesn't.
The structures in this essay were drawn as ideas; they are also astonishing feats of engineering. How the term dictionary finds one term among millions, how posting lists compress, and how intersections skip: Inside the inverted index.
Matching is half the machine. What comes back must also come back in the right order: that is Ranking: the science of first. And everything indexed here got written fast thanks to segments.