Hi Alkis, Great. This aligns with with the separation I too had settled on. >From what I heard almost all had reached a similar consensus. If someone has a different opinion please let me know on this thread. Would be great to hear your thoughts.
With that I'll continue to work towards gathering the numbers and refine the fastlanes proposal/implementation separately from the PFOR proposal as the PFOR delta mode (just like our ALP proposal) can have an enum to determine its underlying layout/packing. Best Prateek On Wed, Sep 23, 2026 at 11:25 PM Alkis Evlogimenos < [email protected]> wrote: > 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. >>> > > >>> > > >>> > > >>> > >>> >>
