第9章关系查询处理和查询优化

9.1关系数据库系统的查询处理第九章关系查询处理和查询优化9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.5小结9.1.1查询处理的步骤RDBMS查询处理可以分为4个阶段：查询分析查询检查查询优化查询执行9.1关系数据库系统的查询处理查询处理的任务是把用户提交给RDBMS的查询语句转换为高效的执行计划。1、查询分析对查询语句进行扫描、词法分析和语法分析，

即判断查询语句是否符合SQL的语法规则。2、查询检查（1）根据数据字典对合法的查询语句进行语义检查。检查语句中的数据库对象（如属性名、关系名）

是否存在和是否有效。（2）根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。（3）将检查通过的查询语句转换成等价的关系代数

表达式。（语法分析树）3、查询优化(QueryOptimization)每个查询都会有许多可供选择的执行策略和操作算法，查询优化就是选择一个高效执行的查询策略。查询优化有多种途径：（1）代数优化将查询语句转换成为相应的关系代数表达式，然后按照一定的规则，改变关系代数表达式的操作次序和组合进行优化，借此来改变基本操作的次序，使查询语句执行起来更有效。这种查询优化仅涉及查询语句本身，而不涉及存取路径，是独立于存取路径的优化。（2）物理优化根据系统提供的存取路径，选择合理的存取路径

和底层操作算法(例如选用顺序搜索或索引进行查找)，

是依赖于存取路径的优化。（3）规则优化查询的优化仅根据启发式规则选择执行的策略。（4）代价估算优化对各种可供选择的策略进行代价估算，从中选用代价最小的执行策略。实际RDBMS中的查询优化器都综合运用了这些优化技术，以获得最好的查询优化效果。4、查询执行依据优化器得到的执行策略生成查询计划，由代码生成器（codegenerator）生成执行这个查询计划的代码。9.1.2实现查询操作的算法示例本节简单介绍实现选择操作和连接操作的几种主要算法。一、选择操作的实现[例１]

Select*fromstudentwhere<条件表达式>考虑<条件表达式>的几种情况：

C1:

无条件；

C2:Sno=‘200215121’；

C3:Sage>20;

C4:Sdept=‘CS’ANDSage>20;对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出。对于小表，这种方法简单有效。对于大表，顺序扫描十分费时，效率很低。1、简单的全表扫描方法如果选择条件中的属性上有索引（例如Ｂ＋树索引或者Ｈash索引），可以用索引扫描方法。通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。2、索引（或散列）扫描方法[例1-C3]以C3为例，Sage>20,并且Sage上有B+树

索引。可以使用B+树索引找到Sage＝20的索引项，以此为入口点在B+树的顺序集上得到Sage>20的所有元组指针，然后通过这些元组指针到student表中检索所有年龄大于20的学生。[例1-C2]以C2为例，Sno=‘200215121’，并且Sno

上有索引。可以使用索引得到Sno为‘200215121’元组的指针，然后通过元组指针在student表中检索到该学生。[例1-C4]以C4为例，Sdept=‘CS’ANDSage>20,

假设Sdept和Sage上都有索引。算法1：分别用上面两种方法分别找到Sdept=‘CS’

的一组元组指针和Sage>20的另一组元组指

针，求这２组指针的交集，再到student表中

检索。算法2：找到Sdept=‘CS’的一组元组的指针，通

过这些元组指针到student表中检索，并

对得到的元组检查另一个选择条件

（Sage>20）是否满足，把满足条件的元组作

为结果输出。二、连接操作的实现连接操作是查询处理中最耗时的操作之一。不失一般性，这里只讨论等值连接（或自然连接）最常用的实现算法。[例２]SELECT*FROMStudent,SC

WHEREStudent.Sno＝SC.Sno算法１：嵌套循环方法这是最简单可行的算法。对外层循环（Student）

的每一个元组（s），检索内层循环（SC）中的每一

个元组（sc），并检查这两个元组在连接属性（Sno）上是否相等。如果满足连接条件，则串接后作为结果输，直到外层循环表中的元组处理完毕为止。算法２：排序－合并方法这也是常用的算法，尤其适合连接的诸表已经排好序的情况。步骤如下：（１）如果连接的表没有排好序，首先对两个表都按

连接属性Sno排序。（２）取Student表中第一个Sno，依次扫描SC表中具

有相同Sno的元组；把它们连接起来（如图）；95001…95002…95003……9500119295001285950013889500229095002380…（３）当扫描到Sno不相同的第一个SC元组时，返回到Student表扫描它的下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来。95001…95002…95003……9500119295001285950013889500229095002380…重复上述步骤直到Student表扫描完毕。这样Student表和SC表只要扫描一遍。当然，如果２个表原来无序，执行时间还要加上对两个表的排序时间。即使这样，对于２个大表，先排序后使用sort-mergejoin方法执行连接，总的时间一般仍会大大减少。算法３：索引连接方法（１）在SC表上建立属性Sno的索引（没有的话）；（２）对Student表中每一个元组，由Sno值通过SC的索引查找相应的SC元组；（３）把这些SC元组和Student表中的元组连接起来。循环执行（２）（３），直到Student表中的元组处理完为止。算法4：HashJoin方法把连接属性Sno作为Hash码，用同一个hash函数

把R和S中的元组散列到同一个hash文件中。第一步，划分阶段，对包含较少元组的表（比如

R）进行一遍处理，把它的元组按hash函数分散到

hash表的桶中；第二步，试探阶段，也称为连接阶段，对另一个

表（S）进行一遍处理，把S的元组散列到适当的hash

桶中，并把元组与桶中所有来自R并与之相匹配的元

组连接起来。备注：上述hash

join算法假设两个表中较小的表在第一阶段后完全放入内存的hash桶中。9.2关系数据库系统的查询优化

9.2.1查询优化概述■关系系统的查询优化既是RDBMS实现的关键技术，也是关系系统的优点所在。它减轻了用户选择存取路径的负担，用户只须提出“干什么”，而不必指出“怎么干”。■查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得最高效率，而且还在于系统可以比用户程序的“优化”做得更好。关系数据库系统的查询优化9.2一、由RDBMS进行查询优化的好处：(1)优化器可以从数据字典中获取许多统计信息，而

用户程序则难以获得这些信息。(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行计划，而程序员

一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术。关系数据库系统的查询优化9.2二、查询优化目标及步骤１、查询优化的总目标选择有效策略，求得给定关系表达式的值，使得查询代价最小（较小）。２、实际系统的查询优化步骤1）

将查询转换成某种内部表示，通常是语法树。2）根据一定的等价变换规则把语法树转换成标准

（优化）形式。3）选择低层的操作算法对于语法树中的每一个操作：（１）计算各种执行算法的执行代价；（２）选择代价小的执行算法；关系数据库系统的查询优化9.24）生成查询计划(查询执行方案)查询计划是由一系列内部操作组成的。代价计算公式如下：▄集中式数据库

►单用户系统总代价=I/O代价+CPU代价

►多用户系统总代价=I/O代价+CPU代价+内存代价一般地，集中式数据库中I/O代价是最主要的。▄分布式数据库总代价=I/O代价+CPU代价+内存代价+通信代价关系数据库系统的查询优化一个实例通过一个简单的例子，说明为什么要进行查询优化。【例３】：求选修了2号课程的学生姓名。

用SQL语言实现如下：

SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;假设学生－课程库中有：1000条Student记录

10000条SC记录

其中，50条选修2号课程记录。关系数据库系统的查询优化9.2系统可用下列3种等价的关系代数表达式来实现这一查询操作。到底哪一种策略效率最优？关系数据库系统的查询优化9.2假设1、外存：

Student：1000条

SC：10000条

其中，选修2号课程：50条2、一个内存块可以装元组:

10个Student,或100个SC

内存中一次可以存放:5块Student元组,1块SC元组,

10块连接结果元组3、读写速度：20块/秒4、连接方法：基于数据块的嵌套循环法关系数据库系统的查询优化9.2①Student×SC

读取总块数=读Student表块数+读SC表遍数*每遍块数

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100块

读数据时间=2100/20=105秒关系数据库系统的查询优化9.2②中间结果写入内存时间（处理时间忽略不计）中间结果大小=1000*10000=107写中间结果时间

=107/10/20=50000秒③бStudent.Sno=SC.Sno∧SC.Cno=‘2’时间读入中间结果时间

（处理时间忽略不计）

读数据时间

=50000秒（结果为50条元组，直接放在内存，不消耗存取时间）④时间：处理时间忽略不计，为０。关系数据库系统的查询优化9.2⑤总时间

=105＋50000＋50000

=100105秒=27.8小时关系数据库系统的查询优化9.2①StudentSC时间读取总块数=1000/10+(1000/(10×5))×(10000/100)=2100块读数据时间=2100/20=105秒②中间结果写入内存时间（处理时间忽略不计）中间结果大小=10000（减少1000倍）写中间结果时间=10000/10/20=50秒

关系数据库系统的查询优化9.2③бSC.Cno=‘2’时间读入中间结果时间

（处理时间忽略不计）

读数据时间

=50秒（结果为50条元组，直接放在内存，不消耗存取时间）④时间：处理时间忽略不计，为０。⑤总时间

=105＋50＋50

=205秒=3.4分钟关系数据库系统的查询优化9.2①б时间

读SC表总块数（一遍）=10000/100=100块

读数据时间=100/20=5秒

（中间结果大小=50条不必写入外存，不耗时

）②自然连接时间 读Student表总块数（一遍）=1000/10=100块

读数据时间=100/20=5秒

③总时间＝5＋5秒＝10秒

关系数据库系统的查询优化9.2三种执行策略中，第三种最优！！！这充分说明了查询优化的必要性！！！为什么？从中我们可以发现什么规律？？？关系数据库系统的查询优化9.2把代数表达式Q1变化成Q2、Q3，即有选择和连接操作时，应当先做选择操作，这样连接的元组就可以大大减少，这就是代数优化。在Q3中，SC表的选择操作算法有全表扫描和索引扫描2种方法，经过初步估算，索引扫描方法较优。同样对于Student和SC的连接，利用Student表上的索引，采用indexjoin代价也较小，这就是物理优化。SQL查询语句代数表达式代数优化物理优化执行转换关系数据库系统的查询优化9.2（局限性）9.3代数优化

9.3.1关系代数表达式等价变换规则代数优化9.3关系代数表达式等价：用相同的关系代替两个表达式

中相应的关系所得到的结果相同。两个关系表达式E1、E2等价，记为：E1≡E2下面介绍常用的关系代数等价变换规则常用的关系代数等价变换规则代数优化—

等价变化规则9.31.连接、笛卡尔积交换律

设E1、E2为关系代数表达式，F为连接运算的条件。

E1×E2≡E2×E1

E1∞E2≡E2∞E1

E1∞E2≡E2∞E1FF2.连接、笛卡尔积的结合律

设E1、E2、E3为关系代数表达式，F1、F2为连接运

算的条件。(E1×E2)×E3≡E1×(E2×E3)(E1∞E2)∞E3≡E1∞(E2∞E3)(E1∞E2)∞E3≡E1∞(E2∞E3)F1F2F1F2

3.投影的串接定律

πA1,A2,…,An(πB1,B2,…,Bm(E))≡πA1,A2,…,An(E)这里，E是关系代数表达式。属性组{A1,A2,…,An}是属性组{B1,B2,…,Bm}的子集。如：πsno(πsno,sname(Stuent))≡πsno(Stuent)代数优化—

等价变化规则9.34.选择的串接定律

σF1(σF2(E))≡σF1∧F2(E)如：σJNO=‘J1’(σPNO=‘P1’(SPJ))≡σJNO=‘J1’∧PNO=‘P1’(SPJ)5.选择与投影的交换律

σF(πA1,A2,…,An(E))≡πA1,A2,…,An

(σF(E))这里，选择条件F只涉及属性A1,A2,…,An。代数优化—

等价变化规则9.3若F中有不属于A1,A2,…,An的属性B1,B2,…,Bm,则πA1,A2,…,An(σF(E))

≡πA1,A2,…,An(σF(πA1,A2,…,An,B1,B2,…,Bm(E)))

6.选择与笛卡尔积的交换律

1）若F中涉及的属性都是E1中的属性,则

σF(E1×E2)≡σF(E1)×E2

2）若F=F1∧F2，且F1只涉及E1中的属性，F2只涉及E2

中的属性，则

σF(E1×E2)≡σF1(E1)×σF2(E2)

代数优化—

等价变化规则9.3

σF(E1×E2)≡σF2(σF1(E1)×E2)

它使部分笛卡尔积先做。3）若F=F1∧F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则7.选择与并的分配律

设E=E1∪E2，E1、E2有相同的属性名

σF(E1∪E2)≡σF(E1)∪σF(E2)8.选择与差的分配律

设E1与E2有相同的属性名

σF(E1-E2)≡σF(E1)-σF(E2)代数优化—

等价变化规则9.39.选择对自然连接的分配律

σF(E1∞E2)≡σF(E1)∞σF(E2)10.投影与笛卡尔积的分配律

设A1,…,An是关系表达式E1的属性，B1,…,Bm是关系表达式E2的属性

πA1,…,An,B1,…,Bm

(E1×E2)≡πA1,…,An(E1)×πB1,…,Bm(E2)代数优化—

等价变化规则9.311.投影与并的分配律

设E1和E2具有相同的属性名

πA1,…,An(E1∪E2)≡πA1,…,An(E1)∪πA1,…,An(E2)9.3.2查询树的启发式优化代数优化—启发式规则9.3本节讨论应用启发式规则的代数优化。这是对关系代数表达式的查询树进行优化的方法。典型的启发式优化规则有：一、选择运算应尽可能先做。

在优化策略中这是最重要、最基本的一条。因为选择运算一般能使计算的中间结果大大减少，所以常常可使执行查询的时间降低几个数量级。二、将投影运算和选择运算同时进行。三、将投影同其前或其后的双目运算结合起来，

没有必要为了去掉某些字段而扫描一遍关系四、将某些选择运算同在其前面要执行的笛

卡尔积运算结合起来成为一个连接运算。五、找出公共子表达式。先求出公共子表达式的值，然后将此值存入中间文件中。代数优化—启发式规则9.3σStudent.Sno=SC.Sno(Student×SC)Student∞SC代数优化—

等价变化规则9.3【例３】：求选修了2号课程的学生姓名。

用SQL语言实现如下：

SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;代数优化示例一、将查询转换成某种内部表示“内部表示”一般采用语法树。结果Project(Sname)Select(SC.Cno=‘2’)join(Student.Sno=SC.Sno)StudentSC

为了进一步使用关系代数表达式的优化准则，须将以上语法树转换成关系代数语法树。πSnameσSC.Cno=‘2’σStudent.Sno=SC.Sno×StudentSC二、将语法树转换成标准优化形式πSnameσSC.Cno=‘2’σStudent.Sno=SC.Sno×StudentSCπSname(Student∞σSC.Cno=‘2’(SC)）9.4物理优化代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径对于一个查询语句有许多存取方案，它们的执行效率不同，仅仅进行代数优化是不够的物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划选择的方法：基于规则的启发式优化基于代价估算的优化两者结合的优化方法9.4.1基于启发式规则的存取路径选择优化一、选择操作的启发式规则:1.对于小关系，使用全表顺序扫描，即使选

择列上有索引对于大关系，启发式规则有：2.对于选择条件是主码＝值的查询查询结果最多是一个元组，可以选择主码索引一般的RDBMS会自动建立主码索引。3.对于选择条件是非主属性＝值的查询，并且选择列

上有索引要估算查询结果的元组数目如果比例较小(<10%)可以使用索引扫描方法否则还是使用全表顺序扫描4.对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引要估算查询结果的元组数目如果比例较小(<10%)可以使用索引扫描方法否则还是使用全表顺序扫描

5.对于用AND连接的合取选择条件如果有涉及这些属性的组合索引,则优先采用组合索引扫描方法如果某些属性上有一般的索引，则可以用［例1-C4］中介绍的索引扫描方法，否则使用全表顺序扫描。

6.对于用OR连接的析取选择条件，一般使用全表顺序扫描二、连接操作的启发式规则：

1.如果2个表都已经按照连接属性排序选用排序-合并方法

2.如果一个表在连接属性上有索引选用索引连接方法

3.如果上面2个规则都不适用，其中一个表较小选用Hashjoin方法

4.可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数(b)较少的表，作为外表(外循环的表)。理由：设连接表R与S分别占用的块数为Br与Bs连接操作使用的内存缓冲区块数为K分配K-1块给外表如果R为外表，则嵌套循环法存取的块数为Br+(Br/K-1)Bs显然应该选块数小的表作为外表9.4.2基于代价的优化

启发式规则优化是定性的选择，适合解释执行的系统解释执行的系统，优化开销包含在查询总开销之中编译执行的系统中查询优化和查询执行是分开的可以采用精细复杂一些的基于代价的优化方法一、统计信息基于代价的优化方法要计算各种操作算法的执行代价，与数据库的状态密切相关数据字典中存储的优化器需要的统计信息：1.对每个基本表该表的元组总数(N)元组长度(l)占用的块数(B)占用的溢出块数(BO)

2.对基表的每个列该列不同值的个数(m)选择率(f)如果不同值的分布是均