数据库原理与技术上课讲义.ppt

《数据库原理与技术上课讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据库原理与技术6.1查询处理概述（2）查询处理的基本步骤：1语法分析与翻译2优化3执行语法分析与翻译关系代数表达式执行计划优化器查询语句执行引擎查询结果有关数据的统计值数据6.1查询处理概述（3）查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。查询执行计划：用于计算一个查询的原语序列。执行原语：加了“如何执行”注释的关系代数运算。6.1查询处理概述（4）查询优化的过程：代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。6.1查询处理概述（5）对于关系数据库系统，查

2、询优化是：挑战：必须进行好的优化，才有可接受的性能机会：关系表达式的语义层次高，提供了优化的可能性。优化器有理由比程序员做得更好：＊优化器具有丰富的可使用的信息＊当数据库发生变化时优化器容易再次进行优化＊优化器能够对多种实现策略逐一进行考虑＊优化器集中了最优秀的程序员的智慧和经验6.2代价估算6.2.1用于估计代价的目录信息6.2.2查询代价的度量6.2.1用于估计代价的目录信息有关关系的统计信息nr：关系r中的元组数目br：含有关系r的元组的块数目sr：关系r中一个元组的大小fr：关系r的块因子，即一个块中能存放的关系r的元组数若假定关系r的元组物理上存于同一文件中，则：br=nr/

3、fr6.2.1用于估计代价的目录信息（2）有关关系的统计信息（续）V(A,r)：关系r中属性A所具有的不同值的数目。V(A,r)等于ПA（r）的大小若A为关系r的码，则V(A,r)=nrSC(A,r)：关系r的属性A的选择基数。表示关系r中满足属性A上的一个等值条件的平均元组数。若A为r的码属性，则SC(A,r)＝1若A为非码属性，并假定V(A,r)个不同的值在元组上均匀分布，则SC(A,r)＝(nr/V(A,r))。说明：V(A,r)与SC(A,r)中的A可以是属性组。6.2.1用于估计代价的目录信息（3）有关索引的统计信息：fi：树形结构(如B＋树)索引i的内部结点的平均扇出。HT

4、i：索引i的层数。对于关系r的属性A上所建的平衡树索引（如B＋树），HTi＝logfi(V(A,r))对于散列索引，HTi＝1LBi：索引i中最低层索引块数目，即索引叶层的块数。对于散列索引，Lbi就是索引中的块数。算法A的代价估计记为EA。6.2.2查询代价的度量查询代价：查询处理对各种资源的使用情况磁盘存取（简化为磁盘块传送数）CPU时间通信开销一个重要的影响因素：主存中缓冲区的大小M＊最好的情形，所有的数据可以读入到缓冲区中＊最坏的情形，缓冲区只能容纳数目不多的数据块——大约每个关系一块。6.3基本运算的实现每一个基本的代数运算都有多种不同的实现算法。•适用于不同的情况等值

5、条件，范围条件数据是聚集的，数据是非聚集的相关属性上有索引，相关属性上没有索引•执行代价不同6.3基本运算的实现（2）6.3.1选择运算6.3.2排序运算6.3.3连接运算6.3.4其他运算6.3.1选择运算全表扫描方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。代价：E=br缺点：效率低优点：对关系的存储方式没有要求，不需要索引。适用于任何选择条件。6.3.1选择运算（2）索引扫描条件：表在选择条件的属性上建有索引。方法：访问索引，根据索引项的指示去访问数据元组。无序索引：访问满足等值条件的元组有序索引：访问满足范围查找条件的一系列元组。6.3.1选择运算.（3）代

6、价：利用主索引，等值比较：E=HTi+SC(A，r)/fr利用辅助索引，等值比较：E=HTi+SC（A，r）利用主索引，非等值比较：E=HTi+br/2（假设大约一半的元组满足比较条件）利用辅助索引，非等值比较：E=HTi+LBi/2+nr/26.3.1选择运算（4）复杂条件的选择合取：σθ1∧θ2∧…∧θn（r）析取：σθ1∨θ2∨…∨θn（r）方法：利用一个索引进行合取选择。利用组合索引进行合取选择。利用多维索引进行合取选择。通过标识符的交集进行合取选择。通过标识符的并集进行析取选择。6.3.2排序运算排序运算在数据库中的重要意义：SQL查询可能要求有序的查询结果。事先对于作为运

7、算对象的关系进行排序，可以提高某些关系运算（例如连接）的执行效率。内排序：文件较小，整个排序过程都能在内存中进行。外排序：文件较大，排序过程需要使用外存。6.3.2排序运算（2）外部排序-归并算法：（设内存中用于排序的缓冲区页面数为M）第一阶段，建立多个已排序的子表。每次读入M块，进行内排序，将长度为M块的已排序子表（共br/M个）写到外存中。第二阶段，对已排序子表进行归并（可能需进行若干趟）。6.3.2排序运算（3）第二阶段，