简介

我们知道索引对于数据库的SQL查询性能至关重要，一个好的索引能够让SQL的执行方式从全表扫描变成索引点查，从而使得查询耗时由秒级降低到毫秒级，获取上千倍的性能提升。但是究竟如何挑选一个好的索引去建立，比较依赖研发同学对数据库引擎内部的优化、执行等原理的了解。研发同学想要建立的索引对SQL到底有没有性能提升，具体能够提升多少，这都是我们在实际建立索引前就想提前知道的。如果数据库本身可以为SQL推荐索引，并给出建立索引后的性能提升量化指标，那将会节省大量的人力。

PolarDB-X数据库的SQL Advisor利用基于代价的优化器提供索引推荐功能，智能化地解决如何挑选索引的问题。本文将会介绍如何使用索引推荐的功能以及索引推荐的技术原理，帮助大家更加高效地使用和更加深入地了解PolarDB-X。

EXPLAIN ADVISOR
SELECT sum(l_extendedprice) / 7.0 AS avg_yearly
FROM lineitem,
     part
WHERE p_partkey = l_partkey
  AND p_brand = 'Brand#23'
  AND p_container = 'MED BOX'
  AND l_quantity <
    (SELECT 0.2 * avg(`l_quantity`)
     FROM lineitem
     WHERE l_partkey = p_partkey);

快速上手

下面是我们的一次TPCH-Q17测试的截图。启用 SQL Advisor 做索引推荐前，一条 SQL 的查询时间为 28.76s。

之后查看 SQL Advisor 给出的索引推荐并添加相应的索引。调用SQL Advisor的语法如下图，explain advisor + sql。我们可以看到SQL Advisor会返回对应推荐索引的SQL(ADVISE_INDEX字段), 添加索引前的代价，添加索引后的代价, 代价提升的比例以及执行计划。30倍的IO提升说明这是个很有用索引。

EXPLAIN ADVISOR
SELECT sum(l_extendedprice) / 7.0 AS avg_yearly
FROM lineitem,
     part
WHERE p_partkey = l_partkey
  AND p_brand = 'Brand#23'
  AND p_container = 'MED BOX'
  AND l_quantity <
    (SELECT 0.2 * avg(`l_quantity`)
     FROM lineitem
     WHERE l_partkey = p_partkey);

添加索引后执行相同的 SQL，时间减少到 1.41s。可以看到通过SQL Advisor优化SQL变得更加简单，高效。

技术原理

索引推荐这项技术早在[1][2]二十多年前就已经有人研究了，概括成来索引推荐就是通过分析SQL，枚举可能的索引组合，并通过优化器What-If的能力，选出其中收益最高的索引组合推荐给用户。下面我们将会详细介绍每一步到底是如何做的。

分析Indexable Column

首先我们需要分析出SQL中哪些列可以利用索引，我们称这些列为Indexable Column。例如:

1. Where条件中的 =, >, <, between, in等列

1. Order By的排序列

1. Group By的聚合列，MIN，MAX函数列

1. Join的Condition等值条件列

我们例子中的Indexable Column是part表的p_partkey，p_brand，p_container列和lineitem表的l_partkey，l_quantity列。

构建Candidate Index

分析出每张表可能存在哪些Indexable Column后，我们再将这列构建出(单列或多列的)索引，这些索引我们称之为Candidate Index。

Candidate Index可以通过参数控制最多生成的索引长度。当前配置为2，即最多考虑2列组成的索引。这依据的Insight是大多数索引前两个列对性能影响最大。
不失一般性，下面给出任意列长度的Candidate Index构建方法。

1. 单列索引通过枚举indexable column，并通过启发式方法过滤收益低的索引(例如：只考虑列的Cardinality值足够大的列)。

1. 多列索引(lenght = k)，通过k-1的CandidateIndex + 单列索引枚举。

我们例子中的Candidate Index有

1. key (l_partkey)

1. key (p_brand)

1. key (p_container)

1. key (p_parykey, p_container)

1. 等等

枚举Configuration

我们将多个Candidate Index的集合称之为Configuration。Configuration最简单的方式可以通过组合数枚举Candidate Index获得。索引推荐最终的结果就是要找到使得SQL代价下降最低的Configuration。简单来说说我们要给用户推荐一组索引，让它的SQL跑得最快。

我们应用下面的假设限制Configuration枚举的数量:

1. 假设SQL中每张表中关键起作用的索引不会超过2个。

1. 假设SQL中多表Join的场景，其中最重要需要考虑索引的表不超过2个。

1. 假设SQL中多张表Join，每张表的索引推荐可以相互独立。

先找到每张表的Candidate Index集合，通过C(n, 2)枚举出Configuration，通过优化器选What-If能力出最优的Configuration。将SQL所有涉及所有表的Configuration汇总作为最终的结果。

我们例子中的Configuration有：

1. key (l_partkey)

1. key (p_brand)

1. key (p_container)

1. key (l_partkey),key (p_container)

1. 等等

优化器What-If能力

我们知道PolarDB-X优化器是一个基于代价的优化器，给定一条SQL，我们可以估算出执行这条SQL的代价。通过(CPU，Memory，IO，Ne)四元组衡量代价的大小。
对于索引推荐来说，优化器的What-If能力[3]指的是，优化器具有假设某些索引存在，并估算出SQL执行代价的能力。简单来说就是不需要真实创建索引，优化器就能够知道这个索引能够对SQL有多少性能提升。PolarDB-X优化器通过What-If能力将SQL Advisor中枚举到Configuration逐一优化并获取SQL的执行代价。最终选择出使得SQL执行代价最低的Configuration。

我们的例子中选择出的最优的Configuration就是：
key (l_partkey)

通过返回的结果我们还可以获取，添加索引前后SQL的代价分别是多少，这个索引大致可以提升30倍的IO效率。添加索引后，SQL执行计划也会给出，可以看到添加索引后，执行计划可以利用BKAJoin来提升IO效率。

总结

本文介绍了PolarDB-X中SQL Advisor的索引推荐功能，通过一个TPCH-Q17的例子展示了索引推荐可以帮助用户更方便、高效地提升SQL的查询性能。并且详细介绍了索引推荐功能背后的技术原理，Indexable Column的分析，Candidate Index的构建，Configuration的枚举，还有优化器的What-If能力。

Reference

[1] Chaudhuri, Surajit, and Vivek R. Narasayya. "An efficient, cost-driven index selection tool for Microsoft SQL server." VLDB. Vol. 97. 1997.
[2] Agrawal, Sanjay, Surajit Chaudhuri, and Vivek R. Narasayya. "Automated selection of materialized views and indexes in SQL databases." VLDB. Vol. 2000. 2000.
[3] Chaudhuri, Surajit, and Vivek Narasayya. "AutoAdmin “what-if” index analysis utility." ACM SIGMOD Record 27.2 (1998): 367-378.