《高级软件-王永利》第四章 查询处理.pptVIP

第四章 查询处理 查询的代价：主要取决于磁盘访问的次数。一个给定的查询，对应多种可能的处理策略。策略不同，访问磁盘的次数相差很大，甚至相差几个数量级。因此，选择一个好的处理策略，是非常重要的。 4．1 概述 4．1 概述 2．优化 本章主要针对关系模型： 例：select balance from account where balance2500 这个简单的查询语句可翻译成下面两个关系代数表达式： σ运算(选择)：选出满足给定谓词的元组 σ谓词(关系) 。 *执行原语：查询－关系代数表达式，对 该表达式加上注释(用于说明 如何实施每个操作的命令，具 体运算的算法，所用的索引)， 加了注释的关系代数运算称为 执行原语。 例：图 ： *查询优化：为查询选择最有效的查询执行 计划的过程。 *查询优化器：估计查询计划的代价，选择 最优计划。 利用各关系的统计信息，关系大小，索引深度等。 4．2 用于估计代价的目录信息 关系的目录信息 nr：关系r中的元组数。 br：含有关系r的元组的块数。 sr：关系r中一个元组的大小。 fr：关系r的块因子，即一个块中能存放的关系r的元组数。 V(A,r)：关系r中属性A所具有的不同值的数目。该数目与πA（r）的大小相同。若A为关系r的码， V(A,r) 即为nr。 SC(A,r):关系r的属性A的选择基数。若A为r的码属性，则SC(A,r)=1,否则， SC(A,r)=（ nr/ V(A,r))。 若关系r的元组物理上存于同一文件中，则下面等式成立： br= [nr/ fr] 索引的目录信息 fi：树形结构（如B+树）索引i的内部结点的平均扇出。 HTi：索引i的层数。B+树， HTi=?log fi(V(A,r)) ? ;散列索引 HTi=1。 LBi：索引I中最底层索引块数。 算法A的代价估计记为EA 4．4 选择运算 基本运算 A1：线性搜索 EA1=br/2 A2：二分法搜索 EA2= ? log2br?+ ? SC(A,r)/fr ?-1(假设所有数据在磁盘上连续存放） 利用索引的选择 A3：主索引，码属性等值比较 EA3= HTi+1 A4：主索引，非码属性等值比较 EA4=HTi+ ? SC(A,r)/fr ? A5：辅助索引，等值比较EA4= HTi+ SC(A,r)，当A是码索引属性时， EA4= HTi+ 1 涉及比较的选择 A6：主索引，比较 EA6= HTi+ br/2 A7：辅助索引，比较 EA6= HTi+ LBi/2+nr/2 复杂选择的实现 合取：合取选择形式：σθ1∧θ2∧…∧θn(r) 析取：析取选择形式：σθ1∨θ2∨…∨θn(r) 取反：选择σ﹁θ(r) A8：利用一个索引的合取选择 A9：使用组合索引的合取选择 A10：通过标识符的交集实现合取选择 A11：通过标识符的并集实现析取选择 例： select account-number from account where brunch-name=“perryridge” and balance=1200 account 的统计信息为： faccount=20 每个数据块中存放20个account元组 V(branch-name,account)=50 有50个不同的分支机构 V(balance,account)=500 有50个不同的balance值 naccount=10000 即account关系有10000个元组 如果使用branch-name上的索引，假定索引为聚集索引（主索引），所需代价为12 由于V(branch-name,account)=50,估计得到account关系中“perryridge”分支机构的10000/50=200个元组。读取account元组需要 200/20=10次块存