####

序号：

文献背景：SIGMOD2020（微软和加州大学伯克利合作的论文）

研究方法：数据分区（data partition）

存在问题：现如今企业收集的数据的规模正在以前所未有的速度不断增长，因此如何在大规模的数据集上进行查询变得至关重要。目前大部分商用数据库在实际中使用了分块（block-based）和压缩的办法来加速查询，然而将每一条数据划分在哪一个数据分区仍是一个开放性问题。一次查询中访问的数据分区数量（the number of blocks accessed by a query）是一个直接关联到I/O开销的指标，从而会对查询的性能产生影响。而现有的技术无法优化这一指标，因此会导致查询的性能不够好。

解决方案：提出了qd-tree(query-data routing tree)，以及基于贪心（greedy）和深度强化学习（deep reinforcement learning）的qd-tree构造方法。qd-tree产生的分区具有两个属性：（1）语义描述（semantic description），精确的描述了每个分区的属性。（2）完整性（completeness），所有满足当前分区对应的语义描述限制的数据都位于该分区中。因而减少了查询需要访问的分区数量，相应地降低了I/O开销，从而提高了查询的性能。

创新点：现有的数据库系统在分区内部的数据组织和压缩方面做了很多工作，但是忽略了查询中的数据分区访问数量这个指标，而本文提出的qd-tree则对这个指标进行了优化，减少了一次查询过程中的数据分区访问数量。

下一步/不足之处：在进行数据分区的时候，可以考虑对分区边界的数据进行数据冗余，即同时存放在临近的几个分区中，从而在处理一些需要访问边界数据的查询时，能够减少不必要的数据分区访问数量。

数据集：

  • TPC-H

2个真实数据集：

  • ErrorLog-Int
  • ErrorLog-Ext

代码和数据集未开源