@Alkis Evlogimenos <[email protected]> I found the layout proposed by fast lanes to be faster than the optimized implementation of DBP. So don't want to shelve it yet.
I dug deeper into fast lanes and did this study because when I proposed PFOR, people wanted a comparison with fast lanes. While experimenting and writing the above document I realized (and Kosta would agree here) that interleaving and fast lanes have their advantages and show promise, especially in the delta encodings. But at the same time I do think we can decouple this (fast lanes) from the PFOR discussion. Best Prateek On Tue, Sep 22, 2026, 10:18 AM Alkis Evlogimenos via dev < [email protected]> wrote: > When I read first about fastlanes I thought it would be great for parquet. > But since then we learned how to optimize DBP to decode fast by breaking > the data deps during decoding and doing parallel sums my take is that it > doesn't warrant the complexity of a new layout. A new layout means extra > onus on the parquet writer to decide yet another dimension (value layout) > so the search space for optimality doubles. PFOR doesn't need this because > the data dependence does not exist per value. > > I suggest we shelve fastlanes for now and reevaluate it when we have other > data dependent encodings in parquet. > > On Fri, Sep 18, 2026 at 8:12 PM PRATEEK GAUR <[email protected]> wrote: > > > 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. > > > > > > > > > > > >
