第9章 查询优化精选文档.ppt

《第9章 查询优化精选文档.ppt》由会员分享，可在线阅读，更多相关《第9章 查询优化精选文档.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第9章章 查询优化查询优化本讲稿第一页，共四十四页An Introduction to Database System第九章第九章 关系系统及其查询优化关系系统及其查询优化9.1关系系统9.2关系系统的查询优化9.3小结本讲稿第二页，共四十四页An Introduction to Database System关系系统关系系统v能够在一定程度上支持关系模型的数据库管理系统是关系系统。v由于关系模型中并非每一部分都是同等重要的v并不苛求一个实际的关系系统必须完全支持关系模型。本讲稿第三页，共四十四页An Introduction to Database System关系系统与关系模型关系系统与

2、关系模型v关系数据结构域及域上定义的关系v关系操作并、交、差、广义笛卡尔积、选择、投影、连接、除等v关系完整性实体完整性、参照完整性、用户自己定义的完整性本讲稿第四页，共四十四页An Introduction to Database System关系系统的定义关系系统的定义 一个数据库管理系统可定义为关系系统，当且仅当它至少支持：1.关系数据库（即关系数据结构）系统中只有表这种结构2.支持选择、投影和（自然）连接运算对这些运算不要求用户定义任何物理存取路径对关系系统的最低要求本讲稿第五页，共四十四页An Introduction to Database System关系系统的定义关系系统的定义

3、 不支持关系数据结构的系统显然不能称为关系系统仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统。原因：不能提高用户的生产率v支持选择、投影和连接运算，但要求定义物理存取路径，这种系统也不能算作真正的关系系统原因：就降低或丧失了数据的物理独立性v选择、投影、连接运算是最有用的运算本讲稿第六页，共四十四页An Introduction to Database System9.1.2 关系系统的分类关系系统的分类 v分类依据：支持关系模型的程度v分类表式系统：支持关系数据结构(即表)(最小)关系系统支持：关系数据结构；选择、投影、连接关系操作关系完备的系统支持：关系数据结构

4、；所有的关系代数操作全关系系统支持：关系模型的所有特征本讲稿第七页，共四十四页An Introduction to Database System关系系统的分类关系系统的分类（续）（续）数据结构数据结构数据操作数据操作完整性完整性表式系统表式系统表表 (最小最小)关系系统关系系统表表选选择择、投投影影、连接连接 关系完备的系统关系完备的系统表表 全关系系统全关系系统 本讲稿第八页，共四十四页An Introduction to Database System第四章第四章 关系系统及其查询优化关系系统及其查询优化9.1 关系系统关系系统9.2 关系系统的查询优化关系系统的查询优化9.3 小结小结

5、本讲稿第九页，共四十四页An Introduction to Database System9.2 关系系统的查询优化关系系统的查询优化 9.2.1 查询优化概述查询优化概述9.2.2 查询优化的必要性查询优化的必要性9.2.3 查询优化的一般准则查询优化的一般准则9.2.4 关系代数等价变换规则关系代数等价变换规则9.2.5 关系代数表达式的优化算法关系代数表达式的优化算法9.2.6 优化的一般步骤优化的一般步骤 本讲稿第十页，共四十四页An Introduction to Database System9.2.1 查询优化概述查询优化概述v查询优化的必要性查询优化的必要性查询优化极大地影响

6、查询优化极大地影响RDBMS的性能。的性能。v查询优化的可能性查询优化的可能性关系数据语言的关系数据语言的级别很高级别很高，使，使DBMS可以从关系表可以从关系表达式中分析查询达式中分析查询语义语义。本讲稿第十一页，共四十四页An Introduction to Database System由由DBMS进行查询优化的好处进行查询优化的好处v用用户户不不必必考考虑虑如如何何最最好好地地表表达达查查询询以以获获得得较较好好的的效率效率v系统可以比用户程序的系统可以比用户程序的优化优化做得更好做得更好(1)优优化化器器可可以以从从数数据据字字典典中中获获取取许许多多统统计计信信息息，而而用用户户程

7、程序序则难以获得这些信息则难以获得这些信息 本讲稿第十二页，共四十四页An Introduction to Database System由由DBMS进行查询优化的好处进行查询优化的好处(2)如如果果数数据据库库的的物物理理统统计计信信息息改改变变了了，系系统统可可以以自自动动对对查查询询重重新新优优化化以以选选择择相相适应的执行计划。适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。(3)优优化化器器可可以以考考虑虑数数百百种种不不同同的的执执行行计计划划，而而程程序序员员一一般般只只能能考

8、考虑虑有有限限的的几几种可能性种可能性。(4)优化器中包括了很多复杂的优化技术优化器中包括了很多复杂的优化技术本讲稿第十三页，共四十四页An Introduction to Database System查询优化目标查询优化目标v查询优化的总目标查询优化的总目标 选择有效策略，求得给定关系表达式的值选择有效策略，求得给定关系表达式的值v实际系统的查询优化步骤实际系统的查询优化步骤1.将查询转换成某种内部表示，通常是语法树将查询转换成某种内部表示，通常是语法树2.根据一定的等价变换规则把语法树转换成标准根据一定的等价变换规则把语法树转换成标准（优化）形式（优化）形式本讲稿第十四页，共四十四页An

9、 Introduction to Database System实际系统的查询优化步骤实际系统的查询优化步骤3.选择低层的操作算法选择低层的操作算法对于语法树中的每一个操作对于语法树中的每一个操作计算各种执行算法的执行代价计算各种执行算法的执行代价选择代价小的执行算法选择代价小的执行算法4.生成查询计划生成查询计划(查询执行方案查询执行方案)查询计划是由一系列内部操作组成的。查询计划是由一系列内部操作组成的。本讲稿第十五页，共四十四页An Introduction to Database System代价模型代价模型v集中式数据库集中式数据库单用户系统单用户系统总代价总代价=I/O代价代价+C

10、PU代价代价多用户系统多用户系统总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价v分布式数据库分布式数据库 总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价+通信代价通信代价 本讲稿第十六页，共四十四页An Introduction to Database System9.2.2 查询优化的必要性查询优化的必要性 例：求选修了课程2的学生姓名SELECTS.SnameFROMS,SCWHERES.Sno=SC.SnoANDSC.Cno=C2;本讲稿第十七页，共四十四页An Introduction to Database System查询优化的必要性（续）查询优化的

11、必要性（续）假设1：外存：S:1000条,SC:10000条,选修C2号课程:50条假设2：一个内存块装元组:10条S,或100条SC,内存中一次可以存放:5块S元组,1块SC元组和若干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于数据块的嵌套循环法本讲稿第十八页，共四十四页An Introduction to Database System执行策略执行策略11s,name(S.Sno=SC.SnoSC.Cno=2(SSC)SSC读取总块数=读S表块数+读SC表遍数*每遍块数=1000/10+(1000/(105)(10000/100)=100+20100=2100读数据时间

12、=2100/20=105秒本讲稿第十九页，共四十四页An Introduction to Database System不同的执行策略不同的执行策略,考虑考虑I/O时间时间中间结果大小=1000*10000=107(1千万条元组)写中间结果时间=10000000/10/20=50000秒读数据时间=50000秒总时间=1055000050000秒=100105秒=27.8小时本讲稿第二十页，共四十四页An Introduction to Database System查询优化的必要性（续）查询优化的必要性（续）2.2,name(SC.Cno=2(SSC)读取总块数=2100块读数据时间=210

13、0/20=105秒中间结果大小=10000（减少1000倍）写中间结果时间=10000/10/20=50秒读数据时间=50秒总时间1055050秒205秒=3.4分本讲稿第二十一页，共四十四页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=5秒总时间55秒10秒本讲稿第二十二页，共四十四页An Introduction

14、to Database System9.2.3 查询优化的一般准则查询优化的一般准则 v选择运算应尽可能先做目的：减小中间关系v在执行连接操作前对关系适当进行预处理按连接属性排序在连接属性上建立索引v投影运算和选择运算同时做目的：避免重复扫描关系v将投影运算与其前面或后面的双目运算结合目的：减少扫描关系的遍数本讲稿第二十三页，共四十四页An Introduction to Database System查询优化的一般准则查询优化的一般准则（续）（续）v某些选择运算在其前面执行的笛卡尔积=连接运算例：S.Sno=SC.Sno(SSC)SSCv提取公共子表达式本讲稿第二十四页，共四十四页An In

15、troduction to Database System9.2.4 关系代数等价变换规则关系代数等价变换规则 v关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的上面的优化策略大部分都涉及到代数表达式的变换本讲稿第二十五页，共四十四页An Introduction to Database System常用的等价变换规则常用的等价变换规则设E1、E2等是关系代数表达式，F是条件表达式l.连接、笛卡尔积交换律E1E2E2E1E1E2E2E1E1FE2E2FE1本讲稿第二十六页，共四十四页An Introduction to Database System关系代数等价变

16、换规则（续）关系代数等价变换规则（续）2.连接、笛卡尔积的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)FFFF本讲稿第二十七页，共四十四页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构成Bl，B2，Bm的子集本讲稿第二十八页，共四十四页An Introduction to Dat

17、abase System关系代数等价变换规则（续）关系代数等价变换规则（续）4.选择的串接定律F1（F2（E）F1F2(E)选择的串接律说明选择条件可以合并这样一次就可检查全部条件。本讲稿第二十九页，共四十四页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,A2,An(F(E)A1,A2,An(F(A1,A2,An,B1,B2,Bm(E)本讲稿第三十页，

18、共四十四页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)本讲稿第三十一页，共四十四页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）(3)假设：F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者

19、的属性F(E1E2)F2(F1(E1)E2)它使部分选择在笛卡尔积前先做本讲稿第三十二页，共四十四页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)本讲稿第三十三页，共四十四页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）9.投影与笛卡尔积的交换假设：E1和E2是两个

20、关系表达式，A1，An是E1的属性，B1，Bm是E2的属性A1,A2,An,B1,B2,Bm（E1E2)A1,A2,An（E1)B1,B2,Bm(E2)本讲稿第三十四页，共四十四页An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续）l0.投影与并的交换假设：E1和E2有相同的属性名A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)本讲稿第三十五页，共四十四页An Introduction to Database System9.2 关系系统的查询优化关系系统的查询优化 9.2.1 查询优化概述查询优化

21、概述9.2.2 查询优化的必要性查询优化的必要性9.2.3 查询优化的一般准则查询优化的一般准则9.2.4 关系代数等价变换规则关系代数等价变换规则9.2.5 关系代数表达式的优化算法关系代数表达式的优化算法9.2.6 优化的一般步骤优化的一般步骤 本讲稿第三十六页，共四十四页An Introduction to Database System语法分析、转换、优化、形成访问路径（执行计划）、计算结果语法分析、转换、优化、形成访问路径（执行计划）、计算结果对对S S（供应商），（供应商），P P（零件），（零件），SPSP（供应关系）三个关系查询（供应关系）三个关系查询供应一个部门供应一个部门1

22、000010000个螺栓以上，个螺栓以上，且供应商位于南京的供应商名字。且供应商位于南京的供应商名字。Selectsnamefroms,p,spwheres.snum=sp.snumandsp.pnum=p.pnumands.city=南京andp.pname=螺栓andsp.quan10000原始查询树（一种查询语句的内部表示法）语法分析优化的查询树优化执行计划（见下一页）本讲稿第三十七页，共四十四页An Introduction to Database System代数优化代数优化v完全基于关系代数，把由查询语句生成代数表达式（查询树）中的操作次序进行等价变换。例如：先做选择和投影，再做连

23、接先做小关系上的连接，再做大关系上的连接v变换原则：尽量减少查询过程中的中间结果的大小。本讲稿第三十八页，共四十四页An Introduction to Database System代数优化一般步骤代数优化一般步骤1.将合取选择分解成一组单选择操作2.在查询树上把选择操作下移，让其尽早执行3.先执行能够产生最小的关系的操作4.将有选择条件的笛卡儿集操作替换成连接操作5.将投影属性分解并在操作树中尽量下移，必要时生成新的投影运算本讲稿第三十九页，共四十四页An Introduction to Database System基于代数优化的一个例子基于代数优化的一个例子v对于关系模式：S（SNUM

24、，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本讲稿第四十页，共四十四页SNAMECSPSPC=S.SNUM=SP.SNUM AND SP.PNUM=P.PNUM AND S.CITY=南京南京 AND P.PNAME=螺栓螺栓 AND SP.QUAN10000 Q的原始查询树的原始查询树本讲稿第四十一页，共四十四页

25、SPSNAMESP.PNUM=P.PNUMS.SNUM=SP.SNUMP.PNAME=螺栓PS.CITY=南京SP.QUAN10000S(b)将选择操作尽量下移将选择操作尽量下移本讲稿第四十二页，共四十四页SNAMESP.PNUM=P.PNUMP.PNAME=螺栓S.SNUM=SP.SNUMS.CITY=南京SP.QUAN10000SSPP（c）将将连连接接条条件件与与笛笛卡卡儿儿乘乘积积组组合成连接操作合成连接操作本讲稿第四十三页，共四十四页SNAMESP.PNUM=P.PNUMS.SNUM=SP.SNUMP.PNAME=螺栓S.CITY=南京SP.QUAN10000SNUM.SNAMESNUM.PNUMPNUMPSSP（e）用用投投影影操操作作消消除除对对查查询询无无用用的属性的属性小关系先做连接小关系先做连接本讲稿第四十四页，共四十四页