关系查询处理和查询优化复习过程.ppt
《关系查询处理和查询优化复习过程.ppt》由会员分享,可在线阅读,更多相关《关系查询处理和查询优化复习过程.ppt(68页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、关系查询处理和查询优化关系查询处理和查询优化内容要求n掌握关系系统查询优化的相关概念掌握关系系统查询优化的相关概念n了解查询优化的一般准则及步骤了解查询优化的一般准则及步骤n能够运用关系代数表达式的优化算法画能够运用关系代数表达式的优化算法画出查询语法树以及优化后的语法树出查询语法树以及优化后的语法树本讲内容一、关系数据库系统的查询处理一、关系数据库系统的查询处理二、关系数据库系统的查询优化二、关系数据库系统的查询优化三、代数优化三、代数优化四、物理优化四、物理优化一、关系数据库系统的查询处理n什么是查询处理?什么是查询处理?从数据库中检索数据的活动。从数据库中检索数据的活动。n查询处理的任务
2、查询处理的任务把用户提交给把用户提交给RDBMSRDBMS的查询语句转换为高效的执的查询语句转换为高效的执行计划。行计划。n查询处理的目标查询处理的目标将高级语言(例如将高级语言(例如SQLSQL)表示的查询转换为正确)表示的查询转换为正确有效的、用低级语言表达的有效的、用低级语言表达的执行策略执行策略,即实现关,即实现关系代数,并通过执行该策略来获取所需的数据。系代数,并通过执行该策略来获取所需的数据。一、关系数据库系统的查询处理1.1.查询处理步骤查询处理步骤2.2.实现查询操作的算法示例实现查询操作的算法示例 1.查询处理步骤nRDBMSRDBMS查询处理过程查询处理过程 :(1 1)查
3、询分析查询分析(2 2)查询检查查询检查(3 3)查询优化查询优化 (4 4)查询执行查询执行 查询处理步骤(续)查询处理步骤(1)查询分析n对查询语句进行扫描、词法分析和语法对查询语句进行扫描、词法分析和语法分析分析 n从查询语句中识别出语言符号从查询语句中识别出语言符号 n进行语法检查和语法分析进行语法检查和语法分析 (2)查询检查 n根据数据字典对合法的查询语句进行语义检查根据数据字典对合法的查询语句进行语义检查 n根据数据字典中的用户权限和完整性约束定义对根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查用户的存取权限进行检查 n检查通过后把检查通过后把SQLSQL查询语
4、句转换成等价的关系代数查询语句转换成等价的关系代数表达式表达式 nRDBMSRDBMS一般都用查询树一般都用查询树(语法分析树语法分析树)来表示扩展的来表示扩展的关系代数表达式关系代数表达式 n把数据库对象的外部名称转换为内部表示把数据库对象的外部名称转换为内部表示 (3)查询优化n查询优化:选择一个高效执行的查询处理策略查询优化:选择一个高效执行的查询处理策略 n查询优化分类查询优化分类 :n代数优化:指关系代数表达式的优化代数优化:指关系代数表达式的优化n物理优化:指存取路径和底层操作算法的选择物理优化:指存取路径和底层操作算法的选择n查询优化方法选择的依据:查询优化方法选择的依据:n基于
5、规则基于规则(rule based)(rule based)n基于代价基于代价(cost based)(cost based)n基于语义基于语义(semantic based)(semantic based)(4)查询执行 n依据优化器得到的执行策略生成查询计依据优化器得到的执行策略生成查询计划划n代码生成器代码生成器(code generator)(code generator)生成执行生成执行查询计划的代码查询计划的代码 示例例:用户例:用户U1U1针对学生课程数据库,完成如针对学生课程数据库,完成如下查询:下查询:select student.sno,cno,Gradeselect st
6、udent.sno,cno,Gradefrom student,scfrom student,scwhere student.sno=sc.sno and where student.sno=sc.sno and sdept=CSsdept=CS与之等价的关系代数表达式?优化后的关系代数与之等价的关系代数表达式?优化后的关系代数表达式?表达式?2.实现查询操作的算法示例(1 1)选择操作的实现)选择操作的实现 (2 2)连接操作的实现)连接操作的实现 示例1 选择操作的实现 例例Select*from student where Select*from student where ;考虑考虑
7、的几种情况:的几种情况:C1 C1:无条件;:无条件;C2 C2:SnoSno200215121200215121;C3 C3:Sage20Sage20;C4 C4:SdeptSdeptCS AND Sage20CS AND Sage20;选择操作的实现(续)1 1)简单的全表扫描方法)简单的全表扫描方法 对查询的基本表顺序扫描,逐一检查每个元组是否对查询的基本表顺序扫描,逐一检查每个元组是否满足选择条件,把满足条件的元组作为结果输出满足选择条件,把满足条件的元组作为结果输出 适合小表,不适合大表适合小表,不适合大表2 2)索引)索引(或散列或散列)扫描方法扫描方法 适合选择条件中的属性上有索
8、引适合选择条件中的属性上有索引(例如例如B+B+树索引或树索引或HashHash索引索引)通过索引先找到满足条件的元组主码或元组指针,通过索引先找到满足条件的元组主码或元组指针,再通过元组指针直接在查询的基本表中找到元组再通过元组指针直接在查询的基本表中找到元组 选择操作的实现(续)例例1-C21-C2 以以C2C2为例,为例,SnoSno200215121200215121,并且,并且SnoSno上上有索引有索引(或或SnoSno是散列码是散列码)n使用索引使用索引(或散列或散列)得到得到SnoSno为为200215121 200215121 元组的指元组的指针针n通过元组指针在通过元组指针
9、在studentstudent表中检索到该学生表中检索到该学生例例1-C31-C3 以以C3C3为例,为例,Sage20Sage20,并且,并且Sage Sage 上有上有B+B+树树索引索引n使用使用B+B+树索引找到树索引找到SageSage2020的索引项,以此为入口点的索引项,以此为入口点在在B+B+树的顺序集上得到树的顺序集上得到Sage20Sage20的所有元组指针的所有元组指针n通过这些元组指针到通过这些元组指针到studentstudent表中检索到所有年龄大于表中检索到所有年龄大于2020的学生。的学生。选择操作的实现(续)例例1-C41-C4 以以C4C4为例,为例,Sde
10、ptSdeptCS AND Sage20CS AND Sage20,如如果果SdeptSdept和和SageSage上都有索引:上都有索引:算法一:分别用上面两种方法分别找到算法一:分别用上面两种方法分别找到SdeptSdeptCSCS的的一一组元组指针和组元组指针和Sage20Sage20的另一组元组指针的另一组元组指针求这求这2 2组指针的交集组指针的交集到到studentstudent表中检索表中检索得到计算机系年龄大于得到计算机系年龄大于2020的学生的学生算法二:找到算法二:找到SdeptSdeptCSCS的一组元组指针,的一组元组指针,通过这些元组指针到通过这些元组指针到stude
11、ntstudent表中检索表中检索对得到的元组检查另一些选择条件对得到的元组检查另一些选择条件(如如Sage20)Sage20)是是否满足否满足把满足条件的元组作为结果输出。把满足条件的元组作为结果输出。(2)连接操作的实现 n连接操作是查询处理中最耗时的操作之一连接操作是查询处理中最耗时的操作之一 n本节只讨论等值连接本节只讨论等值连接(或自然连接或自然连接)最常用的实最常用的实现算法现算法 例例2 2 SELECT*SELECT*FROM Student FROM Student,SC SC WHERE Student.Sno=SC.Sno WHERE Student.Sno=SC.Sno
12、;连接操作的实现(续)1 1)嵌套循环方法嵌套循环方法(nested loop)(nested loop)2 2)排序排序-合并方法合并方法(sort-merge join(sort-merge join 或或merge merge join)join)3 3)索引连接索引连接(index join)(index join)方法方法 4 4)Hash Join Hash Join方法方法 1)嵌套循环方法)嵌套循环方法(nested loop)n对外层循环对外层循环(Student)(Student)的每一个元组的每一个元组(s)(s),检索内层循环检索内层循环(SC)(SC)中的每一个元组中
13、的每一个元组(sc)(sc)n检查这两个元组在连接属性检查这两个元组在连接属性(sno)(sno)上是否相上是否相等等n如果满足连接条件,则串接后作为结果输如果满足连接条件,则串接后作为结果输出,直到外层循环表中的元组处理完为止出,直到外层循环表中的元组处理完为止 SnoSnameSsexSageSdept200215121李勇李勇男男20CS200215122刘晨刘晨女女19IS200215123王敏王敏女女18MA200215125张立张立男男19IS学学 号号课课 程程 号号成成 绩绩SnoCnoGrade20021512119220021512128520021512138820021
14、51222902002151223802)排序)排序-合并方法合并方法n适合连接的诸表已经排好序的情况适合连接的诸表已经排好序的情况 n排序合并连接方法的步骤:排序合并连接方法的步骤:如果连接的表没有排好序,先对如果连接的表没有排好序,先对StudentStudent表和表和SCSC表按表按连接属性连接属性SnoSno排序排序 取取StudentStudent表中第一个表中第一个SnoSno,依次扫描,依次扫描SCSC表中具有相同表中具有相同SnoSno的元组的元组 2)排序)排序-合并方法合并方法(续)200215121200215122200215123200215124.20021512
15、1 1 92200215121 2 85200215121 3 88200215122 2 90200215122 3 80.排序-合并连接方法示意图2)排序)排序-合并方法合并方法(续)n排序合并连接方法的步骤(续):排序合并连接方法的步骤(续):当扫描到当扫描到SnoSno不相同的第一个不相同的第一个SCSC元组时,返回元组时,返回StudentStudent表扫描它的下一个元组,再扫描表扫描它的下一个元组,再扫描SCSC表中表中具有相同具有相同SnoSno的元组,把它们连接起来的元组,把它们连接起来 重复上述步骤直到重复上述步骤直到Student Student 表扫描完表扫描完3)索引
16、连接索引连接(index join)方法方法n步骤:步骤:在在SCSC表上建立属性表上建立属性SnoSno的索引,如果原来没的索引,如果原来没有该索引。有该索引。对对StudentStudent中每一个元组,由中每一个元组,由SnoSno值通过值通过SCSC的索引查找相应的的索引查找相应的SCSC元组。元组。把这些把这些SCSC元组和元组和StudentStudent元组连接起来元组连接起来 循环执行循环执行,直到,直到StudentStudent表中的元组处理表中的元组处理完为止。完为止。4)Hash Join方法方法n把连接属性作为把连接属性作为hashhash码,用同一个码,用同一个ha
17、shhash函数把函数把R R和和S S中的元组散列到同一个中的元组散列到同一个hashhash文件中。文件中。n第一步,划分阶段。第一步,划分阶段。对包含较少元组的表(如对包含较少元组的表(如R R表)进行一遍处理,把它表)进行一遍处理,把它的元组按的元组按hashhash函数分散到函数分散到hashhash表的桶中。表的桶中。n第二步,试探阶段,也称连接阶段。第二步,试探阶段,也称连接阶段。对另一个表(对另一个表(S S)进行一遍处理,把)进行一遍处理,把S S的元组散列到适的元组散列到适当的当的hashhash桶中,并把元组与桶中所有来自桶中,并把元组与桶中所有来自R R并与之相匹并与之
18、相匹配的元组连接起来。配的元组连接起来。二、关系数据库系统的查询优化n为什么提出来查询优化?为什么提出来查询优化?这是由关系数据库系统的特点决定的,系统应该考虑这是由关系数据库系统的特点决定的,系统应该考虑采用什么样的查询才能做到执行起来既省时间,又省采用什么样的查询才能做到执行起来既省时间,又省空间,而且效率也比较高。空间,而且效率也比较高。n什么是查询优化?什么是查询优化?选择有效的执行策略执行查询的活动。选择有效的执行策略执行查询的活动。n查询优化的目标查询优化的目标对于同一个高级查询有许多等价变换,对于同一个高级查询有许多等价变换,RDBMSRDBMS选择占选择占用资源最小的一种。这就
19、是查询优化的目标。用资源最小的一种。这就是查询优化的目标。二、关系数据库系统的查询优化1.1.查询优化的重要性查询优化的重要性2.2.查询优化的可能性查询优化的可能性3.3.查询优化的必要性查询优化的必要性1.查询优化的重要性n关系系统的关系系统的查询优化即是查询优化即是RDBMSRDBMS实现的关键技实现的关键技术又是关系系统的优点所在。术又是关系系统的优点所在。它减轻了用户选它减轻了用户选择存取路径的负担。用户只要提出择存取路径的负担。用户只要提出“干什么干什么”,不必指出,不必指出“怎么干怎么干”。n查询优化的优点不仅在于用户不必考虑如何最查询优化的优点不仅在于用户不必考虑如何最好地表达
20、查询以获得较好的效率,而且在于系好地表达查询以获得较好的效率,而且在于系统可以比用户程序的统可以比用户程序的“优化优化”做得更好。做得更好。n思考:查询优化由谁来完成?思考:查询优化由谁来完成?2.查询优化的可能性(1)(1)优化器可以从数据字典中获取许多统计信息,优化器可以从数据字典中获取许多统计信息,而用户程序则难以获得这些信息而用户程序则难以获得这些信息(2)(2)如果数据库的物理统计信息改变了,系统可以自如果数据库的物理统计信息改变了,系统可以自动对查询重新优化以选择相适应的执行计划。在非动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序,而重写程序在实际应用关系系统中
21、必须重写程序,而重写程序在实际应用中往往是不太可能的。中往往是不太可能的。2.查询优化的可能性(3)(3)优化器可以考虑数百种不同的执行计划,程序优化器可以考虑数百种不同的执行计划,程序员一般只能考虑有限的几种可能性。员一般只能考虑有限的几种可能性。(4)(4)优化器中包括了很多复杂的优化技术,这些优优化器中包括了很多复杂的优化技术,这些优化技术往往只有最好的程序员才能掌握。系统化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化的自动优化相当于使得所有人都拥有这些优化技术。技术。查询时间开销nRDBMSRDBMS通通过过某某种种代代价价模模型型计计算算出出各各种种
22、查查询询执执行行策策略略的的执执行代价,然后选取代价最小的执行方案行代价,然后选取代价最小的执行方案n集中式数据库集中式数据库执行开销主要包括:执行开销主要包括:n磁盘存取块数磁盘存取块数(I/O(I/O代价代价)n处理机时间处理机时间(CPU(CPU代价代价)n查询的内存开销查询的内存开销 I/OI/O代价是最主要的代价是最主要的 n分布式数据库分布式数据库总代价总代价=I/O=I/O代价代价+CPU+CPU代价代价+内存代价内存代价通信代价通信代价 查询优化的总目标n选择有效的策略选择有效的策略n求得给定关系表达式的值求得给定关系表达式的值n使得查询代价最小使得查询代价最小(实际上是较小实
23、际上是较小)示例查询优化的必要性 例例3 3 求选修了求选修了2 2号课程的学生姓名。用号课程的学生姓名。用SQLSQL表达:表达:SELECT Student.SnameSELECT Student.Sname FROM Student FROM Student,SCSC WHERE Student.Sno=SC.Sno AND WHERE Student.Sno=SC.Sno AND SC.Cno=2 SC.Cno=2;n假定学生假定学生-课程数据库中有课程数据库中有10001000个学生记录,个学生记录,1000010000个选课记录个选课记录n其中选修其中选修2 2号课程的选课记录为号
24、课程的选课记录为5050个个 查询优化的必要性(续)n系统可以用多种等价的关系代数表达式系统可以用多种等价的关系代数表达式来完成这一查询来完成这一查询Q Q1 1=SnameSname(Student.Sno=SC.SnoSc.Cno=2Student.Sno=SC.SnoSc.Cno=2 (StudentSC)(StudentSC)Q Q2 2=SnameSname(Sc.Cno=2Sc.Cno=2(Student SC)(Student SC)Q Q3 3=SnameSname(Student (Student Sc.Cno=2Sc.Cno=2(SC)(SC)查询优化的必要性(续)(1 1
25、)第一种情况)第一种情况 Q Q1 1=SnameSname(Student.Sno=SC.SnoSc.Cno=2Student.Sno=SC.SnoSc.Cno=2(StudentSC)(StudentSC)1)1)计算广义笛卡尔积计算广义笛卡尔积 n把把StudentStudent和和SCSC的每个元组连接起来的做法:的每个元组连接起来的做法:n在内存中尽可能多地装入某个表在内存中尽可能多地装入某个表(如如StudentStudent表表)的若干块,留出一的若干块,留出一块存放另一个表块存放另一个表(如如SCSC表表)的元组。的元组。n把把SCSC中的每个元组和中的每个元组和Student
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关系 查询 处理 优化 复习 过程
限制150内