第九章关系查询处理和查询优化

1、第九章第九章 关系查询处理和查询优化关系查询处理和查询优化9.1 9.1 关系数据库系统的查询处理关系数据库系统的查询处理9.2 9.2 关系系统的查询优化关系系统的查询优化9.3 9.3 代数优化代数优化9.4 9.4 物理优化物理优化数据库系统概论2查询处理的步骤查询处理的步骤 ：q查询分析查询分析q查询检查查询检查q查询优化查询优化q查询执行查询执行9.1 9.1 关系数据库系统的查询处理关系数据库系统的查询处理数据库系统概论31.1.查询分析查询分析：对查询语句进行：对查询语句进行扫描、词法分析和语法分析扫描、词法分析和语法分析2.2.查询检查查询检查：根据数据字典对：根据数据字典对合

2、法的查询语句进行语义检查，合法的查询语句进行语义检查，即检查语句中的数据库对象，即检查语句中的数据库对象，如属性名、关系名，是否存在如属性名、关系名，是否存在和是否有效，和是否有效，RDBMSRDBMS一般都通一般都通过查询树或语法分析树来表示过查询树或语法分析树来表示扩展的关系代数表达式扩展的关系代数表达式( (在这在这个过程中要把数据库对象的外个过程中要把数据库对象的外部名称转换为内部表示部名称转换为内部表示) )查询语句查询语句词法分析词法分析语法分析语法分析语义分析语义分析符号名转换符号名转换安全性检查安全性检查完整性检查完整性检查查询树查询树代数优化代数优化物理优化等物理优化等执行策

3、略描述执行策略描述代码生成代码生成查询计划的执行代码查询计划的执行代码数据库数据库数据字典数据字典查询分析查询分析查询检查查询检查查询优化查询优化查询执行查询执行查询处理步骤查询处理步骤数据库系统概论43.3.查询优化查询优化：选择一个高效：选择一个高效执行的查询处理策略执行的查询处理策略( (代数代数优化和物理优化优化和物理优化) )4.4.查询执行：查询执行：依据优化器得依据优化器得到的执行策略生成查询计划，到的执行策略生成查询计划，则代码生成器生成执行这个则代码生成器生成执行这个查询计划的代码查询计划的代码查询语句查询语句词法分析词法分析语法分析语法分析语义分析语义分析符号名转换符号名转

4、换安全性检查安全性检查完整性检查完整性检查查询树查询树代数优化代数优化物理优化等物理优化等执行策略描述执行策略描述代码生成代码生成查询计划的执行代码查询计划的执行代码数据库数据库数据字典数据字典查询分析查询分析查询检查查询检查查询优化查询优化查询执行查询执行查询处理步骤查询处理步骤数据库系统概论59.1.2 实现查询操作的算法示例一、选择操作的实现一、选择操作的实现 1.1.简单的全表扫描方法简单的全表扫描方法 对查询的基本表顺序扫描，逐一检查每个元组是否满足选对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出。择条件，把满足条件的元组作为结果输出。对于小表

5、，这种方对于小表，这种方法简单有效，对于大表来讲，其顺序扫描十分费时，效率很低法简单有效，对于大表来讲，其顺序扫描十分费时，效率很低 2.2.索引索引( (或散列或散列) )扫描方法扫描方法 如果选择条件中的属性上有索引，可以用索引扫描方法。如果选择条件中的属性上有索引，可以用索引扫描方法。通过索引先找到满足条件的元组主码或元组指针，再通过元组通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组指针直接在查询的基本表中找到元组数据库系统概论6 例例11 Select Select * * from student where from student wher

6、e ; 这里条件表达式可能有以下几种情况：这里条件表达式可能有以下几种情况：1.C11.C1：无条件：无条件2.C2: Sno=2002151212.C2: Sno=2002151213.C3: Sage203.C3: Sage204.C4: Sdept=CS AND Sage204.C4: Sdept=CS AND Sage20以以C2C2为例：条件：为例：条件：Sno=200215121Sno=200215121，且，且SnoSno上有索引上有索引( (或散或散列列) ) ，则可以使用索引，则可以使用索引( (或散列或散列) )得到得到SnoSno为为200215121200215121元

7、组元组的指针，然后通过元组指针在的指针，然后通过元组指针在studentstudent表中检索到该学生表中检索到该学生以以C3C3为例：条件：为例：条件： Sage20 Sage20 ，且，且SageSage上有索引，则可以使用上有索引，则可以使用B+B+树索引找到树索引找到Sage=20Sage=20的索引项，以此为入口点在的索引项，以此为入口点在B+B+树的顺序树的顺序集上得到集上得到Sage20 Sage20 的所有元组指针，然后通过元组指针在的所有元组指针，然后通过元组指针在studentstudent表中检索到年龄大于表中检索到年龄大于2020的学生的学生数据库系统概论7二、连接操作

8、的实现二、连接操作的实现 例例22 select select * * from Student,SC from Student,SC where Student.Sno=Sc.Sno; where Student.Sno=Sc.Sno;1.1.嵌套循环方法嵌套循环方法 最简单可行的算法最简单可行的算法。对外层循环的每一个元组，检索内。对外层循环的每一个元组，检索内层循环中的每一个元组，并检查这两个元组在连接属性上是层循环中的每一个元组，并检查这两个元组在连接属性上是否相等。如果满足连接条件，则串接后作为结果输出，直到否相等。如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完

9、为止外层循环表中的元组处理完为止数据库系统概论82.2.排序排序- -合并方法合并方法(1)(1)首先对首先对StudentStudent表和表和SCSC表按连接属性表按连接属性SnoSno排序排序 (2)(2)取取StudentStudent表中第一个表中第一个Sno,Sno,依次扫描依次扫描SCSC表中具有相同表中具有相同SnoSno的的元组，把它们连接起来元组，把它们连接起来 (3)(3)当扫描到当扫描到SnoSno不相同的第一个不相同的第一个SCSC元组时，返回元组时，返回StudentStudent表扫表扫描它的下一个元组，再扫描描它的下一个元组，再扫描SCSC表中具有相同表中具有相

10、同SnoSno的元组，把它的元组，把它们连接起来。们连接起来。 重复上述步骤直到重复上述步骤直到StudentStudent表扫描完。表扫描完。这样这样StudentStudent表和表和SCSC表也只要扫描一遍。当然，执行时间要加表也只要扫描一遍。当然，执行时间要加上对两个表的排序时间。即使这样，使用预处理方法执行连上对两个表的排序时间。即使这样，使用预处理方法执行连接的时间一般仍大大减少接的时间一般仍大大减少95001 1 9295001 1 9295001 2 8595001 2 8595001 3 8895001 3 8895002 2 9095002 2 9095002 3 8095

11、002 3 809500195001950029500295003950039500495004数据库系统概论93.3.索引连接方法索引连接方法1.1.在在SCSC表上建立属性表上建立属性SnoSno的索引；的索引；2.2.对对StudentStudent中每一个元组，由中每一个元组，由SnoSno值通过值通过SCSC的索引查找相应的索引查找相应的的SCSC元组元组3.3.把这些把这些SCSC元组和元组和StudentStudent元组连接起来元组连接起来4.Hash Join4.Hash Join方法方法 把连接属性作为把连接属性作为hashhash码，用同一个码，用同一个hashhash函

12、数把函数把R R和和S S中的中的元组散列到同一个元组散列到同一个hashhash文件中。文件中。数据库系统概论109.2 关系系统的查询优化 9.2.1 查询优化概述查询优化的必要性查询优化的必要性查询优化极大地影响查询优化极大地影响RDBMSRDBMS的性能。的性能。查询优化的可能性查询优化的可能性关系数据语言的级别很高，使关系数据语言的级别很高，使DBMSDBMS可以从关系表达式中可以从关系表达式中分析查询语义。分析查询语义。 数据库系统概论11由由DBMSDBMS进行查询优化的好处进行查询优化的好处 用户不必考虑如何最好地表达查询以获得较好的效率，知道用户不必考虑如何最好地表达查询以获

13、得较好的效率，知道“干什么干什么”，不用知道，不用知道“怎么干怎么干” 系统可以比用户程序的系统可以比用户程序的优化优化做得更好做得更好(1) 优化器可以从数据字典中获取许多统计信息，而用户程优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息序则难以获得这些信息 (2)如果数据库的物理统计信息改变了，系统可以自动对查如果数据库的物理统计信息改变了，系统可以自动对查询询重新优化重新优化以选择相适应的执行计划，在非关系系统中必以选择相适应的执行计划，在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的须重写程序，而重写程序在实际应用中往往是不太可能的(3)优化器可以

14、考虑数百种不同的执行计划，而程序员一般优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性只能考虑有限的几种可能性(4)优化器中包括了很多复杂的优化技术优化器中包括了很多复杂的优化技术数据库系统概论12查询优化的总目标查询优化的总目标 选择有效策略，求得给定关系表达式的值，使得查询代价较选择有效策略，求得给定关系表达式的值，使得查询代价较小小代价模型代价模型集中式数据库集中式数据库单用户系统 总代价总代价 = I/O代价代价 + CPU代价代价多用户系统总代价总代价 = I/O代价代价 + CPU代价代价 + 内存代价内存代价分布式数据库分布式数据库 总代价总代价 = I/

15、O代价代价 + CPU代价代价+ 内存代价内存代价 + 通信代价通信代价 数据库系统概论139.2.2 一个实例（说明查询优化的好处） 例：例：列出所有选修课程列出所有选修课程2的学生姓名。的学生姓名。 SELECT DISTINCT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2; 数据库系统概论14假设1：外存：Student:1000条条,SC:10000条条, 选修选修2号课程号课程:50条条假设2：一个内存块装元组:10个Student, 或100个SC, 内存中一次可以存放: 5块Studen

16、t元组, 1块SC元组和若干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于数据块的嵌套循环法数据库系统概论15执行策略执行策略1 1：1=name(Student.Sno=SC.Sno SC.Cno=2 (StudentSC) StudentSC 读取总块数= 读Student表块数 + 读SC表遍数 *每遍块数 =1000/10+(1000/(105) (10000/100) =100+20100=2100 读数据时间=2100/20=105秒数据库系统概论16不同的执行策略,考虑I/O时间中间结果大小 = 103*104 = 107 (1千万条元组)写中间结果时间 = 1

17、07/10/20 = 50000秒 : 读数据时间 = 50000秒 总时间 =1055000050000 = 100105秒= 27.8小时数据库系统概论172 name(SC.Cno= 2 (Student SC)读取总块数= 2100块读数据时间=2100/20=105秒中间结果大小=10000 （减少1000倍）写中间结果时间=10000/10/20=50秒 读数据时间=50秒 总时间1055050秒205秒=3.4分 执行策略执行策略2 2：数据库系统概论183 Sname(Student SC.Cno= 2 (SC) 读SC表总块数= 10000/100=100块读数据时间=100

18、/20=5秒 中间结果大小=50条 不必写入外存 读Student表总块数= 1000/10=100块读数据时间=100/20=5秒 总时间55秒10秒 执行策略执行策略3 3：数据库系统概论19把代数表达式Q1变换为Q2、Q3，即有选择和连接操作时，应当先做选择操作，后执行连接，尽量减少中间结果的读取时间，加快连接操作的处理在Q3中，SC表的选择操作算法有全表扫描和索引扫描两种方法，经过初步估算，索引扫描方法较优。同样对于Student和SC表的连接，利用Student表上的索引，采用index join代价也较小代数优化代数优化物理优化物理优化总结：总结：数据库系统概论209.3 代数优化

19、 代数优化：基于关系代数系统等价变换规则的优化方法代数优化策略是通过对关系代数表达式的等价变换来提高查询效率关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的两个关系表达式E1和E2是等价的，可记为： E1 E2数据库系统概论219.3.1 关系代数表达式等价变换规则设E1、E2等是关系代数表达式，F是条件表达式 规则1. 连接、笛卡尔积交换律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1 规则2. 连接、笛卡尔积的结合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E

20、2 E3) F F F F数据库系统概论22规则3. 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E)假设：1)E是关系代数表达式2)Ai(i=1，2，n), Bj(j=l，2，m)是属性名3)A1, A2, , An构成Bl，B2，Bm的子集规则4. 选择的串接定律 F1 （ F2（E） F1 F2(E)选择的串接律说明选择条件可以合并，这样一次就可检查全部条件。 9.3.1 关系代数表达式等价变换规则数据库系统概论23规则5. 选择与投影的交换律(1)假设: 选择条件F只涉及属性A1，An F (A1,A2, ,An(E) A1,A2, ,A

21、n(F(E) (2)假设: F中有不属于A1, ,An的属性B1,Bm A1,A2, ,An (F (E)A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E)9.3.1 关系代数表达式等价变换规则数据库系统概论24规则6. 选择与笛卡尔积的交换律(1) 假设：F中涉及的属性都是E1中的属性 F (E1E2)F (E1)E2 (2) 假设：F=F1F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出： F(E1E2) F1(E1)F2 (E2) (3) 假设： F=F1F2， F1只涉及E1中的属性，F2涉及E1和E2两者的属性

22、 F(E1E2) F2(F1(E1)E2) 它使部分选择在笛卡尔积前先做9.3.1 关系代数表达式等价变换规则数据库系统概论25规则7. 选择与并的交换假设：E=E1E2，E1，E2有相同的属性名F(E1E2) F(E1) F(E2)规则8. 选择与差运算的交换假设：E1与E2有相同的属性名F(E1-E2) F(E1) - F(E2) 规则9. 选择对自然连接的分配律F(E1E2) F(E1)F(E2) F史涉及E1与E2的公共属性9.3.1 关系代数表达式等价变换规则数据库系统概论26规则10. 投影与笛卡尔积的分配律假设：E1和E2是两个关系表达式，A1，An是E1的属性，B1，Bm是E2

23、的属性A1,A2,An,B1,B2,Bm(E1E2)A1,A2,An(E1)B1,B2Bm(E2)规则11. 投影与并的交换假设：E1和E2 有相同的属性名A1,A2,An(E1E2)A1,A2,An(E1) A1,A2, ,An(E2)9.3.1 关系代数表达式等价变换规则数据库系统概论279.3.2 查询树的启发式优化规则1：选择和投影操作尽早执行(可以减少查询中间结果的数据量，从而减少查询的执行时间)规则2：把某些选择操作与邻接笛卡尔积相结合，形成一个连接操作(相同关系上的连接操作，特别是等值连接操作要比笛卡尔积节省时间)规则3：同时执行相同关系上的多个选择和投影操作(避免同一个关系上的

24、重复扫描)规则4：把投影操作与邻接操作结合起来执行(节省为单独完成投影操作成进行的关系扫描)规则5：提取公共表达式(减少查询的处理时间)注意：这些规则不能保证一定产生最优化的先化的等价表达式注意：这些规则不能保证一定产生最优化的先化的等价表达式数据库系统概论289.3.2 查询树的启发式优化 算法：关系表达式的优化输入：一个关系表达式的查询树输出：优化的查询树数据库系统概论29查询树概念： 是一种表示关系代数表达式的树形结构。在一个查询树中，叶子节点表示关系，内节点表示关系代数操作。查询树以自底向上的方式执行：当一个内节点的操作分量可用时，这个内节点所表示的操作启动执行，执行结束后用结果关系代

25、替这个内节点。数据库系统概论30优化的一般步骤 1把查询转换成某种内部表示把用高级语言定义的查询转换为关系代数表达式把关系代数表达式转换为查询树2代数优化：把语法树转换成标准（优化）形式3物理优化：选择底层的存取路径 4生成查询计划，选择代价最小的 数据库系统概论31输入：关系代数表达式输出 ：计算输入关系代数表达式的程序 方法：顺序执行下列步骤。（1）使用规则4把形如F1 F2 Fn (E)变换为F1 (F2( (Fn(E) ) （目的是使选择操作可以灵活方便地对下移）（2）通过交换选择运算，将其尽可能移到叶端： 对每一个选择，利用规则49尽可能把它移到树的叶端。（3）通过交换投影运算，将其

26、尽可能移到叶端：对每一个投影利用规则3，5，l0，11中的一般形式尽可能把它移向树的叶端启发式代数优化算法的非形式化描述启发式代数优化算法的非形式化描述 数据库系统概论32（4） 合并串接的选择和投影，以便能同时执行或在一次扫描中完成：利用规则35把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高。（5）对内结点分组：把上述得到的语法树的内节点分组。每一双目运算(， ，-)和它所有的直接祖先为一组(这些直接祖先是，运算)。如果其后代直到叶子全是单目运算，则也将它们并

27、入该组，但当双目运算是笛卡尔积()，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。 启发式代数优化算法的非形式化描述启发式代数优化算法的非形式化描述 数据库系统概论33例例1：列出所有选修课程列出所有选修课程2的学生姓名。的学生姓名。 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2; 查询树 结果结果project(Sname) select(SC.Cno= 2 ) join(Student.Sno=SC.Sno) StudentSCSname SC.Cno=2 Student.Sno=SC.S StudentSC关系代数语法树Sname Student.Sno=SC.Sno SC.Cno= 2 StudentSC优化后的查询树数据库系统概论34例例2：有职工和部门构成的关系数据库如下：有职工和部门构成的关系数据库如下：EMP(EMP(编号编号E#E#，部门名，部门名ENEN，性别，性别SEXSEX，年龄，年龄AGEAGE，工资，工资SALSAL，部门，