SQL查询优化器

时间：2024-07-15

编辑：tance.cc

背景

通常，数据库管理系统 (DBMS) 采用通用的架构模型，划分为四个模块：传输通信、查询处理器、执行引擎和存储引擎。查询处理器由查询解析器和查询优化器组成，其中查询优化器是SQL计划树优化的关键部分。查询处理器的工作流程如图所示，查询优化过程包括两个重要阶段：

逻辑优化：关注查询语句的语义和结构，基于关系代数优化规则进行计划树等价转换，即查询重写规则优化，生成逻辑计划树(LogicalPlan)；

物理优化：注重数据存储结构和物理层面的高效执行，基于物理属性进行优化，生成物理计划树（Physical Plan）。

优化器分类

随着查询优化器技术的发展，出现了多种不同类型的优化器，包括 RBO（规则驱动优化器）、CBO（成本驱动优化器）、HBO（历史驱动优化器）和 ABO（基于人工智能的优化器）等。

目前，主流的查询优化器主要分为两类：RBO优化器和CBO优化器。通常，通用的数据库系统都至少包含这两种优化器，并结合它们来进行计划树优化。

RBO

RBO（基于规则的优化器），按照预设的固定优化规则顺序执行，以实现计划树的等价转换。这些优化规则通常是业界积累的通用准则，一般假设转换后的计划树在查询性能上优于转换前的计划树。由于只需顺序遍历优化规则，其执行效率非常高。然而，RBO也有一些局限性，即仅关注关系代数的变换，而不会考虑具体的数据分布信息。

CBO

CBO（基于成本的优化器），是一种根据代价或成本进行优化的工具。如图所示，它依赖统计信息和成本模型，计算出各个等价计划树的成本，并在搜索空间中选择成本最低的计划树作为最优计划树。

代价模型：一种用于计算计划树代价的数据模型。通过结合统计信息和计划树节点的信息，代价模型能够自下而上地计算出计划树的查询执行成本。

基数估计指的是在查询中估算表中不重复元组的数量，即集合中不同元素的个数。在成本优化器（CBO）的计算模型中，基数估计是重要的计算指标之一，用于估算字段级别的统计信息NDV（不同值的数量）。

选择率（Selectivity）是指满足特定条件的数据行数占总数据行数的比例，其取值范围在0到1之间。它常被用来估计查询条件的过滤效果。

在统计信息中，Filter过滤算子的基数估计可以理解为选择率的估计。

编程语言：txt

复制

基数 = 行数 * 选择性

CBO优化工具

优化器框架

优化器框架的实现方式主要有两种：自下而上的框架和自上而下的框架。

自底向上

从空计划树开始，从叶子节点出发，不断向上迭代生成符合预期的计划树。通过执行静态规则进行初始化优化，利用动态规划确定最佳的表连接顺序，并采用分治搜索方法处理。自底向上的框架直观且易于实现，无需穷尽搜索即可找到相对合理的执行计划。然而，仍然依赖启发式转换，增加规则复杂度，难以应用剪枝策略，也无法提前终止搜索。

示例框架包括：IBM System R、DB2、MySQL、PostgreSQL，以及大多数开源数据库管理系统。

自顶向下

从全局计划树的根节点出发，持续向下迭代，寻找符合预期的计划树。采用分支定界搜索（branch-and-bound search）遍历整个计划树，将逻辑计划树转换为物理计划树，例如：将JOIN(A,B)转换为HASH_JOIN(A,B)，并根据物理属性选择HASH_JOIN的方式。

自顶向下的框架实现较为复杂，搜索空间开销也更大，优化速度较慢。然而，与两阶段方法相比，这种统一搜索方式能产生更多的转换，从而可能带来更好的优化效果。该框架便于添加新的规则和转换规则，重点关注数据的物理特性，并且可以通过分支限界法进行大量剪枝，提前终止优化过程。它是基于关系代数等价转换和代价模型的通用查询优化器框架，目前许多数据库优化器都采用了这种框架。

三种常见的数据库系统示例包括MSSQL、Greenplum和CockroachDB。

优化器模型

优化器模型的发展经历了以下四个主要阶段：

1.启发式方法：以系统 INGRES 为代表；

2.启发式方法 + 基于成本的连接顺序选择：以系统 System R 为代表。

3.随机搜索方法：代表Postgres数据库系统；

层级搜索：例如STARBURST和Oracle这样的系统。

使用一个搜寻工具：代表系统Greenplum。

4层次搜索和5层次搜索模型，允许编写声明式规则来优化查询，实现搜索策略和数据模型的分离，规则与运算符的分离，规则与搜索策略的分离，从而实现优化器生成器。

跳转

启发式方法

利用启发式算法，通过将逻辑计划转化为物理计划的过程中遵循静态定义的规则。通常这些优化规则是根据专家经验得出的，比如当存在等值连接时，会优先选择索引扫描，前提是等值条件的字段有索引。

这个模型容易实现和调试，优化速度很快，但是决策完全取决于预先制定的规则，不能为复杂查询生成有效的计划。

2.启发式搜索和基于代价的搜索相结合。

优先采用静态定义规则进行初步优化，并使用动态规则选择多表JOIN的连接顺序。这个模型是第一个提出基于代价（COST）的查询优化器，首次实现了自底向上的搜索策略，严格区分逻辑优化和物理优化，奠定了现代优化器设计的基础。之后的Volcano和Cascades等方法都是在此基础上进行改进的。

这个模型比较容易实施，但在处理复杂的连接查询时，优化速度较慢，增加规则比较繁琐，需要考虑物理属性。

随机搜索

在20世纪80年代，学术界开始探讨随机搜索策略，利用随机性来避免局部最优解。以Postgres中的遗传算法为例，当涉及到复杂连接的关系数量超过13个时，可以通过这种方法来优化搜索空间过大的问题。

该模型适用于优化复杂情境，占用内存较少，但优化结果的质量无法保证。优化过程是一个黑箱，存在较大的不确定性和难以解释的特性。

分层搜索

分为两阶段：查询重写 + 物理优化。首先使用转换规则重写逻辑计划，之后基于代价搜索将逻辑计划转换为物理计划。在20世纪80年代被提出，是IBM原型系统STARBURST中采用的方法，是针对启发式 + 基于代价的连接搜索的优化。在优化器内不在维护规则列表，而是使用规则引擎，规则引擎可基于输入的计划树，匹配出可优化使用的规则列表，即为声明式规则(优化器生成器)。

该模型实现相对简单，查询效率较高，但难以确定规则执行顺序，由于重写转换时不考虑代价，因此重写后的计划树无法保证更优。

统一搜索

20世纪90年代提出了Cascades优化方法，将逻辑优化与物理优化在同一阶段进行统一。该方法通过自顶向下的规则迭代优化，形成搜索森林。将逻辑上等价且物理属性相同的计划树集合定义为一个组（Group）。其中，Transformation定义为逻辑算子的等价转换，Implementation则定义为将逻辑算子转换为物理算子。

每条规则都可以用一对属性来表示：（1）模式Pattern，定义规则可以应用的计划树结构；（2）替换Substitute，定义应用规则后产生的结果。

基于 Memo 哈希表动态维护搜索空间，记录已搜索过的候选方法，采用组 Group 的方式聚合计划树，利用记忆化搜索避免重复计算，通过动态规划 DP 获取最优的计划树。剪枝操作中，将当前最优计划树的成本作为上界，待评估组内最优计划树的成本作为下界，如果下界大于上界，则剪枝该组并移除 Memo 中的记录。

这个模型的扩展性很好，能够通过Memo记忆化搜索来减少重复计算，支持提前剪枝以缩小搜索范围。但当优化规则较多时，搜索时间会变长或者会卡住。

总结

本篇文章将重点探讨SQL查询优化器，包括介绍优化器的不同分类、框架及模型。虽然市面上各种数据库的优化器具体实现方式有所不同，但总体上遵循相似的架构方案：支持RBO和CBO优化、采用自顶向下的框架、主要基于统一的搜索模型的混合优化器模型。

此外，社区开源的SQL中间件Calcite拥有强大的查询优化功能，基于Cascades统一搜索模型实现。更多内容可以参考：《Calcite系列(九)：执行流程-优化器优化》。