第5章查询处理和优化ppt课件.ppt
第5章查询处理和优化ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望5.1 引言1.概述查询是数据库系统中最基本、最常见和最复杂的操作。对数据库的查询一般都是以查询语言（如SQL）表示。从查询请求出发，直到得到查询结果，这一过程称为查询处理。关系数据库系统的查询语言一般是“非过程语言”，它减轻了用户选择存取路径的负担。用户只要提出干什么，不必指出怎么干。即用户不必关心查询的具体执行过程，而由DBMS确定合理的、有效的执行策略。DBMS在这方面的作用称为查询优化。对于使用非过程查询语言的RDBMS，查询优化是查询处理中非常重要的一环，对系统性能会产生很大的影响。5.1 引言2.查询处理的一般过程查询处理的一般过程 先做词法和语法分析，把查询语句变成语法树或语法图；然后进行查询优化，形成执行计划，生成可执行代码，交系统执行。具体处理过程也可分为解释和编译两种实现方式。解释方式如图61所示。编译方式如图62所示。对于常用的例行事务，编译方式可以显著地提高数据库性能。对于那些不怎么重复使用的偶然查询，解释也不失为一种简单、实用的实现方式。这两种实现方式在现有的商用DBMS中都有应用。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=Sname(S.sno=o=2(SSC)2.Q2=Sname(o=2(S|10000;5.2 代数优化 图6-3(a)Q的原始查询树(P125)图6-3(b)将选择操作尽量下推 图6-3(c)将连接条件与笛卡儿积组合成连接操作 图6-3(d)另一种查询执行方案 图6-3(e)用投影操作消除对查询无用的属性5.3 依赖于存取路径的优化1.选择操作的实现和优化选择操作的执行策略与选择条件、可用的存取路径以及满足选择条件的元组数在整个关系中所占的比例有关。选择条件可分为：等值(=)、范围(,=,Between)和集合(IN)等几种。复合选择条件由简单选择条件通过AND、OR连接而成。选择操作的实现方法包括：(1)顺序扫描：适用于小的关系，满足条件的元组比例较大或无其他存取路径。(2)利用各种存取路径：包括索引（B+树），动态散列 对于选择操作可按照下列启发式规则选取存取路径：(1)(8)P128-1295.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为内关系，用嵌套循环法进行连接需要访问的物理块数为：bS+bS/(nB-1)bR 比较上面2个式子，可以看出选择占用物理块少的关系作为外关系 5.3 依赖于存取路径的优化2.连接操作的实现和优化(续)2)利用索引或散列寻找匹配元组法 可有效减少I/O次数 3)排序归并(sort-merge)法 首先按连接属性对关系排序，然后进行归并连接 具体算法见P131 图6-64)散列连接法(hash join)首先用散列函数将连接属性散列至文件中，然后对散列到同一个桶(Bucket)中的元组进行匹配。有关连接操作实现策略的启发式规则：(1)(4)P131-1325.3 依赖于存取路径的优化3.投影操作的实现投影操作一般可与选择、连接等操作同时进行，不再需要附加的I/O开销。重复值的消除：排序，散列具体实现算法见 P132 图6-74.集合操作的实现对于笛卡儿积()一般可采用嵌套循环法；对于、等操作需要发现共同元组；具体算法见P133 图6-8 图6-9 图6-105.组合操作减少临时文件，尽可能同时执行操作。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次数 D05.4 代价估算优化1.查询执行代价的组成与代价统计参数(续)下面给出进行代价估算时将要用到的统计参数：nR：R中的元组数；PR：R块因子，即每个物理块中包含的元组数；Na：属性A在一个关系中出现的不同值的个数；Fa：属性A的选择因子，即属性A为某一个值的概率，一般假定属性值均匀分布，FA=1/Na ；Ma：属性A的值域大小|DOM(A)|；L：索引的级数；5.4 代价估算优化2.选择操作的代价估算(1)顺序扫描最多选取一个元组的I/O代价：Csa=0.5n/p=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/25.4 代价估算优化例：设有关系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)试用代价估算优化选取存取策略，并估算其执行代价。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)是范围查询。虽然在AGE上建有辅助(二次)索引，但不是聚簇索引。如果取一半元组，则使用索引还不如使用顺序扫描，故：CQ3=b=2000Q4：查询条件是合取式。由于没有适当的多属性索引可用，只有2种可能的策略：5.4 代价估算优化策略1：预查询法DEPT=CSAND DNO=108 AND AGE=20(STUDENT)满足条件 DNO=108 的元组数估算为：n/NDNO=10000/20=500设顺序集每块可容纳200个tid，则从DNO辅助索引的顺序集中取500个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=5335.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=Cb=825.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.4 代价估算优化(2)嵌套循环法代价估算(3)排序归并法代价估算(4)散列连接法代价估算
