查询树的优化

《查询树的优化》由会员分享，可在线阅读，更多相关《查询树的优化（46页珍藏版）》请在金锄头文库上搜索。

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

2、行 o=2从sc表中进行选择。选用何 种方法进行连接。4.查询执行。2021/3/1134.1 关系数据库系统的查询处理n查询处理步骤 查询分析：对查询语句进行扫描、词法分析和语法分析。 查询检查：语义检查 查询优化：代数优化和物理优化 查询执行2021/3/1144.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) )

3、Student）2021/3/1154.1 关系数据库系统的查询处理snamesname( student.sno=sc.sno o=o=2 2 （ SC Student）假设有假设有1000个学生记录，个学生记录，10000个选课记录，个选课记录，2号课程的选课记录为号课程的选课记录为500个。个。1. 笛卡尔积计算：笛卡尔积计算：1000*10000 2. 选择：扫描选择：扫描1000*10000个记录个记录3. 投影投影2021/3/1164.1 关系数据库系统的查询处理假设有假设有1000个学生记录，个学生记录，10000个选课记录，个选课记录，2号课程的选课记录为号课程的选课记录为5

4、00个。个。1. 连接，采用嵌套循环：连接，采用嵌套循环：10000*1000 ，得到，得到10000个结果个结果2. 选择：扫描选择：扫描10000个记录个记录3. 投影投影snamesname( o=o=2 2 （ SC Student）2021/3/1174.1 关系数据库系统的查询处理假设有假设有1000个学生记录，个学生记录，10000个选课记录，个选课记录，2号课程的选课记录为号课程的选课记录为500个。个。1. 选择：扫描选择：扫描10000个记录个记录 ，得到，得到500个记录个记录2. 连接，采用嵌套循环：连接，采用嵌套循环：500*1000次，得到次，得到500个记录个记录

5、3. 投影投影snamesname( o=o=2 2( (SC) ) Student）F 选择操作先做可以提高效率。选择操作先做可以提高效率。2021/3/1184.2 代数优化4.2.1 关系代数表达式等价变换规则关系代数表达式等价变换规则F 等价的概念：n若关系表达式f（E1，E2，En）的结果与关系表达式g（E1，E2，En）的结果是同一个关系，那么称这两个表达式等价。n若关系表达式E1和E2是等价的可以记为：2021/3/119等价变换规则1. 连接、笛卡儿积交换率连接、笛卡儿积交换率 设设E1和和E2是关系代数表达式，是关系代数表达式，F是连接运算的是连接运算的条件，则有：条件，则有

6、：2021/3/1110等价变换规则1. 连接、笛卡儿积的结合率连接、笛卡儿积的结合率 设设E1，E2，E3是关系代数表达式，是关系代数表达式，F1和和F2是是连接运算的条件，则有：连接运算的条件，则有：2021/3/1111等价变换规则2. 连接、笛卡儿积的结合率连接、笛卡儿积的结合率 设设E1，E2，E3是关系代数表达式，是关系代数表达式，F1和和F2是是连接运算的条件，则有：连接运算的条件，则有：Student(SCCourse)StudentSCCourseSC(StudentCourse)StudentSCCourse2021/3/11123. 投影的串接定律 这里，这里，E是关系代

7、数表达式，是关系代数表达式，Ai（i=1，2，n），），Bj（j=1，2，m）是属性名）是属性名且且A1，A2， An 是是B1，B2，Bm 的的子集。子集。等价变换规则2021/3/11134. 选择的串接定律等价变换规则求IS系年龄大于岁的学生：2021/3/11144. 选择的串接定律E是关系代数表达式，是关系代数表达式，F1和和F2是选是选择条件。选择的串接定律说明选择条件择条件。选择的串接定律说明选择条件可以合并，这样一次就可以检查全部的可以合并，这样一次就可以检查全部的条件。条件。等价变换规则2021/3/1115等价变换规则2021/3/11165. 选择与投影的交换律 此时，条

8、件此时，条件F只涉及属性组只涉及属性组A。若条件中有不属。若条件中有不属于于A的属性组的属性组B，那么有更一般的规则：，那么有更一般的规则：等价变换规则2021/3/11176.选择与笛卡尔积的交换（1）F只涉及只涉及E1的属性。的属性。（2）F=F1 F2，且且F1只只涉涉及及E1的的属属性性，F2只只涉涉及及E2的属性。的属性。（3） F=F1 F2，且且F1只只涉涉及及E1的的属属性性，而而F2涉涉及及E1和和E2的属性。的属性。2021/3/1118(1) 实例：选修实例：选修1号课程的学生信息号课程的学生信息等价变换规则(2) 实例：信息系选修实例：信息系选修1号课程的学生信息号课程

9、的学生信息2021/3/11197. 选择与并的分配率设设E=E1 E2，E1和和E2有相同的属性名，则：有相同的属性名，则：注：先做选择可以减少读取写入的数据，因此减少磁盘注：先做选择可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。等价变换规则2021/3/1120设设S1是计科是计科041的学生关系表，的学生关系表，S2是计科是计科042的学生关系表：的学生关系表：等价变换规则2021/3/11218. 选择与差运算的分配率设设E1和和E2有相同的属性名，则：有相同的属性名，则：注：先做选择可以减少读取写入的数据，因此减少磁盘注：先做选择可以减少读取写入的数

10、据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。等价变换规则2021/3/1122设设S1是计科是计科041的学生关系表，的学生关系表，S3是计科专业的学生关系表：是计科专业的学生关系表：等价变换规则2021/3/11239. 选择对自然连接的分配率F只涉及只涉及E1和和E2的公共属性。的公共属性。注：先做选择可以减少做笛卡儿积的数据，结果关系的数注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也同步减少，因此减少磁盘据量也同步减少，因此减少磁盘IO量，提高了效率。量，提高了效率。等价变换规则2021/3/1124等价变换规则2021/3/112510. 投影与笛卡尔积的分配

11、律 设设E1和和E2是两个关系表达式，是两个关系表达式，A是是E1的属性组，的属性组，B是是E2的属性组。则：的属性组。则：注：先做投影可以减少读取写入的数据，因此减少磁盘注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。等价变换规则2021/3/1126查找所有学生可能的选课对：等价变换规则2021/3/112711. 投影与并的分配律设设E1和和E2有相同的属性名，则：有相同的属性名，则：注：先做投影可以减少读取写入的数据，因此减少磁盘注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。等价变换规则2021/

12、3/1128设设S1是计科是计科041的学生关系表，的学生关系表，S2是计科是计科042的学生关系表：的学生关系表：查找计科查找计科041、042的学生姓名：的学生姓名：等价变换规则2021/3/1129优化规则：n选择运算尽可能先做。选择运算尽可能先做。n投影运算和选择运算同时进行。投影运算和选择运算同时进行。n把投影运算同其前后的把投影运算同其前后的 双目运算结合执行。双目运算结合执行。n选择运算和笛卡儿积运算结合成连接运算。选择运算和笛卡儿积运算结合成连接运算。n找出公共子表达式，避免重复运算。找出公共子表达式，避免重复运算。2021/3/11304.2.2 4.2.2 查询树的优化查询

13、树的优化4.2 代数优化1.1.查询树查询树SCSC2021/3/11314.2.2 优化算法1.1.利用规则利用规则4 4分解选择运算。分解选择运算。2.2.利用规则利用规则4949把选择运算尽量移到叶端。把选择运算尽量移到叶端。3.3.利用规则利用规则3 3，5 5，1010，1111把投影运算尽量移到叶端。把投影运算尽量移到叶端。4.4.利利用用规规则则3535把把选选择择和和投投影影的的串串接接合合并并成成单单个个选选择择、单单个个投投影影或或一一个个选选择择后后跟跟一一个个投投影影的的形形式式。使使尽可能多的选择和投影同时执行。尽可能多的选择和投影同时执行。5.5.分分组组。双双目目

14、运运算算和和他他的的直直系系祖祖先先为为一一组组；双双目目运运算算后后代代直直道道叶叶子子全全是是单单目目运运算算时时并并入入改改组组。笛笛卡卡儿儿积积的的后后面面若若不不是是与与之之可可以以合合并并的的自自然然连连接接的的等等值值选选择时，其后代单独分为一组。择时，其后代单独分为一组。2021/3/1132优化实例例例：查查询询至至少少选选修修了了一一门门先先行行课课号号为为5号号课课程程的的学学生生姓姓名名。其其中中，C是是课课程程表表，S是是学学生生表表，SC是学生选课表。是学生选课表。在优化规则中没有对自然连接的直接优化，在优化规则中没有对自然连接的直接优化，我们把自然连接分解为笛卡儿

15、积和选择。我们把自然连接分解为笛卡儿积和选择。2021/3/1133分解后的关系代数表达式SCSC2021/3/1134第一步：利用规则第一步：利用规则4分解选择运算分解选择运算SCSC2021/3/1135第二步：尽量下放选择运算第二步：尽量下放选择运算SCSC2021/3/1136SCSC第二步（第二步（2）：下放完成后：）：下放完成后：2021/3/1137第三步：尽量下放投影运算第三步：尽量下放投影运算SCSCE2021/3/1138第三步：尽量下放投影运算第三步：尽量下放投影运算SCSC2021/3/1139第三步（第三步（2）：第一次下放后：）：第一次下放后：SCSC2021/3/1140第三步（第三步（3）：第二次下放：）：第二次下放：SCSC2021/3/1141第三步（第三步（3）：第二次下放：）：第二次下放：SCSC2021/3/1142第三步（第三步（4）：第二次下放后：）：第二次下放后：SCSC2021/3/1143SCSC第四步：尽量把选择和投影靠在一起第四步：尽量把选择和投影靠在一起2021/3/1144第五步：分组第五步：分组SCSC2021/3/1145作业：nP275第第2题。题。即优化表达式：即优化表达式：2021/3/1146