Corra: Correlation-Aware Column Compression

Column encoding schemes have witnessed a spark of interest lately. This is not surprising -- as data volume increases, being able to keep one's dataset in main memory for fast processing is a coveted desideratum. However, it also seems that single-column encoding schemes have reached a plateau in terms of the compression size they can achieve. We argue that this is because they do not exploit correlations in the data. Consider for instance the column pair (city, zip-code) of the DMV dataset: a city has only a few dozen unique zip codes. Such information, if properly exploited, can significantly reduce the space consumption of the latter column. In this work, we depart from the established, well-trodden path of compressing data using only single-column encoding schemes and introduce correlation-aware encoding schemes. We demonstrate their advantages compared to single-column encoding schemes on the well-known TPC-H's lineitem, LDBC's message, DMV, and Taxi. For example, we obtain a saving rate of 58.3% for lineitem's shipdate, while the dropoff timestamps in Taxi witness a saving rate of 30.6%.