[C++][Parquet] Support RLE Encoder for Boolean type

[mapleFU]

Describe the enhancement requested

Currently, in our spec, boolean type in data page can use RLE to encode itself. And parquet-mr, parquet-go and other versions all supports it.

Thanks #14147 , we already have a Rle Boolean Decoder. So for testing, just testing it local is ok.

I'd like to submit a implemention and testing this weekend.

Component(s)

C++, Parquet

[mapleFU]

Hey, I found an problem when trying to implement RLE for boolean.

• Our Rle implement is in src/arrow/util/rle_encoding.h, the RleEncoder requires pre-compute the bytes it needs.
• Current encoding uses LevelEncoder::Init and LevelEncoder::Encode or DictEncoderImpl::WriteIndices to write all data at once

So, should I:

• Change rle_encoding to use a grow-able buffer?
• Buffer all input in RleBooleanEncoder, and write it all-once?
• Using other workaround?

Any idea here? (I can write a Buffer all input version first)

[rok]

• Buffer all input in RleBooleanEncoder, and write it all-once?

That would mean using upper bound buffer size for boolean and slicing off the unnecessary part after encoding? Sounds like a good idea. Is this what other implementations do?

[mapleFU]

That would mean using upper bound buffer size for boolean and slicing off the unnecessary part after encoding? Sounds like a good idea. Is this what other implementations do?

Maybe we're not able to guess a "upper bound buffer" on Encoder, I'd like to buffer values in PlainEncoder<BooleanType>, and when flushValues, acquire the buffer and put all of them into RleEncoder.

The parquet-mr uses CapacityByteArrayOutputStream in RunLengthBitPackingHybridEncoder, which is able to grow the buffer size.

I didn't find other implementions, seems that maybe people likes PLAIN Encoding? In Rust, parquet2 is not hybrid, seems it just implement bit-packing when encoding. Arrow-rs just uses a BitWriter, which is able to resize.

@rok

[mapleFU]

@pitrou @sfc-gh-nthimmegowda mind take a look? All change is ok for me. Maybe I can use PlainEncoder to cache all values and write to RleEncoder onces first, and later another patch to change to RleEncoder with resizable-buffer?

[pitrou]

@mapleFU Take a look at what? Did you post a PR?

[mapleFU]

Take a look at what? Did you post a PR?

@pitrou Sorry, I'd like to post a PR but meet a problem. I want to make clear it before start writing the code. It's mentioned at #15107 (comment) . And I wonder should I:

1. Cache all input in a PlainEncoder, and put them into RleEncoder once
2. or make RleEncoder use a resizable-buffer
3. using other work-arounds

If I make something wrong, please tell me

[pitrou]

@mapleFU I'm sorry, but I'm afraid you'll need to do more research yourself and decide a reasonable solution.

That said, buffering all values before encoding doesn't sound very optimal...

[pitrou]

Also, see https://issues.apache.org/jira/browse/PARQUET-2222

[mapleFU]

@pitrou I cache all values in bitmap firstly. Can take a look at #34526