【文件属性】：
文件名称：代价估算-ubuntu 18.04 安装opencv3.4.5的教程(图解)
文件大小：4.99MB
文件格式：PDF
更新时间：2021-06-25 08:12:12
数据库系统概 王珊 课后习题
五、物理优化
物理优化是要选择高效合理的操作算法或存取路径，求得优化的查询计划，达到查询优化的目标。选择的方
法可以是：基于规则的启发式优化；基于代价估算的优化；两者结合的优化方法。
1．基于启发式规则的存取路径选择优化
（1）选择操作的启发式规则
①对于小关系，使用全表顺序扫描，即使选择列上有索引。
②对于大关系：
a．对于选择条件是主码=值的查询，查询结果最多是一个元组，可以选择主码索引；
b．对于选择条件是非主属性＝值的查询，并且选择列上有索引，则要估算查询结果的元组数目，比例较小
(<10％)可以使用索引扫描方法，否则使用全表顺序扫描；
c．对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，同样要估算查询结果的元组
数目，比例较小(<10％)可以使用索引扫描方法，否则使用全表顺序扫描；
d．对于用 AND 连接的合取选择条件，如果涉及这些属性的组合索引，则优先采用组合索引扫描方法；如
某些属性上有一般的索引，使用索引扫描方法，否则使用全表顺序扫描；
e．对于用 OR 连接的析取选择条件，一般使用全表顺序扫描。
（2）连接操作的启发式规则
①如果两个表都已经按照连接属性排序，则选用排序-合并方法。
②如果一个表在连接属性上有索引，则可以选用索引连接方法。
③如果上面两个规则都不适用，其中一个表较小，则可以选用 Hash Join 方法。
④最后可以选用嵌套循环方法，并选择其中较小的表，即占用的块数较少的表作为外表。
2．基于代价估算的优化
在编译执行的系统中，一次编译优化，多次执行，查询优化和查询执行是分开的，适合采用精细复杂的基于
代价的优化方法。
（1）统计信息
基于代价的优化方法要计算各种操作算法的执行代价，它与数据库的状态密切相关。为此，在数据字典中存
储了优化器需要的统计信息(database statistics)，主要包括如下几个方面：
①对每个基本表，该表的元组总数(N)、元组长度(I)、占用的块数(B)、占用的溢出块数(BO)；
②对基表的每个列，该列不同值的个数、选择率、该列最大值、最小值，该列上是否已经建立了索引，是哪
种索引（B+树索引、Hash 索引、聚集索引）；
③对索引，例如 B+树索引，该索引的层数(L)、不同索引值的个数、索引的选择基数、索引的叶结点数(Y)。
（2）代价估算
①全表扫描算法的代价估算公式。如果基本表大小为 B 块，全表扫描算法的代价 cost=B；如果选择条件是
码=值，那么平均搜索代价 cost=B/2。
②索引扫描算法的代价估算公式
90