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. > > >
