Hi Antoine, The doc was a little large as I tried to build on things step by step. And then I tried to explain why on certain hardware we didn't see any benefit. I'll try to trim down the content across those sections and see if I can still explain things with less verbosity.
Best, Prateek On Tue, Sep 29, 2026 at 12:38 AM Antoine Pitrou <[email protected]> wrote: > > 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. > >> > >> > >> > > > > >
