《第9章 查询优化优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第9章 查询优化优秀PPT.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第9章章 查询优化查询优化现在学习的是第1页，共44页An Introduction to Database System第九章第九章 关系系统及其查询优化关系系统及其查询优化9.1关系系统9.2关系系统的查询优化9.3小结现在学习的是第2页，共44页An Introduction to Database System关系系统关系系统v能够在一定程度上支持关系模型的数据库管理系统是关系系统。v由于关系模型中并非每一部分都是同等重要的v并不苛求一个实际的关系系统必须完全支持关系模型。现在学习的是第3页，共44页An Introduction to Database System关系系统与关系模
2、型关系系统与关系模型v关系数据结构域及域上定义的关系v关系操作并、交、差、广义笛卡尔积、选择、投影、连接、除等v关系完整性实体完整性、参照完整性、用户自己定义的完整性现在学习的是第4页，共44页An Introduction to Database System关系系统的定义关系系统的定义 一个数据库管理系统可定义为关系系统，当且仅当它至少支持：1.关系数据库（即关系数据结构）系统中只有表这种结构2.支持选择、投影和（自然）连接运算对这些运算不要求用户定义任何物理存取路径对关系系统的最低要求现在学习的是第5页，共44页An Introduction to Database System关系系统
3、的定义关系系统的定义 不支持关系数据结构的系统显然不能称为关系系统仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统。原因：不能提高用户的生产率v支持选择、投影和连接运算，但要求定义物理存取路径，这种系统也不能算作真正的关系系统原因：就降低或丧失了数据的物理独立性v选择、投影、连接运算是最有用的运算现在学习的是第6页，共44页An Introduction to Database System9.1.2 关系系统的分类关系系统的分类 v分类依据：支持关系模型的程度v分类表式系统：支持关系数据结构(即表)(最小)关系系统支持：关系数据结构；选择、投影、连接关系操作关系完备
4、的系统支持：关系数据结构；所有的关系代数操作全关系系统支持：关系模型的所有特征现在学习的是第7页，共44页An Introduction to Database System关系系统的分类关系系统的分类（续）（续）数据结构数据结构数据操作数据操作完整性完整性表式系统表式系统表表 (最小最小)关系系统关系系统表表选选择择、投投影影、连接连接 关系完备的系统关系完备的系统表表 全关系系统全关系系统 现在学习的是第8页，共44页An Introduction to Database System第四章第四章 关系系统及其查询优化关系系统及其查询优化9.1 关系系统关系系统9.2 关系系统的查询优化关
5、系系统的查询优化9.3 小结小结现在学习的是第9页，共44页An Introduction to Database System9.2 关系系统的查询优化关系系统的查询优化 9.2.1 查询优化概述查询优化概述9.2.2 查询优化的必要性查询优化的必要性9.2.3 查询优化的一般准则查询优化的一般准则9.2.4 关系代数等价变换规则关系代数等价变换规则9.2.5 关系代数表达式的优化算法关系代数表达式的优化算法9.2.6 优化的一般步骤优化的一般步骤 现在学习的是第10页，共44页An Introduction to Database System9.2.1 查询优化概述查询优化概述v查询优化
6、的必要性查询优化的必要性查询优化极大地影响查询优化极大地影响RDBMS的性能。的性能。v查询优化的可能性查询优化的可能性关系数据语言的关系数据语言的级别很高级别很高，使，使DBMS可以从关系表达可以从关系表达式中分析查询式中分析查询语义语义。现在学习的是第11页，共44页An Introduction to Database System由由DBMS进行查询优化的好处进行查询优化的好处v用用户户不不必必考考虑虑如如何何最最好好地地表表达达查查询询以以获获得得较较好好的的效率效率v系统可以比用户程序的系统可以比用户程序的优化优化做得更好做得更好(1)优优化化器器可可以以从从数数据据字字典典中中获
7、获取取许许多多统统计计信信息息，而而用用户户程程序序则则难难以以获得这些信息获得这些信息 现在学习的是第12页，共44页An Introduction to Database System由由DBMS进行查询优化的好处进行查询优化的好处(2)如如果果数数据据库库的的物物理理统统计计信信息息改改变变了了，系系统统可可以以自自动动对对查查询询重重新新优优化化以以选选择择相相适适应应的的执行计划。执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。(3)优优化化器器可可以以考考虑虑数数百百种种不不同同的的执
8、执行行计计划划，而而程程序序员员一一般般只只能能考考虑虑有有限限的的几几种可能性种可能性。(4)优化器中包括了很多复杂的优化技术优化器中包括了很多复杂的优化技术现在学习的是第13页，共44页An Introduction to Database System查询优化目标查询优化目标v查询优化的总目标查询优化的总目标 选择有效策略，求得给定关系表达式的值选择有效策略，求得给定关系表达式的值v实际系统的查询优化步骤实际系统的查询优化步骤1.将查询转换成某种内部表示，通常是语法树将查询转换成某种内部表示，通常是语法树2.根据一定的等价变换规则把语法树转换成标准根据一定的等价变换规则把语法树转换成标准
9、（优化）形式（优化）形式现在学习的是第14页，共44页An Introduction to Database System实际系统的查询优化步骤实际系统的查询优化步骤3.选择低层的操作算法选择低层的操作算法对于语法树中的每一个操作对于语法树中的每一个操作计算各种执行算法的执行代价计算各种执行算法的执行代价选择代价小的执行算法选择代价小的执行算法4.生成查询计划生成查询计划(查询执行方案查询执行方案)查询计划是由一系列内部操作组成的。查询计划是由一系列内部操作组成的。现在学习的是第15页，共44页An Introduction to Database System代价模型代价模型v集中式数据库集
10、中式数据库单用户系统单用户系统总代价总代价=I/O代价代价+CPU代价代价多用户系统多用户系统总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价v分布式数据库分布式数据库 总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价+通信代价通信代价 现在学习的是第16页，共44页An Introduction to Database System9.2.2 查询优化的必要性查询优化的必要性 例：求选修了课程2的学生姓名SELECTS.SnameFROMS,SCWHERES.Sno=SC.SnoANDSC.Cno=C2;现在学习的是第17页，共44页An Introduction
11、 to Database System查询优化的必要性（续）查询优化的必要性（续）假设1：外存：S:1000条,SC:10000条,选修C2号课程:50条假设2：一个内存块装元组:10条S,或100条SC,内存中一次可以存放:5块S元组,1块SC元组和若干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于数据块的嵌套循环法现在学习的是第18页，共44页An Introduction to Database System执行策略执行策略11s,name(S.Sno=SC.SnoSC.Cno=2(SSC)SSC读取总块数=读S表块数+读SC表遍数*每遍块数=1000/10+(1000
12、/(105)(10000/100)=100+20100=2100读数据时间=2100/20=105秒现在学习的是第19页，共44页An Introduction to Database System不同的执行策略不同的执行策略,考虑考虑I/O时间时间中间结果大小=1000*10000=107(1千万条元组)写中间结果时间=10000000/10/20=50000秒读数据时间=50000秒总时间=1055000050000秒=100105秒=27.8小时现在学习的是第20页，共44页An Introduction to Database System查询优化的必要性（续）查询优化的必要性（续）2
13、.2,name(SC.Cno=2(SSC)读取总块数=2100块读数据时间=2100/20=105秒中间结果大小=10000（减少1000倍）写中间结果时间=10000/10/20=50秒读数据时间=50秒总时间1055050秒205秒=3.4分现在学习的是第21页，共44页An Introduction to Database System查询优化的必要性（续）查询优化的必要性（续）3.2Sname(SSC.Cno=2(SC)读SC表总块数=10000/100=100块读数据时间=100/20=5秒中间结果大小=50条不必写入外存读S表总块数=1000/10=100块读数据时间=100/20
14、=5秒总时间55秒10秒现在学习的是第22页，共44页An Introduction to Database System9.2.3 查询优化的一般准则查询优化的一般准则 v选择运算应尽可能先做目的：减小中间关系v在执行连接操作前对关系适当进行预处理按连接属性排序在连接属性上建立索引v投影运算和选择运算同时做目的：避免重复扫描关系v将投影运算与其前面或后面的双目运算结合目的：减少扫描关系的遍数现在学习的是第23页，共44页An Introduction to Database System查询优化的一般准则查询优化的一般准则（续）（续）v某些选择运算在其前面执行的笛卡尔积=连接运算例：S.Sn
15、o=SC.Sno(SSC)SSCv提取公共子表达式现在学习的是第24页，共44页An Introduction to Database System9.2.4 关系代数等价变换规则关系代数等价变换规则 v关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的上面的优化策略大部分都涉及到代数表达式的变换现在学习的是第25页，共44页An Introduction to Database System常用的等价变换规则常用的等价变换规则设E1、E2等是关系代数表达式，F是条件表达式l.连接、笛卡尔积交换律E1E2E2E1E1E2E2E1E1FE2E2FE1现在学习的是第26
16、页，共44页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）2.连接、笛卡尔积的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)FFFF现在学习的是第27页，共44页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）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构
17、成Bl，B2，Bm的子集现在学习的是第28页，共44页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）4.选择的串接定律F1（F2（E）F1F2(E)选择的串接律说明选择条件可以合并这样一次就可检查全部条件。现在学习的是第29页，共44页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）5.选择与投影的交换律(1)假设:选择条件F只涉及属性A1，AnF(A1,A2,An(E)A1,A2,An(F(E)(2)假设:F中有不属于A1,An的属性B1,BmA1
18、,A2,An(F(E)A1,A2,An(F(A1,A2,An,B1,B2,Bm(E)现在学习的是第30页，共44页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）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)现在学习的是第31页，共44页An Introduction to Database System关系代数等价变换规
19、则（续）关系代数等价变换规则（续）(3)假设：F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性F(E1E2)F2(F1(E1)E2)它使部分选择在笛卡尔积前先做现在学习的是第32页，共44页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）7.选择与并的交换假设：E=E1E2，E1，E2有相同的属性名F(E1E2)F(E1)F(E2)8.选择与差运算的交换假设：E1与E2有相同的属性名F(E1-E2)F(E1)-F(E2)现在学习的是第33页，共44页An Introduction to Database
20、System关系代数等价变换规则（续）关系代数等价变换规则（续）9.投影与笛卡尔积的交换假设：E1和E2是两个关系表达式，A1，An是E1的属性，B1，Bm是E2的属性A1,A2,An,B1,B2,Bm（E1E2)A1,A2,An（E1)B1,B2,Bm(E2)现在学习的是第34页，共44页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）l0.投影与并的交换假设：E1和E2有相同的属性名A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)现在学习的是第35页，共44页An Introduction
21、to Database System9.2 关系系统的查询优化关系系统的查询优化 9.2.1 查询优化概述查询优化概述9.2.2 查询优化的必要性查询优化的必要性9.2.3 查询优化的一般准则查询优化的一般准则9.2.4 关系代数等价变换规则关系代数等价变换规则9.2.5 关系代数表达式的优化算法关系代数表达式的优化算法9.2.6 优化的一般步骤优化的一般步骤 现在学习的是第36页，共44页An Introduction to Database System语法分析、转换、优化、形成访问路径（执行计划）、计算结语法分析、转换、优化、形成访问路径（执行计划）、计算结果果对对S S（供应商），（供
22、应商），P P（零件），（零件），SPSP（供应关系）三个关系查询（供应关系）三个关系查询供应一个部门供应一个部门1000010000个螺栓以上，个螺栓以上，且供应商位于南京的供应商名字。且供应商位于南京的供应商名字。Selectsnamefroms,p,spwheres.snum=sp.snumandsp.pnum=p.pnumands.city=南京andp.pname=螺栓andsp.quan10000原始查询树（一种查询语句的内部表示法）语法分析优化的查询树优化执行计划（见下一页）现在学习的是第37页，共44页An Introduction to Database System代数优化
23、代数优化v完全基于关系代数，把由查询语句生成代数表达式（查询树）中的操作次序进行等价变换。例如：先做选择和投影，再做连接先做小关系上的连接，再做大关系上的连接v变换原则：尽量减少查询过程中的中间结果的大小。现在学习的是第38页，共44页An Introduction to Database System代数优化一般步骤代数优化一般步骤1.将合取选择分解成一组单选择操作2.在查询树上把选择操作下移，让其尽早执行3.先执行能够产生最小的关系的操作4.将有选择条件的笛卡儿集操作替换成连接操作5.将投影属性分解并在操作树中尽量下移，必要时生成新的投影运算现在学习的是第39页，共44页An Introd
24、uction to Database System基于代数优化的一个例子基于代数优化的一个例子v对于关系模式：S（SNUM，SNAME，CITY）P（PNUM，PNAME，WEIGHT，SIZE）SP（SNUM，PNUM，DEPT，QUAN）v执行查询Q：SELECTSNAMEFROMS，P，SPWHERES.SNUM=SP.SNUMANDSP.PNUM=P.PNUMANDS.CITY=南京ANDP.PNAME=螺栓ANDSP.QUAN10000现在学习的是第40页，共44页SNAMECSPSPC=S.SNUM=SP.SNUM AND SP.PNUM=P.PNUM AND S.CITY=南京南
25、京 AND P.PNAME=螺栓螺栓 AND SP.QUAN10000 Q的原始查询树的原始查询树现在学习的是第41页，共44页SPSNAMESP.PNUM=P.PNUMS.SNUM=SP.SNUMP.PNAME=螺栓PS.CITY=南京SP.QUAN10000S(b)将选择操作尽量下移将选择操作尽量下移现在学习的是第42页，共44页SNAMESP.PNUM=P.PNUMP.PNAME=螺栓S.SNUM=SP.SNUMS.CITY=南京SP.QUAN10000SSPP（c）将将连连接接条条件件与与笛笛卡卡儿儿乘乘积组合成连接操作积组合成连接操作现在学习的是第43页，共44页SNAMESP.PNUM=P.PNUMS.SNUM=SP.SNUMP.PNAME=螺栓S.CITY=南京SP.QUAN10000SNUM.SNAMESNUM.PNUMPNUMPSSP（e）用用投投影影操操作作消消除除对对查查询询无无用的属性用的属性小关系先做连接小关系先做连接现在学习的是第44页，共44页