关系查询和查询优化讲稿.ppt

关系查询和查询优化第一页，讲稿共二十四页哦9.1关系数据库系统的查询处理关系数据库系统的查询处理v查询分析查询分析v查询检查查询检查v查询优化查询优化v查询执行查询执行词法分析词法分析语法分析语法分析语义转换语义转换符号名转换符号名转换安全性检查安全性检查完整性检查完整性检查查询树查询树代数优化代数优化物理优化等物理优化等执行策略描述执行策略描述代码生成代码生成执行查询计划的代码执行查询计划的代码数据库数据库数据字典数据字典查询语句查询语句查询分析查询分析查询检查查询检查查询优化查询优化查询执行查询执行图图9.1查询处理步骤查询处理步骤9.1.1查询处理的步骤查询处理的步骤第二页，讲稿共二十四页哦9.1.2实现查询操作的算法示例实现查询操作的算法示例一、选择操作的实现一、选择操作的实现例例1SELECT*FROMstudentWHEREC1：无条件；：无条件；C2：Sno=200215121;C3:Sage20;C4:Sdept=CSANDSage20方法方法:1.1.简单的全表扫描简单的全表扫描2.2.索引或散列扫描索引或散列扫描二、连接操作的实现二、连接操作的实现例例2SELECT*FROMstudent，SCWHEREstudent.Sno=SC.Sno方法：方法：1.1.嵌套循环方法嵌套循环方法2.2.排序合并方法排序合并方法3.3.索引连接方法索引连接方法4.Hash Join4.Hash Join方法方法第三页，讲稿共二十四页哦9.2关系数据库系统的查询优化关系数据库系统的查询优化9.2.1查询优化概述查询优化概述v查询优化的必要性查询优化的必要性查询优化极大地影响查询优化极大地影响RDBMS的性能。的性能。v查询优化的可能性查询优化的可能性关系数据语言的关系数据语言的级别很高级别很高，使，使DBMS可以从关系表达式中分析查询可以从关系表达式中分析查询语义语义。第四页，讲稿共二十四页哦由由DBMS进行查询优化的好处进行查询优化的好处用户不必考虑如何最好地表达查询以获得较好的效率，系统可以比用用户不必考虑如何最好地表达查询以获得较好的效率，系统可以比用户程序的户程序的优化优化做得更好。做得更好。1.优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息息。2.如果数据库的物理统计信息改变了，系统可以自动对查询如果数据库的物理统计信息改变了，系统可以自动对查询重新优化重新优化以选择相适应以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。是不太可能的。3.优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。可能性。4.优化器中包括了很多复杂的优化技术。这些技术往往只有最好的程序员才能优化器中包括了很多复杂的优化技术。这些技术往往只有最好的程序员才能掌握。系统的自动优化相当于使的所有人都拥有这些优化技术。掌握。系统的自动优化相当于使的所有人都拥有这些优化技术。第五页，讲稿共二十四页哦查询优化目标查询优化目标v查询优化的总目标查询优化的总目标选择有效策略，求得给定关系表达式的值选择有效策略，求得给定关系表达式的值v实际系统的查询优化步骤实际系统的查询优化步骤1.将查询转换成某种内部表示，通常是语法树将查询转换成某种内部表示，通常是语法树2.根据一定的等价变换规则把语法树转换成标准根据一定的等价变换规则把语法树转换成标准（优化）形式（优化）形式3.选择低层的操作算法选择低层的操作算法对于语法树中的每一个操作对于语法树中的每一个操作计算各种执行算法的执行代价计算各种执行算法的执行代价选择代价小的执行算法选择代价小的执行算法4.生成查询计划生成查询计划(查询执行方案查询执行方案)查询计划是由一系列内部操作组成的。查询计划是由一系列内部操作组成的。第六页，讲稿共二十四页哦基于代价模型的优化算法基于代价模型的优化算法v集中式数据库集中式数据库单用户系统单用户系统总代价总代价=I/O代价代价+CPU代价代价多用户系统多用户系统总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价v分布式数据库分布式数据库总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价+通信代价通信代价代价模型代价模型第七页，讲稿共二十四页哦9.2.2一个实例一个实例例例3求选修了课程求选修了课程2的学生姓名的学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=2;执行策略执行策略1name(Student.Sno=SC.SnoSC.Cno=2(StudentSC)2name(SC.Cno=2(StudentSC)3name(StudentSC.Cno=2(SC)第八页，讲稿共二十四页哦9.3代数优化代数优化v基于关系代数等价变换规则的优化方法为基于关系代数等价变换规则的优化方法为代数优化；代数优化；v代代数数优优化化策策略略是是通通过过对对关关系系代代数数表表达达式式的的等等价价变变换换来来提提高查询效率；高查询效率；v关关系系代代数数表表达达式式的的等等价价是是指指用用相相同同的的关关系系代代替替两两个个表表达达式中相应的关系所得到的结果是相同的；式中相应的关系所得到的结果是相同的；v两个表达式两个表达式E1和和E2是等价的是等价的,记为记为E1E2。第九页，讲稿共二十四页哦9.3.1关系代数表达式等价变换规则关系代数表达式等价变换规则设设E1、E2等是关系代数表达式，等是关系代数表达式，F是条件表达式是条件表达式l.连接、笛卡尔积交换律连接、笛卡尔积交换律E1E2E2E1E1E2E2E1E1FE2E2FE1常用的等价变换规则常用的等价变换规则第十页，讲稿共二十四页哦2.连接、笛卡尔积的结合律连接、笛卡尔积的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)FFFF第十一页，讲稿共二十四页哦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）F1F2(E)选择的串接律说明选择的串接律说明选择条件可以合并选择条件可以合并这样一次就可检查全部条件。这样一次就可检查全部条件。5.选择与投影的交换律选择与投影的交换律(1)假设假设:选择条件选择条件F只涉及属性只涉及属性A1，AnF(A1,A2,An(E)A1,A2,An(F(E)(2)假设假设:F中有不属于中有不属于A1,An的属性的属性B1,BmA1,A2,An(F(E)A1,A2,An(F(A1,A2,An,B1,B2,Bm(E)第十三页，讲稿共二十四页哦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两者的属性两者的属性F(E1E2)F2(F1(E1)E2)它使部分选择在笛卡尔积前先做它使部分选择在笛卡尔积前先做第十四页，讲稿共二十四页哦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的的公共属性公共属性第十五页，讲稿共二十四页哦10.投影与笛卡尔积的分配投影与笛卡尔积的分配假设：假设：E1和和E2是两个关系表达式，是两个关系表达式，A1，An是是E1的属性，的属性，B1，Bm是是E2的属性的属性A1,A2,An,B1,B2,Bm（E1E2)A1,A2,An（E1)B1,B2,Bm(E2)l1.投影与并的分配投影与并的分配假设：假设：E1和和E2有有相同的属性名相同的属性名A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)第十六页，讲稿共二十四页哦9.3.2查询树的启发式优化查询树的启发式优化启发式规则的代数优化启发式规则的代数优化,是对关系代数表达式的查询树进行优化是对关系代数表达式的查询树进行优化,其典型的规则有其典型的规则有:1.选择运算应尽可能先做选择运算应尽可能先做目的：减小中间关系目的：减小中间关系2.投影运算和选择运算同时做投影运算和选择运算同时做目的：避免重复扫描关系目的：避免重复扫描关系3.把投影运算与其前面或后面的双目运算结合把投影运算与其前面或后面的双目运算结合目的：减少扫描关系的遍数目的：减少扫描关系的遍数第十七页，讲稿共二十四页哦4.某些选择运算某些选择运算在其前面执行的笛卡尔积在其前面执行的笛卡尔积=连接运算连接运算例：例：Student.Sno=SC.Sno(StudentSC)StudentSC5.提取公共子表达式提取公共子表达式第十八页，讲稿共二十四页哦关系代数表达式的优化算法关系代数表达式的优化算法算法：关系表达式的优化。算法：关系表达式的优化。输入：一个关系表达式的查询树。输入：一个关系表达式的查询树。输出：优化的查询树。输出：优化的查询树。方法：方法：(1)分解选择运算分解选择运算利用规则利用规则4把形如把形如F1F2Fn(E)变换为变换为F1(F2(Fn(E)(2)通过交换选择运算，将其尽可能移到叶端通过交换选择运算，将其尽可能移到叶端对每一个选择，利用规则对每一个选择，利用规则48尽可能把它移到树的叶端。尽可能把它移到树的叶端。(3)通过交换投影运算，将其尽可能移到叶端通过交换投影运算，将其尽可能移到叶端对每一个投影利用规则对每一个投影利用规则3、5、l0、11中的一般形式尽可能把它移向树的叶端。中的一般形式尽可能把它移向树的叶端。第十九页，讲稿共二十四页哦(4)利利用用规规则则35把把选选择择和和投投影影的的串串接接合合并并成成单单个个选选择择、单单个个投投影影或或一一个个选选择择后后跟跟一一个个投投影影。使使多多个个选选择择或或投投影影能能同同时时执执行行，或或在在一一次次扫扫描描中中全全部部完完成成，尽尽管管这这种种变变换换似似乎乎违违背背“投投影影尽尽可可能能早早做做”的的原原则则，但但这这样样做做效效率率更高。更高。(5)对内结点分组对内结点分组把上述得到的语法树的内节点分组。把上述得到的语法树的内节点分组。每每一一双双目目运运算算(，-)和和它它所所有有的的直直接接祖祖先先为为一一组组(这这些些直直接接祖祖先先是是，运算运算)。如如果果其其后后代代直直到到叶叶子子全全是是单单目目运运算算，则则也也将将它它们们并并入入该该组组，但但当当双双目目运运算算是是笛笛卡卡尔尔积积()，而而且且其其后后的的选选择择不不能能与与它它结结合合为为等等值值连连接接时时除除外外。把把这这些些单单目目运算单独分为一组。运算单独分为一组。第二十页，讲稿共二十四页哦例例4求选修了课程求选修了课程2的学生姓名的学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=2;Sname Student.Sno=SC.Sno SC.Cno=2 StudentSC（2）关系代数语法树）关系代数语法树Sname Student.Sno=SC.Sno SC.Cno=2 StudentSC（3）优化后的查询树）优化后的查询树结果结果project(Sname)select(SC.Cno=2)join(Student.Sno=SC.Sno)StudentSC（1）把）把SQL语句转换成查询树语句转换成查询树第二十一页，讲稿共二十四页哦9.4物理优化物理优化代代数数优优化化是是改改变变查查询询语语句句的的次次序序和和组组合合，不不涉涉及及底底层层的的存存取取路路径径，物物理理优优化化就就是是要要选选择择高高效效合合理理的的操操作作算算法法或或存存取取路路径径，求求的的优优化化的查询计划，达到查询优化的目标。具体方法有：的查询计划，达到查询优化的目标。具体方法有：v基于规则的启发式优化基于规则的启发式优化v基于代价估算的优化基于代价估算的优化v两者结合的优化方法两者结合的优化方法第二十二页，讲稿共二十四页哦9.4.1基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化一、选择操作的启发式规则（一、选择操作的启发式规则（P273）对于小关系使用全表顺序扫描。对于小关系使用全表顺序扫描。对大关系来说分情况处理对大关系来说分情况处理二、连接操作的启发式规则（二、连接操作的启发式规则（P273）9.4.2基于代价的优化基于代价的优化一、统计信息一、统计信息二、代价估算示例二、代价估算示例1.全表扫描算法的代价估算公式全表扫描算法的代价估算公式2.索引扫描算法的代价估算公式索引扫描算法的代价估算公式3.嵌套循环连接算法的代价估算公式嵌套循环连接算法的代价估算公式4.排序排序合并连接算法的代价估算公式合并连接算法的代价估算公式第二十三页，讲稿共二十四页哦第九章作业题：第九章作业题：第275页习题 第2、3、4题。第二十四页，讲稿共二十四页哦