数据库查询优化器、RBO 优化规则简介和示例

数据库查询优化器是针对于sql经过解析后生成的ast表达式树的。

目的是能够降低sql执行计算量，简化计算。

传统数据库中，查询优化是很复杂的，大体上可以分为RBO和CBO，其中CBO的收益性不确定，需要进行代价估算，依赖的数据统计会比较多。而RBO规则优化在不需要了解数据统计信息的前提下，可以明确提升sql执行计划的查询性能。

现在的数据库厂商大多使用的是RBO+CBO或者只用CBO的架构。其实只用CBO更主流一些，TIDB,PolarX都在用，只用cbo搜索空间相对更完整，优化结果更接近全局最优。可扩展性更好，对于新规则的添加更简单。

但是相对的，搜索空间会更大，查询优化过程耗时相对更长。优化结果更依赖搜索算法的好坏。而RBO的查询优化耗时更短，RBO能够带来明确收益，虽然优化结果局部最优，但与全局最优解不会相差很多（在CBO阶段优化了最耗时部分，保证最耗时的规则范围内达到最优）。

我经验有限，这里只是写一下自己了解到的RBO优化规则。这里会大量参考李海翔大佬的《数据库查询优化器的艺术》，tidb的分享文章等等。

目录

逻辑查询优化技术（RBO）的理论基础

子查询优化

子查询的分类

子查询展开

常见的子查询类型优化

mysql和pg的支持项

视图重写优化

等价谓词重写

表达式优化及条件化简

单个表达式的简化

多个表达式之间的简化

pg，mysql，ck支持项

连接相关优化

1.外连接消除

外连接到内连接的转化

外连接消除 

2.嵌套连接优化

3.pg，mysql，ck 连接优化

列裁剪优化

算子下推

1.谓词下推

where谓词/having谓词下推场景

join on谓词下推场景

2.TopN和Limit下推（分布式场景）

max/min消除

3.聚合下推

RBO优化框架的问题

---

逻辑查询优化技术（RBO）的理论基础

常见的优化规则包括：

1. sql子句局部优化。比如等价谓词重写、谓词化简等。
2. 子句之间关联的优化。比如外链接消除、子查询优化等。
3. 局部与整体优化。比如or重写成union。
4. 形式变化优化。比如通过形式变化进行嵌套连接消除。
5. 语义优化。根据完整性约束，sql表达含义等信息来进行语义优化。
6. 其他优化。根据一些规则对非SPJ(select,project,join结合的查询)做的其他优化等。

查询优化技术的理论基础是关系代数。关系数据库基于关系代数。

• 关系模型数据结构就是关系数据库中的二维结构。
• 关系是一种对象，偏于理论。表也是，但偏于工业。
• 表中元数据通常用field或者item来表示。
• 表中行数据通常用tuple，row，record等来表示。
• 对关系进行的运算就是关系运算。运算对象，运算符，运算结果是运算的三大要素。

关系代数运算符包括4类：

• 传统集合运算符。并（union），交（intrsection），差（difference）,积。
• 专门的关系运算符。select，投影（project）,连接（join）,除（divide）。
• 辅助运算符。算数比较符和逻辑运算符。
• 关系扩展运算符。比如semi join，extend等。

基本关系运算与对应的sql表

关系代数运算符	对应sql语句
∪ (UNION)并	select * from t1 UNION select * from t2;
∩ (INTERSECTION)交	select * from t1 where t1.id in (select id from t2);
-  (DIFFERENCE)差	select * from t1 where t1.id not in (select id from t2);
× (Cartesian PRODUCT)笛卡尔积	select * from t1,t2;
π (PROJECT)投影	select id,name from t1;
σ (SELECT)选择	select * from t1 where id>10;
⋈ (JOIN)链接	select * from t1 join t2 on t1.id=t2.id;
÷ (DIVISION)除	select * from t1 where not exists (select t2.id from t2 where t2.id!=t1.id);

 

子查询优化

子查询的分类

子查询可以出现在sql中的位置如下：

子查询出现位置	对优化的影响
目标列	必须为标量子查询
from子句	不能有关联子查询。 非关联子查询可上拉到父查询。
where子句	根据数据类型和操作符不同，对子查询的格式有要求。
join on子句	join中同from条件。 on中同where条件，但是具体实现有些许不同。
group by 子句	需要和目标列关联（sql规范）。 直接写在groupby无实用意义。
having子句	同where语句。
order by子句	无实用意义

子查询的分类如下：

分类方式	子查询名称	介绍
关系对象之间的关系	关联子查询	依赖外层父查询属性值
	非关联子查询	不依赖外层父查询属性值
通过谓词分类	[not] in	in子查询
	[not] exists	exists子查询
	其他子查询	除上述外的其他子查询
语句构成复杂度	SPJ子查询	选择/投影/连接 基础语句组合的子查询
	GROUP BY子查询	SPJ + 聚合 组合的子查询
	其他子查询	包含更多其他语句，比如limit ,order by之类的子查询
从结果集来分类	标量子查询	返回结果为单一值
	列子查询	返回结果为单一列，但多行
	行子查询	返回结果为单一行，但多列
	表子查询	返回结果多行多列

子查询展开

常见的子查询优化技术包括：

• 子查询合并。指产生同样结果集的子查询合并成一个子查询。
• 子查询展开。后面详细说。
• 聚合子查询消除。将子查询转换为不包含聚合函数的子查询。
• 其他。利用窗口函数等来优化子查询。

最重要的是子查询展开。最为常用。实质是将某些子查询重写为多表连接的操作。可以将查询层次减少。

子查询展开有两种形式：

1. 如果子查询中出现了聚集，group by，distinct语句，只能单独求解，无法拉到上层。
2. 为SPJ格式的查询，则可以拉到上层。这个也是子查询展开的处理范围。

把子查询上拉，前提是上拉后展开结果不能带来多余的元组（ROW）。所以子查询展开的规则如下：

1. 如果上层查询结果没有重复（唯一键，主键等）。则可以展开子查询，展开后查询的select需要添加distinct。
2. 如果上层查询结果包含distinct，可以直接进行子查询展开。
3. 如果内层查询结果没有重复，可以展开。

子查询展开步骤如下：

1. 子查询和上层子查询的from语句合并成为一个from语句，修改相应的运行参数。
2. 修改子查询的谓词符号。
3. 合并子查询和上层查询的where条件。

常见的子查询类型优化

1.in子查询的优化

// in 类型子查询的sql形式

other_expr [not] in (select inner_expr from ... where subquery_where)

// other_expr：外层查询的表达式
// inner_expr：内层查询的表达式
// subquery_where：子查询的过滤条件

// 优化后的sql
exists(
    select 1 from ...
    where subquery_where and 
        outer_expr=inner_expr
)

 

2.ALL/ANY/SOME子查询的优化

other_expr operator ANY (subquery)
// ALL：对于子查询所有行数据进行operator操作成功

other_expr operator SOME (subquery)
// ANY：对于子查询任意行数据进行operator操作成功

other_expr operator ALL (subquery)
// SOME：同ANY，mysql中用法是相同的

一些适用的转化规则。 

转化前sql形式	转化后sql形式
= ANY (...)	IN (...)
!= ALL (...)	NOT IN (...)
!= ANY (...)	NOT IN (...)
val >= ALL (select ...)	val >= MAX(select ...)
val <= ALL (select ...)	val <= MIN(select ...)
val >= ANY (select ...)	val >= MIN(select ...)
val <= ANY (select ...)	val <= MAX(select ...)

 

3.EXISTS子查询的优化

exists本身有着“半连接”的语义。

所以在一些数据库实现中（比如pg），使用半连接来完成exists。

一些in的子查询是可以等价转换成exists格式的。

而exists格式是可以转换成semi join格式的。

// 优化前的sql
exists(
    select 1 from ...
    where subquery_where and 
        outer_expr=inner_expr
)

// 优化后
select * from outer_table 
semi join inner_table on outer_expr=inner_expr 
where subquery_where

 举几个例子来进行说明。

// 实例一：子查询条件和父查询有关联
select t1.* from t1 where exists ( select t2.id from t2 where t1.id=t2.id );

select t1.* from t1 semi join t2 on t1.id=t2.id;

// 实例二：子查询条件和子查询没有关系
select t1.* from t1 where exists ( select t2.id from t2 where t1.id=10 );

select t1.* from t1 semi join t2 on t1.id=10;//还能再优化，不过当前是优化到这一步

// 实例三：非关联子查询
select t1.* from t1 where exists ( select t2.id from t2 where t2.id=10 );

select t1.* from t1 where exists ( select t2.id from t2 where t2.id=10 );//非关联不进行优化

// 实例四：非关联子查询，且无表
select t1.* from t1 where exists ( select 10 );

select t1.* from t1 where exists ( select 10 ); //同 实例三

mysql和pg的支持项

常见的可优化的子查询类型	PostgreSQL支持优化	MySQL支持优化
IN类型	支持 可使用Hash连接、Hash半连接、嵌套循环半连接等算法进行优化	支持 相当与=ANY操作 可使用Semi-join、Materialization、EXISTS strategy三种方式对IN进行优化
NOT IN类型	不支持	支持 可使用Materialization、EXISTS strategy两种方式对IN进行优化
ALL类型	不支持	>ALL:用MAX优化 =ALL:用EXISTS strategy方式优化 <ALL:用MIN优化
ANY类型	支持 可使用嵌套循环半连接等算法进行优化	>ANY:用MIN优化 =ANY:用EXISTS strategy方式优化 <ANY:用MAX优化
SOME类型	支持 可使用嵌套循环半连接等算法进行优化	>SOME:用MIN优化 =SOME:用EXISTS strategy方式优化 <SOME:用MAX优化
EXISTS类型	支持 可优化为Hash连接、Hash半连接、嵌套循环半连接等算法实现	不支持 用子查询实现
NOT EXISTS类型	支持 可优化Hash反半连接、嵌套循环反半连接等算法实现	不支持 用子查询实现

视图重写优化

视图是基于表的一种对象。视图重写就是将对视图的引用改写为对基本表的引用。

所有的视图都可以被子查询替换，但不是所有的子查询都可以被视图替换，关联子查询就不行。

// 视图重写的例子如下：
create table t1(a int, b int);
create view v_t1 as select * from t1;

// 查询视图的语句如下：
select a from v_t1 where b>100;

// 视图消除改写后：
select a from (
    select a,b from t1
)
where b > 100;

// 优化后
select a from t1 where b > 100;

SPJ视图能够被查询优化器处理，但是比较复杂的视图处理起来就很麻烦了。

oracle提供了“复杂视图合并”，“物化视图查询重写”等方法，但是复杂视图查询技术本身还有待提高。

等价谓词重写

因为数据库执行引擎可能对某一类的谓词的处理效率更高，所以会对谓词进行等价的重写来达到更高的处理效率。

常见的等价谓词重写规则有：

谓词重写规则	重写前	重写后
LIKE 规则	// case 1 name like 'ABC%' // case 2 name like 'ABC'	// case 1 name >='ABC' and name<'ABD' // case 2 name ='ABC'
BETWEEN-AND规则	// case 1 sno BETWEEN 10 AND 20	//case 1 sno>=10 AND ano<=20
IN转OR规则	// case 1 age in (8,12,13)	//case 1 age =8 or age=12 or age=13
IN转ANY规则	// case 1 age in (8,12,13)	// case 1 age = any (8,12,13)
OR转ANY规则	// case1 age =5 or age=6 or age=7	// case 1 age = any(5,6,7)
ALL/ANY转聚合	参考ALL/ANY/SOME子查询优化规则	参考ALL/ANY/SOME子查询优化规则
NOT规则	// case 1 NOT(col_1!=2) // case 2 NOT(col_1!=col_2) // case 3 NOT(col_1=col_2) //case 4 NOT(col_1<col_2)	// case 1 col_1=2 // case 2 col_1=col_2 // case 3 col_1!=col_2 //case 4 col_1>=col_2
OR转UNION规则	// case1 select * from t1 where id>10 or  id<5	// case1 select * from t1 where id>10 union select * from t1 where id<5

 

表达式优化及条件化简

 数据过滤条件一般存在于where子句，having子句，on子句。

这些条件子句一般由多个表达式组成，可以利用等式性质进行化简。

条件化简是分为两种的，一种是多个表达式之间的简化，另一种是表达式本身的简化。

单个表达式的简化

多个表达式之间的简化

条件化简方式	化简前	化简后
having/where条件合并 （仅当having中没有聚合结果列）	select * from t1 where id>5 having name='aiky';	select * from t1 where id>5 and name='aiky';
去除表达式中冗余的括号 （多余括号会增加表达式树深度）	((a AND b) AND (c AND d))	a AND b AND c AND d
常量传递 （消除依赖，使用索引）	col_1=col_2 AND col_2=3	col_1=3 AND col_2=3
不等式变换	a>10 AND b=6 AND a>2	a>10 AND b=6
谓词传递闭包 （使用索引，提前过滤）	a > b AND b > 2	a>b AND b>2 AND a>2
消除死码	0>1 OR a=5	a=5
合取项只要有一个为假，即整个表达式为假	0>1 AND s1=5	false
AND操作符交换	a>b AND b>2 AND a>2	b>2 AND a>2 AND a>b

pg，mysql，ck支持项

条件简化规则	Postgresql	mysql	clickhouse
把HAVING子句并入WHERE子句	支持	支持	支持
去除表达式中冗余的括号	支持	支持	不支持
常量传递	支持	支持	不支持
消除死码	支持	支持	不支持
表达式计算	支持	不支持	不支持
等式变换	不支持	不支持	不支持
不等式变换	不支持	不支持	不支持
谓词传递闭包	不支持	不支持	不支持
合取项只要有一个为假，即整个表达式为假	支持	支持	支持
AND操作符交换	支持	支持	支持

 

连接相关优化

1.外连接消除

外连接指left join，right join，full join。

查询重写可以在满足一定条件下将外连接转换为内联接。转换的意义如下：

1. 外连接的执行操作和时间多于内连接
2. 使用内连接更加灵活多变
3. 使用内连接在一些连接算法下可以减少循环次数

外连接到内连接的转化

总结下来就是：当过滤条件中满足内表列的“空值拒绝”，就可以转为内联接。

// 1. 某个谓词的表达式用NULL值计算后会得到False或NULL。

select * from t1 left join t2 on t1.id = t2.id where t2.id is not null;
select * from t1 left join t2 on t1.id = t2.id where t2.value > 3;

// 2. 多个谓词用AND连接，其中一个能够过滤NULL。

select * from t1 left join t2 on t1.id = t2.id where t2.value > 3 and t2.id is null;

// 3. 多个谓词用OR连接，每一个都能够过滤NULL。

select * from t1 left join t2 on t1.id = t2.id where t2.id is not null or t2.value > 3;

外连接消除 

优化原理：

如果去掉外连接，对最后的查询结果没有影响，那么就可以进行外连接消除。

对于外连接，外表的每一行记录肯定会在连接的结果集里出现一次或多次，如果内表在连接列上满足唯一性属性，外表的每一行记录仅会在连接结果中出现一次。如果join的上层算子只需要外表列的数据，那么join将会成为无用操作，这种情况下的外连接结果集等价于直接读取外表列的数据。

若内表在连接列上不满足唯一性属性，外表的行可能在内表找到多行匹配，则外表的一行会在连接结果中出现多次，当上层算子只需要 outer plan 的去重后结果时，外连接同样也可以被消除。

使用场景：

外连接查询中同时满足以下条件1、2或1、3可应用外连接消除优化规则：

1. join算子节点的父亲算子只会用join算子输出的外表列进行计算。

2. join算子的连接条件中的内表列满足唯一性属性。

3. join算子的父亲算子会对输入的记录去重。

保证join算子的父亲算子只会用到join中外表的去重后结果。

举例：

// case 1
select t1.a from t1 left join t2 on t1.b = t2.pk;
// case 1 优化
select a from t1;

// case 2
select distinct(t1.a) from t1 left join t2 on t1.b = t2.b;
// case 2 优化
select distinct(a) from t1;

 

2.嵌套连接优化

嵌套连接指，当执行连接操作的次序不是从左到右逐个进行，就说明存在嵌套连接。

嵌套链接情况举例： 

// case 1, 使用外连接
select * from t1 left join (
    t2 left join t3 on t2.id=t3.id
) on t1.a=t2.a 
where t1.a>1

// case 2, 使用内连接
select * from t1 join (
    t2 left join t3 on t2.id=t3.id
) on t1.a=t2.a 
where t1.a>1

如果连接表达式中只有内连接，那么可以去掉括号，顺序可以颠倒。

如果是外连接，那么不能去掉括号，但是可能可以做向内连接的转换。

3.pg，mysql，ck 连接优化

连接类型	连接语法格式	PostgreSQL	MySQL	ClickHouse
内连接	[INNER | CROSS] JOIN	满足连接交换律，可互换表位置，优化点在于多表连接时对表的连接次序的选择	多表连接的次序由表的数量决定，即使是内连接，也不可互换表的位置	不支持优化
左外连接	LEFT [OUTER] JOIN	内表的条件列满足空值拒绝，可优化为内连接	同PostgreSQL	不支持优化
右外连接	RIGHT [OUTER] JOIN	转为左外连接，再进行优化	同PostgreSQL	不支持优化
全外连接	FULL [OUTER] JOIN	外表的条件列满足空值拒绝，向左外连接转化 内表的条件列满足空值拒绝，向右外连接转化（右外连接又转化为左外连接的形式） 外表、内表的条件列都满足空值拒绝，向内连接转化	不支持优化	不支持优化
半连接	EXISTS	支持优化（如用Hash Join优化）	不支持优化	不支持优化
反半连接	NOT EXISTS	支持优化（如用Hash Anti Join优化）	不支持优化	不支持优化

 

列裁剪优化

主要影响的算子： Projection，Aggregation，DataSource

做列裁剪时，依据执行节点结构自底向上，看它父节点要哪些列，然后它自己的条件里面要用到哪些列。仅保留需要用到的列。

对于用不上的列，不需要读取对应的数据，减少IO资源的浪费。

// 假设表t有 a, b, c, d四列，查询：

select a from t where b < 5;

// 只用到了a, b两列的数据，读数据时只需要读取a, b两列即可。 

算子下推

查询优化器的目的本质，就是尽可能提前的过滤掉数据，越早过滤数据，越能减少计算耗费的cpu，数据占用的内存量。

1.谓词下推

可以理解为将 where条件/having 条件/ on条件 尽可能的放在执行器最前面的位置。

where谓词/having谓词下推场景

谓词条件	inner join		left join		right join		full join
	left table	right table	left table	right table	left table	right table	left table	right table
where predicate	√	√	√	×	×	√	×	×

以left join的为例对不能下推的情况说明：

对于left join若找不到匹配的行，会对右表列进行补null，若对右表的条件谓词进行下推，那么右表过滤后再join可能会出现很多需要补null的行，这些行没有了过滤条件会被全部返回。但是下推的这个where条件没下推之前实际上是可以把null过滤掉的，这样就出现了优化前后结果集数据不一致的情况。其它join方式同理。

join on谓词下推场景

条件	inner join		left join		right join		full join
	left table	right table	left table	right table	left table	right table	left table	right table
join predicate	√	√	×	√	√	×	×	×

以left join的为例对不能下推的情况说明：

由于左表是保留表，因此结果集包含了左表的全部行，若将左表条件进行下推，则会提前过滤左表的表分数据，再进行join会造成下推前后结果集不一致。 

2.TopN和Limit下推（分布式场景）

查询计划树中，limit子句对应Limit算子节点，order by子句对应sort算子节点，将相邻的limit和sort算子组合为TopN算子节点，表示按照某个排序规则提取前N项记录。

单独的limit算子等价于一个排序规则为空的TopN算子节点。

优化原理：

和谓词下推类似，将查询计划树中的TopN计算尽可能下推至数据源，尽早完成过滤数据，从而减少数据的传输和计算开销。

使用场景：

• 非join场景

查询只涉及单表，可直接将TopN算子下推至存储层对数据进行过滤。

• join场景

当join方式为outer join，且排序规则仅依赖于外表中的列，可以将TopN算子下推至对应数据源。因为外连接会保留外表所有的行，每行数据至少出现一次，排序仅依赖外表的内容时，提前排序再join并不会改变结果集。

其它join场景无法进行TopN下推，因为其它join并不能保证排序列对应的表中的所有行都会被保留在join结果集中，若进行下推可能会造成结果集的缺失。

使用方式：

将TopN下推至存储层，先在存储层做局部sort，然后将所有的局部结果汇总，在计算层做合并进行二次sort。

当排序的列是对应表的主键时，可以直接按顺序读取数据，TopN算子将简化为Limit算子。

能够TopN下推的join场景：

select * from t1 left join t2 on t1.id = t2.id oder by t1.a limit 10;

max/min消除

优化原理：

将 max/min 聚合函数转换为 TopN 算子，从而能够有效地利用索引进行查询。

使用场景：

• 只有一个max或min函数，max/min的聚合函数参数中的列有索引能够保序，且没有group by 语句。
• 存在多个max或min函数，每个max/min的聚合函数参数中的列都有索引能够保序，并且没有group by语句。

使用方式：

// 只有一个max/min函数
// 将查询进行等价改写，以TopN算子对max/min进行替换来避免全表扫描：
select min(id) from t;

select id from t order by id desc limit 1;


// 多个max/min函数
select max(a) - min(a) from t

select max_a - min_a from (
    select a as max_a from t order by a asc limit 1
) t1, (
    select a as min_a from t order by a desc limit 1
) t2;

// 如果a列没有可以保序的索引，则这个规则不会被应用。

3.聚合下推

单机情况下：

考虑多表join时，带有聚合函数的情况。

// 优化前
select LT.id, sum(LT.salary) 
from left_table_agg LT join right_table_agg RT 
on LT.id = RT.id 
group by LT.id;

// 优化后
select LT.id, sum(LT.salary) 
from (
    select id as id , sum(salary) as salary from left_table_agg group by id
) LT join right_table_agg RT 
on LT.id = RT.id 
group LT.id; 

分布式情况下：

提前过滤数据，减少网络传输。

 

聚合方式	下推方式
max	上层聚合：max       下推聚合：max
min	上层聚合：min       下推聚合：min
sum	上层聚合：sum       下推聚合：sum
count	上层聚合：sum       下推聚合：count
avg	上层聚合：sum/count       下推聚合：sum, count

 

RBO优化框架的问题

随着逻辑优化规则的不断增多，优化框架可能存在的几个问题：

1. 优化器要求每个逻辑优化规则一定是有收益的，转换后得到的逻辑执行计划必须比转换前的更优（例如谓词下推），但是某些优化规则只在特定场景下有收益，由于需要考虑特定场景的某些条件，这种优化规则很难添加到逻辑执行优化的优化器中，导致优化器在那些特定场景下的执行计划不够优。
2. 不管什么样的 SQL，在逻辑优化阶段，所有的优化规则都按照同一个固定的顺序依次去看是否能够作用于当前的逻辑执行计划，例如最先执行的规则总是列剪裁。逻辑优化规则之间的顺序需要经过有经验的优化器老手精心的安排，在添加优化规则的时候都需要小心翼翼地安排这个顺序，添加一个优化规则需要了解其他所有优化规则，门槛较高。
3. 逻辑优化阶段，每个规则至多只会在被顺序遍历到的时候执行一次，但实际场景中，往往存在之前某个已经执行过的优化规则可以再次被执行的情况。我们以一个例子来说明，对于这个简单的 SQL：select b from t where a > 1，其中 a 是 int 类型的主键，我们最终会产生这样一个物理执行计划：

       TableScan(table: t, range:(1, inf]) -> TableReader(a, b) -> Projection(b)
   

   在 TableReader 的 Schema 中包含了 a b 两列，也就是说 会从T中读取两列内容，但最终自己却只需要其中第一列。这个问题背后的原因是：优化器先进行列裁剪，再谓词下推，但是谓词下推之后，有可能列剪裁可以再次生效，而这个可能生效的列剪裁在现在优化器中无法被执行了，导致从T多读取了一列数据，增加了 SQL 执行时的网络 IO 使用量。

主要就这些了，之后我再调研一下更普遍的查询优化器，写一下cbo的实现吧，从数据库厂商们的查询优化器走向来看，cbo更主流一点。