作者介绍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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