[C++][Parquet] RleDecoder::Get fails to return false on end for some bit widths

[lesterfan]

Describe the bug, including details regarding any error messages, version, and platform.

On the current main branch, the specified behavior of arrow::util::RleDecoder::Get is to return false if there are no more elements. However, this behavior doesn't work for some bit widths. This failing test case illustrates this: lesterfan@2722055.

I added some logging to the above test case for the original/decoded vector values and lengths below. The RleDecoder seems to be reading some additional values at the end of the buffer for this particular case with bit_width = 17.

Note: Google Test filter = *Rle.DecoderGetBitWidthRoundTrip*
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from Rle
[ RUN      ] Rle.DecoderGetBitWidthRoundTrip
values.size(): 100
values: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
decoded_values.size(): 104
decoded_values: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 15794567, 15794567, 15794567, 15794567, 
/Users/lester/work/arrow/cpp/src/arrow/util/rle_encoding_test.cc:383: Failure
Expected equality of these values:
  values
    Which is: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... }
  decoded_values
    Which is: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... }

[  FAILED  ] Rle.DecoderGetBitWidthRoundTrip (0 ms)
[----------] 1 test from Rle (0 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test suite ran. (0 ms total)
[  PASSED  ] 0 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] Rle.DecoderGetBitWidthRoundTrip

Component(s)

Parquet

[mapleFU]

I haven't checkout this carefully yet, I'll take a round tomorrow

1. Does this problem from real parquet file?
2. Would you mind submit a fix?

[lesterfan]

Thank you for the help!

1. I haven't run into this issue from reading a real parquet file yet; I ran into it when working on GH-32339: [C++][Python][Parquet] Implement direct reads of Parquet RLE encoded data into Arrow REE #46103.
2. I'm happy to take a deeper look in the code and try to find a fix when I'm free! Though it may be more efficient if someone with more context looks as well as this part of the codebase is quite scary 😅

[lesterfan]

Looking into this some more, one strange thing is that the attached simple test case (with bit_width = 17 fails on my M1 Macbook Pro but passes on my Intel i9 Windows laptop. I'm able to repro this on both platforms with the following test modification which is a bit more complicated: lesterfan@42931e4.

[hadrian-reppas]

Since the encoding only supports literal runs with lengths that are a multiple of 8, the RleEncoder sometimes has to pad the last literal run with zeros. This means that the number of encoded values can't be determined from just looking at the run-length encoded data since the encoding does not differentiate between real values and padding values. So calling RleDecoder::Get until it returns false might result in extra zeros from the padding.

The solution is to separately keep track of the number of values and only call Get that many times.

[mapleFU]

The solution is to separately keep track of the number of values and only call Get that many times.

Actually Parquet Page RecordReader would track the num of values🤔

[lesterfan]

This makes sense; thank you! So in summary, the way that the RleEncoder/RleDecoder are implemented is that literal runs will always be padded to the nearest multiple of 8 to ensure byte alignment. From the decoder's perspective, there's no way to distinguish between a "real" value and one of these padded values. Therefore, it's up to the caller of the RleEncoder/RleDecoder to keep track of how many "real" values they want. In practice, this is done by the Parquet page RecordReader as mentioned by @mapleFU, but in my test I was bypassing this.

Given this, I'm going to close the issue. I think the following docstring could be more clear here, but this sounds largely like a user error from my end:

  /// Gets the next value.  Returns false if there are no more.
  template <typename T>
  bool Get(T* val);

[kou]

We'll improve docstring.