数据库 - 物理优化

物理优化

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

基于启发式规则的存取路径选择优化

一、 选择操作的启发式规则:

1. 对于小关系，使用全表顺序扫描，即使选择列上有索引
   对于大关系，启发式规则有：

2. 对于选择条件是主码＝值的查询
   查询结果最多是一个元组，可以选择主码索引
   一般的RDBMS会自动建立主码索引。

3. 对于选择条件是非主属性＝值的查询，并且选择列上有索引
   要估算查询结果的元组数目
   如果比例较小(<10%)可以使用索引扫描方法
   否则还是使用全表顺序扫描

4. 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引
   要估算查询结果的元组数目
   如果比例较小(<10%)可以使用索引扫描方法
   否则还是使用全表顺序扫描

5. 对于用AND连接的合取选择条件
   如果有涉及这些属性的组合索引
   优先采用组合索引扫描方法
   如果某些属性上有一般的索引
   则可以用［例1-C4］中介绍的索引扫描方法
   否则使用全表顺序扫描。

6. 对于用OR连接的析取选择条件，一般使用全表顺序扫描

二、 连接操作的启发式规则：
1. 如果2个表都已经按照连接属性排序
选用排序-合并方法
2. 如果一个表在连接属性上有索引
选用索引连接方法
3. 如果上面2个规则都不适用，其中一个表较小
选用Hash join方法

. 可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数(b)较少的表，作为外表(外循环的表) 。
理由：
设连接表R与S分别占用的块数为Br与Bs
连接操作使用的内存缓冲区块数为K
分配K-1块给外表
如果R为外表，则嵌套循环法存取的块数为:
Br+ (Br/(K-1)) *Bs
显然应该选块数小的表作为外表

一、 统计信息
基于代价的优化方法要计算各种操作算法的执行代价，与数据库的状态密切相关

基于代价的优化

数据字典中存储的优化器需要的统计信息：
1. 对每个基本表
该表的元组总数(N)
元组长度(l)
占用的块数(B)
占用的溢出块数(BO)

2. 对基表的每个列

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

二、 代价估算示例

全表扫描算法的代价估算公式

如果基本表大小为B块，全表扫描算法的代价 cost＝B

如果选择条件是码＝值，那么平均搜索代价 cost＝B/2

1. 索引扫描算法的代价估算公式
   如果选择条件是码＝值
   如［例1-C2］，则采用该表的主索引
   若为B+树，层数为L，需要存取B+树中从根结点到叶结点L块，再加上基本表中该元组所在的那一块，所以cost=L+1
   如果选择条件涉及非码属性
   如［例1-C3］，若为B+树索引，选择条件是相等比较，S是索引的选择基数(有S个元组满足条件)
   最坏的情况下，满足条件的元组可能会保存在不同的块上，此时，cost=L+S

如果比较条件是＞，＞＝，＜，＜＝操作
假设有一半的元组满足条件就要存取一半的叶结点
通过索引访问一半的表存储块cost=L+Y/2+B/2

1. 嵌套循环连接算法的代价估算公式
   9.4.1中已经讨论过了嵌套循环连接算法的代价cost＝Br+(Br/(K-1))*Bs
   如果需要把连接结果写回磁盘，
   cost＝Br+(Br/(K-1))*Bs +(Frs*Nr*Ns)/Mrs
   其中Frs为连接选择性(join selectivity)，表示连接结果元组数的比例
   Mrs是存放连接结果的块因子，表示每块中可以存放的结果元组数目。

2. 排序-合并连接算法的代价估算公式
   如果连接表已经按照连接属性排好序，则cost＝Br+Bs+(Frs*Nr*Ns)/Mrs。
   如果必须对文件排序
   需要在代价函数中加上排序的代价
   对于包含B个块的文件排序的代价大约是(2*B)+(2*B*log2B)

比较复杂的查询，尤其是涉及连接和嵌套的查询
不要把优化的任务全部放在RDBMS上
应该找出RDBMS的优化规律，以写出适合RDBMS自动优化的SQL语句
了解具体的查询计划表示，分析查询的实际执行策略