In its current form Apache Parquet isn’t a great fit for storing fixed-length lists, such as coordinates, RGB(A) colors, or—an increasingly common case—vector embeddings driving search and retrieval workloads. A 768-dimensional embedding is just a list of floats that always has the same length, yet Parquet’s Dremel machinery encodes it as if that length could vary from row to row, spelling out and reconstructing each vector’s structure on read. That costs roughly 3× more than a purely flat columnar representation of the same data (see apache/arrow#34510).
The Parquet community has recognized this problem and is actively working on addressing it.
Several options for adding fixed-length list support are currently under discussion,
for instance in the form of a new logical type FIXED_SIZE_LIST.
Eventually, this should bring decoding performance of fixed-length list data to the level of a fully flat schema.
However, until that’s the case, is there anything we can do to narrow or even close the gap by retrieving effectively fixed-length lists in a smarter way?
Turns out, yes we can.
By examining the encoded data streams for Parquet’s definition and repetition levels it is possible to detect data pages which only contain lists of the same lengths and put these onto a fast path which bypasses the regular Dremel record reconstruction. We’ve implemented this optimization for the upcoming Hardwood release, with striking results. The exact impact depends on the chosen Hardwood reader (row vs. column) and list length. The following chart shows the results from parsing ZSTD-compressed files with two list widths, each with 128M four-byte float values.
The short 3-element lists (say, 3D coordinates) see a modest speed-up of 1.1× for the row reader and a solid 2.5× for the column reader. For the larger 768-element lists (for instance, vector embeddings), the speed-up is 3.7× and 2.5×, respectively, getting on par with a flat column storing the same number of values. The row reader’s advantage grows with the list length: it has to materialize one list object per record, an overhead the fast path can’t remove. At short lists (many records), that cost dominates and the win is minor, whereas for long lists (few records) it essentially vanishes and the fast path brings the row reader down to the flat-column floor.
In the following, we’ll take a closer look at why Parquet in its current form isn’t optimal for storing fixed-length lists and how Hardwood’s fixed-length list fast path makes up for it.
Parquet’s Dremel Encoding
First, let’s explore how exactly Parquet stores nested and repeated data.
The storage representation is described in the seminal Dremel paper from 2010.
An optional list, i.e. a list which itself can be null, of optional elements has the following schema:
1
2
3
4
5
optional group mylist (LIST) {
repeated group list {
optional float element;
}
}
This three-level encoding is required to tell apart null and empty lists from null elements.
Parquet uses the notion of definition levels to encode which elements in the serialized data are null.
In the case of mylist, the maximum definition level is 3:
-
the entire list is null (definition level = 0)
-
the list is present but empty (definition level = 1)
-
the list contains a null element (definition level = 2)
-
the list contains an actual value (definition level = 3)
The notion of repetition levels is used to express at which level of the (potentially deeply nested) document tree elements are repeated. In our example, the maximum repetition level is 1: a value either continues the list of the current record (repetition level = 1), or a new record’s list starts (repetition level = 0).
As an example, let’s consider a Parquet file with four records which contain the following mylist values: [1.0, null, 1.2], null, [], [4.0, 4.1].
Here are the value stream as well as the definition- and repetition-level streams:
The value stream solely by itself would be ambiguous;
when reading it back, you wouldn’t know to which record a given value belongs and where null values sit.
The definition-level stream encodes the null and empty values,
while the repetition-level stream establishes the record boundaries.
This mechanism is great for encoding lists which actually are of varying lengths and which may contain null elements as well as may be null themselves.
Now let’s take a look at an example of required (i.e. non-optional) fixed-length lists of required elements (max def = 1):
The definition levels are now a constant stream of 1s;
while this can be encoded very efficiently using run-length encoding,
we’d ideally not store anything for this at all, as the non-nullness already is part of the data schema.
The repetition levels are a recurring sequence of one 0 followed by n - 1 1s, with n being the fixed length of our lists: 0,1,1,0,1,1,0,….
That’s about the most inefficient way you could think of for encoding a constant n,
so it is understandable that the Parquet community is exploring alternatives for storing fixed-length lists more efficiently.
Now, the disk footprint is not that much of an issue, as this data encodes tightly. The issue is the processing overhead: Definition- and repetition-level streams need to be decoded, arrays for them allocated, the reader needs to keep track when to start a new record with a new list, etc. All this adds up, leading to the 3× slow-down mentioned above.
Reading Effectively-Fixed-Length Lists Faster
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 record start and up to seven subsequent 1s.
If the list length is longer—there are more 1s left—any remaining 1s are put into an RLE run.
This means we need to either look for a series of bit-packed runs (n ≤ 8) or for alternating bit-packed and RLE runs.
If the def-level gate has been passed,
the fixed-length list detector tries to detect small n rep levels first.
n itself is the distance between the first zero and the next zero.
Bit-packing a periodic bit pattern yields a periodic byte pattern, with period n / gcd(n, 8) bytes:
a single byte when n divides 8 (n in {1,2,4,8}), or 3/5/7 bytes otherwise.
For example, for n = 4 the stamp is one byte, 0xee (0 1 1 1 0 1 1 1, read LSB-first),
i.e. the lists of two records are covered by one byte:
If n = 3, the stamp is three bytes, B6 6D DB, spanning eight records (24 bits).
Both single-byte and multi-byte stamps are calculated once and then applied in batches,
reading eight rep-level bytes at a time into one long.
If a given small-n rep-level stream doesn’t match the stamping pattern at some point, this means it contains lists of varying lengths and the fast path can’t be taken.
This technique (SWAR, SIMD within a register) proved fast enough during benchmarking1.
Next, let’s discuss the case where n ≥ 16;
here we need to look for the recurring sequence of a bit-packed run at the record boundary followed by an RLE run of n - 8 1s.
In the common case each record lands on a byte boundary, so every record is the same sequence of bytes.
As an example, for n = 16, we’d have four bytes per record:
We only need to parse the rep levels of the first record, so we can derive n and the stride (in bytes) and then can check whether the whole stream is that stride repeated. It is byte-periodic with period strideBytes, so the stream shifted left by one stride must equal itself.
That one bulk compare replaces per-value rep-level processing.
|
The exact byte split shown, a bit-packed boundary group plus an RLE run, is what mainstream encoders emit, including parquet-java and Arrow C++. It is encoder-dependent, however. The Parquet specification itself only requires that the rep levels decode to the right sequence, not how the RLE/bit-packing hybrid chunks them into runs. Therefore, the detector doesn’t hardcode any specific pattern; instead, it derives the stride from the first record and verifies that the rest of the stream repeats it, deferring to the scalar fallback described below for any layout it doesn’t recognize. |
The third and final scenario is where 9 ≤ n ≤ 15.
In this case, there’s no per-record stride to bulk-compare:
For instance, the rep levels of a 9-element list are nine bits; against eight-bit bytes its boundary drifts by one bit each record and only realigns every lcm(8, 9) = 72 values.
A scalar fallback handles these cases, processing the rep levels run by run, ensuring equal distance between record boundaries.
It reads each run’s header and scans bit-packed groups in 64-bit words at a time, while skipping RLE runs of 1s in O(1) rather than expanding them.
As soon as two records disagree in length, the page is rejected from the fast path.
Because it assumes nothing about the layout, this path also catches the rarer irregular cases:
one-element lists, or writers that split runs unusually.
Performance Gains
Now, what do we actually gain by applying this logic — what exactly is the "fixed-length list fast path" once we have determined that the lists in a given page are all of the same length? A number of optimizations can be applied in this case:
-
values are copied page-wise, rather than processed element by element
-
offsets are trivial—no rep-level scan is required to recover record boundaries
-
def- and rep-level arrays are never materialized, reducing GC pressure
The effect is substantial.
The fast path is opt-in currently,
so we can easily measure the parse times of fixed-length lists with and without the optimization.
The chart shows a sweep of n from 1 all the way up to 1536.
For the column reader the advantage hovers around 2.5× across most of the sweep.
The shaded band flags the scalar-fallback widths (n = 9–15), which aren’t byte-aligned and so make the detector’s rep-level scan fall back to a slower bit-by-bit walk—visible here as a slight dip in the column curve, and the detector’s most expensive case (which we quantify below).
The row reader has a more pronounced shape, climbing to a peak of around 3.9× in the mid-range (n ≈ 64–256) before settling to 3.6× for large lists.
The rare pathological case of lists with a length of 1 is the one exception:
with a single element per record, list-object creation dominates and the fast path brings no advantage for the row reader—if anything, it’s a tiny bit slower2.
Of course, running this detection logic over the encoded def-level and (in particular) rep-level streams has a cost of its own.
So does it penalize a regular variable-length LIST column?
The computational cost for the detector heavily depends on the list size and the applied pattern logic:
for n ≤ 8, where bit-packed runs of all rep levels need to be walked, it is up to ~1.7% of the regular list retrieval cost (latency).
For larger n, the highly efficient RLE runs bring detection down toward O(records) complexity, so the relative cost falls from ~0.2% (for n = 16) to under 0.1% (n = 768).
As expected, the most expensive case is the scalar fallback, with a relative detector overhead of ~17% for n = 15.
However, these are the pure detection latencies measured in isolation in a microbenchmark.
When looking at actual end-to-end parsing times,
the fast-path detector cost is negligible for all values of n.
Even in the absolute worst case, where only the very last list in a page has a different length than all the lists before—i.e. the detector’s O(1) def-level gate passes and it then scans the entire rep-level stream before finding the odd list at the very end and falling back to the regular decode path—there’s no measurable impact on the overall processing time for all list sizes but one.
Only for n = 15 (an uncommon width, and the most expensive scalar fallback case) is there an overhead of ~2%, just outside the 99.9% confidence intervals.
|
The benchmarks in this post are based on JMH, running three forks with five measurements each. Benchmarking was done with Java 25 (Temurin build) on an AWS m7i.2xlarge instance (8 vCPU / 4 physical cores; 32 GB of RAM). Hardwood parallelizes page decoding internally, so the reads exercise all cores. Files were served from the operating system’s page cache. To account for run-to-run variability, the throughput benchmarks (the two charts above) were each run three times and the per-point median is shown. The detector micro-benchmarks further down are single JMH runs of five forks each. The benchmarks also contain a correctness gate that verifies the fast path and the regular parsing routine decode bit-identical values. The complete benchmark source code and the raw numbers from all runs can be found here. |
Summary
Until the fixed-length list support is added to the Parquet format, it’s sub-optimal for storing data such as vector embeddings, triggering a costly retrieval of list boundaries from the file’s repetition-level stream. However, by examining the encoded repetition levels and looking for the patterns clearly identifying actually fixed-length lists, Hardwood’s Parquet parser significantly reduces the reading times for such lists, yielding improvements of up to 2.7× for the column reader and up to 3.9× for the row reader, depending on the specific list lengths.
While the definition-level optimization discussed above is relatively common,
I’m not aware of any mainstream Parquet parser that applies the encoded repetition-level inspection
(if you know of any parser doing this, I’d love to learn about it in the comments below).
This optimization is part of the upcoming Hardwood 1.1.0.Beta1 release.
It currently must be explicitly enabled by setting the parser option hardwood.fixed-list-fast-path to true,
but we expect to enable it by default for the 1.1 release barring any unforeseen issues.
So if you’re storing embeddings, coordinates, or other fixed-length vectors in Parquet, give it a try and see for yourself how much of the list-decoding overhead falls away in your case. Note that the numbers reported above come from relatively large (~450-500 MB) files; on smaller inputs the wins tend to be not quite as large, yet still substantial. Once the Parquet format has a proper fixed-length list type, that optimization should become unnecessary for newly written files. But until then, and for all the list-encoded data already out there, a little inspection of the encoded levels goes a long way.