第5章查询处理和优化ppt课件

1、第5章 查询处置和优化5.1 引言5.2 代数优化5.3 依赖于存取途径的规那么优化5.4 代价估算优化*5.1 引言概述查询是数据库系统中最根本、最常见和最复杂的操作。对数据库的查询普通都是以查询言语如SQL表示。从查询恳求出发，直到得到查询结果，这一过程称为查询处置。关系数据库系统的查询言语普通是“非过程言语，它减轻了用户选择存取途径的负担。用户只需提出干什么，不用指出怎样干。即用户不用关怀查询的详细执行过程，而由DBMS确定合理的、有效的执行战略。DBMS在这方面的作用称为查询优化 。对于运用非过程查询言语的RDBMS，查询优化是查询处置中非常重要的一环，对系统性能会产生很大的影响。5.

2、1 引言2.查询处置的普经过程查询处置的普经过程 先做词法和语法分析，把查询语句变成语先做词法和语法分析，把查询语句变成语法树或语法图；然后进展查询优化，构成执行法树或语法图；然后进展查询优化，构成执行方案，生成可执行代码，交系统执行。方案，生成可执行代码，交系统执行。详细处置过程也可分为解释和编译两种实详细处置过程也可分为解释和编译两种实现方式。现方式。解释方式如图解释方式如图61所示。所示。编译方式如图编译方式如图62所示。所示。对于常用的例行事务，编译方式可以显著对于常用的例行事务，编译方式可以显著地提高数据库性能。地提高数据库性能。对于那些不怎样反复运用的偶尔查询，解对于那些不怎样反复

3、运用的偶尔查询，解释也不失为一种简单、适用的实现方式。这两释也不失为一种简单、适用的实现方式。这两种实现方式在现有的商用种实现方式在现有的商用DBMS中都有运用。中都有运用。 5.1 引言3. 例子首先看一个简单的例子，阐明为什么要进展查询优化。 例：求选修了2号课程的学生姓名。用SQL言语表达： SELECT Sname FROM S，SC WHERE S.SNO=SC.SNO AND SCO=2； 假定学生-课程数据库中有l000个学生记录,l0000个选课记录，其中选修2号课程的选课记录为50个。 系统可以用多种等价的关系代数表达式来完成这一查询 1.Q1= Sname( S.sno=s

4、c.snosco=2(SSC) 2.Q2= Sname( sco=2 (S |10000;5.2 代数优化 图6-3(a) Q的原始查询树(P125) 图6-3(b) 将选择操作尽量下推 图6-3(c) 将衔接条件与笛卡儿积组合成衔接操作 图6-3(d) 另一种查询执行方案 图6-3(e) 用投影操作消除对查询无用的属性5.3 依赖于存取途径的优化 选择操作的实现和优化选择操作的执行战略与选择条件、可用的存取途径以及满足选择条件的元组数在整个关系中所占的比例有关。选择条件可分为：等值(=)、范围(,=,Between )和集合(IN)等几种。复合选择条件由简单项选择择条件经过AND、OR衔接而

5、成。选择操作的实现方法包括：(1) 顺序扫描：适用于小的关系，满足条件的元组比例较大或无其他存取途径。(2) 利用各种存取途径：包括索引B+树，动态散列 对于选择操作可按照以下启发式规那么选取存取途径： (8) P128-1295.3 依赖于存取途径的优化 衔接操作的实现和优化 主要思索二元衔接(two-way join)。 多元衔接(multi-may join)那么以二元衔接为根底。 实现衔接操作普通有以下4种方法： 嵌套循环法(nested loop) 顺序扫描外关系的每一个元组，然后与内关系的每一个元组进展匹配 详细算法见P129 图6-4 设 bR ，bS分别表示R和S的物理块数，n

6、B为可用的内存缓冲块数，并以其中(nB 1)块存放外关系，剩余的1块存放内关系。 假设以R为外关系，S为内关系，用嵌套循环法进展衔接需求访问的物理块数为： bR+bR/(nB-1) bS 假设以S为外关系，R为内关系，用嵌套循环法进展衔接需求访问的物理块数为： bS+bS/(nB-1) bR 比较上面2个式子，可以看出选择占用物理块少的关系作为外关系 5.3 依赖于存取途径的优化衔接操作的实现和优化(续)利用索引或散列寻觅匹配元组法 可有效减少I/O次数 排序归并(sort-merge)法 首先按衔接属性对关系排序，然后进展归并衔接 详细算法见P131 图6-6散列衔接法(hash join)

7、 首先用散列函数将衔接属性散列至文件中，然后对散列到同一个桶(Bucket)中的元组进展匹配。有关衔接操作实现战略的启发式规那么：(1) (4) P131-1325.3 依赖于存取途径的优化投影操作的实现投影操作普通可与选择、衔接等操作同时进展，不再需求附加的I/O开销。反复值的消除：排序，散列详细实现算法见 P132 图6-7集合操作的实现对于笛卡儿积()普通可采用嵌套循环法；对于、等操作需求发现共同元组 ；详细算法见P133 图6-8 图6-9 图6-10组合操作减少暂时文件，尽能够同时执行操作。 5.4 代价估算优化*查询执行代价的组成与代价统计参数查询执行代价主要包括3个方面： I/O

8、代价(*)CPU代价通讯代价访问磁盘1次所需的代价可表示为： CI/O=D0 + xD1 其中：x 存取数据的大小，以字节表示 D0 与x无关的I/O代价，包括寻道时间和等待时间 D1 每个字节所需的传输时间普通D0 xD1 故 I/O代价=I/O次数 D05.4 代价估算优化查询执行代价的组成与代价统计参数(续)下面给出进展代价估算时将要用到的统计参数： nR：R中的元组数； PR ： R块因子，即每个物理块中包含的元组数； Na： 属性A在一个关系中出现的不同值的个数； Fa： 属性A的选择因子，即属性A为某一个值的概率，普通假定属性值均匀分布， FA=1/ Na ； Ma：属性A的值域大

9、小|DOM(A)|； L：索引的级数；5.4 代价估算优化 选择操作的代价估算(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) 利用聚簇索引进展范围查询 CCI

10、R=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)试用代价估算优化选取存

11、取战略，并估算其执行代价。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上建有辅助(二次)索引，但不是聚簇索引。假设取一半元组，那么运用索引还不如运用顺序扫描，故

12、： 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

13、/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 代价估算优化 衔接操作的代价估算 衔接结果大小的估算 为估算衔接操作的代价，首先需求估算衔接结果的大小