Compression Blocks and the Loss of Splittability

A file is splittable when a reader can start decoding at an arbitrary byte offset and still produce correct output from that point. Compression destroys this property in most schemes, because the decoder’s state at any offset depends on everything before it. A file compressed as one stream can only be read from the beginning, which makes it a single unit of work no matter how many cores or nodes are available.

Every format that expects parallel reads therefore arranges compression so that independence is restored at some granularity. The arrangement is the block, and the block size is a trade between compression ratio, per-block overhead, and the number of independent units.

Why the decoder needs history

DEFLATE, the format inside gzip and zlib, compresses by emitting literals and back-references into a 32 KiB sliding window of previously decompressed output. A back-reference is a distance and a length; to resolve it, the decoder must already hold the bytes at that distance. Starting in the middle of the stream leaves the window undefined for the first 32 KiB of output, so those bytes cannot be produced correctly.

The same reasoning applies to any dictionary-based scheme, with different window sizes. Zstandard’s format allows window sizes that grow with the compression level, and a frame header can declare a window as large as the input; LZ4’s block format uses a 64 KiB window. The window is the memory a decoder must allocate, and it is also the distance back that the encoder may reference, so a larger window buys better ratio at the cost of decoder memory and, crucially, of the amount of preceding data a random access must reproduce.

The format-level consequence is that the unit of independent decoding is the unit that resets the window. DEFLATE has no such unit inside a stream: its blocks (stored, fixed-Huffman, dynamic-Huffman) are a bit-level framing for the entropy coder, not independent restart points, since later blocks reference earlier output through the window. Gzip adds a header with a magic of 1f 8b, a method byte, flags, and a trailer holding a CRC-32 and the uncompressed length modulo $2^{32}$; it does not add restart points. A .gz file is therefore a single stream, and a reader cannot seek into it.

Restoring independence with a container

Two strategies restore parallelism without abandoning compression.

The first is concatenation of independent members. Both gzip and zstd permit a file to consist of several complete streams placed end to end, and a decoder must process them in sequence; a reader that knows the member boundaries can assign members to workers independently, because each member’s window starts empty. The container must record the boundaries, either as a side index or by a format rule that lets a reader find member starts. Finding them by scanning is possible for gzip, since the magic bytes can be searched, but false positives inside compressed data make that unreliable without a checksum-verified scan, and the scan is linear.

The second, and the one that matters for data formats, is a block-structured codec designed for it: a stream of independently compressed blocks, each with an uncompressed length and a compressed length, so a reader can compute the byte range of any block without decoding the preceding ones. Snappy’s framing format and LZ4’s frame format both work this way, and both are what systems use when they need splittable compressed files. A reader that receives a block range can decompress the blocks it was given, concatenate the outputs, and hand them to the parser.

Parquet uses the second strategy at a different level. Compression is applied per page, and each page header records both the uncompressed and compressed sizes. A reader can therefore fetch exactly one page and decompress it in isolation, and the column chunk is splittable at page granularity as a direct consequence. The page is the restart point, and the format’s designers chose the page size partly for that reason, as described in Inside a Parquet File.

# Read one framed block without touching its neighbours.
import struct, zlib

def read_block(buf, pos):
    """Return (decompressed_bytes, next_pos) for one length-prefixed block."""
    (clen,) = struct.unpack_from("<I", buf, pos)
    pos += 4
    body = buf[pos:pos + clen]
    pos += clen
    # -15 selects raw DEFLATE with no zlib or gzip wrapper around it.
    return zlib.decompress(body, -15), pos

The four-byte length prefix is the entire mechanism: it converts a stream into a sequence of addressable units. Everything else is bookkeeping about where the block table lives.

The cost of a block boundary

Every block boundary costs compression ratio, because the encoder’s history is discarded and the first bytes of each block are compressed without context. For text-like data with strong long-range repetition, that loss is significant; for numeric columns, where the repetition is local, it is small. The magnitude depends on the block size relative to the correlation length of the data: blocks much larger than the correlation length lose almost nothing, and blocks smaller than it lose a lot.

Per-block overhead is the second cost. Each block carries a header, typically a few bytes for lengths and possibly a checksum, and each block must be allocated and tracked by the reader. At a 64 KiB block size with an 8-byte header, the overhead is about 0.012 percent, which is negligible. At a 4 KiB block size it is 0.2 percent, and the number of blocks becomes large enough that the index describing them is itself a cost.

The third cost is the decoder’s granularity of work. A block of 1 MiB decompresses to 1 MiB and must be held in memory at once; a block of 64 KiB allows a streaming reader to work in small pieces. Formats that store a block per page inherit the page size as both the parallelism unit and the memory unit, which is why page sizes are chosen in the hundreds of kilobytes to a few megabytes rather than in the tens of megabytes.

Splittability at the file level versus the codec level

There are two independent levels at which a file can be split, and conflating them causes confusion.

The codec level asks whether the compressed byte stream can be entered in the middle. A gzip stream cannot; a framed Snappy stream can, if the reader has the frame index. The file level asks whether the container exposes its internal structure so a reader can request a byte range at all. A Parquet file exposes row groups and pages through its footer, so even with an unsplittable codec the file is splittable at page boundaries, because each page’s compressed bytes are a separate codec invocation. A single .gz file of line-delimited JSON exposes nothing, so the file is one unit no matter what the codec allows.

The practical rule is that splittability is a property of the container, and the codec determines whether the container can expose it cheaply. Columnar formats achieve it because they compress small independent units. Row-oriented formats with a single stream do not, which is why a .gz file in a distributed filesystem is read by one task while the same data in an uncompressed or block-compressed file is read by many. Concatenating many gzip members mitigates this, at the cost of the reader having to locate the members.

Choosing a codec under these constraints

The decision has three axes: ratio, decode speed, and block structure.

DEFLATE at typical settings compresses text well and decodes at a few hundred megabytes per second per core, with a 32 KiB window and no block structure. Zstandard spans a wide range: its low levels decode faster than DEFLATE at a comparable ratio, and its high levels trade decode speed for ratio, with a window that can be tuned and a frame format that permits independent blocks and a skippable-frame mechanism for metadata. Snappy and LZ4 sit at the fast end, with ratios well below DEFLATE and decode speeds several times higher, which suits formats where the bottleneck is the decoder rather than the storage. None of these figures should be treated as portable across datasets; the ordering is stable, the multipliers are not.

For a columnar file, the codec is applied per page, so the block structure is supplied by the format rather than the codec. That makes the choice about ratio and decode speed only, and it means a codec without any block structure of its own, such as raw DEFLATE, is perfectly usable inside Parquet. The reverse holds for row-oriented text formats, where the codec’s framing is the only structure available, and where a block-framed codec is the difference between one reader and many. The interaction with the in-memory side is the mirror image: Arrow Buffer Layout and Where Zero-Copy Stops notes that compressed buffers must be decompressed before an array can point at them, so compression at an exchange boundary trades a copy for bandwidth, and the same trade appears at rest.

One last constraint is worth stating because it is easy to violate: a reader must not assume a block size. The sizes are recorded per block, and a writer is free to vary them within a stream, so any reader that computes offsets from a nominal size will misparse a valid file. Block boundaries come from the header, never from arithmetic on a constant.