Breaking It Down: An In-depth Study of Index Advisors

contribution

主要有五点。

1. 端到端分析，即贯穿索引推荐全工作流的完整评估。通过将索引推荐系统解构为三个核心构建模块，建立分类体系对各模块采用的方法进行归类，并系统分析这些方法的优缺点。
2. 统一的开源测试平台，在11个开源或真实数据集上实现了17种索引推荐工具，支持可定制配置以满足多样化测试需求。
3. 多场景下对各类数据库系统中的索引推荐工具展开大规模评估，测试其适应性与鲁棒性，从而确定实际应用场景边界。
4. 构建各模块的变体开展细粒度消融实验，借助可解释机器学习技术识别有效变体，并定位影响索引推荐性能的关键因素。
5. 为索引推荐工具的未来发展指明研究方向。

工作流拆解

两种考虑：

1. 按机制分类：

2. 启发式规则

3. 基于学习

4. 选择的参考：

5. 预算（所需最大存储？）

6. 索引的类型（单列/多列）

主要聚焦于选择，不关心物理设计。都用B+树。

文章将index advisor拆解为三个模块。

1 生成索引候选

主要有四种方案。

随机列排列（permutation）

这类方法通过两步生成候选索引：

1. 解析工作负载​​：提取所有可建立索引的列。
2. ​​合成候选索引​​：在给定的最大索引宽度（即索引包含的列数）内，对提取的列进行排列组合生成候选。

• ​​简化策略​​：部分工具仅生成单列索引；另一些通过模拟执行（what-if）筛选查询计划中实际使用的索引，以减少候选数量。

基于规则（rule-based）的构造

依据查询模式规则生成候选索引

1. 列分类：根据语法特征（JOIN/EQUAL等predicate类型），将索引列分组。
2. 启发式规则生成：DBA放入。

• 扩展考量​​：部分工具还会结合列的统计信息优化候选生成。

基于前缀扩展

动态维护候选索引，而非成批生成。

1. 迭代优化​​：每一轮基于上一轮已选索引，通过追加列生成新候选。
2. 宽度限制​​：候选索引的列数逐步增加，且仅当某前缀索引被选中后，才会考虑其多列扩展版本。

基于学习的过滤模型

通过ml筛选无效候选索引

1. query filter：

• 输入：统计信息。
• 输出：workload中代表性query。

2. index filter

• 生成候选：基于代表性query，排列可索引列，生成候选。
• 过滤无效：根据查询计划/统计信息等，去除低于阈值的候选。

2 索引选择

启发式搜索策略

1. 从空集开始追加：增量迭代

• 贪心
• 混合策略：部分工具先暴力搜索部分最优索引，再用贪心算法补充剩余索引。
• 随机优化​​：通过随机交换已选/未选索引来避免局部最优。

2. 从全集开始驱逐：减量迭代

• 剔除最无效索引​​：优先移除对工作负载代价影响最小的索引。
• 索引变换​​：合并/拆分/截断/移除/聚簇（加速范围查询）。

数学方法求解

这类方法将索引选择建模为​​线性规划（LP）问题​​：

• 变量​​：每个索引是否被选为二元变量（0/1）。

• 目标函数​​：最小化工作负载总代价（基于统计信息）。

• 约束条件​​：如存储预算限制。

• 优化技巧：

  • 简化：限制每查询仅关联一个索引。
  • 分治策略​​：将大问题分解为子问题并行求解。

基于学习的策略

将选择过程表示为马尔科夫决策过程MDP并使用强化学习解决这个问题。

1. 在线学习策略（Online Learning Policy）​​

• ​​适用场景​​：静态工作负载。
• ​流程​​：通过试错迭代优化策略。
• 状态表示​​：
  ​​工作负载特征​​：一维查询频率向量（每通道对应一查询）。
  ​​索引状态​​：多热向量（每通道表示索引是否被选）。
  ​​扩展信息​​：列顺序、索引大小统计。
• ​​优化算法​​：
  ​​深度Q网络（DQN）​​：神经网络预测动作价值（Q值）。
  ​​多臂老虎机（MAB）​​：平衡探索与利用。
  ​​蒙特卡洛树搜索（MCTS）​​：通过模拟选择最优动作。

2. ​​离线学习策略（Offline Learning Policy）​​

• ​​适用场景​​：动态工作负载。
• ​​流程​​：先离线训练，再直接为新负载推荐索引。
  ​​- 状态表示​​：
  ​​工作负载特征​​：查询表示矩阵（每行为统计向量或模型生成的特征）。
  ​​扩展信息​​：列选择率、存储预算等。
• ​​优化算法​​：
  DQN:估计索引收益（Q值）。
  近端策略优化（PPO）：直接优化策略网络参数。

3. ​训练与推理机制​​

• ​​在线学习​​：
  训练与测试为同一工作负载，需针对新负载重新训练。
• 离线学习​​：
  训练与测试为不同负载，直接泛化到新负载，但需在查询模式显著变化时重新训练。

3 索引收益评估

不真正构建索引来进行评估。

基于统计信息

利用数据库优化器的模拟执行（what-if调用）估算索引收益，无需实际构建索引。

1. 查询代价估算：通过假设性索引（如PostgreSQL的HypoPG扩展）调用优化器，返回加权操作成本（如顺序扫描代价seq_page_cost）。
2. 索引大小估算​​：基于预定义函数计算。

直接复用数据库优化器的统计模型，结果可靠。但依赖优化器的成本函数准确性，可能低估复杂索引的收益。

学习型的评估模型

通过机器学习模型建立“工作负载特征+索引属性→收益”的映射关系。

1. 分类模型（Classification Model）​​

• ​​任务​​：比较两个索引的优劣（二分类问题）。
  ​​- 输入​​：查询计划特征（如节点操作代价总和）。
  ​​- 输出​​：选择收益更高的索引。

2. 回归模型（Regression Model）​​

• ​​任务​​：直接预测索引带来的​​绝对代价$cost_{w/index}$降低​或​​相对$1-\frac{cost_{w/index}}{cost_{w/o/index}} $降低比率​。
• ​​模型设计​​：
  • 使用深度学习（如基于注意力的模型）捕捉索引相关特征。
    ​​- 关键特征​​：
    ​​操作类型​​：受索引影响的查询计划节点（如索引扫描 vs 全表扫描）。
    ​​数据统计​​：索引列的选择率（distinct ratios）。
    ​​索引结构​​：列的顺序（如(a,b)与(b,a)收益不同）。

3. ​训练与推理​​：

• ​​离线训练​​：需标注数据集（含查询计划、实际延迟降低等）。
  ​​- 泛化性​​：同一数据集内可直接应用，但查询模式显著变化时需重新训练。

---

实验平台设计

直接看代码。

---

表现评价：静态工作负载

基于OLAP的工作负载
不同随机种子生成参数化查询模板/负载规模从单查询到全模板覆盖/查询频率随机分配(1-1000)。

1 选择有效性

• 学习型方法​​在相同查询负载下比启发式方法推荐更优索引（如SWIRL相对成本降低37.48% vs 启发式平均26.30%），但性能波动更大（标准差5.01，是启发式的2.55倍）。

• 试错策略能捕捉复杂模式，但错误尝试可能导致策略不稳定。

• 启发式方法中DTA表现最佳（成本降低36.14%），因其支持多列索引且无需预设宽度限制。

2 选择效率

• 离线学习策略​​（如DRLindex）效率最高（平均591.39ms，比在线学习快163.32倍），因省去实时搜索和训练开销。
  ​​
• 最耗时方法​​：减量式启发式搜索（如Relaxation and Drop在TPC-DS上耗时超其他10.26倍），主要因为需要全量候选集初始化。
  ​​
• 关键瓶颈​​：79.53%时间用于索引收益估计，其中72.73%代价消耗在模拟请求（Cost Request）。

3 选择粒度

​​查询级推荐​​优于负载级：

• 启发式成本降低48.11%（负载级31.82%），学习型41.47%（负载级21.13%）。
• 简单场景（如单查询）缩小搜索空间，DB2Advis甚至快于SWIRL。

4 预算影响

• ​启发式索引推荐工具​​在存储预算增加时能推荐更有效的索引。
  启发式方法​​的相对成本降低率（Relative Cost Reduction）随存储空间（Storage）和索引数量（#Index）增加呈上升趋势。

• ​​基于学习的方法​​在预算增大时可能推荐次优索引。
  基于学习的方法的相对成本降低率则可能随存储空间/索引数量增加而下降。
  与学习型基数估计模型的发现一致：添加谓词时，基数估计可能因模型偏差而失效。

• 可靠性问题​​：
  学习型方法的不可预测性引发对其可靠性的担忧。
  ​​可解释性缺失​​使其难以满足实际应用的严苛要求，尤其在需要稳定性能的场景（如金融、医疗数据库）中可能不适用。

表现评价：动态工作负载

通过三种方式构建动态工作负载来验证索引推荐工具的鲁棒性：

• ​​频率变化​​：保持查询不变，随机分配1-1000的频率值
  ​​- 查询扰动​​：通过添加新谓词模拟典型工作负载漂移
  ​​- 随机生成​​：基于指定连接谓词随机生成查询，模拟极端工作负载变化

5 频率变化/小扰动场景

• 启发式和基于学习的方法在TPC-H基准测试中表现相当（平均相对成本降低28.53% vs 27.29%）
• 在数据分布倾斜的TPC-H Skew基准上性能显著下降（38.58% vs 30.31%）
• 离线学习策略在简单数据分布下能快速适应小变化，但在倾斜数据上训练曲线波动更大

6 随机生成工作负载

学习型方法表现明显逊色：

• TPC-H基准：28.10% vs 启发式的40.61%
• TPC-H Skew基准：19.12% vs 启发式的41.31%
  收敛性问题突出，特别是在倾斜数据上。

总而言之，动态负载情况学习型仍然略差于启发式方法。

---

表现评价：静态工作负载

数据操作语句（INSERT/UPDATE/DELETE）引起的数据变化影响

7 简单查询场景

• 两类方法对简单SELECT语句都表现良好：
  • 启发式平均成本降低72.71%
  • 学习型平均成本降低65.57%
• 执行时间普遍<100秒
• 优势原因：事务查询结构简单（SPJ模式），平均仅3.5个选择谓词，候选索引数量少

8 读写比例影响

• 启发式方法在读写密集型表现优异。
  • Extend和AutoAdmin吞吐量达699.16请求/秒
  • 延迟仅1425.6ms（比其他低698倍）
• 学习型方法在含IUD语句（insert/update/delete）时失效。
  • SWIRL在写密集型负载吞吐量仅1.21-3.55请求/秒
• 关键缺陷：现有工具未考虑IUD语句的索引维护开销。

9 数据变化影响

• 启发式方法表现稳定（1GB→10GB数据量变化）
• 学习型方法出现性能衰退：
  • SWIRL在TPC-H Skew上成本降低减少14.89%
• 根本差异：
  • 启发式每次从头开始选择
  • 学习型依赖离线训练的固定策略

---

不同模块构建的影响

11 候选索引生成方法对比