Thanks Andrew, > Rename to FASTLANES (patched frame of reference + Delta encoding) I found FastLanes to be a slighly overloaded term :), I fear we might overload it further more with our Patched (FOR + Delta with unified transposed layout) proposal. But yes with delta mode it can't be called PFOR anymore. No strong preferences here, I'm fine with FastLanes naming too. Anyone else has any other suggestions?
> Include Unified Transpose Layout (UTL) I agree with your point that going from zero to a spec acceptance takes time with consensus building. Furthermore with staged rollout PFOR first and then augmenting it with UTL layout for delta mode might increase the total time for adoption. What I feared was with more complex implementation (even though auto vectorized) might result in slower adoption across engines. I remember Martin mentioning that they had to be very careful when implementing it in Rust. I'll try to research a bit on this point and get back. Best Prateek On Tue, Nov 10, 2026 at 2:06 PM Andrew Lamb <[email protected]> wrote: > Thank you for this writeup Prateek. > > Here is some feedback: > > > Separately from PFOR, the existing DBP decoder can be made faster today. > > This is always a good idea in my opinion > > ## Rename to FASTLANES (patched frame of reference + Delta encoding) > > I recommend we change the name of this proposal to FASTLANES because that > term already has significant mindshare (we won't have to educate people > about what PFOR is, why it works, etc) -- we can refer them to the > literature and other implementation. > > Note I am not suggesting we include RLE, which is also mentioned in the > paper. > > ## Include Unified Transpose Layout (UTL) > > I think we need to maximize the competitiveness of this new encoding with > the current state of the art for adoption. The 4x additional speedup given > by UTL will be meaningful, and I think there is important benefits for GPU > and other accelerators. Given how long it takes to get consensus, and roll > encodings out, I doubt we'll have an ability to add an alternate layout > anytime soon. > > Thus, while I understand the concerns about additional implementation > complexity, I hope it will be all that bad -- the real complexity is > squeezing the maximum speed, but the basic (hope-for-auto-vectorization) > implementation I think doesn't add that much more complexity. > > If we include UTL in general, that naturally means we would use it for > efficient delta encoding decoding as well I think, which I think resolves > the final point. > > Andrew > > > On Wed, Nov 4, 2026 at 7:26 PM PRATEEK GAUR <[email protected]> wrote: > > > Hi all, > > > > Thanks, Antoine, for proposing this comparison framework. Following the > > earlier mailing-list > > discussions, I compared the options across the three areas you > identified: > > speed, storage > > efficiency, and development and maintenance effort. I also tried to > > consider the likely reader-adoption > > cost across implementations. > > > > *TL'DR* : My current preference for the 4 outstanding decisions is > > summarized below. > > > > Initial PFOR design > > |-- Include PFOR-Frame > > | `-- Start with conventional bit packing > > | `-- Evaluate interleaving separately > > | > > `-- Include PFOR-Delta > > |-- Payload: DBP layout, with or without patching > > | `-- Tentative preference: with exception patching > > | > > `-- Start with conventional ordering > > `-- Add FastLanes ordering as a follow-up > > > > > > *Longer version* : > > > > PFOR numbers at a glance (median over 43 datasets, Graviton4): > > > > Decode throughput (GB/s, higher is better) > > PFOR [####################] 27.14 GB/s > > LZ4 [### ] 4.32 GB/s > > BSS+LZ4 [## ] 2.86 GB/s > > DBP [## ] 2.33 GB/s > > BSS+ZSTD [## ] 2.23 GB/s > > > > Compression ratio (higher is better) > > PFOR [####################] 4.03x > > BSS+ZSTD [################## ] 3.68x > > DBP [################# ] 3.33x > > BSS+LZ4 [################ ] 3.23x > > LZ4 [####### ] 1.36x > > > > Conventional PFOR reaches great decoding speeds using *widely available > > fixed-width bit-unpacking* > > primitives. Given these results, I see four remaining PFOR design > > decisions. I lay out my preference > > and reasoning alongside it. > > > > 1. PFOR-Frame only vs. PFOR-Frame plus PFOR-Delta > > > > - *Decision*: Should the initial PFOR specification include Delta mode > > alongside Frame mode? > > - *My view*: Include Delta mode. > > - *Reason*: It improves compression for sorted or slowly changing integer > > columns such as timestamps > > and sequential identifiers. Each 1,024-value vector (or whatever vector > > size the format settles > > on) starts its own delta chain, so a reader can still seek to any > vector > > without decoding the ones > > before it. Including Delta initially also avoids a later format > > extension. > > > > [Datapoints] Where Delta mode helps (compression ratio, and decode speed > in > > GB/s, on columns where > > the writer chose Delta): > > > > Column Frame only Frame + Delta Decode speed > > MonotoneRowId 3.2x 194x 27 -> 8 > > Sawtooth 2.7x 72x 28 -> 8 > > SortedKeys 3.3x 14x 28 -> 8 > > SortedUnixTime 2.7x 10x 28 -> 8 > > SensorDropouts 1.9x 2.8x 27 -> 7 > > > > 2. DBP layout: with or without exception patching > > > > - *Decision*: Should the delta payload be plain DBP > (DELTA_BINARY_PACKED), > > or the DBP layout plus > > exception patching? > > - *My view*: DBP plus exception patching. > > - *Reason*: My first PFOR-Delta experiments used a single delta chain > over > > 1,024 values, with > > exceptions patched the same way as in PFOR-Frame mode, and it decoded > > faster than DBP. After > > changing a few parameters of the DBP layout and using a vectorized > > decoder, DBP decodes at similar > > speed, so decode speed is no longer the deciding factor. What remains > is > > whether to add patching. > > Patching helps with outliers, such as a temperature series with > > occasional anomalous readings. > > Without it, one outlier forces a wider bit width on the whole group of > > values that shares it. With > > it, the outlier is stored separately and the common deltas stay narrow. > > For example, on a sensor > > series with dropout readings in our dataset, PFOR-Delta with patching > > stored about 27% fewer bytes > > than plain DBP. > > *It also lets us reuse the existing DBP code and extend it, instead of > > adding a second delta payload (resuse existing code and easier > > maintainability).* > > > > 3. Conventional vs. interleaved packing for PFOR-Frame > > > > - *Decision*: Should PFOR-Frame use lane-interleaved bit packing for SIMD > > execution? > > - *My view*: Evaluate interleaving separately and add it as a follow-up. > > - *Reason*: Interleaving did show good promize for narrow widths and I > saw > > 40-50% faster decoding in > > experiments. But requiring it in the initial specification would make > > every implementation add new > > unpacking kernels, which could delay PFOR adoption. With conventional > > bit-unpacking kernels, > > which are already widely available, PFOR already decodes more than 10x > > faster than BSS+ZSTD. > > > > 4. Conventional vs. FastLanes ordering for PFOR-Delta > > > > - *Decision*: Should PFOR-Delta use FastLanes ordering? > > - *My view*: Evaluate FastLanes separately and add it as a follow-up. > > - *Reason*: It shows promising decode improvements for delta layouts, but > > it also carries substantial > > cross-language implementation cost: a new physical ordering, > specialized > > decode paths, and coordinated > > reader and writer adoption. Including it now could delay PFOR adoption > > for the same reason as interleaved > > packing. So I'd like to take it up as a follow up. > > > > Separately from PFOR, the existing DBP decoder can be made faster today. > > These are reader-only > > changes that need no format or layout change, so they speed up every > > existing DBP file. I suggest we > > continue that work alongside the PFOR proposal. (I'll take that up next) > > > > I welcome feedback on the measurements, the decision breakdown, and > > especially the implementation > > and adoption assumptions. > > > > PFOR: > > > > > https://docs.google.com/document/d/1ZZOtxmq6K8pNU0npijfSglTJVkspXL5GLDKPSGj9HlA > > FastLanes: > > https://docs.google.com/document/d/1L2pfrHfAZG4vKTHc-OD8p9alIUD-sUFg > > > > Thanks, > > Prateek > > > > On Wed, Sep 30, 2026 at 9:51 PM Julien Le Dem <[email protected]> wrote: > > > > > 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. > > > > > >>> > > > > > >>> > > > > > >>> > > > > > >> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
