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. > > > > > > >
