CMU-15-445笔记(十二)

Query Optimization

Pipleline

1. 首先用户写的SQL query经过SQL Rewriter重写优化（这个模块实现的比较少）
2. 经过语法解析器分解成抽象语法树传给Binder
3. Binder通过查询System Catalog将SQL查询中的命名对象转换为内部的标识符
4. Tree Rewirer有静态的规则，将语法树进行优化
5. 然后传入优化器中，优化器会有一些动态的优化，可以进行cost的比较，从而选取最优的方案
6. 最后形成Physical Plan 执行

Relational Algebra(代数) Equivalences(等价)

如果两个关系代数产生的tuples set（顺序任意）是一样的，那么这两个关系代数就是等价的，所以query rewriting就是寻找一个高效的，等价关系代数替代用户所写的关系代数。

Selections

对于Selections来说

• 越早执行filters越好
• 将复杂的predicate push down（大概意思就是将它往语法树下方一移动）
  

Join

Join是符合交换律和结合律的

n-way join不同的顺序有 $4^n$种， 也就是卡特兰数

Projections

Projections越早执行越好，这样可以减少无用信息的来回复制，Projections也可以先将除了所需数据之外的数据丢弃。