查询优化的作用及基本原理

在数据库处理查询语句的过程中，优化器接收用户输入的查询语句并进行一系列的等价变换后，通过查询中的基数与代价估计，从等价的执行计划中选取最优计划执行。由于在执行查询时使用的执行计划好坏对性能的影响非常关键，因此在所有的数据库系统中都存在查询优化器，典型的查询优化器结构如下图所示：

通常，查询优化器会通过如下三个典型组件来协同工作：

• Plan space enumeration：根据一系列的等价变换规则生成与查询等价的多个执行计划。

• cardinality estimation：根据查询表的分布情况，估计查询执行过程中的数据量、数据分布情况等。

• cost model：根据执行计划以及数据库内部的状态，计算按照各个执行计划执行所需要的代价。

在查询优化器中，最为广泛研究的是查询计划中的join order问题，选错join顺序可能极大地影响查询性能。同时，该问题依赖于以上三个组件的能力。

HTAP负载对优化器的新诉求

MySQL是目前被广泛使用的OLTP数据库。在数据的存储、访问以及部分简单或固定pattern的查询下表现出色，为了达到这一点，MySQL的查询优化器做了大量与其执行模型相关的优化。例如，在查询优化阶段执行并消除子查询、基于索引消除order by子句等，这类优化在MySQL的查询优化与执行中起到了很好的效果。但另一方面，也使得MySQL的优化器与其执行模型与存储绑定。在HTAP负载下，很多解决方案是通过行式存储+列式索引（replica）再加上针对列存优化的执行层来进行类似工作负载的复杂查询加速，在这样的条件下，大量MySQL优化器中的假设被破坏。同时，由于其优化器与执行模型以及存储的耦合，使得其很难通过简单的修改以适应HTAP负载的查询优化能力，对于需要处理不同存储模式、不同执行模型以及不同数据模型的数据库来说，优化器需要做到以下几点：

• 与存储层或执行层没有过紧的耦合，便于未来功能的演进。

• 能够处理多维度过滤、连接以及聚合等复杂查询。

• 能够高效地进行查询优化，以满足HTAP中实时分析的诉求。

列存索引查询优化

行存Plan优化及其限制

MySQL的优化器有一套清晰的优化流程，其查询优化流程如下：

1. 应用一些基于规则的优化，规则通常会让plan变得更优，不涉及代价计算。

2. 将部分outer join转换为inner join。

3. 等值推导。如c1 = 5 and c1 = c2可以被转换为c1 = 5 and c2 = 5。

4. 分区裁剪。如果查询仅落在部分分区，那么其他分区将不会被访问，能有效减少扫描的数据量。

5. 子查询消除。部分仅返回一行的子查询会被提前执行并用结果替换该子查询，能简化plan。

6. 基于代价的join reorder。

7. 后续优化。确定表的访问方法，根据使用的索引优化掉ORDER BY与DISTINCT。

该查询优化流程非常清晰，在MySQL的执行模式下也足够好，但是在添加列式replica的负载下，这个优化体系也暴露出了一些问题。如下：

• 基于MySQL执行模式的限制，join reorder仅能生成左深树的执行计划。在HTAP复杂查询下，可能会遗漏最优的执行计划，而通过子查询+join order hint的方式改写SQL，对业务的改动又太大。

• MySQL在枚举执行计划时，会计算每个join的输入行数以及选择率。因为MySQL的Join执行方式中以Index Join为主，MySQL依赖表上已有的二级索引来估计选择率。如果没有二级索引，那么代价估计的误差就可能很大。这契合了原本MySQL的使用场景：join通过索引来完成，并通过索引解决慢查询问题。但面对列式索引的多维过滤、连接以及聚合操作时，需要增加大量二级索引，这种做法不太合适。因为添加索引是一个通过将读负载均摊到写入操作的行为，大量的二级索引会占用大量的存储空间，同时也会减慢数据库的写入效率，虽然MySQL在8.0引入了histogram，但其使用范围有限，仅支持在单表上过滤条件和估计选择率，如果查询语句复杂，histogram并不能给予帮助。

• 将join reorder与其他问题拆分，虽然提高了搜索效率，但可能陷入局部最优问题。

列存索引Plan优化过程

为了解决MySQL原生优化器在HTAP workload下的不足，IMCI针对HTAP workload下可能缺少索引、拥有新的执行模型以及输入复杂查询等情况，补充了新的优化流程来解决这些问题。在使用了列索引的查询中，优化器也通过基于规则的改写与基于代价的查询优化来优化查询。

基于规则的查询计划改写

这一步与MySQL优化器类似，除了MySQL优化器已有的规则之外，还增加了新的规则，这些规则的主要目的是进一步优化列式执行器执行查询的效率以及使执行计划满足执行模型的要求。例如：

• 子查询去关联：在没有索引的情况下，关联子查询的执行类似于nested loop join，这会导致执行效率很差，IMCI通过子查询去关联技术将关联子查询转换为join，使用hash join来高效地执行查询。

• 消除子查询中带有DISTINCT的聚合函数。如下：

  SELECT COUNT(DISTINCT c1) FROM t;
  -- 会被转换为
  SELECT COUNT(c1) FROM (SELECT c1 FROM t GROUP BY c1);

  通过这样的转换可以简化列式执行器的设计，能够支持更多的功能。

• 谓词重排序：单表扫描中存在多个谓词的情况，例如t1.c2 LIKE '%cat%' AND t1.c1 = 5，其中t1.c1 = 5执行的代价较低，且选择率较低，通过重排这两个谓词的顺序，让t1.c1 = 5先执行，可以显著地减少更重的LIKE操作，提高查询效率。

  该步骤实际上也包含了部分基于代价的查询优化，绝大部分情况下都能使得查询更优。如谓词下推这类操作，在这一步通过应用这些规则，使得基于代价的查询优化器与执行器得到了规范的输入，同时提前执行谓词下推这类操作也减少了基于代价的查询优化空间，提高了查询优化的效率。

基于代价的查询优化

在经过基于规则的查询改写之后，plan会被输入到基于代价的查询优化器中。在IMCI中使用了cascade优化器框架来进行查询优化，该框架能够很好地避免查询优化中可能存在的局部最优问题。但在这个框架之外，仍然使用了传统优化器的三个功能模块：plan enumeration、cardinality estimation与cost model，此处以join order问题为例，阐述各个模块的内部原理与工作流程。

Plan enumeration

Plan enumeration是优化器用于枚举plan的组件，用户的一条SQL经过parse、binding等一系列步骤之后，会生成一个初始的查询计划并输入到优化器。优化器会通过规则对输入的查询计划做各种等价变换，产生新的等价查询计划。在IMCI中，这些用于改写计划的规则被分为以下类：

• Transform Rule：这类规则与rewriting rule类似，但这类规则可选，用于优化查询性能，并不泛用。因此，这类规则会被放进IMCI基于代价的优化器中，用于枚举等价查询计划，后续会通过cardinality estimation + cost model选出最优查询计划。

• Implement Rule：这类规则用于逻辑计划到物理计划之间的算法选择。例如，对join可以选择hash join、index join、sort merge join等方式，不同算法适用于不同的场景，因此这类规则也被放进IMCI基于代价的优化器中。

在这个模块中，执行计划会通过这些改写规则生成大量的等价plan，后续通过cost比较选出最佳的执行计划。IMCI使用cascade优化器，通过Memo、Group、GroupExpr这类数据结构保存共用的中间结果，减少了大量冗余的中间结果。但即使这样，含有大量join的查询语句仍可能产生数量巨大的等价计划，对于n个表形成的join，一共有至少2ⁿ种可能的join顺序。在不考虑笛卡尔积的情况下，join plan数量与枚举时间的关系如下图所示：

由上图可以看出，最坏的情况下，包含12张表的join reorder，其时间超过了10秒钟。即使是常见的星形查询，在20张表时优化时间也超过10秒钟。对于一些查询语句中包含非常多表的查询来说，这样的优化时间可能是不能接受的。因此，要选择一个最佳的join顺序，其中包含了三个问题：

1. 枚举出来的join plan包含最优的plan，为了达到这个目的，枚举的效率要足够高，这样才能尽可能地将最好的join plan包含在搜索空间中。

2. 如果join的表实在太多，需要有一个稳定的启发式算法在可以接受的时间内搜索到效果不错的查询计划。

3. 在所有枚举出的join plan中，正确地选择出最好的plan。

cardinality estimation与cost model

通过估算各个查询计划的代价，并从中选出最佳的执行计划。在目前的优化器中，基本流程如下：

1. 通过Cardinality estimation估算出每个算子的输入/输出行数与该算子输出数据之后的近似分布。其依赖两个模块，即统计信息的采集与计算以及计算输入输出行数的逻辑。

2. 通过cost model计算cost，将每个算子的执行代价相加得到总cost，选取总cost最低的执行计划。

IMCI中统计信息的采集与计算

为了在缺少足够的二级索引情况下进行查询优化，IMCI开发了用于自身优化器的统计信息模块，IMCI通过采集表的如下信息来估计算子的输出/输出行数：

• 每个列的基数（列上唯一值的个数，相当于COUNT(DISTINCT col)）。

• 每个列NULL值占有的比例。

• 每个列的最大值与最小值。

• 每个列根据值大小创建histogram。

• 表上的unique key与foreign key属性。

列式存储上统计信息的构建

为了采集这些统计信息，系统会根据表的数据量计算出需要采样的行数，采样的行数由以下公式确定：

其中n为表的大小，k为histogram的桶数量，f为相对误差的置信区间，为置信度。当优化器根据合适的常数计算出采样行数之后，会使用输入的行构建histogram来计算NULL值的比例。随后，优化器会根据采样的数据计算列的基数。在IMCI中，首先会根据上述公式计算出采样的行数，随后通过采样率选择不同的基数估计公式，尽可能减少基数估计的误差。这类公式通常都要求采样是均匀的随机采样，但在列存储上，通常不会以page为单位存储数据。以IMCI为例，通常64K行会经过压缩后一并存储。如果读取一行数据，则需要从磁盘中读取该行对应的整个数据块并解压，读放大非常严重。为了解决这个问题，IMCI选择按照数据块采样以减少读放大，同时使用COLLAPSE算法对distinct value的计算公式做了修正。即如果有多个相同的值出现在同一个block中，按只出现一次计算，因为上文的估计公式都很大程度上取决于，通过减少数据局部性的影响，修正了基于均匀随机采样的估计误差。

IMCI中算子如何利用统计信息估计行数

实际上真正需要估计的算子只有filter、join和groupby三个，其他的算子（例如排序）通常输出仅和输入行数有关。通过histogram，可以有效地估计出类似a > 10 AND a < 100这样的谓词的选择率，同时也可以通过histogram的join计算出equal join与range join的选择率。可以使用列上的基数估计group by输出的group数量，以及在部分histogram不可用的情况下辅助估计等值谓词与equal join的选择率。例如Selectivity(a = 1) = 1 / COUNT(DISTINCT a)，unique key和foreign key则可以在计算equal join时对结果进行修正，例如SQL语句：

SELECT COUNT(*)
FROM t1, t2
WHERE t1.a = t2.a;

其中，t1.a是t1上的unique key，且t1.a是t2.a的外键，对于t2中的每一行，t1中一定会有一行与之匹配，那么就可以精确地得到这个join的输出行数和t2表的大小。

多个谓词关联的问题

IMCI中做了数据列之间有关联性的假设，计算多个谓词之间的选择率时，采用指数回退算法。即先按照各个谓词的选择率排序，之后按照如下公式计算选择率：

该算法在基于现实数据的大部分数据集中能有效地减少估计误差。

优化效果评估

在TPCH 1 TB数据集上测试开启/关闭IMCI查询优化的性能。如下图所示：

由上图可以看出，对于Q8和Q9的多表join，开启IMCI查询优化之后，因为选择了更好的查询计划，执行效率明显提高。

在用户场景workload中，未开启查询优化时，join按照的方式执行，下图中d、e表的join（橙色的部分）处理的数据量很大，整个查询60%以上的时间都用于处理这部分大表join。查询效果图如下：

开启查询优化后的效果图如下：

开启查询优化后，join顺序变为了，d与e的大表join被消除，执行时间减少了50%以上。