Delta encoding

Deep dive

How it works

In: a sequence of integers (sorted, or sampled at regular steps) · Out: the first value followed by small, zigzag-mapped differences · State: the previous value (the running sum when decoding) · Cost: O(n); encode is 1 subtraction per value, decode a serial prefix sum

1. Delta: d[0] = v[0], d[i] = v[i] − v[i−1]. Use wrapping arithmetic so any input round-trips.
2. Zigzag for signed deltas: (d << 1) ^ (d >> 63) maps small magnitudes of either sign to small unsigned numbers.
3. Delta-of-delta: dd[i] = d[i] − d[i−1] for regular sampling.
4. Frame of reference (FOR): per block, subtract the block minimum (or minimum delta) and bit-pack the remainder; Parquet's DELTA_BINARY_PACKED does delta + FOR + bit packing.
5. Decode with a prefix sum; restart at block boundaries (store the first value per block) to allow random access and parallelism.

values   1000 1010 1020 1031 1040
delta       -   10   10   11    9     (first value stored raw)
dod         -    -    0    1   -2     (first delta stored raw) -> zigzag 0 2 3

Code

#[inline] pub fn zigzag(v: i64) -> u64 { ((v << 1) ^ (v >> 63)) as u64 }
#[inline] pub fn unzigzag(u: u64) -> i64 { ((u >> 1) as i64) ^ -((u & 1) as i64) }

fn put_varint(out: &mut Vec<u8>, mut v: u64) {
    while v >= 0x80 { out.push(v as u8 | 0x80); v >>= 7; }
    out.push(v as u8);
}
fn get_varint(buf: &[u8], pos: &mut usize) -> u64 {
    let (mut v, mut shift) = (0u64, 0);
    loop {
        let b = buf[*pos];
        *pos += 1;
        v |= ((b & 0x7F) as u64) << shift;
        if b < 0x80 { return v; }
        shift += 7;
    }
}

/// order = 1: delta; order = 2: delta-of-delta. Zigzag + varint on top.
pub fn encode(vals: &[i64], order: usize) -> Vec<u8> {
    let (mut out, mut prev, mut prev_d) = (Vec::new(), 0i64, 0i64);
    for &v in vals {
        let d = v.wrapping_sub(prev);
        let r = if order == 2 { d.wrapping_sub(prev_d) } else { d };
        put_varint(&mut out, zigzag(r));
        (prev, prev_d) = (v, d);
    }
    out
}

pub fn decode(buf: &[u8], n: usize, order: usize) -> Vec<i64> {
    let (mut pos, mut prev, mut prev_d) = (0, 0i64, 0i64);
    (0..n).map(|_| {
        let r = unzigzag(get_varint(buf, &mut pos));
        let d = if order == 2 { prev_d.wrapping_add(r) } else { r };
        prev = prev.wrapping_add(d);
        prev_d = d;
        prev
    }).collect()
}

/// D4 delta for u32 lanes: each value minus the one 4 positions back.
/// Decoding is one 4-wide vector add per 4 values (no serial prefix sum).
pub fn d4_encode(v: &[u32]) -> Vec<u32> {
    (0..v.len()).map(|i| if i < 4 { v[i] } else { v[i].wrapping_sub(v[i - 4]) }).collect()
}

pub fn d4_decode(d: &[u32]) -> Vec<u32> {
    let mut out = d.to_vec();
    for i in 4..out.len() { out[i] = out[i].wrapping_add(out[i - 4]); } // dependency distance 4: vectorizes
    out
}

Complexity and constants

• Delta encode: 1 subtract per value, fully parallel. Decode: prefix sum, a serial chain of adds at ~1 cycle each when scalar; SIMD in-register prefix sums (log2(lanes) shift+add steps) reach several values per cycle.
• After delta, the bits needed are ~log2(average gap) for sorted lists. Rule of thumb for posting lists: dense terms need 1-4 bits/doc, rare terms 10-20.
• Gorilla's delta-of-delta on regular timestamps: about 96 % of timestamps compressed to a single bit in Facebook's data.
• Binary delta (bsdiff, Courgette, zstd --patch-from): patch size scales with the change, not the file, so small updates ship as a few % of the compressed file.

Efficiency

• Cost: encode is 1 subtract per value and fully parallel; decode is a prefix sum, a serial chain of adds at about 1 cycle each when scalar, while SIMD in-register prefix sums (log2(lanes) shift+add steps) reach several values per cycle. After delta a sorted list needs about log2(average gap) bits per value: dense posting-list terms 1-4 bits per doc, rare terms 10-20. Bound: the serial dependency of the prefix sum once unpacking is fast.
• Levers:
  • D4 deltas (difference to the value 4 back) — SIMD-friendly decode for a little ratio — after a fast SIMD unpacker
  • blocks of 128-1024 with a stored first value — parallel decode and skipping — random access
  • fuse the prefix sum with the scan or intersection — no decoded array in memory — query paths
  • store d − 1 for distinct sorted values — saves a bit on dense lists — posting lists
  • delta-of-delta for regular sampling — about 96 % of timestamps in one bit in Facebook's data (Gorilla) — fixed-interval series
• Naive → standard → state of the art:
  • raw 32/64-bit values · full width per value
  • delta + zigzag + varint · 1-2 bytes per small gap
  • delta + FOR + bit packing with SIMD prefix sums · a few bits per value at billions of values per second

Implementation notes

• Blocks of 128-1024 values with the first value (or a checkpoint) stored per block: random access by skipping blocks, SIMD-friendly bit widths per block.
• Min-delta subtraction (Parquet): store min delta per block, so slightly decreasing data does not need zigzag.
• Sorted lists: store d − 1 (gaps are ≥ 1 when values are distinct), saving a bit in dense lists.
• Fuse decode with use: compute the prefix sum while intersecting or scanning, instead of materializing a decoded array.
• Floats: never delta raw float bits arithmetically; use XOR (Gorilla) or scale to integers first (e.g., price in cents).

Pitfalls

• Overflow: v[i] - v[i-1] overflows for i64 extremes; use wrapping arithmetic on both sides (the code above does).
• Unsorted input to an encoder that assumes non-negative gaps: huge unsigned deltas, or corrupted data if the codec assumes monotonicity.
• One corrupted delta corrupts every later value in the block; checksum blocks.
• Delta on data that is already noisy (random low bits): no gain, and zigzag adds one bit.
• Serial prefix sum becomes the bottleneck after a fast SIMD unpacker; consider D4 or fused decoding.

Variants and alternatives

In production

Databases and file formats: Parquet DELTA_BINARY_PACKED, ORC RLE v2, ClickHouse Delta/DoubleDelta codecs, TimescaleDB. Search: Lucene postings (doc ID gaps in blocks of 128). Time-series monitoring: Prometheus and Gorilla timestamps (delta-of-delta). Images and software distribution: PNG filters, git packfile deltas, Chrome's Courgette/Zucchini updates.

Implementations

Sources

• D. Lemire, L. Boytsov, Decoding billions of integers per second through vectorization, Software: Practice and Experience, 2015. paper · arXiv
• T. Pelkonen et al., Gorilla: A Fast, Scalable, In-Memory Time Series Database, VLDB, 2015. paper
• D. Korn, J. MacDonald, J. Mogul, K. Vo, RFC 3284: The VCDIFF Generic Differencing and Compression Data Format, 2002. RFC
• C. Percival, Naive Differences of Executable Code, 2003. page
• Apache Parquet, Encodings.md (DELTA_BINARY_PACKED), github.com/apache/parquet-format. spec