You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@parquet.apache.org by Micah Kornfield <em...@gmail.com> on 2024/05/28 06:16:02 UTC
[DISCUSS] Encoding improvements (follow-up from Parquet "V3" discussion)
As a follow-up to the "V3" Discussions [1][2] I wanted to start a thread on
improvements to encodings.
There are several areas to pursue here:
1. Curating a standard set of benchmarks and criteria for determining if a
new encoding is worth adding.
2. Developing new encodings
3. Better implementations to select existing encodings.
4. Better support for encodings with point/indexed lookups.
5. Benchmarking frameworks that allow assessing trade-off of encodings on
storage systems with different latency/throughput.
Realistically, given my current commitments, I don't think I have bandwidth
to help with this track in the near term. If someone else would like to
help drive this and make concrete proposals in these areas it would be
greatly appreciated.
Thanks,
Micah
[1] https://lists.apache.org/thread/5jyhzkwyrjk9z52g0b49g31ygnz73gxo
[2]
https://docs.google.com/document/d/19hQLYcU5_r5nJB7GtnjfODLlSDiNS24GXAtKg9b0_ls/edit
Re: [DISCUSS] Encoding improvements (follow-up from Parquet "V3" discussion)
Posted by Micah Kornfield <em...@gmail.com>.
Great. BTW, I removed the encoding I referenced above from the PR to avoid
putting too much into at once:
I'm pasting the description below for posterity.
/** Encoding for variable length binary data that allows random access of
values.
*
* This encoding is designed for random access of BYTE_ARRAY values. It
is mostly useful in cases
* for non-nullable BYTE_ARRAY columns where determining the exact
offset of the value does not require
* parsing definition levels.
*
* The layout consists of the following elements:
* 1. byte_arrays - Byte Array values layed out contiguously. The
BYTE_ARRAYs are immediately contiguous to the cumulative
* offsets.
* 2. offsets: A contiguous set of signed N-byte little-endian
unsigned integers
* representing the end byte offset (exclusive) of a BYTE_ARRAY
value from
* the the beginning of the page. For simplicity of implementation
the 0 index is
* always as zero.
* 3. The last byte indicates the number of bytes used for offsets
(valid values are 1,2,3 and 4).
* Implementations SHOULD try to use the smallest byte value that
meets the length requirements.
*
* Note the order of lengths is reversed from DELTA_BINARY_PACKED to
allow for byte array values to
* potentially allow for incremental compression in the case of Data
Page V2 or other future data pages
* where values are compressed separately from nesting information.
*
* The beginning offset of the offsets can be determined using the
final offset element.
*
* An individual byte array element can be found at an index using the
following pseudo-code
* (real implementations SHOULD do bounds checking):
*
* return byte_arrays[offsets[index] : offsets[index+1]]
*
*
* Example encoding of "f", "oo", "bar1" (square brackets delimit the
components listed):
* [foobar1][0,1,3,7][1]
*/
On Wed, May 29, 2024 at 10:57 PM Gang Wu <us...@gmail.com> wrote:
> I'm interested in experimenting and implementing new encodings.
> Will follow up with concrete proposals or findings.
>
> Best,
> Gang
>
> On Thu, May 30, 2024 at 3:29 AM Ed Seidl <et...@live.com> wrote:
>
> > Maybe this is putting the cart too far in front of the horse, but I'd be
> > willing to implement an encoding like this to see if is a better
> > alternative to PLAIN and DELTA_LENGTH_BYTE_ARRAY as a dictionary
> > fallback for byte arrays, at least for GPU decoding. We might want to
> > change the name since it wouldn't be used exclusively for random access
> > any longer. Maybe LENGTH_BYTE_ARRAY? Or PLAIN_BYTE_ARRAY?
> >
> > I'll also raise my hand as interested in participating in all 5 of the
> > tasks outlined, as time permits.
> >
> > Cheers,
> > Ed
> >
> > On 5/28/24 11:05 PM, Micah Kornfield wrote:
> > > BTW, I did propose a new RANDOM_ACCESS_BYTE_ARRAY encoding (effectively
> > > Arrow's representation) as part footer improvements [1] to help allow
> for
> > > O(1) access to particular column metadata, once a column is identified.
> > >
> > > [1] https://github.com/apache/parquet-format/pull/250
> > >
> > > On Mon, May 27, 2024 at 11:16 PM Micah Kornfield <
> emkornfield@gmail.com>
> > > wrote:
> > >
> > >> As a follow-up to the "V3" Discussions [1][2] I wanted to start a
> thread
> > >> on improvements to encodings.
> > >>
> > >> There are several areas to pursue here:
> > >> 1. Curating a standard set of benchmarks and criteria for determining
> > if
> > >> a new encoding is worth adding.
> > >> 2. Developing new encodings
> > >> 3. Better implementations to select existing encodings.
> > >> 4. Better support for encodings with point/indexed lookups.
> > >> 5. Benchmarking frameworks that allow assessing trade-off of
> encodings
> > on
> > >> storage systems with different latency/throughput.
> > >>
> > >> Realistically, given my current commitments, I don't think I have
> > >> bandwidth to help with this track in the near term. If someone else
> > would
> > >> like to help drive this and make concrete proposals in these areas it
> > would
> > >> be greatly appreciated.
> > >>
> > >> Thanks,
> > >> Micah
> > >>
> > >>
> > >> [1] https://lists.apache.org/thread/5jyhzkwyrjk9z52g0b49g31ygnz73gxo
> > >> [2]
> > >>
> >
> https://docs.google.com/document/d/19hQLYcU5_r5nJB7GtnjfODLlSDiNS24GXAtKg9b0_ls/edit
> > >>
> >
> >
>
Re: [DISCUSS] Encoding improvements (follow-up from Parquet "V3" discussion)
Posted by Gang Wu <us...@gmail.com>.
I'm interested in experimenting and implementing new encodings.
Will follow up with concrete proposals or findings.
Best,
Gang
On Thu, May 30, 2024 at 3:29 AM Ed Seidl <et...@live.com> wrote:
> Maybe this is putting the cart too far in front of the horse, but I'd be
> willing to implement an encoding like this to see if is a better
> alternative to PLAIN and DELTA_LENGTH_BYTE_ARRAY as a dictionary
> fallback for byte arrays, at least for GPU decoding. We might want to
> change the name since it wouldn't be used exclusively for random access
> any longer. Maybe LENGTH_BYTE_ARRAY? Or PLAIN_BYTE_ARRAY?
>
> I'll also raise my hand as interested in participating in all 5 of the
> tasks outlined, as time permits.
>
> Cheers,
> Ed
>
> On 5/28/24 11:05 PM, Micah Kornfield wrote:
> > BTW, I did propose a new RANDOM_ACCESS_BYTE_ARRAY encoding (effectively
> > Arrow's representation) as part footer improvements [1] to help allow for
> > O(1) access to particular column metadata, once a column is identified.
> >
> > [1] https://github.com/apache/parquet-format/pull/250
> >
> > On Mon, May 27, 2024 at 11:16 PM Micah Kornfield <em...@gmail.com>
> > wrote:
> >
> >> As a follow-up to the "V3" Discussions [1][2] I wanted to start a thread
> >> on improvements to encodings.
> >>
> >> There are several areas to pursue here:
> >> 1. Curating a standard set of benchmarks and criteria for determining
> if
> >> a new encoding is worth adding.
> >> 2. Developing new encodings
> >> 3. Better implementations to select existing encodings.
> >> 4. Better support for encodings with point/indexed lookups.
> >> 5. Benchmarking frameworks that allow assessing trade-off of encodings
> on
> >> storage systems with different latency/throughput.
> >>
> >> Realistically, given my current commitments, I don't think I have
> >> bandwidth to help with this track in the near term. If someone else
> would
> >> like to help drive this and make concrete proposals in these areas it
> would
> >> be greatly appreciated.
> >>
> >> Thanks,
> >> Micah
> >>
> >>
> >> [1] https://lists.apache.org/thread/5jyhzkwyrjk9z52g0b49g31ygnz73gxo
> >> [2]
> >>
> https://docs.google.com/document/d/19hQLYcU5_r5nJB7GtnjfODLlSDiNS24GXAtKg9b0_ls/edit
> >>
>
>
Re: [DISCUSS] Encoding improvements (follow-up from Parquet "V3" discussion)
Posted by Ed Seidl <et...@live.com>.
Maybe this is putting the cart too far in front of the horse, but I'd be
willing to implement an encoding like this to see if is a better
alternative to PLAIN and DELTA_LENGTH_BYTE_ARRAY as a dictionary
fallback for byte arrays, at least for GPU decoding. We might want to
change the name since it wouldn't be used exclusively for random access
any longer. Maybe LENGTH_BYTE_ARRAY? Or PLAIN_BYTE_ARRAY?
I'll also raise my hand as interested in participating in all 5 of the
tasks outlined, as time permits.
Cheers,
Ed
On 5/28/24 11:05 PM, Micah Kornfield wrote:
> BTW, I did propose a new RANDOM_ACCESS_BYTE_ARRAY encoding (effectively
> Arrow's representation) as part footer improvements [1] to help allow for
> O(1) access to particular column metadata, once a column is identified.
>
> [1] https://github.com/apache/parquet-format/pull/250
>
> On Mon, May 27, 2024 at 11:16 PM Micah Kornfield <em...@gmail.com>
> wrote:
>
>> As a follow-up to the "V3" Discussions [1][2] I wanted to start a thread
>> on improvements to encodings.
>>
>> There are several areas to pursue here:
>> 1. Curating a standard set of benchmarks and criteria for determining if
>> a new encoding is worth adding.
>> 2. Developing new encodings
>> 3. Better implementations to select existing encodings.
>> 4. Better support for encodings with point/indexed lookups.
>> 5. Benchmarking frameworks that allow assessing trade-off of encodings on
>> storage systems with different latency/throughput.
>>
>> Realistically, given my current commitments, I don't think I have
>> bandwidth to help with this track in the near term. If someone else would
>> like to help drive this and make concrete proposals in these areas it would
>> be greatly appreciated.
>>
>> Thanks,
>> Micah
>>
>>
>> [1] https://lists.apache.org/thread/5jyhzkwyrjk9z52g0b49g31ygnz73gxo
>> [2]
>> https://docs.google.com/document/d/19hQLYcU5_r5nJB7GtnjfODLlSDiNS24GXAtKg9b0_ls/edit
>>
Re: [DISCUSS] Encoding improvements (follow-up from Parquet "V3" discussion)
Posted by Micah Kornfield <em...@gmail.com>.
BTW, I did propose a new RANDOM_ACCESS_BYTE_ARRAY encoding (effectively
Arrow's representation) as part footer improvements [1] to help allow for
O(1) access to particular column metadata, once a column is identified.
[1] https://github.com/apache/parquet-format/pull/250
On Mon, May 27, 2024 at 11:16 PM Micah Kornfield <em...@gmail.com>
wrote:
> As a follow-up to the "V3" Discussions [1][2] I wanted to start a thread
> on improvements to encodings.
>
> There are several areas to pursue here:
> 1. Curating a standard set of benchmarks and criteria for determining if
> a new encoding is worth adding.
> 2. Developing new encodings
> 3. Better implementations to select existing encodings.
> 4. Better support for encodings with point/indexed lookups.
> 5. Benchmarking frameworks that allow assessing trade-off of encodings on
> storage systems with different latency/throughput.
>
> Realistically, given my current commitments, I don't think I have
> bandwidth to help with this track in the near term. If someone else would
> like to help drive this and make concrete proposals in these areas it would
> be greatly appreciated.
>
> Thanks,
> Micah
>
>
> [1] https://lists.apache.org/thread/5jyhzkwyrjk9z52g0b49g31ygnz73gxo
> [2]
> https://docs.google.com/document/d/19hQLYcU5_r5nJB7GtnjfODLlSDiNS24GXAtKg9b0_ls/edit
>
Re: [DISCUSS] Encoding improvements (follow-up from Parquet "V3" discussion)
Posted by Micah Kornfield <em...@gmail.com>.
Hi Julien,
Yes I a doc would be good, I didn't mean to officially propose the encoding
here but wanted it kept for posterity. As I said above, I have my hands a
little bit full at the moment on the other tracks and can't really devote
meaningful time here. Hopefully, Gang and others can drive this forward
and I'm happy to try to help with reviews and possibly contribute more when
I get a little bit more bandwidth.
Thanks,
Micah
On Fri, May 31, 2024 at 5:35 PM Julien Le Dem <ju...@apache.org> wrote:
> Micah, would it make sense to start a google doc specifically to discuss:
> - the goals (there could be a few subsets)
> - the candidate encodings
> - the existing/future prototypes to validate candidates.
>
> On Thu, May 30, 2024 at 3:14 AM Steve Loughran <stevel@cloudera.com.invalid
> >
> wrote:
>
> > be good for a benchmark to be targetable at cloud storage; local stores,
> > especially those with SSD, hide a lot of the costs of datalakes
> >
> > On Tue, 28 May 2024 at 07:17, Micah Kornfield <em...@gmail.com>
> > wrote:
> >
> > > As a follow-up to the "V3" Discussions [1][2] I wanted to start a
> thread
> > on
> > > improvements to encodings.
> > >
> > > There are several areas to pursue here:
> > > 1. Curating a standard set of benchmarks and criteria for determining
> > if a
> > > new encoding is worth adding.
> > > 2. Developing new encodings
> > > 3. Better implementations to select existing encodings.
> > > 4. Better support for encodings with point/indexed lookups.
> > > 5. Benchmarking frameworks that allow assessing trade-off of encodings
> > on
> > > storage systems with different latency/throughput.
> > >
> > > Realistically, given my current commitments, I don't think I have
> > bandwidth
> > > to help with this track in the near term. If someone else would like to
> > > help drive this and make concrete proposals in these areas it would be
> > > greatly appreciated.
> > >
> > > Thanks,
> > > Micah
> > >
> > >
> > > [1] https://lists.apache.org/thread/5jyhzkwyrjk9z52g0b49g31ygnz73gxo
> > > [2]
> > >
> > >
> >
> https://docs.google.com/document/d/19hQLYcU5_r5nJB7GtnjfODLlSDiNS24GXAtKg9b0_ls/edit
> > >
> >
>
Re: [DISCUSS] Encoding improvements (follow-up from Parquet "V3" discussion)
Posted by Julien Le Dem <ju...@apache.org>.
Micah, would it make sense to start a google doc specifically to discuss:
- the goals (there could be a few subsets)
- the candidate encodings
- the existing/future prototypes to validate candidates.
On Thu, May 30, 2024 at 3:14 AM Steve Loughran <st...@cloudera.com.invalid>
wrote:
> be good for a benchmark to be targetable at cloud storage; local stores,
> especially those with SSD, hide a lot of the costs of datalakes
>
> On Tue, 28 May 2024 at 07:17, Micah Kornfield <em...@gmail.com>
> wrote:
>
> > As a follow-up to the "V3" Discussions [1][2] I wanted to start a thread
> on
> > improvements to encodings.
> >
> > There are several areas to pursue here:
> > 1. Curating a standard set of benchmarks and criteria for determining
> if a
> > new encoding is worth adding.
> > 2. Developing new encodings
> > 3. Better implementations to select existing encodings.
> > 4. Better support for encodings with point/indexed lookups.
> > 5. Benchmarking frameworks that allow assessing trade-off of encodings
> on
> > storage systems with different latency/throughput.
> >
> > Realistically, given my current commitments, I don't think I have
> bandwidth
> > to help with this track in the near term. If someone else would like to
> > help drive this and make concrete proposals in these areas it would be
> > greatly appreciated.
> >
> > Thanks,
> > Micah
> >
> >
> > [1] https://lists.apache.org/thread/5jyhzkwyrjk9z52g0b49g31ygnz73gxo
> > [2]
> >
> >
> https://docs.google.com/document/d/19hQLYcU5_r5nJB7GtnjfODLlSDiNS24GXAtKg9b0_ls/edit
> >
>
Re: [DISCUSS] Encoding improvements (follow-up from Parquet "V3" discussion)
Posted by Steve Loughran <st...@cloudera.com.INVALID>.
be good for a benchmark to be targetable at cloud storage; local stores,
especially those with SSD, hide a lot of the costs of datalakes
On Tue, 28 May 2024 at 07:17, Micah Kornfield <em...@gmail.com> wrote:
> As a follow-up to the "V3" Discussions [1][2] I wanted to start a thread on
> improvements to encodings.
>
> There are several areas to pursue here:
> 1. Curating a standard set of benchmarks and criteria for determining if a
> new encoding is worth adding.
> 2. Developing new encodings
> 3. Better implementations to select existing encodings.
> 4. Better support for encodings with point/indexed lookups.
> 5. Benchmarking frameworks that allow assessing trade-off of encodings on
> storage systems with different latency/throughput.
>
> Realistically, given my current commitments, I don't think I have bandwidth
> to help with this track in the near term. If someone else would like to
> help drive this and make concrete proposals in these areas it would be
> greatly appreciated.
>
> Thanks,
> Micah
>
>
> [1] https://lists.apache.org/thread/5jyhzkwyrjk9z52g0b49g31ygnz73gxo
> [2]
>
> https://docs.google.com/document/d/19hQLYcU5_r5nJB7GtnjfODLlSDiNS24GXAtKg9b0_ls/edit
>