Principle:Duckdb Duckdb LZ4 Block Compression
| Knowledge Sources | |
|---|---|
| Domains | Compression, Storage |
| Last Updated | 2026-02-07 12:00 GMT |
Overview
An extremely fast lossless compression algorithm that prioritizes compression and decompression speed over compression ratio, operating on fixed-size blocks of data.
Description
LZ4 is a byte-oriented lossless compression algorithm that belongs to the LZ77 family. It was designed by Yann Collet with a singular focus on speed, achieving compression speeds of over 500 MB/s per core and decompression speeds exceeding several GB/s per core on modern hardware. The algorithm trades compression ratio for raw throughput, making it ideal for scenarios where data must be compressed and decompressed in real time.
LZ4 operates on blocks of data (up to 4 MB by default) and uses a simplified matching strategy with a hash table for match finding. The format encodes data as a sequence of literals (uncompressed bytes) and match copies (back-references to previously seen data). Each sequence is encoded with a token byte that contains both the literal length and the match length, followed by optional additional length bytes, the literal data, and a 2-byte match offset.
The block format is deliberately simple to enable branch-free decoding on modern CPUs, which is the primary reason for its exceptional decompression performance. The simplicity of the format also means the compressor can be implemented with minimal memory overhead, typically requiring only a 4 KB to 16 KB hash table.
Usage
LZ4 is used in DuckDB's storage layer for block-level compression of data segments. When data is written to persistent storage, DuckDB compresses individual blocks using LZ4 to reduce I/O while maintaining fast read performance. The extremely fast decompression speed ensures that the cost of decompressing data during query execution is negligible compared to disk I/O savings.
Theoretical Basis
LZ77 Hash-Based Matching: LZ4 uses a hash table to find matches efficiently:
// Compression pseudo-code
hash_table = array of size 4096 (or larger)
for each position p in input:
h = hash(input[p..p+3]) // hash 4 bytes
candidate = hash_table[h] // look up candidate
hash_table[h] = p // update table
if input[candidate..] matches input[p..]:
emit match(offset = p - candidate, length)
else:
emit literal(input[p])
Token Encoding: Each sequence is encoded with a compact token:
Token byte: [literal_length (4 bits) | match_length (4 bits)]
- If literal_length == 15: read additional bytes until byte < 255
- Followed by: literal bytes
- Followed by: 2-byte match offset (little-endian)
- If match_length == 15: read additional bytes until byte < 255
- Minimum match length = 4 (encoded as match_length + 4)
Decompression: The decoder processes tokens sequentially:
while not end of block:
token = read_byte()
lit_len = token >> 4
if lit_len == 15: lit_len += read_variable_length()
copy lit_len bytes from input to output
offset = read_16bit_le()
match_len = (token & 0x0F) + 4
if match_len == 19: match_len += read_variable_length()
copy match_len bytes from output[pos - offset] to output