When you perform a backup using pg_basebackup --compress=zstd, PostgreSQL sends your data to the Zstandard library and returns a very minimal amount. It's so compressed and small because zstd compresses your data twice (in two steps) and not just one smart method. Knowing those two phases is essential to know about zstd and how it compresses data.
Based on PostgreSQL's own source for the base backup path (src/fe_utils/astreamer_zstd.c), this blog shows a two-stage pipeline that demonstrates exactly how PSQL performs the compression. (The fundamental libzstd behavior is the same, but pg_dump's zstd support is kept separately in src/bin/pg_dump/compress_zstd.c.)
The main concept: two passes, two types of redundancy
We will see two types of redundancy in data, which cannot be solved by a single method or a single stage:
- When the same byte sequences (such as a template string, a column value, or an HTML element) repeat often in the data, this is known as repetition. Repetition removal is a dictionary problem.
- Skew: Even after repetition is removed, the remaining bytes and symbols are not equally likely. It wastes space to encode a common symbol with the same number of bits as a rare one. Removing skew is a statistical problem.
Older methods, such as pglz and lz4, end compression early, implying that they are pure dictionary coders that locate matches (i.e., repetition) while leaving statistical redundancy unchanged. They have different speed/ratio trade-offs, but lz4 does not include an entropy coding stage and is tuned for raw speed.
On the other hand, zstd solves both forms of redundancy in order; two stages happen in zstd:
- Stage 1 - LZ77 match finding eliminates redundancy by substituting short references for repeated sequences.
- Stage 2 - entropy coding removes skew by re-encoding what Stage 1 produced so that frequent symbols cost fewer bits than rare ones, the skew problem we have discussed above.
What people refer to as zstd's "double compression" is the second pass or stage that compresses the output of the first compressor; older LZ-only methods simply lack this stage.
Stage 1 - LZ77 match finding (remove the repetition)
Zstd slides a window over your input data, asking at each position: "Have I seen these upcoming bytes somewhere earlier in the window?" To respond so quickly, it maintains hash tables of recent sequences. Once again, it shifts a compact reference instead of the bytes when it detects a match.
Instead of raw bytes, this stage generates a list of sequences, each of which has three numbers and a few literal bytes:
- literal length - which is the number of unseen ("literal") bytes that come next,
- the literal bytes themselves,
- match length - which is the number of bytes to copy from earlier, and
- offset - the distance back from which they should be copied.
So a 4 KB repeated block becomes something like "copy 4096 bytes from 20000 bytes back" with a few bytes instead of 4096. That's how LZ77 succeeds.
How hard it searches is the "compression level"
This is an array of work. When a greedy parser finds the first good match, it immediately moves on, but it ignores better matches that are directly in front of it. A lazy or optimal parser chooses the set of matches that gives the shortest output more slowly but more accurately, searches farther, and keeps larger hash and chain tables.
The zstd compression level precisely regulates this. High levels (up to 22) use much more CPU time on the best parser to locate longer, better matches, whereas low levels use the rapid, greedy end of the range. PostgreSQL forwards your requested level straight into this stage:
You can find this code block in src/fe_utils/astreamer_zstd.c:
/* Set compression level */
ret = ZSTD_CCtx_setParameter(streamer->cctx, ZSTD_c_compressionLevel,
compress->level);
The window size scales with the level; higher levels remember more history, so matches can reach further back.
Going further back: long-range matching
At high levels, the normal window is limited to a few MB. Consider a basic backup with repeated page content megabytes apart for huge archives where similar blocks appear widely apart. Long-distance matching (LDM), a more advanced long-range match finder provided by zstd, significantly expands the reach of Stage 1 by finding matches for longer texts. PostgreSQL makes it available as a choice:
You can find this code block in src/fe_utils/astreamer_zstd.c:
if ((compress->options & PG_COMPRESSION_OPTION_LONG_DISTANCE) != 0)
{
ret = ZSTD_CCtx_setParameter(streamer->cctx, ZSTD_c_enableLongDistanceMatching, compress->long_distance);
You enable it with, e.g., pg_basebackup --compress=zstd:long.
At the end of Stage 1, repetition is gone, but the sequences it produced (all those literal bytes, match lengths, and offsets) are still written in fixed-width, statistically wasteful form. That's what Stage 2 fixes.
Stage 2 - entropy coding (eliminate the skew)
This is the pass that makes zstd zstd. zstd takes the streams. It compresses the streams created in Stage 1 once more, using entropy coders to assign long codes to uncommon symbols and short bit codes to frequently occurring ones. It employs two distinct coders, each suitable for the data it uses:
Huffman coding for the literal bytes
The distribution of the literal bytes (the information that didn't match anything) is still skewed in JSON; quotes and braces are common, but e and spaces predominate in text. Common bytes take a few 1 to 2 bits rather than a flat 8 because zstd creates a Huffman code over those literals. This alone will shrink the literal stream on real world data.
FSE (Finite State Entropy) is used for the sequence symbols
FSE, a quick table-driven entropy coder based on Asymmetric Numeral Systems (ANS), provides a better coder for the offset codes, literal lengths, and matching lengths. Since FSE is powered by precomputed state transition tables rather than per-symbol arithmetic, it operates far more quickly while achieving compression ratios that are extremely similar to those of arithmetic coding. This is why zstd can be simultaneously high ratio and fast.
Why are there two different coders? Because FSE's fractional bit precision works best on the short, highly skewed alphabets of the sequence symbols, Huffman is straightforward and ideal for the byte-sized literal alphabet. The design of zstd includes utilizing each where it is most effective.
The benefit of Stage 2 is that redundancy in Stage 1 can't see statistical skew; rather, literal repetition gets squeezed out. The data is larger than what we obtain via zstd since a pure LZ compressor ends after Stage 1 and leaves everything on the table.
How the two stages become a zstd frame
zstd does not repeat this process across the whole file. After dividing the input into blocks, it executes Stages 1 and 2 for each block before writing a compressed block that includes:
- The Huffman-coded literals, and
- The FSE coded sequences (which contain literal lengths, match lengths, offsets), with small headers describing the Huffman/FSE tables used (or a note to reuse the previous block's tables)
Blocks are wrapped in a frame with a header (window size, checksum flag, etc.). This block structure is also what makes streaming possible. postgres can feed data in and pull compressed output out incrementally, which is exactly how the base backup path uses it.
Zstd has an advantage over the more common LZ-only technique because of that second step. In Stage 1, repetition is found and rewritten as brief sequences. The statistical skew that sequences still carry is then addressed in Stage 2, which gives FSE the length/offset symbols and Huffman the literals. It is important to perform both passes because neither could perform the duty of the other. While libzstd operates the actual machinery, PostgreSQL stays out of the way. It sets the level, optionally switches on more workers or long-distance matching, and sends data block by block. The next time a base backup shrinks to a small portion of its initial size, you'll know that it was caused by two quite different methods layered one after the other.