一、了解关系代数

关系代数是一种过程化查询语言。它包括一个运算的集合，这些运算以一个或两个关系为输入，产生一个新的关系作为结果。
关系代数是关系型数据库操作的理论基础，关系代数支持并、差、笛卡尔积、投影和选择等基本运算，任何一个查询都可以表示成由关系运算符组成的树，一般sql查询引擎会在解析优化中会先将 SQL 转换成关系表达式（relational expression），然后通过规则匹配（rules match）进行相应的优化，优化会有一个成本（cost）模型为参考。

名称	英文	符号	说明
选择	select	σ	类似于 SQL 中的 where
投影	project	Π	类似于 SQL 中的 select
并	union	∪	类似于 SQL 中的 union
集合差	set-difference	-	SQL中没有对应的操作符
笛卡儿积	Cartesian-product	×	类似于 SQL 中不带 on 条件的 inner join
重命名	rename	ρ	类似于 SQL 中的 as
集合交	intersection	∩	SQL中没有对应的操作符
自然连接	natural join	⋈	类似于 SQL 中的 inner join
赋值	assignment	←

二、查询优化

2-1 查询处理过程

查询处理过程.png

1.解析 SQL， 语法分析、词法分析，把 SQL 转换成为 AST （抽象语法树），解析工具包括JavaCC、ANRLR；
2.查询检查，根据数据库的元数据信息进行语法验证；包括语义检查、视图转换、安全检查、完整性检查等；
3.逻辑计划优化，优化器的核心，根据前面生成的逻辑计划按照相应的规则（Rule）进行优化；
4.物理执行，生成物理计划，物理执行计划执行。

2-2 查询优化模型

2-2-1有一个例子

查询sql
select u.id as user_id, u.name as user_name, j.company as user_company, u.age as user_age from users u join jobs j on u.name=j.name where u.age > 30 and j.id>10 order by user_id

解析和优化（谓词下推）

谓词下推.png

这个sql 中有一个明显可以优化的地方就是过滤条件的下压（push down），在进行 join 操作前，先进行 filter 操作，这样的话就不需要在 join 时进行全量 join，减少参与 join 的数据量。

2-2-2 代数优化

2-2-2-1 代数等价变换

总结起来就是: "(连接类的)交换律, 结合律; (投影和选择类的)串接律, (这两大类相互之间)分配率"
1.E1 X E2 = E2 X E1, (E1 X E2) X E3 = E1 X (E2 X E3)做笛卡尔积, 多个表做连接是满足交换律和结合律的
2.投影和选择的串接定律
多层的投影可以取小的那个
多层的选择可以取交集(其实也是那个范围比较小的), 这样能够把多次选择多次表的扫描, 改成一次.
3.选择与投影交换律: 选择和投影的顺序可以随意改变
4.选择与笛卡尔积, 并, 自然连接, 差的分配律: 处在后面的选择, 可以与处在前面的二目运算顺序进行调整, 使得对相应的表先实施选择, 再实现连接等二目运算. 这个非常重要, 是先选择后进行二目运算的依据, 又名"选择提前".
5.选择与笛卡尔积, 并的分配率: 可以先投影, 也可以先进行二目运算

2-2-2-2 经验性优化五大策略

其实就是"选择, 合并, 视图"
1.选择运算尽可能先做。 这样往往使得执行代价减少了几个数量级, 主要的原理就是选择运算能够大大降低参与连接的元组的行数, 使得连接生成的A•B结果也大大被缩小.
2.把选择和投影运算同时进行, 如果有若干投影和选择运算, 并且他们都是针对同一个表, 那么可以在扫描这个表的时候同时完成这些所有的运算, 以此避免重复扫描这张表.
3.把投影与其前或者后的双目运算(笛卡尔积, 等值连接, 并集, 差集)结合起来, 也就是说, 没有必要为了选择出几个字段而单独再重新扫描全表.
4.把某些选择和在它前面要执行的笛卡尔积结合起来成为一个连接运算(比如变成等值连接), 这是因为连接运算要比同样情形下的笛卡尔积节省很多时间.
5.找出公共子表达式(一次计算, 多次使用). 比如很多的查询都基于某个公共部分, 那么可以定义一个公共子表达式, 然后先计算一次公共子表达式, 然后把它存盘, 供其他大量的表达式来使用. 我们定义视图其实就是在实践这种策略.

2-2-3 物理优化

常用的两个优化模型：RBO（Rule-Based Optimizer） 和 CBO（Cost-Based Optimizer）
1.RBO
启发式优化器（heuristic implementation ），它简单地按 AST 树结构匹配所有已知规则，直到没有规则能够匹配为止；
对于小的表, 直接全表扫描, 即使列上有索引.
对于大的表, 如果是选择条件涉及主键, 那么使用主键索引(MySQL等主流关系数据库都会对主键建立索引);
如果不是涉及主键, 那么如果是等值查询, 列上有索引, 就使用索引; 如果非等值查询, 而是范围值查询, 那么范围<=10%用索引, 范围比较大的, 直接全表扫描.
And 和 OR: AND连接的, 优先考虑使用索引; OR连接的, 优先考虑使用顺序扫描, 毕竟OR可能性非常多.
连接操作: 如果两个表都按照连接属性排序, 用sort-merge算法, 如果其中一个表在连接属性上有索引,采用索引连接算法; 如果啥都没有, 对小的表建立哈希表, 使用hash join方法; 或者使用基本的嵌套循环, 不过外层循环(i循环)使用小表, 这样能稍微减小代价.

2.CBO
火山式优化器（VolcanoPlanner）成本优化器也会匹配并应用规则，当整棵树的成本降低趋于稳定后，优化完成，成本优化器依赖于比较准确的成本估算。