《第5章查询处理和优化ppt课件》由会员分享，可在线阅读，更多相关《第5章查询处理和优化ppt课件（40页珍藏版）》请在金锄头文库上搜索。
1、第5章 查询处理和优化5.1 引言5.2 代数优化5.3 依赖于存取路径的规则优化5.4 代价估算优化*冰渔馒遥斟惩詹户歧梭睫酥徽敞继焙产未筐叁齐燎绣勘磊洞签杜嚎迈验掏第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.1 引言1.概述查询是数据库系统中最基本、最常见和最复杂的操作。对数据库的查询一般都是以查询语言（如SQL）表示。从查询请求出发，直到得到查询结果，这一过程称为查询处理。关系数据库系统的查询语言一般是“非过程语言”，它减轻了用户选择存取路径的负担。用户只要提出干什么，不必指出怎么干。即用户不必关心查询的具体执行过程，而由DBMS确定合理的、有效的执行策略。DBMS在
2、这方面的作用称为查询优化 。对于使用非过程查询语言的RDBMS，查询优化是查询处理中非常重要的一环，对系统性能会产生很大的影响。隧俐扩虽滇加富卧拂殊碱她夏炸库峨锄听侥慰帐蝉诬洱砌眺础厄慈弗蒂绞第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.1 引言2.查询处理的一般过程查询处理的一般过程 先做词法和语法分析，把查询语句变成语法树或语法图；然后进行查询优化，形成执行计划，生成可执行代码，交系统执行。具体处理过程也可分为解释和编译两种实现方式。解释方式如图61所示。编译方式如图62所示。对于常用的例行事务，编译方式可以显著地提高数据库性能。对于那些不怎么重复使用的偶然查询，解释也不
3、失为一种简单、实用的实现方式。这两种实现方式在现有的商用DBMS中都有应用。 键震鸽笨怔饥恍厚阑篓撞祷劲扩兔菌摩骗沫籽迪加游螟寞区捂宫堰貌窥侵第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.1 引言3. 例子首先看一个简单的例子，说明为什么要进行查询优化。 例：求选修了2号课程的学生姓名。用SQL语言表达： SELECT Sname FROM S，SC WHERE S.SNO=SC.SNO AND SC.CNO=2； 假定学生-课程数据库中有l000个学生记录,l0000个选课记录，其中选修2号课程的选课记录为50个。 系统可以用多种等价的关系代数表达式来完成这一查询 1.Q1
4、= Sname( S.sno=o=2(SSC) 2.Q2= Sname( o=2 (S |10000;服嫂腑央谰掳却赏完拈纹澡骏晕奥汛栅衰劈焦又卓哲诫媳择扬红豺吮噶夕第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.2 代数优化 图6-3(a) Q的原始查询树(P125) 图6-3(b) 将选择操作尽量下推 图6-3(c) 将连接条件与笛卡儿积组合成连接操作 图6-3(d) 另一种查询执行方案 图6-3(e) 用投影操作消除对查询无用的属性霉棺淖砧粮硬雷戌太损笼京萧总话币哮裔黎坏汞镭炸肯铲芦戍认援熊枪没第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.3 依赖于存取
5、路径的优化1. 选择操作的实现和优化选择操作的执行策略与选择条件、可用的存取路径以及满足选择条件的元组数在整个关系中所占的比例有关。选择条件可分为：等值(=)、范围(,=,Between )和集合(IN)等几种。复合选择条件由简单选择条件通过AND、OR连接而成。选择操作的实现方法包括：(1) 顺序扫描：适用于小的关系，满足条件的元组比例较大或无其他存取路径。(2) 利用各种存取路径：包括索引（B+树），动态散列 对于选择操作可按照下列启发式规则选取存取路径：(1) (8) P128-129该课态菌淹然情垛南壤索茵寄瞎州三尸局缩哮且翰搅原砖传莎羌谜妨僵撞第5章查询处理和优化ppt课件第5章查询
6、处理和优化ppt课件5.3 依赖于存取路径的优化2.连接操作的实现和优化主要考虑二元连接(two-way join)。多元连接(multi-may join)则以二元连接为基础。实现连接操作一般有下列4种方法：1)嵌套循环法(nested loop) 顺序扫描外关系的每一个元组，然后与内关系的每一个元组进行匹配 具体算法见P129 图6-4 设 bR ，bS分别表示R和S的物理块数，nB为可用的内存缓冲块数，并以其中(nB 1)块存放外关系，剩余的1块存放内关系。 若以R为外关系，S为内关系，用嵌套循环法进行连接需要访问的物理块数为： bR+bR/(nB-1) bS 若以S为外关系，R为内关系
7、，用嵌套循环法进行连接需要访问的物理块数为： bS+bS/(nB-1) bR 比较上面2个式子，可以看出选择占用物理块少的关系作为外关系 眼人抠摆提桶梳名罗获难窖脓铂躺窍浓戒吞湍逞窥朗身驳俞协世花湛碰踊第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.3 依赖于存取路径的优化2.连接操作的实现和优化(续)2)利用索引或散列寻找匹配元组法 可有效减少I/O次数 3)排序归并(sort-merge)法 首先按连接属性对关系排序，然后进行归并连接 具体算法见P131 图6-64)散列连接法(hash join) 首先用散列函数将连接属性散列至文件中，然后对散列到同一个桶(Bucket)
8、中的元组进行匹配。有关连接操作实现策略的启发式规则：(1) (4) P131-132编停岿矮叁篆艾支羚蓬唐剑髓皂零吸八高注恼剖用畜刃晃醇涉擒姐杰俺术第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.3 依赖于存取路径的优化3.投影操作的实现投影操作一般可与选择、连接等操作同时进行，不再需要附加的I/O开销。重复值的消除：排序，散列具体实现算法见 P132 图6-74.集合操作的实现对于笛卡儿积()一般可采用嵌套循环法；对于、等操作需要发现共同元组 ；具体算法见P133 图6-8 图6-9 图6-105.组合操作减少临时文件，尽可能同时执行操作。 撤茸疥哈怎息茨穿凉残碰似俐赁徘冶全
9、野笑潞尊熙巨个诛雍哑筒贫读阶卵第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.4 代价估算优化*1.查询执行代价的组成与代价统计参数查询执行代价主要包括3个方面：1) I/O代价(*)2)CPU代价3)通信代价访问磁盘1次所需的代价可表示为： CI/O=D0 + xD1 其中：x 存取数据的大小，以字节表示 D0 与x无关的I/O代价，包括寻道时间和等待时间 D1 每个字节所需的传输时间一般D0 xD1 故 I/O代价=I/O次数 D0耀刽栈弥颠怠椿浇瑞克弄泥耗猫怯蓑彪烽寻氧铡硕叁峻芽肝护佃钦烧星字第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.4 代价估算优化
10、1.查询执行代价的组成与代价统计参数(续)下面给出进行代价估算时将要用到的统计参数： nR：R中的元组数； PR ： R块因子，即每个物理块中包含的元组数； Na： 属性A在一个关系中出现的不同值的个数； Fa： 属性A的选择因子，即属性A为某一个值的概率，一般假定属性值均匀分布， FA=1/ Na ； Ma：属性A的值域大小|DOM(A)|； L：索引的级数；操俊您荒想霓惦辩弦蒜淖降苦蓉荧涨粮溢旱浚蒲娄莹辫飞祁予资翰绅结绵第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.4 代价估算优化2. 选择操作的代价估算(1) 顺序扫描最多选取一个元组的I/O代价：Csa=0.5n/p=
11、0.5 b选取多个元组的I/O代价： Csb = b(2) 利用主键上的索引或散列进行等值查询通过索引访问的I/O代价：Cik = L+1通过散列访问的I/O代价：Chk = 1 (假定散列没有溢出)(3) 利用非主键上的无序索引进行等值查询分析表明几乎每取一个元组都需要访问一个物理块，故 CINK = L + s 其中 s 为满足选择条件的元组数(4) 利用聚簇索引进行等值查询 CCI = L + s/p(5) 利用聚簇索引进行范围查询 CCIR=L + b/2赘志痴绿跋脑兰补拔构汲渠噬芳暮秤皑毫饱约诣码呢浇哪趴峰婚它兽堪甄第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.4
12、代价估算优化例：设有关系STUDENT，其统计数据及存取路径如下：n=10000b=2000 即 p=5在属性DEPT上建有聚簇索引：NDEPT = 25， L=2在属性SNO上建有主键索引：NSNO = 10000， L=4在属性DNO上建有辅助索引：NDNO = 20， L=3在属性AGE上建有辅助索引：NAGE = 15， L=2设有下列查询：Q1：SNO=992311(STUDENT)Q2：DEPT=CS(STUDENT)Q3：AGE=20(STUDENT)Q4：DEPT=CSAND DNO=108 AND AGE=20(STUDENT)试用代价估算优化选取存取策略，并估算其执行代价。
13、傈帕便果迄空完猫大袭烷炯贤圣拦糟秀坑猖弘蹲畏藉宾米判倦避确耪辈平第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.4 代价估算优化解：Q1：SNO=992311(STUDENT) 由于SNO上建有主索引，应优先采用主索引，其执行代价可估算为： CQ1=L+1=4+1=5Q2：DEPT=CS(STUDENT) DEPT上建有聚簇索引，故可不考虑顺序扫描。满足Q2的元组数s估计为: s=10000/25=400由于STUDENT关系对DEPT是聚簇的，故I/O代价可估算为： CQ2=L + s/p = 2 + 400/5 = 82Q3：AGE=20(STUDENT) 是范围查询。虽然
14、在AGE上建有辅助(二次)索引，但不是聚簇索引。如果取一半元组，则使用索引还不如使用顺序扫描，故： CQ3 = b = 2000Q4：查询条件是合取式。由于没有适当的多属性索引可用，只有2种可能的策略：臣哈字蚜骗蟹挛鹃苦渭徘春元表随孝朝尺涂塔水双散辩撼抗射意符丑扭曙第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.4 代价估算优化策略1：预查询法DEPT=CSAND DNO=108 AND AGE=20(STUDENT)满足条件 DNO=108 的元组数估算为： n/NDNO = 10000/20 = 500设顺序集每块可容纳200个tid，则从DNO辅助索引的顺序集中取500个
15、tid所需的I/O代价为 CDNO = L + 500/200 = 3+3 =6满足条件 AGE= 20 的元组数估算为：n/2 = 10000/2 = 5000则从AGE辅助索引的顺序集中取5000个tid所需的I/O代价为 CAGE = L + 5000/200 = 2+25 = 272个tid集的交集的大小应小于或等于500。由于取500个随机存放的元组一般需要500次I/O，故预查询法的I/O代价估算为： Ca = CDNO + CAGE + 500 = 533孽咒煤晚灵牲分壹专佣剑士豌搅肖寺捅腔凛溺扩瞥铸嫁且煤固合管株掌捌第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5
16、.4 代价估算优化策略2：用其中代价最小的一个条件选出元组，再用其他 条件对这些元组进行筛选应从3个条件中选出I/O代价最小的条件：DEPT=CSAND DNO=108 AND AGE=20(STUDENT)DEPT=CS：同Q2，CQ2 = 82DNO=108：s = 10000/20= 500 CDNO=108 = CDNO+500 = 6 + 500=506AGE=20：同Q3，CQ3 = 2000在3个条件中，以DEPT=CS的代价最小，故可先按此条件选取出满足条件DEPT=CS的学生的元组并同时检查每个元组是否满足其他2个条件，其I/O代价为 Cb = 82由于CaCb，故CQ4=C
17、b=82检督库唉拌惹烃甚步盼皆灸计秒闺凛埋巷义咀防后此撞奖懈貌瞄陵褒付写第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.4 代价估算优化3.连接操作的代价估算(1)连接结果大小的估算为估算连接操作的代价，首先需要估算连接结果的大小。为此，引入连接选择因子(join selectivity) js = | R|CS | / |R| |S| 如果无连接条件C，则js=1如果没有元组满足连接条件，则js=0一般 0=js=1如果连接属性A为R的键，则js= 1/ |R|如果连接属性A为S的键，则js|CS | = (|R| |S| )/M 其中M为连接属性A的值域大小。梗嫡约踩过汉狞胳等批翘交抑郊属怕牺店围渠棱草戮得糜觅输奸损肆株瘟第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件5.4 代价估算优化(2)嵌套循环法代价估算(3)排序归并法代价估算(4)散列连接法代价估算瘤男阉抱言捧泪性聋协岿衰寺出糠拜这冈雄膜蒙维菲峻爱浴众窒柑形经素第5章查询处理和优化ppt课件第5章查询处理和优化ppt课件
