数据库原理与技术

第六章查询处理6.1查询处理概述

6.2代价估算

6.3基本运算的实现

6.4表达式计算

6.5关系表达式转换

6.6选择执行计划

6.1查询处理概述查询处理是指从数据库中提取数据的一系列活动。主要包括：

将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式

为优化查询而进行各种转换

查询的实际执行

输入：SQL语句输出：满足查询条件的数据

6.1查询处理概述（2）查询处理的基本步骤：

1语法分析与翻译

2优化

3执行语法分析与翻译关系代数表达式执行计划优化器查询语句执行引擎查询结果有关数据的统计值数据6.1查询处理概述（3）查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。查询执行计划：用于计算一个查询的原语序列。执行原语：加了“如何执行”注释的关系代数运算。6.1查询处理概述（4）查询优化的过程：代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。

查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。

6.1查询处理概述（5）对于关系数据库系统，查询优化是：挑战：必须进行好的优化，才有可接受的性能机会：关系表达式的语义层次高，提供了优化的可能性。优化器有理由比程序员做得更好：＊优化器具有丰富的可使用的信息＊当数据库发生变化时优化器容易再次进行优化＊优化器能够对多种实现策略逐一进行考虑＊优化器集中了最优秀的程序员的智慧和经验

6.2代价估算

6.2.1用于估计代价的目录信息

6.2.2查询代价的度量

6.2.1用于估计代价的目录信息

有关关系的统计信息nr：关系r中的元组数目br：含有关系r的元组的块数目sr：关系r中一个元组的大小fr：关系r的块因子，即一个块中能存放的关系r的元组数若假定关系r的元组物理上存于同一文件中，则：br=

nr/fr

6.2.1用于估计代价的目录信息（2）有关关系的统计信息（续）V(A,r)：关系r中属性A所具有的不同值的数目。

V(A,r)等于ПA（r）的大小若A为关系r的码，则V(A,r)=nrSC(A,r)：关系r的属性A的选择基数。表示关系r中满足属性A上的一个等值条件的平均元组数。若A为r的码属性，则SC(A,r)＝1

若A为非码属性，并假定V(A,r)个不同的值在元组上均匀分布，则SC(A,r)＝(nr/V(A,r))。说明：V(A,r)与SC(A,r)中的A可以是属性组。

6.2.1用于估计代价的目录信息（3）

有关索引的统计信息：

fi

：树形结构(如B＋树)索引i的内部结点的平均扇出。

HTi

：索引i的层数。对于关系r的属性A上所建的平衡树索引（如B＋树），HTi＝

logfi(V(A,r))

对于散列索引，HTi＝1

LBi

：索引i中最低层索引块数目，即索引叶层的块数。对于散列索引，Lbi就是索引中的块数。

算法A的代价估计记为EA。

6.2.2查询代价的度量查询代价：查询处理对各种资源的使用情况

磁盘存取（简化为磁盘块传送数）

CPU时间

通信开销

一个重要的影响因素：主存中缓冲区的大小M＊最好的情形，所有的数据可以读入到缓冲区中＊最坏的情形，缓冲区只能容纳数目不多的数据块——大约每个关系一块。

6.3基本运算的实现

每一个基本的代数运算都有多种不同的实现算法。

•适用于不同的情况

等值条件，范围条件数据是聚集的，数据是非聚集的相关属性上有索引，相关属性上没有索引

•执行代价不同

6.3基本运算的实现（2）6.3.1选择运算

6.3.2排序运算

6.3.3连接运算

6.3.4其他运算

6.3.1选择运算全表扫描

方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。代价：E=br

缺点：效率低

优点：

对关系的存储方式没有要求，不需要索引。适用于任何选择条件。

6.3.1选择运算（2）索引扫描

条件：表在选择条件的属性上建有索引。方法：访问索引，根据索引项的指示去访问数据元组。无序索引：访问满足等值条件的元组有序索引：访问满足范围查找条件的一系列元组。

6.3.1选择运算.（3）代价：利用主索引，等值比较：

E=HTi+

SC(A，r)/fr

利用辅助索引，等值比较：

E=HTi+SC（A，r）利用主索引，非等值比较：

E=HTi+br/2

（假设大约一半的元组满足比较条件）利用辅助索引，非等值比较：

E=HTi+LBi/2+nr/2

6.3.1选择运算（4）复杂条件的选择合取：σθ1∧θ2∧…∧θn（r）析取：σθ1∨θ2∨…∨θn（r）

方法：利用一个索引进行合取选择。利用组合索引进行合取选择。利用多维索引进行合取选择。通过标识符的交集进行合取选择。通过标识符的并集进行析取选择。

6.3.2排序运算排序运算在数据库中的重要意义：SQL查询可能要求有序的查询结果。

事先对于作为运算对象的关系进行排序，可以提高某些关系运算（例如连接）的执行效率。

内排序：文件较小，整个排序过程都能在内存中进行。

外排序：文件较大，排序过程需要使用外存。

6.3.2排序运算（2）外部排序-归并算法：（设内存中用于排序的缓冲区页面数为M）第一阶段，建立多个已排序的子表。

每次读入M块，进行内排序，将长度为M块的已排序子表（共

br/M

个）写到外存中。

第二阶段，对已排序子表进行归并（可能需进行若干趟）。6.3.2排序运算（3）第二阶段，对已排序子表进行归并。

第一趟：将头M-1个已排序子表的各块逐步读入内存，归并并输出。将下M-1个已排序子表的各块逐步读入内存，归并并输出。

……

已排序子表数目减少到原来的1/（M-1）

第二趟：以第一趟的输出作为输入，重复过程。第三趟：以第二趟的输出作为输入，重复归并过程

……

直至归并为一个已排序文件。6.3.2排序运算（4）

第二阶段第一趟：

将头M-1个已排序子表的每一个的第一块读入内存的一个缓冲页

repeat

在所有缓冲页中的第一个元组中挑选排序码值最小的元组； 把该元组写到第M个缓冲页，并将其从原缓冲页中删除；

if任何一个归并段文件Ri的缓冲页为空并且没有到达Ri末尾

then读入Ri的下一块到相应的缓冲页；

if第M个缓冲页满

then将第M个缓冲页写到磁盘，并清空该缓冲页；

until 所有的缓冲页均空将下M-1个已排序子表的每一个的第一块读入内存，归并。

…….6.3.2排序运算（5）

初始关系

归并段文件归并段文件

排序结果第一阶段第二阶段第二阶段创建归并段文件第一趟归并第二趟归并6.3.2排序运算（6）代价估算：趟数=

logM-1(br/M)

E=br(2

logM-1(br/M)

+1)

6.3.3连接运算二元运算，涉及两个关系。

r|><|

s,r|><|s

重要的运算，多种不同的实现算法。

6.3.3连接运算（2）

自然连接结果集大小的估计：

基于主码、外码连接的情况：结果集的元组数等于外码所在关系的元组数。

一般情况：（假设连接属性A的每个值在关系的元组中等概率出现），结果集的元组数为：

nr*(ns/V(A,s))或ns*(

nr/V(A,r))说明：

当V(A,s)与V(A,r)不同时，取两个估计值中较小者。若两个关系中的元组在连接属性上的取值能匹配上的很少时，上述估计值太高。但实际上这种情况很少发生。6.3.3连接运算（3）嵌套循环连接块嵌套循环连接索引嵌套循环连接排序-归并连接散列连接复杂连接的实现

6.3.3连接运算（4）嵌套循环连接

foreach元组trinrdobeginforeach元组tsinsdobegin

测试元组对(tr,ts)是否满足连接条件θ

如果满足，把tr

ts加到结果中

endend6.3.3连接运算（5）嵌套循环连接（续）优点：对参加运算的关系没有要求，适合于任何连接条件。代价：最坏情况（缓冲区只能够容纳每个关系的一个块）：

nr

bs+br或ns

br+bs

最好情况（内层关系s能完全放在内存中）：

bs+br

6.3.3连接运算（6）块嵌套循环连接：以块的方式循环，以减少块读写次数。

foreach块Brofrdobeginforeach块Bsofsdobeginforeach元组trinBrdobeginforeach元组tsinBsdo

begin

测试元组对(tr,ts)是否满足连接条件θ

如果满足，把tr

ts加到结果中

endendendend6.3.3连接运算（7）

块嵌套循环连接（续）优点：对参加运算的关系没有要求，适合于任何连接条件。代价：最坏情况（缓冲区只能够容纳每个关系的一个块）：

br*bs+br或bs*br+bs

最好情况（内层关系s能完全放在内存中）：

bs+br

6.3.3连接运算（8）块嵌套循环连接（续）一些改进：

连接属性是内层关系的码时，内层循环可中途跳出。内层循环轮流做正、反向扫描，重用缓冲区中的数据，以减少磁盘读取。内层循环利用索引。

6.3.3连接运算（9）索引嵌套循环连接：在内层循环中利用连接属性上的索引。

foreach元组trinrdobeginforeach与元组tr满足连接条件的索引项

ins关系在连接属性上的索引dobegin利用索引取到相应的ts

把tr

ts加到结果中

endend

6.3.3连接运算（10）索引嵌套循环连接（续）代价：最坏情况（缓冲区只能够容纳关系r的一个块和索引的一个块）：

br+nr*c

或bs+ns*c

最好情况不必考虑，因为不必采用索引嵌套循环连接方法。对关系S使用连接条件利用索引进行选择操作的代价6.3.3连接运算（11）排序-归并连接类似于外排序的归并算法的思路，进行连接运算。前提：两个关系的元组都已按连接属性排好序。适用于自然连接和等值连接。a3b1d8d13f7m5q6aAaGcLdNmB

rsa1a2a1a3在归并连接中使用的已排序关系rs6.3.3连接运算（12）pr:=r的第一个元组的地址ps:=s的第一个元组的地址；while(ps≠nullandpr≠null)dobegints:=ps所指向的元组；Ss:={ts}； 让ps指向关系s的下一个元组；done:=false; while(notdoneandps≠null)dobegints’:=ps所指向的元组；

if(ts’[JoinAttrs]=ts[JoinAttrs])thenbeginSs:=Ss∪{ts’}； 让ps指向关系s的下一个元组；

endelsedone:=true；

end在连接属性上具有相同值的S元组被加入到了Ss中。Ps指向在连接属性上具有另一个值的S元组。6.3.3连接运算（13）tr:=pr所指向的元组；

while(pr≠nullandtr[JoinAttrs]<ts[JoinAttrs])do begin

让pr指向关系r的下一个元组；

tr:=pr所指向的元组；

end while(pr≠nullandtr[JoinAttrs]=ts[JoinAttrs])do beginforeachtsinSsdo begin将tstr加入结果中；end

让pr指向关系r的下一个元组；

tr:=pr所指向的元组；

endend在r中跳过中不能与Ss中的s元组匹配的r元组。在r中前进，将r元组与Ss中的每个s元组连接，直至r元组中的连接属性值大于s元组的连接属性值。

6.3.3连接运算（14）

在归并连接中使用的已排序关系

a3b1d8d13f7m5q6aAaGcLdNmBprpsa1a2a1a3在归并连接中使用的已排序关系rs6.3.3连接运算（15）排序-归并连接（续）代价：br+bs6.3.3连接运算（16）排序-归并连接（续）---混合归并连接思想：利用有序索引，对未排序的关系采用排序-归并连接。前提：一个关系（r）按连接属性排好序，另一个关系（S）未排序，但在连接属性上有B+树索引。方法：r的元组与s的B+树叶结点进行“连接”，（结果的“元组”为r元组与s元组地址）按s元组地址排序，

访问s的块，完成连接。

6.3.3连接运算（17）散列连接适用于自然连接和等值连接。

基本思想:将两个关系按连接属性值划分成有相同散列函数值的元组集合。关系r在一个散列划分中的元组只需要与关系s在对应的划分中的元组相比较。在r和s的每一对划分中进行索引嵌套循环连接（散列索引）。6.3.3连接运算（18）散列连接方法：确定连接属性上的散列函数h，用于对s元组和r元组进行划分。确定连接属性上的散列函数h’，用于逐个对每一划分中的s元组构造散列索引，再对同一划分中的r元组查找散列索引，同时进行连接。

6.3.3连接运算（19）关系的散列划分rs关系r的划分关系s的划分01234012346.3.3连接运算（20）

/*对关系s进行划分*/

置Hs0,

Hs1…,Hsmax为空

foreach元组tsinsdobegini:=h(ts[JoinAttrs])；

Hsi

:=Hsi

∪{ts}；

end/*对关系r进行划分*/置Hr0,

Hr1…,Hrmax为空

foreach元组trinrdobegini:=h(tr[JoinAttrs])；

Hri

:=Hri

∪{tr}；

end6.3.3连接运算（21）/*对每一分划进行索引嵌套循环连接*/ fori:=0tomaxdobegin读Hsi

，在内存中建立其散列索引；

foreach元组trinHri

dobegin检索Hsi的散列索引，定位所有满足

ts[JoinAttrs]=tr[JoinAttrs]的元组ts foreach匹配的元组tsinHsi

dobegintr

ts加入结果中；end end end构造用输入关系查找用输入关系6.3.3连接运算（22）散列连接（续）

代价：最基本的情况为3（br+bs）+2*max

讨论：

max的值应选得足够大，使内存中能容纳构造用输入关系的任一分划以及其上的散列索引，max至少应为

bs/M

。显然最好用较小的关系作为构造用输入关系。当bs>M2时，关系的划分不可能一趟完成，需要递归划分。当对于某个i，Hsi中的元组数大于内存容量时，需要进行溢出处理，想办法使Hsi变小。改进：混合散列连接当M

2>

>bs时，充分利用内存空间，减少磁盘I/O的方法。前提：读每个关系一遍就能完成散列划分，构造用输入关系的每一个分划都能完全放入内存。6.3.3连接运算（23）复杂连接的实现合取式：r|><|

1∧

2∧…∧

ns

用一种高效技术计算某一条件下的连接r|><|

1s，在生成结果元组时测试其他条件。析取式：r|><|

1∨

2∨…∨

ns==>r|><|

1s

r|><|

2s…

r|><|

ns

6.3.4其他运算

消除重复

投影

并、交、差

外连接

聚集

6.3.4其他运算（2）消除重复用排序的方法用散列的方法投影投影，消除重复并、交、差排序的方法

散列的方法6.3.4其他运算（3）外连接计算连接，然后将适当的元组加到结果中。例r]><|θs

计算r|><|θS==>q1

计算r-∏R(q1)，在s对应的分量填上空值，加到q1中。

6.3.4其他运算（4）外连接（续）修改连接算法修改嵌套循环连接算法进行左外连接、右外连接。修改排序-归并连接算法进行全外连接、左外连接、右外连接。修改散列连接算法进行全外连接、左外连接、右外连接。6.3.4其他运算（5）聚集排序的方法散列的方法6.4表达式计算

例Пcustomer_name（σbalance<2500(account)|><|customer）

Пcustomer_nameσbalance<2500customeraccount|><|6.4表达式计算（2）

实体化的方法—建立临时关系代价：各个运算的代价加上中间结果写到磁盘的代价。(nr/fr)

流水线的方法—不建临时关系，一个操作的结果传给下一个操作作为输入。6.4表达式计算（3）流水线的实现：需求驱动—在操作树的顶端将数据往上拉。生产者驱动—将数据从操作树的底层往上推需求驱动的流水线方法比生产者驱动的流水线方法使用更广泛，因为它更容易实现。6.4表达式计算（4）说明：流水线技术限制了实现操作的可用算法。

例若连接运算的左端输入来自流水线，则不可用排序-归并连接算法，

可用索引嵌套循环连接算法。若连接运算的两端输入均来自流水线，则限制更大。并非所有情况下都是流水线方法的代价小于实体化方法的代价，因为流水线方法对于运算的实现算法有限制。

6.5关系表达式转换

查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。

查询优化的过程：代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。

查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。6.5.1表达式的等价性

两个表达式等价：产生的结果关系具有相同的属性集和相同的元组集。

例

Пcustomer_name

(σbranch-city=”Brooklyn”

(branch|><|(account|><|depositor)))

等价于

Пcustomer_name

((σbranch-city=”Brooklyn”

(branch))|><|(account|><|depositor))

6.5.1表达式的等价性（2）

Пcustomer_nameσbranch_city=”Brooklyn”branchaccountdepositorПcustomer_nameσbranch_city=”Brooklyn”branchaccountdepositor6.5.2等价规则等价规则

将一个表达式转换为与之等价的另一个表达式的规则。符号：θ、θ1、θ2等表示谓词，

L1、L2、L3等表示属性列表，

E、E1、E2等表示关系代数表达式。关系名r是关系代数表达式的特例，在E可以出现的地方它就可以出现。

6.5.2等价规则（2）1.选择运算的级联：合取选择运算可分解为单个选择运算的序列。

σθ1∧θ2(E)=σθ1(σθ2(E))2.选择运算满足交换律

σθ1(σθ2(E))=σθ2(σθ1(E))3.投影运算的级联：投影运算序列中只有最后一个运算是需要的，其余的可省略。∏L1(∏L2(…(∏Ln(E))…))=∏L1(E)

6.5.2等价规则（3）

4.选择与笛卡尔积以及theta连接相结合

a.σθ(E1×E2)=E1|><|θE2

b.σθ1(E1|><|θ2

E2)=E1|><|θ1∧θ2

E25.theta连接运算满足交换律：

E1|><|θE2=E2|><|θE1

自然连接也满足交换律

E1|><|

E2=E2|><|

E16.5.2等价规则（4）6.连接运算的结合律

a.自然连接运算满足结合律：

(E1|><|

E2)

|><|

E3=E1

|><|

(E2|><|

E3)

b.theta连接具有以下方式的结合律：

(E1|><|θ1

E2)|><|θ2∧θ3E3

=E1|><|θ1∧θ3(E2|><|θ2E3)

其中θ2只涉及E2与E3的属性。由于任意一个条件都可为空，因此笛卡尔积运算也具有结合律。6.5.2等价规则（5）

7.选择运算在下面两个条件下对theta连接运算具有分配律：a.当选择条件θ0的所有属性只涉及参与连接运算的表达式之一(E1)时：

σθ0(E1|><|θE2)=(σθ0(E1))|><|θE2b.当选择条件θ1只涉及E1的属性，选择条件θ2只涉及E2的属性时：

σθ1∧θ2(E1|><|θE2)=(σθ1(E1))|><|θ(σθ2(E2))6.5.2等价规则（6）8.投影运算对theta连接运算具有分配律：a.令L1、L2分别是E1、E2的属性。假设连接条件θ只涉及L1∪L2中的属性，则：∏L1∪L2

(E1|><|θE2)=(∏L1(E1))

|><|θ(∏L2(E2))b.考虑连接E1|><|θE2。令L1、L2分别是E1、E2的属性；令L3是E1中出现在连接条件θ中但不在L1∪L2中的属性；令L4是E2中出现在连接条件θ中但不在L1∪L2中的属性。那么：∏L1∪L2

(E1|><|θE2)=∏L1∪L2

((∏L1∪L3(E1))

|><|θ(∏L2∪L4(E2)))

6.5.2等价规则（7）

9.集合运算并与交满足交换律

E1∪E2=E2∪E1E1∩E2=E2∩E1

集合差运算不满足交换律10.集合运算并与交满足结合律

(E1∪E2)∪E3=E1∪(E2∪E3)(E1∩E2)∩E3=E1∩(E2∩E3)

集合差运算不满足结合律6.5.2等价规则（8）

11.选择运算对并、交、差运算具有分配律：

σp（E1-E2）=σp（E1）-σp（E2）

σp（E1∪E2）=σp（E1）∪σp（E2）

σp（E1∩E2）=σp（E1）∩σp（E2）

进一步有：

σp（E1-E2）=σp（E1）-E2σp（E1∩E2）=σp（E1）∩E2

但对于∪不成立。

6.5.2等价规则（9）

12.投影运算对并运算具有分配律∏L(E1∪E2)=(∏L(E1))∪(∏L(E2))

最小的等价规则集：若一个等价规则集中的任何一条规则都不能由其它规则结合起来导出，则称该等价规则集为最小的等价规则集。

6.5.2等价规则（10）

例Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000

(branch|><|(account|><|depositor)))

规则6a==>Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000

((branch|><|account)|><|depositor))规则7a==>Пcustomer-name((σbranch_city=”Brooklyn”∧balance>1000

(branch|><|account))|><|depositor)6.5.2等价规则（11）Пcustomer-name((σbranch-city=”Brooklyn”∧balance>1000(branch|><|account))|><|depositor)规则7b==>Пcustomer-name((σbranch-city=”Brooklyn”(branch)|><|σbalance>1000(account))|><|depositor)规则8b==>Пcustomer-name(Пaccount-number(σbranch-city=”Brooklyn”(branch)|><|σbalance>1000(account))|><|depositor)

6.5.2等价规则（12）说明：

规则只说明两个表达式等价，并不说明哪一个更好。

连接的次序很重要，好的连接次序序列产生小的中间结果。

规则的使用会产生大量的等价表达式，优化器要采用适当的技术来减少所产生的表达式的数量。

6.6选择执行计划关系代数表达式的基础上，执行计划进一步说明：

每个运算的实现算法各运算的执行顺序是否采用流水线技术注意：每个运算的最小代价算法组合起来不一定是整个表达式的最佳算法，必须考虑各个运算之间的相互作用。6.6选择执行计划（2）两类主要的优化算法：

基于代价的方法

启发式方法6.6.1基于代价的优化

通过使用等价规则为给定的查询语句产生一系列查询执行计划，并选择其中代价最小或接近最小的。

等价于给定查询的不同查询计划可能很多，因此优化的代价太大，所以：

采用一些巧妙的技术来减少需要考虑的表达式的数目。

采用启发式方法来减少需考虑的表达式的数目。

6.6.1基于代价的优化（2）减少需要考虑的表达式数目的技术只考虑左深连接次序

r1r2r3r4r5左深连接树r1r2r3r4r5非左深连接树6.6.1基于代价的优化（3）找多个关系的最佳连接顺序时，不是简单地考虑所有的可能顺序，而是为每个子集找出最佳连接顺序，这样能大大减少需要检查的连接顺序的总数。如果检查一个表达式的某部分后发现这一部分的最小代价已经比先前已检查过的整个表达式的执行计划的最小代价要大，则可以终止对这个表达式的检查。如果发现计算一个子表达式的代价最小的方法所用的代价比先前已检查过的整个表达式的最小代价执行计划所需代价还大，则没有必要对包含该子表达式的任何完整表达式进行检查。6.6.2启发式优化运用启发式规则，对关系代数表达式进行等价变换。常用的规则：

尽早进行选择运算

尽早进行投影运算

避免进行笛卡尔积运算

………..

6.6.2启发式优化（2）

启发式优化的步骤:

1.将合取选择分解为单个选择运算的序列。这有助于将选择运算往查询树下层移。

2.把选择运算在查询树上下推到最早可能执行的地方。

例如，尽可能将σθ(r|><|s)转换成σθ(

r)|><|s或r|><|σθ(s)

3.

通过使用|><|的结合律，重新组织查询树，使得具有限制比较严格的选择运算的叶结点关系首先执行。

4.将跟有选择条件的笛卡尔积运算替换成连接运算。

5.将投影属性加以分解并在查询树上尽可能往下推。必要时可以引入新的投影运算。

6.识别那些可用流水方式执行其运算的子树，并采用流水线方法执行之。

6.6.3嵌套子查询的优化

复杂嵌套子查询的优化相当困难，许多优化器对于嵌套子查询的优化仅做了少量的工作。

例selectcustomer-name from

borrower whereexists(select*

from

depositor

where

depositor.customer-name =borrower.customer-name)SQL概念上按以下方式执行查询：计算外层查询的from子句中的关系的笛卡尔积，然后对该笛卡尔积的每个元组用位于where子句中的谓词进行测试。本例中，即测试子查询运算结果是否为空。6.6.3嵌套子查询的优化（2）