An Experimental Evaluation of Index Selection Algorithms

本文为论文 Magic mirror in my hand, which is the best in the land?An Experimental Evaluation of Index Selection Algorithms 的阅读笔记。

1 引言

🟠 索引对于高效处理数据库工作负载来说很重要，针对索引选择提出的方案有很多，主要的难点是：

• 解空间是巨大的：随索引数量、列、类型增加
• 索引间相互作用
• 很难在部署运行前量化索引对工作负载的影响

🟡 本文描述和分析了 8 种基于不同概念的索引选择算法，并沿着不同的维度进行比较，如解决方案质量、运行时长、多列支持、解决方案粒度和复杂性。

🟢 虚拟索引（hypothetical indexes）

为了避免执行查询、创建索引，一些数据库系统支持虚拟索引，通过它来估计成本。

2 索引选择算法

索引选择算法的里程碑时间轴如下：

2.1 Drop

这种方法依次删除候选索引，直到不能进一步降低成本为止。成本是由数据的特征决定的，而不是由查询优化器决定的。不支持多列索引的选择

2.2 AutoAdmin

该迭代算法通过在每次迭代中增加索引宽度来识别多列索引。首先从每个查询 $j=1,…Q$ 确定候选索引 $S_j$ ，再将所有查询的候选并集作为第二步的输入，确定最佳索引配置时考虑所有查询。

2.3 (Anytime) DTA

首先确定每个查询的候选索引，然后根据原始贪婪枚举确定整个工作负载的索引配置。

2.4 DB2Advis

① 确定候选索引：对每个查询 j ，在列上创建假设索引。然后，向优化器询问查询 j 的最佳计划，在结果计划中使用的假设索引被添加到索引候选集。

② I 中的所有候选索引都按照它们的逐空间效益比降序排序。下面，如果索引对w1的比值更高，则组合索引对w1和w2，直到达到存储预算。

③ 将先前计算的解决方案集与不属于的索引集交换，看成本是否降低。

2.5 Relaxation

① 为每个查询获取最佳索引配置。

② 整个工作负载的最优索引配置定义为所有查询的最优索引集的并集。

③ 反复转换该配置，以降低其存储消耗，同时保持配置的收益尽可能高。

2.6 LP-based Approaches (CoPhy)

把索引选择视为整数LP问题，通过限制解空间来降低LP公式的复杂性。

2.7 Dexter

该算法建立在假设索引的基础上，分为两个阶段。首先，从计划缓存中收集已处理的查询及其运行时信息。具有相同模板但不同参数值的查询被分组。

第二阶段包括多个子步骤。(i)收集的查询的初始成本(当前索引配置的)由EXPLAIN命令确定。(ii)为所有尚未建立索引的潜在单列和多列索引创建假想索引。(iii)同样，从查询优化器检索成本估计和查询计划。步骤(ii)中创建的假设索引是这些查询计划的一部分，成为相应查询的候选索引。(iv)对于所有查询，与步骤(i)中获得的成本相比，选择成本节省最显著的索引候选。

仅限于两列索引。

2.8 Extend

以上八种比较指标选择算法的主要特点：

Machine Learning-based Approaches

尽管将机器学习应用于指数选择的概念是有希望的，但我们没有将上述方法包括在本次评估中，因为目前它们仍然是有限的，不能应用于用于评估的基准。

3 METHODOLOGY

3.1 Workloads

为了进行比较，我们使用了三种不同规模和特征的基准工作负载，以调查工作负载对算法解决方案质量和运行时间的潜在影响。以下是TPC-H[37]、TPC-DS[32]和连接顺序基准[28]的索引选择的相关指标。

这些指标展示了基准测试的不同规模。TPC-H基准相对较小，可用于快速评估，而TPC-DS基准代表更现实的场景，在每个维度上都更丰富。尽管JOB的工作负载包含最多的查询，但潜在(多列)索引的数量相对较低。

3.2 Determining Query Cost

通过物理地创建/删除索引和执行查询来获得查询成本是可能的，但将花费大量时间，并在很大程度上限制可行的算法设置，特别是候选索引的数量。因此，我们使用假设的索引来估计成本。

3.3 Constraints and Optimization Goal

🟠 优化目标：索引的存储消耗、估计的工作负载成本。

🟡 索引选择限制：算法在限制所选索引数量上的方式不同。对于所有工作负载和算法，我们报告不同存储消耗的工作负载成本。

🔵 运行时：最初只有DTA支持限制选择过程的运行时间。一般来说，可以通过限制所调查的候选索引来间接控制运行时，例如，索引宽度或简单的枚举组合。

4 EVALUATION

4.1 TPC-H

• 图3(a)描述了预算从0到10 GB的确定解决方案的性能，每个标记指示一个索引组合。

• 大多数算法都没有充分利用10GB的最大预算，因为无法找到进一步降低工作负载成本的索引。例如，Extend只使用 6 G B。

• 使用 最大索引数作为停止标准的算法 与 基于预算的算法 之间存在结构性差异。

• DB2Advis的运行时间一直很低，但仍能找到可接受的解决方案。低运行时是由它的操作方式造成的：大多数其他算法生成许多组合，并使用假设优化调用检查它们的影响，而DB2Advis只发出固定数量的2Q个代价请求。

• Dexter的运行时间是恒定的，因为它不依赖于预算，而是依赖于查询的数量和复杂性。虽然它的解决方案质量接近于最佳，但它不能产生细粒度的解决方案，并且只能为所有评估的预算确定两个解决方案。

• 图4(a)和4(b)显示了每个算法的最佳索引组合所实现的成本，每个查询不消耗超过5 GB的存储空间
• 除了Dexter和Drop，大多数算法都能在索引适用的情况下识别出重要的查询索引
• DTA和Extend对所有显示的查询实现了最低的成本
• relax仅对查询9、12和21执行得稍差

4.2 TPC-DS

• 对于TPC-H实验，Drop和AutoAdmin为相对较大的预算找到了第一个索引，大约2 GB。对于TPC-DS，它们更早地确定了有益的解决方案，因为在TPC-DS数据集中没有单一的主导表。
• 对于2gb及以上的预算，差异开始变得明显，extend和DTA领先并生成最佳解决方案。

4.3 Join Order Benchmark

• 对于TPC-H和TPC-DS, DTA和Extend为大多数检查的预算找到具有最低工作负载成本的解决方案。中等规模的预算(从2到3.5 GB)在这个实验中没有得到很好的处理，因为缺少细粒度的解决方案。
• Drop识别了许多小型索引，这些索引为中等规模的预算显著降低了工作负载成本，而它完全缺乏类似于AutoAdmin的小型预算解决方案。
• CoPhy, DB2Advis, DTA, Extend为小预算找到最佳解决方案。然而，对于较大的预算，CoPhy缺乏多列索引、每个查询只能有两个索引。
• 图3(f)显示了与TPC-DS算法运行时比较的相似结果。AutoAdmin的运行时间增加了一半，Drop几乎减半，而Extend的运行时间略有减少。

4.4 Cost Breakdown and Cost Requests

• 基于what-if的索引选择算法的大部分运行时通常不是花在算法逻辑上，而是花在对what-if优化器的成本估计调用上。
• 对于所有算法，大部分运行时都花费在成本请求(假设优化调用)上，Drop是唯一的例外。
• Drop和Relaxation在评估配置的数量上存在差异，但产生的成本请求数量最多。它们是最慢的两种方法，与所有其他方法相比，它们遵循相同的一般概念:它们从一个广泛的配置开始，然后减少它，直到它符合给定的预算。

4.5 Parameter Influence

• Index Width：在我们的评估中，每个索引的列数是多少，每个索引的列数对PostgreSQL上的工作负载没有太大的影响。
• DB2Advis - Try Variations：可测量影响通常很小。根据我们的实验，即使在核心算法运行时间为1、变化时间为30秒的情况下，变化也能使工作负载成本提高约1%。
• AutoAdmin - Naive Enumerations：对该方法的求解质量影响很小，但是对运行时影响很大。

5 LEARNINGS

5.1 General Insights

• 根据用户需求选择算法。在运行时、解决方案质量、解决方案粒度和多列索引支持方面的差异是显著的。
• 基于查询的方法(DB2Advis、Dexter)，一次评估所有可能索引的好处；基于索引组合的方法(Extend、AutoAdmin、Drop、CoPhy、DTA)，它评估相对较小的索引集的好处。通常，后者考虑索引交互的程度更高，而基于查询的方法要快几个数量级。
• 假设调用或成本请求的成本不是固定的，它们取决于查询和评估的索引组合(参见第6.5节)。
• 按每个空间的效益而不是纯粹按效益排序索引候选项目是有益的，特别是中等预算。对于事务性工作负载，这种优势可能会消失。

5.2 Drop

• 重复的功能导致大量的成本请求，同时显示出最高的缓存率。
• 支持多列索引的扩展将导致需要某种预选的候选索引数量不可行。

5.3 AutoAdmin

• 单纯枚举选取的指标个数对求解质量影响不大，但对运行时的影响巨大。
• 通过忽略索引的大小，多列索引只比单列索引收益略高，但内存消耗明显更高。

5.4 DB2Advis

• 适用于高预算，同时运行时间较低。在这种情况下，索引组合会针对每个查询进行优化。
• 对于较宽的指标，运行时间增加，而解决方案质量不是最好的。
• 可能会错过局部劣等但全局优越的索引。

5.5 Relaxation

• 大的候选集及其变换规则导致评估的配置数量巨大，从而可以最好地考虑索引交互。
• 对于大预算，在评价基准中表现最好，但导致实际预算的运行时间较长。

5.6 CoPhy

• 解决方案的质量取决于精心选择的初始候选项和每个查询的适当索引组合选择。
• 有了更多的候选项，成本请求在运行时占据主导地位，而每个查询的索引数量会影响求解器运行时。

5.7 Dexter

• Dexter识别出合适的索引组合，并保证低的、恒定的运行时间。然而，解决方案的粒度通常过于粗糙。

5.8 Extend

• Extend是在可接受的时间内识别宽索引的唯一算法，索引宽度对运行时没有显著影响。
• 对于较大的预算，运行时间可以减少，因为确定了较少但较大的索引。
• 解决方案质量和运行时间之间的折中对于各种预算来说是最好的。

5.9 DTA

• 大量的种子配置保证了合适的配置，特别是对于中小型预算，通常是最好的。
• 当考虑到随时中断算法的能力时，它的运行时间可以与大多数其他方法相提并论。

6 CONCLUSIONS

• 如果需要大预算的快速解决方案，并且索引宽度有限，建议使用AutoAdmin，特别是DB2Advis。
• 如果更高的运行时间是可行的，我们建议Relaxation。
• 对于所有相关的候选组合都可以被详尽列举的小问题，CoPhy的LP保证了任何预算的最优解。
• Dexter是一个简单易用的开源选项，开销很低。
• 与其他算法相比，Drop是最容易实现的。
• 总的来说，Extend和DTA在广泛的场景中提供了运行时和解决方案质量的最佳组合。