Data reordering for better compression in databases

点击翻译按钮获取中文摘要

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.