关系查询处理和其查询优化课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《关系查询处理和其查询优化课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关系 查询 处理 优化 课件
- 资源描述:
-
1、第九章第九章 关系查询处理和其查询优化关系查询处理和其查询优化9.1 关系数据库系统的查询处理关系数据库系统的查询处理9.2 关系数据库系统的查询优化关系数据库系统的查询优化9.3 代数优化代数优化9.4 物理优化物理优化9.1关系数据库系统的查询处理关系数据库系统的查询处理l9.1.1 查询处理步骤查询处理步骤 分分4个阶段:查询分析,查询检个阶段:查询分析,查询检查,查询优化,查询执行查,查询优化,查询执行l1 查询分析查询分析 对查询语句进行扫描、词法分析和语法对查询语句进行扫描、词法分析和语法分析。分析。l2 查询检查查询检查 根据数据字典对合法的查询语句进行语根据数据字典对合法的查询
2、语句进行语义检查,即检查语句中的数据库对象,义检查,即检查语句中的数据库对象,如属性名、关系名,是否存在和是否有如属性名、关系名,是否存在和是否有效。权限和完整性检查,转换为查询树效。权限和完整性检查,转换为查询树l3 查询优化查询优化 在许多的执行策略中选择一个高效在许多的执行策略中选择一个高效的查询处理策略。分为代数优化和的查询处理策略。分为代数优化和物力优化。物力优化。l4 查询执行查询执行 生成查询计划,由代码生成器生成生成查询计划,由代码生成器生成执行查询的代码。执行查询的代码。查询语句词法分析语法分析语义分析符号名转换安全性检查完整性检查查询树代数优化物理优化等执行策略描述代码生成
3、查询计划的执行代码查询分析查询检查查询优化查询执行9.1.2实现查询操作的算法示例实现查询操作的算法示例一、选择操作的实现一、选择操作的实现例例 select *from student where;条件为:条件为:C1:无条件:无条件 C2:sno=200215121 C3:sage20 C4:sdept=CS AND sage20;l1.简单的全表扫描简单的全表扫描 对小表简单有效,对大表费时,效率低对小表简单有效,对大表费时,效率低snoSnameSsexSagesdept20021513220021512220021512120021525.l2.索引扫描方法索引扫描方法 如果选择条件
4、中的属性上有索引,用索如果选择条件中的属性上有索引,用索引扫描法。通过索引先找到满足条件的引扫描法。通过索引先找到满足条件的元组主码或指针,再通过指针找基表中元组主码或指针,再通过指针找基表中的数据的数据snoSnameSsexSagesdept20021513220021512220021512120021525.索引索引地址地址200215121200215122200215125200215132l二、连接操作的实现二、连接操作的实现 连接操作是最费时的操作连接操作是最费时的操作 例:例:select*from student,scwhere student.sno=sc.sno1.嵌套
5、循环方法嵌套循环方法Snosname5837snocno7578382.排序排序-合并方法合并方法适合于连接的诸表已经排序的情况适合于连接的诸表已经排序的情况步骤:步骤:1)先对待连接的表在连接属性上排序)先对待连接的表在连接属性上排序2)取左表的第一个元组,一次扫描右表,找连)取左表的第一个元组,一次扫描右表,找连接属性相等的元组,把他们连接起来接属性相等的元组,把他们连接起来3)当在右表中找到第一个与左表提供的值不相)当在右表中找到第一个与左表提供的值不相等时,返回左表取下一个元组再往下扫描右表。等时,返回左表取下一个元组再往下扫描右表。重复这一过程,直到左表扫描完毕。重复这一过程,直到左
6、表扫描完毕。Snosname5837snocno757838sno357788sno35783.索引连接方法索引连接方法步骤:步骤:1)在)在sc表上建立属性表上建立属性sno的索引的索引2)对)对student中的每一个中的每一个sno,通过通过sc的索引的索引找相应的找相应的sc元组元组3)把这些元组与)把这些元组与student中的当前元组连中的当前元组连接起来接起来4)重复)重复2)3)直到)直到student表处理完毕表处理完毕9.2 关系系统的查询优化关系系统的查询优化 9.2.1 查询优化概述查询优化概述9.2.1 查询优化概述查询优化概述l查询优化的必要性查询优化的必要性 查询
7、优化极大地影响查询优化极大地影响RDBMS的性能。的性能。l查询优化的可能性查询优化的可能性 关系数据语言的关系数据语言的级别很高级别很高,使,使DBMS可以从关系表达式中分析查询可以从关系表达式中分析查询语义语义。由由DBMS进行查询优化的好处进行查询优化的好处l用户不必考虑如何最好地表达查询以获用户不必考虑如何最好地表达查询以获得较好的效率得较好的效率l系统可以比用户程序的系统可以比用户程序的优化优化做得更好做得更好(1)优化器可以从数据字典中获取许多统计信息,优化器可以从数据字典中获取许多统计信息,而用户程序则难以获得这些信息而用户程序则难以获得这些信息 由由DBMS进行查询优化的好处进
8、行查询优化的好处(2)如果数据库的物理统计信息改变了,系统可以自动如果数据库的物理统计信息改变了,系统可以自动对查询对查询重新优化重新优化以选择相适应的执行计划。以选择相适应的执行计划。在非关系系统中必须重写程序,而重写程序在实际在非关系系统中必须重写程序,而重写程序在实际应用中往往是不太可能的。应用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行计划,而程序员优化器可以考虑数百种不同的执行计划,而程序员一般只能考虑有限的几种可能性一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术优化器中包括了很多复杂的优化技术查询优化目标查询优化目标l查询优化的总目标查询优化的总目
9、标 选择有效策略,求得给定关系表达式的值选择有效策略,求得给定关系表达式的值l实际系统的查询优化步骤实际系统的查询优化步骤1.将查询转换成某种内部表示,通常是语法树将查询转换成某种内部表示,通常是语法树2.根据一定的等价变换规则把语法树转换成标准根据一定的等价变换规则把语法树转换成标准(优化)形式(优化)形式实际系统的查询优化步骤实际系统的查询优化步骤3.选择低层的操作算法选择低层的操作算法对于语法树中的每一个操作对于语法树中的每一个操作 计算各种执行算法的执行代价计算各种执行算法的执行代价 选择代价小的执行算法选择代价小的执行算法4.生成查询计划生成查询计划(查询执行方案查询执行方案)查询计
10、划是由一系列内部操作组成的。查询计划是由一系列内部操作组成的。代价模型代价模型l集中式数据库集中式数据库 单用户系统单用户系统总代价总代价=I/O代价代价+CPU代价代价 多用户系统多用户系统总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价l分布式数据库分布式数据库 总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价+通信代价通信代价 9.2.2 一个实例一个实例 例:求选修了课程例:求选修了课程2的学生姓名的学生姓名 SELECT Student.SnameFROM Student,SCWHERE Student.Sno=SC.SnoAND SC.Cno=2;假设假
11、设1:外存:外存:Student:1000条条,SC:10000条条,选修选修2号课程号课程:50条条假设假设2:一个内存块装元组:一个内存块装元组:10个个Student,或或100个个SC,内存中一次可以存放内存中一次可以存放:5块块Student元组元组,1块块SC元组和若干块连接结果元组元组和若干块连接结果元组假设假设3:读写速度:读写速度:20块块/秒秒假设假设4:连接方法:连接方法:基于数据块基于数据块的嵌套循环法的嵌套循环法 3种执行策略种执行策略 Q1Sname(Student.Sno=SC.SnoSC.Cno=2(StudentSC)2 name(SC.Cno=2(Stude
12、nt SC)3 Sname(Student SC.Cno=2(SC)执行策略执行策略1Q1Sname(Student.Sno=SC.SnoSC.Cno=2(StudentSC)StudentSC 读取总块数读取总块数=读读Student表块数表块数+读读SC表遍数表遍数*每遍块数每遍块数=1000/10+(1000/(105)(10000/100)=100+20100=2100 读数据时间读数据时间=2100/20=105秒秒不同的执行策略不同的执行策略,考虑考虑I/O时间时间中间结果大小中间结果大小=1000*10000=107 (1千万条千万条元组元组)写中间结果时间写中间结果时间=100
13、00000/10/20=50000秒秒 读数据时间读数据时间=50000秒秒 总时间总时间=1055000050000秒秒=100105秒秒 =27.8小时小时2.2 name(SC.Cno=2(Student SC)读取总块数读取总块数=2100块块读数据时间读数据时间=2100/20=105秒秒中间结果大小中间结果大小=10000 (减少(减少1000倍)倍)写中间结果时间写中间结果时间=10000/10/20=50秒秒 读数据时间读数据时间=50秒秒 总时间总时间1055050秒秒205秒秒=3.4分分 3.3 Sname(Student SC.Cno=2(SC)读读SC表总块数表总块数
展开阅读全文