Modern Postings Compression

The codes that replaced variable byte and gamma codes in search engines, worked bit by bit on the Reuters-21578 postings of the course's index compression page. Binary packing and the frame of reference, patched coding with the choice of width derived, Simple-9 and the layouts built for vector instructions, and the Elias–Fano representation with its space bound proved and its skipping explained, each measured in bits per posting and decoded for a round-trip check. Worked problems encode a textbook list in every code, compare Elias–Fano with gamma codes on evenly spaced and clustered lists, and find where a bitmap is smaller.

Index compression left the 725,793 postings of Reuters-21578 at 9.57 bits each under variable byte codes, 8.63 under gamma codes and 8.08 under delta codes. It closed with three bullet points naming what current engines use instead: word-aligned codes, PForDelta, and codecs built on the vector instructions of modern processors. None of the three was worked there. What do those codes do bit by bit, what does the Elias–Fano representation that joined them later do, and do any of them make this index smaller?

They are list compressors. A gamma or variable byte code gives each gap its own codeword, and a decoder must finish one codeword to learn where the next begins. A list compressor encodes a run of integers together, with one decision for the whole run (Pibiri and Venturini, 2021, section 3). The answer on size is mixed, and it is reported below as measured. Plain blocks of fixed width do not beat the delta code on this index, and patched blocks beat it by a quarter of a bit. Elias–Fano brings the index to 6.91 bits per posting, the smallest of every code tried. The block codes were designed for decoding speed, which a script in Python cannot measure, so their speeds are cited from the papers that measured them.

Here is the route. First we see why a code for single integers is slow to decode. Then we work binary packing and patched coding on one real block of 128 gaps, and derive how the width of a patched block is chosen. Next come the layouts built for whole machine words and for vector instructions, which are described and cited. Then Elias–Fano is built on a five-posting list, its space bound is proved, and its way of skipping is traced. Finally every code is measured on the whole collection and on this site's own index. The article assumes index compression, whose gaps, variable byte, gamma and delta codes are used without being defined again, and its two Reuters lists carry through this article too: palladium, with the docIDs 1467, 1521, 1792, 1795 and 8079, and oil, with 1,038 postings. The numbers are computed by tools/experiments/query-processing/modern-postings-compression.py, which encodes every postings list with every code, decodes it, and compares the result with the original.

Why one integer at a time is slow

A gamma decoder reads ones until it meets a zero, and only then knows how many more bits belong to the gap. A variable byte decoder tests the high bit of every byte. In both, what the processor does next depends on the data it has just read. Zukowski, Héman, Nes and Boncz (2006) made this the center of their design argument. A modern processor runs several instructions at once and guesses the outcome of each test before it is known. A wrong guess throws away the work in progress. A decoder whose inner loop tests each value therefore runs well below what the processor can do, and their compression schemes were built to have no if-then-else in the parts that run for every value.

The same reasoning shapes everything in the first half of this article. If 128 gaps are all stored in the same number of bits, the position of every gap in the block is known before any of them is read. The decoder is then a loop of shifts and masks whose steps do not depend on each other. The price is paid in size: all 128 gaps get the width that the largest of them needs.

Two conventions hold for every measurement below. Sizes are exact counts of bits, with no padding to whole bytes between lists, which is how the course page counted its gamma and delta rows. The number of postings in a list, its document frequency, is taken to be stored in the dictionary, so no code spends bits on it. A megabyte is a million bytes.

Frame of reference and binary packing

The oldest idea of this family comes from databases, where Goldstein, Ramakrishnan and Shaft (1998) compressed the records of a table page by page. In the description of Lemire and Boytsov (2015, section 2.6), the values of a block are written "in reference to the range of values": if they lie between 1000 and 1127, each is stored in 7 bits as its offset from 1000, since the 128 possible offsets need $\lceil \log_2(1127 + 1 - 1000) \rceil = 7$ bits. The smallest value is the frame of reference.

Applied to the docIDs of a postings list, the frame would be the first docID of each block. The first 128 postings of oil run from docID 3 to docID 1364. Their offsets from 3 reach 1361, which takes 11 bits, so the block would cost $128 \times 11$ bits, which is 1,408. Gaps do much better, because they are small whatever the docIDs are. When the integers are gaps, the frame is simply zero, and the method is called binary packing. Cut the gaps into blocks, find the number of bits $w$ that the largest gap of the block needs, write $w$ in a header, and write every gap of the block in exactly $w$ bits.

For a block of $n$ gaps whose largest is $G_{\max}$, the width is $w = \lfloor \log_2 G_{\max} \rfloor + 1$, the number of binary digits of $G_{\max}$. With an 8-bit header the block takes

$$8 + n\,w \ \text{bits}.$$

Take the first 128 gaps of oil. The largest is 62, which has six binary digits, so $w = 6$ and the block takes $8 + 128 \times 6 = 776$ bits, 6.06 per gap. Variable byte spends 1,024 bits on the same gaps and the gamma code 714. The gamma code is smaller because most of these gaps are much shorter than six bits:

Bits needed Gaps in the block
1 17
2 26
3 26
4 31
5 18
6 10

Ten gaps of the 128 need six bits, and they set the width for the other 118. That is the weakness of binary packing, and the next section removes most of it. What it buys is the decoder. Gap number $j$ of the block, counting from zero, occupies bits $8 + 6j$ to $8 + 6j + 5$, so all 128 can be extracted by one loop with no tests, and the docIDs follow by a running sum.

The block size is a trade. Smaller blocks follow the local size of the gaps more closely and pay for more headers. On the whole Reuters index, blocks of 128 give 8.18 bits per posting, blocks of 32 give 7.91, and blocks of 8 give 7.94, where the headers begin to cost more than the tighter widths save.

Apache Lucene's postings format is a documented example of this design. The format of Lucene 9.9 packs the gaps between docIDs in blocks of 128 with one bit width per block, set by the largest value and without patching. It writes the postings left over at the end of a list, fewer than 128, as variable-length integers (Apache Software Foundation, 2023). That is the format of one release, of December 2023. As of November 2026 the documentation of Lucene 10.3.0 describes a later class, Lucene103PostingsFormat, in the same terms: packed blocks whose integers share one bit width, with a block size that "is fixed (currently 128)" (Apache Software Foundation, 2025). The row "binary packing of full blocks of 128, variable byte for the rest" in the measurements below follows that plan.

Patched coding

Zukowski, Héman, Nes and Boncz (2006) called their answer to the one large value patching. Choose a width smaller than the largest value needs. Values that fit are stored in it as before. The few that do not fit are exceptions, stored somewhere else, and the decoder first unpacks every slot as if nothing were unusual and then repairs the slots of the exceptions in a second pass. In their words, the first loop "simply decodes all values", and the second "patches up the incorrect values". Neither loop tests each value, which was the point. They named the schemes PFOR, for patched frame of reference, and PFOR-DELTA when it is applied to differences, as it is on gaps. The name PForDelta in the course article refers to the second.

The original layout is worth knowing because later ones were reactions to it. As Lemire and Boytsov (2015, section 2.8) describe it, a single width serves a whole page of blocks, and exception values are stored uncompressed in a separate area. The slot of each exception holds the distance to the next exception, so that the exceptions form a linked list through the block. A distance too large for the slot forces an extra exception in between. Yan, Ding and Suel (2009, section 4.2) removed that chain in the variants they call NewPFD and OptPFD. A block still has 128 slots of one width. The slot of an exception keeps the low bits of the value, and the high bits and the positions of the exceptions go into two separate arrays, which are compressed in their turn. The two variants differ in how the width is chosen. As Lemire and Boytsov (2015, section 2.8.1) describe them, NewPFD takes the smallest width that leaves at most a tenth of the values as exceptions, and OptPFD takes the width that makes the block smallest. Yan, Ding and Suel add that the widths may then be changed, block by block, to buy decoding speed at a cost in size. FastPFOR, the variant of Lemire and Boytsov, stores for each block one byte for the width, one for the largest width in the block, one for the number of exceptions and one byte for the position of each exception. It gathers the high bits of the exceptions of many blocks so that they can be packed together.

The code measured in this article is of that last kind, kept per block so that it can be worked by hand. For a block of $n$ gaps:

  • a header of two bytes holds the width $w$ and the number of exceptions $c$;
  • the low $w$ bits of every gap are packed, as in binary packing;
  • if $c > 0$, one byte holds the largest width $w_{\max}$ in the block, then one byte gives the position of each exception, and then the high part of each exception follows in $w_{\max} - w$ bits.

How the width is chosen. Here is the idea in one sentence: lowering the width by one bit saves a bit in every slot and costs a position and a high part for every gap that no longer fits. Write $c(w)$ for the number of gaps of the block that need more than $w$ bits. The size of the block is

$$\mathrm{size}(w) = 16 + n\,w + \begin{cases} 0 & c(w) = 0 \\ 8 + c(w)\,(8 + w_{\max} - w) & c(w) > 0, \end{cases}$$

and the encoder takes the $w$ between 0 and $w_{\max}$ that makes it smallest. For the first block of oil, $n = 128$ and $w_{\max} = 6$, and the table of gap widths above gives $c(5) = 10$, $c(4) = 28$, $c(3) = 59$ and $c(2) = 85$:

Width $w$ Exceptions Packed part Header and patches Block size in bits
6 0 768 16 784
5 10 640 114 754
4 28 512 304 816
3 59 384 673 1057
2 85 256 1044 1300

At $w = 5$ the packed part falls by 128 bits. The patches cost $8 + 10 \times (8 + 1) = 98$ bits beyond the 16-bit header, so the block takes 754 bits against 784 without exceptions and against the 776 of binary packing. Going on to $w = 4$ saves another 128 bits and adds 18 exceptions at 10 bits each, plus one more bit for each of the first ten, a loss. The best width is 5. The decoder unpacks 128 five-bit fields, then for each of the ten exceptions reads a position and one high bit and adds $2^5$ times that bit to the slot.

With no exceptions the code costs 8 bits more per block than binary packing, the second header byte. So patched packing can lose on blocks that have no outliers, and wins where a few gaps are much larger than the rest. In the Reuters lists of 128 postings or more, the encoder makes 27,939 of the 513,500 gaps exceptions, 5.4 percent.

Word-aligned and vector-friendly layouts

The codes of this section are not different ideas about what to store. They are different answers to the question of how the stored bits should be laid out for the machine that decodes them. Two are described here from their sources and one is also measured.

Simple-9. Anh and Moffat (2005) pack as many gaps as will fit into each 32-bit word. Four bits of the word select one of nine layouts, and the other 28 hold the gaps, all at the same width (the layouts are those of their Table 1, with the selectors numbered as in Pibiri and Venturini, 2021, Table 6):

Selector Gaps in the word Bits each Bits unused
0 28 1 0
1 14 2 0
2 9 3 1
3 7 4 0
4 5 5 3
5 4 7 0
6 3 9 1
7 2 14 0
8 1 28 0

The encoder used here takes, for each word, the first layout in the table whose width holds every one of the next gaps it would take. At the end of a list a layout may be used with fewer gaps than it has room for, since the decoder knows how many postings the list has. The first ten gaps of oil are 3, 36, 41, 11, 3, 1, 6, 18, 2 and 5. Layouts 0 to 4 fail on the first word, because 36 needs six bits, and layout 5 takes the four gaps 3, 36, 41, 11 at seven bits each. The next five gaps, 3, 1, 6, 18 and 2, fit layout 4 at five bits each. The last gap, 5, sits alone in a word of layout 2. That is three words, 96 bits, against 68 for one binary-packed block of ten gaps, 58 for the gamma code and 80 for variable byte. A word is decoded by one table lookup on the selector and a fixed sequence of shifts, and every word starts on a word boundary. The cost is visible on short lists: a list with one posting takes a whole word.

Grouped variable byte. Variable byte can be rearranged the same way. In the formats that Pibiri and Venturini (2021, section 2.9) survey, the continuation bits are taken out of the data bytes and gathered into a control byte. Varint-GB spends two bits of a control byte on the length in bytes of each of four integers. Varint-G8IU lets one control byte describe however many integers fit in exactly eight data bytes, between two and eight of them, which suits a vector instruction that shuffles bytes into place. Stream-VByte writes the control bytes and the data bytes as two separate streams. These formats change how fast the bytes can be turned back into integers. None of them is measured here.

Vectorized binary packing. Lemire and Boytsov (2015) designed binary packing around instructions that operate on four 32-bit integers at once. Their scheme SIMD-BP128 packs blocks of 128 integers and groups sixteen blocks, 2,048 integers, behind one 128-bit descriptor that holds the sixteen widths. Within a block the layout is interleaved: the first four integers go into four different 32-bit words, the fifth is stored next to the first, and so on. One shift and one mask on a 128-bit register then extract four integers together. Turning gaps back into docIDs is a running sum, and they vectorize that as well. Without it, they write, they "were unable to reach a speed of two billion integers per second".

The speeds are cited. Their Table I collects the best decoding speeds that authors had reported up to then, each from its own paper and on its own processor, with the warning that the results "are not directly comparable". Their own SIMD-BP128, measured in C++ on a 3.4 GHz Core i7, decodes 2,300 million integers per second, about 1.5 processor cycles per integer. The other figures are those the authors of each scheme stated. The table reports 1,512 million for the grouped variable byte format varint-G8IU on a 3.3 GHz Xeon, 1,120 million for NewPFD on a 2.66 GHz Core 2, and 1,024 million for the original PFOR on a 3 GHz Pentium 4. One of these figures was compared with its paper. Stepanov, Gangolli, Rose, Ernst and Oberoi (2011, Table 2) give 1,518 million integers per second as the best rate of varint-G8IU, measured on a 3.3 GHz Xeon, where the table of Lemire and Boytsov has 1,512. Their abstract puts SIMD-BP128 at nearly twice the speed of the fastest earlier schemes on desktop processors. In space, a block of SIMD-BP128 costs what a binary-packed block of 128 costs here, apart from its alignment padding, and Lemire and Boytsov also write the integers left over after the last full block as variable bytes. So the row for full blocks of 128 with a variable-byte remainder, below, is the closest to it.

Nothing in this section was timed for this article. A decoder written in Python spends its time in the interpreter, and its speed says nothing about shifts, masks and branch prediction.

Elias–Fano

Every code so far stores gaps. The last one stores the docIDs themselves. Pibiri and Venturini (2021, section 3.4) trace its form to Elias (1974) and, independently, to a memorandum of Fano (1971), and Vigna (2013) engineered it into an inverted index under the name quasi-succinct index. Here is the idea in one sentence: split each docID into a high part and a low part, write the low parts as they are, and write the high parts, which form a slowly growing sequence, in unary.

Let a postings list have $n$ docIDs $x_1 < x_2 < \dots < x_n$, all at most $u$. For a postings list, $u$ can be the number of documents $N$, which is known without being stored. Following Vigna (2013, section 4), set

$$\ell = \max\{0, \lfloor \log_2 (u/n) \rfloor\}.$$

  • The lower bits are the $\ell$ lowest binary digits of each docID, written one after another: $n\ell$ bits.
  • The upper bits describe the high parts $h_i = \lfloor x_i / 2^\ell \rfloor$. For each docID in turn, write $h_i - h_{i-1}$ zeros and then a one, with $h_0 = 0$.

For palladium, $n = 5$ and $u = 10{,}788$, so $u/n = 2157.6$ and $\ell = 11$, since $2^{11} = 2048 \le 2157.6 < 4096$.

docID Binary (14 bits) High part Low 11 bits
1467 00010110111011 0 10110111011
1521 00010111110001 0 10111110001
1792 00011100000000 0 11100000000
1795 00011100000011 0 11100000011
8079 01111110001111 3 11110001111

The lower bits are 10110111011 10111110001 11100000000 11100000011 11110001111, 55 bits. The first four docIDs have high part 0, so each contributes a single one to the upper bits. The fifth has high part 3, so it contributes three zeros and a one. The upper bits are 11110001, 8 bits. The list takes 63 bits, against 64 for variable byte, 77 for the gamma code and 65 for the delta code.

To decode, read the upper bits from the left, counting zeros. Each one met is a docID. Its high part is the number of zeros read so far, and its low part is the next $\ell$ bits of the lower array. The fifth one of 11110001 is met after three zeros, so the fifth docID is $3 \times 2048$ plus the low part 11110001111, which is 1935: $6144 + 1935 = 8079$.

The space bound

Theorem. Let $x_1 \le x_2 \le \dots \le x_n \le u$ be positive integers with $u \ge n$, and let $\ell = \lfloor \log_2(u/n) \rfloor$. The Elias–Fano representation takes exactly

$$n\ell + n + \lfloor x_n / 2^\ell \rfloor \ \text{bits},$$

and this is at most $n\,(2 + \lceil \log_2(u/n) \rceil)$.

The condition $u \ge n$ always holds for a postings list, because $n$ distinct positive docIDs have a largest member of at least $n$. The statement and the argument are Vigna's (2013, section 4), written out in full.

Proof. The lower bits take $n\ell$ bits by construction. The upper bits contain one one for each docID, $n$ in all. The number of zeros is $\sum_{i=1}^{n} (h_i - h_{i-1}) = h_n - h_0 = \lfloor x_n / 2^\ell \rfloor$, because the sum telescopes. That gives the exact size.

For the bound, write $r = u/n \ge 1$. By the choice of $\ell$, $2^\ell \le r < 2^{\ell+1}$. The number of zeros is at most $x_n / 2^\ell \le u / 2^\ell = n\,r/2^\ell$. There are two cases.

  • If $r = 2^\ell$, the number of zeros is at most $n$. The total is at most $n\ell + n + n = n(2 + \ell)$, and $\ell = \log_2 r = \lceil \log_2 r \rceil$.
  • If $r > 2^\ell$, then $r/2^\ell < 2$, so there are fewer than $2n$ zeros. The total is less than $n\ell + 3n = n(2 + (\ell + 1))$, and $\ell + 1 = \lceil \log_2 r \rceil$ because $\log_2 r$ lies strictly between $\ell$ and $\ell + 1$.

In both cases the size is at most $n\,(2 + \lceil \log_2(u/n) \rceil)$. $\blacksquare$

The proof also shows that the upper bits hold $n$ ones and at most $2n$ zeros, whatever the list. For palladium the bound is $5 \times (2 + 12) = 70$ bits and the size is 63. The script checks the exact formula and the bound on each of the 29,187 Reuters lists.

Why this $\ell$. Each extra low bit adds $n$ bits to the lower array and halves the largest possible number of zeros, $u/2^\ell$. Moving from $\ell$ to $\ell + 1$ therefore changes the worst-case size $n\ell + n + u/2^\ell$ by $n - u/2^{\ell+1}$, which is negative exactly when $2^{\ell+1} < u/n$. So the worst-case size falls as long as $2^{\ell + 1} < u/n$ and rises once $2^{\ell+1} > u/n$, and its minimum is at the largest $\ell$ with $2^\ell \le u/n$, the floor above. (When $u/n$ is a power of two, that $\ell$ and the one below it give the same value.) The survey of Pibiri and Venturini (2021, section 3.4) writes the ceiling. For the worst-case size the floor is the minimizer, as just shown: with $u/n = 3$ the floor, $\ell = 1$, gives $3.5n$ bits and the ceiling, $\ell = 2$, gives $3.75n$.

How close to the least possible

The bound says nothing yet about whether a different code could do much better. A counting argument settles it.

There are $\binom{u}{n}$ strictly increasing lists of $n$ docIDs between 1 and $u$. A code that can represent every one of them must give them different bit strings. There are only $2^L - 1$ bit strings shorter than $L$ bits, so if $\binom{u}{n} \ge 2^L$, some list receives at least $L$ bits. Hence no code can keep every such list below $\lfloor \log_2 \binom{u}{n} \rfloor$ bits. And $\binom{u}{n} \ge (u/n)^n$: writing the binomial coefficient as $\prod_{i=0}^{n-1} \frac{u - i}{n - i}$, each factor is at least $u/n$, because $(u - i)\,n \ge u\,(n - i)$ is the same as $iu \ge in$, which holds since $u \ge n$. So

$$\log_2 \binom{u}{n} \ge n \log_2 \frac{u}{n}.$$

Now compare. Write $c = \lceil \log_2(u/n) \rceil$. By the theorem the Elias–Fano size is at most $n(2 + c) = 3n + n(c - 1)$. Since $c - 1 < \log_2(u/n)$, we have $n(c - 1) < n \log_2(u/n) \le \log_2 \binom{u}{n}$, and $n(c - 1)$ is a whole number, so $n(c - 1) \le \lfloor \log_2 \binom{u}{n} \rfloor$. Hence the size is at most $\lfloor \log_2 \binom{u}{n} \rfloor + 3n$: at most three bits per docID above the least that the worst list of that length must cost under any code. This holds for every list, however its gaps are distributed. That much is proved here. The sources state more. Vigna (2013) reports that Elias proved the representation to be less than half a bit per element from optimal, and Pibiri and Venturini (2021, section 3.4) give the same figure. That sharper statement is cited, not derived here.

On Reuters, $\sum_t \log_2 \binom{N}{\mathit{df}_t}$ over all terms comes to 6.28 bits per posting, and Elias–Fano with $u = N$ takes 6.91, which is 0.63 above. For palladium, $\log_2 \binom{10788}{5}$ is 60.1 bits and the code takes 63.

Example (below the entropy of the gaps). The course page computed the entropy of the pooled gap distribution of this index, 7.19 bits, and noted that no single prefix-free code that gives each gap value one codeword can average less. Elias–Fano averages 6.91. There is no contradiction. The 7.19-bit bound applies to codes that give each gap value one codeword for the whole index, and the course page noted that it "says nothing about codes that change from list to list". Elias–Fano is not such a code, for two reasons. Its parameter $\ell$ changes with each list's length, which the dictionary already holds. And it codes the docIDs of a list together, not gap by gap. So the comparison with 7.19 does not show how close Elias–Fano is to any limit. A gap code that may change with the document frequency escapes the 7.19-bit figure too: computed the same way, the entropy of the gaps given the document frequency of their list is 5.96 bits per posting. That figure is optimistic. It is the average length of codes fitted to the very gaps they code, and it leaves out the cost of storing one code table for each document frequency, many of which are shared by only a few lists. Lists drawn at random with the same lengths, which have no clustering at all, give 6.05 [6.05, 6.05] by the same computation (median and quartiles over 30 seeds). So only about a tenth of a bit of the distance below 6.28 comes from the structure of the real lists, and the rest comes from the fitting.

The four numbers therefore bound different things. The 7.19 bits limit prefix-free codes that give each gap value one codeword for the whole index, on these gaps. The 5.96 bits limit such codes when one is allowed per document frequency, again on these gaps and with the code tables free. The counting bound of 6.28 bits is a statement of another kind: no code can keep every list of these lengths below it, but it does not limit what a code spends on the particular lists of Reuters. Elias–Fano itself takes fewer than $\log_2 \binom{N}{\mathit{df}}$ bits on 313 of the 29,187 lists. Its guarantee is stated against that worst case, and on Reuters its 6.91 bits are 0.63 above the counting bound for lists of these lengths.

Skipping without skip pointers

Skip pointers exist because a gap-coded list can only be read from its start. The upper bits of an Elias–Fano list make a different kind of jump possible: the zeros are a table of contents by high part.

To find the first docID that is at least $b$, compute the high part of $b$, $h_b = \lfloor b/2^\ell \rfloor$. Every docID with a smaller high part is smaller than $b$. Those docIDs are exactly the ones whose one comes before the $h_b$-th zero of the upper bits. So jump to just after the $h_b$-th zero, and from there read docIDs in order until one is at least $b$. The number of ones passed on the way is the number of docIDs skipped, which tells where their low parts end in the lower array.

For palladium and $b = 5000$: $h_b = \lfloor 5000/2048 \rfloor = 2$. In 11110001 the second zero is the sixth bit, and four ones precede it, so four docIDs are skipped without their low parts being read. Reading on, one more zero raises the high part to 3, and the next one is the fifth docID, $3 \times 2048 + 1935 = 8079 \ge 5000$. One low part was read. For $b = 1700$ the high part is 0, nothing can be skipped, and the search reads 1467, 1521 and 1792 before it stops, three low parts.

Finding the $h_b$-th zero is the remaining cost. Vigna (2013, section 4) stores a small table of forward pointers into the upper bits, one for every fixed number of zeros, and shows that a skip then takes constant time on average. Pibiri and Venturini (2021, section 3.4) describe the same operation, which they call NextGEQ, with a binary search inside the bucket of $b$. This operation is what WAND and Block-Max WAND ask of a postings list on every step.

What it cannot exploit

The size of an Elias–Fano list depends on $n$, $u$ and the last docID, and on nothing else. That is the guarantee, and it is also the limit. Vigna (2013) lists it as a property: the distribution of the gaps "is irrelevant". Renumbering the documents so that similar ones are adjacent, which makes gaps small and helps every gap code, cannot help it.

Take 1,000 consecutive docIDs at the end of a collection of a million documents. The gamma code spends 39 bits on the first gap and one bit on each of the others, 1,038 bits. Elias–Fano has $u/n = 1000$, so $\ell = 9$, and takes $9{,}000 + 1{,}000 + \lfloor 10^6/512 \rfloor = 11{,}953$ bits, more than eleven times as much.

Two remedies are in the literature. For a list so dense that it holds a large share of all documents, Vigna (2013, section 5) switches to a bitmap of $u$ bits with a small table for counting, which he calls a ranked characteristic function. The fourth worked problem finds where the switch pays. For clustering in general, Ottaviano and Venturini (2014) cut the list into chunks, encode each chunk with Elias–Fano over its own short range, and encode the chunk endpoints with Elias–Fano again. Each chunk then has its own $u$ and $n$, so a run of close docIDs is cheap. They give an algorithm that finds, in linear time, a partition whose size is within any chosen factor of the smallest possible. They report that indexes in plain Elias–Fano were more than 23 percent larger than their partitioned ones on ClueWeb09 and more than 64 percent larger on Gov2, with the partitioned indexes only slightly slower. Those measurements are theirs. Partitioned Elias–Fano was not implemented for this article.

Measured on Reuters-21578

The index is the one of the course page: 10,788 stories, 29,187 terms and 725,793 postings, docIDs in filing order. The first three rows reproduce that page's table. Lists of 128 postings or more are 939 of the 29,187, and they hold 513,500 postings, 70.8 percent of the total. The last column gives the bits per posting within those lists alone, because block codes were designed for long lists.

Encoding Size Bits per posting Bits per posting, lists of 128 or more
Variable byte on gaps 0.868 MB 9.57 8.20
Gamma on gaps 0.783 MB 8.63 5.83
Delta on gaps 0.733 MB 8.08 5.94
Simple-9 on gaps 0.782 MB 8.62 6.19
Binary packing, blocks of 128 0.742 MB 8.18 6.55
Binary packing of full blocks of 128, variable byte for the rest 0.765 MB 8.43 6.59
Binary packing, blocks of 32 0.718 MB 7.91 6.20
Binary packing, blocks of 8 0.720 MB 7.94 6.21
Patched binary packing, blocks of 128 0.710 MB 7.83 5.76
Patched binary packing, blocks of 32 0.739 MB 8.14 6.13
Elias–Fano on docIDs 0.627 MB 6.91 5.37

Several things can be read from the table.

  • Elias–Fano is the smallest, by more than a bit. At 6.91 bits per posting it is 1.18 below the delta code. Its worst-case bound, summed over the lists, is 7.52 bits per posting, already below every other row.
  • Fixed-width blocks alone do not beat the bit-level codes. Binary packing with blocks of 128 lands between the gamma and delta codes over the whole index, and within the long lists both rows for blocks of 128 are larger than every code except variable byte. One width for 128 gaps is expensive when gaps vary.
  • Patching recovers most of that. Patched blocks of 128 take 7.83 bits per posting, and 5.76 within the long lists, a little under the gamma code's 5.83.
  • The treatment of short lists matters as much as the code. Writing the leftover postings as variable bytes, as the Lucene format does, costs a quarter of a bit per posting over packing them as a short block (8.43 against 8.18). On this collection only 63.7 percent of the postings fall in full blocks of 128.
  • Patched blocks of 32 are worse than patched blocks of 128, and worse than plain blocks of 32. The header of two or three bytes is a fixed cost that small blocks cannot spread.

The averages hide how differently the codes treat rare and common terms. Grouping the terms by document frequency, as the course page did for variable byte and gamma:

Document frequency Share of postings Variable byte Gamma Binary packing (128) Patched (128) Elias–Fano
1 1.8% 15.92 23.97 20.49 28.49 14.25
2 to 9 5.5% 14.88 19.52 14.63 16.77 12.78
10 to 99 18.7% 12.51 14.10 11.04 10.90 10.02
100 to 999 41.0% 8.51 8.27 8.12 7.36 6.90
1,000 or more 33.1% 8.00 3.36 4.92 4.09 3.79
Bits per posting for five codes on Reuters-21578, with terms grouped by document frequency and each group's share of all postings in parentheses. Follow the Elias–Fano line: it is the lowest in every group except the last, where the gamma code passes under it. Notice also how far apart the codes are for rare terms, where a list is one or two large numbers, and how the two block codes sit between variable byte and gamma for the most frequent terms.
Bits per posting for five codes on Reuters-21578, with terms grouped by document frequency and each group's share of all postings in parentheses. Follow the Elias–Fano line: it is the lowest in every group except the last, where the gamma code passes under it. Notice also how far apart the codes are for rare terms, where a list is one or two large numbers, and how the two block codes sit between variable byte and gamma for the most frequent terms.

Elias–Fano is the smallest code in every band but the last. A term that occurs in one story costs it 14.25 bits, close to the 13.4 bits that naming one story out of 10,788 must cost ($\log_2 10788 = 13.40$). The gamma code spends 23.97, because the single "gap" is a large number. For terms in a thousand or more stories the gamma code wins, at 3.36 bits against 3.79. There two thirds of the gaps are 1, 2 or 3, and Elias–Fano cannot go below two bits per posting whatever the gaps are. The two lists of the course page show the same pattern:

Code palladium (5 postings) oil (1,038 postings) oil, bits per posting
Variable byte 64 8,304 8.00
Gamma 77 5,728 5.52
Delta 65 6,085 5.86
Simple-9 96 6,528 6.29
Binary packing (128) 73 6,656 6.41
Patched (128) 81 5,972 5.75
Elias–Fano 63 5,499 5.30

For oil, $u/n = 10.39$ and $\ell = 3$. The list takes $3 \times 1038 + 1038$ bits plus one zero for each step of the high part, which ends at $\lfloor 10782/8 \rfloor = 1347$: 5,499 bits, under its bound of 6,228 and above $\log_2 \binom{10788}{1038}$, which is 4,923.

What docID order does to each code

The course page shuffled the docIDs of this index with 30 seeds and found the gamma-coded size rising by about 4 percent. Filing order keeps stories on one subject near each other, which makes gaps small. Repeating that shuffle with the same seeds for the codes of this article gives, in bits per posting:

Encoding Filing order Random order, median [quartiles] of 30
Gamma on gaps 8.63 8.99 [8.98, 8.99]
Binary packing, blocks of 128 8.18 7.97 [7.96, 7.97]
Patched binary packing, blocks of 128 7.83 7.75 [7.75, 7.75]
Elias–Fano on docIDs 6.91 6.92 [6.92, 6.92]

Three behaviors appear. The gamma code gets worse when the order is destroyed, as the course page found. Elias–Fano does not move, which is the property stated above: only the last docID of each list changes its size. And binary packing gets smaller in random order. That may be surprising. A reading consistent with the definition of the code is that filing order produces bursts, with many very small gaps and a few very large ones, and a block pays for its largest gap in every slot. Random order spreads a term's postings evenly, so the gaps of a block are closer in size and the largest is less extreme. Patching, which exists to absorb a few large gaps, shrinks the effect to a tenth of a bit. The experiment shows the three directions. It does not test that explanation against others.

The same codes on this site's index

The search index of this site is not compressed at all. app/search.py keeps its postings as Python dictionaries: for each term, a dictionary from page to field to a list of positions. The site's deploy notes record that each server process uses about a gigabyte, of which this index is one part, and that the size is what prevents running more than one process. A direct measurement shows how much of that is representation.

The script builds the index from the pages as they stood at commit 643484d: 679 pages, 26,905 terms, 472,166 postings (pairs of a term and a page) and 1,678,301 positions. It adds up the memory of every Python object in the postings structure, counting each object once (as CPython 3.11 reports sizes on 64-bit Windows), and then codes the same information: the docIDs of each term by Elias–Fano, or by a bitmap of 679 bits where that is smaller, and for each posting a 5-bit mask of the fields present, and for each field a gamma-coded count and gamma-coded gaps between positions.

Representation of the postings Size
Python dictionaries and lists, as app/search.py holds them 206 MB
DocIDs: gamma codes on gaps 0.27 MB
DocIDs: Elias–Fano, or a bitmap where smaller 0.23 MB
Field masks, counts and positions: gamma codes 3.62 MB

The coded postings come to under 4 megabytes, about a fiftieth of the Python structure. The docIDs take 3.96 bits per posting, less than on Reuters because the collection is small and a term's pages are a large share of it. The positions dominate, at 17.24 bits each including their share of the masks and counts.

This is a measurement of stored size, and it should not be read as a design. A compressed index must be decoded to be used, and a decoder in Python would be far slower than a dictionary lookup. What the numbers establish is narrower. Nearly all of the postings structure's memory is the overhead of Python objects, so a compact layout of the same information, in the codes measured here, would be about two percent of its present size.

What is proved here, what is cited, what the experiment shows

Proved on this page. The exact size of an Elias–Fano list and the bound $n(2 + \lceil \log_2(u/n) \rceil)$; that $\ell = \lfloor \log_2(u/n) \rfloor$ minimizes the worst-case size $n\ell + n + u/2^\ell$; the counting bound $\lfloor \log_2 \binom{u}{n} \rfloor$ and the inequality $\binom{u}{n} \ge (u/n)^n$, which together put Elias–Fano at most three bits per docID above any code's worst case; the size formula of the patched block as defined here; and, in the worked problems, the comparison with the gamma code on evenly spaced lists and the point where a bitmap is smaller.

Cited. The designs of the frame of reference, PFOR and its variants, Simple-9, the grouped variable byte formats, SIMD-BP128 and partitioned Elias–Fano, each as described in the paper named, or in the survey named where the original was not read. Every decoding speed. The statement that Elias–Fano is within half a bit per element of optimal. The properties of Lucene's format.

Measured. Every size in bits, on Reuters-21578 and on this site's index, by a script that also decodes every list. The measurements are of two small collections. The ordering of the codes on a web-scale index with long lists and reordered docIDs is reported in the papers cited and may differ: Reuters has 29,187 lists of which 28,248 are shorter than one block.

Worked problems

The first two problems use the postings list of Exercise 5.6 of the course text (Manning, Raghavan, and Schütze, 2008), which the course page encoded with variable byte and gamma codes; the last two are posed on constructed lists. The script recomputes every number.

Problem 1 (Elias–Fano by hand). Encode the postings list 4, 10, 11, 12, 15, 62, 63, 265, 268, 270, 400 with Elias–Fano, taking $u = 400$. Compare the size with the bound, with the counting bound, and with the gamma and variable byte codes. Then find the first docID that is at least 100.

Solution. The list takes 78 bits. Here $n = 11$ and $u/n = 36.36$, so $\ell = 5$, since $32 \le 36.36 < 64$. Each docID splits into a high part $\lfloor x/32 \rfloor$ and its five low bits:

docID High part ($\lfloor x / 32 \rfloor$) Low 5 bits
4 0 00100
10 0 01010
11 0 01011
12 0 01100
15 0 01111
62 1 11110
63 1 11111
265 8 01001
268 8 01100
270 8 01110
400 12 10000

The lower bits are 00100 01010 01011 01100 01111 11110 11111 01001 01100 01110 10000, 55 bits. For the upper bits, five docIDs have high part 0 (five ones), then the high part rises by 1 (one zero) for two docIDs (two ones), by 7 (seven zeros) for three docIDs, and by 4 (four zeros) for the last: 11111011000000011100001, 23 bits, made of 11 ones and 12 zeros. The exact formula agrees: $11 \times 5 + 11 + \lfloor 400/32 \rfloor = 55 + 11 + 12 = 78$.

The bound is $11 \times (2 + \lceil \log_2 36.36 \rceil) = 11 \times 8 = 88$ bits. The counting bound is $\log_2 \binom{400}{11} = 69.6$ bits. The course page found 63 bits for the gamma code and 104 for variable byte on the same list. So the gamma code is smaller here, and smaller than the counting bound. That is no contradiction either. The counting bound limits what a code can guarantee for every list of 11 docIDs up to 400, and this list, with its runs of adjacent docIDs, is far from the worst. Elias–Fano spends about the same on every list of this length. The gamma code spends less on clustered lists and more on spread ones.

For the first docID that is at least 100, $h_b = \lfloor 100/32 \rfloor = 3$. The third zero of the upper bits is its tenth bit, and seven ones precede it, so seven docIDs are skipped. Reading on, five more zeros bring the high part to 8, and the next one is the eighth docID, with low part 01001: $8 \times 32 + 9 = 265$. One low part was read.

Problem 2 (the same list in blocks). Encode the gaps of the same list, 4, 6, 1, 1, 3, 47, 1, 202, 3, 2, 130, as one binary-packed block, as one patched block, and in Simple-9.

Solution. All three take 96 bits. The largest gap, 202, has eight binary digits, so binary packing takes $8 + 11 \times 8 = 96$ bits. For the patched block, the gaps need 3, 3, 1, 1, 2, 6, 1, 8, 2, 2 and 8 bits, so $w_{\max} = 8$, and the size formula gives:

Width $w$ Exceptions Block size in bits
8 0 104
7 2 119
6 2 110
5 3 112
4 3 104
3 3 96
2 5 116

At $w = 3$ the three exceptions are 47, 202 and 130, and the block takes $16 + 33 + 8 + 3 \times (8 + 5) = 96$ bits. The packed part has fallen from 88 bits to 33, and the header and the patches have taken back exactly the difference from binary packing. Widths of 1 and 0 cost more still, 155 and 200 bits. In Simple-9, layouts 0 to 3 would each take more than five gaps, and the sixth gap, 47, needs six bits, so the first word takes layout 4: the five gaps 4, 6, 1, 1, 3 at five bits each. The gaps 47, 1 and 202 fill a word of layout 6 (three gaps of nine bits), and 3, 2 and 130 another. Three words are 96 bits. On eleven gaps the block codes tie with each other and lose to the gamma code's 63 bits. Their overheads, a header or a word boundary, are paid once per block, and a short list has little to spread them over.

Problem 3 (evenly spaced and clustered lists). A term occurs in every $g$-th document: its docIDs are $g, 2g, \dots, ng$, and $u = ng$. For which $g$ is Elias–Fano smaller than the gamma code, per posting?

Solution. For every $g \ge 4$; the two tie at $g = 2$, and the gamma code is smaller for $g = 1$ and $g = 3$. Here $u/n = g$, so $\ell = \lfloor \log_2 g \rfloor$, and the last docID is $u$, so the number of zeros is $\lfloor ng/2^\ell \rfloor$. Per posting, and ignoring the rounding of that one count, Elias–Fano takes

$$\ell + 1 + \frac{g}{2^\ell} \ \text{bits},$$

and $1 \le g/2^\ell < 2$, so this lies between $\ell + 2$ and $\ell + 3$. Every gap is $g$, and its gamma code takes $2\ell + 1$ bits. Elias–Fano is smaller exactly when $\ell + 1 + g/2^\ell < 2\ell + 1$, that is, when $g/2^\ell < \ell$. For $\ell \ge 2$, which means $g \ge 4$, the left side is below 2 and the inequality holds. For $\ell = 1$ it reads $g/2 < 1$, false for $g = 2$ (where the two sides are equal and the codes tie at 3 bits) and for $g = 3$. For $\ell = 0$, $g = 1$, Elias–Fano takes 2 bits and the gamma code 1. The script confirms it with $n = 1{,}000$:

Gap $g$ Gamma bits per posting Elias–Fano bits per posting
1 1 2.00
2 3 3.00
3 3 3.50
4 5 4.00
8 7 5.00
10 7 5.25
16 9 6.00
100 13 8.56
1,000 19 11.95

The gamma code pays twice the logarithm of the gap and Elias–Fano pays the logarithm plus about two, so the advantage grows with the gap. Evenly spaced lists are the best case for Elias–Fano. The run of 1,000 consecutive docIDs at the end of a million, in the text above, is the opposite case: 1,038 bits for the gamma code and 11,953 for Elias–Fano. The same run takes 3,496 bits in binary-packed blocks of 128 and 1,163 in patched blocks, where the one large gap becomes a single exception.

Problem 4 (when a bitmap is smaller). A list of $n$ docIDs out of $u$ documents can also be stored as a bitmap: $u$ bits, with bit $x$ set when docID $x$ is in the list. For which densities is the bitmap no larger than the Elias–Fano bound? How many Reuters lists does that concern?

Solution. The bitmap is no larger than the bound exactly when the list holds at least a fifth of the documents, $u/n \le 5$. Per docID the bitmap costs $u/n$ bits and the bound is $2 + \lceil \log_2(u/n) \rceil$:

$u/n$ Elias–Fano bound, bits per element Bitmap, bits per element
1 2 1
2 3 2
3 4 3
4 4 4
5 5 5
8 5 8
16 6 16

Write $r = u/n$ and $c = \lceil \log_2 r \rceil$, so that $r \le 2^c$ and the bound is $2 + c$. If $c \le 2$, that is $r \le 4$, then $r \le 2^c \le 2 + c$, since $1 \le 2$, $2 \le 3$ and $4 \le 4$: the bitmap is no larger, and the two are equal only at $r = 4$. If $c = 3$, that is $4 < r \le 8$, the bound is 5, and the bitmap is no larger exactly when $r \le 5$. If $c \ge 4$, then $r > 2^{c-1} \ge 2 + c$, because $2^{c-1} \ge 2 + c$ holds at $c = 4$ (8 against 6) and the left side doubles with each step of $c$ while the right side grows by one. The bitmap is then larger. So the bitmap is at most the bound for $r \le 5$ and larger beyond.

In Reuters, compare the bitmap's 10,788 bits with each list's actual Elias–Fano size. The bitmap is smaller for 32 terms, the least frequent of which occurs in 2,804 stories, a little over a quarter of the collection. Those 32 lists hold 139,976 postings. The term the occurs in 6,951 stories: Elias–Fano takes 17,739 bits, the bitmap 10,788, and the gamma code 12,099. Using the bitmap for those 32 lists and Elias–Fano for the rest brings the index from 6.91 to 6.78 bits per posting. This is the simplest case of choosing a representation by density, the idea that partitioned Elias–Fano applies chunk by chunk.

What we have learned

A list compressor fixes one layout for a run of integers, so that a decoder need not inspect each one to find the next. Binary packing gives a block the width of its largest gap; patching lowers the width and stores the few gaps that do not fit as exceptions, with a size that can be written down and minimized. Simple-9 and the vector layouts rearrange the same bits for the machine. Elias–Fano stores docIDs by their high and low parts in at most $2 + \lceil \log_2(u/n) \rceil$ bits each, at most three bits above any code's worst case, and its upper bits serve as their own skip structure. On Reuters-21578 it was the smallest code, at 6.91 bits per posting against 8.08 for the delta code and 7.83 for patched blocks. It was indifferent to docID order, where the gamma code needs clustering and binary packing was hurt by it.

Every code here was applied to a list that is complete when it is encoded. A block's width, an exception table and the parameter $\ell$ of an Elias–Fano list are all fixed by the whole block or the whole list. The next article, Updating an Index, asks what an engine does when documents keep arriving and such a list is never finished.

References

  • Anh, V. N., and Moffat, A. (2005). Inverted index compression using word-aligned binary codes. Information Retrieval, 8(1), 151–166. record · 2 pages
  • Apache Software Foundation (2023). Apache Lucene 9.9.0 API documentation: Lucene99PostingsFormat. https://lucene.apache.org/core/9_9_0/core/org/apache/lucene/codecs/lucene99/Lucene99PostingsFormat.html record · 4 pages
  • Apache Software Foundation (2025). Apache Lucene 10.3.0 core API documentation: Lucene103PostingsFormat. https://lucene.apache.org/core/10_3_0/core/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.html record · 2 pages
  • Elias, P. (1974). Efficient storage and retrieval by content and address of static files. Journal of the ACM, 21(2), 246–260. record
  • Fano, R. M. (1971). On the number of bits required to implement an associative memory. Memorandum 61, Computer Structures Group, Massachusetts Institute of Technology. record
  • Goldstein, J., Ramakrishnan, R., and Shaft, U. (1998). Compressing relations and indexes. In Proceedings of ICDE 1998, 370–379. record
  • Lemire, D., and Boytsov, L. (2015). Decoding billions of integers per second through vectorization. Software: Practice and Experience, 45(1), 1–29. record · 2 pages
  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 5. Cambridge University Press. record · 102 pages
  • Ottaviano, G., and Venturini, R. (2014). Partitioned Elias-Fano indexes. In Proceedings of SIGIR 2014, 273–282. record
  • Pibiri, G. E., and Venturini, R. (2021). Techniques for inverted index compression. ACM Computing Surveys, 53(6), article 125. record · 3 pages
  • Stepanov, A. A., Gangolli, A. R., Rose, D. E., Ernst, R. J., and Oberoi, P. S. (2011). SIMD-based decoding of posting lists. In Proceedings of CIKM 2011, 317–326. record
  • Vigna, S. (2013). Quasi-succinct indices. In Proceedings of WSDM 2013, 83–92. record
  • Yan, H., Ding, S., and Suel, T. (2009). Inverted index compression and query processing with optimized document ordering. In Proceedings of WWW 2009, 401–410. record
  • Zukowski, M., Héman, S., Nes, N., and Boncz, P. (2006). Super-scalar RAM-CPU cache compression. In Proceedings of ICDE 2006, 59. record · 2 pages