第5章查询处理和查询优化详解.ppt

* * 2. 连接操作的启发式规则 (4) 可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用存储块数较少的表，作为外表（外循环的表）。 理由： 设连接表R与S分别占用的块数为Br与Bs 连接操作使用的内存缓冲区块数为K 分配K-1块给外表 如果R为外表，则嵌套循环法存取的块数为 显然应该选块数小的表作为外表 * * 5.5 基于代价估算的优化 启发式规则优化是定性的选择，适合解释执行的系统 解释执行的系统，优化开销包含在查询总开销之中 编译执行的系统中查询优化和查询执行是分开的 可以采用精细复杂一些的基于代价的优化方法 影响查询执行代价的因素主要有： 访问存储器的代价：搜索、读和写二级存储器（主要是磁盘）上的数据库的代价 存储代价：存储在查询执行时生成的中间文件的代价 计算代价：在查询执行时对内存操作的代价，包括搜索元组、排序元组、合并元组、计算等。 内存使用代价：查询执行需要的内存缓冲区数目。 通信代价：查询过程中数据在不同数据库节点传送的代价 * * 统计信息 基于代价的优化方法要计算各种操作算法的执行代价，与数据库的状态密切相关 数据字典中存储的优化器需要的统计信息： 1. 对每个基本表 该表的元组总数(N) 元组长度(l) 占用的块数(B) 占用的溢出块数(BO) * * 统计信息 数据字典中存储的优化器需要的统计信息(续)： 2. 对基表的每个列 该列不同值的个数(m) 选择率(f) 如果不同值的分布是均匀的，f＝1/m 如果不同值的分布不均匀， 则每个值的选择率f ＝具有该值的元组数/N 该列最大值 该列最小值 该列上是否已经建立了索引 索引类型(B+树索引、Hash索引、聚集索引) * * 统计信息 数据字典中存储的优化器需要的统计信息(续)： 3. 对索引(如B+树索引) 索引的层数(L) 不同索引值的个数 索引的选择基数S(有S个元组具有某个索引值) 索引的叶结点数(Y) * * 5.5.2 连接操作的代价估算 1. 嵌套循环法 设连接表R与S分别占用的块数为BR与BS，连接操作使用的内存缓冲区块数为K，分配K-1块给外表， 如果R为外表，则嵌套循环法存取的块数为 BR+ BRBS/(K-1)。 如果需要把连接结果写回磁盘，则 cost=BR+ BRBS/(K-1)+(Frs*NR*Ns)/Mrs。 其中N是关系的元组总数, Frs为连接选择性(join selectivity)，表示连接结果元组数的比例 Mrs是存放连接结果的块因子，即一个块中能够存放的关系R的元组数量 。 * * 5.5.2 连接操作的代价估算 2. 索引嵌套循环法 若内关系S存在索引，针对外关系R的任意一个给定的元组，都有一次利用索引查找内关系S的相关元组 最坏情况下，内存只能容纳关系R和索引各一个物理块，所需要访问的物理块数为BR+ NR×c， 这里c表示利用索引的选择来获得满足连接条件的关系S的元组所需要的代价。 可以看出，在关系上建立索引进行连接操作与嵌套循环法相比，所花费的代价要降低很多。 如果两个关系都有索引，一般效率较高的方法是把元组较少的关系作为外关系。 * * 5.5.2 连接操作的代价估算 3. 排序合并法 如果连接表已经按照连接属性排好序，则cost＝BR+Bs+(Frs*Nr*Ns)/Mrs。 如果必须对文件排序 需要在代价函数中加上排序的代价 对于包含B个块的文件排序的代价大约是(2*B)+(2*B*log2B) 因此代价函数是： Cost＝(2* BR)+(2* BR*log2 BR)+ (2* BS) +(2*Bs*log2Bs)+BR+BS+(Frs*Nr*Ns)/Mrs * * 5.6 小结 查询处理和查询优化的一般过程，以及查询处理的一些典型的实现算法 查询优化技术 代数优化技术是指关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合,使查询执行更高效 基于存取路径的优化是指存取路径和底层操作算法的选择和优化 代价估算的优化是对多个查询策略的优化选择，代价估算优化开销较大，而且产生所有的执行策略也是不太可能的，因此将产生的执行策略的数目保持在一定范围内才是比较合理的 * * 5.6 小结 解释执行的系统，优化开销包含在查询总开销之中。 全面的优化会延长系统的响应时间。 启发式规则优化是定性的选择，适合解释执行的系统。 在编译模式下查询优化后被存储起来，稍后运行。 编译执行的系统中查询优化和查询执行是分开的，可以采用精细复杂一些的基于代价的优化方法。 使用代价估算的优化方法需要能够准确地估算查询代价才能比较不同的查询策略，这种方法比较适合在编译模式下使用。 因此，查询优化器应该综合这些因素确定优化方案 * *