优化器-RBO 的规则转化

1.RBO 背景介绍

RBO(Rule-Based Optimization,基于规则的优化器)有着一套严格的使用规则,按照 RBO 去写 SQL 语句,无论数据表中的内容怎样,也不会影响到你的“执行计划”。

换言之 RBO 对数据不“敏感”,它根据指定的优先顺序规则,对指定的表进行执行计划的选择。比如在规则中,索引的优先级大于全表扫描。RBO 是根据可用的访问路径以及访问路径等级来选择执行计划,在 RBO 中,SQL 的写法往往会影响执行计划。

2.Optgen 介绍

Optgen 是一种域细节语言 (DSL),它提供了一种直观的语法来定义、匹配、替换目标表达式树中的节点,优化器规则的编写便是基于这种语言。

代码中存在这样的模块:将 DSL 语言转化为真实的 go 语言(文件后缀 og.go),以便优化器调用。模块入口在 pkg/sql/opt/optgen/cmd/optgen/main.go 中的 func main(),这里暂不涉及,以下介绍中此模块简称“代码生成模块”。

3.RBO 规则介绍

RBO 涉及的规则定义在 kaiwu/pkg/sql/opt/norm/rules/*.opt 中。

1.关系代数的 9 种操作

关系代数中包括了:并、交、差、乘、选择、投影、联接、除、自然联接等操作。其中五个基本操作为并(∪)、差(-)、笛卡尔积(×)、投影(π)、选择(σ)。

2.关系代数表达式

由关系代数运算经有限次复合而成的式子称为关系代数表达式,这种表达式的运算结果仍然是一个关系,可以用关系代数表达式表示对数据库的查询和更新操作。

3.关系代数表达式的转换

若两个关系表达式在每一个有效数据实例中都会产生相同的结果集,则可以称他们是等价的(元组的顺利是无关紧要的,而且不能说明任何表达式更优于其他表达式)。合取选择运算可以分解为单个选择运算,称为选择运算的级联: 

选择运算具有交换律: 

投影在合理的情况下,只有最后一个有效:

选择操作可与笛卡尔积以及连接相结合:

 连接操作满足交换律:

自然连接满足结合律:

4.RBO 转化实例

语句如下:
select course_id, title from course;
select * from teaches join ① on teaches.course_id = ① .course_id;
select * from instructor join ② on Instructor.ID = ② .ID;
select name, title from ③ where dept_name = Music and year = 2009;执行 ④ 语句,转换前的表达式树和转换后的表达式树如下: 

在这次转换工程中,使用了谓词下推,结合律,转换后的表达式树一定优于前面的表达式树,这就称为 RBO,基于规则的转换。

5.RBO 基本规则

(1)列裁剪

Select a from t where b >5;
我们可以将 t 表中的所有数据读取上来,然后根据条件过滤,然后再投影,最后拿到列(a)的数据。也可以先进行列剪裁,先把 a,b 数据读取,然后根据过滤条件进行过滤,最后输出数据。

(2)最大最小消除

Select min(ID) from t;这句话可以转换成 Select id from t order by id desc limit 1;

(3)投影消除

如果一个投影的输入和输出列是一样的,那么这个投影是无用的。

(4)谓词下推

尽量把选择的算子推到叶子节点,这样可以大大减少上面每个表达式节点的消耗。

考虑这样一个句子:Select * from t1,t2 where t1.a > 4 and t2.b >5;

如果先进行笛卡尔积在进行过滤条件时,则会产生很多不必要的元组,但是如果先过滤t1,t2 的关系,在进行笛卡尔积,那么表达式的消耗将大大减少。

在进行过滤时,尽可能精确到一个 select 算子,如若不能,则在具有过滤需要的列及时处理,比如 a.a > 5 and b.b > 10 and a.c > a.b 第一个和第二个条件都可以推到 select 算子中,在这个算子上面立即加一个 a.c > a.b 的过滤条件。

4.规则生成源代码介绍

1.生成代码模块定位,参数解释

入口函数 pkg/sql/opt/optgen/cmd/optgen/main.go 中的 func main(),如图所示:

Kaiwu/Makefile 中调用这个函数,需要输入 5 个参数 os.Args,这些参数依次如下(以探索阶段涉及的 factory.og.go 为例):

-out :输出文件标签输出文件名 :(pkg/sql/opt/xform/factory.og.go)
命令标签 :(compile/explorer/exprs/factory/ops/ rulenames)
结构定义文件 :(pkg/sql/opt/ops/*.opt)
规则源文件 :(pkg/sql/opt/norm/rules/  opt/pkg/sql/opt/xform/rules/.opt)

Makefile 代码定位如下:

2.调试建议

调式某个 opt 文件生成 factory.og.go 文件,如 norm/rules/comp.opt,可以采用如下方式:

 3.重要阶段介绍

(1)流程图中重要函数

a.  以 pkg/sql/opt/norm/rules/comp.opt 文件为例进行流程分析:run(),Parse(),parseOne()函数 

进入 Parse()函数——>parseOne():

① Parse()函数对parsed, args赋值;
② parseOne() 函数:裁剪 args a 和 b 参数,剩下 c、d、e;对 FlagSet 结构体中的 actual 赋值;
③ 将生成文件 b 参数赋值给 Flag 中的 Value。 

b. g.globResolver(source)函数是将 pkg/sql/opt/ops/*.opt 中的文件 append 到 files 文件中,并将规则文件 pkg/sql/opt/norm/rules/comp.opt 文件加入到 file 中。

c.  NewCompiler(files...)函数: 构建 Compiler 结构体,将 files 文件导入:

d.  compiler.Compile()→ Parse()→ parseRoot()→ p.scan():p.scan(): 根据返回值执行不同的操作
① WHITESPACE: 清除空白
② COMMENT: 向 Parser 中的 comment 中添加注释
③ LBRACKET:返回上层函数 parseRoot()
④ parseTags(): 解析出规则名和标准⑤  parseRule():解析出具体规则

e.  compiler.Compile()中的 compileDefines()函数:

将 defines 中的内容赋值给 Compiler→compiled→defineIndex中。将 define 中的 Tags 赋值给 unique 中。

f.  compiler.Compile()→compileRules()→ruleCompiler.compile():

将 pkg/sql/opt/ops/*.opt 文件中定义的元数据和 pkg/sql/opt/norm/rules/camp.opt 中所定义的规则相结合生成新规则,存于  ruleCompiler→compiled→Rules 中。

(2)代码流程图如下 

5.总结

以上就是 RBO 的规则转化在数据库中的功能方式,通过规则查询优化器执行一个预设的计划,在此预设规则下,大幅提升执行效率。

作者:KaiwuDB原文地址:https://segmentfault.com/a/1190000043375366

%s 个评论

要回复文章请先登录注册