[Format] RLE encoding spec incorrect for v2 data pages

[asfimport]

The spec (https://github.com/apache/parquet-format/blob/master/Encodings.md#run-length-encoding--bit-packing-hybrid-rle--3) has this:

rle-bit-packed-hybrid: <length> <encoded-data>
length := length of the <encoded-data> in bytes stored as 4 bytes little endian (unsigned int32)

But the length is actually prepended only in v1 data pages, not in v2 data pages.

Reporter: Antoine Pitrou / @pitrou
Assignee: Xuwei Fu / @mapleFU

_{Note: This issue was originally created as PARQUET-2222. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou:
cc @julienledem @piyushnarang @rdblue @isnotinvain

[asfimport]

Xuwei Fu / @mapleFU:
I don't understand. Isn't length the part of encoding in spec?

And seems that DataPageV2 in parquet-mr is not in-prod?

 

[asfimport]

Antoine Pitrou / @pitrou:

I don't understand. Isn't length the part of encoding in spec?

What do you mean?

And seems that DataPageV2 in parquet-mr is not in-prod?

What is that supposed to mean?

[asfimport]

Xuwei Fu / @mapleFU:
ok, I got it. Previously I found RLE format requires a length here:

`rle-bit-packed-hybrid: <length> <encoded-data>`

`length := length of the <encoded-data> in bytes stored as 4 bytes little endian (unsigned int32)`

`encoded-data := <run>*`

So I thought it already has length in encoded data, but actually, in data page v2's rep-levels and def-levels, length is not included?

[asfimport]

Gang Wu / @wgtmac:
I think the reason is that DataPageHeaderV2 has two fields to store them.

struct DataPageHeaderV2 {
// repetition levels and definition levels are always using RLE (without size in it)

/** length of the definition levels */
5: required i32 definition_levels_byte_length;
/** length of the repetition levels */
6: required i32 repetition_levels_byte_length;

[asfimport]

Gang Wu / @wgtmac:
The implementations are consistent between parquet-cpp and parquet-mr. Please refer to https://github.com/apache/parquet-mr/blob/master/parquet-column/src/main/java/org/apache/parquet/column/impl/ColumnWriterV2.java#L41

So I think the only issue is the wording of the specs does not cover RLE-encoded levels in the data page v2.

@pitrou Please correct me if I am wrong.

[asfimport]

Antoine Pitrou / @pitrou:
Yes, this is why I've filed this under parquet-format.

[asfimport]

Gabor Szadovszky / @gszadovszky:
@pitrou, @wgtmac,

It seems my review was not deep enough. Sorry for that. So, parquet-mr does not use RLE encoding for boolean values in case of V1 but only bit packing:

• V1 -> ... -> Bit packing (encoding written to page header: PLAIN)

• V2 -> ... -> RLE (encoding written to page header: RLE)

  @pitrou, could you please confirm that is the same for parquet cpp?

  So the table we added in this PR about prepending the length is misleading. Also, the link in the PLAIN encoding for boolean is dead and misleading. It should point to BIT_PACKED. In the definition of BIT_PACKED it is also wrongly stated that it is valid only for RL/DL. I think, the deprecation is valid since the "BIT_PACKED" encoding should not be written to anywhere but the actual encoding is used under PLAIN for boolean.
  Would you guys like to work on this? We probably want to add this to the current format release.

[asfimport]

Gang Wu / @wgtmac:
Thanks for bringing this up @gszadovszky 

I will look into it again. Also cc @mapleFU  

[asfimport]

Xuwei Fu / @mapleFU:
I think in cpp, in 12.0.0, even if it's Format V1, writer can only write RLE for RL/DL.

[asfimport]

Gang Wu / @wgtmac:
@mapleFU Do you have any idea how does the rust or go implementation behave?

[asfimport]

Gabor Szadovszky / @gszadovszky:
@mapleFU, -This is specifically about BOOLEAN values (data pages), not rl/dl. (In parquet-mr we write rl/dl and dictionary indices using RLE for both v1 and v2 settings.)-
Sorry, misread your comment. So parquet-cpp does not write BOOLEAN data pages in any case using RLE?

[asfimport]

Xuwei Fu / @mapleFU:
@gszadovszky Hi Gabor maybe I'm misleading.

1. RLE for Boolean is just implemented a few month ago by me. I guess Legacy writer cannot write use RLE.
2. For RL/DL, in parquet-cpp, only RLE can be used.

In arrow-rs, I found the code below

/// RLE/Bit-Packing hybrid encoding for values.
/// Currently is used only for data pages v2 and supports boolean types.
pub struct RleValueEncoder<T: DataType> {
    // Buffer with raw values that we collect,
    // when flushing buffer they are encoded using RLE encoder
    encoder: Option<RleEncoder>,
    _phantom: PhantomData<T>,
}

I guess it only supports Page V2 and format V2.  @tustvold  am I right?

[asfimport]

Raphael Taylor-Davies / @tustvold:
Within arrow-rs levels data is always written using RLE, only prepending the length for v1 data pages. We also support reading bit backed level data but we never write it.

We additionally support reading/writing boolean data using RLE, this is the default for writer version 2, but theoretically a v1 writer could opt-in to this. This will always prepend the length when flushing a data page.

Finally for dictionary indices we do not prepend the length

Not sure if that answers your question

[asfimport]

Xuwei Fu / @mapleFU:
Yes this answers my question. I think arrow parquet c++ is same on this. In cpp user can write the rle but I just introduce it few month later, so maybe user haven't and should not use it in v1 format.

As for RL/DL, I guess RLE is used