[C++][Parquet] Fast path for reading fixed-size lists by detecting constant list length from encoded levels #61

Describe the enhancement requested

Reading fixed_size_list<T, n> columns is much slower than reading the same values as a flat column. One report (apache/arrow#34510) measured about 3×; profiling there showed that decoding levels costs about as much as decoding the values.

Today FixedSizeListReader (cpp/src/parquet/arrow/reader.cc) reuses ListReader<int32_t>. For every value, the record reader decodes def and rep levels into int16_t buffers, DelimitRecords scans rep levels to find record boundaries, DefRepLevelsToList builds an offsets buffer, and AssembleArray then checks every offset delta equals n before throwing the offsets away.

When all lists in a page have the same length and there are no nulls, none of that work is needed. Fast path for fixed-length lists in Parquet describes how the Hardwood reader detects this case cheaply from the encoded levels, without decoding them. It reports about 2.5× faster column reads and up to about 3.9× faster row reads. A similar result (about 2.3× on 4k-float arrays) was reported on the Parquet dev list.

Proposal

Add per-page detection in the column/record reader:

1. Def levels: check that the def-level stream is a single RLE run of max_def_level whose length equals the page's num_values. This is O(1), and it also helps variable-length list columns with no nulls.

2. Rep levels: check that the stream is the periodic pattern 0, 1×(n-1), working on the encoded RLE/bit-packed bytes:

   • small n (≤ 8): bit-packed groups form a repeating byte pattern, which can be compared a machine word at a time
   • large n: parse the first record's runs to find the stride, then check the rest of the stream repeats it byte for byte
   • otherwise, or on any irregularity: fall back to the existing path

   With V2 data pages this needs no decompression, since levels are stored outside the compressed section.

3. When a page passes both checks and n matches the Arrow FixedSizeListType::list_size(): skip level materialization, DelimitRecords, offset building and offset validation. Count records as values / n and read the values in bulk straight into the child array.

The expected rep-level patterns must match what Parquet C++, parquet-java and other major writers actually produce; add test files from those writers. Any page that doesn't match silently uses the existing path, so behaviour and results must not change.

Possible follow-ups: use the same detection for list<T> read as ListArray, with offsets generated arithmetically; and skip detection entirely if a spec-level fixed-size marker is adopted.

Acceptance criteria

• Unit tests for the detector on hand-built RLE/bit-packed level streams: several n including 1, 3, 8, 9, 15, 16 and 768; pages that start or end mid-pattern; mixed run types; near-miss patterns that must be rejected.
• Round-trip tests showing the fast and generic paths return identical arrays, including files with a mix of fast-path and fallback pages, record batches that span page boundaries, and SkipRecords.
• Nullable lists and elements that actually contain nulls fall back correctly.
• A benchmark in reader_writer_benchmark.cc comparing reading fixed_size_list<float, n> against reading the same values as a flat column, before and after the change.

Context

• Related write-side issue: [C++][Parquet] Fast path for writing fixed-size lists #60
• Parquet dev list discussion: https://lists.apache.org/thread/qhq33wg1loxhymsyqjnsfsrd82qnv43m
• Hardwood's detector (FixedSizeListDetector.java): https://github.com/hardwood-hq/hardwood

Component(s)

C++, Parquet