You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@parquet.apache.org by Andrew Lamb <an...@gmail.com> on 2025/10/30 21:09:27 UTC
Discussion: Dynamic encoding selection for Paruqet
Hello,
I wanted to start a discussion about adaptive encoding selection as a way
to improve the performance of Parquet implementations that we started at
the sync earlier this week.
Specifically the question came up "would we need to specify some way in the
spec to pick between any new encodings" and I think the consensus answer
was "no, that would be up to the writer implementation"
At the moment, all open source Parquet implementations I know of have a
simple heuristics for choosing the encoding, but we are discussing a more
dynamic encoding advisor in arrow-rs (thanks MapleFU)[1] . Are there other
conversations that people are aware of?
Andrew
p.s. This is part of a larger point and misconception about the Parquet
format, specifically that the choice of encoding is dictated by the
format. Many new file format proposal such as BtrBlocks[2] include a
dynamic approach to encoding selection (after claiming that "Parquet" uses
static heuristics):
> In BtrBlocks, we test each encoding scheme on a sample and select the
scheme that performs best.
(the paper then proposes a sampling technique to avoid skewed samples)
[1]: https://github.com/apache/arrow-rs/issues/8378
[2]: https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/papers/btrblocks.pdf
Re: Discussion: Dynamic encoding selection for Paruqet
Posted by Alkis Evlogimenos <al...@databricks.com.INVALID>.
When the input data fits a zipf distribution, assigning ids on values when
they are first seen gets *very* close to the "optimal" dictionary with ids
ordered by frequency. I have done such experiments in the past for web and
email data and the natural method of assign ids on first seen was giving
ids that were not far from optimal - for such large data. I do not recall
the exact numbers but sorting ids to get the optimal assignment was not
resulting in a large enough compression improvement to justify the
complexity.
Writers typically assign ids as above so it should work for all writers.
On Mon, Nov 10, 2025 at 11:44 AM Antoine Pitrou <an...@python.org> wrote:
> On Mon, 10 Nov 2025 09:17:31 +0100
> Alkis Evlogimenos
> <al...@databricks.com.INVALID>
> wrote:
> > DELTA_BINARY_PACKED of dictionary ids makes sense if writer assigns ids
> in
> > frequency order and the input values fit some power law/zipf
> distribution.
>
> Does any writer actually do that, though? Parquet data is typically
> written page per page, and the column chunk's unique dictionary page
> will grow in column data order.
>
> Regards
>
> Antoine.
>
>
>
Re: Discussion: Dynamic encoding selection for Paruqet
Posted by Antoine Pitrou <an...@python.org>.
On Mon, 10 Nov 2025 09:17:31 +0100
Alkis Evlogimenos
<al...@databricks.com.INVALID>
wrote:
> DELTA_BINARY_PACKED of dictionary ids makes sense if writer assigns ids in
> frequency order and the input values fit some power law/zipf distribution.
Does any writer actually do that, though? Parquet data is typically
written page per page, and the column chunk's unique dictionary page
will grow in column data order.
Regards
Antoine.
Re: Discussion: Dynamic encoding selection for Paruqet
Posted by Alkis Evlogimenos <al...@databricks.com.INVALID>.
DELTA_BINARY_PACKED of dictionary ids makes sense if writer assigns ids in
frequency order and the input values fit some power law/zipf distribution.
For example, say we get half a million dictionary ids but most values are
concentrated in the first 500 ids. RLE will use bitwidth of 19 but most
miniblocks will have small deltas (<500) and will pack very well in <= 9
bits.
On Sun, Nov 9, 2025 at 11:03 AM Antoine Pitrou <an...@python.org> wrote:
> On Mon, 3 Nov 2025 08:26:00 +0100
> Alkis Evlogimenos
> <al...@databricks.com.INVALID>
> wrote:
> >
> > We could bring Parquet closer to nested encodings by changing the spec a
> > bit without adding new encodings:
> > 1. present dictionary encoding as a transformation from any domain to the
> > integer domain
> > 2. allow encoding integers with PLAIN, RLE, DELTA_BINARY_PACKED and
> > BYTE_STREAM_SPLIT
>
> I'm not sure delta-encoding of dictionary ids makes much sense? Unless
> perhaps the "active" subset of the dictionary changes slowly along a
> column.
>
> > 3. "add" the new encodings (RLE_DICTIONARY exists): DELTA_DICTIONARY,
> > BYTE_STREAM_SPLIT_DICTIONARY
> >
> > This would add more decisions to the writer and potentially generate
> better
> > Parquet files. That said I don't see BYTE_STREAM_SPLIT being super useful
> > for dictionary ids. DELTA_BINARY_PACKED may be better than RLE in some
> > cases though.
>
> Given that dictionary ids are generally small integers,
> BYTE_STREAM_SPLIT could increase their compressibility quite a bit. How
> it would fare compared to RLE is an open question.
>
> Regards
>
> Antoine.
>
>
>
Re: Discussion: Dynamic encoding selection for Paruqet
Posted by Antoine Pitrou <an...@python.org>.
On Mon, 3 Nov 2025 08:26:00 +0100
Alkis Evlogimenos
<al...@databricks.com.INVALID>
wrote:
>
> We could bring Parquet closer to nested encodings by changing the spec a
> bit without adding new encodings:
> 1. present dictionary encoding as a transformation from any domain to the
> integer domain
> 2. allow encoding integers with PLAIN, RLE, DELTA_BINARY_PACKED and
> BYTE_STREAM_SPLIT
I'm not sure delta-encoding of dictionary ids makes much sense? Unless
perhaps the "active" subset of the dictionary changes slowly along a
column.
> 3. "add" the new encodings (RLE_DICTIONARY exists): DELTA_DICTIONARY,
> BYTE_STREAM_SPLIT_DICTIONARY
>
> This would add more decisions to the writer and potentially generate better
> Parquet files. That said I don't see BYTE_STREAM_SPLIT being super useful
> for dictionary ids. DELTA_BINARY_PACKED may be better than RLE in some
> cases though.
Given that dictionary ids are generally small integers,
BYTE_STREAM_SPLIT could increase their compressibility quite a bit. How
it would fare compared to RLE is an open question.
Regards
Antoine.
Re: Discussion: Dynamic encoding selection for Paruqet
Posted by Alkis Evlogimenos <al...@databricks.com.INVALID>.
Picking the right encoding for parquet is much simpler than btrblocks or
fastlanes. The latter have to search a tree of nested encodings up to some
depth whereas for parquet the "tree" is fixed.
As we add more encodings, encoding selection will require a more
sophisticated search.
Right now the decision tree for Parquet is rather simple:
1. try dictionary, if profitable encode data pages with RLE [1]
2. if not dictionary
a. if strings try DELTA_LENGTH_BYTE_ARRAY or DELTA_BYTE_ARRAY and pick
the best
b. otherwise try DELTA_BINARY_PACKED or BYTE_STREAM_SPLIT
3. finally decide on Page v1 or v2 (sometimes v1 is better than v2)
We could bring Parquet closer to nested encodings by changing the spec a
bit without adding new encodings:
1. present dictionary encoding as a transformation from any domain to the
integer domain
2. allow encoding integers with PLAIN, RLE, DELTA_BINARY_PACKED and
BYTE_STREAM_SPLIT
3. "add" the new encodings (RLE_DICTIONARY exists): DELTA_DICTIONARY,
BYTE_STREAM_SPLIT_DICTIONARY
This would add more decisions to the writer and potentially generate better
Parquet files. That said I don't see BYTE_STREAM_SPLIT being super useful
for dictionary ids. DELTA_BINARY_PACKED may be better than RLE in some
cases though.
On Fri, Oct 31, 2025 at 3:38 AM wish maple <ma...@gmail.com> wrote:
> Generally I think encoded size can be a good target at first. And duckdb
> does well on pick dictionary and bloom filter, and split the page by row.
> However, seems that duckdb wouldn't pick the encoding algorithm
> in parquet-v2.
>
> Picking dictionary might be straightforward sometimes, however, picking
> row-group size and split pages would affect by reader workloads and
> writer memory limit.
>
>
> Best,
> Xuwei Fu
>
> Kenny Daniel <pl...@gmail.com> 于2025年10月31日周五 09:15写道：
>
> > It would be great if there were more discussion of these encoder choices.
> > Authoring hyparquet reader was more straightforward in some ways than
> > authoring the writer. A million little choices came up, and sometimes I
> > would just guess, and other times I would look at reference
> implementations
> > (mostly duckdb because it has the cleanest code of all the parquet
> > implementations imo)
> >
> > Examples:
> >
> > - Choosing between RLE and bitpack in bitpacked hybrid encoding (try
> > both
> > <
> >
> https://github.com/hyparam/hyparquet-writer/blob/v0.8.0/src/encoding.js#L14-L24
> > >
> > )
> > - When to use dictionary encoding? (non-boolean columns where rows /
> > unique > 2
> > <
> >
> https://github.com/hyparam/hyparquet-writer/blob/v0.8.0/src/column.js#L91-L100
> > >
> > )
> > - When to split pages? By row count? By compressed bytes? By
> > uncompressed bytes?
> > - Default row group size?
> >
> >
> >
> >
> > On Thu, Oct 30, 2025 at 2:09 PM Andrew Lamb <an...@gmail.com>
> > wrote:
> >
> > > Hello,
> > >
> > > I wanted to start a discussion about adaptive encoding selection as a
> way
> > > to improve the performance of Parquet implementations that we started
> at
> > > the sync earlier this week.
> > >
> > > Specifically the question came up "would we need to specify some way in
> > the
> > > spec to pick between any new encodings" and I think the consensus
> answer
> > > was "no, that would be up to the writer implementation"
> > >
> > > At the moment, all open source Parquet implementations I know of have a
> > > simple heuristics for choosing the encoding, but we are discussing a
> more
> > > dynamic encoding advisor in arrow-rs (thanks MapleFU)[1] . Are there
> > other
> > > conversations that people are aware of?
> > >
> > >
> > > Andrew
> > >
> > > p.s. This is part of a larger point and misconception about the
> Parquet
> > > format, specifically that the choice of encoding is dictated by the
> > > format. Many new file format proposal such as BtrBlocks[2] include a
> > > dynamic approach to encoding selection (after claiming that "Parquet"
> > uses
> > > static heuristics):
> > >
> > > > In BtrBlocks, we test each encoding scheme on a sample and select the
> > > scheme that performs best.
> > >
> > > (the paper then proposes a sampling technique to avoid skewed samples)
> > >
> > > [1]: https://github.com/apache/arrow-rs/issues/8378
> > > [2]:
> https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/papers/btrblocks.pdf
> > >
> >
>
Re: Discussion: Dynamic encoding selection for Paruqet
Posted by wish maple <ma...@gmail.com>.
Generally I think encoded size can be a good target at first. And duckdb
does well on pick dictionary and bloom filter, and split the page by row.
However, seems that duckdb wouldn't pick the encoding algorithm
in parquet-v2.
Picking dictionary might be straightforward sometimes, however, picking
row-group size and split pages would affect by reader workloads and
writer memory limit.
Best,
Xuwei Fu
Kenny Daniel <pl...@gmail.com> 于2025年10月31日周五 09:15写道：
> It would be great if there were more discussion of these encoder choices.
> Authoring hyparquet reader was more straightforward in some ways than
> authoring the writer. A million little choices came up, and sometimes I
> would just guess, and other times I would look at reference implementations
> (mostly duckdb because it has the cleanest code of all the parquet
> implementations imo)
>
> Examples:
>
> - Choosing between RLE and bitpack in bitpacked hybrid encoding (try
> both
> <
> https://github.com/hyparam/hyparquet-writer/blob/v0.8.0/src/encoding.js#L14-L24
> >
> )
> - When to use dictionary encoding? (non-boolean columns where rows /
> unique > 2
> <
> https://github.com/hyparam/hyparquet-writer/blob/v0.8.0/src/column.js#L91-L100
> >
> )
> - When to split pages? By row count? By compressed bytes? By
> uncompressed bytes?
> - Default row group size?
>
>
>
>
> On Thu, Oct 30, 2025 at 2:09 PM Andrew Lamb <an...@gmail.com>
> wrote:
>
> > Hello,
> >
> > I wanted to start a discussion about adaptive encoding selection as a way
> > to improve the performance of Parquet implementations that we started at
> > the sync earlier this week.
> >
> > Specifically the question came up "would we need to specify some way in
> the
> > spec to pick between any new encodings" and I think the consensus answer
> > was "no, that would be up to the writer implementation"
> >
> > At the moment, all open source Parquet implementations I know of have a
> > simple heuristics for choosing the encoding, but we are discussing a more
> > dynamic encoding advisor in arrow-rs (thanks MapleFU)[1] . Are there
> other
> > conversations that people are aware of?
> >
> >
> > Andrew
> >
> > p.s. This is part of a larger point and misconception about the Parquet
> > format, specifically that the choice of encoding is dictated by the
> > format. Many new file format proposal such as BtrBlocks[2] include a
> > dynamic approach to encoding selection (after claiming that "Parquet"
> uses
> > static heuristics):
> >
> > > In BtrBlocks, we test each encoding scheme on a sample and select the
> > scheme that performs best.
> >
> > (the paper then proposes a sampling technique to avoid skewed samples)
> >
> > [1]: https://github.com/apache/arrow-rs/issues/8378
> > [2]: https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/papers/btrblocks.pdf
> >
>
Re: Discussion: Dynamic encoding selection for Paruqet
Posted by Kenny Daniel <pl...@gmail.com>.
It would be great if there were more discussion of these encoder choices.
Authoring hyparquet reader was more straightforward in some ways than
authoring the writer. A million little choices came up, and sometimes I
would just guess, and other times I would look at reference implementations
(mostly duckdb because it has the cleanest code of all the parquet
implementations imo)
Examples:
- Choosing between RLE and bitpack in bitpacked hybrid encoding (try both
<https://github.com/hyparam/hyparquet-writer/blob/v0.8.0/src/encoding.js#L14-L24>
)
- When to use dictionary encoding? (non-boolean columns where rows /
unique > 2
<https://github.com/hyparam/hyparquet-writer/blob/v0.8.0/src/column.js#L91-L100>
)
- When to split pages? By row count? By compressed bytes? By
uncompressed bytes?
- Default row group size?
On Thu, Oct 30, 2025 at 2:09 PM Andrew Lamb <an...@gmail.com> wrote:
> Hello,
>
> I wanted to start a discussion about adaptive encoding selection as a way
> to improve the performance of Parquet implementations that we started at
> the sync earlier this week.
>
> Specifically the question came up "would we need to specify some way in the
> spec to pick between any new encodings" and I think the consensus answer
> was "no, that would be up to the writer implementation"
>
> At the moment, all open source Parquet implementations I know of have a
> simple heuristics for choosing the encoding, but we are discussing a more
> dynamic encoding advisor in arrow-rs (thanks MapleFU)[1] . Are there other
> conversations that people are aware of?
>
>
> Andrew
>
> p.s. This is part of a larger point and misconception about the Parquet
> format, specifically that the choice of encoding is dictated by the
> format. Many new file format proposal such as BtrBlocks[2] include a
> dynamic approach to encoding selection (after claiming that "Parquet" uses
> static heuristics):
>
> > In BtrBlocks, we test each encoding scheme on a sample and select the
> scheme that performs best.
>
> (the paper then proposes a sampling technique to avoid skewed samples)
>
> [1]: https://github.com/apache/arrow-rs/issues/8378
> [2]: https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/papers/btrblocks.pdf
>