查询优化.ppt

第14章:查询优化概述用于代价估计的统计信息关系代数表达式的转换基于代价的优化算法物化视图与视图维护概述一个给定查询有多种可选择的求值方法等价表达式一个操作有若干不同算法(Chapter13)一个查询求值方法的好坏带来的代价差别可能是巨大的例如:=,连接属性的不同值的数目,(续)两个等价表达式生成的关系具有相同的属性集合并包含相同的元组集合,(续)对一个表达式的查询计值方案的生成涉及几个步骤:(Annotate)::::r的块因子—即,(A,r):r中出现的A属性上的不同值的个数;等于A(r)(A,r):关系r中属性A的选择基数;,则:关于索引的目录信息fi:索引i的内节点的平均扇出,适用于树结构索引如B+:索引i的层数—(如B+-树),HTi=logfi(V(A,r)).对于散列索引,:索引i的底层索引块数—:典型地,磁盘存取是决定性的代价,,A=v(r)SC(A,r):满足选择的记录数SC(A,r)/fr—这些记录将占用的块数例如二分搜索的代价估计为键属性上的等值条件:SC(A,r)=ount=20(ount的20个元组)V(branch-name,account)=50(50个分行)V(balance,account)=500(500个不同的balance值)account=10000(account有10,000条元组)ount上存在下列索引:属性branch-name上的主B+-树索引属性balance上的次级B+-树索引涉及比较的选择形如AV(r)的选择(AV(r)的情形是对称的)(A,r)和max(A,r)在目录中可得c=0ifv<min(A,r)c=若没有统计信息,c可假设为nr/2.