查询树的优化

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

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

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

4、果2. 选择：扫描选择：扫描10000个记录个记录3. 投影投影snamesname( o=o=2 2 （ SC Student）4.1 关系数据库系统的查询处理假设有假设有1000个学生记录，个学生记录，10000个选课记录，个选课记录，2号课程的选课记录为号课程的选课记录为500个。个。1. 选择：扫描选择：扫描10000个记录个记录 ，得到，得到500个记录个记录2. 连接，采用嵌套循环：连接，采用嵌套循环：500*1000次，得到次，得到500个记录个记录3. 投影投影snamesname( o=o=2 2( (SC) ) Student）F 选择操作先做可以提高效率。选择操作先做可以

5、提高效率。4.2 代数优化4.2.1 关系代数表达式等价变换规则关系代数表达式等价变换规则F 等价的概念：n若关系表达式f（E1，E2，En）的结果与关系表达式g（E1，E2，En）的结果是同一个关系，那么称这两个表达式等价。n若关系表达式E1和E2是等价的可以记为：12EE等价变换规则1. 连接、笛卡儿积交换率连接、笛卡儿积交换率 设设E1和和E2是关系代数表达式，是关系代数表达式，F是连接运算的是连接运算的条件，则有：条件，则有：1221EEEE1221EEEE 1221FFEEEE等价变换规则1. 连接、笛卡儿积的结合率连接、笛卡儿积的结合率 设设E1，E2，E3是关系代数表达式，是关系

6、代数表达式，F1和和F2是是连接运算的条件，则有：连接运算的条件，则有：123123()()EEEEEE123123()()EEEEEE1212123123()()FFFFEEEEEE等价变换规则2. 连接、笛卡儿积的结合率连接、笛卡儿积的结合率 设设E1，E2，E3是关系代数表达式，是关系代数表达式，F1和和F2是是连接运算的条件，则有：连接运算的条件，则有：Student(SCCourse)StudentSCCourseSC(StudentCourse)StudentSCCourse3. 投影的串接定律121212,( ) )( )nmnA AAB BBA AAEE 这里，这里，E是关系代

7、数表达式，是关系代数表达式，Ai（i=1，2，n），），Bj（j=1，2，m）是属性）是属性名且名且A1，A2， An 是是B1，B2，Bm 的子集。的子集。等价变换规则,( )( )SnameSname SageSnameSS4. 选择的串接定律等价变换规则1919( )( )SdeptISSageSdeptISSageSS求IS系年龄大于岁的学生：4. 选择的串接定律1212( ) )( )FFFFEEE是关系代数表达式，是关系代数表达式，F1和和F2是选是选择条件。选择的串接定律说明选择条件择条件。选择的串接定律说明选择条件可以合并，这样一次就可以检查全部的可以合并，这样一次就可以检查全

8、部的条件。条件。等价变换规则等价变换规则19,19( )( )SageSname SageSname SageSageSS1919,( )( )SnameSageSnameSageSname SageSS5. 选择与投影的交换律 此时，条件此时，条件F只涉及属性组只涉及属性组A。若条件中有不属。若条件中有不属于于A的属性组的属性组B，那么有更一般的规则：，那么有更一般的规则：1212,( ) )( ) )nnFA AAA AAFEE12121212,( ) )( ) ) )nnnmA AAFA AAFA AA B BBEE等价变换规则6.选择与笛卡尔积的交换122112121212()1()(

9、)()23()FFFFFFEEEEEEEE（ ）（ ）（ ）（1）F只涉及只涉及E1的属性。的属性。（2）F=F1F2，且，且F1只涉及只涉及E1的属性，的属性，F2只涉及只涉及E2的属性。的属性。（3） F=F1F2，且，且F1只涉及只涉及E1的属性，而的属性，而F2涉及涉及E1和和E2的属性。的属性。11()()cnocnoSSCSCS(1) 实例：选修实例：选修1号课程的学生信息号课程的学生信息等价变换规则11()()()cnosdeptIScnosdeptISSSCSCS(2) 实例：信息系选修实例：信息系选修1号课程的学生信息号课程的学生信息7. 选择与并的分配率设设E=E1E2，E

10、1和和E2有相同的属性名，则：有相同的属性名，则：1212()()()FFFEEEE注：先做选择可以减少读取写入的数据，因此减少磁盘注：先做选择可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。等价变换规则设设S1是计科是计科041的学生关系表，的学生关系表，S2是计科是计科042的学生关系表：的学生关系表：1912191192()()()SageSageSageSSSS等价变换规则8. 选择与差运算的分配率设设E1和和E2有相同的属性名，则：有相同的属性名，则：1212()()()FFFEEEE注：先做选择可以减少读取写入的数据，因此减少磁盘注：先做选择可以减少

11、读取写入的数据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。等价变换规则设设S1是计科是计科041的学生关系表，的学生关系表，S3是计科专业的学生关系表：是计科专业的学生关系表：1931193191()()()SageSageSageSSSS等价变换规则9. 选择对自然连接的分配率F只涉及只涉及E1和和E2的公共属性。的公共属性。1212()()()FFFEEEE 注：先做选择可以减少做笛卡儿积的数据，结果关系的数注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也同步减少，因此减少磁盘据量也同步减少，因此减少磁盘IO量，提高了效率。量，提高了效率。等价变换规则等价变换规则10

12、. 投影与笛卡尔积的分配律 设设E1和和E2是两个关系表达式，是两个关系表达式，A是是E1的属性组，的属性组，B是是E2的属性组。则：的属性组。则：12121212,12,1,2()()()nmnmA AA B BBA AAB BBEEEE注：先做投影可以减少读取写入的数据，因此减少磁盘注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。等价变换规则,()( )( )Sname CnameSnameCnameSCSC查找所有学生可能的选课对：等价变换规则11. 投影与并的分配律设设E1和和E2有相同的属性名，则：有相同的属性名，则：121212,12,1

13、,2()()()nnnA AAA AAA AAEEEE注：先做投影可以减少读取写入的数据，因此减少磁盘注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。等价变换规则设设S1是计科是计科041的学生关系表，的学生关系表，S2是计科是计科042的学生关系表：的学生关系表：1212()()()SnameSnameSnameSSSS查找计科查找计科041、042的学生姓名：的学生姓名：等价变换规则优化规则：n选择运算尽可能先做。选择运算尽可能先做。n投影运算和选择运算同时进行。投影运算和选择运算同时进行。n把投影运算同其前后的把投影运算同其前后的 双目运算结合

14、执行。双目运算结合执行。n选择运算和笛卡儿积运算结合成连接运算。选择运算和笛卡儿积运算结合成连接运算。n找出公共子表达式，避免重复运算。找出公共子表达式，避免重复运算。4.2.2 4.2.2 查询树的优化查询树的优化4.2 代数优化1.1.查询树查询树5()SnameCpnoCSCSSname5CpnoSCSC4.2.2 优化算法1.1.利用规则利用规则4 4分解选择运算。分解选择运算。2.2.利用规则利用规则4949把选择运算尽量移到叶端。把选择运算尽量移到叶端。3.3.利用规则利用规则3 3，5 5，1010，1111把投影运算尽量移到叶端。把投影运算尽量移到叶端。4.4.利用规则利用规则

15、3535把选择和投影的串接合并成单个选把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影的形式。使择、单个投影或一个选择后跟一个投影的形式。使尽可能多的选择和投影同时执行。尽可能多的选择和投影同时执行。5.5.分组。双目运算和他的直系祖先为一组；双目运分组。双目运算和他的直系祖先为一组；双目运算后代直道叶子全是单目运算时并入改组。笛卡儿算后代直道叶子全是单目运算时并入改组。笛卡儿积的后面若不是与之可以合并的自然连接的等值选积的后面若不是与之可以合并的自然连接的等值选择时，其后代单独分为一组。择时，其后代单独分为一组。优化实例例：查询至少选修了一门先行课号为例：查询至少选修了一门先

16、行课号为5号课程的号课程的学生姓名。其中，学生姓名。其中，C是课程表，是课程表，S是学生表，是学生表，SC是学生选课表。是学生选课表。5()SnameCpnoCSCS在优化规则中没有对自然连接的直接优化，在优化规则中没有对自然连接的直接优化，我们把自然连接分解为笛卡儿积和选择。我们把自然连接分解为笛卡儿积和选择。分解后的关系代数表达式5.()SnameCpnoC Cno SC Cno SC Sno S SnoCSCSSname5.CpnoC Cno SC Cno SC Sno S SnoSCSC第一步：利用规则第一步：利用规则4分解选择运算分解选择运算Sname.SC Sno S SnoSCS

17、C5Cpno.C Cno SC Cno1212( )( )FFFFEE1212( )( )FFFFEE第二步：尽量下放选择运算第二步：尽量下放选择运算Sname.SC Sno S SnoSCSC5Cpno.C Cno SC Cno1212()()FFEEEESname.SC Sno S SnoSCSC5Cpno.C Cno SC Cno第二步（第二步（2）：下放完成后：）：下放完成后：第三步：尽量下放投影运算第三步：尽量下放投影运算Sname.SC Sno S SnoSCSC5Cpno.C Cno SC Cno., .,( )( )SnameSC Sno S SnoSnameSC Sno S

18、SnoSC Sno S Sno SnameEEE第三步：尽量下放投影运算第三步：尽量下放投影运算Sname.SC Sno S SnoSCSC5Cpno.C Cno SC Cno., .,SC Sno S Sno Sname12121212,12,1,2()()()nmnmA AA B BBA AAB BBEEEE第三步（第三步（2）：第一次下放后：）：第一次下放后：.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname., .S Sname S Sno.SC Sno第三步（第三步（3）：第二次下放：）：第二次下放：.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname.SC Sno.,.,.( )( )SC Sn