第5章 查询处理和优化 5.1 引言 5.2 代数优化 5.3 依赖于存取路径的规则优化 5.4 代价估算优化*

5.1 引言 概述 查询是数据库系统中最基本、最常见和最复杂的操作。对数据库的查询一般都是以查询语言（如SQL）表示。从查询请求出发，直到得到查询结果，这一过程称为查询处理。 关系数据库系统的查询语言一般是“非过程语言”，它减轻了用户选择存取路径的负担。用户只要提出‘干什么’，不必指出‘怎么干’。即用户不必关心查询的具体执行过程，而由DBMS确定合理的、有效的执行策略。DBMS在这方面的作用成为查询优化 。 对于使用非过程查询语言的RDBMS，查询优化是查询处理中非常重要的一环，对系统性能会产生很大的影响。

5.1 引言 查询优化的优点 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。这是因为： 优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。

5.1 引言 查询优化的目标和途径 关系数据库查询优化的总目标是：选择有效的策略，求得给定关系表达式的值。 查询优化的途径包括： 对查询语句进行等价变换（如改变基本操作的顺序）使查询执行起来更加有效。这种优化只涉及查询语句本身，而不涉及存取路径，故称为独立于存取路径的优化，或代数优化。 根据系统提供的查询路径，选择合理的存取策略（例如是选择顺序扫描还是选择索引），这称为依赖于存取路径的优化，或称物理优化。 有些查询可根据启发式规则选择执行策略，这称为规则优化。 根据可供选择的执行策略进行代价估算，并从中选择代价最小的执行策略，这称为代价估算优化。 此外，还可以通过应用数据库的语义信息对查询进行优化，这称为语义优化。

5.1 引言 查询处理和优化的步骤 实际系统对查询优化的具体实现一般可以归纳为四个步骤： 在集中式数据库中，查询的执行开销主要包括： 将查询转换成某种内部表示，通常是语法树。 根据一定的等价变换规则把语法树转换成标准（优化）形式。 选择低层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 生成查询计划。查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。 在集中式数据库中，查询的执行开销主要包括： 总代价 = I/O代价 + CPU代价 在多用户环境下： 总代价 = I/O代价 + CPU代价 + 内存代价

5.1 引言 一个简单的例子 首先看一个简单的例子，说明为什么要进行查询优化。 例：求选修了2号课程的学生姓名。用SQL语言表达： SELECT S.Sname FROM Student S，SC WHERE S.SNO=SC.SNO AND SC.CNO='2'； 假定学生-课程数据库中有l000个学生记录,l0000个选课记录，其中选修2号课程的选课记录为50个。 系统可以用多种等价的关系代数表达式来完成这一查询 1.Q1= Sname(σ Student.sno=sc.sno∧sc.cno='2'(Student×SC)) 2.Q2= Sname(σ sc.cno='2' (Student |><|SC)) 3.Q3= Sname(Student|><| σ sc.cno='2'(SC)) 还可以写出几种等价的关系代数表达式,但分析这三种就足以说明问题了。我们将看到由于查询执行的策略不同,查询时间相差很大。

5.1 引言 查询执行策略Q1代价分析 计算广义笛卡尔积的代价 把S和SC的每个元组连接起来。一般连接的做法是：在内存中尽可能多地装人某个表(如Student表)的若干块元组，留出一块存放另一个表(如SC表)的元组。然后把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上，再从SC中读入一块和内存中的S元组连接，直到SC表处理完。这时再一次读入若干块S元组，读入一块SC元组，量复上述处理过程，直到把S表处理完。 设一个块能装l0个Student元组或l00个SC元组，在内存中存放5块Student元组 和l块SC元组，则读取总块数为： 1000/10+1000/(10 X 5) X (10000/100)=2100块 其中读Student表l00块。读SC表20遍，每遍l00块。若每秒读写20块，则总计要花105(秒)。 连接后的元组数为1000X10000。设每块能装l0个元组，则写出这些块要花1000000/20=50000( 秒)。

5.1 引言 查询执行策略Q1代价分析(续) 选择操作的代价 依次读入连接后的元组，按照选择条件选取满足要求的的记录。假定内存处理时间忽略。这一步读取中间文件花费的时间(同写中间文件一样)需50000 秒。满足条件的元组假设仅50个，均可放在内存。 投影操作的代价 把第2步的结果在Sname上作投影输出,得到最终结果。 因此第一种情况下执行查询的总时间约为105+2X5X10000秒。这里，所有内存处理时间均忽略不计。

5.1 引言 查询执行策略Q2代价分析 因此，第二种情况总的执行时间≈105+50+50≈205秒。 计算自然连接的代价 为了执行自然连接，读取Student和SC表的策略不变,总的读取块数仍为2100块，花费l05秒。但自然连接的结果比第一种情况大大减少，为 10000个。因此写出这些元组时间为 /10/20=50秒。仅为第一种情况的千分之一。 读取中间文件块，执行选择运算，花费时间也为50秒。 将第2步结果投影输出。 因此，第二种情况总的执行时间≈105+50+50≈205秒。

5.1 引言 查询执行策略Q3代价分析 先对SC表作选择运算，只需读一遍SC表，存取l00块花费时间为5秒，因为满足条件的元组仅50个，不必使用中间文件。 读取STUDENT表，把读入的STUDENT元组和内存中的SC元组作连接。也只需读一遍STUDENT表共l00块花费时间为5秒。 把连接结果投影输出。 第三种情况总的执行时间≈5+5≈10秒。

5.1 引言 假如SC表的Cno字段上有索引，第l步就不必读取所有的SC元组而只需读取CNO=‘2’的那些元组(50个)。 存取的索引块和SC中满足条件的数据块大约总共3～4块。若STUDENT表在Sno上也有索引，则第2步也不必读取所有的STUDENT元组，因为满足条件的SC记录仅50个，涉及最多50个STUDENT记录，因此读取STUDENT表的块数也可大大减少。总的存取时间将进一步减少到数秒。 这个简单的例子充分说明了查询优化的必要性，同时也给了我们一些查询优化方法的初步概念。如当有选择和连接操作时，应当先做选择操作，这样参加连接的元组就可以大大减少。 下面给出查询优化的一般策略。

5.2 代数优化 查询优化的一般准则 下面的优化策略一般能提高查询效率,但不一定是所有策略中最优的。其实‘优化’一词并不确切，也许‘改进’或‘改善’更恰当些。 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。它常常可使执行时节约几个数量级，因为选择运算一般使计算的中间结果大大变小。 在执行连接前对关系适当地预处理。预处理方法主要有两种，在连接属性上建立索引和对关系排序，然后执行连接。第一种称为索引连接方法，第二种称为排序合并（SORT-MERGE）连接方法。 将投影运算和选择运算同时进行。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完戌所有的这些运算以避免重复扫描关系。

5.2 代数优化 把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。 将某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。 找出公共子表达式。如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读人这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写人中间文件。当查询的是视图时，定义视图的表达式就可成为公共子表达式。

5.2 代数优化 关系代数等价变换规则 上面的优化策略大部分都涉及到代数表达式的变换。关系代数表达式的优化是查询优化的基本课题。而研究关系代数表达式的优化最好从研究关系表达式的等价变换规则开始。 两个关系表达式El和E2是等价的，可记为E1≡E2。 常用的等价变换规则有： (1)选择的串接 σF1(σF2(R))≡σF1∧ F2(R) (2) 选择的交换 σF1(σF2(R))≡σF2(σF1(R))

5.2 代数优化 (3)投影的串接. πL1(πL2(…πLn(R)…)) ≡πL1(R) 条件：L1 L2 … Ln (4)选择与投影的交换. πL(σF(R))≡σF(πL(R)) 条件：Attr(F)是L的子集 (5)连接／笛卡儿积的交换律 R|><| S≡S|><| R R×S≡S×R

5.2 代数优化 (6)选择对连接／笛卡儿积的分配律 σF(R|><|S) ≡ (σF(R))|><|S 条件：Attr(F)∩Attr(S)=NULL σF1∧ F2 (R|><|S) ≡σF1(R)|><|F2(S) 条件： Attr(F1)∩Attr(S)=NULL, Attr(F2)∩Attr(R)=NULL (7)投影对连接／笛卡儿积的分配律 πL1∪L2(R|><|S) ≡πL1 (R)|><|πL2 (R) F F Attr(F) Attr(L1∪L2)

5.2 代数优化 (8)选择对∪、∩、－的分配律 σF(R∪S) ≡σF(R) ∪σF(S) σF(R∩S) ≡σF(R)∩σF(S) (9)投影对∪的分配率. πL (R∪S) ≡πL (R) ∪πL (S) (10) |><|、×、∪、∩的结合率 (R|><|S)|><|T≡R |><|(S|><|T)

5.2 代数优化 关系代数表达式优化算法 我们可以应用上面的变换法则来优化关系表达式，使优化后的表达式能遵循4.2.3中的一般原则。例如把选择和投影尽可能地早做(即把它们移到表达式语法树的下部)。下面给出关系表达式的优化算法。 算法：关系表达式的优化。 输入：一个关系表达式的语法树。 输出：计算该表达式的程序。 步骤： 利用规则(4)把形如 σ F1∧F2...∧Fn(E)的表达式变换为 σF1(σF2(...(σFn(E))...)) 对每一个选择，利用规则(4)—（8）尽可能把它移到树的叶端。 对每一个投影利用规则(3)，(9)，(l0)，(5)中的一般形式尽可能把它移向树的叶端。 注意，法则(3)可能回使一些投影消失，而一般形式的规则(5)则可能把一个投影分裂为两个，其中一个有可能被移向树的叶端。

5.2 代数优化 利用规则(3)～(5)把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种变换以乎违背‘投影尽可能早做’的原则，但这样做效率更高。 把上述得到的语法树的内节点分组。每一双目运算(×, ∩ |,∪，-)和它所有的直接祖先(包括σ , π运算)为一组。如果其后代直到叶子全是单目运算则也将它们并入该组，但当双目运算是笛卡尔积(×)，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。 生成一个程序，每组结点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。

5.2 代数优化 例：设有下列关系： S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) SP(SNUM,PNUM,DEPT,QUAN) 和如下查询： SELECT SNAME FROM S,SP,P WHERE S.SNUM=SP.SNUM AND SP.PNUM=P.PNUM AND S.CITY=‘NJ’ AND P.PNAME=‘BLOT’ AND SP.QUAN>10000;

5.2 代数优化 图6-3(a) Q的原始查询树(P119) 图6-3(b) 将选择操作尽量下推 图6-3(c) 将连接条件与笛卡儿积组合成连接操作 图6-3(d) 另一种查询执行方案 图6-3(e) 用投影操作消除对查询无用的属性

5.3 依赖于存取路径的优化 选择操作的实现和优化 选择操作的执行策略与选择条件、可用的存取路径以及满足选择条件的元组数在整个关系中所占的比例有关。 选择条件可分为：等值(=)、范围(<,<=,>,>=,Between )和集合(IN)等几种。 复合选择条件由简单选择条件通过AND、OR连接而成。 选择操作的实现方法包括： (1) 顺序扫描：适用于“小”的关系，满足条件的元组比例较大或无其他存取路径。 (2) 利用各种存取路径：包括索引（B+树），动态散列 对于选择操作可按照下列启发式规则选取存取路径： – (8) P122-123

5.3 依赖于存取路径的优化 连接操作的实现和优化 主要考虑二元连接(two-way join)。 多元连接(multi-may join)则以二元连接为基础。 实现连接操作一般有下列4种方法： 嵌套循环法(nested loop) 顺序扫描外关系的每一个元组，然后与内关系的每一个元组进行匹配 具体算法见P123 图6-4 设 bR ，bS分别表示R和S的物理块数，nB为可用的内存缓冲块数，并以其中(nB – 1)块存放外关系，剩余的1块存放内关系。 若以R为外关系，S为内关系，用嵌套循环法进行连接需要访问的物理块数为： bR+[bR/(nB-1)] X bS 若以S为外关系，R为内关系，用嵌套循环法进行连接需要访问的物理块数为： bS+[bS/(nB-1)] X bR 比较上面2个式子，可以看出选择占用物理块少的关系作为外关系

5.3 依赖于存取路径的优化 连接操作的实现和优化(续) 有关连接操作实现策略的启发式规则： 利用索引或散列寻找匹配元组法 可有效减少I/O次数 排序归并(sort-merge)法 首先按连接属性对关系排序，然后进行归并连接 具体算法见P125 图6-6 散列连接法(hash join) 首先用散列函数将连接属性散列至文件中（），然后对散列到同一个桶(Bucket)中的元组进行匹配。 有关连接操作实现策略的启发式规则： (1) – (4) P125-126

5.3 依赖于存取路径的优化 投影操作的实现 集合操作的实现 组合操作 对于笛卡儿积(×)一般可采用嵌套循环法； 投影操作一般可与选择、连接等操作同时进行，不再需要附加的I/O开销。 重复值的消除：排序，散列 具体实现算法见 P126 图6-7 集合操作的实现 对于笛卡儿积(×)一般可采用嵌套循环法； 对于∪、∩、－等操作需要发现共同元组 ； 具体算法见P127 图6-8 图6-9 图6-10 组合操作 减少临时文件，尽可能同时执行操作。

5.4 代价估算优化* 查询执行代价的组成与代价统计参数 查询执行代价主要包括3个方面： 访问磁盘1次所需的代价可表示为： 5.4 代价估算优化* 查询执行代价的组成与代价统计参数 查询执行代价主要包括3个方面： I/O代价(*) CPU代价 通信代价 访问磁盘1次所需的代价可表示为： CI/O=D0 + xD1 其中：x 存取数据的大小，以字节表示 D0 与x无关的I/O代价，包括寻道时间和等待时间 D1 每个字节所需的传输时间 一般D0>> Xd1 故 I/O代价=I/O次数 X D0

5.4 代价估算优化 查询执行代价的组成与代价统计参数(续) 下面给出进行代价估算时将要用到的统计参数： NR：R中的元组数； PR ： R块因子，即每个物理块中包含的元组数； nA： 属性A在一个关系中出现的不同值的个数； FA： 属性A的选择因子，即属性A为某一个值的概率，一般假定属性值均匀分布， FA=1/ Na ； MA：属性A的值域大小|DOM(A)|； L：索引的级数；

5.4 代价估算优化 选择操作的代价估算 (1) 顺序扫描 最多选取一个元组的I/O代价：Csa=0.5[n/p]=0.5 b 选取多个元组的I/O代价： Csa = 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.4 代价估算优化 例：设有关系STUDENT，其统计数据及存取路径如下： n=10000 b=2000 即 p=5 在属性DEPT上建有聚簇索引：NDEPT = 25， L=2 在属性SNO上建有主键索引：NSNO = 10000， L=4 在属性DNO上建有辅助索引：NDNO = 20， L=2 在属性AGE上建有辅助索引：NAFE = 15， L=2 设有下列查询： Q1：σSNO=‘992311’(STUDENT) Q2：σDEPT=‘CS’(STUDENT) Q3：σAGE>=20(STUDENT) Q4：σDEPT=‘CS’AND DNO=‘108’ AND AGE>=20(STUDENT) 试用代价估算优化选取存取策略，并估算其执行代价。

5.4 代价估算优化 解： Q1：由于SNO上建有主索引，应优先采用主索引，其执行代价可估 算为： CQ1=L+1=4+1=5 Q2：DEPT上建有聚簇索引，故可不考虑顺序扫描。满足Q2的元组 数s估计为: s=10000/25=400 由于STUDENT关系对DEPT是聚簇的，故I/O代价可估算为： CQ2=L + [s/p] = 2 + [400/5] = 82 Q3：是范围查询。虽然在AGE上建有辅助(二次)索引，但不是聚簇 索引。如果取一半元组，则使用索引还不如使用顺序扫描，故： CQ3 = b = 2000 Q4：查询条件是合取式。由于没有适当的多属性索引可用，只有2种 可能的策略：

5.4 代价估算优化 策略1：预查询法 满足条件 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 = 27 2个tid集的交集的大小应小于或等于500。由于取500个随机存放的元 组一般需要500次I/O，故预查询法的I/O代价估算为： Ca = CDNO + CAGE + 500 = 533

5.4 代价估算优化 σDEPT=‘CS’：同Q2，CQ2 = 82 σDNO=‘108’：s = 10000/20= 500 策略2：用其中代价最小的一个条件选出元组，再用其他 条件对这些元组进行筛选 应从3个条件中选出I/O代价最小的条件： σDEPT=‘CS’：同Q2，CQ2 = 82 σDNO=‘108’：s = 10000/20= 500 CDNO=‘108’ = CDNO+500 = 6 + 500=506 σAGE>=20：同Q3，CQ3 = 2000 在3个条件中，以σDEPT=‘CS’的代价最小，故可先按此条件选取出满 足条件DEPT=‘CS’的学生的元组并同时检查每个元组是否满足其他2个条件， 其I/O代价为 Cb = 82 由于Ca>Cb，故CQ4=Cb=82

5.4 代价估算优化 连接操作的代价估算 连接结果大小的估算 为估算连接操作的代价，首先需要估算连接结果的大小。为此，引入连接选择因子(join selectivity) js = | R|><|CS | / |R X S| = | R|><|CS | / |R| X |S| 如果无连接条件C，则js=1 如果没有元组满足连接条件，则js=0 一般 0<=js<=1 如果连接属性A为R的键，则js<= 1/ |R| 如果连接属性A为S的键，则js<= 1/ |S| 经过分析可知，一般情况下，连接结果的元组数为： | R|><|CS | = (|R| X |S| )/M 其中M为连接属性A的值域大小。

5.4 代价估算优化 嵌套循环法代价估算 排序归并法代价估算 散列连接法代价估算