Data reordering for better compression in databases

通过使用正确的压缩技术，我们可以将数据库查询速度提高几个数量级。毫不奇怪，数据仓库供应商在压缩比上展开了竞争。唉，我们经常不得不在更高的压缩和更高的速度之间做出选择。通过使用轻量级压缩技术，我们既减少了存储空间，又提高了速度。为了最大化压缩，我们按列组织数据(至少在磁盘页内)，并对表进行排序。我们在旅行商问题(TSP)的启发下，用行重排序启发式方法超过了词典编排排序(50%或更多)。实际上，我们在表的各行中寻找一次巡视，从而使行之间的距离最小化。我们使TSP适应我们的压缩技术：例如，游程编码对应于汉明距离。许多TSP启发式算法可扩展到数十亿个元素。如果我们专门针对我们的环境(数据库压缩)对它们进行调整，则它们的可伸缩性更强。此外，我们希望列的可压缩性能够反映预期的工作负载。例如，我们可能希望几个列的压缩效果都很好，而不是以其他列为代价。这个问题与平衡格雷码密切相关。此外，虽然将表视为行列表是很自然的，但如果图结构的存储足够便宜，我们也可以在图(如生成树)中组织行。我们寻求的不是最好的旅行，而是最好的生成树。然后，行重新排序问题变成了图被约束到列表的特殊情况。使用这种图方法，初步结果表明，我们优于最好的TSP启发式算法，在解压缩时只需要很小的开销。我们推测，这可能会为面向列的数据库提供一种更好的存储策略。我们的兴趣不仅限于关系数据库的压缩：它还扩展到面向文档的数据库。我们推测，在温和的假设下，它们在存储方面可能与关系数据库一样高效。

By using the right compression techniques, we can accelerate database queries by orders of magnitude. Unsurprisingly, data warehouse vendors compete over compression ratios. Alas, we often have to choose between more compression or more speed. By using lightweight compression techniques, we get both: reduced storage and improved speed. To maximize compression, we organize the data in columns (at least within disk pages) and we sort tables. We surpass the lexicographical sort (by 50% or more) with row-reordering heuristics inspired by the Traveling Salesman Problem (TSP). Effectively, we seek a tour through the rows of a table which minimizes the distances between rows. We adapt the TSP to our compression technique: e.g., run-length encoding corresponds to the Hamming distance. Many TSP heuristics scale to billions of elements. They are even more scalable if we adapt them specifically for our context (database compression). Moreover, we want the compressibility of the columns to reflect the expected workload. For example, perhaps we want several columns to have uniformly excellent compression, at the expense of other columns. This problem is closely related to balanced Gray codes. Moreover, while it is natural to view a table as a list of rows, we can also organize the rows in a graph (such as a spanning tree) if the storage of the graph structure is sufficiently inexpensive. Instead of seeking the best tour, we seek the best spanning tree. The row-reordering problem then becomes a special case where the graph is constrained to a list. Using such a graph approach, preliminary results show that we outclass the best TSP heuristics with only a small overhead at decompression time. We conjecture that this may provide a superior storage strategy for column-oriented databases. Our interest is not limited to the compression of relational databases: it extends to document-oriented databases. We conjecture that they could be just as efficient with respect to storage as relational databases, under mild assumptions.