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