数据库查询优化器,RBO优化规则介绍及示例
![](https://img-home.csdnimg.cn/images/20240711042549.png)
数据库查询优化器是针对于sql经过解析后生成的ast表达式树的。
目的是能够降低sql执行计算量,简化计算。
传统数据库中,查询优化是很复杂的,大体上可以分为RBO和CBO,其中CBO的收益性不确定,需要进行代价估算,依赖的数据统计会比较多。而RBO规则优化在不需要了解数据统计信息的前提下,可以明确提升sql执行计划的查询性能。
现在的数据库厂商大多使用的是RBO+CBO或者只用CBO的架构。其实只用CBO更主流一些,TIDB,PolarX都在用,只用cbo搜索空间相对更完整,优化结果更接近全局最优。可扩展性更好,对于新规则的添加更简单。
但是相对的,搜索空间会更大,查询优化过程耗时相对更长。优化结果更依赖搜索算法的好坏。而RBO的查询优化耗时更短,RBO能够带来明确收益,虽然优化结果局部最优,但与全局最优解不会相差很多(在CBO阶段优化了最耗时部分,保证最耗时的规则范围内达到最优)。
我经验有限,这里只是写一下自己了解到的RBO优化规则。这里会大量参考李海翔大佬的《数据库查询优化器的艺术》,tidb的分享文章等等。
目录
子查询优化
子查询的分类
子查询展开
常见的子查询类型优化
mysql和pg的支持项
视图重写优化
等价谓词重写
表达式优化及条件化简
单个表达式的简化
多个表达式之间的简化
pg,mysql,ck支持项
连接相关优化
1.外连接消除
外连接到内连接的转化
外连接消除
2.嵌套连接优化
3.pg,mysql,ck 连接优化
列裁剪优化
算子下推
1.谓词下推
where谓词/having谓词下推场景
join on谓词下推场景
2.TopN和Limit下推(分布式场景)
max/min消除
3.聚合下推
RBO优化框架的问题
逻辑查询优化技术(RBO)的理论基础
常见的优化规则包括:
- sql子句局部优化。比如等价谓词重写、谓词化简等。
- 子句之间关联的优化。比如外链接消除、子查询优化等。
- 局部与整体优化。比如or重写成union。
- 形式变化优化。比如通过形式变化进行嵌套连接消除。
- 语义优化。根据完整性约束,sql表达含义等信息来进行语义优化。
- 其他优化。根据一些规则对非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之类的子查询 | |
从结果集来分类 | 标量子查询 | 返回结果为单一值 |
列子查询 | 返回结果为单一列,但多行 | |
行子查询 | 返回结果为单一行,但多列 | |
表子查询 | 返回结果多行多列 |
子查询展开
常见的子查询优化技术包括:
- 子查询合并。指产生同样结果集的子查询合并成一个子查询。
- 子查询展开。后面详细说。
- 聚合子查询消除。将子查询转换为不包含聚合函数的子查询。
- 其他。利用窗口函数等来优化子查询。
最重要的是子查询展开。最为常用。实质是将某些子查询重写为多表连接的操作。可以将查询层次减少。
子查询展开有两种形式:
- 如果子查询中出现了聚集,group by,distinct语句,只能单独求解,无法拉到上层。
- 为SPJ格式的查询,则可以拉到上层。这个也是子查询展开的处理范围。
把子查询上拉,前提是上拉后展开结果不能带来多余的元组(ROW)。所以子查询展开的规则如下:
- 如果上层查询结果没有重复(唯一键,主键等)。则可以展开子查询,展开后查询的select需要添加distinct。
- 如果上层查询结果包含distinct,可以直接进行子查询展开。
- 如果内层查询结果没有重复,可以展开。
子查询展开步骤如下:
- 子查询和上层子查询的from语句合并成为一个from语句,修改相应的运行参数。
- 修改子查询的谓词符号。
- 合并子查询和上层查询的where条件。
常见的子查询类型优化
1.in子查询的优化
67658: 多谢提醒,也给你点个
liuxiaoye666: 第一句话就写错,是modeling,,。。,
studying chaofan: 谢谢
(CC.: 用例图不是结构图吗
qq_41598508: 您好,这个data buffer是什么