第9章数据库查询优化课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第9章数据库查询优化课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据库 查询 优化 课件
- 资源描述:
-
1、第第9章章 数据库查询优化数据库查询优化9.1 关系数据库系统的查询处理关系数据库系统的查询处理9.2 关系数据库系统的查询优化关系数据库系统的查询优化9.3 基于半联接的查询优化基于半联接的查询优化9.4 基于枚举法的查询优化基于枚举法的查询优化9.1 关系数据库系统的查询处理9.2 关系数据库系统的查询优化 查询优化的必要性查询优化的必要性查询优化极大地影响查询优化极大地影响RDBMS的性能。的性能。查询优化的可能性查询优化的可能性关系数据语言的关系数据语言的级别很高级别很高,使,使DBMS可以从关系表达式中分析查询可以从关系表达式中分析查询语义语义。9.2 关系数据库系统的查询优化 用户
2、不必考虑如何最好地表达查询以获用户不必考虑如何最好地表达查询以获得较好的效率得较好的效率 系统可以比用户程序的系统可以比用户程序的优化优化做得更好做得更好(1)优化器可以从数据字典中获取许多统计信息,优化器可以从数据字典中获取许多统计信息,而用户程序则难以获得这些信息而用户程序则难以获得这些信息 9.2 关系数据库系统的查询优化(2)如果数据库的物理统计信息改变了,系统可以自如果数据库的物理统计信息改变了,系统可以自动对查询动对查询重新优化重新优化以选择相适应的执行计划。以选择相适应的执行计划。在非关系系统中必须重写程序,而重写程序在实际在非关系系统中必须重写程序,而重写程序在实际应用中往往是
3、不太可能的。应用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行计划,而程序优化器可以考虑数百种不同的执行计划,而程序员一般只能考虑有限的几种可能性员一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术优化器中包括了很多复杂的优化技术9.2 关系数据库系统的查询优化查询优化的总目标查询优化的总目标选择有效策略,求得给定关系表达式的值选择有效策略,求得给定关系表达式的值实际系统的查询优化步骤实际系统的查询优化步骤1.将查询转换成某种内部表示,通常是语法树将查询转换成某种内部表示,通常是语法树2.根据一定的等价变换规则把语法树转换成标准根据一定的等价变换规则把语法树转换成标
4、准(优化)形式(优化)形式例例:有查询有查询Q1:查询北部地区(:查询北部地区(AREA=North)所属部门发出订单的供应商号。)所属部门发出订单的供应商号。这 里 涉 及 两 个 全 局 关 系这 里 涉 及 两 个 全 局 关 系 D e p t(D#,D N A M E,M G T R S S N,A R E A)和和Sp(S#,P#,D#,QUAN),SQL表达式为:表达式为:Select S From Dept,Sp Where SpD=Dept.D And AREA=NorthNorth;其相应的代数表达式为:其相应的代数表达式为:S#AREA=North(Sp Sp DeptD
5、ept)D=D 其相应的查询树如下:其相应的查询树如下:s#s#AREA=Nouth D=D Sp Dept查询树显然,边为显然,边为 E1(,Sp)D=D时,则时,则Sp是非叶节点是非叶节点 的分量。的分量。查询表达式的等价性 例例:对关系对关系 Emp,有如下有如下SQL查询表达式查询表达式 Select ENAME,DNO From Emp Where DNO=15;(4-14-1)其相应的代数操作表达式为:其相应的代数操作表达式为:ENAMEENAME,DNODNO(DNODNO=1515 EmpEmp)(4-24-2)或或 DNODNO=1515(ENAMEENAME,DNO DNO
6、 EmpEmp)(4-34-3)本例本例表示了不同的操作顺序仍可获得相同的结果。这就是等价的概念。表示了不同的操作顺序仍可获得相同的结果。这就是等价的概念。两个查询表达式两个查询表达式 E1 和和 E2 是等价的,如果其是等价的,如果其 查询的结果是相同的,记为查询的结果是相同的,记为 E1 E2。9.2 关系数据库系统的查询优化3.选择低层的操作算法选择低层的操作算法对于语法树中的每一个操作对于语法树中的每一个操作 计算各种执行算法的执行代价计算各种执行算法的执行代价 选择代价小的执行算法选择代价小的执行算法4.生成查询计划生成查询计划(查询执行方案查询执行方案)查询计划是由一系列内部操作组
7、查询计划是由一系列内部操作组成的成的查询树可以理解为全局查查询树可以理解为全局查询树询树根据等价定义,可用三种根据等价定义,可用三种方式描述查询:方式描述查询:SQL表达式(查询语句)表达式(查询语句)代数表达式代数表达式 查询树查询树代价模型 集中式数据库集中式数据库 单用户系统单用户系统总代价总代价=I/O代价代价+CPU代价代价 多用户系统多用户系统总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价 分布式数据库分布式数据库 总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价+通信代价通信代价 9.3 基于半联接的查询优化4.5.1 联接操作重要性4.5.2 联接
8、操作4.5.3 半联接操作原理和不对称性4.5.4 半联接操作的缩减作用4.5.5 半联接程序的作用4.5.6 半联接程序的具体过程4.5.7 半联接技术的不足9.3.1 联接操作重要性n关系数据库由许多关系组成,关系与关系之间的联系主要通过联接操作表现出来,因而在二元操作中,联接操作远比其它操作用得多。n讨论联接,其实包括了“选择投影联接”的综合问题,即二元操作和一元操作的综合优化问题。n分布式查询处理的联接操作,更是影响分布式查询效率的最关键因素。n在DDB中,联接操作的大量数据会引起场地间的传输,它直接影响整个系统性能。n当前对联接操作的优化有两种趋向:一种是采用半联接技术来减少联接操作
9、的操作数,以降低通讯费用;另一种是直接进行联接操作的代价计算9.3.2 联接操作联接操作联接操作是从两个关系的笛卡尔积中选取属性间满足一定条件的元是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。记作:组。记作:其中其中A和和B分别为分别为R和和S上可比的属性组。上可比的属性组。自然联接自然联接(Natural join)是一种特殊的等值联接,它要求两个关系中)是一种特殊的等值联接,它要求两个关系中进行比较的分量必须是相同的属性组,并且要在结果中把重复的属性进行比较的分量必须是相同的属性组,并且要在结果中把重复的属性去掉。即若去掉。即若R和和S具有相同的属性组具有相同的属性组B,则自然连接
10、可记作:,则自然连接可记作:等值连接等值连接(equi-join),),为为“”的连接运算称为等值连接。它是从的连接运算称为等值连接。它是从关系关系R与与S的笛卡尔积中选取的笛卡尔积中选取A、B属性值相等的那些元组。即等值连属性值相等的那些元组。即等值连接为:接为:(回顾)自然联接图 自然联接实例自然联接自然联接的结果是在的结果是在 R R 和和 S S 中的在它们的公共属性名字上相等的所有中的在它们的公共属性名字上相等的所有元组的组合。例如下面是表格元组的组合。例如下面是表格“雇员雇员”和和“部门部门”和它们的自然联接和它们的自然联接:(回顾)等值联接图-联接实例-联接和等值联接联接和等值联
11、接如果我们要组合来自两个关系的元组,而组合条件不是简单的共享属性如果我们要组合来自两个关系的元组,而组合条件不是简单的共享属性上的相等,则有一种更一般形式的连接算子才方便,这就是上的相等,则有一种更一般形式的连接算子才方便,这就是 -联接联接(或或 theta-theta-联接联接)。是在集合是在集合 ,中的二元关系。中的二元关系。的结果由在的结果由在 R R 和和 S S 中满足关系中满足关系 的元素的所有组合构成。只有的元素的所有组合构成。只有 S S 和和 R R 的表头是不相的表头是不相交的,即不包含公共属性的情况下,交的,即不包含公共属性的情况下,-连接的结果才是有定义的。连接的结果
12、才是有定义的。实例:实例:考虑分别列出车模和船模的价格的表“车”和“船”。假设一个顾客要购买一个车模和一个船模,但不想为船花费比车更多的钱。在关系上的-联接 CarPrice BoatPrice 生成所有可能选项的一个表。9.3.3 半联接操作原理和不对称性半联接操作半联接操作是关系代数操作中联接(是关系代数操作中联接(JOIN)操作的一种缩减,关系)操作的一种缩减,关系R和和S的半联接记为的半联接记为RS。其结果关系是其结果关系是R和和S的自然联接(的自然联接(Natural JOIN)后,)后,在在R的属性上的投影的属性上的投影,可用下述表达式表示:,可用下述表达式表示:RS=R(RS)等
13、价方法:将等价方法:将S中与中与R有相同属性名的属性集投影出来,然后与有相同属性名的属性集投影出来,然后与R完成自然完成自然联接,其等价公式为:联接,其等价公式为:RS=R (BS)具不对称操作性:具不对称操作性:RSSR。(回顾)半联接图 半联接实例半联接半联接的结果只是在 S 中有在公共属性名字上相等的元组所有的 R 中的元组。实例:实例:“雇员”和“部门”和它们的半联接的表:9.3.4 半联接操作的缩减作用例例4.17 有R(A,B)和 S(B,C),根据半联接计算公式有:和 。如果有图 4.21(a)的实例,则 R S的结果如 4.21(b)所示,S R的结果如图4.21(C)所示。)
14、(SRSRBB)(RSRSBBBB图图4.12 半联接操作的不对称性与缩减作用半联接操作的不对称性与缩减作用 从图从图4.21(b)、()、(c)可得出结论:半联接操可得出结论:半联接操作作对操作数对操作数R或或S有缩减有缩减作用作用,且由于,且由于其不对称其不对称性则各自缩减的程度不性则各自缩减的程度不一样一样。半联接操作的缩。半联接操作的缩减性与在联接操作前先减性与在联接操作前先对操作数关系做选择和对操作数关系做选择和投影有相似的效果。特投影有相似的效果。特别在分布式环境中,可别在分布式环境中,可用半联接操作减少网上用半联接操作减少网上数据的传送量。数据的传送量。9.3.5 半联接程序的作
15、用半联接程序半联接程序是用半联接技术实现联接操作的程序,即用一组具有半联接与是用半联接技术实现联接操作的程序,即用一组具有半联接与联接的操作,映射出具有与等值联接相同结果的过程。联接的操作,映射出具有与等值联接相同结果的过程。SSRSRBABBABA)(4-11a)RRSSRABAABBA)(4-11b)(411a)、()、(411b)式说明半联接程序与两个关系的直接等值联接等价。)式说明半联接程序与两个关系的直接等值联接等价。同样,在分布式数据库中,当同样,在分布式数据库中,当R,S两个关系不在相同场地上时,用(两个关系不在相同场地上时,用(411a)公式或()公式或(411b)公式处理,可
16、公式处理,可以减少联接操作的数据传送量,并且以减少联接操作的数据传送量,并且半联接程序的技术可以缩减它的操作数。半联接程序的技术可以缩减它的操作数。9.3.6 半联接程序的具体过程以式(以式(4-11a)为例,且假定)为例,且假定 R和和S不在同一场地:不在同一场地:在在s场地对场地对S关系做投影操作,使关系做投影操作,使S关系缩减为关系缩减为S:SSB 将将S送往送往r场地;场地;在在r场地上完成场地上完成R与与S的半联接操作,使的半联接操作,使R关系缩减为关系缩减为R:RSRBA 将将R关系送回关系送回S场地;场地;在在S场地完成场地完成R与与S的联接操作。的联接操作。SRT图图4.22
展开阅读全文