查询优化技术.ppt

《查询优化技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章查询优化技术查询处理器是数据库管理系统DBMS的一个部件，它把用户的查询命令转换成对数据库的一连串操作。鉴于用查询语言SQL表达查询是在较高的层次上，查询处理器必须提供如何进行查询的诸多细节。设S是一个存储有关学生信息的关系，包括学号S#和姓名SN等属性。SC是存储学生选课情况的关系，包括学号S#和课程号C#等属性。下边的SQL语句表示查询“列出所有选修课程C2的学生姓名”：SELECTDISTINCTS.SNFROMS,SCWHERES.S#＝SC.S#ANDSC.C#＝“C2”。查询优化例假定S中包含1000个学生记录，SC中包含10000个选课记

2、录，其中选修C2课程的选课记录为50个。我们用三个等价的关系代数表达式来表示这个查询的三种处理策略：Q1=∏SN(σ(s.s#＝sc.s#)∧(sc.c#=”c2”)(s×sc))；Q2＝∏SN(σ(sc.c#＝”c2”)(ss.s#=sc.s#sc))；Q3＝∏SN(σsc.c#＝”c2”scs.s#=sc.s#s)三种查询处理策略Q1=∏SN(σ(s.s#＝sc.s#)∧(sc.c#=”c2”)(s×sc)执行过程和时间开销分析(1)计算S和SC的笛卡尔积。步骤1，使用一个内存缓冲区BS读入某个关系(如S)的未处理元组；步骤2，使用另一个内存缓冲区B

3、SC读入另一个关系(如SC)的未处理元组；步骤3，把BS中的每个元组和BSC中每个元组相连接，并送人输出缓冲区BO；步骤4，如果BO已满则写到一个临时文件；步骤5，重复步骤②～④，直至SC中元组全部处理完；步骤6，重复步骤①～⑤，直至S中元组全部处理完。设BS能装50个S的元组，BSC能装100个SC的元组，每个磁盘块能装10个S的元组或100个SC的元组。上述算法需要读关系S的100个磁盘块数据，需要20遍读SC关系，每遍读100个磁盘块，读取总块数为：2100。若每秒可读20个磁盘块，则总计要花105秒。S和SC的笛卡尔积的结果元组数为10000000。

4、设每个磁盘块能装5个结果元组，则结果元组的写出要花费100000秒(设每秒写20块)。(2)从临时文件读入S和SC的笛卡尔积，按照选择条件选取满足要求的记录。这一步读取中间文件花费的时间为100000秒(同写中间文件一样)。(3)把第2步的结果在SN上作投影输出，得到最终结果。设满足条件的元组数为50，可存放在内存中。忽略CPU时间，Q1需要的处理时间大于200105秒。Q2的处理过程和时间开销分析(1)计算自然连接。为了执行自然连接，读取S和SC表的策略不变，总的读取块数仍为2100块，需要105秒的时间。但自然连接的结果大大减少，为l000个元组。因此写

5、出这些元组花费的时间为l0秒。(2)读取中间文件块，执行选择运算，花费时间也为10秒。(3)把第2步结果投影输出。如果忽略CPU时间，Q2的处理时间约为125秒。Q3的处理过程和时间开销分析(1)先对SC作选择运算，只需读一遍SC表，存取100块花费时间为5秒。因为满足条件的元组仅50个，不必使用中间文件。(2)读取S表，把读入的S元组和内存中的SC元组作连接。这一步只需读一遍S，共100块，需要5秒钟的时间。(3)把连接结果投影输出。忽略CPU时间，Q3的处理时间约为10秒。本章的开始部分，将考察用于改善逻辑查询方案的各种代数法则。并考察每一种关系代数算符

6、的可能算法。将一个逻辑查询方案转换为一个物理查询方案，不仅要定义出所用的算子，还要给出如何实现算子及如何将数据传给另一算子的方法。本章主要内容关系代数传统的关系代数假设关系是在集合的基础上设计出来的，而SQL中的关系实际上是包(bag)，或称多重集。也就是说，SQL关系中可以存在任意个重复元组。因此，我们将引入一种包上的关系代数。并，交，差在R∪S中，元组t在运算结果中出现的次数，等于在R中出现的次数与S中出现的次数之和。在R∩S中，元组t在运算结果中出现次数，是R中出现次数与S中出现次数的较小者。在R-S中，元组t在运算结果中出现次数，等于R中出现次数减去

7、S中出现次数之差，但不少于零它们对应着SQL中的UNION,INTERSECT和EXCEPT运算。选择运算假设R是一个关系，C是条件,则σC(R)表示对关系R进行选择运算。它是R中符合条件C的元组的包。运算结果的域与R的域相同。运算σ被称为关系代数的选择运算。投影运算若R是一个关系，则∏L（R）为R在投影属性表L上的投影。将扩充这一运算，使之模拟SQL的SELECT子句。允许属性的重命名，用→来指示重命名。例如，L中的成员x→y表示取R的x属性列并重新命名为y。允许表L中包括属性的算术或条件运算。若L的成员不是单个的属性，则必须由箭号和属性来命名表达式的结果

8、。笛卡尔乘积运算若R和S是关系，则R×S也是关系，其