Data reordering for better compression in databases

数据重新排序以更好地压缩数据库

• 批准号: 261437-2012
• 负责人: Lemire, Daniel
• 金额: $ 2.04万
• 依托单位: TÉLUQ
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=547763
• 关键词: Data; reordering; better; compression; 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.

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