优化器 -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 的规则转化在数据库中的功能方式，通过规则查询优化器执行一个预设的计划，在此预设规则下，大幅提升执行效率。