Delta Encoding for Time-Series and Sorted Data

Introduction

Delta encoding is a compression technique that replaces absolute values with the differences between consecutive elements. When data exhibits locality (values that are close together in magnitude or that increase monotonically), these differences are small, and small integers compress far more efficiently than large ones. This makes delta encoding a foundational building block in time-series databases, columnar storage engines, and any system that stores sorted sequences.

The technique itself is simple. Its power comes from how it composes with downstream encodings like variable-length integer encoding (varint), bit-packing, and run-length encoding (RLE). A column of monotonically increasing 64-bit timestamps might require 8 bytes per value when stored raw. After delta encoding, the differences may fit in 1 or 2 bytes, or collapse into RLE runs when the interval is constant. This composition is what makes delta encoding essential rather than merely convenient.

Core Mechanism

Given a sequence of values v₀, v₁, v₂, ..., vₙ, delta encoding produces:

d₀ = v₀           (the base value, stored as-is)
dᵢ = vᵢ - vᵢ₋₁    for i > 0

Decoding is the prefix sum:

v₀ = d₀
vᵢ = vᵢ₋₁ + dᵢ    for i > 0

For sorted data, all deltas are non-negative. For time-series data with a regular sampling interval, most deltas are identical. Both properties are exploitable by downstream encoders.

Delta-of-Delta Encoding

When values follow a roughly linear trend (e.g., timestamps sampled at a near-constant rate), the first-order deltas themselves form a near-constant sequence. Applying delta encoding a second time yields delta-of-delta values that cluster tightly around zero. Facebook's Gorilla paper demonstrated this for timestamp compression in their in-memory time-series database, achieving an average of 1.37 bytes per data point (combining both timestamp and value encoding) across entire time-series blocks.

Given first-order deltas d₁, d₂, ..., dₙ:

dd₁ = d₁           (store first delta as-is)
ddᵢ = dᵢ - dᵢ₋₁    for i > 1

For perfectly regular timestamps (e.g., one sample every 60 seconds), all delta-of-delta values are zero, and the entire block compresses to just the base value plus the first delta.

Algorithm

Delta Encoding with Bit-Packing

The following walkthrough describes the encoding pipeline used in systems like Apache Parquet and InfluxDB's TSM engine.

Step 1: Compute deltas.

Input:  [1000, 1003, 1005, 1010, 1010, 1015, 1021]
Deltas: [1000, 3, 2, 5, 0, 5, 6]

Step 2: Store the base value (first element) separately, using its full width.

Base value: 1000 (stored as 64-bit integer or varint)
Remaining deltas: [3, 2, 5, 0, 5, 6]

Step 3: Determine the minimum number of bits needed to represent the largest delta.

max(3, 2, 5, 0, 5, 6) = 6
bits_needed = ceil(log2(6 + 1)) = 3 bits

Edge case: if all deltas are identical (max_delta = 0), bits_needed = 0, and the delta stream can be represented by a single value with a count — effectively RLE.

Step 4: Bit-pack the remaining deltas (count - 1 values) using the computed width.

Header: base=1000, count=7, bit_width=3
Body: [011, 010, 101, 000, 101, 110]  (3 bits each, packed contiguously)
       ^--- 6 deltas (count-1), not 7

Step 5: Write the header and body to the output buffer.

Total storage: 8 bytes (base) + 1 byte (header metadata) + ceil(6 × 3 / 8) = 3 bytes for body (18 bits packed into 3 bytes). Roughly 12 bytes for 7 values that would otherwise require 56 bytes as raw int64s.

Pseudocode: Encode

function delta_encode(values):
    if values is empty:
        return empty

    base = values[0]
    deltas = []
    for i in 1..len(values)-1:
        deltas.append(values[i] - values[i-1])

    if all deltas are non-negative:
        # Sorted or monotonic data: use unsigned bit-packing
        max_delta = max(deltas)
        bit_width = max_delta > 0 ? ceil(log2(max_delta + 1)) : 0
    else:
        # Non-monotonic: use zigzag encoding, then bit-pack
        zigzag_deltas = [zigzag_encode(d) for d in deltas]
        max_delta = max(zigzag_deltas)
        bit_width = max_delta > 0 ? ceil(log2(max_delta + 1)) : 0
        deltas = zigzag_deltas

    write_header(base, len(values), bit_width)
    bitpack_write(deltas, bit_width)

The zigzag encoding step (mapping signed integers to unsigned via (n << 1) ^ (n >> 63), where >> is an arithmetic right shift) is critical for non-monotonic sequences. Without it, negative deltas require sign bits that inflate the bit width for the entire block. Note: the arithmetic right shift behavior must be guaranteed by the implementation language or handled explicitly.

Pseudocode: Decode

function delta_decode(buffer):
    base, count, bit_width = read_header(buffer)
    deltas = bitpack_read(buffer, count - 1, bit_width)

    values = [base]
    for d in deltas:
        values.append(values[-1] + d)
    return values

Decoding is a sequential prefix sum. This has implications for random access, discussed below.

Composition with Other Encodings

Delta encoding rarely appears in isolation. The practical compression ratios come from layering it with complementary techniques.

Delta + RLE. If many consecutive deltas are identical (common with regular-interval timestamps), run-length encoding the delta stream is highly effective. Apache Parquet's DELTA_BINARY_PACKED encoding uses a hybrid of delta and miniblock bit-packing, while InfluxDB applies delta + RLE for timestamp columns.

Delta + Varint. Protocols like Protocol Buffers and storage formats like LevelDB's block format use delta encoding followed by variable-length integer encoding. Small deltas encode in 1 byte; large ones expand as needed.

Delta + Frame-of-Reference (FOR). Instead of computing deltas against the previous element, FOR subtracts a per-block minimum value from all elements. Delta encoding and FOR can be combined: compute deltas, then subtract the minimum delta from all deltas within a block, and bit-pack the residuals. This is the approach used in the PFOR and FastPFOR families of integer compression.

Delta-of-delta + XOR (Gorilla). For floating-point time-series values, Facebook's Gorilla uses delta-of-delta on timestamps and XOR-based encoding on values. The XOR of consecutive IEEE 754 floats tends to have many leading and trailing zeros when values change slowly, allowing compact storage.

Trade-offs and Limitations

Sequential Decode Dependency

The prefix-sum decode means you cannot access the i-th value without decoding all preceding values. This is a fundamental limitation for random access. Systems mitigate this by encoding data in fixed-size blocks (e.g., 128 or 1024 values per block) with independently decodable headers. Seeking to a specific value requires decoding at most one block.

SIMD-Friendly Decoding

The prefix sum is inherently sequential, but SIMD-parallel prefix sum algorithms exist and are well-studied. Daniel Lemire's work on SIMD-accelerated integer decoding demonstrates that delta decoding of bit-packed blocks can sustain billions of integers per second on modern CPUs. The key insight is processing blocks of 128 or 256 integers at a time, using vector instructions for both the unpacking and the prefix sum.

Poor Fit for High-Entropy Data

If consecutive values have no correlation (e.g., random UUIDs stored as integers), deltas are as large as the original values and may actually increase storage due to sign-handling overhead. Delta encoding should be applied selectively, based on data statistics collected during ingestion or compaction.

Overflow Concerns

For unsigned 64-bit values, the delta between consecutive values can exceed the range of a signed 64-bit integer if the sequence is not monotonic. Most implementations handle this by defining delta arithmetic as modular (wrapping) arithmetic over the unsigned integer domain, ensuring correct round-trip reconstruction regardless of sign. Alternatively, implementations may use wider intermediate types or restrict delta encoding to monotonic sequences and fall back to plain encoding otherwise.

Applications in Practice

Apache Parquet uses DELTA_BINARY_PACKED encoding for integer columns, dividing values into miniblocks of 32 values each and computing per-miniblock bit widths.

InfluxDB's TSM engine delta-encodes timestamps and applies further compression (RLE or simple8b packing) to the delta stream.

Prometheus uses a Gorilla-inspired delta-of-delta encoding for timestamps with a variable-bit-width scheme that assigns 0, 7, 9, or 12 bits based on the magnitude of each delta-of-delta value. This scheme is specific to Prometheus's implementation and differs in detail from the original Gorilla paper's encoding.

LevelDB / RocksDB uses prefix compression for keys within a data block. Since keys are sorted, a shared key prefix is factored out relative to restart points placed every N keys, and only the differing suffix is stored. This is a form of prefix/dictionary compression rather than numeric delta encoding, though the principle of exploiting sorted-order locality is analogous.

Apache Druid applies delta encoding in its numeric column compression, combined with Roaring Bitmaps for sparse bitmap data.

Key Points

• Delta encoding replaces absolute values with differences between consecutive elements, producing small integers from sequences with locality or monotonicity.
• Its primary value comes from composition with downstream encodings like bit-packing, varint, RLE, and zigzag encoding.
• Delta-of-delta encoding is effective for near-linear sequences such as regularly sampled timestamps, reducing most values to near-zero.
• The prefix-sum decode dependency prevents true random access; block-based encoding with independent headers is the standard mitigation.
• SIMD-parallel prefix sum algorithms make delta decoding competitive at billions of integers per second on modern hardware.
• For unsorted or high-entropy data, delta encoding provides no benefit and may increase storage overhead.
• Zigzag encoding converts signed deltas to unsigned integers, enabling efficient bit-packing for non-monotonic sequences.
• Overflow in delta arithmetic is typically handled via modular (wrapping) unsigned arithmetic to guarantee correct reconstruction.

References

Pelkonen, T., Franklin, S., Tischler, J., Cavallaro, P., Huang, Q., Meza, J., and Veeraraghavan, K. "Gorilla: A Fast, Scalable, In-Memory Time Series Database." Proceedings of the VLDB Endowment, Vol. 8, No. 12, 2015.

Lemire, D. and Boytsov, L. "Decoding Billions of Integers per Second through Vectorization." Software: Practice and Experience, Vol. 45, No. 1, 2015.

Zukowski, M., Heman, S., Nes, N., and Boncz, P. "Super-Scalar RAM-CPU Cache Compression." Proceedings of the 22nd IEEE International Conference on Data Engineering (ICDE), 2006.

Apache Parquet Format Specification: Encodings. https://parquet.apache.org/documentation/latest/

Salomon, D. "Data Compression: The Complete Reference." Springer, 4th Edition, 2007.