ch07Compression

What you build: Snappy, LZ4 and DEFLATE decompressors in the read path, and every codec's sizes from footers.

The question#

What does compression add on top of encoding, and what does it cost?

ch05 made values compact using what they are: integers that go up by one, strings that share prefixes, a few countries repeated. ch06 showed that every page header carries two sizes, and that in the fixtures so far they were equal. They differ once a writer compresses its pages.

A codec is a general-purpose compressor applied to each page after encoding. It knows nothing about types. It sees bytes, finds repetition in them, and writes it more briefly. The column chunk’s metadata names the codec, and a reader must undo it before it can decode anything the page holds.

The experiment#

One table, six codecs#

The codec-*.parquet files hold the same orders, encoded the same way: PLAIN, no dictionary. Only the codec differs, so their pages are identical before compression, and any difference in size is the codec’s. Appendix B lists how each was written.

Each step below is a few lines of code. In Python, run them in the page, change them with Edit, and run them again. In Rust, open them in a Codespace, or run one at a desk with cargo run -p walkthroughs --bin and its name. Each step finds the footer as ch02 did, decodes it with the reader’s decode_file_metadata from ch03, and finds a column chunk’s page with walk_pages from ch06.

Snappy by hand. A Snappy page starts with a varint, the length of what comes out. Then come elements, each opening with a tag byte whose low two bits say what it is. 00 is a literal: bytes to copy from the input as they are. The other three are copies: bytes to repeat from earlier in the output, given how far back they start and how many there are. Undo the country page of codec-snappy.parquet:

# Undo Snappy by hand: a length, then tags that say "literal" or "copy".
import sys
sys.path.insert(0, "python")  # the book's reader, from the repository's python/ directory
from parquet_lab import metadata, pages

data = open("fixtures/codec-snappy.parquet", "rb").read()
length = int.from_bytes(data[-8:-4], "little")
base = len(data) - 8 - length
md = metadata.decode_file_metadata(data[base:-8], base)
chunk = md.row_groups[0].columns[1].byte_range()  # country; try 5, distance_km
[page] = pages.walk_pages(data[chunk.start:chunk.end], chunk.start)
body = data[page.body_span.start:page.body_span.end]

size, shift, i = 0, 0, 0
while body[i] & 0x80:  # a varint: seven bits a byte, lowest first; a top bit means more
    size, shift, i = size | (body[i] & 0x7F) << shift, shift + 7, i + 1
size, i = size | body[i] << shift, i + 1
print(f"{len(body)} bytes; the varint says {size} will come out")
out, tokens = bytearray(), []
while i < len(body):
    tag, kind = body[i], body[i] & 3  # the low two bits say what the element is
    if kind == 0:  # a literal: its length - 1 in the top six bits, or in 1..4 more bytes
        n, i = (tag >> 2) + 1, i + 1
        if n > 60:
            n, i = int.from_bytes(body[i:i + n - 60], "little") + 1, i + n - 60
        out += body[i:i + n]
        i += n
        tokens.append(f"literal {n} bytes")
        continue
    if kind == 1:  # a copy of 4..11 bytes, up to 2047 back
        n, back, i = 4 + (tag >> 2 & 7), (tag >> 5) << 8 | body[i + 1], i + 2
    else:  # a copy of 1..64 bytes, its distance in 2 or 4 more bytes
        width = 2 if kind == 2 else 4
        n, back = (tag >> 2) + 1, int.from_bytes(body[i + 1:i + 1 + width], "little")
        i += 1 + width
    for _ in range(n):  # byte by byte: a copy may overlap the bytes it writes
        out.append(out[-back])
    tokens.append(f"copy {n} from {back} back")
print(*tokens[:6], sep="\n")  # try tokens[-6:]
header = page.uncompressed_page_size
print(f"{len(tokens)} tokens wrote {len(out)} bytes; the page header says {header}")

//! Undo Snappy by hand: a length, then tags that say "literal" or "copy".

use parquet_lab::metadata::decode_file_metadata;
use parquet_lab::pages;

fn le(bytes: &[u8]) -> usize {
    bytes.iter().rev().fold(0, |acc, &b| acc << 8 | b as usize)
}

fn main() {
    let path = "fixtures/codec-snappy.parquet";
    let data = std::fs::read(path).expect("run this from the repository's root");
    let n = data.len();
    let length = u32::from_le_bytes(data[n - 8..n - 4].try_into().unwrap()) as usize;
    let base = n - 8 - length;
    let md = decode_file_metadata(&data[base..n - 8], base as u64).expect("a footer");
    let chunk = md.row_groups[0].columns[1].byte_range(); // country; try 5, distance_km
    let (from, to) = (chunk.start as usize, chunk.end as usize);
    let page = &pages::walk_pages(&data[from..to], chunk.start).expect("pages")[0];
    let body = &data[page.body_span.start as usize..page.body_span.end as usize];

    // A varint: seven bits a byte, lowest first; a top bit means more.
    let (mut size, mut shift, mut i) = (0, 0, 0);
    while body[i] & 0x80 != 0 {
        (size, shift, i) = (size | (body[i] as usize & 0x7f) << shift, shift + 7, i + 1);
    }
    (size, i) = (size | (body[i] as usize) << shift, i + 1);
    println!("{} bytes; the varint says {size} will come out", body.len());
    let (mut out, mut tokens) = (Vec::new(), Vec::new());
    while i < body.len() {
        let (tag, kind) = (body[i] as usize, body[i] & 3); // the low two bits say what it is
        if kind == 0 {
            // A literal: its length - 1 in the top six bits, or in 1..4 more bytes.
            let (mut n, mut at) = ((tag >> 2) + 1, i + 1);
            if n > 60 {
                (n, at) = (le(&body[at..at + n - 60]) + 1, at + n - 60);
            }
            out.extend_from_slice(&body[at..at + n]);
            i = at + n;
            tokens.push(format!("literal {n} bytes"));
            continue;
        }
        let (n, back) = if kind == 1 {
            // A copy of 4..11 bytes, up to 2047 back.
            i += 2;
            (4 + (tag >> 2 & 7), (tag >> 5) << 8 | body[i - 1] as usize)
        } else {
            // A copy of 1..64 bytes, its distance in 2 or 4 more bytes.
            let width = if kind == 2 { 2 } else { 4 };
            i += 1 + width;
            ((tag >> 2) + 1, le(&body[i - width..i]))
        };
        for _ in 0..n {
            // Byte by byte: a copy may overlap the bytes it writes.
            out.push(out[out.len() - back]);
        }
        tokens.push(format!("copy {n} from {back} back"));
    }
    for token in tokens.iter().take(6) {
        println!("{token}"); // try tokens.iter().rev()
    }
    let (count, header) = (tokens.len(), page.uncompressed_page_size);
    println!(
        "{count} tokens wrote {} bytes; the page header says {header}",
        out.len()
    );
}

A PLAIN string is a four-byte length and then its bytes, so the page starts 02 00 00 00, then UK. The first element is a literal: those six bytes, as they are. The next country’s length prefix is the same four bytes, and Snappy writes it as a copy from six bytes back, in two bytes. The country code itself is a literal, because Snappy’s compressor never copies fewer than four bytes. The last line checks the result: the elements wrote exactly as many bytes as the varint promised and the page header says.

Print tokens[-6:] instead (tokens.iter().rev() in Rust, which lists them last first). Once the five countries have all appeared, the page repeats with a fixed period, and from there every element is a copy from one period back, longer than the distance it reaches. A copy may overlap the bytes it writes, which is why the step copies a byte at a time. Then change the column to 5, distance_km: noisy floating point, mostly long literals with short copies between them.

This is the LZ77 idea every codec here shares: replace a run of bytes the output already holds with how far back it is and how long. The codecs differ in how they write those references down, and in what else they do.

Three codecs, one page. The reader’s compress.decompress takes a codec’s name from the footer, a page’s compressed bytes and the size its header promises. Give it the country page from three files, and compare each result with the same page in codec-none.parquet:

# Decompress one page under three codecs, and compare it with the uncompressed file's.
import sys
sys.path.insert(0, "python")  # the book's reader, from the repository's python/ directory
from parquet_lab import compress, metadata, pages

def first_page(name, column):
    data = open(f"fixtures/codec-{name}.parquet", "rb").read()
    length = int.from_bytes(data[-8:-4], "little")
    base = len(data) - 8 - length
    md = metadata.decode_file_metadata(data[base:-8], base)
    chunk = md.row_groups[0].columns[column]
    span = chunk.byte_range()
    [page] = pages.walk_pages(data[span.start:span.end], span.start)
    return chunk.codec, page, data[page.body_span.start:page.body_span.end]

column = 1  # country; try 5, which is distance_km
_, _, plain = first_page("none", column)
for name in ["snappy", "lz4", "gzip"]:  # try adding "zstd"
    codec, page, body = first_page(name, column)
    size = page.uncompressed_page_size
    out = compress.decompress(codec, body, page.body_span.start, size)
    tokens, same = len(out.tokens), out.data == plain
    print(f"{codec}: {len(body)} bytes become {size} in {tokens} tokens, the same: {same}")

//! Decompress one page under three codecs, and compare it with the uncompressed file's.

use parquet_lab::compress;
use parquet_lab::metadata::decode_file_metadata;
use parquet_lab::pages::{self, Page};

fn first_page(name: &str, column: usize) -> (String, Page, Vec<u8>) {
    let path = format!("fixtures/codec-{name}.parquet");
    let data = std::fs::read(path).expect("run this from the repository's root");
    let n = data.len();
    let length = u32::from_le_bytes(data[n - 8..n - 4].try_into().unwrap()) as usize;
    let base = n - 8 - length;
    let md = decode_file_metadata(&data[base..n - 8], base as u64).expect("a footer");
    let chunk = &md.row_groups[0].columns[column];
    let span = chunk.byte_range();
    let (from, to) = (span.start as usize, span.end as usize);
    let page = pages::walk_pages(&data[from..to], span.start)
        .expect("pages")
        .remove(0);
    let body = data[page.body_span.start as usize..page.body_span.end as usize].to_vec();
    (chunk.codec.clone(), page, body)
}

fn main() {
    let column = 1; // country; try 5, which is distance_km
    let (_, _, plain) = first_page("none", column);
    // Try adding "zstd".
    for name in ["snappy", "lz4", "gzip"] {
        let (codec, page, body) = first_page(name, column);
        let size = page.uncompressed_page_size as usize;
        let out = compress::decompress(&codec, &body, page.body_span.start, size).expect("a page");
        let (tokens, same) = (out.tokens.len(), out.bytes == plain);
        let compressed = body.len();
        println!("{codec}: {compressed} bytes become {size} in {tokens} tokens, the same: {same}");
    }
}

Every codec gives back the uncompressed file’s page, byte for byte, and each gets there in a different number of bytes and tokens. The reader counts the Snappy varint as a token, so its count is one more than the first step’s. The GZIP tokens include the stream’s header and trailer.

Change the column to 5, distance_km: every codec saves far less, and needs hundreds of tokens. Add "zstd" to the list: the reader refuses, because it does not decode ZSTD. In Python, compare out.data with zlib.decompress(body, 31), which inflates a GZIP page with the standard library.

The reader also counted what each token wrote:

Snappy limits a copy to 64 bytes, so a long repeat is many copies in a row. LZ4 writes a match’s length in a nibble and extends it a byte at a time, so one match covers nearly the whole page. GZIP wraps DEFLATE, whose copies stop at 258 bytes, but whose tokens are Huffman codes: the literals and lengths that occur most get the fewest bits. That second step, entropy coding, is what the smaller codecs add. ZSTD and Brotli do it too, with more elaborate machinery.

Step through the tokens#

The panel runs the same decompressors on one page, and draws what each token did. Each token highlights the compressed bytes it read and, in the decompressed page, the bytes it wrote. A copy also outlines the earlier bytes it repeated.

Step through the country page under Snappy, and watch a copy’s outline stay a period behind what it writes. Switch to codec-lz4.parquet and find the one token that writes most of the page. Switch to codec-gzip.parquet: the tokens do the same work, but each is written in a few bits rather than whole bytes, so neighbouring tokens share a byte. Then open pages-v2-snappy.parquet and pick country. In version 2 data pages the levels sit in front of the compressed section, untouched.

What each codec saved#

The whole file under each codec:

The codecs fall into two groups. Snappy and LZ4 land close together. GZIP, ZSTD and Brotli all land smaller, and Brotli is smallest here. The two groups differ in method: Snappy and LZ4 only replace repeated bytes with references to earlier ones, and the other three also give common bytes shorter codes.

The same measurement column by column says more. The first table holds the codecs that only copy, the second the codecs that also code:

The columns differ far more than the codecs do. country and note repeat a few values, and every codec shrinks them to a small fraction. distance_km is noisy floating point, and every codec saves least on it. order_id is a counter: no value repeats, and Snappy and LZ4 find only the runs of zero bytes between the low bytes. The codecs that also give frequent bytes short codes do much better, because most of each value’s bytes are zero. A delta encoding would store it in almost nothing, as ch05 showed.

Encoding and compression are not rivals. An encoding uses what it knows about the type; a codec finds whatever repetition is left.

Encoding before compression#

ch05 said that BYTE_STREAM_SPLIT does not shrink anything by itself, and that a compressor might find more in its output. codec-zstd-split.parquet is codec-zstd.parquet with both float columns split:

Splitting helped distance_km and hurt weight_kg. The noisy floats behave as ch05 described: the sign and exponent bytes barely change, and once they sit together the compressor finds them. The weights are different. Each is a number of kilograms to two decimal places, and a decimal fraction has no exact binary form: its mantissa is a repeating bit pattern. Set the second step’s column to 4, weight_kg, and print the page it decompressed (out.data.hex(" ") in Python, or {:02x?} of out.bytes in Rust). The same byte sequences recur, 33 33 33 and 14 ae 47 e1 7a among them. In PLAIN order a compressor matches them as whole runs. Split, each run is scattered over eight streams.

Neither result is a rule. What an encoding is worth to a codec depends on the values, and the only way to know is to measure both on real data.

What it costs#

A codec’s saving is paid for when the file is read.

• A reader decompresses whole pages. Compressed bytes cannot be decoded from the middle: a copy refers to bytes earlier in the output. To read one value, a reader decompresses every byte of its page before it.
• The page header says how much memory to set aside. uncompressed_page_size is known before decompression starts, and the reader checks the output against it.
• Version 2 leaves the levels alone. A reader can count rows and nulls, or skip to a row, without decompressing anything, as ch06 described.
• Decompression takes time. Faster codecs usually compress less. Whether the time or the bytes matter more depends on where the file lives: bytes fetched over a network cost more than bytes read from a local disk. ch10 weighs the two.

Codec names#

The footer stores a codec as a number, and parquet.thrift names each one. Two names need care. LZ4 is an early codec whose framing implementations disagreed about, and it is deprecated. LZ4_RAW is its replacement: a plain LZ4 block. pyarrow writes LZ4_RAW when asked for lz4, and reports it as LZ4 in its own metadata, which is why the book’s fixture tests map one name to the other. Ask a library, at the end of Building it, shows both names. LZO is defined and rarely written.

Building it#

The steps undid Snappy by hand, then called the reader’s decompress on three codecs. This section builds the Snappy decoder, says where the other two are, and shows where the column reader calls them. The tabs switch every excerpt on the page between the two languages.

Snappy#

snappy reads the varint as the first step did, then decodes elements until the input ends, recording each as a token. A literal copies bytes from the input:

    out = bytearray()
    while i < len(data):
        start, tag = i, data[i]
        i += 1
        at = len(out)
        if tag & 0b11 == 0b00:
            length = tag >> 2
            if length >= 60:
                extra = length - 59
                length = _le(data, i, extra)
                i += extra
            length += 1
            if i + length > len(data):
                raise CompressError("a literal runs past the end of the compressed bytes")
            out += data[i : i + length]
            i += length
            tokens.append(
                Token(LITERAL, "literal", _span(base, start, i), Span(at, len(out)),
                      f"tag {tag:02x}: a literal, the next {n_bytes(length)}")
            )  # fmt: skip
            continue

    let mut out = Vec::with_capacity(size);
    while i < input.len() {
        let start = i;
        let tag = input[i];
        i += 1;
        let at = out.len() as u64;
        match tag & 0b11 {
            0b00 => {
                let mut len = (tag >> 2) as usize;
                if len >= 60 {
                    let extra = len - 59;
                    len = le(input, i, extra)?;
                    i += extra;
                }
                len += 1;
                let bytes = input
                    .get(i..i + len)
                    .ok_or("a literal runs past the end of the compressed bytes")?;
                out.extend_from_slice(bytes);
                i += len;
                tokens.push(Token {
                    kind: TokenKind::Literal,
                    label: "literal".into(),
                    input: span(base, start, i),
                    output: Span::new(at, out.len() as u64),
                    detail: format!("tag {tag:02x}: a literal, the next {}", n_bytes(len)),
                });
            }

A copy reads its length and distance from the tag and the bytes after it, in one of three layouts, and repeats earlier output:

        if tag & 0b11 == 0b01:
            length = 4 + ((tag >> 2) & 0b111)
            distance = ((tag >> 5) << 8) | _get(data, i)
            i += 1
        elif tag & 0b11 == 0b10:
            length, distance = 1 + (tag >> 2), _le(data, i, 2)
            i += 2
        else:
            length, distance = 1 + (tag >> 2), _le(data, i, 4)
            i += 4
        copy_back(out, distance, length)
        tokens.append(
            Token(COPY, "copy", _span(base, start, i), Span(at, len(out)),
                  f"tag {tag:02x}: copy {n_bytes(length)} from {distance} back", distance)
        )  # fmt: skip

            kind => {
                let (len, distance) = match kind {
                    0b01 => {
                        let len = 4 + ((tag >> 2) & 0b111) as usize;
                        let distance = (((tag >> 5) as usize) << 8) | get(input, i)? as usize;
                        i += 1;
                        (len, distance)
                    }
                    0b10 => {
                        let d = le(input, i, 2)?;
                        i += 2;
                        (1 + (tag >> 2) as usize, d)
                    }
                    _ => {
                        let d = le(input, i, 4)?;
                        i += 4;
                        (1 + (tag >> 2) as usize, d)
                    }
                };
                copy_back(&mut out, distance, len)?;
                tokens.push(Token {
                    kind: TokenKind::Copy {
                        distance: distance as u64,
                    },
                    label: "copy".into(),
                    input: span(base, start, i),
                    output: Span::new(at, out.len() as u64),
                    detail: format!("tag {tag:02x}: copy {} from {distance} back", n_bytes(len)),
                });
            }
        }
    }

copy_back copies byte by byte, because a copy may overlap the bytes it writes: a distance of one repeats the last byte. It also checks that the distance points into the output.

In the column reader#

Version 1 compresses the whole body, so the reader decompresses it first and reads the levels and values from the copy:

        # Version 1 compresses the whole body as one block. Decompress it, and read the levels
        # and values from the copy.
        whole = page.v2 is None and codec != "UNCOMPRESSED"
        levels_bytes = body
        if whole:
            levels_bytes = _decompress(codec, body, page, page.uncompressed_page_size)
        levels_base = page.body_span.start

        // Version 1 compresses the whole body as one block. Decompress it, and read the levels
        // and values from the copy.
        let whole = page.v2.is_none() && codec != "UNCOMPRESSED";
        let v1_plain;
        let (levels_bytes, levels_base) = if whole {
            v1_plain = decompress(codec, body, &page, page.uncompressed_page_size)?;
            (&v1_plain[..], page.body_span.start)
        } else {
            (body, page.body_span.start)
        };

Version 2 compresses only the values:

        # Version 2 compresses only the values, and only when the header says so.
        values_compressed = codec != "UNCOMPRESSED" and v2 is not None and v2.is_compressed
        if values_compressed:
            levels = values_start - page.body_span.start
            rest = _decompress(codec, rest, page, page.uncompressed_page_size - levels)

        // Version 2 compresses only the values, and only when the header says so.
        let values_compressed =
            codec != "UNCOMPRESSED" && page.v2.is_some_and(|v2| v2.is_compressed);
        let v2_plain;
        let rest = if values_compressed {
            let levels = (values_start - page.body_span.start) as i64;
            v2_plain = decompress(codec, rest, &page, page.uncompressed_page_size - levels)?;
            &v2_plain[..]
        } else {
            rest
        };

Values decoded from a decompressed copy have no position in the file, so the reader reports the compressed bytes that hold them. It can say which compressed page a value came from, but not which of its bytes.

Checking it#

Every page of every Snappy, LZ4 and GZIP fixture decompresses to the uncompressed file’s page, byte for byte, and every column reassembles to pyarrow’s rows. A ZSTD or Brotli page is refused with a message rather than misread:

python3 -m pytest python/tests

cargo test -p parquet-lab --test fixtures

Ask a library#

pyarrow and the parquet crate both read the codec and the two sizes from the footer. Ask each for the country column chunk in the three files the second step decompressed:

# The same facts from pyarrow: each file's codec for country, and the chunk's two sizes.
import pyarrow.parquet as pq

for name in ["snappy", "lz4", "gzip"]:  # try "zstd", "brotli" or "none"
    chunk = pq.read_metadata(f"fixtures/codec-{name}.parquet").row_group(0).column(1)
    before, after = chunk.total_uncompressed_size, chunk.total_compressed_size
    print(f"{chunk.path_in_schema}: {chunk.compression}, {after} of {before} bytes")

//! The same facts from the `parquet` crate: each file's codec for country, and the chunk's two
//! sizes. `compression()` turns the codec into a writer's setting, with a level of its own.

use parquet::file::reader::{FileReader, SerializedFileReader};

fn main() {
    for name in ["snappy", "lz4", "gzip"] {
        let file = std::fs::File::open(format!("fixtures/codec-{name}.parquet"))
            .expect("run this from the repository's root");
        let reader = SerializedFileReader::new(file).expect("a Parquet file");
        let chunk = reader.metadata().row_group(0).column(1); // country
        let (before, after) = (chunk.uncompressed_size(), chunk.compressed_size());
        let (path, codec) = (chunk.column_path().string(), chunk.compression_codec());
        println!("{path}: {codec:?}, {after} of {before} bytes");
        println!("  as a writer's setting: {}", chunk.compression());
    }
}

Both report the sizes the tables above were made from. Each counts the page header in both, and the header is never compressed, so the difference between them is what the codec saved. The names differ. The file names LZ4_RAW, and the crate says so, where pyarrow prints LZ4, as Codec names described. The crate’s compression() answers with a writer’s setting rather than the file’s field: for GZIP it adds a compression level, which the file does not record. The level is the crate’s default, the one it would write with. compression_codec() gives the name the file stores. No reader needs the level: a DEFLATE stream decodes the same way whatever level wrote it.

In Python, the first run loads pyarrow into the page, a much larger download than the other steps. In Rust the step needs the parquet crate, in walkthroughs/libraries, so it runs in a Codespace or at a desk:

cargo run -q --manifest-path walkthroughs/libraries/Cargo.toml --bin compression_with_a_library

What this cannot tell you#

How fast each codec is. The book’s numbers come from files, not clocks, so they are the same on every machine. Speed depends on the implementation, the hardware and the data. Measure it with the reader you use, on files like yours.

How ZSTD and Brotli work inside. Their sizes are measured here, and their pages are not decoded. Both add entropy coding to LZ77, as DEFLATE does, with larger windows and more careful modelling. Their specifications are listed below.

How compression levels change the result. Each fixture uses pyarrow’s default level for its codec. Most codecs can trade more compression time for smaller output, and decompressing usually costs about the same whichever level wrote the file.

How real pages behave. The fixtures hold one small page per column chunk. A compressor finds more repetition in a larger input, so production pages of a megabyte or so usually compress better than these.

Key takeaways#

Problems#

Three, in exercises/python/compression.py, or in Rust in exercises/src/compression.rs. The first two have tests. The third has none.

The editor below holds the Python stubs and keeps your edits in this browser. Run the tests runs the graders in the page, the same tests that run at a desk.

7.1 Snappy. Decompress a raw Snappy block. The test decompresses every page of codec-snappy.parquet and compares it, byte for byte, with the same page in codec-none.parquet.

7.2 LZ4. Decompress an LZ4 block. The fixture’s pages include a match long enough to need several extra length bytes.

7.3 Your own codec. No test: the data is yours. Take a Parquet file your systems write and rewrite it with each codec your writer supports, keeping everything else the same. Record each file’s size and, with the reader you use in production, the time to read it end to end. Then say which codec you would choose, and for which storage: local disk, a network file system, or an object store. A good answer names the column that contributes most to the size, and says whether a different encoding for that column would matter more than the codec.

For the Rust stubs, or to work at a desk, run the chapter’s graders with these commands. Add -k problem_7_1 in Python, or problem_7_1 before the -- in Rust, to run one problem:

python3 -m pytest exercises/python/tests/test_compression.py --problems

cargo test -p exercises --test compression -- --ignored

Where to go next#

• The codecs Parquet allows, and the history of the two LZ4s, are in the format repository’s Compression.md.
• Snappy’s format description and LZ4’s block format are each a page long.
• DEFLATE is RFC 1951 and gzip RFC 1952. Mark Adler’s puff.c is an inflater written to be read.
• Zstandard is RFC 8878, and Brotli RFC 7932.
• ch08 turns to what the footer records about the values in each column chunk, so that a reader can decide not to decompress it at all.

Built from commit c32f48e.