Hey Prateek, I am not able to access https://docs.google.com/document/d/1L2pfrHfAZG4vKTHc-OD8p9alIUD-sUFg due to permissions.
-- Div On Tue, Sep 29, 2026 at 3:54 PM PRATEEK GAUR <[email protected]> wrote: > 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. > > >> > > >> > > >> > > > > > > > > > >
