系统概论王珊_系统概论第五版_系统概论(3)

理由： 设连接表R与S分别占用的块数为Br与Bs 连接操作使用的内存缓冲区块数为K 分配K-1块给外表 如果R为外表，则嵌套循环法存取的块数为Br+BrBs/ K-1 显然应该选块数小的表作为外表 9.4 物理优化 9.4.1 基于启发式规则的存取路径选择优化 9.4.2 基于代价的优化 9.4.2 基于代价的优化 启发式规则优化是定性的选择，适合解释执行的系统 解释执行的系统，优化开销包含在查询总开销之中 编译执行的系统中查询优化和查询执行是分开的 可以采用精细复杂一些的基于代价的优化方法 基于代价的优化（续） 1.统计信息 2.代价估算示例 3.优化方法 基于代价的优化（续） 1.统计信息 基于代价的优化方法要计算查询的各种不同执行方案的执行代价，它与的状态密切相关 优化器需要的统计信息 （1）对每个基本表 该表的元组总数 N 元组长度 l 占用的块数 B 占用的溢出块数 BO 基于代价的优化（续） （2）对基表的每个列 该列不同值的个数 m 列最大值 最小值 列上是否已经建立了索引 哪种索引 B+树索引、Hash索引、聚集索引 可以计算选择率 f 如果不同值的分布是均匀的，f＝1/m 如果不同值的分布不均匀，则要计算每个值的选择率，f＝具有该值的元组数/N 基于代价的优化（续） （3）对索引 索引的层数 L 不同索引值的个数 索引的选择基数S 有S个元组具有某个索引值 索引的叶结点数 Y 基于代价的优化（续） 2.代价估算示例 （1）全表扫描算法的代价估算公式 如果基本表大小为B块，全表扫描算法的代价 cost＝B 如果选择条件是“码＝值”，那么平均搜索代价 cost＝B/2 基于代价的优化（续） （2）索引扫描算法的代价估算公式 如果选择条件是“码＝值” 则采用该表的主索引 若为B+树，层数为L，需要存取B+树中从根结点到叶结点L块，再加上基本表中该元组所在的那一块，所以cost L+1 基于代价的优化（续） （2）索引扫描算法的代价估算公式（续） 如果选择条件涉及非码属性 若为B+树索引，选择条件是相等比较，S是索引的选择基数 有S个元组满足条件 满足条件的元组可能会保存在不同的块上，所以 最坏的情况 cost L+S 基于代价的优化（续） （2）索引扫描算法的代价估算公式（续） 如果比较条件是＞，＞＝，＜，＜＝操作 假设有一半的元组满足条件 就要存取一半的叶结点 通过索引访问一半的表存储块 cost L+Y/2+B/2 如果可以获得更准确的选择基数，可以进一步修正Y/2与B/2 9.2 关系系统的查询优化 查询优化在关系系统中有着非常重要的地位 关系查询优化是影响关系管理系统性能的关键因素 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性 9.2 关系系统的查询优化 9.2.1查询优化概述 9.2.2一个实例 9.2.1 查询优化概述 关系系统的查询优化 是关系管理系统实现的关键技术又是关系系统的优点所在 减轻了用户选择存取路径的负担 查询优化概述（续） 非关系系统 用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户来决定的 用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定 如果用户做了不当的选择，系统是无法对此加以改进的 查询优化概述 查询优化的优点 用户不必考虑如何最好地表达查询以获得较好的效率 系统可以比用户程序的“优化”做得更好 （1） 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25972-3.html