第9章 关系系统和查询优化精选文档.ppt
第9章 关系系统和查询优化本讲稿第一页，共四十九页第九章 关系系统和查询优化 数据库原理本讲稿第二页，共四十九页 数据库原理 10/4/2022本章的主要内容9.1 关系系统9.2 关系系统的查询优化9.3 代数优化 关系系统与关系模型 关系系统的分类 本讲稿第三页，共四十九页 数据库原理 10/4/2022关系系统与关系模型n关系系统能够在一定程度上支持关系模型的数据库管理系统是关系系统。由于关系模型中并非每一部分都是同等重要的，所以并不苛求一个实际的关系系统必须完全支持关系模型。本讲稿第四页，共四十九页 数据库原理 10/4/2022关系系统与关系模型n关系系统与关系模型1.关系数据结构n域及域上定义的关系2.关系操作n并、交、差、广义笛卡尔积、选择、投影、连接、除等 3.关系完整性n实体完整性、参照完整性、用户自己定义的完整性 本讲稿第五页，共四十九页 数据库原理 10/4/2022关系系统与关系模型n关系系统的定义一个数据库管理系统可定义为关系系统，当且仅当它至少支持：关系数据库（即关系数据结构）系统中只有表这种结构；支持选择、投影和（自然）连接运算 对这些运算不要求用户定义任何物理存取路径。这是对关系系统的最低要求。本讲稿第六页，共四十九页 数据库原理 10/4/2022关系系统与关系模型n关系系统的定义不支持关系数据结构的系统显然不能称为关系系统。仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统。原因是：不能提高用户的生产率。支持选择、投影和连接运算，但要求定义物理存取路径，这种系统也不能算作真正的关系系统。原因是：降低或丧失了数据的物理独立性。在关系系统中，选择、投影、连接运算是最有用的运算。本讲稿第七页，共四十九页 数据库原理 10/4/2022n关系系统的分类分类依据：支持关系模型的程度。1.表式系统：支持关系数据结构（即表）2.（最小）关系系统：支持关系数据结构；选择、投影、连接关系操作 3.关系完备的系统：支持：关系数据结构；所有的关系代数操作4.全关系系统：支持：关系模型的所有特征 关系系统的分类本讲稿第八页，共四十九页 数据库原理 10/4/2022关系系统的分类n关系系统的分类数据结构数据操作完整性表式系统表（最小）关系系统表选择、投影、连接关系完备的系统表全关系系统本讲稿第九页，共四十九页 数据库原理 10/4/2022本章的主要内容9.1 关系系统9.2 关系系统的查询优化9.3 代数优化 查询优化概述 查询优化的必要性 查询优化的一般准则本讲稿第十页，共四十九页 数据库原理 10/4/2022查询优化概述n查询优化的必要性查询优化极大地影响RDBMS的性能。n查询优化的可能性关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。本讲稿第十一页，共四十九页 数据库原理 10/4/2022查询优化概述n由DBMS进行查询优化的好处用户不必考虑如何最好地表达查询以获得较好的效率，系统可以比用户程序的优化做得更好。优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优化器中包括了很多复杂的优化技术 本讲稿第十二页，共四十九页 数据库原理 10/4/2022查询优化概述n查询优化的目标选择有效策略，求得给定关系表达式的值n实际系统的查询优化步骤：将查询转换成某种内部表示，通常是语法树；根据一定的等价变换规则把语法树转换成标准（优化）形式；选择低层的操作算法，对于语法树中的每一个操作，计算各种执行算法的执行代价，选择代价小的执行算法；生成查询计划(查询执行方案)，查询计划是由一系列内部操作组成的。本讲稿第十三页，共四十九页 数据库原理 10/4/2022查询优化概述n代价模型1.集中式数据库单用户系统：总代价=I/O代价+CPU代价多用户系统：总代价=I/O代价+CPU代价+内存代价2.分布式数据库总代价=I/O代价+CPU代价+内存代价+通信代价 本讲稿第十四页，共四十九页 数据库原理 10/4/2022查询优化的必要性例：查询求选修了课程C2的学生姓名SELECTS.SnameFROMS,SCWHERES.Sno=SC.SnoANDSC.Cno=C2;假设1：外存：S：1000个元组，SC：10000个元组，选修C2号课程：50个元组假设2：一个内存块装：10个S元组，或100个SC元组；内存中一次可以存放：5块S元组，1块SC元组和若干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于数据块的嵌套循环法本讲稿第十五页，共四十九页 数据库原理 10/4/2022查询优化的必要性n执行策略1广义笛卡尔积Q1sname(S.Sno=SC.SnoSC.Cno=2(S SC)SSC读取总块数=读S表块数+每次读取SC块数*读SC表次数=1000/10+(10000/100)(1000/(105)=100+20100=2100读数据时间1=2100/20=105秒中间结果大小=1000*10000=107(1千万条元组)设每块装10个中间结果元组，则：写中间结果时间=107/10/20=50000秒n假设1：外存：S：1000个元组，SC：10000个元组，选修C2号课程：50个元组n假设2：一个内存块装：10个S元组，或100个SC元组；内存中一次可以存放：5块S元组，1块SC元组和若干块连接结果元组n假设3：读写速度：20块/秒本讲稿第十六页，共四十九页 数据库原理 10/4/2022查询优化的必要性n执行策略1广义笛卡尔积Q1sname(S.Sno=SC.SnoSC.Cno=2(S SC)SSC读数据时间1=2100/20=105秒写中间结果时间=107/10/20=50000秒：读数据时间2=50000秒：总时间=读数据时间1+写中间结果时间+读数据时间2=1055000050000秒=100105秒=27.8小时本讲稿第十七页，共四十九页 数据库原理 10/4/2022查询优化的必要性n执行策略2自然连接Q2sname(SC.Cno=2(S SC)SSC读取总块数=2100块（计算方法同上）读数据时间1=2100/20=105秒中间结果大小=10000（SC元组数）（比前面方法减少1000倍）写中间结果时间=10000/10/20=50秒读数据时间2=50秒总时间=读数据时间1+写中间结果时间+读数据时间21055050秒205秒=3.4分n假设1：外存：S：1000个元组，SC：10000个元组，选修C2号课程：50个元组n假设2：一个内存块装：10个S元组，或100个SC元组；本讲稿第十八页，共四十九页 数据库原理 10/4/2022查询优化的必要性n执行策略3优化的自然连接Q3sname(S SC.Cno=2(SC)读SC表总块数=10000/100=100块读数据时间=100/20=5秒中间结果大小=50条（不必写入外存）读S表总块数=1000/10=100块读数据时间=100/20=5秒总时间=读SC数据时间+读S数据时间55秒10秒n假设1：外存：S：1000个元组，SC：10000个元组，选修C2号课程：50个元组n假设2：一个内存块装：10个S元组，或100个SC元组；本讲稿第十九页，共四十九页 数据库原理 10/4/2022查询优化的一般准则n查询优化的一般准则1.选择运算应尽可能先做（目的：减小中间关系）2.在执行连接操作前对关系适当进行预处理：按连接属性排序；在连接属性上建立索引3.投影运算和选择运算同时做（目的：避免重复扫描关系）4.将投影运算与其前面或后面的双目运算结合（目的：减少扫描关系的次数）5.某些选择运算在其前面执行的笛卡尔积=连接运算例如：S.Sno=SC.Sno(SSC)=SSC6.提取公共子表达式本讲稿第二十页，共四十九页 数据库原理 10/4/2022本章的主要内容9.1 关系系统9.2 关系系统的查询优化9.3 代数优化 关系代数等价变换规则 关系代数表达式的优化算法 代数优化的一般步骤 本讲稿第二十一页，共四十九页 数据库原理 10/4/2022关系代数等价变换规则n关系代数表达式等价是指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。前面的优化策略大部分都涉及到代数表达式的变换。设E1、E2等是关系代数表达式，F1和F2是条件表达式本讲稿第二十二页，共四十九页 数据库原理 10/4/2022关系代数等价变换规则1.连接、笛卡尔积交换律E1E2E2E1E1E2E2E1E1E2E2E12.连接、笛卡尔积的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)F1F1F1F2F1F2本讲稿第二十三页，共四十九页 数据库原理 10/4/2022关系代数等价变换规则3.投影的串接定律假设：A1,A2,An和B1,B2,Bm是属性名且A1,A2,AnB1,B2,Bm，则有：A1,A2,An(B1,B2,Bm(E1)A1,A2,An(E1)4.选择的串接定律F1（F2（E1）F1F2（E1）该定律说明：选择条件可以合并，这样一次就可检查全部条件。求IS系年龄大于岁的学生本讲稿第二十四页，共四十九页 数据库原理 10/4/2022关系代数等价变换规则5.选择与投影的交换律假设:选择条件F1只涉及属性A1,A2,An，则有：F1（A1,A2,An（E1）)A1,A2,An（F1（E1）)假设:条件F1中有不属于A1,A2,An的属性B1,B2,Bm，则有：A1,A2,An（F1（E1）)A1,A2,An(F1(A1,A2,An,B1,B2,Bm(E1)本讲稿第二十五页，共四十九页 数据库原理 10/4/2022关系代数等价变换规则6.选择与笛卡尔积的交换律假设：F1只涉及E1中的属性，F2只涉及E2中的属性nF1（E1E2）F1（E1）E2nF1F2(E1E2)F1（E1）F2（E2）假设：F1只涉及E1中的属性，F2涉及E1和E2两者的的属性nF1F2(E1E2)F2（F1（E1）E2）95001这个学生可能的选课情况证明：证明：本讲稿第二十六页，共四十九页 数据库原理 10/4/2022关系代数等价变换规则7.选择与并运算的分配律假设：E=E1E2,E1，E2有相同的属性名，则：F1（E1E2）F1（E1）F1（E2）8.选择与差运算的分配律假设：E1，E2有相同的属性名，则：F1（E1E2）F1（E1）F1（E2）9.选择对自然连接的分配律假设：F1只涉及E1和E2的公共属性，则：F1（E1E2）F1（E1）F1（E2）设S1是软件01的学生关系表，S2是软件02的学生关系表设S1是软件01的学生关系表，S3是软件专业的学生关系表查找95001这位学生的选课记录本讲稿第二十七页，共四十九页 数据库原理 10/4/2022关系代数等价变换规则10.投影与笛卡尔积的分配律假设：A1,A2,An是E1的属性，B1,B2,Bm是E2的属性，则：A1,A2,An,B1,B2,Bm（E1E2）A1,A2,An（E1）B1,B2,Bm（E2）11.投影与并运算的分配律假设：E1，E2有相同的属性名A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)查找所有学生可能的选课对设S1是软件01的学生关系表，S2是软件02的学生关系表查找软件01、02的大于岁的学生本讲稿第二十八页，共四十九页 数据库原理 10/4/2022关系代数表达式的优化算法n代数优化完全基于关系代数，把由查询语句生成代数表达式（查询树）中的操作次序进行等价变换。例如：先做选择和投影，再做连接先做小关系上的连接，再做大关系上的连接n变换原则：尽量减少查询过程中的中间结果的大小。原始查询树（一种查询语句的内部表示法）语法分析优化的查询树优化执行计划本讲稿第二十九页，共四十九页 数据库原理 10/4/2022代数优化的一般步骤n代数优化的一般步骤1.将合取选择分解成一组单选择操作2.在查询树上把选择操作下移，让其尽早执行3.先执行能够产生最小的关系的操作4.将有选择条件的笛卡儿集操作替换成连接操作5.将投影属性分解并在操作树中尽量下移，必要时生成新的投影运算本讲稿第三十页，共四十九页 数据库原理 10/4/2022代数优化的一般步骤对于关系模式：供应商：S（Snum，Sname，city）零件：P（Pnum，Pname，weight，size）供应关系：SP（Snum，Pnum，dept，quan）查询供应一个部门10000个螺栓以上，且供应商位于南京的供应商名字。SELECTSnameFROMS,SP,PWHERES.Snum=SP.SnumANDSP.Pnum=P.PnumANDS.city=南京ANDP.Pname=螺栓ANDSP.quan10000本讲稿第三十一页，共四十九页 数据库原理 10/4/2022SNAMECPSSP查询条件C=S.SNUM=SP.SNUMANDSP.PNUM=P.PNUMANDS.CITY=南京ANDP.PNAME=螺栓ANDSP.QUAN10000代数优化的一般步骤原始查询树本讲稿第三十二页，共四十九页 数据库原理 10/4/2022代数优化的一般步骤SPSNAMESP.PNUM=P.PNUMS.SNUM=SP.SNUMP.PNAME=螺栓PS.CITY=南京SP.QUAN10000S将选择操作尽量下移本讲稿第三十三页，共四十九页 数据库原理 10/4/2022代数优化的一般步骤SNAMESP.PNUM=P.PNUMP.PNAME=螺栓S.SNUM=SP.SNUMS.CITY=南京SP.QUAN10000SSPP将连接条件与笛卡儿乘积组合成连接操作本讲稿第三十四页，共四十九页 数据库原理 10/4/2022代数优化的一般步骤SNAMESP.PNUM=P.PNUMS.SNUM=SP.SNUMP.PNAME=螺栓S.CITY=南京SP.QUAN10000SNUM,SNAMESNUM,PNUMPNUMPSSP用投影操作消除对查询无用的属性小关系先做连接本讲稿第三十五页，共四十九页 数据库原理 10/4/2022优化实例例：对课本第二章例9”查询至少选修了一门其直接先行课为5号课程的学生姓名”的关系代数表达式（如下）进行优化。其中，C是课程表，S是学生表，SC是学生选课表。在优化规则中没有对自然连接的直接优化，我们把自然连接分解为笛卡儿积和选择。Sname(Cpno=5(C SC S)本讲稿第三十六页，共四十九页 数据库原理 10/4/2022分解后的关系代数表达式SCSC本讲稿第三十七页，共四十九页 数据库原理 10/4/2022第一步：利用规则4分解选择运算SCSC本讲稿第三十八页，共四十九页 数据库原理 10/4/2022第二步：尽量下放选择运算SCSC本讲稿第三十九页，共四十九页 数据库原理 10/4/2022SCSC第二步（2）：下放完成后本讲稿第四十页，共四十九页 数据库原理 10/4/2022第三步：尽量下放投影运算SCSCE本讲稿第四十一页，共四十九页 数据库原理 10/4/2022第三步：尽量下放投影运算SCSC本讲稿第四十二页，共四十九页 数据库原理 10/4/2022第三步（2）：第一次下放后SCSC本讲稿第四十三页，共四十九页 数据库原理 10/4/2022第三步（3）：第二次下放SCSC本讲稿第四十四页，共四十九页 数据库原理 10/4/2022第三步（3）：第二次下放SCSC本讲稿第四十五页，共四十九页 数据库原理 10/4/2022第三步（4）：第二次下放后SCSC本讲稿第四十六页，共四十九页 数据库原理 10/4/2022SCSC第四步：尽量把选择和投影靠在一起本讲稿第四十七页，共四十九页 数据库原理 10/4/2022第五步：分组SCSC本讲稿第四十八页，共四十九页 数据库原理 10/4/2022作业nP2752本讲稿第四十九页，共四十九页
