本文是SIGMOD 2019《Automatically Indexing Millions of Databases in Microsoft Azure SQL Database》论文的笔记，个人见解。本文重点讨论了Azure的自动索引推荐系统，讨论了整个过程的细节和反馈。
1. 前言
自动索引推荐是数据库领域里的一个研究了很久的问题，也有很多种算法提出来，但大多是基于数据表的统计信息或优化器的计算方式，结合SQL语句中的查询条件进行选择，然后得到当前SQL所需要使用的索引。
然而，一个端到端的自动索引推荐系统却很少见，尤其是在大规模运维的云上数据库系统里更是没见过有这类功能。主要挑战点如下：
1. 如何大规模的应用到所有的数据库上。Azure上数据库覆盖了超过140个国家，涉及了50多个全球化区域。
2. 要推荐出合适的索引。推荐索引时还有很多附加因素，如索引占据的空间大小。
3. 最好的索引推荐算法是依赖查询优化器组件。数据库理论上的最优索引与查询优化器实现过程中采用的索引不一定是一致的，而生产环境下是不接受出现这种badcase的。（毕竟理论是理论，实现是实现，在实现的过程中会权衡多种因素对理论做一定的妥协。）
4. 自动索引的操作不能影响用户。建索引可能会锁表、会占大量cpu或I/O。
2. 方法
本文主要是介绍了框架，包含如下几个组件：
1. 控制面板（Control Plane）：作为整个系统的控制面板，掌握整个自动优化流程的生命周期，协调不同组件。
2. 索引推荐器（Index Recommender）：分析业务的workload，识别出哪些index需要被创建或者是被抛弃。这里主要是微软以前做过的两个工具MI（Missing Index）和DTA（Database Engine Tunning Advisor）。
3. 验证器（Validator）：分析index对workload的影响，用于检查新的index是否产生了导致SQL性能变差的情况。
微软的这个工作已经做了很多年，它的主要时间节点如下：
2015年：自动优化系统启动
2016年：整个系统GA
2018年：已经百万级别数据库实例的应用
3. 工程方面
在工程上，为了避免数据跨region的问题，微软在每个region都部署一个auto-index的服务节点，服务之间的调用采用了RPC调用，服务的内部细节见Figure 4。
从Figure 4的流程上可以看出，Control Plane是整个流程的核心，它发起任务后，由SQL引擎根据workload进行索引推荐，然后将建议反馈给Control Plane和用户Portal，然后Control Plane再启动创建索引和验证索引流程，让SQL引擎在Validator上基于Query Store的数据进行验证，再把验证结果反馈给Control Plane和用户Portal。其中，该服务中的有两个重要的节点：
SQL Server查询优化器。它可以产生出一些缺失的索引，也会借助“what-if” API去解决索引配置。
Query Store。这个工具将所有的SQL流水数据进行存储，并且对不同的SQL 模板进行了统计，记录了SQL层面很多维度的数据。
3.1. Control Plane
Control Plane部分管控整个流程，主要的任务就是如Figure 4里的作用：
1. 发起数据库诊断和生成索引
2. 应用索引推荐
3. 验证推荐结果
4. 检测索引应用后的效果或告警
而推荐出的索引在整个流程中是有很多种状态：
Active：索引准备应用或者删除（推荐删除某个索引 也是索引推荐的一部分）
Expired：索引由于生命周期原因导致的过期
Implementing：正在执行索引推荐的结果
Validating：验证应用索引建议后的效果
Success：索引建议符合预期
Reverting：索引建议Validate过程中出现性能变差的case，系统正在回滚
Reverted：回滚完成
Retry：重试
Error：失败
跟踪索引建议的这些状态是管理索引推荐流程的重要环节，这样对数据跟踪有很大帮助，也能快速定位问题。
3.2. Index Recommender
微软的索引推荐器主要是两个：MI（Missing Indexes）和DTA（Database Engine Tunning Advisor）。这两个工作均已经发布很久，经过了线上环境的验证。
其中，MI可以识别出数据库中目前不存在且能提升SQL性能的索引，它通过DMV（Dynamic management view）或者执行计划把缺失的索引暴露出来，相对比较轻量。MI是个局部优化，同时它不能对groupby join, order by类查询产生优化，并且也不能从workload视角对索引进行优化。DTA则是一个较为完整的physical design tool级别的工具，它可以用workload作为输入并产出基于workload级别优化的索引建议，它也会使用 what-if 优化器。DTA对资源的消耗比较高。因此，微软在机型偏差的数据库上采用MI进行推荐，对机型较好的采用了DTA进行推荐。
在workload选择上，微软利用QueryStore中的数据对业务workload进行排序处理，然后选择占比较大的部分进行整体性能优化，例如占比workload>80%以上的SQL部分。
（对于MI和DTA的更多细节处理，以及微软在应用过程中处理的一些操作，还是看原文吧，就两页纸，这里不去翻译了。只能说，这里的细节坑都是生产环境中真实要处理的地方，如workload选择、中间表优化、优化器badcase等问题。）
对于索引删除建议，这其实也是个很有难度的问题，也是生产环境中被质疑最多的地方，主要难点：
1. 很重要的偶发SQL要用的索引。这种索引通常是特定业务需求下产生的SQL。例如，每个月底才运行一次的报表SQL。
2. 用户加了hint或者force index的查询。在未优化索引时，开发同学可能会通过hint或者force index来纠正某些优化器对SQL执行的bad case。
3. 重复索引。有些索引可能已经包含在另一个索引里，如何找出和选择这些重复的索引，也是很困难的。因为有时优化器的选择跟我们理解的选择还是有差异，会出bad case。
微软在针对上面这3种问题上，采用了更加详尽的索引使用统计、避开force index、扩大索引分析窗口长度等方法，尽可能的将影响降到最低。
3.3. Implementation and Validation
当索引推荐器产生出索引后，要对这些建议进行验证，才能应用到线上环境。
在执行的时间上，操作的前提是选择业务的低峰期，进行索引变更，并且把变更索引的权重调整到最低，避免影响用户。
在验证细节上，评价指标值中只关注逻辑指标（cpu time、logic read等），评价对象是只分析与索引建议相关的SQL，评价方法上采用了Welch t-test来校验索引变更前后分布是否一致。若检测到有性能退化，则回滚。
4. 实验阶段
实验阶段，是指如何验证索引建议的正确性。由于业务的多样性，SQL也有很多种case需要去验证算法的覆盖度。
微软采用了一个非常实用且高效的方法：B-instance。思路非常简单：为了给A数据库产生索引推荐，先做一个A的镜像B，然后对镜像B进行索引推荐并应用，这样B就是具备新索引的节点。然后，当业务SQL执行到A的时候，同时发送给B一份，然后观察B节点上的性能指标，如果性能变好就说明索引建议有效。在这个过程中，创建镜像B、转发SQL流量、B节点的结果均确保对A实例和业务无影响。
这个方法仅在实验阶段用于验证算法和方案的有效性，验证结束后的线上生产环境中并没有对每个数据库均做一套B-instance方案。
4.1. 实验结果
由于MI和DTA应用在了不同机型，因此实验也分成了两类建议效果的评价。
基准数据为User，即数据库上DBA自己产生的索引。通过随机从这些索引中扔掉索引，再让算法MI/DTA进行推荐，然后对比前后的效果。
从Figure 6来看，MI和DTA并没有出现一个完全覆盖另一个的情况，说明了MI和DTA服务同时存在的必要性。算法推荐出的索引可以在85~90%的数据库实例上达到甚至超过DBA调整的索引，说明了算法的有效性。在Preminum tier中User的占比高于Standard tier中User，说明在非常复杂的workload上，DBA人工的索引效果要更好一些。
5. 商业价值
截止到2018年10月，Auzre上产生了250 K的新建索引建议和3.4 Million的删除索引建议。
在打开了自动推荐索引的数据库上，约50K的索引被创建，约20K的索引被删除。
约11%的索引建议产生了回滚。
6. 结论
微软的工作做的非常细致，毕竟是应用在Azure全部数据库上且运行了两年以上的系统。每个基础工作均有扎实的基础，在确保不影响用户的前提下也创新了很多操作，如低优先级的index operation、invisible index、resumable index create等等。
