[C++][Parquet] Refactor RLE decoding by extract a RLE parser

[pitrou]

Describe the enhancement requested

The Parquet Bit-packed RLE encoding is used in two performance-critical situations:

1. definition and repetition levels, which are present on many or even most columns (when writing nullable Arrow data, for example, definition levels are always generated even if there are no nulls)
2. dictionary indices for Dictionary encoding

Both these areas lack performance currently, and it has been difficult to optimize.
The RLE decoder is currently spread over two facilities: the RleDecoder does the actual decoding to a linear array of integers, while the BitReader hosts some low-level reading routines.

This issue is to refactor the RleDecoder into a parser+decoder. The parser would be a pure event-driven facility to decompose a RLE stream into its individual tokens (. The parser does not need to use the BitReader class, it can just reimplement the corresponding operations.

(an inspiration for event-driven parser APIs can be found in RapidJSON, though the RLE parser would be much simpler as there are only two different kinds of tokens in the RLE stream: literal runs and repeated runs)

This refactoring will probably not bring any performance benefits in itself (though who knows?). However, once we have a RLE parser, we can then avoid the decoder in some situations.

For example, a very common situation is OPTIONAL columns in Parquet, where definition levels can have only two values: 0 and 1. Currently, we decode such levels into 16-bit integers and then re-encode them into a bitmap. This is wasteful and pointless, while we could generate the bitmap directly from the RLE stream.

Component(s)

C++, Parquet

[pitrou]

cc @AntoinePrv

[AntoinePrv]

I'm working on this.

This issue is to refactor the RleDecoder into a parser+decoder. The parser would be a pure event-driven facility to decompose a RLE stream into its individual tokens.

So while this is not so hard to (re)implement with the existing code, the main difficulty lies with the inversion of the control over the decoding.

Today, callers call RleDecoder::GetBatch (and the likes) to pull n_values regardless of how they are encoded.
This logic goes up the inheritance tree up to the TypedDecoder.

With an event driven API, callers would pull either type of run, but would need some bookkeeping to manage cases where the n_values they are asked to pull will fall in the middle of a run. This logic need to be repeated for each caller.

However, once we have a RLE parser, we can then avoid the decoder in some situations.

Since a large part of the work will go into plugging the events into the callers, maybe we should take this more into considerations when designing this API.

[pitrou]

(sorry for the delay, I was on vacation!)

With an event driven API, callers would pull either type of run, but would need some bookkeeping to manage cases where the n_values they are asked to pull will fall in the middle of a run. This logic need to be repeated for each caller.

That, or the event driven API itself has a top-level Parse method that takes a n_values, such that the parser does the bookkeeping by itself.

Something like:

struct RepeatedRun {
  uint32_t value;
  int32_t num_values; 
};

struct LiteralRun {
  const uint8_t* data;
  int32_t num_values;
};

class RleBitPackedParser {
 public:
   // Snip constructor, etc.

   template <typename Handler>
   void ParseValues(int n_values, Handler&& handler);
};

// API expected of a handler
struct Handler {
  void OnRepeatedRun(RepeatedRun run);
  void OnLiteralRun(LiteralRun run);
  void OnEnd();
};

[pitrou]

Issue resolved by pull request 47294
#47294