第四章关系系统的查询优化精选文档.ppt

第四章关系系统的查第四章关系系统的查询优化询优化本讲稿第一页，共五十二页第四章第四章关系系统的查询优化关系系统的查询优化4.1关系系统关系系统4.2查询优化处理查询优化处理数数据据库库系系统统原原理理本讲稿第二页，共五十二页第四章第四章 关系系统的查询优化关系系统的查询优化学习要求学习要求 了解关系系统的基本概念及分类标准，初步了解了解关系系统的基本概念及分类标准，初步了解查询处理的基本步骤，理解查询优化的意义，掌握关查询处理的基本步骤，理解查询优化的意义，掌握关系代数优化的算法及相应的等价变换。系代数优化的算法及相应的等价变换。学习重点学习重点利用关系优化规则对关系语法树进行优化。利用关系优化规则对关系语法树进行优化。数数据据库库系系统统原原理理本讲稿第三页，共五十二页第四章第四章关系系统的查询优化关系系统的查询优化4.1关系系统关系系统4.2查询优化处理查询优化处理数数据据库库系系统统原原理理本讲稿第四页，共五十二页第一节第一节 关系系统关系系统关系模型关系模型关系数据结构关系数据结构域及域上定义的关系域及域上定义的关系关系操作关系操作关系代数：并、交、差、广义笛卡尔积、选择、投关系代数：并、交、差、广义笛卡尔积、选择、投影、连接、除等影、连接、除等 关系完整性关系完整性实体完整性、参照完整性、用户自己定义的完整性实体完整性、参照完整性、用户自己定义的完整性关关系系系系统统的的查查询询优优化化本讲稿第五页，共五十二页关系系统关系系统(续续)关系系统的定义关系系统的定义能能够够在在一一定定程程度度上上支支持持关关系系模模型型的的数数据据库库管管理系统是关系系统。理系统是关系系统。定定义义4.1一个系统是关系系统当且仅当它：一个系统是关系系统当且仅当它：支支持持关关系系数数据据库库（即即关关系系数数据据结结构构）。从从用用户户观观点点看看，数数据据库库是是由由表表构构成成的的，并并且且系系统统中只有表这种结构。中只有表这种结构。支支持持选选择择、投投影影和和（自自然然）连连接接运运算算。对对这这些运算不要求用户定义任何物理存取路径。些运算不要求用户定义任何物理存取路径。关关系系系系统统的的查查询询优优化化本讲稿第六页，共五十二页二、关系系统的分类二、关系系统的分类 分类依据分类依据 依据关系系统支持关系模型的程度不同。依据关系系统支持关系模型的程度不同。分类分类S：结结构构I：完整性：完整性M：数据操：数据操纵纵关关系系系系统统的的查查询询优优化化本讲稿第七页，共五十二页数据结构数据结构数据操纵数据操纵数据完整性数据完整性 表式结构表式结构表表 最小关系系统最小关系系统表表选择、投影、连接选择、投影、连接关系完备的系统关系完备的系统表表全部全部 全关系系统全关系系统全部全部全部全部完全支持完全支持关系系统的分类关系系统的分类（续）（续）关关系系系系统统的的查查询询优优化化本讲稿第八页，共五十二页第二节第二节 关系系统的查询优化关系系统的查询优化 关系系统的查询处理关系系统的查询处理查询优化概述查询优化概述查询优化问题的提出查询优化问题的提出关系代数的优化规则关系代数的优化规则关系代数的优化算法关系代数的优化算法查询优化的一般步骤查询优化的一般步骤 关关系系系系统统的的查查询询优优化化本讲稿第九页，共五十二页一、关系系统的查询处理一、关系系统的查询处理1、查询处理步骤、查询处理步骤关关系系系系统统的的查查询询优优化化查询语句转化成关系代查询语句转化成关系代数表达式数表达式本讲稿第十页，共五十二页关系系统的查询处理（续）关系系统的查询处理（续）2、实现查询操作的算法示例、实现查询操作的算法示例例例4.1选择操作的实现选择操作的实现Select*FromStudentWhere;的几种情况：的几种情况：C1:Sno=95001C2:Sage20简单的全表扫描方法简单的全表扫描方法对查询的基本表顺序扫描，逐一检查每个元对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结组是否满足选择条件，把满足条件的元组作为结果输出。果输出。关关系系系系统统的的查查询询优优化化本讲稿第十一页，共五十二页 选择操作的实现示例（续）选择操作的实现示例（续）索引扫描方法索引扫描方法 通过索引先找到满足条件的元组主码或元组通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找指针，再通过元组指针直接在查询的基本表中找到元组。到元组。【C1例例】Sno=95001，并且在，并且在Sno上有索引，上有索引，则则可可以使用索引得到以使用索引得到Sno为为95001元元组组的指的指针针，然后通，然后通过过元元组组指指针针在在Student表中表中检检索到索到该该学生。学生。【C2例例】Sage20，并且，并且Sage上有上有B+树树索引，索引，则则可以可以使用使用B+树树索引找到索引找到Sage=20的索引的索引项项，以此，以此为为入口点在入口点在B+树树的的顺顺序集上得到序集上得到Sage20的所有元的所有元组组指指针针，然后通，然后通过这过这些元些元组组指指针针到到Student表中表中检检索到所有年索到所有年龄龄大于大于20的学生。的学生。关关系系系系统统的的查查询询优优化化本讲稿第十二页，共五十二页Sage20的一的一组组元元组组指指针针【C3例例】Sdept=CSAndSage20，如果，如果Sdept和和Sage上都上都有索引，有索引，则则：另一种算法：另一种算法：关关系系系系统统的的查查询询优优化化 选择操作的实现示例（续）选择操作的实现示例（续）Sdept=CS的一的一组组元元组组指指针针Sdept=CS的的一一组组元元组组指指针针Sdept=CS的一的一组组元元组组指指针针Sage20的一的一组组元元组组指指针针指指针针交交集集满足条件的学生信息满足条件的学生信息Student表表Student表表Sage20的一的一组组元元组组指指针针满足条件的学满足条件的学生信息生信息满满足足Sdept=CS条件的元条件的元组组信息信息本讲稿第十三页，共五十二页实现查询操作的算法示例（续）实现查询操作的算法示例（续）例例4.2连连接操作的接操作的实现实现Select*FromStudent,SCWhereStudent.Sno=SC.Sno嵌套循环方法嵌套循环方法关关系系系系统统的的查查询询优优化化学号学号Sno姓名姓名Sname性别性别Ssex年龄年龄Sage所在系所在系Sdept95002950019500395004李勇李勇刘晨刘晨王敏王敏张立张立男男女女女女男男20191819CSISMAISStudent学号学号Sno课程号课程号Cno成绩成绩Grade9500195002950019500295002123239290888580SC对对Student中的每一个元中的每一个元组组，检查检查SC中的每一个元中的每一个元组组，若在，若在连连接属性上相接属性上相等，等，则连则连接接输输出，直到出，直到Student中的元中的元组处组处理完理完为为止。止。本讲稿第十四页，共五十二页 连接操作的实现（续）连接操作的实现（续）排序排序-合并方法合并方法学号学号Sno姓名姓名Sname性别性别Ssex年龄年龄Sage所在系所在系Sdept95001950029500395004李勇李勇刘晨刘晨王敏王敏张立张立男男女女女女男男20191819CSISMAISStudent学号学号Sno课程号课程号Cno成绩成绩Grade9500195001950019500295002123239285889080SC关关系系系系统统的的查查询询优优化化取取Student表中第一个表中第一个Sno，依次，依次扫扫描描SC表中具有相同表中具有相同Sno的元的元组组，把他，把他们连们连接起来；接起来；当当扫扫描到描到Sno不相同的第一个不相同的第一个SC元元组时组时，返回，返回Student表表扫扫描它描它的下一个元的下一个元组组，再，再扫扫描描SC表中具有相同表中具有相同Sno的元的元组组，把它，把它们连们连接接起来。起来。本讲稿第十五页，共五十二页二、查询优化概述二、查询优化概述查询优查询优化是从众多可供化是从众多可供选择选择的的执执行策略和操行策略和操作算法中，作算法中，选择选择一个高效一个高效执执行的行的查询处查询处理策略。理策略。按照按照优优化的化的层层次可以分次可以分为为代数代数优优化和物理化和物理优优化。化。代数代数优优化：化：是指关系代数表达式的是指关系代数表达式的优优化，按照化，按照一定的一定的规则规则，改，改变变代数表达式中操作的次序和代数表达式中操作的次序和组组合，使合，使查询执查询执行效率更高。行效率更高。物理物理优优化：化：则则是指存取路径和底是指存取路径和底层层操作算法的操作算法的选择选择。关关系系系系统统的的查查询询优优化化本讲稿第十六页，共五十二页 查询优化概述（续）查询优化概述（续）目目前前RDBMS通通过过某某种种代代价价模模型型计计算算出出各各种种查查询询执执行行策策略的略的执执行代价，然后行代价，然后选选取代价最小的取代价最小的执执行方案。行方案。查询查询的的执执行开行开销销主要包括主要包括集中式数据集中式数据库库磁磁盘盘存取存取块块数（数（I/O代价）代价）处处理机理机时间时间（CPU代价）代价）查询查询的内存开的内存开销销分布式数据分布式数据库库I/O代价代价+CPU代价代价+内存代价内存代价+通信代价通信代价查询优查询优化的化的总总目目标标选选择择有有效效策策略略，求求得得给给定定关关系系表表达达式式的的值值，使得使得查询查询代价最小。代价最小。关关系系系系统统的的查查询询优优化化本讲稿第十七页，共五十二页三、查询优化问题的提出三、查询优化问题的提出例例4.3：求：求选选修了修了2号号课课程的学生姓名程的学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=2;系统可以用多种等价的关系代数表达式来完系统可以用多种等价的关系代数表达式来完成这一查询。成这一查询。关关系系系系统统的的查查询询优优化化本讲稿第十八页，共五十二页查询优化问题的提出（续）查询优化问题的提出（续）假假设设1外存：外存：Student表中有表中有1000条学生条学生记录记录SC表中有表中有10000条条选课记录选课记录 其中其中选选修修2号号课课程的程的选课记录为选课记录为50条条假假设设2内存：内存：一个内存一个内存块块可以装可以装10个个Student元元组组或或100个个SC元元组组一个内存一个内存块块可以装可以装10个个Student和和SC的的连连接接结结果元果元组组内存中一次可以存放内存中一次可以存放5块块Student元元组组、1块块SC元元组组和和若干若干块连块连接接结结果元果元组组假假设设3读读写速度：写速度：20块块/秒秒假假设设4连连接方法：接方法：基于数据基于数据块块的嵌套循的嵌套循环环法法关关系系系系统统的的查查询询优优化化本讲稿第十九页，共五十二页1、第一种方法、第一种方法关关系系系系统统的的查查询询优优化化查询优化问题的提出（续）查询优化问题的提出（续）内存块内存块100Student表表SC表表内存块内存块1内存块内存块2内存块内存块3内存块内存块4内存块内存块5一般连接的方法：一般连接的方法：内存块内存块1内存块内存块2内存块内存块100读读Student表表100块块，读读SC表表20遍，每遍遍，每遍100块块。本讲稿第二十页，共五十二页计计算广算广义义笛卡笛卡尔尔集集StudentSC读读取取总块总块数数=读读Student表表块块数数+读读SC表遍数表遍数*每遍每遍块块数数=1000/10+(1000/(105)(10000/100)=100+20100=2100读读数据数据时间时间=2100/20=105秒秒中中间结间结果大小（果大小（连连接后的元接后的元组组数）数）=1000*10000=107(1千万条元千万条元组组)写中写中间结间结果果时间时间=10000000/10/20=50000秒秒选择选择操作操作读读数据数据时间时间=50000秒秒投影操作投影操作总时间总时间=1055000050000秒秒=100105秒秒=27.8小小时时关关系系系系统统的的查查询询优优化化第一种方法（续）第一种方法（续）本讲稿第二十一页，共五十二页2、第二种方法、第二种方法计计算自然算自然连连接接读读取取总块总块数数=2100块块读读数据数据时间时间=2100/20=105秒秒中中间结间结果大小果大小=10000（减少（减少1000倍）倍）写中写中间结间结果果时间时间=10000/10/20=50秒秒选择选择操作操作读读取中取中间间文件文件块块，执执行行选择选择运算，花运算，花费时间费时间50秒秒投影操作投影操作把第二步的把第二步的结结果投影果投影输输出出总时间总时间(1055050)秒秒205秒秒=3.4分分关关系系系系统统的的查查询询优优化化查询优化问题的提出（续）查询优化问题的提出（续）本讲稿第二十二页，共五十二页3、第三种方法、第三种方法 Q3=Sname(Student SC.Cno=2(SC)选择选择操作操作读读SC表表总块总块数数=10000/100=100块块读读数据数据时间时间=100/20=5秒秒中中间结间结果大小果大小=50条（条（满满足条件的元足条件的元组组只有只有50个），不个），不必使用中必使用中间间文件。文件。自然自然连连接操作接操作读读Student表表总块总块数数=1000/10=100块块（只需（只需读读一遍一遍该该表）表）读读数据数据时间时间=100/20=5秒秒投影操作投影操作把把连连接接结结果投影果投影输输出。出。总时间总时间55秒秒10秒秒关关系系系系统统的的查查询询优优化化查询优化问题的提出（续）查询优化问题的提出（续）本讲稿第二十三页，共五十二页四、关系代数的优化规则四、关系代数的优化规则关关系系代代数数优优化化策策略略是是通通过过对对关关系系代代数数表表达达式式的的等等价变换来提高查询效率。价变换来提高查询效率。关系代数表达式等价关系代数表达式等价指指把把相相同同的的关关系系代代入入两两个个关关系系代代数数表表达达式式所所得得到到的的结结果果是相同的。是相同的。两个关系表达式两个关系表达式E1和和E2是等价的，是等价的，记为记为E1E2。关关系系系系统统的的查查询询优优化化本讲稿第二十四页，共五十二页关系代数的优化规则（续）关系代数的优化规则（续）1、常用的等价、常用的等价变换规则变换规则设设E1、E2是关系代数表达式，是关系代数表达式，F是条件表达式。是条件表达式。（1）连连接、笛卡接、笛卡尔尔积积交交换换律律E1E2E2E1E1E2E2E1E1E2E2E1（2）连连接、笛卡接、笛卡尔尔积积的的结结合律合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)关关系系系系统统的的查查询询优优化化FFF1F1F2F2本讲稿第二十五页，共五十二页 常用的等价变换规则（续）常用的等价变换规则（续）（3）投影的）投影的级联级联（串接定律）（串接定律）假假设设：1)E是关系代数表达式是关系代数表达式2)Ai(i=1，2，n),Bj(j=l，2，m)是属性名是属性名3)A1,A2,An是是Bl，B2，Bm的的子集子集。则则：（4）选择选择的的级联级联（串接定律）（串接定律）选择选择的串接律的串接律说说明明选择选择条件可以合并。条件可以合并。关关系系系系统统的的查查询询优优化化本讲稿第二十六页，共五十二页关系代数等价变换规则（续）关系代数等价变换规则（续）（5）选择选择与投影的交与投影的交换换律律假假设设:选择选择条件条件F只涉及属性只涉及属性A1，An假假设设:F中有不属于中有不属于A1,An的属性的属性B1,Bm关关系系系系统统的的查查询询优优化化本讲稿第二十七页，共五十二页关系代数等价变换规则（续）关系代数等价变换规则（续）（6）选择选择与笛卡与笛卡尔尔积积的交的交换换律律假假设设：F中涉及的属性都是中涉及的属性都是E1中的属性，中的属性，则则假假设设：F=F1F2，并并且且F1只只涉涉及及E1中中的的属属性性，F2只只涉涉及及E2中中的的属性，属性，则则由上面的等价由上面的等价变换规则变换规则1，4，6可推出可推出假假设设：F=F1F2，F1只只涉涉及及E1中中的的属属性性，F2涉涉及及E1和和E2两两者者的的属性，属性，则则关关系系系系统统的的查查询询优优化化 F(E1E2)F1F2(E1E2)F2(F1(E1E2)F2(F1(E1)E2)F(E1E2)F1F2(E1E2)F1(F2(E1E2)F1(F2(E2)E1)F1(E1)F2(E2)本讲稿第二十八页，共五十二页关系代数等价变换规则（续）关系代数等价变换规则（续）（7）选择选择与并的分配律与并的分配律假假设设：E=E1E2，E1，E2有相同的属性名有相同的属性名（8）选择选择与差运算的分配律与差运算的分配律假假设设：E1与与E2有相同的属性名有相同的属性名（9）选择对选择对自然自然连连接的分配律接的分配律假假设设：F只涉及只涉及E1和和E2的公共属性的公共属性F(E1 E2)F(E1)F(E2)关关系系系系统统的的查查询询优优化化本讲稿第二十九页，共五十二页关系代数等价变换规则（续）关系代数等价变换规则（续）（10）投影与笛卡）投影与笛卡尔尔积积的分配律的分配律假假设设：E1和和E2是两个关系表达式，是两个关系表达式，A1，An是是E1的属性，的属性，B1，Bm是是E2的属性，的属性，则则（11）投影与并的分配）投影与并的分配假假设设：E1和和E2有相同的属性名，有相同的属性名，则则关关系系系系统统的的查查询询优优化化本讲稿第三十页，共五十二页关系代数等价变换规则小结关系代数等价变换规则小结1-2:连连接、笛卡接、笛卡尔尔积积的交的交换换律、律、结结合律合律3：投影运算的合并或分解：投影运算的合并或分解4：选择选择运算的合并或分解运算的合并或分解5-6：选择选择运算与其他运算的交运算与其他运算的交换换律律7-9：选择选择运算与其他运算的分配律运算与其他运算的分配律10-11：投影运算与其他运算的分配律投影运算与其他运算的分配律关关系系系系统统的的查查询询优优化化本讲稿第三十一页，共五十二页2、关系代数的、关系代数的优优化化规则规则（1）选择选择运算运算应应尽可能先做尽可能先做。目的：减少中目的：减少中间结间结果大小果大小（2）投影运算和）投影运算和选择选择运算同运算同时时做。做。目的：避免重复目的：避免重复扫扫描关系描关系（3）将投影运算与其前面或后面的双目运算）将投影运算与其前面或后面的双目运算结结合。合。目的：减少目的：减少扫扫描关系的遍数。描关系的遍数。关关系系系系统统的的查查询询优优化化关系代数等价变换规则（续）关系代数等价变换规则（续）本讲稿第三十二页，共五十二页查询优化的一般准则查询优化的一般准则（续）（续）（4）把把某某些些选选择择同同在在它它前前面面执执行行的的笛笛卡卡儿儿积积结结合合起起来来成成为为一个一个连连接运算。接运算。例：例：Student.Sno=SC.Sno(StudentSC)StudentSC例例4.3中：中：关关系系系系统统的的查查询询优优化化本讲稿第三十三页，共五十二页（5）提取公共子表达式。）提取公共子表达式。一个关系表达式如果包含多个相同的子表达式，那一个关系表达式如果包含多个相同的子表达式，那么只需么只需计计算一次公共表达式，把所得的中算一次公共表达式，把所得的中间结间结果存起来，果存起来，以后每遇到以后每遇到这这种子表达式，只需种子表达式，只需检检索中索中间结间结果而无果而无须须重重新新计计算。算。关关系系系系统统的的查查询询优优化化查询优化的一般准则查询优化的一般准则（续）（续）本讲稿第三十四页，共五十二页五、关系代数的优化算法五、关系代数的优化算法 1、查询树查询树在在查查询询优优化化过过程程中中，查查询询语语句句被被转转换换为为更更适适合合处处理理的的内内部部表表示示，通通常常这这种种内内部部表表示示表表现现为为查查询询树树的的形形式，它的构造方法如下式，它的构造方法如下:（1）每一个叶）每一个叶节节点点对应对应于于查询查询中的基本关系中的基本关系;（2）非叶）非叶节节点是关系代数运算点是关系代数运算产产生的中生的中间间关系关系;（3）树树的根的根节节点代表点代表查询结查询结果果;（4）运算按照从叶到根的）运算按照从叶到根的顺顺序序执执行。行。关关系系系系统统的的查查询询优优化化本讲稿第三十五页，共五十二页 查询树（续）查询树（续）例例4.3中的关系代数表达式：中的关系代数表达式：转转化化为查询树为查询树：关关系系系系统统的的查查询询优优化化本讲稿第三十六页，共五十二页关系代数的优化算法（续）关系代数的优化算法（续）2、关系表达式的、关系表达式的优优化算法化算法输入：一个关系表达式的查询树。输入：一个关系表达式的查询树。输出：优化的查询树。输出：优化的查询树。方法：方法：1分解分解选择选择运算。运算。2通通过过交交换选择换选择运算，将其尽可能移到叶端。运算，将其尽可能移到叶端。3通通过过交交换换投影运算，将其尽可能移到叶端。投影运算，将其尽可能移到叶端。4合并串接的合并串接的选择选择和投影，以便能同和投影，以便能同时执时执行或在一次行或在一次扫扫描中完成。描中完成。5对对内内结结点分点分组组。6生成程序。生成程序。关关系系系系统统的的查查询询优优化化本讲稿第三十七页，共五十二页关系代数的优化算法关系代数的优化算法(续续)（1）分解选择运算。）分解选择运算。利用利用规则规则4把形如把形如 F1F2Fn(E)变换为变换为 F1(F2(Fn(E)（2）通通过过交交换换选选择择运运算算，将将其其每每个个选选择择尽尽可可能能移移到到叶叶端。端。对对每每一一个个选选择择，利利用用规规则则49尽尽可可能能把把它它移移到到树树的的叶端。叶端。（3）通）通过过交交换换投影运算，将其尽可能移到叶端。投影运算，将其尽可能移到叶端。对对每每一一个个投投影影利利用用规规则则3，5，l0，11中中的的一一般般形形式式尽可能把它移向尽可能把它移向树树的叶端。的叶端。关关系系系系统统的的查查询询优优化化本讲稿第三十八页，共五十二页关系代数表达式的优化算法关系代数表达式的优化算法(续续)（4）合合并并串串接接的的选选择择和和投投影影，以以便便能能同同时时执执行行或或在在一一次次扫扫描中完成。描中完成。利利用用规规则则35把把选选择择和和投投影影的的串串接接合合并并成成单单个个选择选择、单单个投影或一个个投影或一个选择选择后跟一个投影。后跟一个投影。使使多多个个选选择择或或投投影影能能同同时时执执行行,或或在在一一次次扫扫描描中全部完成。中全部完成。尽尽管管这这种种变变换换似似乎乎违违背背“投投影影尽尽可可能能早早做做”的的原原则则，但，但这样这样做效率更高。做效率更高。关关系系系系统统的的查查询询优优化化本讲稿第三十九页，共五十二页关系代数表达式的优化算法关系代数表达式的优化算法(续续)（5）对对内内结结点分点分组组把上述得到的把上述得到的语语法法树树的内的内节节点分点分组组。每每一一双双目目运运算算(,-)和和它它所所有有的的直直接接祖祖先先（,运算）运算）为为一一组组。如如果果其其后后代代直直到到叶叶子子全全是是单单目目运运算算，则则也也将将它它们们并并入入该该组组，但但当当双双目目运运算算是是笛笛卡卡尔尔积积()而而且且其其后后的的选选择择不不能能与与它它结结合合为为等等值值连连接接时时除外。把除外。把这这些些单单目运算目运算单单独分独分为为一一组组。关关系系系系统统的的查查询询优优化化本讲稿第四十页，共五十二页关系代数表达式的优化算法关系代数表达式的优化算法(续续)（6）生成程序）生成程序生生成成一一个个程程序序，每每组组结结点点的的计计算算是是程程序序中中的的一步。一步。各各步步的的顺顺序序是是任任意意的的，只只要要保保证证任任何何一一组组的的计算不会在它的后代组之前计算计算不会在它的后代组之前计算。关关系系系系统统的的查查询询优优化化本讲稿第四十一页，共五十二页例例4.4给给出例出例4.3中中SQL语语句的代数句的代数优优化算法。化算法。（1）把）把SQL语语句句转换转换成成查询树查询树，对应对应的关系表的关系表达式达式为为：关关系系系系统统的的查查询询优优化化关系代数表达式的优化算法关系代数表达式的优化算法(续续)本讲稿第四十二页，共五十二页关系代数查询树关系代数查询树 关关系系系系统统的的查查询询优优化化关系代数表达式的优化算法关系代数表达式的优化算法(续续)Sname Student.Sno=SC.SnoSC.Cno=2 StudentSC本讲稿第四十三页，共五十二页（2）对查询树进对查询树进行行优优化化分解分解选择选择运算，运算，对应对应的关系代数表达式的关系代数表达式为为:Sname(Student.Sno=SC.Sno(SC.Cno=2(StudentSC);关关系系系系统统的的查查询询优优化化关系代数表达式的优化算法关系代数表达式的优化算法(续续)Sname SC.Cno=2 StudentSC Student.Sno=SC.Sno优化后的关系代数查询树优化后的关系代数查询树：本讲稿第四十四页，共五十二页对查询树进行优化（续）对查询树进行优化（续）将将选择选择运算下移运算下移,对应对应的关系代数表达式的关系代数表达式为为:Sname(Student.Sno=SC.Sno(StudentSC.Cno=2(SC);关关系系系系统统的的查查询询优优化化优化后的关系代数查询树优化后的关系代数查询树：Sname StudentSC SC.Cno=2 Student.Sno=SC.Sno本讲稿第四十五页，共五十二页将将选择选择/笛卡儿笛卡儿积变为积变为自然自然连连接，接，对应对应的关系代的关系代数表达式数表达式为为：Sname(StudentSC.Cno=2(SC);对查询树进行优化（续）对查询树进行优化（续）关关系系系系统统的的查查询询优优化化Sname StudentSC SC.Cno=2 优化后的关系代数查询树优化后的关系代数查询树：本讲稿第四十六页，共五十二页将投影运算下移将投影运算下移,对应对应的关系代数表达式的关系代数表达式为为:Sname(Sno,Sname(Student)Sno(SC.Cno=2(SC)关关系系系系统统的的查查询询优优化化对查询树进行优化（续）对查询树进行优化（续）Sname StudentSC SC.Cno=2 Sno,SnameSno优化后的关系代数查询树优化后的关系代数查询树：本讲稿第四十七页，共五十二页 课堂练习课堂练习对对学生学生-课课程数据程数据库库有如下的有如下的查询查询：SELECTCnameFROMStudent,Course,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=Course.CnoANDStudent.Sdept=IS;试画出用初始查询的语法树，并用关系代数表试画出用初始查询的语法树，并用关系代数表达式优化算法对原始语法树进行优化处理，画出达式优化算法对原始语法树进行优化处理，画出优化后的标准语法树。优化后的标准语法树。本讲稿第四十八页，共五十二页六、查询优化的一般步骤六、查询优化的一般步骤 1把把查询转换查询转换成某种内部表示（成某种内部表示（查询树查询树）2代数代数优优化：化：对查询树进对查询树进行行优优化化3物理物理优优化：化：选择选择底底层层的存取路径的存取路径4生成生成查询计查询计划，划，选择选择代价最小的方案代价最小的方案关关系系系系统统的的查查询询优优化化本讲稿第四十九页，共五十二页本章小结本章小结 关系系关系系统统关系系关系系统统定定义义当且当且仅仅当它至少支持：当它至少支持：关系数据关系数据库库（即关系数据（即关系数据结结构）构）支支持持选选择择、投投影影和和（自自然然）连连接接运运算算，且且不不要要求求用用户户定定义义任何物理存取路径任何物理存取路径关系系统的分类关系系统的分类表式系统表式系统最小关系系统最小关系系统关系完备系统关系完备系统全关系系统全关系系统 关关系系系系统统的的查查询询优优化化本讲稿第五十页，共五十二页本章小结本章小结（续）（续）关系系统的查询优化关系系统的查询优化查询处理的步骤查询处理的步骤代数优化：关系代数表达式的优化代数优化：关系代数表达式的优化关系代数优化规则关系代数优化规则关系代数的等价变换规则关系代数的等价变换规则启发式优化规则启发式优化规则关系代数表达式的优化算法关系代数表达式的优化算法查询树的表达查询树的表达查询树的优化过程查询树的优化过程物理优化：存取路径和低层操作算法的选择物理优化：存取路径和低层操作算法的选择 关关系系系系统统的的查查询询优优化化本讲稿第五十一页，共五十二页 谢谢！谢谢！本讲稿第五十二页，共五十二页