目前，美团外部的日均慢查问数量曾经超过上亿条，如何对对这些慢查问进行剖析并建设适合的索引，是美团数据库研发核心面临的一项挑战。美团数据库平台研发组与华东师范大学开展了科研单干，通过基于 AI+ 数据驱动的索引举荐，来与基于代价的办法并行地为慢查问举荐索引，以晋升举荐成果。
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.
浏览更多
| 在美团公众号菜单栏对话框回复【2022 年货】、【2021 年货】、【2020 年货】、【2019 年货】、【2018 年货】、【2017 年货】等关键词，可查看美团技术团队历年技术文章合集。
| 本文系美团技术团队出品，著作权归属美团。欢送出于分享和交换等非商业目标转载或应用本文内容，敬请注明“内容转载自美团技术团队”。本文未经许可，不得进行商业性转载或者应用。任何商用行为，请发送邮件至 tech@meituan.com 申请受权。