御财宝：浅析SQL代数优化

1.代数优化

代数优化是对查询进行等价交换，以减少执行的开销。所谓等价是指变换后的关系代数表达式与变换前的关系代数表达式所得到的结果是相同的。

（1）等价变化规则

将一个关系代数表达式转换为另一个等价的能更有效执行的表达式。

尽可能先做选择和投影操作，再做连接操作。

在连接时，先做小关系之间的连接，再做大关系的连接。

1）多重选择（σ）

2）选择（σ）的交换律

3）多重投影（∏）

4）选择（σ）与投影（∏）的交换

5）连接和笛卡尔积（x）的交换律

6）并（∪）和交（∩）运算的交换律

R ∪ S = S ∪ R

R ∩ S = S ∩ R

7）选择（σ）和连接的交换律

8）投影（∏）和连接的分配律

9）选择与集合并、交、差运算的分配律

10）投影（∏）与并运算的分配律

11）连接和笛卡尔积的结合律

12）并（∪）和交（∩）的结合律

（2）启发式规则

1）选择运算应尽可能先做；

2）在执行连接前对关系进行适当地预处理；

3）投影运算和选择运算同时进行；

4）投影同其前或其后的双目运算（并、交、差）结合起来；

5）将某些选择运算和在其前面执行的笛卡尔积转变成为连接运算；

6）将投影运算提前做（但要保留用于连接的属性）；

7）找出公共子表达式。

举例：查询选修了2号课程的学生的姓名

优化的过程：

（1）转换为初始关系代数表达式（未经优化过的）：

（2）利用转换规则进行优化

①用规则1将选择操作的连接操作部分分解到各个选择操作中，使尽可能先执行选择操作

②将笛卡尔积操作替换为等值连接操作

③用规则4和规则6对Student进行投影操作

2.物理优化

（1）选择操作的优化

1）对于小关系，不必考虑其他存取路径，直接用顺序扫描；

2）如果无索引或散列等存取路径可用，或估计选择的元组数在关系中占有较大的比例（例如大于15%），且有关属性无聚集索引，则引用顺序扫描；

3）对于非主键的等值条件查询，要估计选择的元组数在关系中所占的比例。如果比例较小（例如比例小于15%），可用非聚集索引，否则只能用聚集索引或顺序扫描；

4）对于范围条件查询，一般先通过索引找到范围的边界，再通过索引的有序集沿相应的方向进行搜集；

5）对于用and连接的合取选择条件，若有相应的多属性索引，则应先采用多属性索引；

6）对于用or连接的析取选择条件，还没有好的优化方法，只能按其中各个条件分别选出一个元组集，然后再计算这些元组的并集；

7）有些选择操作只要访问索引就可以获得结果。

（2）连接操作的优化

1）如果两个关系都已按连接属性排序，则优先选用排序归并法；

2）如果两个关系中有一个关系在连接属性有索引（特别是聚集索引）或散列，则可以将另一个关系作为外关系，顺序扫描，并利用内关系上的索引或散列寻找与之匹配的元组，以代替多变扫描；

3）如果应用上述两个规则条件都不具备，且两个关系都比较小，则可以应用嵌套循环法；

4）如果规则1、2、3都不适用，则可以选用散列连接法。

（3）投影操作的优化

投影操作一般与选择、连接等操作同时进行，不需要附件的I/O开销。如果投影的属性集中不包含主键，则投影结果中可能出现重复元组。消除重复元组是比较费时的操作，一般需要将投影结果按其所有属性排序，使重复元组连续存放，以便于发现重复元组。散列也是消除重复元组的一个可行的方法。