SIGMOD 2020 | 为数据库构建基于存储布局的多维学习索引
论文地址：https://www.aminer.cn/pub/5de8d5463a55ac9c4229173a
在多维索引表格（multi-dimensional table）上进行扫描和筛选是现代分析型数据库引擎的关键技术。为了对这些操作进行优化，数据库常建立起聚类的索引结构（indexes），如R-Trees，Z-ordering等，然而这些索引结构在不同的数据集以及查询集合（query workload）下很难进行统一优化。在本篇论文中，作者提出了名为Flood的多维学习索引结构。通过同时优化索引结构以及存储布局，这种结构自动地调整自身以适应具体数据集和查询集合。该工作用来为端到端学习型数据库系统构建索引模块。
论文背景
为了解决上述缺点，本文提出了名为Flood的基于内存的学习多维索引。该索引方案的重点在于自动地同时优化数据存储布局以及索引的结构，以此来获得优于其他所有多维索引的索引速度。Flood框架有以下两个重点idea：
1. 使用一个下采样的查询集合，即一小部分查询样例构成的查询集合样本，以此来学习不同维度属性在查询过程中的使用频率。基于该信息，Flood框架自动地调节数据存储布局，以此优化索引性能。
2. 使用一个累计分布函数CDF（Calculative Distribution Function）模型来将多维上可能的倾斜数据映射到一个均匀空间中。这个平滑（Flatten）过程使得每一个存储的存储单元储存的数据量基本一致。以此更快地进行索引。
Flood框架的主要贡献有三：
1. 提出了第一个学习型多维索引，Flood框架。Flood从一个筛选断言集合，即一个下采样的查询集合中学习查询集合的分布函数，以此调节数据存储布局。
2. 使用三个真实数据集评估了多个不同的多维索引结构，实验显示Flood框架大大优于其他的多维索引结构。
3. 实验显示出Flood框架在不同的Filter Predicates上都实现了搜索加速，其索引结构的建立速度与其他多维索引的建立速度相当。
多维索引查询的难点在于同时对Y和Z两个属性进行筛选，对其中某一个维度进行排序的二分搜索无法顺利完成该任务。
数据布局
如果把整个多维空间看作一个欧几里得空间的话，不同于单维数据，多维数据不可以基于一个维度，或者属性进行排序，这导致很多单维上可以使用的索引方法在多维索引上并不适用。但是如果将整个空间分成一个个小的格子，在单独一个格子内使用统一维度进行排序，则在访问该格子内的数据中就可以通过使用单维索引技术加速索引。
模型基本操作
1. 映射查找存储块（Projection）：通过查询中的筛选条件得到需要遍历的数据网格，并且将索引范围约束在这些网格当中。
2. 凝练查找范围（Refinement）：对按照某一维度进行排序的网格数据进行进一步筛选，根据查找筛选条件对排序维度的限制进一步缩小检索的范围。
3. 进行搜索。
网格优化
网格分割需要决定每一个维度所应该分割的子空间个数。Flood框架可以通过学习选择合适的网格个数以及决定哪一个维度作为排序维度，即在网格内对数据进行排序的维度。
数据学习优化索引结构
1. 数据平滑化
2. 快速查找范围凝练（使用机器学习方法）
在凝练搜索范围的过程中，通过使用学习索引模型，RMI（Recursive Model Index），这一个多层线性回归模型的索引结构，加速范围索引的速度。论文中称之为piecewise linear model。
本文在Sales，OSM，Perform三个真实数据上进行了试验。
赞 (0)