A Fast Path for Fixed-Length Lists in Parquet

Summary

In Hardwood, we have recently implemented an optimization which avoids this overhead. By scanning the encoded definition and repetition levels (def and rep levels from here on) we can detect that lists in a data set effectively are fixed-length, i.e. they all have the same size. If that’s the case, we can bypass the regular Dremel record reconstruction machinery for the affected data pages, yielding a very nice speed-up. So how does this work? For def levels, it’s trivial. For a given page, we’re looking for a stream of max_def_level whose length matches the number of values in the page. Both required lists (max def = 1) and optional lists (max def = 2) are handled. Parquet stores def and rep levels using a hybrid scheme of bit-packing and run-length encoding (RLE). Say, we’re dealing with a page of 3D float coordinates, i.e. fixed-length lists with n = 3. With 4-byte floats, a ~1 MB page holds roughly 87,000 records of 3 coordinates each—​261,000 leaf entries in total (261,000 × 4 bytes ≈ 1 MB). For a stream of all-present list elements, the encoder will serialize the def levels as one single RLE run, made up of a varint header—​the run length shifted left by one, with the freed low bit set to 0 to mark this as an RLE run rather than bit-packed—​followed by a byte for the max def level: This check for the absence of null values computes in O(1) and if it succeeds, the page is simply stamped with a "no null values" marker, avoiding the decoding and processing of the def-level stream. In fact, this optimization isn’t specific to fixed-length lists; it also speeds up the common case of a column whose schema permits null values but that happens to contain none. That shortcut is a well-known one and is also implemented in other Parquet readers and engines, including DuckDB. Detecting the repeating 0,1,1,0,…​ pattern in the encoded rep-level stream is a bit more complex. How it encodes depends on the value of n: Parquet’s RLE/bit-packing hybrid bit-packs the 0 at the rec...