SQL查询优化器

原创

Yiwenwu

修改于 2024-06-30 20:34:03

3070

修改于 2024-06-30 20:34:03

背景

一般的，数据库管理系统(DBMS)有通用的架构模型，可分为四个模块：传输通信、查询处理器、执行引擎、存储引擎。其中查询处理器包括查询解析器和查询优化器，而查询优化器是实现SQL计划树优化的核心。查询处理器的处理流程如下图所示，查询优化的执行过程包括两个关键阶段：

逻辑优化：关注查询语句的语义和结构，基于关系代数优化规则进行计划树等价转换，即查询重写规则优化，生成逻辑计划树(LogicalPlan)；
物理优化：关注数据存储结构和物理层面的高效执行，基于物理属性优化，生成物理计划树(PhysicalPlan)。

优化器分类

随着查询优化器的发展，提出不同"based"的优化器，包括 RBO(Rule-based Optimizer)、CBO(Cost-based Optimizer)、HBO(History-based Optimizer)、 ABO(AI-based Optimizer)等。

主流的查询优化器分类，一般仅分为两大类：RBO优化器和CBO优化器。目前，业界通用的数据库系统，其优化器也至少包括RBO和CBO优化器，结合两者进行计划树优化。

RBO

RBO(Rule-based Optimizer)，基于规则的优化器。顺序执行一组预设固定的优化规则进行计划树等价转换。RBO的优化规则一般是业界沉淀的通用规则，通常假设转换后的计划树的查询性能往往更优于转换前的计划树。由于仅考虑顺序遍历优化规则，其执行效率十分高效。但RBO也存在的一些问题，仅关注关系代数的变换，不会考虑具体的数据分布信息。

CBO

CBO(Cost-based Optimizer)，基于代价/成本(COST)的优化器。如下图所示，依赖统计信息和代价模型，计算出各个等价计划树的代价COST，在搜索空间中选择代价最低的计划树作为最优计划树。

代价模型：一种可以计算出计划树代价(COST)的数据模型。结合统计信息和计划树节点信息，代价模型可自底向上计算出该计划树的查询执行成本。
基数估计：基数(Cardinality)是指集合中不同元组的个数，基数估计是在查询中估算表中不重复元组的数量，是CBO中代价模型中的重要计算指标之一，字段级别的统计信息NDV(Number of Distinct Values)是基数估计的一个关键输入。
选择率：Selectivity，是满足特定条件的数据行与总数据行数的比例，取值范围从0到1。常用于估算查询条件的过滤效果。

其中，统计信息中Filter过滤算子的Cardinality基数估计，也可理解为 Selectivity 选择率估计。

Cardinality=NUM_ROWS * Selectivity

优化器框架

优化器框架的实现方式主要分为两种：自底向上框架、自顶向下框架。

自底向上

从空计划树开始，叶子节点出发，不断向上迭代生成符合预期的计划树。基于静态规则执行初始化优化，使用动态规划确定最佳的表连接顺序，并采用分治搜索方法处理。自底向上框架直观、易于实现，不需要穷尽搜索就能找到较为合理的执行计划。但没有摆脱启发式转换，添加规则繁琐，难以使用剪枝策略，无法提前停止。

示例框架：IBM System R, DB2, MySQL, Postgres, most open-source DBMS。

自顶向下

从全局计划树根节点开始，不断向下迭代查找符合预期的计划树。基于分支定界搜索(branch-and-bound search)遍历整个计划树，将逻辑计划树转换为物理计划树，例如：JOIN(A,B) → HASH_JOIN(A,B)，根据物理属性选择HASH_JOIN方式。

自顶向下框架实现比较复杂，搜索空间开销更大，优化较慢。但相较于两阶段方法，统一搜索会产生更多的转换，优化效果可能更好。易于添加新规则和转换规则，重点关注数据的物理特性，可利用分支界定进行大量剪枝，可提前终止。该框架是通用的基于关系代数等价转换和代价模型的查询优化器，目前很多数据库优化器都采用该框架实现。

示例框架：MSSQL, Greenplum, CockroachDB。

优化器模型

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

启发式方法：代表系统 INGRES；
启发式方法 + 基于代价选择连接顺序：代表系统 System R；
随机化搜索：代表系统Postgres；
分层搜索：代表系统STARBURST、Oracle；
统一搜索：代表系统Greenplum。

其中4分层搜索、5统一搜索模型，支持编写声明式规则进行查询优化，将搜索策略与数据模型分离，规则与算子分离，规则与搜索策略分离，实现优化器生成器。

1. 启发式方法

基于启发式算法，由静态定义规则实现逻辑计划到物理计划的转换。优化规则通常是专家经验沉淀的，如等值连接，如果等值条件的字段有索引，则优先使用索引扫描。

该模型易于实现与调试，优化速度快，但决策完全依赖于预定义的规则，无法为复杂查询生成好的计划。

2. 启发式 + 基于代价的连接搜索

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

该模型相对容易实现，但对于复杂的连接查询，优化时间较慢，添加规则繁琐，需要考虑物理属性。

3. 随机搜索

20世纪80年代，学术界提出了随机化的搜索策略，利用随机化策略来跳出搜索空间中的局部最优。例如，Postgres中的遗传算法，对于复杂连接的关系数(13个以上)，可以优化搜索空间过大的问题。

该模型适合优化复杂情况，内存占用较小，但优化质量无法保证，优化过程黑盒，不确定性/不可解释性较强。

4. 分层搜索

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

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

5. 统一搜索

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

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

基于Memo哈希表动态维护搜索空间，存储已经搜索过的候选方法，将计划树以组Group的方法聚合在一起，使用记忆化搜索避免重复计算，通过动态规划DP获取最优的计划树。剪枝操作将保留当前最优计划树的代价作为upperbound上界，待评估Group组内的最优计划树代价作为lowerbound下界，如果lowerbound > upperbound，则将该Group组剪枝并移除Memo。

该模型规则扩展性好，可以利用Memo记忆化搜索减少冗余计算，支持提前剪枝减少搜索范围。但优化规则较多时，搜索耗时较长或卡主。

总结

本文围绕SQL查询优化器进行展开说明，分别介绍优化器分类、优化器框架、优化器模型。市面上，很多数据库的优化器虽然实现细节不同，但整体遵循相同的架构方案：同时支持RBO和CBO优化，基于自顶向下框架实现的，以统一搜索模型为主的混合优化器模型。

另，社区开源的SQL中间件Calcite具备完善的查询优化能力，基于Cascades统一搜索模型实现，更多可参考：《Calcite系列(九)：执行流程-优化器优化》