The inverted index, mechanically
What it is
A map from term to the list of documents containing it, which inverts the natural document-to-terms direction and is the reason full-text search is fast.
FORWARD (the natural direction, useless for search)
doc1 -> [the, quick, brown, fox]
doc2 -> [the, lazy, brown, dog]
To find "brown" you scan every document.
INVERTED
brown -> [1, 2]
dog -> [2]
fox -> [1]
quick -> [1]
To find "brown" you do one lookup.
The structure has three parts and conflating them hides where the cost is:
TERM DICTIONARY term -> pointer into the postings.
Must be small enough to keep hot, so it is
usually a compressed FST or a B-tree.
POSTINGS LIST for each term, the sorted document ids
containing it, plus per-document data:
term frequency, and positions if you want
phrase queries.
DOC VALUES / column-oriented per-document values for
STORED FIELDS sorting, faceting and retrieval. NOT part
of matching.
Commonly confused with "the index" as one thing. The dictionary decides lookup cost, the postings decide intersection cost, and doc values decide sort and facet cost, and a slow query is usually slow in exactly one of the three.
The problem it solves
Matching without scanning.
10 million documents, average 500 terms each.
A scan for one term reads 5 billion terms.
An inverted index reads one dictionary entry and one
postings list, which for a moderately common term is
thousands of entries.
That is the difference between a query being impossible and
being a millisecond.
And the second problem, which is the one that shapes the data structures: the postings lists are enormous. A term appearing in 10 percent of a 100-million-document corpus has a 10-million-entry postings list, so how those integers are stored decides whether the index fits in memory.
Mechanics
Postings compression: delta encoding plus variable-byte
Document ids are sorted, which is the property everything exploits.
RAW [3, 17, 25, 26, 40, 41, 42, 100]
8 x 4 bytes = 32 bytes
DELTA (gaps) [3, 14, 8, 1, 14, 1, 1, 58]
Same information, much smaller numbers.
VARIABLE-BYTE Small numbers take one byte, large ones
take more. Most gaps are small.
-> roughly 8 bytes total.
*** 32 bytes to 8. And the denser the term, the smaller the
gaps, so the most expensive lists compress best. ***
Modern implementations use block-based schemes rather than per-integer variable-byte:
FOR (frame of reference) / PFOR-delta
Take a block of 128 docids, find the minimum gap, store
the offsets in the smallest bit-width that fits, and
store the exceptions separately.
-> Decodes with SIMD, several times faster than
per-integer decoding, and it is why block sizes are
powers of two.
Lucene uses a PFOR-delta variant on 128-document blocks,
with a skip structure on top.
The property that matters for query speed: decompression is sequential and SIMD-friendly, so scanning a postings list is bandwidth-bound rather than branch-bound, which is why postings intersection is much faster than the entry count suggests.
Skip lists: how intersection avoids reading everything
QUERY: "brown AND dog"
brown -> [1, 2, 5, 9, 14, 22, 31, 45, 60, 77, 91, ...]
dog -> [45, 91, 200]
NAIVE: walk both lists in lockstep. Reads all of brown.
WITH SKIPS: dog's first entry is 45. Ask brown to advance
to at least 45. The skip structure jumps directly past the
entries below 45 without decoding them.
The skip structure is a multi-level index into the postings:
level 2: docid 1 docid 512 docid 1024
level 1: 1 128 256 384 512 ...
level 0: every 128-document block boundary
advance(target) descends the levels, so it is logarithmic
rather than linear in the postings length.
This is why a query with one rare term and one common term is fast: the rare term drives the iteration and the common term skips, so the cost is proportional to the rare list rather than the common one. And it is why query planners order conjunctions by document frequency, cheapest first.
WAND and block-max WAND: skipping on score
Skip lists let you skip on document id. WAND lets you skip on score, which is a much bigger win for top-k queries.
THE OBSERVATION
For a top-10 query you do not need every matching
document, only the 10 best. If a document cannot possibly
score above the current 10th-best, you can skip it
without scoring it.
WAND (Weak AND)
Keep an upper bound on each term's maximum contribution.
Sort the term iterators by current docid. Sum the upper
bounds of the leading terms; if the sum cannot exceed the
current threshold, advance past that document entirely.
BLOCK-MAX WAND
Store a per-BLOCK maximum score alongside each postings
block, so you can skip a whole 128-document block whose
best possible score is below the threshold.
The effect is large: block-max WAND commonly evaluates a small fraction of the matching documents
for a top-k query, and it is why Lucene's top-k retrieval is far faster than the matching-document
count implies. It also means totalHits is expensive, which is why Elasticsearch stopped
counting exact totals by default above 10,000: the optimisation that makes top-k fast is precisely
the one that stops you knowing how many matched.
That trade is worth knowing because it surprises people: "why does my hit count say 10,000+" has a real answer, and it is not a limitation, it is the price of the optimisation you want.
The term dictionary: FSTs
The dictionary maps term -> postings offset, for possibly
hundreds of millions of terms, and it must be small enough
to stay in memory.
Lucene uses a FINITE STATE TRANSDUCER: a minimal automaton
that shares prefixes AND suffixes.
"cat", "cats", "category", "catalog"
share the "cat" prefix; "s" endings share suffix states.
-> Typically a small fraction of the raw term bytes,
while still supporting exact lookup, prefix scans and
fuzzy matching over the automaton.
The FST is why wildcard and fuzzy queries are possible at all: they compile to an automaton and
are intersected with the dictionary's automaton, so bro* does not scan every term.
Positions, and what phrase queries cost
WITHOUT POSITIONS
brown -> [1, 2]
Enough for "brown", useless for "brown fox" as a phrase.
WITH POSITIONS
brown -> [ (1, tf=1, pos=[2]), (2, tf=1, pos=[2]) ]
fox -> [ (1, tf=1, pos=[3]) ]
Phrase match: doc 1 has brown@2 and fox@3, adjacent. Hit.
COST
Positions typically DOUBLE the index size or more, and
phrase queries are substantially slower because they read
and intersect position lists as well as docid lists.
Which is why index_options is a real decision: docs for a filter-only field, freqs if you
score it, positions only if you need phrases or proximity. Indexing positions on a field nobody
phrase-searches is a pure cost, and it is the most common index-size mistake.
Where a slow query actually is
SYMPTOM LIKELY PART
-------------------------------------------------------
slow with many terms postings intersection;
check for a term with a
huge list and no skip
benefit
slow with wildcards or fuzzy the term dictionary: the
automaton is matching a
large number of terms
slow when sorting or faceting doc values, which are read
for every matching doc
slow only at high hit counts you are asking for exact
total hits and defeating
block-max WAND
slow after a bulk load segment count; the query
pays a fixed cost per
segment
That table is the diagnostic, and the point is that "search is slow" has five different causes living in three different structures, so the first move is finding out which.
A worked example: an index that was three times too large
SYMPTOM
A 40 GB index for 20 million documents of roughly 2 KB
each. The raw text is 40 GB, so the index is 1x the
source, which is high: 0.3x to 0.6x is typical.
THE AUDIT (Lucene's index inspection, or
_cat/segments plus field-level stats)
postings (docids + freqs) 9 GB
POSITIONS 18 GB <-- 45%
doc values 7 GB
stored fields 5 GB
term dictionary 1 GB
FINDING 1: positions were indexed on every text field.
Six text fields. Phrase queries were used on exactly one
of them, the title.
-> index_options: freqs on the other five.
-> 18 GB to about 4 GB.
FINDING 2: doc values on fields never sorted or faceted.
Doc values are enabled by default on keyword fields, and
eleven of them were never used in a sort, a facet or an
aggregation.
-> doc_values: false on those.
-> 7 GB to 3 GB.
FINDING 3: stored fields held the full document body,
which was also in the source of truth and never returned
from search.
-> store only the fields actually returned.
-> 5 GB to 1 GB.
RESULT
40 GB to 18 GB, and the query p99 improved as well,
because the working set now fit in page cache where
before it did not.
THE OBSERVATION
None of the three was a tuning parameter. All three were
DEFAULTS that were correct for a general-purpose engine
and wrong for this corpus, and nobody had looked at what
the fields were actually used for.
Production evidence
Lucene's index format documentation specifies the postings encoding (PFOR-delta on 128-document blocks), the skip structure, the FST-based term dictionary and the separation of doc values from postings, and it is the authoritative reference because Elasticsearch, OpenSearch and Solr all inherit it.
Broder et al., "Efficient Query Evaluation using a Two-Level Retrieval Process" (CIKM 2003) is the WAND paper, and Ding and Suel, "Faster Top-k Document Retrieval Using Block-Max Indexes" (SIGIR 2011) is block-max WAND. Both are short and are the reason top-k retrieval is fast.
Elasticsearch's change to track_total_hits defaulting to 10,000 is the visible consequence of
block-max WAND: exact counting defeats the early-termination optimisation, so it became opt-in.
Manning, Raghavan and Schütze, Introduction to Information Retrieval chapters 1 to 5 cover the index construction, compression and skip pointers from first principles and remain the standard teaching reference.
Lucene's index_options and doc_values field settings exist precisely because the defaults
are general-purpose, and the Elasticsearch tuning-for-disk-usage documentation recommends exactly
the three changes in the worked example.
The debate
The case for understanding this depth: index size and query latency problems are diagnosed in these structures, and a team that treats the index as opaque tunes the wrong things. The three defaults in the worked example cost 22 GB and a page-cache miss rate, and finding them required knowing what the parts are.
The case against: almost nobody implements an inverted index, the engines handle it, and the practical levers are field mappings and shard sizing rather than postings encoding. Time spent on PFOR-delta is time not spent on relevance.
My position: know the three parts and what each costs, because that is the diagnostic, and treat the encoding details as background.
The distinction that pays is dictionary, postings, doc values, because a slow query is slow in one of them and the fix differs completely: a wildcard problem lives in the dictionary, an intersection problem in the postings, a sort or facet problem in doc values. "Search is slow" is five different causes in three structures, and knowing which to look at first is most of the value of this topic.
The lever I would reach for first on index size is index_options and doc_values per field,
because positions typically double the index and are needed only for phrase and proximity queries,
and doc values are enabled by default on fields that are frequently never sorted or faceted. In the
worked example those two accounted for 22 of 40 gigabytes, and none of it was a tuning parameter,
it was defaults that were right in general and wrong for that corpus.
The mechanism worth being able to explain is block-max WAND, because it explains something users actually notice: exact total hit counts are expensive, and the reason Elasticsearch stopped reporting them by default is that counting everything defeats the early termination that makes top-k fast. That is a trade rather than a limitation, and being able to say so turns a confusing default into an understandable one.
Where I would push back on going deeper: the encoding is genuinely background. Knowing that postings are delta-encoded in SIMD-friendly blocks explains why intersection is bandwidth-bound, and beyond that the details do not change any decision you will make.
Follow-up Q&A
"What is an inverted index, mechanically?" Three parts, and separating them is what makes it diagnosable. A term dictionary mapping term to a postings offset, usually an FST so it shares prefixes and suffixes and stays small enough to keep hot. Postings lists holding sorted document ids plus term frequencies and optionally positions. And doc values, which are column-oriented per-document values used for sorting and faceting and are not part of matching at all.
"How are postings stored so they fit?" Delta encoding first, because docids are sorted so the gaps are small numbers, then a block scheme like PFOR-delta over 128-document blocks: find the bit-width that fits most gaps, store exceptions separately. That decodes with SIMD, so scanning a postings list is bandwidth-bound rather than branch-bound. And the nice property is that the densest terms have the smallest gaps, so the most expensive lists compress best.
"How does an AND query avoid reading the whole common list?" Skip lists. The postings have a
multi-level skip structure, so advance(target) descends the levels and jumps past blocks without
decoding them. So for "rare AND common", the rare term drives the iteration and the common one
skips, making the cost proportional to the rare list. That is also why query planners order
conjunctions by document frequency, cheapest first.
"What is WAND?" Skipping on score rather than on docid, which is a much bigger win for top-k. For a top-10 query you only need the ten best, so if a document cannot possibly score above the current tenth-best you can skip it without scoring it. WAND keeps an upper bound per term and compares the sum of the leading terms' bounds against the threshold. Block-max WAND stores a per-block maximum so you can skip a whole 128-document block, and it commonly evaluates a small fraction of matching documents.
"Why doesn't Elasticsearch give me an exact hit count any more?" Because exact counting defeats
block-max WAND. The optimisation that makes top-k retrieval fast works by never evaluating documents
that cannot make the top k, and counting them all means evaluating them all. So track_total_hits
defaults to 10,000 and exact counts became opt-in. It is a trade rather than a limitation, and it is
the price of the thing you actually want.
"Why are phrase queries slower?" They need positions, which means the index stores where in the
document each term occurred, not just that it occurred. That typically doubles index size or more,
and the query reads and intersects position lists in addition to docid lists. Which makes
index_options a real decision: docs for a filter-only field, freqs if you score it, and
positions only where you genuinely phrase-search. Indexing positions on a field nobody
phrase-searches is pure cost and it is the most common index-size mistake.
"Where do you look when a query is slow?" It depends which of the three parts, and the symptom tells you. Slow with many terms is postings intersection. Slow with wildcards or fuzzy is the term dictionary, because the automaton is matching many terms. Slow when sorting or faceting is doc values, which are read for every match. Slow only at high hit counts means you are asking for exact totals. And slow after a bulk load is usually segment count, since queries pay a fixed cost per segment.
"How would you shrink an oversized index?" Field settings before anything else. In one case a 40 gigabyte index for 20 million documents was 45 percent positions, indexed on six text fields when phrase queries were used on one. Turning that off took 18 gigabytes to 4. Then doc values on eleven keyword fields that were never sorted or faceted, 7 gigabytes to 3. Then stored fields holding the full body that was never returned, 5 to 1. Forty gigabytes to eighteen, and the p99 improved because the working set now fit in page cache.
"How much of this do you actually need?" The three parts and what each costs, because that is the diagnostic. The encoding details are background: knowing postings are delta-encoded in SIMD-friendly blocks explains why intersection is bandwidth-bound, and beyond that it does not change a decision. What changes decisions is knowing that positions double the index, doc values are on by default and often unused, and exact hit counts are expensive.
Common misconceptions
"The index is one structure." Dictionary, postings and doc values have different costs and different failure modes, and a slow query is slow in one of them.
"An AND query reads both postings lists." Skip lists let the common term jump, so the cost is proportional to the rare term.
"Top-k retrieval scores every match." Block-max WAND skips whole blocks that cannot reach the threshold, which is why counting exact hits is expensive.
"Positions are free." They typically double the index and slow phrase queries, and they are indexed by default on text fields that never need them.
"Doc values are part of matching." They are for sorting, faceting and aggregation, and they are enabled by default on fields that frequently never need them.
Interview delivery note
Give the three parts first, because it converts a vague structure into a diagnostic: "Three parts that fail differently. A term dictionary, usually an FST so it shares prefixes and suffixes and stays hot. Postings lists with sorted docids, frequencies and optionally positions. And doc values, which are columnar per-document values for sorting and faceting and aren't part of matching. A slow query is slow in exactly one of those, and the fix differs completely."
Explain the intersection trick, since it is the mechanism people cannot usually produce: "Docids are sorted, so postings are delta-encoded and stored in SIMD-decodable blocks. And there's a multi-level skip structure, so for 'rare AND common' the rare term drives the iteration and the common one jumps past blocks without decoding them. That's why planners order conjunctions by document frequency."
Then the one that explains something users see: "Block-max WAND skips on score rather than docid: for a top-ten query, a document that can't beat the current tenth-best is never scored, and a whole 128-document block whose maximum can't reach the threshold is skipped entirely. Which is also why Elasticsearch stopped giving exact hit counts by default. Counting everything defeats exactly the optimisation that makes top-k fast."
Close with the practical lever, because it is where the money is: "And for index size the levers are field settings rather than anything exotic. In one case a forty-gigabyte index was forty-five percent positions, indexed on six fields when one was phrase-searched. Positions off on the other five took it to eighteen gigabytes total, and the p99 improved because the working set finally fit in page cache. None of the three fixes was a tuning parameter, they were defaults that were right in general and wrong for that corpus."
Further reading
- The Lucene index format documentation, for the postings encoding, skip structure and FST dictionary.
- Broder et al., "Efficient Query Evaluation using a Two-Level Retrieval Process" (CIKM 2003), and Ding and Suel, "Faster Top-k Document Retrieval Using Block-Max Indexes" (SIGIR 2011).
- Manning, Raghavan and Schütze, Introduction to Information Retrieval, chapters 1 to 5.
- Elasticsearch's "Tune for disk usage" documentation and the
index_optionsanddoc_valuesmapping references.