Delta Encoding and Variable-Byte Postings

A postings list of absolute document identifiers has an obvious inefficiency: every entry is roughly as large as the full identifier range, because the high-order bytes rarely change. A collection of ten million documents needs 24 bits per identifier, and an uncompressed list spends all 24 on each entry even though consecutive identifiers differ by small amounts. Storing the difference between successive identifiers removes the shared high-order part entirely, and the distribution of those differences — mostly small, occasionally huge — is the thing that makes variable-length codes worth their complexity.

What the differences look like

Take a term appearing in documents 3, 17, 18, 45, 91. The absolute list is five 24-bit numbers. The differences, with an implied starting point of zero, are 3, 14, 1, 27, 46. Each of those fits in a single byte, so the representation drops from 15 bytes to 5.

The gain is not that every gap is small. It is that gaps are small where postings are dense, and postings are dense exactly for the terms that dominate index size. A term appearing in a tenth of the collection has an average gap of ten, which needs four bits in a fixed scheme or one byte in a byte scheme. A term appearing in three documents spread over ten million has average gap in the millions and gets no benefit at all. Since a handful of very frequent terms account for most postings, the aggregate saving is large even though rare terms see none.

The distribution is approximately geometric for randomly placed postings, and real collections make it heavier-tailed than geometric: bursty topics create runs of adjacent documents, producing gaps of one, and rare terms in the tail produce gaps in the tens of thousands. A code tuned for the geometric mean copes badly with the tail, and a code tuned for the tail wastes bits on the body. This tension is the whole subject of postings compression, and every scheme described in this cluster is a different resolution of it.

The vByte layout and its continuation bit

Variable-byte encoding, usually written vByte or VB, packs an integer into a sequence of bytes in which the high bit of each byte is a continuation flag. Seven bits of payload per byte; the high bit set means another byte follows. Little-endian order within the number is conventional: the least significant seven bits come first, so the low bits are available before the whole number has been read.

/* Encode n into out; returns bytes written. Little-endian 7-bit groups. */
size_t vbyte_encode(uint32_t n, uint8_t *out) {
    size_t i = 0;
    while (n >= 0x80) {
        out[i++] = (uint8_t)((n & 0x7F) | 0x80);   /* continuation set */
        n >>= 7;
    }
    out[i++] = (uint8_t)n;
    return i;
}

/* Decode one integer; *pos advances past it. */
uint32_t vbyte_decode(const uint8_t *in, size_t *pos) {
    uint32_t n = 0;
    int shift = 0;
    while (in[*pos] & 0x80) {
        n |= (uint32_t)(in[*pos] & 0x7F) << shift;
        shift += 7;
        (*pos)++;
    }
    n |= (uint32_t)in[*pos] << shift;
    (*pos)++;
    return n;
}

The cost per integer is one byte for values up to 127, two bytes up to 16,383, three up to 2,097,151, and four up to the 32-bit range. For a term with average gap of ten, that is one byte per posting, which is eight times denser than the absolute 32-bit form and four times denser than a 24-bit one.

The inefficiency is the flag bit. Seven-eighths of a byte is payload, so a byte-aligned integer carries 12.5 percent overhead before any other consideration. A four-bit gap stored in a byte wastes half the byte. This is why vByte is a baseline rather than an optimum, and why schemes that pack bits tightly — bit packing with frame-of-reference blocks — beat it on dense lists.

Decoding cost and branch prediction

Each decoded integer requires a run of byte loads with a data-dependent loop exit. The branch on the continuation bit is hard to predict: for a run of one-byte integers the predictor learns the pattern, but a mixture of one- and two-byte values makes every exit a potential misprediction. A mispredicted branch costs in the neighbourhood of fifteen to twenty cycles on current cores, which is more than the arithmetic of decoding.

The standard remedies are branch-free decoding and unconditional multi-byte loads. If the decoder always reads four bytes into a register — safe when the buffer is padded at the end, or when the read stays within the final cache line — and locates the terminating byte with a bit-scan over the masked high bits, the data-dependent loop disappears and the pipeline stays full. The number of bytes to advance becomes a function of the count of continuation bits, computed with one instruction. Implementations that use this structure can decode several integers per cycle across independent lanes, since gaps within a block are not serially dependent.

Serial dependence is the other structural limit. A gap cannot be decoded until its starting document identifier is known, and that requires all preceding gaps. This makes the decode of a block inherently sequential, defeating the instruction-level parallelism the branch-free form enables on paper. The usual fix is to decode the compressed gaps in parallel and separate the prefix-sum from the decode step, so that the sum is a short dependent chain over already-decoded values.

Blocking and skip pointers

Pure vByte has no random access. A cursor cannot be placed at an arbitrary posting without decoding from the start of the list, because byte offsets of interior postings are not recorded.

The fix is a skip structure. Every fixed number of postings — 128 is a common choice, and 64 shows up where more granularity pays — the encoder records the absolute document identifier and the byte offset. To advance to identifier d, the reader binary-searches the skip entries for the largest recorded identifier below d, seeks to its byte offset, and decodes forward at most one block.

The absolute identifiers in the skip array are the reason the block boundary needs an absolute value rather than a gap: a reader that lands mid-list has no predecessor to add to. Skipping costs a search over a small sorted array, whose size is the list length divided by the block size, so it stays in cache and is cheap.

Blocking has a compression cost. The first posting of each block stores a full absolute identifier rather than a gap from the previous block, which for 24-bit identifiers adds three bytes per 128 postings — a fraction of a percent, and the block offsets add a few more bytes. The trade is worthwhile in any index that needs conjunctions of terms with very different document frequencies, which is nearly all of them.

Relationship to the other codes

vByte sits between two extremes. Fixed-width bit packing per block is faster to decode and, for dense lists with small gaps, smaller; it needs the block maximum to choose a width, so it is intrinsically blocked and intrinsically better on dense postings. Bit-level codes like Golomb and Rice are smaller still on geometric gap distributions but slower per decoded value because they read a variable number of unaligned bits. Elias-Fano achieves near-optimal space for the whole list with random access built in, at a cost dominated by a bit-select primitive.

The choice of code interacts with the evaluation strategy. A term-at-a-time evaluator reads long runs of postings in order and never seeks, so it prefers the smallest code regardless of decode speed. A document-at-a-time evaluator with short, dispersed lists seeks constantly and prefers cheap random access, which biases toward vByte with skips, or toward small blocks. Document-at-a-time and term-at-a-time evaluation follows this ordering.

Where the scheme breaks down

Three failure modes are worth naming.

Long lists of tiny gaps: a gap of one stored in a full byte wastes seven bits, and the byte-aligned form cannot exploit that. Dense lists want sub-byte packing, and the crossover is somewhere around an average gap of a few units.

Lists of huge gaps: identifiers above 2,097,151 take three bytes and above 268 million take four, and the savings over fixed-width vanish. More importantly, for terms with a handful of postings total, the decode overhead and skip array cost more than the entropy of the list saves, so a threshold below which the list is stored uncompressed is a common degenerate-case guard.

Non-monotone data: if the sequence is not sorted, differences can be negative. Encoders that work on document identifiers are safe because the ordering is an invariant enforced at build time, but the same class of code applied to positions inside a document requires that positions be sorted too. A block-structured format that stores payloads out of order loses the delta property entirely, and the fallback is absolute storage for the affected regions.

Finally, a vByte decoder trusts the input. A truncated block, or a block whose last integer has its continuation bit set, runs the decoder past the buffer. Since index files are memory-mapped, the practical consequence is a read into the next block rather than a crash, and the last integer decodes to garbage. Block framing, with each block’s byte length recorded, makes truncation detectable; formats without lengths rely on the index being written correctly once and never edited.