（P53-56）物理层查询优化

文章目录

1.为什么要物理查询优化？

一个选择查询的eg：
在这里插入图片描述的执行方案

方案1：表空间扫描方法
直接对Course表进行扫描，从第一条检索到最后一条，将满足条件的记录找出
方案2：利用Course上的Cname排序索引的方法
利用排序索引可以进行诸如二分查找等快速检索，找到相应的索引项，依据指针将满足条件的记录找出
当条件更复杂时，可选择的方案还会更多，对于上述的方案，究竟用哪一个算法的程序来执行?为什么如此选择?

物理查询运算符

物理查询运算符通常是关系代数操作符的一个特定实现程序
获取关系元组的操作
TableScan(\R) —表空间扫描算法
SortTableScan(\R)—表空间扫描排序算法
IndexScan(\R)—索引扫描算法
SortIndexScan(\R)—索引扫描排序算法

关系操作的各种实现算法

，集合上的操作： , 包上的操作： , 积，连接： PRODUCT， JOIN
每个关系操作都有下面的算法：一趟算法、两趟算法；基于索引算法、基于散列算法、基于排序算法；

迭代器构造–流水化、物化；

物理优化

就是为每一个关系代数操作选择合适的执行程序

2.代价估算

DBMS如何衡量物理查询计划的优劣呢？

衡量I/O访问次数
衡量CPU的占用时间
内存使用代价(与缓冲区数目与大小的匹配)
中间结果存储代价
计算量(如搜索记录、合并记录、排序记录、字段值的计算等)
网络通信量

依据什么信息来计算这些方案的上述各种指标呢？

依据数据库的一些统计信息—存放在数据字典或系统目录中的
$T_R或者T(R)：关系R的元组数目$
$B_R或B(R) ：关系R的磁盘块数目$
$f_R或f(R) : R的块因子，即一块能够存储的R的元组数目$
$V(R, A): R中属性A出现不同值的数目，即 π_A(R) 的数目$
$S C (A, R) : R 中属性 A 的选择基数，满足 A 上等值条件的平均记录数$
$b ：每个磁盘块的字节数；$
DBMS依据上述统计信息对DB操作的各种物理查询计划进行评估，以确定最优的计划予以执行

上述信息如何获得呢？

当一个表装入内存和创建索引的时候，统计信息不是被自动收集的，必须由DBA使用特定的命令来完成信息统计，这些命令就是收集统计信息并把其存入系统目录中的实用程序
随着表的更新操作，统计信息可能会过时，过时的统计信息会使DBMS确定方案时决策错误，因此要求DBA定期的对有频繁更新操作的Table进行统计
DBA要熟悉统计信息收集命令的使用，并定期执行

IBM DB2使用Runstats收集统计信息
RUNSTATS ON TABLE username.tablename
[ WITH DISTRIBUTION [ AND DETAILED ]
{ INDEXES ALL | INDEX indexname} ] ；

收集SCT数据库的Student表的统计信息
Runstats on table SCT.student ;

Oracle使用Analyze命令收集统计信息并将其放入系统表中
ANALYZE { INDEX | TABLE | CLUSTER }
{ indexname | tablename | clustername }
COMPUTE STATISTICS
{ FOR TABLE | FOR ALL [ INDEXED ] COLUMNS [SIZE n] } ；

收集SCT数据库的Student表的统计信息
Analyze table student compute statistics for table ;

物理查询计划的形成：

理想: 寻找最优的查询计划；
现实: 避免最差的查询计划
给定一个表达式E，如何计算E的元组数目T(E)以及属性A上不同值的数目V(E,A)?
（1）在E实际获得之前计算T(A)，V(E,A)等是很难的事情；
（2）因而，要“估算”，代价估算；

投影运算的代价估算

估算一个投影 $π_L(R)$ 的大小
简单: T( $π_L(R)$ ) = T(\R)
投影运算只是对列有所取舍，并未对行有所变化，如并未消除重复（物理优化的投影运算不会去重，逻辑优化的投影可以）
投影运算并未减少行数，但可能有效地减少了存储结果关系的块数
例如：磁盘块大小=1024 Byte
R的元组长度=120 Byte, 8元组/块，T®=10,000, 则
B(\R) = 10000/8 = 1250;
$π_L(R)$ 的元组长度=20 Byte, 50元组/块，则
B( $π_L(R)$ ) = 10000/50 = 200;

不同选择运算的代价估算

估算选择运算 $S = σ_{A=c}(R)$ 的大小
T(S) 介于 0 to T(\R)–V(R,A)+1之间—最多：A属性不同值的元组都只存在一个，剩余的都是A=c的元组
估计: T(S) = T(\R) / V(R,A)—A属性不同值的元组数假设是平均分布的
当不知道V(R,A)时，估计：T(S) = T(\R)/10
估算选择运算 $S = σ_{A<c}(R)$ 的大小
T(S) 介于 0 to T(\R) 之间—最多：所有元组都满足条件
估计：T(S) = T(\R)/2—直觉，应有一半的元组，
实际应用的估计： T(S) = T(\R)/3
估算选择运算 $S = σ_{A=10 AND B<20}(R)$ 的大小
估计：T(S) = T(\R)/(V(R, A)*3)
$S = σ_{A=10 AND B<20}(R)$ = $σ_{B<20}(σ_{A=10})(R)$
A=10，得出T(S) = T(\R)/V(R,A);
B<20，得出T(S) = T(S)/3
估算选择运算 $S = σ_{C1 or C2}(R)$ 的大小
估计：T(S)=n(1-(1-m1/n)(1-m2/n))
R有n个元组，其中有m1个满足C1, 有m2个满足C2
(1-m1/n)是不满足C1的那些元组，(1-m2/n)是不满足C2的那些元组
两数之积是不在S中的那部分R的元组，1减去这个积就是属于S的那部分元组出现的概率。
估算选择运算 $S = σ_{A=10 or B<20}(R)$ 的大小
估计：T(S)=n(1-(1-m1/n)(1-m2/n))
n = T(\R)=10000, V(R,A)=50,
m1=T(\R)/V(R,A)=10000/50=200;
m2=T(\R)/3 = 10000/3  3333
（有m1个满足C1, 有m2个满足C2，(1-m1/n)(1-m2/n)不满足这个条件的元组的概率，1- (1-m1/n)(1-m2/n)满足这个条件的元组的概率 )
—简单估计：T(S)= T(\R)/3 = 10000/3 = 3333
—复杂估计：
T(S)=10000*(1-(1-200/10000)(1-3333/10000) = 3466
估算连接运算 S = R(X,Y) Natural Join S(Y,Z)的大小
估计：T (S)=T(\R)T(S)/max(V(R,Y),V(S,Y))
假定V(R,Y)>=V(S,Y),R中元组r和S中元组有相同Y值的概率=1/V(R,Y)
假定V(R,Y)<V(S,Y),R中元组r和S中元组有相同Y值的概率=1/V(S,Y)
则，在Y上相等的概率 = 1/max(V(R,Y),V(S,Y))
eg：
例：T(\R)=10000, T(S)=50000, V(R, Y) = 500, V(S, Y)=1000
估计：T(S)=1000050000/1000=500000记录
例：T(\R)=10000, T(S)=50000, V(R, Y) = 2000, V(S, Y)=1000
估计：T(S)=1000050000/2000=250000

3.代价估算总结

T(\R)–R的元祖个数，V(R, A)—R中属性A上出现的不同值的数目
判断满足单一条件元组出现的概率

出现等于某一个值的概率 = 1 / V(R,A), 或者简单的概率 = 1/10
出现不等于某一个值的概率 = 1 – 1/V(R,A), 或者简单的概率 = 1-1/10
出现小于或不等于某一个值的概率直觉上 = 1/2, 实际处理概率=1/3

判断满足多个条件的元组出现的概率

如果是“与”，则将满足两个条件的概率相乘
如果是“或”，则=(1-(1-m1/n)(1-m2/n)，不出现满足条件1的元组的概率(1-m1/n)，不出现满足条件2的元组的概率(1-m2/n)，二者相乘是不同时出现的概率，则1- (1-m1/n)(1-m2/n)即为去掉不同时出现的概率，即为或条件的概率。

复杂的表达式可以依上原则进行估算，确定估算公式

4.小结

在这里插入图片描述