Agreed we should decouple. On Tue, Sep 22, 2026 at 8:34 PM PRATEEK GAUR <[email protected]> wrote:
> @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. >> > > >> > > >> > > >> > >> >
