Delta and frame of reference

What do delta and frame-of-reference encodings bet on, and what happens when the bet fails?

Delta and delta-of-delta

Idea. Store xᵢ − xᵢ₋₁ (the difference from the previous value). The number of bits needed falls from log₂(max value) to log₂(max delta).

Delta-of-delta takes the difference of the differences. For a regular series, the second difference is 0, and a zero can be run-length encoded away or given a one-bit code.

timestamps:        1000  1001  1002  1003  1005  1006
delta:                    1     1     1     2     1
delta-of-delta:                 0     0     1    -1

The Gorilla paper (Facebook's in-memory metrics database) reports that 96% of timestamps compress to a single bit on its metrics workload.

There are two boundary conditions. Both are routinely ignored.

1. Delta costs about one extra bit per value on uncorrelated data (derived above). It is a bet, not a free transformation. A series with irregular intervals gets a small fraction of the advertised benefit. The "12× overall" figure from Gorilla belongs to regularly sampled metrics, not to time series in general. It is one of the most over-generalized numbers in this field.

2. Delta destroys random access. To decode value i you must add up all deltas since the last absolute value (a prefix sum). This is the same dependency chain we met with varints in Serialization, in a different form. The fix is also the same: restart with an absolute value every B entries. This bounds the dependency chain and restores random access at block granularity. The restart interval is the access granularity: you are choosing the amplification factor yourself (decode up to B values to read one). The values chosen in practice are around 64–128, for the cache-line and SIMD-width reasons that appear again below.

SIMD prefix sums exist. They need a logarithmic number of shuffle steps, so vectorized delta decoding is perhaps 4–8× slower than a plain copy, not 100× slower. It is a real cost, not a disqualifying one.

Frame of reference (FOR) and PFOR

FOR stores the minimum of a block once, and then each value as (x − min) in ⌈log₂(max − min + 1)⌉ bits.

This looks like delta, but it is structurally its opposite. The reference is a constant for the block, not the previous value. So decoding value i touches only value i. FOR keeps random access; delta does not. They are usually taught together, and this most important difference is usually left out.

The failure case

Now put one value of 2³¹ in that block. The range becomes about 2³¹, so all 128 values need 31 bits, not 8. You lose about 3.9× of your ratio (31 ÷ 8). The cost of the block is set by its maximum, so 0.8% of the data (1 of 128 values) decides 100% of the width. This is the principle "variance costs more than volume" in its most literal form. It is not an analogy: the cost function is N × log₂(max), and the maximum is a tail statistic (it depends only on the single most extreme value).

PFOR: patched frame of reference

The response is more important than the mechanism. PFOR (Patched FOR) chooses a width that covers, say, the 90th percentile of the values, and stores the remainder as exceptions (position plus full value) in a separate patch list. The total cost becomes

RelationshipPatched frame of reference →

N \times w + e \times (w_{full} + w_{pos})

$w$: the chosen width
$e$: the number of exceptions
$w_{full}$: the bits for a full value
$w_{pos}$: the bits for a position inside the block

Principle: Variance costs more than volume →

where w is the chosen width, e is the number of exceptions, w_full is the bits for a full value and w_pos is the bits for a position inside the block. You pick w by evaluating this expression for each of at most 64 candidate widths, using the block's bit-width histogram (how many values need 1 bit, 2 bits, ...). That is cheap to compute.

Worked example

The block above with one outlier: choose w = 8. Then N × w = 128 × 8 = 1,024 bits. One exception costs 31 bits (value) + 7 bits (position in 128 slots) = 38 bits. Total 1,062 bits, against 128 × 31 = 3,968 bits for plain FOR. That is 3.7× smaller.

def pfor_cost(values, w, full_bits=32, pos_bits=7):
    limit = 1 << w
    exceptions = sum(1 for v in values if v >= limit)
    return len(values) * w + exceptions * (full_bits + pos_bits)

best_w = min(range(1, 33), key=lambda w: pfor_cost(block, w))   # 'block' holds offsets from the minimum

This is a general rule: specialize on the realized distribution, then exile the violations to a second path. It has two parts that follow from each other. First, declared types are upper bounds, not descriptions. Every encoder that inspects actual values recovers compression that the schema gave away: dictionary encoding recovers the real cardinality, FOR the real range, and ALP the real type. Second, because specialization is fragile to outliers, it must be paired with an exception path or it fails on the tail. PFOR's patch list and the dictionary's fallback to plain are that path. The idea is not limited to compression: a JIT compiler's inline cache observes the real types at a call site, emits specialized code, and "deoptimizes" (falls back to general code) when a different type appears. One idea, built independently by people who did not read each other's papers.