parquet: large dictionary-encoded binary values decode ~2x slower than parquet-cpp

[AarryaSaraf]

Describe the bug / limitation

Reading a Parquet column of large, distinct, dictionary-encoded binary values
through the parquet crate costs roughly 2× the wall time of reading the same
file with parquet-cpp (pyarrow.parquet.read_table). Rewriting the same data with
use_dictionary=False inverts the result — the crate is then slightly faster — so
the gap is specific to the dictionary decode path.

We found one contributing cause and have a patch for it (#10690), but it accounts
for only about a fifth of the gap. Most of it we cannot explain, which is why we
are filing this rather than just sending the patch.

The file shape

One file, 1024 rows, a binary() column of 256 KiB incompressible random values
plus an int64 column, single row group, page index written, ~256 MiB total,
written with PyArrow defaults.

The load-bearing property is a writer default rather than anything contrived.
use_dictionary=True is on and the 1 MB dictionary_pagesize_limit is checked
lazily, so the writer never falls back to plain. The dictionary page ends up
holding the entire 268 MB column, every value distinct, every dictionary entry
referenced exactly once, and every data page is just RLE keys. Any
PyArrow-default pipeline writing unique large binary values produces this.

Measurements

• parquet / arrow crate 59.1.0, read from Python over the C data interface
• pyarrow 24.0.0
• Linux, wall time at the read operation, 3 repeats per arm, medians

	wall
parquet-cpp (pq.read_table)	0.6148 s
parquet crate	1.2167 s
ratio	1.98

Caveats on those, stated up front because they bound how much they are worth:
n = 3 per arm with overlapping spreads, and the two arms come from runs whose
PyArrow baselines drifted structurally against each other, so we are quoting the
one uncontaminated baseline rather than an in-run normalizer. Treat 1.98 as "about
2×", not a precise figure.

Localization

These are macOS, and directional only — magnitudes from that machine are not
quotable for this shape (see the caveat at the bottom). They are what pointed us
at the dictionary path:

• A value-size matrix at equal total bytes loses at 256 KiB values but is at
  parity at 64 B. So the cost scales with value size, not row count, and it is
  not decompression.
• Rewriting the same data with use_dictionary=False gives a ratio of 0.93 —
  the crate is faster than parquet-cpp as soon as dictionary encoding is off.
• Profiling the decode (sample, ~4,300 decode samples) puts 54% under
  OffsetBuffer::extend_from_dictionary → memmove.

That last one points at extend_from_dictionary, which reserves offsets but
never values, so each gathered value is appended to an unreserved Vec<u8> and
amortized doubling re-copies roughly all the gathered data one extra time:

https://github.com/apache/arrow-rs/blob/main/parquet/src/arrow/buffer/offset_buffer.rs#L90-L110

Note that the 54% does not separate the reallocation copies from the gather
copy itself, which is unavoidable. Only the former is addressable — consistent
with the partial result below.

The partial fix, and the residual

#10690 pre-sizes values with an O(1) estimate. On the Linux box above:

• crate read wall median 1.2167 → 1.0700 s, min 1.0922 → 1.0261, rank-matched
  3/3 not-worse. The honest band is −6% to −12%.
• ratio against parquet-cpp 1.98 → 1.74

So the mechanism is real but minor. We had predicted the reserve would take the
ratio to ≤1.0 and it moved about a fifth of that, which is the main reason for
this issue: most of the gap is something else in the dictionary path, and we do
not know what.

We deliberately did not use the exact-sum reserve proposed in #5250 — we
reproduced its rejection on 59.1.0 (+8–18% on the three
arrow_array_reader/StringArray/dictionary encoded cases), because the second
bounds-checked pass over the keys costs more than the copy it saves at ~19-byte
values. The O(1) estimate measures at parity on those cases.

Caveat on our macOS numbers

We are not quoting any macOS magnitude for this shape. A null control there —
byte-identical code re-benched against its own saved baseline — reported "+43.6%
regressed, p = 0.00", and one case read 24.6 / 37.1 / 30.9 / 35.4 ms across four
builds, two of which were provably identical. The regime is allocation and
page-fault dominated on that machine and swings ±45% build to build. The
small-string cases are stable there (null control −0.6%, p = 0.40); the
large-value ones are not.

Question

1. Is there a known reason the dictionary gather path would be ~2× parquet-cpp on
   large distinct values, beyond the missing reservation?

AI disclosure

This report was drafted with AI assistance. The measurements, the analysis and
the conclusions are mine, and I have reviewed every claim above against my own
run records.