Parquet/parquet-mr — pull request #58 by isnotinvain (2013-05-31 22:23:55+00:00)
Title: Adds rle / bitpacking hybrid encoding

1) this implementation uses the wrong order for bit packing, and will have to be updated once https://github.com/Parquet/parquet-mr/pull/57 is merged.

2) this implementation uses the same logic / optimizations as the impala implementation, namely:
* RLE runs don't begin for values that repeat < 8 times -- I think we can do beter here, see below
* Bit-packed runs can only store 504 values max, because only 1 bytes is allocated for the bit-packed-header (I don't see any good way around this)

I think that, depending on the bitwidth used and how frequent we expect repeats to be, the rle threshold can be tuned. For example, with bitwidth 1 it doen't make sense to start a RLE run until there have been 16 repeats. It gets more complicated at bitwidth 2 to about 12, but at some point it becomes better to always rle encode, even for 2 repeats (for example, bit width 32)

I started to explore this tuning in another branch but it's not ready yet.