Hi all,
I realize my words in the previous message were very harsh and uncalled
for. I would like to apologize to Prateek for being so dismissive of the
work he put in. These explorations are very valuable for the community,
regardless of which words are used to convey them.
To come back to the concrete topic, IMHO what's missing now is a
higher-level document explaining the problem we're trying to solve, and
comparing various solutions:
- current DELTA_BINARY_PACKED
- PFOR or a custom variation thereof
- FastLanes or a custom variation thereof
- [*optional*: optimized DELTA_BINARY_PACKED - see my earlier message in
this thread]
- [*optional*: a new encoding with the same structure as
DELTA_BINARY_PACKED, but with interleaved value streams (e.g. miniblocks
of 32*8 values with 8 values/stream and 8 independent delta accumulators)]
These would ideally be compared on the following 3 axes:
1. speed
2. storage efficiency
3. development and maintenance effort
Point number 3 is what's currently missing from the various evaluation
efforts, but I think it's what critically separates a tremendous idea
from working production-quality code. :-)
Also, after chatting with Prateek I'm convinced that he's enthusiastic
about these developments but also about open source development in general.
Thanks again Prateek for the work!
Best regards
Antoine.
Le 29/09/2026 à 09:37, Antoine Pitrou a écrit :
Hello Prateek,
I've tried several times to read and parse your sentences. They all look
like AI-generated gibberish to me.
Can I ask you to rephrase this as a human (no, please don't delegate
this to a LLM)?
Similarly, the descriptions for your PRs are all AI-generated. Please
reformulate like a human talking to a human.
Thank you
Antoine.
Le 18/09/2026 à 20:12, PRATEEK GAUR a écrit :
Hi Antoine,
You hit the nail on the head. Your intuition about breaking the sequential
dependency using a
vectorized prefix sum (a log-step scan) is exactly right.
In fact, I completely agree that optimizing the existing format is crucial
for immediate impact.
I dug into this recently and actually have three draft PRs open against
Parquet C++ (under
issue #51268) that do exactly what you are suggesting.
Specifically, PR #51295 [3] implements the exact log-step SIMD scan you
described. Combined with
batched miniblock unpacking (PR #51250) [2], it yields about a 2.15x
speedup on narrow 32-bit
pages on Graviton4.
With that said: even when compared against this newly optimized, vectorized
DELTA_BINARY_PACKED baseline, the FastLanes transposed layout (FL_ORDER) is
still roughly
2x faster on top of that. (Also the document introduces interleaved layout
in addition to FL_ORDER).
The difference comes down to how much work the CPU has to do:
1. Vectorized DELTA_BINARY_PACKED (Software): Because the values are stored
sequentially, the
CPU has to execute a log-depth tree of cross-lane shifts and adds to
accumulate the totals
within the vector.
2. FastLanes FL_ORDER (Layout): By rearranging the bits on disk so that a
lane gets its own
contiguous run of values, the decoder requires zero cross-lane
communication. It just issues
standard, vertical SIMD ADDs, advancing 32 independent dependency chains
perfectly in parallel.
So you are absolutely right that we can (and should!) make the existing
DELTA_BINARY_PACKED
much faster right now. But the benchmark data shows that solving the
dependency chain at the
layout level still extracts about twice (more on hardware that Kosta tried
on) as much performance
as solving it in software.
So my thinking is :
1) We should definitely optimize the DELTA_BINARY_PACKED.
2) In addition we should give serious thought to interleaving + fl_order
3) PFOR can use both sequential bit packing or fl_order/interleave based on
a flag.
Thanks,
Prateek
[1] https://github.com/apache/arrow/pull/51249
[2] https://github.com/apache/arrow/pull/51250
[3] https://github.com/apache/arrow/pull/51295 (not yet stacked on top of
#51249)
On Fri, Sep 18, 2026 at 10:25 AM Antoine Pitrou <[email protected]> wrote:
Le 18/09/2026 à 16:53, PRATEEK GAUR a écrit :
For Delta encoding, the transposed layout looks highly promising:
Standard Delta encoding forces the CPU to calculate values
sequentially,
which slows things down. The FastLanes container fundamentally
breaks this
bottleneck by splitting the work into parallel streams. Using its
recommended layout (FL_ORDER), we saw a massive decoding speedup with
virtually no impact on file size.
This begs the question: can an equivalent optimization be implemented
for regular DELTA_BINARY_PACKED?
The main difficulty of DELTA_BINARY_PACKED decoding is the sequential
dependency when accumulating each delta with the previous value.
However, I think the sequential dependency can be broken up:
1. Partial accumulation per miniblock: for each miniblock, build a
cumulated sum of deltas (cum_deltas) with 0 as the start value. A
cumulated sum is inherently sequential, but several cumulated sum
computations can be interleaved (probably 4 or 8 of them) to enable some
parallelism on the CPU. By carefully laying out the arrays of deltas and
cum_deltas, SIMD might even be exploitable.
2. Final accumulation step: for each miniblock, add the previous
miniblock's last value to its cum_deltas, which gives you the final
decoded output. This is an inherently vectorizable sum; the only
sequential dependency is between miniblocks (you need to wait for a
miniblock's last value to start handling the next miniblock), so this
should be quite fast.
Am I missing something?
I will mention I know nothing about Fastlanes; currently I don't really
have the time to read about it, so I have no idea whether other factors
might make it faster or slower, or more or less space-spacing than the
idea above.
However, given that DELTA_BINARY_PACKED is already widespread, a
solution to make its decoding faster sounds better than introducing an
entirely different integer encoding that people won't use before years.
Regards
Antoine.
