查询树的优化

1、第四章,查询优化,1,4.1,关系数据库系统的查询处理,?,查询处理步骤,Select ,from student,sc,Where student.sno=sc.sno,and o=2;,例：选修了,2,号课程的学生姓名,2,4.1,关系数据库系统的查询处理,Select ,from student,sc,Where student.sno=sc.sno,and o=2;,1.,查询分析：识别其中的关键字，属性名，表名。,2.,查询检查：属性名是否有效，表名是否有效等。,3.,查询优化：例如上例中先执行连接还是先执行,o=2,从,sc,表中进行

2、选择。选用何,种方法进行连接。,4.,查询执行。,3,4.1,关系数据库系统的查询处理,?,查询处理步骤,?,查询分析：对查询语句进行扫描、,词法分析和语法分析。,?,查询检查：语义检查,?,查询优化：代数优化和物理优化,?,查询执行,4,4.1,关系数据库系统的查询处理,?,为什么进行代数优化？,例：选修了,2,号课程的学生姓名,sname,(,o=,2,（,SC,Student,）,?,sname,( student.sno=sc.sno,o=,2,（,SC,Student,）,?,sname,(,o=,2,(,SC,),Student,）,?,5,4.1,关系数据库系统的查询处理,sna

3、me,( student.sno=sc.sno,o=,2,（,SC,Student,）,?,假设有,1000,个学生记录，,10000,个选课记录，,2,号课程的选课记录为,500,个。,1.,笛卡尔积计算：,1000*10000,2.,选择：扫描,1000*10000,个记录,3.,投影,6,4.1,关系数据库系统的查询处理,假设有,1000,个学生记录，,10000,个选课记录，,2,号课程的选课记录为,500,个。,1.,连接，采用嵌套循环：,10000*1000,，得到,10000,个结果,2.,选择：扫描,10000,个记录,3.,投影,sname,(,o=,2,（,SC,Stude

4、nt,）,?,7,4.1,关系数据库系统的查询处理,假设有,1000,个学生记录，,10000,个选课记录，,2,号课程的选课记录为,500,个。,1.,选择：扫描,10000,个记录,，得到,500,个记录,2.,连接，采用嵌套循环：,500*1000,次，得到,500,个记录,3.,投影,sname,(,o=,2,(,SC,),Student,）,?,?,选择操作先做可以提高效率。,8,4.2,代数优化,4.2.1,关系代数表达式等价变换规则,?,等价的概念：,?,若关系表达式,f,（,E1,，,E2,，,，,En,）的结果与,关系表达式,g,（,E1,，,E2,，,，,En,）的结果是同

5、,一个关系，那么称这两个表达式等价。,?,若关系表达式,E1,和,E2,是等价的可以记为：,1,2,E,E,?,9,等价变换规则,1.,连接、笛卡儿积交换率,设,E,1,和,E,2,是关系代数表达式，,F,是连接运算的,条件，则有：,1,2,2,1,E,E,E,E,?,?,?,1,2,2,1,E,E,E,E,?,1,2,2,1,F,F,E,E,E,E,?,10,等价变换规则,1.,连接、笛卡儿积的结合率,设,E1,，,E2,，,E3,是关系代数表达式，,F1,和,F2,是,连接运算的条件，则有：,1,2,3,1,2,3,(,),(,),E,E,E,E,E,E,?,?,?,?,?,1,2,3,1

6、,2,3,(,),(,),E,E,E,E,E,E,?,1,2,1,2,1,2,3,1,2,3,(,),(,),F,F,F,F,E,E,E,E,E,E,?,11,等价变换规则,2.,连接、笛卡儿积的结合率,设,E1,，,E2,，,E3,是关系代数表达式，,F1,和,F2,是,连接运算的条件，则有：,Student,(,SC,Course),Student,SC,Course,SC,(,Student,Course),Student,SC,Course,12,3.,投影的串接定律,1,2,1,2,1,2,(,(,),),(,),n,m,n,A,A,A,B,B,B,A,A,A,E,E,?,?,?,?

7、,L,L,L,这里，,E,是关系代数表达式，,A,i,（,i=1,，,2,，,，,n,），,B,j,（,j=1,，,2,，,，,m,）是属性,名且,A,1,，,A,2,，, A,n,是,B,1,，,B,2,，,，,B,m,的子集。,等价变换规则,(,(,),(,),Sname,Sname,Sage,Sname,S,S,?,?,?,?,13,4.,选择的串接定律,等价变换规则,19,19,(,(,),(,),Sdept,IS,Sage,Sdept,IS,Sage,S,S,?,?,?,?,?,?,?,?,?,求,IS,系年龄大于岁的学生：,14,4.,选择的串接定律,1,2,1,2,(,(,),)

8、,(,),F,F,F,F,E,E,?,?,?,?,?,E,是关系代数表达式，,F,1,和,F,2,是选,择条件。选择的串接定律说明选择条件,可以合并，这样一次就可以检查全部的,条件。,等价变换规则,15,等价变换规则,19,19,(,(,),(,(,),Sage,Sname,Sage,Sname,Sage,Sage,S,S,?,?,?,?,?,?,?,19,19,(,(,),(,(,(,),Sname,Sage,Sname,Sage,Sname,Sage,S,S,?,?,?,?,?,?,?,?,16,5.,选择与投影的交换律,此时，条件,F,只涉及属性组,A,。若条件中有不属,于,A,的属性组

9、,B,，那么有更一般的规则：,1,2,1,2,(,(,),),(,(,),),n,n,F,A,A,A,A,A,A,F,E,E,?,?,?,?,?,L,L,1,2,1,2,1,2,1,2,(,(,),),(,(,(,),),),n,n,n,m,A,A,A,F,A,A,A,F,A,A,A,B,B,B,E,E,?,?,?,?,?,?,L,L,L,L,等价变换规则,17,6.,选择与笛卡尔积的交换,1,2,2,1,1,2,1,2,1,2,1,2,(,),1,(,),(,),(,),2,3,(,(,),),F,F,F,F,F,F,E,E,E,E,E,E,E,E,?,?,?,?,?,?,?,?,?,?,?

10、,?,?,?,?,?,（）,（,）,（,）,（,1,）,F,只涉及,E,1,的属性。,（,2,）,F=F,1,F,2,，且,F,1,只涉及,E,1,的属性，,F,2,只涉及,E,2,的属性。,（,3,）,F=F,1,F,2,，且,F,1,只涉及,E,1,的属性，而,F,2,涉及,E,1,和,E,2,的属性。,18,1,1,(,),(,),cno,cno,S,SC,SC,S,?,?,?,?,?,?,?,(1),实例：选修,1,号课程的学生信息,等价变换规则,1,1,(,),(,),(,),cno,sdept,IS,cno,sdept,IS,S,SC,SC,S,?,?,?,?,?,?,?,?,?,

11、?,?,(2),实例：信息系选修,1,号课程的学生信息,19,7.,选择与并的分配率,设,E=E,1,E,2,，,E,1,和,E,2,有相同的属性名，则：,1,2,1,2,(,),(,),(,),F,F,F,E,E,E,E,?,?,?,?,U,U,注：先做选择可以减少读取写入的数据，因此减少磁盘,IO,量，从而提高了效率。,等价变换规则,20,设,S1,是计科,041,的学生关系表，,S2,是计科,042,的学生关系表：,19,1,2,19,1,19,2,(,),(,),(,),Sage,Sage,Sage,S,S,S,S,?,?,?,?,?,?,?,U,U,等价变换规则,21,8.,选择与差

12、运算的分配率,设,E,1,和,E,2,有相同的属性名，则：,1,2,1,2,(,),(,),(,),F,F,F,E,E,E,E,?,?,?,?,?,?,注：先做选择可以减少读取写入的数据，因此减少磁盘,IO,量，从而提高了效率。,等价变换规则,22,设,S1,是计科,041,的学生关系表，,S3,是计科专业的学生关系表：,19,3,1,19,3,19,1,(,),(,),(,),Sage,Sage,Sage,S,S,S,S,?,?,?,?,?,?,?,?,?,等价变换规则,23,9.,选择对自然连接的分配率,F,只涉及,E1,和,E2,的公共属性。,1,2,1,2,(,),(,),(,),F,

13、F,F,E,E,E,E,?,?,?,?,注：先做选择可以减少做笛卡儿积的数据，结果关系的数,据量也同步减少，因此减少磁盘,IO,量，提高了效率。,等价变换规则,24,等价变换规则,25,10.,投影与笛卡尔积的分配律,设,E,1,和,E,2,是两个关系表达式，,A,是,E,1,的属性组，,B,是,E,2,的属性组。则：,1,2,1,2,1,2,1,2,1,2,1,2,(,),(,),(,),n,m,n,m,A,A,A,B,B,B,A,A,A,B,B,B,E,E,E,E,?,?,?,?,?,?,L,L,L,L,注：先做投影可以减少读取写入的数据，因此减少磁盘,IO,量，从而提高了效率。,等价变换

14、规则,26,(,),(,),(,),Sname,Cname,Sname,Cname,S,C,S,C,?,?,?,?,?,?,查找所有学生可能的选课对：,等价变换规则,27,11.,投影与并的分配律,设,E,1,和,E,2,有相同的属性名，则：,1,2,1,2,1,2,1,2,1,2,(,),(,),(,),n,n,n,A,A,A,A,A,A,A,A,A,E,E,E,E,?,?,?,?,L,L,L,U,U,注：先做投影可以减少读取写入的数据，因此减少磁盘,IO,量，从而提高了效率。,等价变换规则,28,设,S1,是计科,041,的学生关系表，,S2,是计科,042,的学生关系表：,1,2,1,2

15、,(,),(,),(,),Sname,Sname,Sname,S,S,S,S,?,?,?,?,U,U,查找计科,041,、,042,的学生姓名：,等价变换规则,29,优化规则：,?,选择运算尽可能先做。,?,投影运算和选择运算同时进行。,?,把投影运算同其前后的,双目运算结合执行。,?,选择运算和笛卡儿积运算结合成连接运算。,?,找出公共子表达式，避免重复运算。,30,4.2.2,查询树的优化,4.2,代数优化,1.,查询树,5,(,(,),Sname,Cpno,C,SC,S,?,?,?,?,?,Sname,?,5,Cpno,?,?,S,C,SC,31,4.2.2,优化算法,1.,利用规则,4

16、,分解选择运算。,2.,利用规则,49,把选择运算尽量移到叶端。,3.,利用规则,3,，,5,，,10,，,11,把投影运算尽量移到叶端。,4.,利用规则,35,把选择和投影的串接合并成单个选,择、单个投影或一个选择后跟一个投影的形式。使,尽可能多的选择和投影同时执行。,5.,分组。双目运算和他的直系祖先为一组；双目运,算后代直道叶子全是单目运算时并入改组。笛卡儿,积的后面若不是与之可以合并的自然连接的等值选,择时，其后代单独分为一组。,32,优化实例,例：查询至少选修了一门先行课号为,5,号课程的,学生姓名。其中，,C,是课程表，,S,是学生表，,SC,是学生选课表。,5,(,(,),Sna

17、me,Cpno,C,SC,S,?,?,?,在优化规则中没有对自然连接的直接优化，,我们把自然连接分解为笛卡儿积和选择。,33,分解后的关系代数表达式,5,.,.,.,.,(,(,),Sname,Cpno,C,Cno,SC,Cno,SC,Sno,S,Sno,C,SC,S,?,?,?,?,?,?,?,?,?,Sname,?,5,.,.,.,.,Cpno,C,Cno,SC,Cno,SC,Sno,S,Sno,?,?,?,?,?,?,S,C,SC,34,第一步：利用规则,4,分解选择运算,Sname,?,.,.,SC,Sno,S,Sno,?,?,S,C,SC,5,Cpno,?,?,.,.,C,Cno,S

18、C,Cno,?,?,1,2,1,2,(,(,),),(,),F,F,F,F,E,E,?,?,?,?,?,1,2,1,2,(,),(,(,),),F,F,F,F,E,E,?,?,?,?,?,35,第二步：尽量下放选择运算,Sname,?,.,.,SC,Sno,S,Sno,?,?,S,C,SC,5,Cpno,?,?,.,.,C,Cno,SC,Cno,?,?,1,2,1,2,(,),(,),F,F,E,E,E,E,?,?,?,?,?,36,Sname,?,.,.,SC,Sno,S,Sno,?,?,S,C,SC,5,Cpno,?,?,.,.,C,Cno,SC,Cno,?,?,第二步（,2,）：下放完成

19、后：,37,第三步：尽量下放投影运算,Sname,?,.,.,SC,Sno,S,Sno,?,?,S,C,SC,5,Cpno,?,?,.,.,C,Cno,SC,Cno,?,?,.,.,.,.,.,.,(,(,),(,(,(,),Sname,SC,Sno,S,Sno,Sname,SC,Sno,S,Sno,SC,Sno,S,Sno,Sname,E,E,?,?,?,?,?,?,?,?,E,38,第三步：尽量下放投影运算,Sname,?,.,.,SC,Sno,S,Sno,?,?,S,C,SC,5,Cpno,?,?,.,.,C,Cno,SC,Cno,?,?,.,.,SC,Sno,S,Sno,Sname,?

20、,1,2,1,2,1,2,1,2,1,2,1,2,(,),(,),(,),n,m,n,m,A,A,A,B,B,B,A,A,A,B,B,B,E,E,E,E,?,?,?,?,?,?,L,L,L,L,39,第三步（,2,）：第一次下放后：,.,.,SC,Sno,S,Sno,?,?,S,C,SC,5,Cpno,?,?,.,.,C,Cno,SC,Cno,?,?,Sname,?,.,.,S,Sname,S,Sno,?,.,SC,Sno,?,40,第三步（,3,）：第二次下放：,.,.,SC,Sno,S,Sno,?,?,S,C,SC,5,Cpno,?,?,.,.,C,Cno,SC,Cno,?,?,Sname,?,.,SC,Sno,?,.,.,.,.,.,.,.,.,.,(,(,),(,(,(,(,),SC,Sno,C,Cno,SC,Cno,SC,Sno,C,Cno,SC,Cno,C,Cno,SC,Sno,SC,Cno,E,E,?,?,?,?,?,?,?,?,.,.,S,Sname,S,Sno,?,41,第三步（,3,）：第二次下放：,.,.,SC,Sno,S,Sno,?,?,S,C,SC,5,Cpno,?,