Postings lab

How a search engine stores and walks its postings lists, small enough to see every bit. Build an index from the built-in notes, a synthetic Zipf-distributed collection or your own text, then look at the three things that make an inverted index fast: compression, skipping and dynamic pruning. All of it runs in the page.

How to use it

Index. Choose the collection: 30 short notes about search engines (good for stepping through), a synthetic collection of up to 50,000 documents of made-up words drawn from a Zipf distribution (realistic list lengths and sizes), or your own documents (one per paragraph or per line; a first line starting with # is a title). Text is lower-cased and split on anything that is not a letter or digit, optionally without English stop words — for real analysis chains use the analyzer playground. Pick a term to see its postings: docID, d-gap, term frequency and positions.

Compression. For the whole index: bits per posting for the docID gaps, the term frequencies and the position gaps under every codec, and the total size. For one list: bits per codec, a round trip check, the first gaps written out bit by bit, the block widths and exceptions of the block codecs, and the Roaring containers.

Codec	How it works
VByte	7 data bits a byte, the high bit says another byte follows (Lucene’s VInt)
Elias γ	⌊log₂ x⌋ zeros, then x in binary
Elias δ	the length of x in γ, then x without its leading 1
Golomb	b = ⌈ln 2 · N / df⌉; the quotient (x−1)/b in unary, the remainder in truncated binary — close to optimal when documents are spread at random
Rice	Golomb with b a power of two, so the remainder is plain bits
Simple-9 / Simple-16	32-bit words: a 4-bit selector and 28 data bits split 9 (or 16) ways
FOR-128	blocks of 128 gaps at the bit width of the largest; the tail in VByte
PForDelta	blocks of 128 at the width that makes the block smallest; values that do not fit are patched in afterwards (NewPFD-style: positions and high bits in VByte)
Lucene PForUtil	Lucene 9’s postings blocks: the width of the 8th-largest value (at most 8 below the largest), up to 7 exceptions as an index byte and a high-bits byte; a block of equal values is one VInt
Roaring	the docIDs themselves in chunks of 65,536: a sorted array (≤ 4,096 values), an 8 KB bitmap, or runs — whichever is smaller — in the portable format CRoaring, Java and Go read

Codec

How it works

VByte

7 data bits a byte, the high bit says another byte follows (Lucene’s VInt)

Elias γ

⌊log₂ x⌋ zeros, then x in binary

Elias δ

the length of x in γ, then x without its leading 1

Golomb

b = ⌈ln 2 · N / df⌉; the quotient (x−1)/b in unary, the remainder in truncated binary — close to optimal when documents are spread at random

Rice

Golomb with b a power of two, so the remainder is plain bits

Simple-9 / Simple-16

32-bit words: a 4-bit selector and 28 data bits split 9 (or 16) ways

FOR-128

blocks of 128 gaps at the bit width of the largest; the tail in VByte

PForDelta

blocks of 128 at the width that makes the block smallest; values that do not fit are patched in afterwards (NewPFD-style: positions and high bits in VByte)

Lucene PForUtil

Lucene 9’s postings blocks: the width of the 8th-largest value (at most 8 below the largest), up to 7 exceptions as an index byte and a high-bits byte; a block of equal values is one VInt

Roaring

the docIDs themselves in chunks of 65,536: a sorted array (≤ 4,096 values), an 8 KB bitmap, or runs — whichever is smaller — in the portable format CRoaring, Java and Go read

AND / OR. A boolean query intersected shortest list first, three ways: a linear merge, a merge with √n skip pointers, and galloping (exponential) search — with the number of docID comparisons each needs, and the skip pointers of the first term.

Top-k. BM25 (Lucene 8+: idf · tf / (tf + k1·(1 − b + b·dl/avgdl))) top k by five algorithms: term-at-a-time and document-at-a-time exhaustive scoring, MaxScore, WAND and Block-Max WAND. The table counts documents fully scored, term scores computed, cursor moves and blocks decoded, and checks that every algorithm returned exactly the exhaustive top k. Step by step replays MaxScore, WAND or BMW: the cursors on each list with their upper bounds, the threshold θ (the k-th best score so far), the pivot, and what happened — a document scored, a cursor moved to the pivot, a block skipped because the block maxima cannot beat θ, or a candidate dropped by MaxScore. With the built-in notes and a block size of 4 you can follow every step.

Checked against

The tests encode the tables in Witten, Moffat & Bell, Managing Gigabytes (γ, δ, Golomb b = 3, Rice), the VInt example 300 → AC 02, the Simple-9/16 layouts and Lucene’s PForUtil block layout; round-trip every codec on lists from 0 to 1,000 gaps of every shape, gaps up to 2³¹, and every list of a 1,500-document index; and compare the Roaring serialisation byte for byte with pyroaring 1.2.0 (CRoaring) with and without run_optimize. MaxScore, WAND and Block-Max WAND are run on 720 random query/k/block-size/k1/b combinations and must return the same documents with bit-identical scores as exhaustive scoring (ties go to the lower docID); they also check that pruning scores fewer documents.

Sources: Manning, Raghavan & Schütze, Introduction to Information Retrieval ch. 2 and 5; Witten, Moffat & Bell, Managing Gigabytes (1999) ch. 3; V. N. Anh & A. Moffat, "Inverted index compressed using word-aligned binary codes" (Simple-9), 2005; J. Zhang, X. Long & T. Suel, "Performance of compressed inverted list caching in search engines" (Simple-16), WWW 2008; M. Zukowski, S. Héman, N. Nes & P. Boncz, "Super-scalar RAM-CPU cache compression" (PFOR), ICDE 2006; H. Yan, S. Ding & T. Suel, "Inverted index compression and query processing with optimized document ordering" (NewPFD), WWW 2009; S. Chambi, D. Lemire, O. Kaser & R. Godin, "Better bitmap performance with Roaring bitmaps", 2016; H. Turtle & J. Flood, "Query evaluation: strategies and optimizations" (MaxScore), 1995; A. Broder et al., "Efficient query evaluation using a two-level retrieval process" (WAND), CIKM 2003; S. Ding & T. Suel, "Faster top-k document retrieval using block-max indexes", SIGIR 2011; Lucene’s ForUtil/PForUtil and BM25Similarity.

Limits

Sizes are of the postings only: no term dictionary, skip data or norms. Golomb’s b is not counted (it would sit in the term dictionary).
The index is built in memory: up to about 50,000 short documents. Lucene also impacts-sorts frequency/norm pairs for its block maxima and uses multi-level skips; here each block has an exact maximum score.

Related: Analyzer and inverted-index playground (analysis, postings of an Elasticsearch field, phrase matching), Relevance and scoring explainer (BM25 term by term, function_score, hybrid), Elasticsearch, simulated (shards, segments, merges), Probabilistic sketches, Click models workbench.

Privacy

Documents you paste or open are indexed in this page and never leave it; they and your settings are kept in this browser’s local storage. Nothing is loaded from the network.

Works with

How to use it

Checked against

Limits

Privacy