一． 查询优化

查询优化一般可以分为代数优化和物理优化。代数优化是指代数表达式的优化，物理优化是指通过存取路径和底层操作算法的选择进行的优化。

1. 代数优化规则

代数优化主要用途是在于可以改写对应的SQL语句的情况下，构造慢SQL语句的查询树，利用等价变化规则，得出最优查询树，转化关系代数表达式为SQL语句，得出最优的SQL语句来提高SQL的查询效率。
等价变换规则如下：

1. 交换律（F为连接条件）

2. 结合律

3. 投影串接律（An和Bm为属性字段）

4. 选择串接律（F为选择条件）

5. 选择投影交换

6. 选择笛卡儿积交换

7. 选择与并交换

8. 选择与差交换

9. 投影与笛卡儿积交换

10. 投影与并交换

（1） 选择运算尽可能先做，因为选择运算一般使中间结果大大变小
（2） 把投影运算和选择运算同时进行，如有若干投影和选择运算，并且它们都是对同一个关系操作，则可以在扫描此关系的同时完成所有这些运算以避免重复扫描关系
（3） 把投影同其前或后的双目运算结合起来
（4） 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。
（5） 找出公共子表达式

2. 代数优化步骤（举例）

从数据库中找出选修了课程名为“IS”的学生姓名
Select Cname
From Student, Course, SC
WHERE Student.Sno = SC.Sno AND SC.Cno = Course.Cno AND Student.Sdept =’IS’;

第一步构造查询树

关系代数表达式为：∏Cname(σStudent.Sdept=’IS’(Student ⋈ Course ⋈ SC))

第二步串接定律转换

第三步选择下移

第四步得出优化树

3. 物理优化

代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径，对于一个查询语句有许多存取方案，它们的执行效率不同， 仅仅进行代数优化是不够的，物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划。

4. 基于启发式规则的存取路径选择优化如下：

4.1选择操作的启发式规则:

对于小关系，使用全表顺序扫描，即使选择列上有索引
对于选择条件是主码＝值的查询
查询结果最多是一个元组，可以选择主码索引。
一般的RDBMS会自动建立主码索引。（达梦数据库默认rowid）
对于选择条件是非主属性＝值的查询，并且选择列上有索引
要估算查询结果的元组数目。
如果比例较小(<10%)可以使用索引扫描方法。
否则还是使用全表顺序扫描。
对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引
要估算查询结果的元组数目。
如果比例较小(<10%)可以使用索引扫描方法。
否则还是使用全表顺序扫描。
对于用AND连接的合取选择条件
如果有涉及这些属性的组合索引。
优先采用组合索引扫描方法。
如果某些属性上有一般的索引。
则可以用合适的索引扫描方法。
否则使用全表顺序扫描。
对于用OR连接的析取选择条件，一般使用全表顺序扫描

4.2连接操作的启发式规则

1. 如果2个表都已经按照连接属性排序

选用排序-合并方法（达梦数据库是归并连接hint use_merge）

2. 如果一个表在连接属性上有索引

选用索引连接方法（USE_NL_WITH_INDEX）

3. 如果上面2个规则都不适用，其中一个表较小

选用Hash join方法
可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的页数(b)较少的表，作为驱动表(外循环的表) 。

举例4.2：

设连接表R与S分别占用的页数为Br与Bs
连接操作使用的内存缓冲区页数为K
分配K-1页给外表
如果R为外表，则嵌套循环法存取的页数为:
Br+ (Br/(K-1)) *Bs
显然应该选页数小的表作为外表

5. 基于代价的优化方法

基于代价的优化要计算各种操作算法的执行代价，与数据库的状态密切相关
数据字典中存储的优化器需要的统计信息：

1. 对每个基本表

该表的元组总数(N)，元组长度(l)，占用的页数(B)，占用的溢出页数(BO)

2. 对基表的每个列

该列不同值的个数(m)，选择率(f)
如果不同值的分布是均匀的，f＝1/m
如果不同值的分布不均匀，则每个值的选择率＝具有该值的元组数/N
该列最大值
该列最小值
该列上是否已经建立了索引
索引类型(B+树索引、Hash索引、聚集索引)

3. 对索引(如B+树索引)

索引的层数(L)
不同索引值的个数
索引的选择基数S(有S个元组具有某个索引值)
索引的叶结点数(Y)

4. 代价估算示例

全表扫描算法的代价估算公式
如果基本表大小为B页，全表扫描算法的代价 cost＝B
如果选择条件是码＝值，那么平均搜索代价 cost＝B/2
索引扫描算法的代价估算公式
如果选择条件是码＝值
若为B+树，层数为L，需要存取B+树中从根结点到叶结点L页，再加上基本表中该元组所在的那一页，所以cost=L+1
如果选择条件涉及非主码属性
若为B+树索引，选择条件是相等比较，S是索引的选择基数(有S个元组满足条件)
最坏的情况下，满足条件的元组可能会保存在不同的页上，此时，cost=L+S
如果比较条件是＞，＞＝，＜，＜＝操作
假设有一半的元组满足条件就要存取一半的叶结点
通过索引访问一半的表存储页cost=L+Y/2+B/2
嵌套循环连接算法的代价估算公式
如4.2例子中嵌套循环连接算法的代价cost＝Br+(Br/(K-1))Bs
如果需要把连接结果写回磁盘，
cost＝Br+(Br/(K-1))Bs +(FrsNrNs)/Mrs
其中Frs为连接选择性(join selectivity)，表示连接结果元组数的比例
Mrs是存放连接结果的块因子，表示每块中可以存放的结果元组数目。
排序-合并连接算法的代价估算公式
如果连接表已经按照连接属性排好序，则cost＝Br+Bs+(FrsNrNs)/Mrs。
如果必须对文件排序
需要在代价函数中加上排序的代价
对于包含B个块的文件排序的代价大约是(2B)+(2B*log2B)
比较复杂的查询，尤其是涉及连接和嵌套的查询
不要把优化的任务全部放在RDBMS上
应该找出RDBMS的优化规律，以写出适合RDBMS自动优化的SQL语句
了解具体的查询计划表示，分析查询的实际执行策略