《查询树的优化【优质分析】.ppt》由会员分享，可在线阅读，更多相关《查询树的优化【优质分析】.ppt（46页珍藏版）》请在三一文库上搜索。
1、第四章 查询优化,1,严选文书,4.1 关系数据库系统的查询处理,查询处理步骤,Select student.name from student,sc Where student.sno=sc.sno and o=2;,例：选修了2号课程的学生姓名,2,严选文书,4.1 关系数据库系统的查询处理,Select student.name 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( student.sno=sc.sno o=2 （ SC Student）,5,严选文书,4.1 关系数据库系统的查询处理,sname( student.sno=sc.sno o=2 （ SC Student）,假设有1000个学生记录，10000个选课记录，2号课
3、程的选课记录为500个。,1. 笛卡尔积计算：1000*10000 2. 选择：扫描1000*10000个记录 3. 投影,6,严选文书,4.1 关系数据库系统的查询处理,假设有1000个学生记录，10000个选课记录，2号课程的选课记录为500个。,1. 连接，采用嵌套循环：10000*1000 ，得到10000个结果 2. 选择：扫描10000个记录 3. 投影,7,严选文书,4.1 关系数据库系统的查询处理,假设有1000个学生记录，10000个选课记录，2号课程的选课记录为500个。,1. 选择：扫描10000个记录 ，得到500个记录 2. 连接，采用嵌套循环：500*1000次，得
4、到500个记录 3. 投影,选择操作先做可以提高效率。,8,严选文书,4.2 代数优化,4.2.1 关系代数表达式等价变换规则,等价的概念：,若关系表达式f（E1，E2，En）的结果与关系表达式g（E1，E2，En）的结果是同一个关系，那么称这两个表达式等价。 若关系表达式E1和E2是等价的可以记为：,9,严选文书,等价变换规则,1. 连接、笛卡儿积交换率 设E1和E2是关系代数表达式，F是连接运算的条件，则有：,10,严选文书,等价变换规则,1. 连接、笛卡儿积的结合率 设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件，则有：,11,严选文书,等价变换规则,2. 连接、笛卡儿积
5、的结合率 设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件，则有：,12,严选文书,3. 投影的串接定律,这里，E是关系代数表达式，Ai（i=1，2，n），Bj（j=1，2，m）是属性名且A1，A2， An 是B1，B2，Bm 的子集。,等价变换规则,13,严选文书,4. 选择的串接定律,等价变换规则,求IS系年龄大于岁的学生：,14,严选文书,4. 选择的串接定律,E是关系代数表达式，F1和F2是选择条件。选择的串接定律说明选择条件可以合并，这样一次就可以检查全部的条件。,等价变换规则,15,严选文书,等价变换规则,16,严选文书,5. 选择与投影的交换律,此时，条件F只涉及属
6、性组A。若条件中有不属于A的属性组B，那么有更一般的规则：,等价变换规则,17,严选文书,6.选择与笛卡尔积的交换,（1）F只涉及E1的属性。 （2）F=F1F2，且F1只涉及E1的属性，F2只涉及E2的属性。 （3） F=F1F2，且F1只涉及E1的属性，而F2涉及E1和E2的属性。,18,严选文书,(1) 实例：选修1号课程的学生信息,等价变换规则,(2) 实例：信息系选修1号课程的学生信息,19,严选文书,7. 选择与并的分配率,设E=E1E2，E1和E2有相同的属性名，则：,注：先做选择可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。,等价变换规则,20,严选文书,设S1是
7、计科041的学生关系表， S2是计科042的学生关系表：,等价变换规则,21,严选文书,8. 选择与差运算的分配率,设E1和E2有相同的属性名，则：,注：先做选择可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。,等价变换规则,22,严选文书,设S1是计科041的学生关系表， S3是计科专业的学生关系表：,等价变换规则,23,严选文书,9. 选择对自然连接的分配率,F只涉及E1和E2的公共属性。,注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也同步减少，因此减少磁盘IO量，提高了效率。,等价变换规则,24,严选文书,等价变换规则,25,严选文书,10. 投影与笛卡尔积的分配律
8、,设E1和E2是两个关系表达式，A是E1的属性组，B是E2的属性组。则：,注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。,等价变换规则,26,严选文书,查找所有学生可能的选课对：,等价变换规则,27,严选文书,11. 投影与并的分配律,设E1和E2有相同的属性名，则：,注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。,等价变换规则,28,严选文书,设S1是计科041的学生关系表， S2是计科042的学生关系表：,查找计科041、042的学生姓名：,等价变换规则,29,严选文书,优化规则：,选择运算尽可能先做。 投影运算和选择运算同时进行。 把投
9、影运算同其前后的 双目运算结合执行。 选择运算和笛卡儿积运算结合成连接运算。 找出公共子表达式，避免重复运算。,30,严选文书,4.2.2 查询树的优化,4.2 代数优化,1.查询树,S,C,SC,31,严选文书,4.2.2 优化算法,1.利用规则4分解选择运算。 2.利用规则49把选择运算尽量移到叶端。 3.利用规则3，5，10，11把投影运算尽量移到叶端。 4.利用规则35把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影的形式。使尽可能多的选择和投影同时执行。 5.分组。双目运算和他的直系祖先为一组；双目运算后代直道叶子全是单目运算时并入改组。笛卡儿积的后面若不是与之可以合
10、并的自然连接的等值选择时，其后代单独分为一组。,32,严选文书,优化实例,例：查询至少选修了一门先行课号为5号课程的学生姓名。其中，C是课程表，S是学生表，SC是学生选课表。,在优化规则中没有对自然连接的直接优化，我们把自然连接分解为笛卡儿积和选择。,33,严选文书,分解后的关系代数表达式,S,C,SC,34,严选文书,第一步：利用规则4分解选择运算,S,C,SC,35,严选文书,第二步：尽量下放选择运算,S,C,SC,36,严选文书,S,C,SC,第二步（2）：下放完成后：,37,严选文书,第三步：尽量下放投影运算,S,C,SC,E,38,严选文书,第三步：尽量下放投影运算,S,C,SC,39,严选文书,第三步（2）：第一次下放后：,S,C,SC,40,严选文书,第三步（3）：第二次下放：,S,C,SC,41,严选文书,第三步（3）：第二次下放：,S,C,SC,42,严选文书,第三步（4）：第二次下放后：,S,C,SC,43,严选文书,S,C,SC,第四步：尽量把选择和投影靠在一起,44,严选文书,第五步：分组,S,C,SC,45,严选文书,作业：,P275第2题。 即优化表达式：,46,严选文书,