Compression Techniques in Columnar Storage

This page describes the investigations into improving the compression techniques used in columnar storage, for instance, with RCFile.

Hadoop already provides BZip2 and Gzip codecs which can be used for columnar compression in hive/hcatalog.

There are other compressors available which are better at resource usage (snappy,...), or provide better compression (paq,...) but we should be able to exploit certain aspects of the usage scenario here to provide a compression which is both better and faster than the options available.

• the fact that the data is of the same type
• in some cases, that data may be ordered
• block compression is always possible
• record order may not matter in most situations

Initially, I am going to look into integer compression but the learnings here should translate to other types as well.

Here is the compression metrics with some simulated data. The number of bits per symbol, where the symbol is a 32-bit integer is shown here. In general, bzip2 does well in terms of compression efficiency, but still has a higher bits-per-symbol than 1st order entropy so we could exploit this to produce a better compressor using a 1-level ppm compression.

Note that the first two are not actually compressors but entropy calculations for the datasets.

To be done: Analysis of cpu/memory

Issues to be sorted out:

The SerDe/Compression codecs split - where serdes convert from cells to byte arrays and compression codecs compress these byte arrays later, means that we need to (a) either deserialize before compression or (b) allow bit boundaries for cell values.