DSE精选文章|深度强化学习的动态索引构建

本文使用两台具有相同硬件配置的服务器（Xeon CPU 32 核、64GB DRAM、2MB L2 和 20MB L3 以及 NVIDIA GTX TITANX）。一台服务器专用于控制器的训练过程，另一台用于索引物化和性能评估。本文使用四个数据集进行测试：合成统一数据集（uniform64）和三个真实数据集（amzn，facebook，osmc）。所有数据集都有2亿个键值对。

为了比较，本文使用了 -Tree、SkipList、ART、FAST、Bw-Tree、Learned Index（RMI）和PGM作为基线。所有索引都是内存索引并且不涉及磁盘I/O。

图2. 仅查找工作负载的性能

图2展示了仅查找工作负载下的不同方法在不同数据集上的性能，y轴表示查询的平均处理成本（以纳秒为单位）。在本实验中将NIS与其他基线进行比较，按照数据分布均匀生成1000万个单键查找查询，即对高密度数据范围有更多的查询。从图2中观察到，uniform64是一个具有均匀分布的合成数据集，更容易用神经模型进行模拟。因此，RMI在uniform64上表现最好，其次是NIS。原因是NIS仍然保持传统索引的结构，产生额外的开销，而RMI通过采用新的索引设计更加灵活。osmc、amzn和facebook是三个不同的真实数据集。由于分布复杂，RMI很难对数据进行精确建模，尤其是对于最复杂的数据集osmc64。所以RMI的性能可能不如一些基线索引。相反，NIS能够学习给定数据集和工作负载分布的最佳索引架构。

图3. 混合工作负载的实验结果

图3展示了混合工作负载的实验结果。在这个实验中，本文关注两个数据集，osmc和uniform，并生成四个不同的工作负载。W1表示在之前的实验中使用的工作负载（1000万个查找查询）。W2包含100万个范围查询，选择性为0.1%。W3混合了500万次查找和500万次插入。W4混合了200万次查找、200万次插入和100万次范围查询（选择性=0.1%）。本文以纳秒为单位显示平均查询处理成本。RMI仅在W1和W2中显示，因为当前的开源RMI实现不支持更新。可以观察到，对于范围工作负载和混合工作负载，NIS在统一数据集和真实数据集上表现出优于其他指标的性能。

图4. 鲁棒性和增量学习的实验结果

图4展示了使用增量学习技术定期更新索引结构的实验结果。这个实验评估了索引在不同分布场景下的鲁棒性。有四种情况：(a)数据集和工作负载分布均保持不变；(b)数据集分布发生变化，而工作量分布保持不变；(c)数据集和工作量分布的变化；(d)数据集分布保持不变，而工作负载分布发生变化。图4显示了场景 (a)到 (d)的结果。可以观察到，当分布发生显着变化时，索引表现也会受到影响。与数据分布相比，工作负载分布的变化对性能的影响更为严重，而增量学习可以部分解决问题。

图5. 增量学习在工作负载发生巨大变化时的表现

图5展示了增量学习在工作负载发生巨大变化时的表现。本文定义一个数据集，从osmc64和9个不同工作负载中随机采样的5000万个键，每个工作负载包含1000万次查找和1000万次插入，并遵循具有不同中心的log-正态分布。由于大量的插入，数据大小急剧增长，分布也是极具变化。NIS每10秒调用一次增量学习来更新索引，可以看到新的索引结构可以提供更好的性能，直到下一个工作负载开始。