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