第3第9章章补充查询处理和查询优化课件.ppt

1、本章内容：本章内容：1 关系数据库系统的查询处理关系数据库系统的查询处理2 关系数据库系统的查询优化关系数据库系统的查询优化3 代数优化代数优化4 物理优化物理优化第九章第九章 关系查询处理和查询优化关系查询处理和查询优化1、了解查询处理的一般步骤、了解查询处理的一般步骤2、了解为什么必须进行查询优化？、了解为什么必须进行查询优化？3、掌握关系代数的等价变换规则、掌握关系代数的等价变换规则4、掌握代数优化的算法和优化的一般步骤、掌握代数优化的算法和优化的一般步骤5、了解物理优化的内容和方法、了解物理优化的内容和方法本章要求：本章要求：一、查询处理步骤一、查询处理步骤 查询处理分为查询处理分为4

2、个阶段，在处理过程中，个阶段，在处理过程中，一旦发现问题，则报告错误，中止处理。一旦发现问题，则报告错误，中止处理。1 1 关系数据库系统的查询处理关系数据库系统的查询处理查询处理的任务：查询处理的任务：将用户提交给将用户提交给RDBMS的查询语句转换为的查询语句转换为高效的执行计划（方案）。高效的执行计划（方案）。词法分析：识别出语句中的词法分析：识别出语句中的SQL关键字、属关键字、属性名、关系名、运算符、常量等语性名、关系名、运算符、常量等语言符号。言符号。语法分析：检查语句是否符合语法分析：检查语句是否符合SQL语法规则。语法规则。(1)查询分析查询分析语义检查语义检查：根据数据字典，

3、检查语句中的数据库根据数据字典，检查语句中的数据库对象，如属性名、关系名等，是否有对象，如属性名、关系名等，是否有效。效。符号名转换：符号名转换：将外部名转换为内部名。将外部名转换为内部名。安全性检查：安全性检查：检查用户是否有请求的存取权限。检查用户是否有请求的存取权限。完整性检查：完整性检查：检查是否违反完整性约束。检查是否违反完整性约束。查询树转换查询树转换：用基于关系代数的查询树来表示查：用基于关系代数的查询树来表示查询，查询树也叫语法分析树。询，查询树也叫语法分析树。(2)查询检查查询检查(3)查询优化查询优化 从多个可能的执行方案中选择一个执行从多个可能的执行方案中选择一个执行效率

4、较高的方案。效率较高的方案。分为两个层次。分为两个层次。(4)查询执行查询执行 依据查询优化得到的结果，生成执行代依据查询优化得到的结果，生成执行代码，执行之。码，执行之。代数优化：代数优化：按照一定的规则，改变代数表达按照一定的规则，改变代数表达式中关系操作的次序和组合，使式中关系操作的次序和组合，使执行效率更高，又称逻辑优化。执行效率更高，又称逻辑优化。物理优化物理优化：依据事先确定的策略，选择底层：依据事先确定的策略，选择底层存取路径和算法。存取路径和算法。二、实现查询操作的算法举例二、实现查询操作的算法举例1.选择操作的实现选择操作的实现Select*from student wher

5、e；考虑考虑的几种情况：的几种情况：C1:无条件；无条件；C2:Sno=200215121；C3：Sage20;C4:Sdept=CS AND Sage20;二、实现查询操作的算法举例二、实现查询操作的算法举例1.选择操作的实现选择操作的实现(1)简单的全表扫描方法简单的全表扫描方法 对查询基本表顺序扫描，逐一检查每个元组是否对查询基本表顺序扫描，逐一检查每个元组是否满足选择的条件，对满足条件的元组作为结果输满足选择的条件，对满足条件的元组作为结果输出。对于小表，简单有效。对于大表，费时。出。对于小表，简单有效。对于大表，费时。(2)索引或散列扫描方法索引或散列扫描方法 如果选择条件中的属性上

6、有索引（如果选择条件中的属性上有索引（B+树索引或树索引或Hash索引），可以用索引扫描方法。通过索引先索引），可以用索引扫描方法。通过索引先找到满足条件的元组的主码或元组指针，再通过找到满足条件的元组的主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。元组指针直接在查询的基本表中找到元组。二、实现查询操作的算法举例二、实现查询操作的算法举例2.连接操作的实现连接操作的实现Select*from Student,Sc Where Student.Sno=SC.sno(1)嵌套循环方法嵌套循环方法 对于外层循环对于外层循环(Student)的每个元组的每个元组(s),检检索内层循环索内

7、层循环(SC)中的每个元组中的每个元组(sc)，并检查这，并检查这两个元组在连接属性两个元组在连接属性(sno)上是否相等。如果上是否相等。如果满足连接条件，则串接后作为结果输出，直到满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。外层循环表中的元组处理完为止。二、实现查询操作的算法举例二、实现查询操作的算法举例(2)排序排序-合并方法合并方法 如果连接的表没有排好序，则将如果连接的表没有排好序，则将Student和和SC表按表按连接属性连接属性Sno排序；排序；取取Student表中的第一个表中的第一个Sno，依次扫描，依次扫描SC表中具表中具有相同有相同Sno的元组，

8、把它们连接起来；的元组，把它们连接起来；当扫描到当扫描到Sno不相同的第一个不相同的第一个SC元组时，返回元组时，返回Student表扫描下一个元组，再扫描表扫描下一个元组，再扫描SC表中具有相同表中具有相同Sno的元组，把它们连接起来。的元组，把它们连接起来。重复上述步骤直到重复上述步骤直到Student表扫描完。表扫描完。二、实现查询操作的算法举例二、实现查询操作的算法举例(3)索引连接方法索引连接方法在在SC表上建立属性表上建立属性Sno的索引，如果原来没的索引，如果原来没有的话；有的话；对对Student表中的每一个元组，由表中的每一个元组，由Sno的值通的值通过过SC的索引查找相应的

9、的索引查找相应的SC元组；元组；把这些把这些SC元组和元组和Student元组连接起来。元组连接起来。循环执行、循环执行、；直到；直到Student表中的元表中的元组处理完为止。组处理完为止。二、实现查询操作的算法举例二、实现查询操作的算法举例(4)Hash Join方法方法把连接属性作为把连接属性作为hash码，用同一个码，用同一个hash函数把函数把R和和S中的元组散列到同一个中的元组散列到同一个hash文件中。文件中。划分阶段：划分阶段：对包含较少元组的表对包含较少元组的表(比如比如R)进行进行一遍处理，把它的元组按一遍处理，把它的元组按hash函数分散到函数分散到hash表的桶中；表的

10、桶中；试探阶段：试探阶段：对另一个表对另一个表(S)进行一遍处理，把进行一遍处理，把S的元组散列到适当的的元组散列到适当的hash桶中，并将元组与桶桶中，并将元组与桶中所有来自中所有来自R并与之匹配的元组连接起来。并与之匹配的元组连接起来。2 2 关系数据库系统的查询优化关系数据库系统的查询优化 关系数据语言只需用户提出关系数据语言只需用户提出“做什么做什么”，不必，不必指出指出“怎么做怎么做”，为什么能做到这一点？，为什么能做到这一点？一个重要原因就是一个重要原因就是系统能自动进行查询优化系统能自动进行查询优化。系统自动优化比用户自己优化会做得更好，系统自动优化比用户自己优化会做得更好，见见

11、P267。在集中式数据库中，查询执行的总代价在集中式数据库中，查询执行的总代价(开销开销)为：为：总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价 三者中，三者中，I/O代价是最主要的。代价是最主要的。查询优化的总目标：查询优化的总目标：选择有效的策略，求得给定的关系表达式的值，选择有效的策略，求得给定的关系表达式的值，使得查询代价较小。使得查询代价较小。例：例：求选修了求选修了2号课程的学生姓名。其号课程的学生姓名。其SQL语句为：语句为：SELECT 姓名姓名 FROM Student,SCWHERE Student.学号学号=SC.学号学号 AND 课号课号=2;为什么要进

12、行查询优化？为什么要进行查询优化？也可用也可用SQL语言如下实现语言如下实现:SELECT 姓名姓名 FROM Student WHERE 学号学号 IN (SELECT 学号学号 FROM SC WHERE 课号课号=2);对于一个复杂的查询，不同用户可能会写对于一个复杂的查询，不同用户可能会写出各种不同的查询方法。这些方法有的简单，出各种不同的查询方法。这些方法有的简单，有的复杂。它们的执行结果是一样的，但执行有的复杂。它们的执行结果是一样的，但执行效率可能是不一样的。系统能解决这一问题吗？效率可能是不一样的。系统能解决这一问题吗？对这一查询，可以考虑下面几种实现方式：对这一查询，可以考虑

13、下面几种实现方式：1、先求、先求Student和和SC的笛卡尔积，然后从中选出两学的笛卡尔积，然后从中选出两学号字段值相等、课程号为号字段值相等、课程号为2的元组，再投影姓名。的元组，再投影姓名。Q1=姓名姓名(Student.学号学号=SC.学号学号课号课号=2(Student SC)2、先做、先做Student和和SC的自然连接，然后从中选出课程的自然连接，然后从中选出课程号为号为2的元组，再投影姓名。的元组，再投影姓名。Q2=姓名姓名（课号课号=2（Student SC）3、先从、先从SC中选出课程号为中选出课程号为2的元组，然后将该结果与的元组，然后将该结果与Student 连接，再投

14、影姓名。连接，再投影姓名。Q3=姓名姓名（Student 课号课号=2（SC）分析三种实现策略的执行时间：分析三种实现策略的执行时间：设有设有1000个学生记录，个学生记录，10000个选课记录，个选课记录，选修选修2号课程的学生有号课程的学生有50名。名。1、第一种策略：、第一种策略：Q1=姓名姓名(Student.学号学号=SC.学号学号课号课号=2(Student SC)（1）计算广义笛卡尔积）计算广义笛卡尔积 Student SC：执行方式：执行方式：读读Student若干块和若干块和SC的的1块到内存，块到内存，然后执行连接，结果装满然后执行连接，结果装满1块后就立即写入磁盘的临块后

15、就立即写入磁盘的临时文件中，当内存中的时文件中，当内存中的Student记录与记录与SC记录全部连记录全部连接后，再读入接后，再读入SC的下一块，继续连接，直到的下一块，继续连接，直到SC的所的所有记录与内存中的有记录与内存中的Student都连接，再读入都连接，再读入Student的的另若干块，重复上面的过程。另若干块，重复上面的过程。设一块能装设一块能装10个个Student记录或记录或100个个SC记录。记录。则则Student的总块数为的总块数为 1000/10=100 块，块，SC的总的总块数为块数为 10000/100=100 块块 若每次在内存中装入若每次在内存中装入5块块Stu

16、dent记录和记录和1块块SC的的记录，则记录，则Student被读取被读取1遍，遍，SC被读取被读取 100/5=20 遍。读取两表的总块数为遍。读取两表的总块数为 100+100 20=2100块块 连接结果为连接结果为1000*10000=1000 0000个记录，若个记录，若每块可装每块可装10个结果记录，共需写入磁盘个结果记录，共需写入磁盘1000 0000/10=100 0000块。块。若每秒可读写若每秒可读写20块，则读、写总时间分别为：块，则读、写总时间分别为：2100/20=105 秒秒 100 0000/20=50000 秒秒（2）依次读入）依次读入Student SC的记

17、录，然后执行的记录，然后执行选择。选择。读的时间：读的时间：100 0000/20=50000秒秒 满足条件的记录为满足条件的记录为50个，全部放入内存，个，全部放入内存，不再临时存储。不再临时存储。（3）在上步基础上执行投影得最终结果（此）在上步基础上执行投影得最终结果（此步时间不计）。步时间不计）。第一种策略的总时间为：第一种策略的总时间为：105+50000+50000 10万秒（近万秒（近28小时）小时）2、第二种策略、第二种策略（1）计算自然连接）计算自然连接 读取读取Student表和表和SC表的策略不变，执行时间还表的策略不变，执行时间还是是2100/20=105秒秒。因为因为S

18、C表中的每一个学号都在表中的每一个学号都在Student表中出现，表中出现，而而Student表中无重复学号，故连接后的结果和表中无重复学号，故连接后的结果和SC表表的行数一样，为的行数一样，为10000行，将它们临时存入盘中需行，将它们临时存入盘中需（10000/10）块）块/20块块/秒秒=50秒秒计算自然连接需时：计算自然连接需时：105+50=155秒秒Q2=姓名姓名（课号课号=2（Student SC）（2）执行选择运算）执行选择运算 将存储在磁盘上临时文件中的自然连接结将存储在磁盘上临时文件中的自然连接结果，读入内存进行选择，结果为果，读入内存进行选择，结果为50个记录，不个记录，

19、不再临时存储。再临时存储。主要为读取自然连接结果的时间：为主要为读取自然连接结果的时间：为50秒秒（3）把上一步结果投影，时间忽略不计）把上一步结果投影，时间忽略不计第二种策略的总时间为：第二种策略的总时间为：155+50=205秒秒3、第三种策略、第三种策略（1）先对）先对SC表作选择表作选择 只需读一遍只需读一遍SC表，需时表，需时 100块块/20块块/秒秒=5秒秒 中间结果只有中间结果只有50个记录，不需使用中间文件个记录，不需使用中间文件（2）作自然连接）作自然连接 只需读一遍只需读一遍Student表，边读边和内存中的中间结表，边读边和内存中的中间结果连接，结果仍为果连接，结果仍为

20、50个元组，需时个元组，需时 5 秒秒Q3=姓名姓名（Student 课号课号=2（SC）（3）把上一步结果投影，时间忽略不计）把上一步结果投影，时间忽略不计第三种策略的总时间为：第三种策略的总时间为：5+5=10 秒秒结论：不同的查询策略其执行时间可能差别很大结论：不同的查询策略其执行时间可能差别很大说明：说明：刚才使用的是全表扫描的方法，比较费时，刚才使用的是全表扫描的方法，比较费时，如果在选择字段和连接字段上建立了适当的索如果在选择字段和连接字段上建立了适当的索引，就可以减少记录的读取量，从而降低查询引，就可以减少记录的读取量，从而降低查询开销。这就是存取路径选择问题，由物理优化开销。这

21、就是存取路径选择问题，由物理优化解决。解决。总结：总结：通过刚才的例子可知，前两种策略的中间通过刚才的例子可知，前两种策略的中间结果集（笛卡尔积和自然连接）包含了许多对结果集（笛卡尔积和自然连接）包含了许多对查询结果无用的记录，造成结果集太大，不得查询结果无用的记录，造成结果集太大，不得不进行磁盘缓存处理，从而使得花费时间较多。不进行磁盘缓存处理，从而使得花费时间较多。由此启发我们，在查询处理时，应尽可能由此启发我们，在查询处理时，应尽可能早地去掉对查询结果没有用的数据（记录或字早地去掉对查询结果没有用的数据（记录或字段），以降低中间结果集的规模，这可通过优段），以降低中间结果集的规模，这可通

22、过优先执行一元运算（选择和投影）来实现，象第先执行一元运算（选择和投影）来实现，象第三种策略那样。三种策略那样。3 3 代数优化代数优化一、关系代数表达式等价变换规则一、关系代数表达式等价变换规则 设设E1、E2是关系代数表达式。若用相同是关系代数表达式。若用相同的关系代替的关系代替E1、E2中相应的关系所得到的结中相应的关系所得到的结果相同，则称果相同，则称E1、E2等价，记作等价，记作 E1 E2。1、投影的串接定律（幂等律）、投影的串接定律（幂等律）A1,A2,An(B1,B2,Bm(E)A1,A2,An(E)其中其中A1,A2,An B1,B2,Bm例：例：姓名姓名(学号，姓名学号，姓

23、名(Student)姓名姓名(Student)2、选择的串接定律（幂等律）、选择的串接定律（幂等律）F1（F2（E）F1 F2（E）性别性别=男男(年龄年龄20(Student)性别性别=男男 年龄年龄20(Student)3、连接、笛卡尔积的交换律、连接、笛卡尔积的交换律笛卡尔积：笛卡尔积：E1 E2 E2 E1自然连接：自然连接：E1 E2 E2 E1一般连接：一般连接：E1 E2 E2 E1FF4、连接、笛卡尔积的结合律、连接、笛卡尔积的结合律笛卡尔积：笛卡尔积：(E1 E2)E3 E1 (E2 E3)自然连接：自然连接：(E1 E2)E3 E1 (E2 E3)一般连接：一般连接：(E1

24、 E2)E3 E1 (E2 E3)F1F2F1F25、选择与投影的交换律、选择与投影的交换律 F(A1,A2,An(E)A1,A2,An(F(E)其中其中F只涉及只涉及A1,A2,An中的属性中的属性例：例：性别性别=男男(学号，姓名，性别学号，姓名，性别(Student)学号，姓名，性别学号，姓名，性别(性别性别=男男(Student)若若F中有不属于中有不属于A1,A2,An的属性的属性B1,B2,Bm，则则 A1,A2,An(F(E)A1,A2,An(A1,A2,An,B1,B2,Bm(F(E)A1,A2,An(F(A1,A2,An,B1,B2,Bm(E)例：例：学号，姓名学号，姓名(性

25、别性别=男男(Student)学号，姓名学号，姓名 性别性别=男男(学号，姓名，性别学号，姓名，性别(Student)6、选择与笛卡尔积的交换律（分配律）、选择与笛卡尔积的交换律（分配律）设设F=F1F2F3，其中，其中F1只涉及只涉及E1中的中的属性，属性，F2只涉及只涉及E2中的属性，中的属性，F3涉及涉及E1和和E2两者中的属性，两者中的属性，则则 F(E1 E2)F3(F1 E1 F2 E2)如果某个如果某个Fi不存在，则去掉相应的不存在，则去掉相应的 Fi。例：例：Student.学号学号=SC.学号学号成绩成绩60(Student SC)Student.学号学号=SC.学号学号(S

26、tudent 成绩成绩=90(Student SC)性别性别=男男 Student 成绩成绩=90 SC8、选择对并、交、差的分配律、选择对并、交、差的分配律 F(E1 E2)F E1 F E2 F(E1 E2)F E1 F E2 F(E1-E2)F E1 -F E29、投影对笛卡尔积的分配律、投影对笛卡尔积的分配律 设设A1,A2,，An是是E1的属性，的属性，B1,B2,，Bm是是E2的属性，则的属性，则 A1,A2,An,B1,B2,Bm(E1 E2)A1,A2,An E1 B1,B2,Bm E210、投影对并、交、差的分配律、投影对并、交、差的分配律 A(E1 E2)A E1 A E2

27、 A(E1 E2)A E1 A E2 A(E1-E2)A E1 -A E2二、查询树的启发式优化二、查询树的启发式优化1、启发式规则、启发式规则（1）一元运算应尽可能先做。这样可及时丢）一元运算应尽可能先做。这样可及时丢掉对查询结果无用的记录或字段，极大地减掉对查询结果无用的记录或字段，极大地减小中间结果集。小中间结果集。（2）将选择、投影及其前后的笛卡尔积、连）将选择、投影及其前后的笛卡尔积、连接运算同时进行。这样可减少对关系的扫描接运算同时进行。这样可减少对关系的扫描遍数和中间结果的存储量。遍数和中间结果的存储量。（3）找出公共子表达式，将计算结果临时保）找出公共子表达式，将计算结果临时保

28、存，再遇到该表达式时，不再计算，直接使存，再遇到该表达式时，不再计算，直接使用保存的结果。用保存的结果。2、关系代数语法树、关系代数语法树 用来表示关系代数表达式的一棵树，其内结点用来表示关系代数表达式的一棵树，其内结点表示一种运算，叶结点表示一个关系。如：表示一种运算，叶结点表示一个关系。如：SELECT 姓名姓名 FROM Student，SC WHERE Student.学号学号=SC.学号学号 AND 课号课号=2；姓名姓名 Student.学号学号=SC.学号学号 课号课号=2StudentSC方法：方法：将目标列转换为投影，将目标列转换为投影，将将WHERE中的条件转换为中的条件转

29、换为选择，将选择，将FROM后的表用笛后的表用笛卡尔积连接起来。卡尔积连接起来。也可转换为自然连接。也可转换为自然连接。课号课号=23、关系代数表达式的优化算法、关系代数表达式的优化算法输入：一棵关系代数表达式的语法树输入：一棵关系代数表达式的语法树输出：优化的语法树输出：优化的语法树 利用选择的串接定律，把形如利用选择的串接定律，把形如 F1 F2Fn（E）的式子变换为）的式子变换为 F1(F2(Fn(E)（1）分解选择）分解选择 对每一个选择，利用对每一个选择，利用“选择的串接定律、选择的串接定律、选择与投影的交换律、选择对笛卡尔积的分配选择与投影的交换律、选择对笛卡尔积的分配律、选择对自

30、然连接的分配律、选择对并、交、律、选择对自然连接的分配律、选择对并、交、差的分配律差的分配律”尽可能把它移到树的叶端。尽可能把它移到树的叶端。（2）选择下移）选择下移 对每一个投影，利用对每一个投影，利用“投影的串接定律、投影的串接定律、选择与投影的交换律、投影对笛卡尔积的分配选择与投影的交换律、投影对笛卡尔积的分配律、投影对并、交、差的分配律律、投影对并、交、差的分配律”尽可能把它尽可能把它移到树的叶端。移到树的叶端。（3）投影下移）投影下移（1）分解选择）分解选择（2）选择下移）选择下移 利用利用“投影的串接定律、选择的串接定律、投影的串接定律、选择的串接定律、选择与投影的交换律选择与投影

31、的交换律”把选择和投影合并成单把选择和投影合并成单个选择、单个投影、或选择后跟投影等三种情个选择、单个投影、或选择后跟投影等三种情况，使多个选择和况，使多个选择和/或投影能同时执行、或在或投影能同时执行、或在一次扫描中完成。一次扫描中完成。（4）选择、投影合并）选择、投影合并（3）投影下移）投影下移（1）分解选择）分解选择（2）选择下移）选择下移 把上面得到的语法树分组：把上面得到的语法树分组：每个二元运算和它的每个二元运算和它的 一元直接祖先一元直接祖先 为一组。为一组。若它的后代直到叶子全是一元运算，则也将它若它的后代直到叶子全是一元运算，则也将它们并入该组。们并入该组。（5）按点分组（每

32、组只有一个二元运算）按点分组（每组只有一个二元运算）不超过别的不超过别的二元运算结点二元运算结点 但对于笛卡尔积，若后面（父结点）是不但对于笛卡尔积，若后面（父结点）是不能与它结合为等值连接的选择运算时，其一直能与它结合为等值连接的选择运算时，其一直到叶子的一元运算结点需单独算一组。到叶子的一元运算结点需单独算一组。例：考虑由以下关系组成的图书馆数据库例：考虑由以下关系组成的图书馆数据库BOOKS（书名，作者，出版社，编号）（书名，作者，出版社，编号）BORROWERS（姓名，单位，证号）（姓名，单位，证号）LOANS（证号，编号，借阅日期）（证号，编号，借阅日期）找出找出2007年年12月月

33、01日前借出书籍的书名和借阅人姓名。日前借出书籍的书名和借阅人姓名。用用SQL 语言可表达如下：语言可表达如下：SELECT 书名，姓名书名，姓名 FROM BOOKS，BORROWERS，LOANS WHERE BOOKS.编号编号=LOANS.编号编号 AND BORROWERS.证号证号=LOANS.证号证号 AND 借阅日期借阅日期 2007-12-01;上述上述SQL语句可转化为如下关系代数表达式：语句可转化为如下关系代数表达式：书名，姓名书名，姓名(借阅日期借阅日期2007-12-01 (BOOKS（BORROWERS LOANS)或或 书名，姓名书名，姓名(借阅日期借阅日期200

34、7-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 (BOOKS(BORROWERS LOANS)通常先转化为后一种形式，在优化的后通常先转化为后一种形式，在优化的后期会将笛卡尔积转换为自然连接。期会将笛卡尔积转换为自然连接。书名，姓名书名，姓名 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号上述表达式的语法树上述表达式的语法树 LOANS BOOKS BORROWERS根据算法第根据算法第1步，步，分解该选择分解该选择第第1步优化（分解选择）后的语

35、法树步优化（分解选择）后的语法树 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2005-10-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 分解之后分解之后根据算法第根据算法第2步，步，该选择可下移该选择可下移 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROW

36、ERS.证号证号=LOANS.证号证号 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 该选择已不能下移该选择已不能下移该选择也不能下移该选择也不能下移将该选择下移将该选择下移交换交换 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 交换后交换后继续下移继续下移 书名，姓名书名，姓名 LOANS

37、 BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 交换交换 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 继续下移继续下移 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 OK

38、第第2步优化（选择下移）后的语法树步优化（选择下移）后的语法树该投影能否与选择交换？该投影能否与选择交换？不能！不能！怎么办？怎么办？利用投影的幂等律插入一个投影利用投影的幂等律插入一个投影算法第算法第3步，投影下移步，投影下移 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 书名，姓名，书名，姓名，BOOKS.编号，编号，LOANS.编号编号交换交换 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-

39、12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 书名，姓名，书名，姓名，BOOKS.编号，编号，LOANS.编号编号对笛卡尔分配对笛卡尔分配 书名，书名，BOOKS.编号编号 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 姓名，姓名，LOANS.编号编号OK还需下移还需下移 书名，书名，BOOKS.编号编号 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借

40、阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 姓名，姓名，LOANS.编号编号插入一个投影插入一个投影 姓名，姓名，LOANS.编号，编号，BORROWERS.证号，证号，LOANS.证号证号 下移下移 书名，书名，BOOKS.编号编号 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 姓名，姓名，LOANS.编号编号 姓名，姓名，LOANS.编号，编号，BORROWE

41、RS.证号，证号，LOANS.证号证号 对笛卡尔分配对笛卡尔分配 LOANS.编号，编号，LOANS.证号证号 姓名，姓名，BORROWERS.证号证号 书名，书名，BOOKS.编号编号 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 姓名，姓名，LOANS.编号编号第第3步优化（投影下步优化（投影下移）后的语法树移）后的语法树 LOANS.编号，编号，LOANS.证号证号 姓名，姓名，BORROWERS.证号证号 书名，书名，BOOKS.编号

42、编号 书名，姓名书名，姓名 LOANS BOOKS BORROWERS 借阅日期借阅日期2007-12-01 BOOKS.编号编号=LOANS.编号编号 BORROWERS.证号证号=LOANS.证号证号 姓名，姓名，LOANS.编号编号第第4步优化（选择、步优化（选择、投影合并）投影合并）本例不需要。本例不需要。第第5步优化（节点步优化（节点分组）分组）4 4 物理优化物理优化 物理优化是在代数优化的基础上，选择合理的算物理优化是在代数优化的基础上，选择合理的算法或存取路径（数据存取方法），生成优化的查询计法或存取路径（数据存取方法），生成优化的查询计划（可执行程序）。划（可执行程序）。代数

43、优化得到的组是一个代数优化得到的组是一个计算单元计算单元，物理优化时，物理优化时，先为每组生成一个计算方案，然后再按从叶到根的顺先为每组生成一个计算方案，然后再按从叶到根的顺序将它们逻辑组织起来，生成完整的查询计划。当包序将它们逻辑组织起来，生成完整的查询计划。当包含根的一组操作执行完毕时，查询完成。含根的一组操作执行完毕时，查询完成。算法或存取路径的选择依赖于算法或存取路径的选择依赖于操作的种类操作的种类（选择、（选择、连接等）、连接等）、是否建立索引是否建立索引、是什么样的索引是什么样的索引（HASH索引、索引、B+树索引等）等因素。见树索引等）等因素。见9.1.29.1.2。物理优化通常

44、采用物理优化通常采用启发式规则启发式规则和和代价估算代价估算相结相结合的策略。即先用启发式规则产生几个候选方案，然合的策略。即先用启发式规则产生几个候选方案，然后通过代价估算，选择较优的一个。后通过代价估算，选择较优的一个。启发式规则是人们从实践中总结出的一些效率可启发式规则是人们从实践中总结出的一些效率可能较高的方法。例如对于小表上的选择操作，使用全能较高的方法。例如对于小表上的选择操作，使用全表顺序扫描优于索引扫描等。表顺序扫描优于索引扫描等。代价估算是针对某个可能的查询方案，根据数据代价估算是针对某个可能的查询方案，根据数据库的统计信息（如记录条数、记录长度、选择率、列库的统计信息（如记

45、录条数、记录长度、选择率、列中不同值的个数等），按一定的公式计算其代价（通中不同值的个数等），按一定的公式计算其代价（通常为花费时间）常为花费时间）。然后比较各个方案的代价，选择代。然后比较各个方案的代价，选择代价较小的一个方案。价较小的一个方案。物理优化涉及的启发式规则和算法、公式，物理优化涉及的启发式规则和算法、公式，可能达数百种之多，在此不再详细介绍。可能达数百种之多，在此不再详细介绍。作业：作业：2、3、4由由DBMSDBMS进行查询优化的好处进行查询优化的好处(1)优化器可以从数据字典中获取许多统计信息，优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。而用户程序则难以获得这些信息。(2)如果数据库的物理统计信息改变了，系统可以如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。实际应用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行计划，而程优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。序员一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术优化器中包括了很多复杂的优化技术返回返回