1 背景

随着美团业务量的不断增长，慢查询的数量也日益增多。目前，日均慢查询数量已经超过上亿条，如果仅依靠DBA和开发人员手动地对这些慢查询进行分析并建立合适的索引，显然是不太现实的。为了解决这一难题，美团内部DAS（数据库自治服务）平台已经集成了基于代价的慢查询优化建议来自动地为慢查询推荐索引。然而，仍然存在一些问题：

  • 基于代价的慢查询优化建议是借助于优化器的代价估计，来推荐出对于查询代价改善最大的索引，但优化器的代价估计并不是完全准确[1]，因此可能存在着漏选或者错选推荐索引的问题。
  • 基于代价的慢查询优化建议需要计算查询在不同索引下查询代价的改善程度，因此需要进行大量的增删索引操作，但真实增删索引的代价是非常大的，需要借助于假索引[2]技术，假索引技术并不创建真实的物理索引文件，只是通过模拟索引存在时的查询计划来估算索引对于查询的收益。目前，美团大部分业务都是运行在MySQL实例上的，不同于商业数据库SQL Server和开源数据库PostgreSQL，MySQL内部并没有集成假索引技术，因此需要自己构建支持假索引的存储引擎，其开发成本较高，这也是目前DAS平台基于代价的慢查询优化建议所采用的方案。

为了解决上述两个问题，美团数据库研发中心与华东师范大学数据科学与工程学院展开了《基于数据驱动的索引推荐》的科研合作，双方通过在DAS平台上集成基于AI+数据驱动的索引推荐，来与基于代价的方法并行地为慢查询推荐索引，以提升推荐效果。

  • 首先，基于代价的方法每天会为慢查询推荐索引，并在采样库上评估推荐的索引是否真正地改善了查询的执行时间，这为AI方法积累了大量可信的训练数据，根据此数据训练的AI模型，可以在一定程度上弥补基于代价的方法漏选或错选索引的问题。
  • 其次，基于AI的方法将针对慢查询的索引推荐看作是二分类问题，通过分类模型直接判别在某一列或某些列上建立索引是否能够改善查询的执行性能，并不借助于查询优化器和假索引技术，这使得AI方法更加通用，且开发成本更低。

2 索引推荐介绍

索引推荐可以划分为两个级别：Workload级别和Query级别：

  • 在Workload级别，索引推荐是在限制的索引存储空间或索引个数下，推荐出一组最优的索引集合来使得整个Workload的代价最低。
  • Query级别的索引推荐可以被视为Workload级别索引推荐的简化版本，在Query级别，索引推荐是为单个慢查询推荐缺失的索引，以改善其性能。

2.1 基于代价的索引推荐

基于代价的索引推荐[3]大多聚焦于Workload级别的索引推荐，出现在查询中每一列或者列的组合都可以看作是一个能够改善Workload代价的候选索引，所有的候选索引构成了一个巨大的搜索空间（候选索引集合）。

基于代价的索引推荐的目标，是在候选索引集合中搜索出一组最优索引集合，以最大程度地改善Workload代价。如果候选索引的个数$N$，限制的最大推荐索引个数是$M$，那么最优索引集合的搜索空间是：

$$ C_{N}^{M}=\frac{N *(N-1) \ldots(N-M+1)}{M !} $$

这是一个属于NP-hard范畴的搜索问题[4]。目前，基于代价的索引推荐方法大多会采用“贪心策略”来简化搜索过程，但这可能会导致最后推荐出的索引是次优解[5]。

2.2 基于AI+数据驱动的索引推荐

基于AI+数据驱动的索引推荐聚焦于Query级别的索引推荐，出发点是在某个数据库中因为缺失索引导致的慢查询，在其它数据库中可能有相似的索引创建案例：这些查询语句相似，因此在相似位置上的列创建索引也可能带来类似的收益。例如下图中，查询$q_s$和$q_t$在语句结构和列类型上非常相似。因此，我们可以通过学习查询$q_s$的索引创建模式来为查询 $q_t$推荐缺失的索引。

对于不同列数的索引推荐，我们会分别训练基于XGBoost的二分类模型。例如，我们目前最高支持三列的索引推荐，因此会分别训练一个单列索引推荐模型、一个两列索引推荐模型和一个三列索引推荐模型。对于给定的一个单列候选索引和它对应的慢查询，我们使用单列索引推荐模型来判断该单列候选索引是否能够改善该慢查询的性能。

同样的，对于给定的一个两列（三列）候选索引和它对应的慢查询，我们使用两列（三列）索引推荐模型来判断这个两列（三列）候选索引是否能够改善该慢查询的性能。如果一条慢查询中包含的候选索引个数为$N$，那么则需要$N$次模型预测来完成对这条慢查询的索引推荐。

3 整体架构

基于AI+数据驱动的索引推荐的整体架构如下图所示，主要分为两个部分：模型训练和模型部署。

3.1 模型训练

如上文所述，我们收集DAS平台基于代价的慢查询优化建议每天的索引推荐数据（包括慢查询和被验证有效的推荐索引）作为训练数据。我们生成每条查询的单列、两列和三列候选索引，并通过特征工程来为每个候选索引构建特征向量，使用索引数据来为特征向量打标签。之后，单列、两列和三列特征向量将分别用于训练单列、两列和三列索引推荐模型。

3.2 模型部署

针对需要推荐索引的慢查询，我们同样生成候选索引并构建特征向量。接下来，我们使用分类模型来预测特征向量的标签，即预测出候选索引中的有效索引。随后，我们在采样库上创建模型预测出的有效索引，并通过实际执行查询来观察建立索引前后查询性能是否得到改善。只有当查询性能真正得到改善时，我们才会将索引推荐给用户。

4 建模过程

4.1 生成候选索引

我们提取查询中出现在聚合函数、WHERE、JOIN、ORDER BY、GROUP BY这些关键词中的列作为单列候选索引，并对这些单列候选索引进行排列组合来生成两列和三列候选索引。同时，我们会获取查询所涉及的表中已经存在的索引，并将其从候选索引集合中删除。这一步骤遵循索引的最左前缀原则：如果存在索引$Idx (col1, col2)$，那么候选索引 $(col1)$ 和 $(col1, col2)$ 都将从候选索引集合中删除。

4.2 特征工程

一个候选索引的特征向量包括语句特征和统计特征两部分。语句特征描述了候选索引列在查询中的出现位置（采用one-hot的编码方式），统计特征描述了候选索引列的统计信息，如所在表的表行数、Cardinality值、选择率等，这些是判断是否需要在候选索引列上建立索引的重要指标。

下表以单列候选索引 $(col1)$ 为例，展示了它的部分重要特征及其含义：

两列候选索引 $(col1, col2)$ 的特征是通过对单列候选索引 $(col1)$ 和 $(col2)$ 的特征进行拼接而成的，此外，我们还会计算 $col1$ 和 $col2$ 共同的Cardinality值作为两列候选索引 $(col1, col2)$ 的额外统计特征，以更加全面地描述其统计信息。同样地，我们也会采用使用这种方式来构建三列候选索引 $(col1, col2, col3)$ 的特征。在生成完一条查询的特征向量之后，我们使用这条查询使用到的索引来为生成的特征向量打标签。

4.3 建模举例

下图以查询 $q_1$ 为例，展示我们为训练集中的一条查询生成特征向量并打标签的过程。查询 $q_1$ 涉及两张表customer表和warehouse表，其中customer表的c_w_id、c_id、c_d_id、c_last四列参与到查询中，因此对应生成四条单列特征向量；warehouse表的w_id列参与到查询中，因此只生成了一条单列特征向量。查询 $q_1$ 使用的单列索引为Idx(w_id)，所以单列候选索引 (w_id) 对应的特征向量被标记为正样本，其余特征向量则被标记为负样本。

接下来，我们对单列候选索引进行排列组合来生成多列候选索引及其特征向量。由于查询 $q_1$ 使用到的多列索引只有一个三列索引Idx(c_d_id, c_id, c_last)，因此我们跳过生成两列候选索引，只生成三列候选索引。这是因为我们是基于查询使用到的索引来为特征向量打标签的，如果查询没有使用到两列索引，那么生成的所有两列特征向量均为负样本，这可能会导致训练集正负样本不均衡的问题。

最后，基于查询使用到的三列索引，我们将三列候选索引 (c_d_id, c_id, c_last) 对应的特征向量标记为正样本。以上就是我们为查询 $q_1$ 生成特征向量并打标签的整个过程，查询 $q_1$ 为单列索引推荐模型的训练集贡献了五条样本（一条正样本，四条负样本），为三列索引推荐模型的训练集贡献了六条样本（一条正样本，五条负样本）。

4.4 模型预测和索引评估

在为一条慢查询推荐索引时，我们依次生成慢查询中所有的单列、双列和三列候选索引，并通过上述的特征工程来构造特征向量。然后，我们将特征向量输入给对应的分类模型进行预测，并从三个分类模型的预测结果中分别挑选出一个预测概率最高的候选索引（即一个单列索引、一个两列索引和一个三列索引）作为模型推荐的索引。

虽然推荐的索引越多，慢查询的性能就越有可能得到改善，但是模型推荐的部分索引可能是无效的，这些无效索引带来的存储空间开销和更新索引的开销是不可忽视的。因此，直接将模型推荐的索引全部推荐给用户是不合理的。为此，在将索引推荐给用户之前，我们会首先将三个分类模型推荐的索引建立在采样库上进行验证，采样库是线上数据库的一个mini版本，它抽取了线上数据库的部分数据。在采样库上，我们会观察在建立推荐的索引之后，查询的执行时间是否得到改善。如果得到改善，我们就把查询使用到的一个或多个模型推荐的索引作为索引建议推荐给用户。

5 项目运行情况

正如前文所述，美团DAS平台目前采用代价方法和AI模型并行为慢查询推荐索引。具体来说，AI模型可以在某些场景下，弥补代价方法漏选或错选推荐索引的问题。就在刚过去的3月份，在代价方法推荐索引的基础上，AI模型有额外12.16%的推荐索引被用户所采纳。

这些额外补充的索引对于查询的改善情况如上图所示：上半部分展示了优化的查询执行次数，下半部分展示了查询在使用推荐的索引之后的执行时间以及减少的执行时间，这些索引总计约优化了52亿次的查询执行，减少了4632小时的执行时间。

6 未来规划

目前，大模型技术（如GPT-4）已经得到了越来越多的认可，几乎可以胜任各种领域的任务。我们计划尝试通过Fine-Tune开源的大型语言模型（如Google开源的T5模型）来解决索引推荐的问题：输入一条慢查询，让模型来生成针对慢查询的索引建议。

在推荐索引无法改善慢查询的情况下，后续我们可以提供一些文本建议来帮助用户优化SQL，比如减少返回不必要的列，使用JOIN代替子查询等。

7 本文作者

彭淦，美团基础研发平台工程师，主要负责美团数据库自治服务DAS的SQL优化建议工作。

8 特别感谢

在这里特别感谢华东师范大学数据科学与工程学院的蔡鹏教授，教授在VLDB、ICDE、SIGIR、ACL等领域重要国际会议上发表多篇论文。目前的研究方向为内存事务处理，以及基于机器学习技术的自适应数据管理系统。本文也是美团数据库研发中心跟蔡鹏教授展开科研合作后的具体实践。

美团科研合作致力于搭建美团技术团队与高校、科研机构、智库的合作桥梁和平台，依托美团丰富的业务场景、数据资源和真实的产业问题，开放创新，汇聚向上的力量，围绕机器人、人工智能、大数据、物联网、无人驾驶、运筹优化等领域，共同探索前沿科技和产业焦点宏观问题，促进产学研合作交流和成果转化，推动优秀人才培养。面向未来，我们期待能与更多高校和科研院所的老师和同学们进行合作。欢迎老师和同学们发送邮件至：meituan.oi@meituan.com。

9 参考文献

  • [1] Leis V, Gubichev A, Mirchev A, et al. 2015. How good are query optimizers, really? Proc. VLDB Endow. 9, 3 (2015), 204-215.
  • [2] https://github.com/HypoPG/hypopg
  • [3] Kossmann J, Halfpap S, Jankrift M, et al. 2020. Magic mirror in my hand, which is the best in the land? an experimental evaluation of index selection algorithms. Proc. VLDB Endow. 13,12 (2020), 2382-2395.
  • [4] Piatetsky-Shapiro G. 1983. The optimal selection of secondary indices is NP-complete. SIGMOD Record. 13,2 (1983), 72-75.
  • [5] Zhou X, Liu L, Li W, et al. 2022. Autoindex: An incremental index management system for dynamic workloads. In ICDE. 2196-2208.