第九章 关系查询处理和查询优化.ppt

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

1、第九章关系查询处理和查询优化2学习目标学习目标掌握关系系统查询优化的步骤掌握关系系统查询优化的步骤掌握关系系统查询优化的一般准则掌握关系系统查询优化的一般准则34569.1.1 9.1.1 关系数据库系统的查询处理关系数据库系统的查询处理1.1.查询处理步骤查询处理步骤查询处理步骤查询处理步骤：(2)(2)查询检查查询检查根据数据字典对合法的查询语句进行语义检查根据数据字典对合法的查询语句进行语义检查 检查检查检查检查数据库对象数据库对象数据库对象数据库对象是否存在和是是否存在和是是否存在和是是否存在和是否有效；否有效；否有效；否有效；根据数据字典中的根据数据字典中的根据数据字典中的根据数据字

2、典中的用户权限用户权限用户权限用户权限和和和和完整性约束完整性约束完整性约束完整性约束定义对用户的定义对用户的定义对用户的定义对用户的存取存取存取存取权限权限权限权限进行检查；进行检查；进行检查；进行检查；检查后，把查询语句转换为关检查后，把查询语句转换为关检查后，把查询语句转换为关检查后，把查询语句转换为关系代数表达式（系代数表达式（系代数表达式（系代数表达式（查询树查询树查询树查询树）79.1.1 9.1.1 关系数据库系统的查询处理关系数据库系统的查询处理1.1.查询处理步骤查询处理步骤查询处理步骤查询处理步骤：(3)(3)查询优化查询优化就是从许多执行策略和操作算法中，选择一就是从许多

3、执行策略和操作算法中，选择一个高效率的查询处理策略。个高效率的查询处理策略。代数优化代数优化代数优化代数优化：是指关系代数表达式的优化是指关系代数表达式的优化 即改变关系代数表达式中操作的即改变关系代数表达式中操作的 次序和组合。次序和组合。物理优化物理优化物理优化物理优化：是指存取路径和底层操作算法的是指存取路径和底层操作算法的 选择选择89.1.1 9.1.1 关系数据库系统的查询处理关系数据库系统的查询处理1.1.查询处理步骤查询处理步骤查询处理步骤查询处理步骤：(4)(4)查询执行查询执行依据依据优化器优化器得到的执行策略生成查询计划；得到的执行策略生成查询计划；由由代码生成器代码生成

4、器生成执行这个查询计划的代码。生成执行这个查询计划的代码。99.1.2 9.1.2 实现查询操作的算法示例实现查询操作的算法示例1.1.选择操作的实现选择操作的实现选择操作的实现选择操作的实现：例例1:Select*fromstudentwhere几种情况：几种情况：无条件无条件Sno=0215121Sage20Sdept=CSandSage20109.1.2 9.1.2 实现查询操作的算法示例实现查询操作的算法示例1.1.选择操作的实现选择操作的实现选择操作的实现选择操作的实现：例例1:Select*fromstudentwhere(1)(1)简单的全表扫描方法简单的全表扫描方法n 方法：方

5、法：对查询的基表逐一、顺序检查，满足条件的输对查询的基表逐一、顺序检查，满足条件的输出。出。n 适用范围：适用范围：小表小表 119.1.2 9.1.2 实现查询操作的算法示例实现查询操作的算法示例1.1.选择操作的实现选择操作的实现选择操作的实现选择操作的实现：(2)(2)索引扫描方法索引扫描方法n 前提：前提：在选择条件的属性上有索引在选择条件的属性上有索引n 方法：方法：通过索引先找到满足条件的元组指针通过索引先找到满足条件的元组指针 通过指针在查询的基本表中找到元组通过指针在查询的基本表中找到元组例如：例如：Sno=0215121 Sage20例如：例如：Sdept=CSandSage

6、20有两种方法：有两种方法：索引的交集：索引的交集 ：先找到满足一个条件的指针组，在基本：先找到满足一个条件的指针组，在基本表中找到相应的元组，并判断第二个条件。表中找到相应的元组，并判断第二个条件。129.1.2 9.1.2 实现查询操作的算法示例实现查询操作的算法示例2.2.连接操作的实现连接操作的实现连接操作的实现连接操作的实现：例例2:Select*FROMstudent,SCWHEREStudent.Sno=SC.Sno(1)(1)嵌套循环法嵌套循环法 提示提示提示提示：StudentStudentStudentStudent表扫描一遍表扫描一遍表扫描一遍表扫描一遍 SCSCSCSC

7、表扫描遍数与表扫描遍数与表扫描遍数与表扫描遍数与StudentStudentStudentStudent表的元组个数相同表的元组个数相同表的元组个数相同表的元组个数相同(2)(2)排序合并法排序合并法 提示：提示：提示：提示：StudentStudentStudentStudent和和和和SCSCSCSC表各扫描一遍表各扫描一遍表各扫描一遍表各扫描一遍(3)(3)索引连接方法索引连接方法(4)Hash Join(4)Hash Join方法方法13第第9 9章章 关系系统及其查询优化关系系统及其查询优化9.1关系数据库系统的查询处理关系数据库系统的查询处理9.2关系系统的查询优化关系系统的查询优

8、化9.3代数优化代数优化9.4物理优化物理优化149.2 9.2 关系系统的查询优化关系系统的查询优化 9.2.1查询优化概述查询优化概述9.2.2一个实例一个实例9.2.3一般优化准则一般优化准则159.2.1 9.2.1 查询优化概述查询优化概述 1.1.1.1.查询优化的必要性查询优化的必要性查询优化的必要性查询优化的必要性查询优化极大地影响查询优化极大地影响RDBMSRDBMS的性能。的性能。2.2.2.2.查询优化的可能性查询优化的可能性查询优化的可能性查询优化的可能性关关系系数数据据语语言言的的级级别别很很高高，使使DBMSDBMS可可以以从从关关系表达式中分析查询系表达式中分析查

9、询语义语义。n用用户户不不必必考考虑虑如如何何最最好好地地表表达达查查询询以以获获得得较较好好的效率的效率!163.3.3.3.系统优化的特点：系统优化的特点：系统优化的特点：系统优化的特点：系统系统可以比用户程序的优化可以比用户程序的优化做得更好做得更好(1)(1)优优化化器器从从数数据据字字典典中中获获取取许许多多统统计计信信息息，而而用用户户程程序序则难以获得这些信息则难以获得这些信息 。(2)(2)如如果果数数据据库库的的物物理理统统计计信信息息改改变变，系系统统自自动动对对查查询询重重新优化新优化以选择相适应的执行计划。以选择相适应的执行计划。在非关系系统中必须重写程序，在应用中不太

10、现实在非关系系统中必须重写程序，在应用中不太现实(3)(3)优优化化器器可可以以考考虑虑数数百百种种不不同同的的执执行行计计划划，而而程程序序员员一一般只能考虑有限的几种可能性。般只能考虑有限的几种可能性。(4)(4)优化器中包括了很多复杂的优化器中包括了很多复杂的优化技术优化技术。9.2.1 9.2.1 查询优化概述查询优化概述 174.4.4.4.查询优化的目标：查询优化的目标：查询优化的目标：查询优化的目标：选择有效策略，求得给定关系表达式的值。选择有效策略，求得给定关系表达式的值。5.5.5.5.实际系统查询优化的步骤实际系统查询优化的步骤实际系统查询优化的步骤实际系统查询优化的步骤9

11、.2.1 9.2.1 查询优化概述查询优化概述 189.2.1 9.2.1 查询优化概述查询优化概述 6.6.6.6.6.6.代价模型代价模型代价模型代价模型代价模型代价模型查询处理的代价可以通过该查询对各种资源的使用查询处理的代价可以通过该查询对各种资源的使用情况进行衡量。情况进行衡量。n资源包括：资源包括：磁盘存取（磁盘存取（I/0I/0）执行查询所用的执行查询所用的CPUCPU时间时间 并行并行/分布式数据库中通信的开销分布式数据库中通信的开销在集中式、大型数据库中，在集中式、大型数据库中，磁盘访问磁盘访问通常是主要的通常是主要的代价代价199.2.1 9.2.1 查询优化概述查询优化概

12、述 6.6.6.6.6.6.代价模型代价模型代价模型代价模型代价模型代价模型n集中式数据库集中式数据库单用户系统单用户系统单用户系统单用户系统:总代价总代价=I/O代价代价+CPU代价代价多用户系统多用户系统总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价n分布式数据库分布式数据库总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价+通信代价通信代价209.2.2 9.2.2 一个实例一个实例例：求选修了课程例：求选修了课程2 2号的学生姓名号的学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoAND

13、SC.Cno=2;219.2.2 9.2.2 一个实例一个实例例：求选修了课程例：求选修了课程2 2号的学生姓名号的学生姓名假设假设假设假设1.外存：外存：Student:1000Student:1000条条,SC:10000,SC:10000条条,选修选修2 2号课程号课程:50:50条条2.内存：内存：一个内存块装元组一个内存块装元组:10:10个个Student,Student,或或100100个个SC,SC,内存中一次可以存放内存中一次可以存放:5:5块块StudentStudent元组、元组、1 1块块SCSC元组和若干块连接结果元组元组和若干块连接结果元组3：读写速度：读写速度：2

14、020块块/秒秒4：连接方法：连接方法：基于数据块的嵌套循环法基于数据块的嵌套循环法22执行策略执行策略1：Sname(Student.Sno=SC.Sno SC.Cno=2(StudentSC)9.2.2 9.2.2 一个实例一个实例执行策略执行策略2：Sname(SC.Cno=2(StudentSC)执行策略执行策略3：Sname(StudentSC.Cno=2(SC)执行策略执行策略4：Sname(StudentSC.Cno=2(SC)假设假设SCSC表在表在CnoCno上有索引，上有索引，StudentStudent表在表在SnoSno上有索引。上有索引。231.执行策略执行策略1Sn

15、ame(Student.Sno=SC.Sno SC.Cno=2(StudentSC)9.2.2 9.2.2 一个实例一个实例StudentSC读取总块数读取总块数=读读Student表块数表块数+读读SC表遍数表遍数*每遍块数每遍块数=1000/10+(1000/(105)(10000/100)=100+20100=2100块块读数据时间读数据时间=2100/20=105秒秒中间结果大小中间结果大小=1000*10000=107(1千万条元组千万条元组)写中间结果时间写中间结果时间=10000000/10/20=50000秒秒241.执行策略执行策略1name(Student.Sno=SC.S

16、no SC.Cno=2(StudentSC)9.2.2 9.2.2 一个实例一个实例：忽略内存处理时间忽略内存处理时间读数据时间读数据时间=50000秒秒：投影时间可以忽略投影时间可以忽略总时间总时间总时间总时间=1055000050000秒秒=100105秒秒=27.8小时小时252.执行策略执行策略2name(SC.Cno=2(StudentSC)9.2.2 9.2.2 一个实例一个实例：读取总块数：读取总块数=2100块块读数据时间读数据时间=2100/20=105秒秒中间结果大小中间结果大小=10000（减少（减少1000倍）倍）写中间结果时间写中间结果时间=10000/10/20=5

17、0秒秒：忽略内存处理时间忽略内存处理时间读数据时间读数据时间=50秒秒：时间可以忽略时间可以忽略总时间总时间总时间总时间1055050秒秒205秒秒=3.4分分263.执行策略执行策略3Sname(StudentSC.Cno=2(SC)：读读SC表总块数表总块数=10000/100=100块块读读SC表表数据时间数据时间=100/20=5秒秒中间结果大小中间结果大小=50条条不必写入外存不必写入外存：读读Student表总块数表总块数=1000/10=100块块读读Student表表数据时间数据时间=100/20=5秒秒：总时间总时间55秒秒10秒秒9.2.2 9.2.2 一个实例一个实例27

18、4.执行策略执行策略4Sname(StudentSC.Cno=2(SC)，假设假设SC表表Cno上有索引，上有索引，Student表表Sno上有索引。上有索引。：读读SC表索引表索引：读读SC表总块数表总块数=50/1001块块读数据时间：读数据时间：中间结果大小中间结果大小=50条条不必写入外存不必写入外存：读读Student表索引：读表索引：读Student表总块数表总块数=50/10=5块块读数据时间读数据时间=5/20秒。秒。：总时间总时间=连接运算连接运算例：例：Student.Sno=SC.Sno(StudentSC)StudentSC6.6.提取公共子表达式提取公共子表达式视图视

19、图前提：公共子表达式的关系不是很大前提：公共子表达式的关系不是很大从外存读入比计算该表达式省时间从外存读入比计算该表达式省时间399.3.2 9.3.2 查询树的启发式优化查询树的启发式优化算法：算法：关系表达式的优化关系表达式的优化输入：一个关系表达式的查询树。输入：一个关系表达式的查询树。输出：优化的查询树。输出：优化的查询树。方法：方法：(1)(1)分解选择分解选择运算运算利用规则利用规则4 4把形如把形如F1 F2 F1 F2 Fn Fn(E)(E)变换为变换为 F1F1(F2F2(FnFn(E)(E)(2)(2)通过通过交换选择交换选择运算运算，将其尽可能移到，将其尽可能移到叶端叶端

20、对每个选择，利用规则对每个选择，利用规则4 48 8尽可能把它移到叶端尽可能把它移到叶端。40(3)(3)通过交换通过交换投影运算投影运算，将其尽可能移到，将其尽可能移到叶端叶端对对每每一一个个投投影影利利用用规规则则3 3，9 9，l0l0，5 5中中的的一一般般形形式尽可能把它移向树的叶端。式尽可能把它移向树的叶端。(4)(4)合合并并串串接接的的选选择择和和投投影影，以以便便能能同同时时执执行行或或在在一一次扫描中完成。次扫描中完成。利利用用规规则则3 35 5把把选选择择和和投投影影的的串串接接合合并并成成单单个个选选择、单个投影或一个选择后跟一个投影。择、单个投影或一个选择后跟一个投

21、影。使使多多个个选选择择或或投投影影能能同同时时执执行行，或或在在一一次次扫扫描描中中全部完成全部完成9.3.2 9.3.2 查询树的启发式优化查询树的启发式优化41(5)(5)(5)(5)对内结点分组对内结点分组对内结点分组对内结点分组每一双目运算每一双目运算(，-)-)和它所有的直接祖先为和它所有的直接祖先为一组一组(这些直接祖先是这些直接祖先是，运算运算)。如果其后代直到叶子全是单目运算，则也将它们并入如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积该组，但当双目运算是笛卡尔积()()，而且其后的选，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算择不

22、能与它结合为等值连接时除外。把这些单目运算单独分为一组。单独分为一组。(6)(6)(6)(6)生成程序生成程序生成程序生成程序生成一个程序，每组结点的计算是程序中的一步。生成一个程序，每组结点的计算是程序中的一步。各各步步的的顺顺序序是是任任意意的的，只只要要保保证证任任何何一一组组的的计计算算不不会会在它的后代组之前计算。在它的后代组之前计算。9.3.2 9.3.2 查询树的启发式优化查询树的启发式优化42优化的一般步骤：优化的一般步骤：优化的一般步骤：优化的一般步骤：1把查询转换成某种内部表示把查询转换成某种内部表示2代数优化：代数优化：把语法树转换成标准（优化）把语法树转换成标准（优化）

23、形式形式3物理优化：物理优化：选择低层的存取路径选择低层的存取路径4生成查询计划，选择代价最小的生成查询计划，选择代价最小的9.3.2 9.3.2 查询树的启发式优化查询树的启发式优化43例例4 4：对：对“查询选修课程查询选修课程C2C2的学生姓名的学生姓名”SQLSQL语句的代数优语句的代数优化化SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnANDSC.Cno=2;(1)(1)(1)(1)把查询转换成某种内部表示把查询转换成某种内部表示把查询转换成某种内部表示把查询转换成某种内部表示9.3.2 9.3.2 查询树的启发式优化查询树的启发式优化

24、44结果结果 project(Sname)select(SC.Cno=2)join(Student.Sno=SC.Sno)StudentSCSname SC.Cno=2 Student.Sno=SC.Sno StudentSC图图9.3查询树查询树图图9.4关系代数语法树关系代数语法树9.3.2 9.3.2 查询树的启发式优化查询树的启发式优化(1)(1)(1)(1)把查询转换成某种内部表示把查询转换成某种内部表示把查询转换成某种内部表示把查询转换成某种内部表示45(2)(2)(2)(2)代数优化代数优化代数优化代数优化n利用优化算法把语法树转换成标准（优化）形式利用优化算法把语法树转换成标准

25、（优化）形式Sname Student.Sno=SC.Sno SC.Cno=2 StudentSCSname SC.Cno=2 Student.Sno=SC.Sno StudentSC9.3.2 9.3.2 查询树的启发式优化查询树的启发式优化46例如：例如：例如：例如：9.3.2 9.3.2 查询树的启发式优化查询树的启发式优化 对学生对学生-课程数据库有如下查询，查询信息系学课程数据库有如下查询，查询信息系学生选修的所有课程名称生选修的所有课程名称:SELECTCnameFROMStudent,Course,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=Course

26、.CnoANDStudent.Sdept=IS 试画出试画出:(1):(1)用关系代数表示的语法树用关系代数表示的语法树;(2)(2)并用关系代数表达式优化算法并用关系代数表达式优化算法,画出画出 优化后的标准语法树。优化后的标准语法树。47 CoursescCno=Course.CnoSt.sdept=ISst.sno=sc.Snocname答：关系代数表达式如下：答：关系代数表达式如下：cnamecname(St.sdept=ISSt.sdept=IS(st.sno=sc.Sno st.sno=sc.Sno(sc.Cno=Course.Cnosc.Cno=Course.Cno (StSCCourse)StSCCourse)结果结果 CourseSt ScscCno=Course.CnoSt.sdept=ISScst.sno=sc.Snocname结果结果Stcno,cnamecno,snosno48小结小结关系系统查询优化的步骤关系系统查询优化的步骤关系代数等价变换规则关系代数等价变换规则关系系统查询优化的一般准则关系系统查询优化的一般准则此此课件下件下载可自行可自行编辑修改，修改，仅供参考！供参考！感感谢您的支持，我您的支持，我们努力做得更好！努力做得更好！谢谢!