[IMPALA-6658] Parquet RLE encoding can waste space with small repeated runs

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Fixed
• Fix Version/s: Impala 3.1.0
• Component/s: Backend
• Labels: parquet ramp-up
• Epic Color: ghx-label-4
• Assignee: Andrew Sherman
• Reporter: Csaba Ringhofer
• Created: 14/Mar/18 14:23
• Updated: 12/Mar/19 00:29
• Resolved: 11/Dec/18 21:42

Description

Currently RleEncoder creates repeated runs from 8 repeated values, which can be less space efficient than bit-packed if bit width is 1 or 2. In the worst case, the whole data page can be ~2X larger if bit width is 1, and ~1.25X larger if bit is 2 compared to bit-packing.

A comment in rle_encoding.h writes different numbers, but it probably does not calculate with the overhead of splitting long runs into smaller ones (every run adds +1 byte for its length): https://github.com/apache/impala/blob/8079cd9d2a87051f81a41910b74fab15e35f36ea/be/src/util/rle-encoding.h#L62

Note that if the data page is compressed, this size difference probably disappears, but the larger uncompressed buffer size can still affect performance.

Parquet RLE encoding is described here: 
https://github.com/apache/parquet-format/blob/master/Encodings.md#run-length-encoding-bit-packing-hybrid-rle-3