Thank you Prateek for putting this together. Julien On Wed, Sep 30, 2026 at 22:17 PRATEEK GAUR <[email protected]> wrote:
> Hi Antoine, > > It was great speaking with you this morning. Thanks for your time > and your follow-up. > > For a quick recap for the community here is how we arrived at this point: > - As a community, we have been exploring better encodings for numeric > data. > - After reviewing the literature and evaluating several approaches, we > proposed > PFOR for community consideration. > - During the PFOR discussion, the community asked for a comparison with > FastLanes. > - We studied the FastLanes paper and prepared an evaluation covering its > core > concepts, design rationale, and benchmark results. Some follow-up work > and > clarification are still needed. > - That evaluation produced several useful observations: > - Some data distributions benefit substantially from delta encoding, > making > delta decoding an important part of this work. > - The existing DELTA_BINARY_PACKED decoder can be improved without > changing > the format. Our implementation measured up to an 80% decoding-speed > improvement under the tested conditions. > - Our current results suggest that further substantial improvements to > delta > decoding may require a different physical layout. This is where ideas > from > FastLanes, particularly its transposed ordering, become relevant. > > I agree that we now need a higher-level document that clearly states the > problem, explains the motivation, and compares the available approaches in > one > place. I will prepare a follow-up comparing: > > - Current and optimized DELTA_BINARY_PACKED > - PFOR and PFOR-delta > - FastLanes-inspired layouts, including their possible use with delta > encoding > > I will evaluate them across the three dimensions you proposed: > Decoding speed, Storage efficiency and Implementation+maintenance cost. > > My current view, based on the available evidence, is: > - Improving the existing DBP decoder is valuable and can be done without > changing the format. > - PFOR is promising on wide variety of datasets we evaluated on. > - FastLanes-inspired ordering deserves further investigation for delta > decoding, where independent reconstruction chains may improve > performance. > > Peter Boncz suggested a few technical clarifications for the FastLanes > evaluation. I will incorporate those first and then follow up with the > broader > comparison. > > Thanks again, > Prateek > > > On Wed, Sep 30, 2026 at 7:40 AM Antoine Pitrou <[email protected]> wrote: > > > > > Hi all, > > > > I realize my words in the previous message were very harsh and uncalled > > for. I would like to apologize to Prateek for being so dismissive of the > > work he put in. These explorations are very valuable for the community, > > regardless of which words are used to convey them. > > > > To come back to the concrete topic, IMHO what's missing now is a > > higher-level document explaining the problem we're trying to solve, and > > comparing various solutions: > > > > - current DELTA_BINARY_PACKED > > - PFOR or a custom variation thereof > > - FastLanes or a custom variation thereof > > - [*optional*: optimized DELTA_BINARY_PACKED - see my earlier message in > > this thread] > > - [*optional*: a new encoding with the same structure as > > DELTA_BINARY_PACKED, but with interleaved value streams (e.g. miniblocks > > of 32*8 values with 8 values/stream and 8 independent delta > accumulators)] > > > > These would ideally be compared on the following 3 axes: > > 1. speed > > 2. storage efficiency > > 3. development and maintenance effort > > > > Point number 3 is what's currently missing from the various evaluation > > efforts, but I think it's what critically separates a tremendous idea > > from working production-quality code. :-) > > > > Also, after chatting with Prateek I'm convinced that he's enthusiastic > > about these developments but also about open source development in > general. > > > > Thanks again Prateek for the work! > > > > Best regards > > > > Antoine. > > > > > > > > Le 29/09/2026 à 09:37, Antoine Pitrou a écrit : > > > > > > 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. > > >>> > > >>> > > >>> > > >> > > > > > > > > > >
