Principle:Duckdb Duckdb Zstandard Compression
| Knowledge Sources | |
|---|---|
| Domains | Compression, Storage, Columnar_Storage |
| Last Updated | 2026-02-07 12:00 GMT |
Overview
A modern lossless compression algorithm that provides configurable trade-offs between compression speed and ratio, with support for dictionary-based compression and multi-threaded operation.
Description
Zstandard (zstd) is a lossless compression algorithm developed by Yann Collet at Facebook. It is designed to provide compression ratios comparable to or better than zlib/deflate while offering significantly faster compression and decompression speeds. Zstandard achieves this through a combination of a large LZ77 match-finding window, a Finite State Entropy (FSE) encoder (a variant of Asymmetric Numeral Systems), and Huffman coding for literals.
A key differentiator of Zstandard is its wide range of configurable compression levels (1 through 22), allowing users to choose the optimal trade-off between compression speed and ratio for their use case. At low levels (1-3), Zstandard compresses faster than zlib while achieving similar ratios. At high levels (19-22), it approaches LZMA-class compression ratios while remaining significantly faster at decompression.
Zstandard also supports dictionary compression, where a pre-trained dictionary captures common patterns in the data. This is especially effective for compressing many small, similar records, as the dictionary provides context that would otherwise require a large window. The dictionary training algorithm analyzes sample data to extract the most useful patterns for compression.
Usage
Zstandard is used in DuckDB in two primary contexts. First, it serves as a compression codec in the DuckDB native storage format, where it compresses data blocks written to disk. Second, it is one of the supported compression codecs when reading and writing Apache Parquet files. Its configurable compression levels allow DuckDB to balance write performance against storage efficiency depending on the workload.
Theoretical Basis
Finite State Entropy (FSE): Zstandard's core entropy coder uses table-based ANS:
// ANS encoding: maps (state, symbol) -> new_state + output_bits
// Table construction from symbol frequencies
for each symbol s with frequency f[s]:
assign f[s] cells in table of size 2^table_log
// Encoding
state = initial_state
for each symbol in input (reverse order):
nb_bits = table[state].nb_bits
output(state & mask(nb_bits)) // emit low bits
state = encode_table[symbol][state >> nb_bits]
Sequence Encoding: Each LZ77 match is encoded as a triple:
Sequence = (literal_length, match_offset, match_length)
- Literal length: FSE-encoded with extra bits
- Match offset: FSE-encoded with extra bits; supports repeated offsets
- Match length: FSE-encoded with extra bits
- Minimum match length = 3
Dictionary Compression: Pre-trained dictionaries provide initial context:
// Dictionary structure
dictionary:
magic_number: 0xEC30A437
dict_id: 4 bytes
entropy_tables: pre-built Huffman and FSE tables
content: raw byte sequences for match references
// During compression, the dictionary content is placed
// before the input in the virtual window, enabling
// back-references into dictionary content
Block Format: Data is organized into frames and blocks:
Frame:
frame_header: magic + frame_descriptor + window_size [+ dict_id] [+ content_size]
blocks: repeated {
block_header: 3 bytes (last_block_flag, block_type, block_size)
block_data: compressed sequences
}
[content_checksum: xxHash64 lower 4 bytes]