Three plain ideas, put together: a term, a document, and a list. Once each is clear, the rest follows naturally.

Elasticsearch stores documents, such as product descriptions, news articles, or log lines. When a text document arrives, Elasticsearch runs it through an analyzer, which cuts the text into small pieces called terms. Roughly speaking, a term is a word that has been cleaned up: lowercased, stripped of punctuation, and sometimes reduced to its root form. The sentence “The Quick Brown Fox” might become the terms “the”, “quick”, “brown”, and “fox”.

For every distinct term, the index keeps a list of the documents in which that term occurs. That list is the postings list of the term. Each entry in the list is called a posting. At its simplest, a posting is just the number of a document. In richer forms, a posting also says how many times the term occurs in that document, and at which positions.

The collection of all terms, each with its postings list, is called an inverted index. It is “inverted” because a normal document is a list of words, while this structure turns things around: it is a list of words, each pointing back to documents. When you search for “fox”, Elasticsearch does not scan documents. It looks up the term “fox” in the sorted dictionary of terms, follows the pointer to its postings list, and reads off the documents.

What it is not

A postings list is not the document itself. The original text lives in a different structure, the stored fields, from which Elasticsearch builds the source you see in results. It is not the structure used for sorting and grouping either, which is a column-style structure called doc values. And it is not the structure used for numbers and dates, which are stored in a special tree for fast range checks. The postings list has one job: to answer, quickly, which documents contain a given term. Chapter 8 shows how these structures sit side by side.

The one-sentence version

If you remember one line from this chapter, make it this: a postings list is the sorted list of documents, inside one segment, that contain a particular term, optionally carrying how often and where the term appears, and it is the data structure that makes full-text search fast.

Every data structure is born from a painful problem. The problem here is that reading everything is far too slow.

Suppose you keep a hundred million documents, and a user searches for the word “volcano”. The simplest approach is to open every document and check whether it contains that word. This is called a full scan. If each document takes a microsecond to check, the scan takes a hundred seconds. And that is for one word, for one user, on one machine. With thousands of users searching at once, the approach collapses.

The inverted index changes the arithmetic. Instead of checking every document, it goes straight to the word. Finding the word in the sorted dictionary takes a few steps, because the dictionary is organized so that a lookup skips most of it. Reading the postings list costs time only in proportion to the number of documents that match, not the number that exist. If only a few thousand documents mention “volcano”, then only a few thousand entries are read. The cost is tied to the answer, not to the size of the collection.

A short history

The exact release for each step is worth double-checking in the release notes of your version. The direction of travel is what matters: the idea stayed the same, while the encoding became smaller and the reading became smarter.

Two ways to organize the same information

To see why the inversion matters, compare two views of the same three short documents. In the forward view, each document lists its words. In the inverted view, each word lists its documents. If you want to know “which documents contain brown?”, the forward view forces you to read every document. The inverted view gives you the list at once. The forward view is good for showing a whole document, and the inverted view is good for finding documents. Search needs the second, and Elasticsearch stores both, each in its own structure.

Why not a database index on the text?

An ordinary database index on a text column stores the whole value in a sorted tree. It answers “find rows where the column equals this exact value” very well, but it cannot answer “find rows where the text contains this word” without scanning. Full-text search needs an index built from the words inside the text, and that is exactly what postings lists provide.

A dozen words explain nearly everything about postings lists. Learn them here, and later chapters will read like common sense.

The unit of storage: the segment

Every shard is made of segments, small sealed sets of files that are never changed after they are written. Postings lists live inside a segment. This means that a term such as “fox” has not one postings list per shard but one per segment, each listing only the documents of that segment. When new documents arrive, they land in a new segment with its own fresh lists. When segments are merged, their lists are combined into new ones. The whole life of a postings list is tied to the life of its segment.

Document IDs are local and small

Inside a segment, documents are numbered from zero upward, in the order they were added. These numbers are what postings lists contain. They are small whole numbers, because a segment holds at most a couple of billion documents, and typically far fewer. They are local: document number 7 in one segment has nothing to do with document number 7 in another. They are also temporary in a sense: when segments are merged, the surviving documents are renumbered. The identifier you see in results, the _id, is a different, permanent thing, stored separately.

Frequency versus position

These two details are often confused. Term frequency answers “how many times does the term appear in this document?” Position answers “where, exactly, does it appear?” Frequency is a single small number per document. Positions are a list of numbers per document, and therefore cost far more space. Frequency helps scoring. Positions help phrase and proximity searches. Whether they are stored is a choice you make in the mapping.

Quick glossary

Where do postings lists come from, where do they live, and which parts of Elasticsearch and Lucene work together to build and use them?

A document that arrives at Elasticsearch travels through several stages before its words end up in postings lists. The analyzer cuts its text into terms. The indexing machinery of Lucene collects those terms in memory, building lists as it goes. When it is time to write, the collected data is sorted and saved as a new segment. From then on, the segment holds a term dictionary, the postings lists, and several neighbor structures, all sealed and read-only.

flowchart TB
    Doc["Document arrives"] --> An["Analyzer: splits text into tokens and cleans them"]
    An --> IC["Indexing chain: builds postings in memory"]
    IC --> Ref["Refresh or flush writes a new segment"]
    subgraph Seg["One segment on disk"]
        TD["Term dictionary: sorted terms with statistics"]
        PL["Postings lists: doc ids, frequencies, positions"]
        NR["Norms: field length information"]
        DV["Doc values and stored fields: other structures"]
    end
    Ref --> Seg
    TD -->|points to| PL
    

Read the picture from top to bottom. The analyzer is the front door: it decides what the terms are, and therefore what postings lists will exist. The indexing chain gathers terms and grows lists in memory. A refresh, or a flush when the memory buffer is full, turns the gathered data into a segment. Inside the segment, the term dictionary is a sorted directory of terms, and each entry points to a postings list. Norms, doc values, and stored fields sit beside them, serving other purposes.

The main components

One set of lists per field

Terms are kept separately for each field. The word “apple” in a title field and the word “apple” in a description field are two different entries in two different dictionaries, each with its own postings list. This is why a query names a field, and why adding more fields to your mapping increases the number of lists, and the size of the index.

Walking one search through the machine

Now we open the list and look at each part. A small example makes it concrete.

Take three tiny documents. Document 0 says “quick brown fox”. Document 1 says “lazy brown dog”. Document 2 says “quick brown cat”. After analysis, the index holds the terms shown in the picture below, each pointing to its list of documents.

flowchart LR
    T1["Term: brown"] --> P1["Postings: doc 0, doc 1, doc 2"]
    T2["Term: quick"] --> P2["Postings: doc 0, doc 2"]
    T3["Term: fox"] --> P3["Postings: doc 0"]
    T4["Term: dog"] --> P4["Postings: doc 1"]
    T5["Term: lazy"] --> P5["Postings: doc 1"]
    T6["Term: cat"] --> P6["Postings: doc 2"]
    

The term dictionary keeps terms in alphabetical order: brown, cat, dog, fox, lazy, quick. The list for “brown” has three postings, because the word appears in all three documents. The list for “fox” has one. The number of postings in a list is the term’s document frequency. A search for “quick brown” needs the lists for “quick” and “brown”, and asks which documents appear in both: documents 0 and 2.

What one posting can contain

In its simplest form, a posting is only a document number. Depending on how the field is mapped, it can carry more.

A richer example with positions

Now consider a document that says “the quick brown fox jumps over the lazy dog”. Counting from zero, the term “the” is at positions 0 and 6, “quick” at position 1, “brown” at position 2, “fox” at position 3, and so on. If the field stores positions, the posting for “the” in this document says: term frequency two, positions 0 and 6. A phrase search for “quick brown” finds documents that contain both terms and then checks that the position of “brown” is exactly one more than the position of “quick”. Here, positions turn a simple “both words appear” into “the words appear next to each other, in order.”

Statistics kept with each term

Besides the list, the dictionary entry for each term stores a few numbers. The document frequency is the number of documents in the list. The total term frequency is the sum of the term frequencies across all documents, meaning how many times the term occurs in the whole segment. These numbers are cheap to read, and they feed scoring: a term that appears in nearly every document says little about relevance, while a rare term says a lot.

The shape of real lists

In real text, the sizes of lists are very unequal. A tiny number of words, such as “the” and “and”, occur in nearly every document, so their lists are enormous. A great many words occur in only one or two documents, so their lists are tiny. This pattern, sometimes called Zipf’s law, is one of the most important facts about postings lists. It explains why some queries are cheap and others are costly, and why removing or handling very common words matters.

Sorted order is the secret

The document numbers in each list are always in increasing order. This is not an accident. It makes two very important things possible. First, numbers can be stored as small differences from one to the next, which compresses well, as Chapter 7 shows. Second, two lists can be combined by walking them side by side, like zipping two sorted rows, instead of comparing every pair. Nearly every clever thing that Lucene does with postings depends on this one rule.

Postings lists are not typed by anyone. They grow, in memory, as documents flow through the analyzer. Here is how.

flowchart LR
    A["Tokens from analysis"] --> B["In-memory table of terms with growing lists"]
    B --> C{"Buffer full or refresh due?"}
    C -- No --> B
    C -- Yes --> D["Sort the terms alphabetically"]
    D --> E["Write term dictionary and postings files"]
    E --> F["New immutable segment, ready to search"]
    

Step one: analysis

The journey starts with the analyzer. It cuts the text into tokens, and each token receives a position, a counter that goes up by one for each token. Filters then transform the tokens: they lowercase them, remove stop words, reduce words to stems, or add synonyms. Whatever comes out at the end of this chain is the set of terms that will get postings. The analyzer is therefore the most powerful control you have over the shape of the index, because it decides what the vocabulary is.

Step two: growing lists in memory

As tokens arrive, Lucene keeps, for each field, an in-memory table from terms to growing lists. When a term is seen for the first time in a document, a new entry is created, and the document number is added to its list. When the same term appears again in the same document, its frequency is increased and the new position is added. When the next document arrives, and contains the same term, its number is appended. Because documents are numbered in the order they arrive, each list is naturally in increasing order without any extra sorting.

Step three: writing a segment

When the memory buffer fills up, or when a refresh happens, Lucene writes the collected data to disk as a new segment. At this point, it sorts the terms alphabetically, writes the term dictionary in sorted order, and writes each term’s list, in compressed form, to the postings files. The segment is then sealed. From this moment, its lists are read-only.

How positions are counted

Positions are more subtle than they look. Each token normally advances the position by one. But some filters change this. If a stop word is removed, the analyzer still leaves a gap where it was, so that the positions of the remaining words stay true to the original text. Synonyms are placed at the same position as the word they stand for, so that a phrase search works with either word. And when a field holds several values, such as an array of strings, Elasticsearch inserts a gap of a hundred positions between the values by default, so that a phrase search does not accidentally match words from the end of one value and the start of the next.

The cost of building

Building postings is real work. Analysis uses processor time, growing lists use memory, sorting and compressing use more processor time, and writing uses disk. This is why heavy text fields make indexing slower than light ones, and why choices such as storing positions, or applying n-grams, show up directly in indexing throughput and in the size of the index.

See what the analyzer produces

Elasticsearch has an analysis endpoint that shows the terms and positions that a piece of text would produce under a given analyzer. It is the best way to understand why a document does or does not match a query, because the match happens between the terms of the query and the terms in the postings, not between the raw words.

A postings list can have millions of entries. Storing it compactly, and reading it quickly, is where much of Lucene’s cleverness lies.

flowchart TD
    Q["Look up a term"] --> FST["Term index in memory: finds the right block of the term dictionary"]
    FST --> TB["Term dictionary block on disk: finds the term and its statistics"]
    TB --> PP["Pointers to postings, positions, and skip data"]
    PP --> DB["Document number blocks of 128, packed with few bits each"]
    PP --> SK["Skip data: jump ahead over blocks"]
    PP --> PS["Positions read only if the query needs them"]
    

Finding the term

The term dictionary of a segment is stored in sorted order, in blocks of terms that share a common beginning. A small index on top of the blocks, held in a very compact structure called a finite state transducer, lets Lucene find the right block for a given term in a handful of steps, without reading the whole dictionary. Once the block is read from disk, the term itself is found, and with it, its statistics and its pointers into the postings files. This design keeps the part that must be in memory small, even when the number of terms is huge.

Squeezing the document numbers

The first trick is delta encoding. Because the numbers in a list are sorted, each can be stored as the difference from the previous one, instead of as a whole number. A list of document numbers 3, 7, 8, 15, 20 becomes the differences 3, 4, 1, 7, 5. The differences are small numbers, and small numbers need few bits.

Blocks and bit-packing

The second trick is to store the list in blocks of a fixed size, 128 postings in current formats. For each block, Lucene finds the largest difference in the block and works out how many bits are needed to write the biggest one. Then every difference in that block is written using exactly that many bits, packed tightly next to each other. If the biggest gap in a block is 30, five bits are enough for each entry, so 128 entries take 80 bytes, instead of hundreds of bytes in plain form. Fixed-size, bit-packed blocks are also very fast to decode with modern processors. Frequencies are packed in a similar way.

A numbers walkthrough

Let us use invented numbers. Suppose a common term appears in one million documents of a segment with ten million documents. On average, the gap between consecutive documents in its list is about ten. A gap of ten fits in four bits, though a few larger gaps make some blocks need five or six bits. Plain, each posting would need four bytes, so the list would take four megabytes. With delta encoding and bit-packing at about five bits per posting, the same list takes roughly 600 kilobytes. That is a saving of nearly seven times, and the saving is even bigger for very dense lists, where the gaps are tiny.

Skip data

When a search needs to jump, for example to the first document at or after number 5,000,000, reading every posting from the start would be wasteful. So along with the list, Lucene stores skip data: for each block, the last document number in it and where the block starts on disk, with higher levels that summarize groups of blocks. A reader looks at the skip data first, jumps to the right block, and decodes only that block. This is like the tabs on the side of a directory, and it makes the “advance to document X” operation cheap even on lists with millions of entries.

The files

Memory and the operating system

Postings files are read through the operating system’s file cache, by mapping them into memory. That is why Elasticsearch performs best when a good part of the machine’s memory is left to the operating system rather than given entirely to the Java heap. Frequently read lists stay in the cache, and the disk is touched only for the cold parts. The small in-memory index over the term dictionary has historically lived in memory too, and newer versions may read it through memory mapping instead, so check the notes for your version.

Not every field has a postings list, and not every postings list stores the same details. The mapping decides.

The choices for text fields

For fields that hold text, a mapping option chooses how much detail the postings store. The choice is a trade between features and size.

Different field types, different structures

A common confusion is to assume that every field is stored as a postings list. It is not. Elasticsearch uses several structures, and each field type picks the ones it needs.

Why numbers do not use postings

A postings list is excellent for finding documents with a specific term. But a question such as “price between 20 and 50” would need to look at every distinct price value between the two and combine all their lists, which is slow. For numbers and dates, Lucene therefore uses a different structure, a tree built to answer range questions quickly. A search for one exact number also uses that tree. So do not expect to see a postings list for an integer field, and do not choose an integer type for identifiers that you only ever match exactly. A keyword field, which does use a postings list, is usually the faster and more natural choice for such values.

Keyword fields: one term per value

A keyword field does not split its value. The whole value, such as a country code or a status, is one term. The postings list of that term names all documents with that value. For low-cardinality fields, such as status, the lists are long and few. For high-cardinality fields, such as user identifiers, the lists are short and many, and the dictionary becomes large. Both work, but the shape differs, and so does the cost.

Norms: length information beside the lists

Norms are not part of the postings, but they travel with them. For each document and each scored field, the index stores one small number that encodes the field length. It lets scoring treat a match in a short title as more significant than the same match inside a long body. Norms take about one byte per document per field. For fields that are never scored, such as filters, turning norms off saves space.

Options that add extra lists

How to choose

A search is, at heart, a small program that walks and combines lists. Understanding the walk explains why some queries are fast and others slow.

The iterator

To read a list, Lucene creates an iterator. It has two main abilities. It can move to the next document in the list. And it can advance to the first document at or after a given number, using the skip data to jump over stretches it does not need. These two abilities are enough to build every kind of query.

Requiring several terms: the leapfrog

Suppose a query requires documents that contain both “quick” and “brown”. Both lists are sorted. Instead of comparing every pair, Lucene picks the list that is expected to be shortest as the lead. It takes the lead’s first document, and asks the other list to advance to that document. If the other list lands exactly on it, the document is a match. If the other list lands on a later document, that later number becomes the new target, and the lead advances to it. The iterators leapfrog over each other until one is exhausted.

flowchart TD
    A["Start with the rarest term as the lead iterator"] --> B["Take its next document"]
    B --> C["Ask the other terms to advance to that document"]
    C --> D{"Do all terms land on the same document?"}
    D -- Yes --> E["Match: record the document"]
    D -- No --> F["Use the largest document seen as the new target"]
    E --> B
    F --> C
    

Why the rarest term leads

The lead iterator walks its entire list. Every other iterator only needs to jump. So choosing the shortest list as the lead minimizes the number of steps. A query for a rare word and a common word is therefore cheap: it walks the short list and jumps through the long one. A query for two common words is costly, because even the shortest list is long. This is one reason that combining a rare term with a common one is much cheaper than combining two common ones.

Alternatives and exclusions

When a query asks for documents that contain either of several terms, Lucene walks all the lists at once, always moving on the list whose current document is smallest, so that each matching document is visited once. When a query excludes documents that contain a term, the list of that term is used as a filter that rejects matches. Both operations rely on the sorted order of the lists.

One document at a time

Lucene evaluates queries by going through documents in increasing order, and for each candidate document, finding out which terms match and computing its score, before moving to the next. This document-at-a-time style works well with sorted lists, keeps memory use small, and lets the search stop early when it has enough results. The alternative, term-at-a-time, would process one whole list before the next and needs a table of partial scores for all documents, which is heavy for large indexes.

Phrase searches use positions

A phrase search, such as “quick brown”, first finds documents where both terms appear, using the leapfrog. Only for those candidate documents does it read the positions data, and check whether the positions line up. This two-step approach keeps position reading, which is expensive, to a minimum. It also explains why phrase searches are slower than plain term searches, and why fields that never need phrase matching should not store positions.

Filters and caching

Filters, meaning yes-or-no conditions that do not need scores, are handled like any other list, but with a difference: the result can be remembered. Elasticsearch has a query cache that stores the set of matching documents of costly, repeated filters per segment, so that the postings lists behind them do not need to be walked again. This connects the two subjects: postings lists are the raw material, and the query cache is a shortcut for the lists that are read again and again.

Every segment, every time

A search must visit each segment of each shard it covers, since each has its own lists. A shard with many small segments needs many dictionary lookups and many small list reads. A shard with a few large segments needs fewer, larger reads. This is a large part of why heavy write activity, which creates many small segments, can slow searches until merging tidies up.

Finding matching documents is only half of search. The other half is ranking them, and postings supply most of the numbers for that.

The ingredients of the score

The default ranking formula in Elasticsearch is called BM25. It combines a few quantities, and most of them come straight from postings and their neighbors.

Statistics are per shard

By default, the document frequency and other statistics used in scoring are taken from the shard that holds the document, not from the whole index. For big indexes with evenly spread data, the numbers are close enough and nobody notices. For small indexes, or unevenly spread data, the numbers may differ noticeably between shards, and the same document may score differently depending on where it lives. A search mode exists that first collects statistics from all shards and then scores, at the price of an extra round trip.

The cost of scoring long lists

Consider a search for “the quick brown fox”. The word “the” has a list of millions of entries, and it contributes almost nothing to relevance. A naive engine would still score every document in that list. This is wasteful, because most of those documents will never reach the top ten. The cleverness of modern Lucene lies in avoiding it.

Block-max skipping

For each block of 128 postings, Lucene stores a summary of the best score that any document in that block could achieve for the term, based on the largest frequencies and shortest lengths inside it. While collecting the top results, the search keeps track of the lowest score among the current best ones. Before scoring a block, it asks: even if a document in this block had the highest possible score for each of its terms, could it beat the current lowest? If not, the whole block is skipped without decoding or scoring a single document.

flowchart TD
    S["Keep the top k documents so far and their lowest score"] --> B{"Can the next block of postings beat the lowest score?"}
    B -- No --> K["Skip the whole block without scoring"]
    B -- Yes --> C["Score the documents in the block"]
    C --> U["Update the top k"]
    K --> N["Move to the next block"]
    U --> N
    N --> S
    

The price: approximate counts

Skipping means that the search does not look at every matching document. As a result, it cannot say exactly how many documents matched. By default, Elasticsearch counts accurately only up to a threshold, ten thousand hits, and after that reports a lower bound with a note that the total is “at least” that number. If you need the exact total, you can ask for it, but then the skipping must be turned off, and the search reads far more of the lists. For most user-facing search, the lower bound is fine, and the speed gain is large.

A numbers walkthrough

Suppose a search has one common term with a list of five million documents and one rare term with a list of two thousand. Without skipping, a “match any” search would score up to five million documents. With block-max skipping, once the top ten documents have been found among those that contain the rare term, the lowest score among them is high. Blocks of the common term’s list that cannot reach that score are skipped entirely. In practice, only a small fraction of the long list is actually decoded. The figures are invented, but the effect is real, and it is why modern Elasticsearch handles common words far better than older versions did.

Postings lists are sealed and never edited. Yet documents change all the time. Here is how the two facts live together.

flowchart LR
    W["New documents"] --> R["Refresh: new small segment with its own postings"]
    R --> M["Merge: postings of several segments combined and document numbers renumbered"]
    M --> B["Larger segment with fewer, longer lists"]
    D["Deleted or updated documents"] --> L["Marked in a live-documents bitmap"]
    L --> M
    

New documents: new lists

Each refresh writes the documents indexed since the last refresh into a new segment, with a complete little inverted index of its own. Existing segments are untouched. That is why new documents can become searchable quickly and cheaply: nothing has to be edited, only added. The price is that the shard now has one more segment, with its own lists, that every search must visit.

Deletes and updates: marking, not editing

Because lists cannot be edited, deleting a document does not remove its number from any list. Instead, the segment keeps a separate bitmap of live documents, and the deleted one is marked as gone. At search time, matches are checked against this bitmap and skipped if deleted. An update is treated as a delete of the old version and an add of the new one, in a newer segment. The old version lingers in the old segment’s lists until a merge removes it.

Merging: rewriting lists into bigger ones

In the background, Elasticsearch merges segments. The merge policy chooses several segments of similar size, and a merge process reads their term dictionaries together, in sorted order. For each term, it takes the lists from each input segment and combines them into one new, longer list. Along the way, it drops the postings of deleted documents and renumbers the surviving documents, so that the numbers in the new segment run from zero without gaps. Then it writes the new segment and, when it is ready, replaces the old ones.

What merging changes

Deleted documents still count, for a while

A subtle consequence is that the statistics stored with each term, such as its document frequency, keep counting deleted documents until a merge. This slightly distorts scoring in indexes with many recent deletes or updates. It usually goes unnoticed, but it can explain small scoring differences between a freshly merged index and a busy one.

Force merge for finished data

For an index that will not receive writes anymore, such as last month’s logs, you can ask for a force merge down to a small number of segments. This produces the most compact lists and the fastest searches. It is expensive, and it should only be done on data that is truly finished, because merging an index that still receives writes creates very large segments that are costly to keep tidy.

Index sorting and list compression

By default, documents are numbered in the order they arrive. An optional index setting can sort the documents inside each segment by a chosen field. Documents with similar values then get neighboring numbers, and their postings lists contain runs of close numbers, which compress better and allow some searches to stop early. The cost is slower indexing and merging, so use it only when a specific, frequent search pattern benefits.

A plain term query reads one list. Some queries read hundreds or thousands. Knowing how they work helps you avoid nasty surprises.

Expanding a pattern into terms

A query such as “words starting with quick” does not correspond to one term. It corresponds to every term in the dictionary that starts with those letters: quick, quickly, quicker, quicksand, and possibly hundreds more. Lucene first walks the sorted term dictionary to find all matching terms. Then it combines the postings lists of all of them, as an “any of these” query. The work is therefore the cost of finding the terms plus the cost of reading every one of their lists.

How each kind of pattern behaves

Why leading wildcards hurt

The dictionary is sorted by the beginning of terms. A pattern that starts with a fixed piece can use this order to jump close to the right region. A pattern that starts with a star, such as “anything followed by fox”, cannot jump anywhere, because matching terms may be scattered throughout. Lucene must test every single term. On a dictionary with tens of millions of terms, this can take a long time. This is the most common way people accidentally build slow queries.

Combining many lists

Once the matching terms are known, Lucene has to combine their lists. If there are only a few terms, it treats the query as a scored “any of these.” If there are many, it takes a shortcut: it reads all their lists once, builds a single set of matching documents, and uses that set as a constant-score filter. This avoids enormous scoring work, at the price of giving all matches the same score. The switch happens automatically according to the number of terms.

Limits to protect the cluster

Making these searches cheap: pay at indexing time

The remedy for slow pattern searches is usually to do the work when documents are indexed, not when queries run. Options include indexing the beginnings of terms for prefix search, indexing small overlapping pieces of words for partial matching, or using a special field type built for substring searches. Each of these multiplies the number of terms and postings, so the search becomes fast at the cost of a larger index and slower indexing. Choose them only for fields that truly need such searches.

The postings lists of a text-heavy index are often its biggest part. Shaping them well saves disk, memory, and time.

What determines the size

A numbers walkthrough

Let us use invented numbers. Suppose an index holds 50 million documents, each with about 100 tokens in its main text field, so 5 billion token occurrences in total. Suppose, after removing repeats within a document, there are about 3 billion pairs of a term and a document. With compression, storing only document numbers and frequencies might cost about 1 byte per pair, so around 3 gigabytes. Storing positions costs roughly another byte per occurrence, adding about 5 gigabytes. In this example, positions are more than half of the postings size. If phrase searches are not needed on that field, dropping positions cuts the postings by well over half.

Now imagine the same field also gets edge n-grams from 2 to 15 characters. A ten-letter word now yields nine or more extra terms, so token occurrences might grow eight to ten times, and the index may grow by a similar factor. It is easy to see why applying n-grams to long text is dangerous, and why they belong on short fields such as names and titles.

Measuring where the space goes

Elasticsearch has an analysis endpoint for index disk usage that breaks an index down by field and by structure: how many bytes go to the inverted index, to norms, to stored fields, to doc values, and to the number trees. It is an expensive operation, so run it on a test copy or in a quiet period. It answers the most useful question in sizing: which fields are the big ones, and which structure inside them.

Tuning levers

Queries that cost a lot

• Two common terms required together. Even the shorter list is long. Use filters, or rank on rarer terms where possible.
• Leading wildcards and heavy regular expressions. They test every term.
• Very large terms lists. Each term costs a lookup and a list read.
• Exact counts on every request. They disable skipping.
• Phrase searches on very common words. Many candidates, each needing a position check.
• Searching across very many segments. Each adds a lookup.

Memory: leave it for the file cache

Postings are read from files through the operating system’s cache. The more of the hot lists fit in that cache, the fewer disk reads a search needs. That is why guidance always says to keep the heap moderate and leave a generous share of the machine’s memory to the operating system. If searches are slow and disk reads are high, more memory for the cache, faster disks, or smaller lists will help more than any query trick.

Every design carries a price. Here is the honest balance sheet of the postings list.

How rich should the postings be?

Postings lists live in files on disk. Their reliability comes from checks, copies, and careful upgrades.

Every copy builds its own lists

In the standard model, each replica applies the same operations as the primary, so each builds its own postings lists in its own segments. The segments on two copies of a shard therefore differ in layout and timing, although they describe the same documents. A search may be served by any copy, and returns the same matches, except for small differences caused by refresh timing and by statistics that depend on segment layout.

Checksums guard every file

Lucene writes a checksum at the end of every file it creates, including postings files. The checksum is verified in several situations: when files are copied to another node during recovery, when segments are merged, and, if requested, when a shard opens. If a file has been damaged by a disk fault, the check finds it, rather than letting a search read garbage or spread the damage into a merge.

When a segment is corrupted

If a shard copy discovers corruption, it is marked as failed, and the cluster rebuilds it from a healthy copy, in the same way as after any other failure. This is one of the practical reasons to keep at least one replica for important data. Without a replica, a corrupted shard can only be repaired from a snapshot, or, in the worst case, may lose the affected documents.

Upgrades and the file format

The format of postings files changes when Lucene moves forward. Elasticsearch can read segments written by the previous major version of Lucene, and new segments and merged ones are written in the newer format, so old data is rewritten gradually. But it cannot read segments that are more than one major generation old. For very old indexes, upgrading requires reindexing the data into a new index, or using the special handling that the release notes describe. Plan large upgrades with this in mind, and check the compatibility rules of your target version early.

Habits that keep postings safe

The words of your documents live in the dictionary and the lists. That deserves the same care as the documents themselves.

The index contains your text

A postings index is not an opaque blob. The term dictionary holds the words of your documents, and the lists, together with positions, can be used to reconstruct large parts of the original text. Anyone who can read the files of a shard can learn a great deal about the content. Protect the disks with encryption at rest, restrict who can log in to the machines, and treat snapshots, which contain the same files, with the same care.

Some APIs reveal indexed terms

Restrict who can call these on sensitive indexes. Use the security features of Elasticsearch to limit users to the indexes and fields they need, and where your subscription supports it, use field-level and document-level restrictions, which work by combining the user’s filters with the lists behind each query.

Deleted does not mean gone yet

When a document is deleted, its terms and postings remain in the sealed segment until a merge removes them, and older history may be kept for recovery for a while longer. For strict privacy rules, such as erasing personal data on request, this means that the data may remain on disk for some time after deletion. Design your deletion process with this in mind: know how long merges and history retention take in your setup, consider forcing merges on affected indexes where appropriate, and remember that snapshots hold copies until they expire.

Sensitive terms and the dictionary

Even after all documents that contained a certain word are deleted and merged away, ordinary practice is fine, but before that happens the word remains in the term dictionary. If a word itself is sensitive, such as a person’s name, treat the index as containing it until the data is fully purged.

Query abuse

As Chapter 12 explained, some queries are very expensive. A user, or an attacker, who can send arbitrary wildcard, regular expression, or huge terms queries can slow the cluster for everyone. Limit what queries applications can construct, set timeouts and limits, and put rate limits in front of public search endpoints.

Timing and inference

The time a query takes depends on the length of the lists it reads. In theory, an observer who can run many queries and measure the timings may infer how common a certain word is. For public search boxes over sensitive data, this is a reason to limit result detail, throttle requests, and avoid exposing raw timings.

You cannot tune what you cannot see. These are the windows onto your postings lists and the signals worth watching.

Metrics to chart

Reading the patterns

A troubleshooting playbook

Good habits keep postings lists small and searches fast. Bad habits are behind most bloated indexes and slow queries.

Patterns that work

Anti-patterns to avoid

A short list you could hand to a new teammate on their first day.

Best practices

Common mistakes

• Thinking postings hold the documents. They hold only document numbers, frequencies, and positions. The text lives elsewhere.
• Expecting the internal document number to be the _id. They are unrelated, and the internal number changes at merges.
• Using numeric types for identifiers. Numbers use range trees, not postings. Exact-match identifiers usually belong in keyword fields.
• Debugging documents instead of terms. Matching happens on analyzed terms. Compare the terms, not the raw text.
• Forgetting that filters and scores differ. Conditions that need no score belong in filter context.
• Ignoring segment counts. Many tiny segments slow every search.
• Force merging live indexes. It creates very large segments that are hard to keep tidy.
• Assuming a mapping can be changed in place. Changes to analyzers or index options usually require reindexing.

Myths versus facts

Where do postings lists quietly decide success or trouble?

Many well-known organizations have said publicly that Elasticsearch is part of their systems, including Wikipedia’s search, Netflix, Uber, and Stack Overflow. They rarely publish how they shape their indexes, so the scenarios below are typical patterns for such workloads, not descriptions of anyone’s private configuration.

Short answers to the questions that come up most often.

If you skim only one part of this guide, make it this one.

The postings list is the quiet workhorse of Elasticsearch. For each word in a field, inside each segment, it keeps a sorted, compressed list of the documents that contain it, sometimes with how often and where. Searches read and combine these lists, ranking uses their numbers, merges rewrite them, and their size and shape decide much of the cost of your cluster.