查询优化技术

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 查询优化技术,查询处理器是数据库管理系统,DBMS,的一个部件，它把用户的查询命令转换成对数据库的一连串操作。鉴于用查询语言,SQL,表达查询是在较高的层次上，查询处理器必须提供如何进行查询的诸多细节。,设,S,是一个存储有关学生信息的关系，包括学号,S#,和姓名,SN,等属性。,SC,是存储学生选课情况的关系，包括学号,S#,和课程号,C#,等属性。下边的,SQL,语句表示查询“列出所有选修课程,C2,的学生姓名”：,SELECT DISTINCT S.SN,FROM S, SC,WHERE,S.S#SC.S# AND SC.C#“C2”。,查询优化例,假定,S,中包含1000个学生记录，,SC,中包含10000个选课记录，其中选修,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，,使用另一个内存缓冲区,BSC,读入另一个关系(如,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。设每个磁盘块能装5个结果元组，则结果元组的写出要花费100000秒(设每秒写20块)。,(2)从临时文件读入,S,和,SC,的笛卡尔积，按照选择条件选取满足要求的记录。这一步读取中间文件花费的时间为100000秒(同写中间文件一样)。,(3)把第2步的结果在,SN,上作投影输出，得到最终结果。设满足条件的元组数为50，可存放在内存中。,忽略,CPU,时间，,Q1,需要的处理时间大于200105秒。,Q2,的处理过程和时间开销分析,(1)计算自然连接。为了执行自然连接，读取,S,和,SC,表的策略不变，总的读取块数仍为2100块，需要105秒的时间。但自然连接的结果大大减少，为,l000,个元组。因此写出这些元组花费的时间为,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秒。,本章的开始部分，将考察用于改善逻辑查询方案的各种代数法则。并考察每一种关系代数算符的可能算法。将一个逻辑查询方案转换为一个物理查询方案，不仅要定义出所用的算子，还要给出如何实现算子及如何将数据传给另一算子的方法。,本章主要内容,关系代数,传统的关系代数假设关系是在集合的基础上设计出来的，而,SQL,中的关系实际上是包(,bag)，,或称多重集。也就是说，,SQL,关系中可以存在任意个重复元组。因此，我们将引入一种包上的关系代数。,并，交，差,在,RS,中，元组,t,在运算结果中出现的次数，等于在,R,中出现的次数与,S,中出现的次数之和。,在,RS,中，元组,t,在运算结果中出现次数，是,R,中出现次数与,S,中出现次数的较小者。,在,R-S,中，元组,t,在运算结果中出现次数，等于,R,中出现次数减去,S,中出现次数之差，但不少于零,它们对应着,SQL,中的,UNION, INTERSECT,和,EXCEPT,运算。,选择运算,假设,R,是一个关系，,C,是条件, 则,C,(R),表示对关系,R,进行选择运算。,它是,R,中符合条件,C,的元组的包。运算结果的域与,R,的域相同。,运算,被称为关系代数的选择运算。,投影运算,若,R,是一个关系，则,L,（R）,为,R,在投影属性表,L,上的投影。,将扩充这一运算，使之模拟,SQL,的,SELECT,子句。,允许属性的重命名，用来指示重命名。例如，,L,中的成员,xy,表示取,R,的,x,属性列并重新命名为,y。,允许表,L,中包括属性的算术或条件运算。,若,L,的成员不是单个的属性，则必须由箭号和属性来命名表达式的结果。,笛卡尔乘积运算,若,R,和,S,是关系，则,RS,也是关系，其结果关系的域来自于,R,的域加上,S,的域。,若某一个属性，如,a，,在两个关系中都有，则在结果域中用,R.a,和,S.a,作为这两个属性的名字。,结果关系的元组都是由从,R,中取一个元组且在这一元组的分量后接,S,的任一元组的分量而形成的。,若一元组,r,在,R,中出现,n,次，另一元组,s,在,S,中出现,m,次，则元组,rs,在结果中出现,nm,次。,连接运算,最简单的连接是自然连接；我们用,R,S,来表示,R,和,S,的自然连接。,自然连接可分解为,L,（,C,(RS)），,其中：,.,C,是使,R,和,S,中所有同名的属性对相等的条件。,.,L,是,R,和,S,的所有属性的列表，只是每一对相等的属性中去掉一个。若,R.x,和,S.x,是相等的属性，则因为在投影的结果中只有一个属性,x，,任取,R.x,和,S.x,之一, 并重新命名为,x。,用于改善查询方案的代数定律,关系代数表达式可以用树结构来表示。在不改变查询结果的前提下，将这棵树进行变换，以达到降低查询的时间和空间复杂性的目的。这一工作称为关系代数优化。,这一工作是在较高的抽象层次上即逻辑数据结构层上进行的。,查询的符号表示形式：查询树,查询树是一种表示关系代数表达式的树形结构。在一个查询树中，叶子节点表示关系，内部节点表示关系代数操作。查询树以自底向上的方式执行：,当一个内部节点的操作分量有值时，这个内部节点所表示的操作开始启动执行，,执行结束后用结果关系代替这个内部节点。,给定一个用,SQL,语言定义的查询：,SELECT list,FROM R,1,，R,2,，,R,n,WHERE C,其中，,C,是条件表达式，,list,是输出属性表。,可以按照如下方法把这个查询转换为关系代数表达式：,1）,使用,FROM,从句中的关系,R,1,、R,2,、,R,n,构造笛卡尔乘积,R,1,R,2,R,n,；,2）,在第1步的基础上构造一个选择操作：,C,（R,1,R,2,R,n,）；,在第2步的基础上构造一个投影操作：,list,(,C,（R,1,R,2,R,n,）)。,假设有关系,MovieStar,(name,addr,gender,birthdate,),StarsIn,(title,year,starName,),从中我们要查找出那些在1996年的影片中出现的女演员的出生日期和影片名：,SELECT title,birthdate,FROM,MovieStar,StarsIn,WHERE year=1996 AND,gender=F AND,starName,=name;,等价的表达方式,下图中所用的方案与上图明显不同。,第一,，应用于两个关系的乘积上的,WHERE,子句中的条件,starName,=name,是一个等值连接。一般地，连接运算产生的元组比乘积运算产生的结果元组要少，因此，如有可能，尽量使用连接运算。,第二,，,WHERE,子句的其他两个条件被分成了两个,运算，并且两个,运算都被顺着树往下移。其中，因为选择运算,year,=1996,只涉及到,StarsIn,的一个属性,year，,所以，它可直接应用到关系,StarsIn,之上。,的两个分离规则：,C1 AND C2,(R),C1,(,C2,(R)。,C1 OR C2,(R) (,C1,(R) (,C2,(R)。,注意,和,的次序是灵活的。例如，我们也可以把上面的第一个规则写成,在,之后进行操作，即,C2,(,C1,(R)。,实际上，,运算符的次序可任意交换。,C1,(,C2,(R) ,C2,(,C1,(R)。,优化查询过程的一个最重要的思想，是不改变表达式的作用而尽量将选择操作顺着查询树往下移,例,给出关系,R（a，b）、S（b，c）,和表达式,(a=1 OR a=3) AND bc,(R,S)。,条件,bc,可单独应用于,S，,条件,a1 OR a3,可单独应用于,R，,因此，从分解这两个条件的,AND,开始，得,a,=1 OR a=3,(,b,c,(R,S)。,接着，可以将选择,b,c,下移至,S，,得到表达式：,a,=1 OR a=3,(R,b,c,(S),最后，将第一个条件移至,R，,生成,a,=1 OR a=3,(R),b,c,(S),设有关系,MovieStar,(name,addr,gender,birthdate,),StarsIn,(title,year,starName,),并且想知道对每一年出现在该年影片中的最年轻演员的生日。我们可以把这一查询表达为：,SELECT year,MAX(,birthdate,),FROM,MovieStar,StarsIn,WHERE name=,starName,GROUP BY year；,直接由这一查询建立起来的最初查询方案如：,从一个包中删去重复元组的运算符,分组和聚集(,Grouping and aggregation),做一些变换：,.,把选择和积合并到一个等值连接中。,.,因为,为不受副本影响的，在,下增加一个,。,.,在,之下（且在引入的,之上）增加一个在,year,和,birthdate,（,对,有关的两个属性）上的,运算。,这样生成的查询方案如图：,从一个包中删去重复元组的运算符,运算,分组和聚集,