4.3 逻辑优化：抽象语法树到逻辑计划树（选做）
查询优化器在逻辑优化阶段主要解决的问题是：如何找出SQL语句的等价变换形式，使SQL执行更高效；一般可以使用代数优化的方式完成这一过程。代数优化是通过关系代数中一些等价变化的方式调整原始的抽象语法树结构，使其变化为执行过程上更为简洁高效的逻辑计划树的形式。主要是一些基于规则的固定转化模式，逻辑优化过程基于如下的经验规则：
- 尽早进行选择运算，这样可以尽早降低运算数据的规模
- 合并同表的多个选择和投影运算，减少表的扫描次数
- 合并投影运算和其他双目运算（笛卡尔积，等值连接，并集差集），减少表的扫描次数
- 合并选择运算与笛卡尔积，避免直接计算笛卡尔积
- 提取公共子表达式，重复使用
基于上述的经验规则，常用的变化包括如下几类：
- 列裁剪：运算过程中仅保留必要的列，忽略其余列，降低数据传输开销。
- 谓词下推：将查询语句中的过滤表达式计算尽可能下推到距离数据源最近的地方，以尽早完成数据的过滤，进而显著地减少数据传输或计算的开销。
- 子查询合并：在语义等价条件下，多个子查询可以合并成一个子查询，这样多次表扫描，多次连接减少为单次表扫描和单次连接。
- 谓词重写：利用一些等价规则将IN、OR、LIKE、BETWEEN、AND等谓词进行等价转化。
- 条件化简：对于WHERE、HAVING等条件进行化简，例如常量传递和不等式变化等。
逻辑优化部分的代码实现需要一定编译原理的课程基础以及较高的编程能力支持，所以这一部分可能对于部分没有接触过编译原理知识的同学造成过大的负担。所以逻辑优化的内容仅作为选做内容，希望各位对于数据库系统感兴趣的同学可以自行探索并实现这一部分的内容。
Authors: