第六章 查询处理 6.1 查询处理概述 6.2 代价估算 6.3 基本运算的实现 6.4 表达式计算 6.5 关系表达式转换 6.6 选择执行计划.

Presentation on theme: "第六章 查询处理 6.1 查询处理概述 6.2 代价估算 6.3 基本运算的实现 6.4 表达式计算 6.5 关系表达式转换 6.6 选择执行计划."— Presentation transcript:

1 第六章 查询处理 6.1 查询处理概述 6.2 代价估算 6.3 基本运算的实现 6.4 表达式计算 6.5 关系表达式转换 6.6 选择执行计划

2 6.1 查询处理概述 查询处理是指从数据库中提取数据的一系列活动。主要包括：
6.1 查询处理概述 查询处理是指从数据库中提取数据的一系列活动。主要包括： 将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式 为优化查询而进行各种转换 查询的实际执行 输入：SQL语句 输出：满足查询条件的数据

3 6.1 查询处理概述（2） 查询处理的基本步骤： 1 语法分析与翻译 2 优化 3 执行 语法分析与翻译 关系代数表达式 执行计划 优化器
6.1 查询处理概述（2） 查询处理的基本步骤： 1 语法分析与翻译 2 优化 3 执行 语法分析与翻译 关系代数表达式 执行计划 优化器 查询语句 执行引擎 查询结果 有关数据的统计值 数据

4 6.1 查询处理概述（3） 查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。 查询执行计划：用于计算一个查询的原语序列。 执行原语：加了“如何执行”注释的关系代数运算。

5 6.1 查询处理概述（4） 查询优化的过程： 代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。
6.1 查询处理概述（4） 查询优化的过程： 代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。   查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。

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

7 6.2 代价估算 6.2.1 用于估计代价的目录信息 查询代价的度量

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

9 6.2.1 用于估计代价的目录信息（2） 有关关系的统计信息（续） V(A,r) ：关系r中属性A所具有的不同值的数目。
V(A,r)等于 ПA（r）的大小 若A为关系r的码，则V(A,r) = nr SC(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可以是属性组。

10 6.2.1 用于估计代价的目录信息（3） 有关索引的统计信息： 算法A的代价估计记为EA。
fi ：树形结构(如B＋树)索引i的内部结点的平均扇出。 HTi ：索引i的层数。 对于关系r的属性A上所建的平衡树索引（如B＋树），HTi＝logfi(V(A,r)) 对于散列索引，HTi＝1  LBi ：索引i中最低层索引块数目，即索引叶层的块数。 对于散列索引，Lbi就是索引中的块数。 算法A的代价估计记为EA。

11 6.2.2 查询代价的度量  查询代价：查询处理对各种资源的使用情况 CPU时间 通信开销 一个重要的影响因素：主存中缓冲区的大小M
磁盘存取 （简化为磁盘块传送数） CPU时间 通信开销 一个重要的影响因素：主存中缓冲区的大小M ＊最好的情形，所有的数据可以读入到缓冲区中 ＊最坏的情形，缓冲区只能容纳数目不多的数据块——大约每个关系一块。 

12 6.3 基本运算的实现 每一个基本的代数运算都有多种不同的实现算法。 • 适用于不同的情况 等值条件，范围条件 • 执行代价不同
6.3 基本运算的实现 每一个基本的代数运算都有多种不同的实现算法。 • 适用于不同的情况 等值条件，范围条件 数据是聚集的，数据是非聚集的 相关属性上有索引，相关属性上没有索引 • 执行代价不同

13 6.3 基本运算的实现（2） 6.3.1 选择运算 排序运算 连接运算 其他运算

14 6.3.1 选择运算 全表扫描 方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。 代价：E = br 缺点： 效率低
优点： 对关系的存储方式没有要求，不需要索引。 适用于任何选择条件。

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

16 6.3.1 选择运算.（3） 代价： 利用主索引，等值比较： E = HTi + SC(A，r)/fr  利用辅助索引，等值比较：
利用主索引，非等值比较： E = HTi + br /2 （假设大约一半的元组满足比较条件） 利用辅助索引，非等值比较： E = HTi + LBi /2 + nr /2

17 6.3.1 选择运算（4） 复杂条件的选择 合取：σθ1∧θ2∧…∧θn（r） 析取：σθ1∨θ2∨…∨θn（r）
方法：利用一个索引进行合取选择。 利用组合索引进行合取选择。 利用多维索引进行合取选择。 通过标识符的交集进行合取选择。 通过标识符的并集进行析取选择。

18 6.3.2 排序运算 排序运算在数据库中的重要意义： 内排序：文件较小，整个排序过程都能在内存中进行。
SQL查询可能要求有序的查询结果。 事先对于作为运算对象的关系进行排序，可以提高某些关系运算（例如连接）的执行效率。 内排序：文件较小，整个排序过程都能在内存中进行。 外排序：文件较大，排序过程需要使用外存。

19 6.3.2 排序运算（2） 外部排序-归并算法： （设内存中用于排序的缓冲区页面数为M） 第一阶段，建立多个已排序的子表。
每次读入M块，进行内排序，将长度为M块的已排序子表（共 br /M个）写到外存中。 第二阶段，对已排序子表进行归并（可能需进行若干趟）。

20 6.3.2 排序运算（3） 第一趟：将头M-1个已排序子表的各块逐步读入内存，归并并输出。 第二阶段，对已排序子表进行归并。
…… 已排序子表数目减少到原来的1/（M-1） 第二趟：以第一趟的输出作为输入，重复过程。 第三趟：以第二趟的输出作为输入，重复归并过程 直至归并为一个已排序文件。

21 6.3.2 排序运算（4） 第二阶段第一趟： 将头M-1个已排序子表的每一个的第一块读入内存的一个缓冲页 repeat
在所有缓冲页中的第一个元组中挑选排序码值最小的元组； 把该元组写到第M个缓冲页，并将其从原缓冲页中删除； if 任何一个归并段文件Ri的缓冲页为空并且没有到达Ri末尾 then 读入Ri的下一块到相应的缓冲页； if 第M个缓冲页满 then 将第M个缓冲页写到磁盘，并清空该缓冲页； until 所有的缓冲页均空 将下M-1个已排序子表的每一个的第一块读入内存，归并。 …….

22 6.3.2 排序运算（5） 初始关系 归并段文件 归并段文件 排序结果 第一阶段 第二阶段 第二阶段 创建归并段文件 第一趟归并 第二趟归并

23 6.3.2 排序运算（6） 代价估算： 趟数 = logM-1( br /M ) E = br ( 2 logM-1( br /M ) + 1 )

24 6.3.3 连接运算 二元运算，涉及两个关系。 r |><|  s, r |><| s
重要的运算，多种不同的实现算法。

25 6.3.3 连接运算（2） 自然连接结果集大小的估计： 基于主码、外码连接的情况：结果集的元组数等于外码所在关系的元组数。
一般情况：（假设连接属性A的每个值在关系的元组中等概率出现）， 结果集的元组数为： nr *(ns /V(A,s)) 或 ns *( nr /V(A,r)) 说明： 当V(A,s)与V(A,r)不同时，取两个估计值中较小者。 若两个关系中的元组在连接属性上的取值能匹配上的很少时，上述估计值太高。但实际上这种情况很少发生。

26 6.3.3 连接运算（3） 嵌套循环连接 块嵌套循环连接 索引嵌套循环连接 排序-归并连接 散列连接 复杂连接的实现

27 6.3.3 连接运算（4） 嵌套循环连接 for each元组tr in r do begin for each元组ts in s do
测试元组对(tr,ts)是否满足连接条件θ 如果满足，把tr  ts加到结果中 end

28 6.3.3 连接运算（5） 嵌套循环连接（续） 优点：对参加运算的关系没有要求， 适合于任何连接条件。 代价：
最坏情况（缓冲区只能够容纳每个关系的一个块）： nr  bs + br 或 ns  br + bs 最好情况（内层关系s能完全放在内存中）： bs + br

29 6.3.3 连接运算（6） 块嵌套循环连接：以块的方式循环，以减少块读写次数。 for each块Br of r do
块嵌套循环连接：以块的方式循环，以减少块读写次数。  for each块Br of r do begin for each块Bs of s do begin for each元组tr in Br do begin for each元组ts in Bs do begin 测试元组对(tr,ts)是否满足连接条件θ 如果满足，把tr  ts加到结果中 end

30 6.3.3 连接运算（7） 块嵌套循环连接（续） 优点：对参加运算的关系没有要求， 适合于任何连接条件。 代价：
最坏情况（缓冲区只能够容纳每个关系的一个块）： br * bs + br 或 bs * br + bs 最好情况（内层关系s能完全放在内存中）： bs + br

31 6.3.3 连接运算（8） 块嵌套循环连接（续） 一些改进： 连接属性是内层关系的码时，内层循环可中途跳出。
内层循环轮流做正、反向扫描，重用缓冲区中的数据，以减少磁盘读取。 内层循环利用索引。

32 6.3.3 连接运算（9） 索引嵌套循环连接：在内层循环中利用连接属性上的索引。 for each 元组 tr in r do
begin for each与元组tr满足连接条件的索引项 in s关系在连接属性上的索引do begin 利用索引取到相应的ts 把tr  ts加到结果中 end

33 6.3.3 连接运算（10） 索引嵌套循环连接（续） 代价： 最坏情况（缓冲区只能够容纳关系r的一个块和索引的一个块）：
br + nr * c 或 bs + ns * c 最好情况不必考虑，因为不必采用索引嵌套循环连接方法。 对关系S使用连接条件利用索引进行选择操作的代价

34 6.3.3 连接运算（11） 排序-归并连接 类似于外排序的归并算法的思路，进行连接运算。 前提：两个关系的元组都已按连接属性排好序。
适用于自然连接和等值连接。 a 3 b 1 d 8 13 f 7 m 5 q 6 A G c L N B r s a1 a2 a3 在归并连接中使用的已排序关系

35 6.3.3 连接运算（12） pr := r的第一个元组的地址 ps := s的第一个元组的地址； while (ps≠null and pr≠null) do begin ts := ps所指向的元组； Ss := { ts }； 让ps指向关系s的下一个元组； done := false; while (not done and ps≠null) do begin ts’:= ps所指向的元组； if (ts’[JoinAttrs] = ts[JoinAttrs]) then begin Ss := Ss∪{ ts’}； 让ps指向关系s的下一个元组； end else done := true； 在连接属性上具有相同值的S元组被加入到了Ss中。 Ps指向在连接属性上具有另一个值的S元组。

36 6.3.3 连接运算（13） tr := pr所指向的元组； while (pr≠null and tr[JoinAttrs] < ts[JoinAttrs]) do begin 让pr指向关系r的下一个元组； end while (pr≠null and tr[JoinAttrs] = ts[JoinAttrs]) do begin for each ts in Ss do begin 将ts tr加入结果中；end 让pr指向关系r的下一个元组； 在r中跳过中不能与Ss中的s元组匹配的r元组。 在r中前进，将r元组与Ss中的每个s元组连接，直至r元组中的连接属性值大于s元组的连接属性值。

37 6.3.3 连接运算（14） 在归并连接中使用的已排序关系 a 3 b 1 d 8 13 f 7 m 5 q 6 A G c L N B
pr ps a1 a2 a3 在归并连接中使用的已排序关系 r s

38 6.3.3 连接运算（15） 排序-归并连接（续） 代价：br + bs

39 6.3.3 连接运算（16） 排序-归并连接（续）--- 混合归并连接 思想：利用有序索引，对未排序的关系采用排序-归并连接。
前提：一个关系（r）按连接属性排好序， 另一个关系（S）未排序，但在连接属性上有B+树索引。 方法：r的元组与s的B+树叶结点进行“连接”，（结果的“元组”为r元组与s元组地址） 按s元组地址排序， 访问s的块，完成连接。

40 6.3.3 连接运算（17） 散列连接 适用于自然连接和等值连接。
基本思想:将两个关系按连接属性值划分成有相同散列函数值的元组集合。关系r在一个散列划分中的元组只需要与关系s在对应的划分中的元组相比较。在r和s的每一对划分中进行索引嵌套循环连接（散列索引）。

41 6.3.3 连接运算（18） 散列连接 方法： 确定连接属性上的散列函数h，用于对s元组和r元组进行划分。

42 6.3.3 连接运算（19） 关系的散列划分 1 1 2 2 3 3 4 4 s r 关系r 的划分 关系s 的划分

43 6.3.3 连接运算（20） /*对关系s进行划分*/ 置Hs0 , Hs1 …, Hsmax为空 for each元组ts in s do
begin i := h(ts[JoinAttrs])； Hsi := Hsi ∪{ts}； end /*对关系r进行划分*/ 置Hr0 , Hr1 …, Hrmax为空 for each元组tr in r do begin i := h(tr[JoinAttrs])； Hri := Hri ∪{tr}；

44 6.3.3 连接运算（21） /*对每一分划进行索引嵌套循环连接*/ for i:=0 to max do begin 读Hsi ，在内存中建立其散列索引； for each 元组tr in Hri do begin 检索Hsi的散列索引，定位所有满足 ts[JoinAttrs]=tr[JoinAttrs]的元组ts for each 匹配的元组tsin Hsi do begin tr ts加入结果中；end end 构造用输入关系 查找用输入关系

45 6.3.3 连接运算（22） 散列连接（续） 代价：最基本的情况为 3（br + bs）+2 * max 讨论：
前提：读每个关系一遍就能完成散列划分，构造用输入关系的每一个分划都能完全放入内存。 散列连接（续） 代价：最基本的情况为 3（br + bs）+2 * max 讨论： max的值应选得足够大，使内存中能容纳构造用输入关系的任一分划以及其上的散列索引，max至少应为  bs /M 。显然最好用较小的关系作为构造用输入关系。 当bs > M2时，关系的划分不可能一趟完成，需要递归划分。 当对于某个i， Hsi中的元组数大于内存容量时，需要进行溢出处理，想办法使Hsi变小。 改进：混合散列连接 当M 2> > bs时，充分利用内存空间，减少磁盘I/O的方法。

46 6.3.3 连接运算（23） 复杂连接的实现 合取式：r |><| 1∧  2∧…∧  n s
用一种高效技术计算某一条件下的连接 r|><| 1 s，在生成结果元组时测试其他条件。 析取式：r |><|  1∨  2∨…∨  n s ==> r |><|  1 s  r |><|  2 s … r |><|  n s

47 6.3.4 其他运算 消除重复 投影 并、交、差 外连接 聚集

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

49 6.3.4 其他运算（3） 外连接 例 r ]><| θs 计算 r |><| θS ==> q1
计算连接，然后将适当的元组加到结果中。 例 r ]><| θs 计算 r |><| θS ==> q1 计算 r - ∏R(q1)，在s对应的分量填上空值，加到q1中。

50 6.3.4 其他运算（4） 外连接（续） 修改连接算法 修改嵌套循环连接算法进行左外连接、右外连接。
修改排序-归并连接算法进行全外连接、左外连接、右外连接。 修改散列连接算法进行全外连接、左外连接、右外连接。

51 6.3.4 其他运算（5） 聚集 排序的方法 散列的方法

52 6.4 表达式计算 例 Пcustomer_name（σbalance < 2500(account)|><|customer） Пcustomer_name |><| σbalance < 2500 customer account

53 6.4 表达式计算（2） 实体化的方法 —建立临时关系 代价：各个运算的代价加上中间结果写到磁盘的代价。(nr/fr)
6.4 表达式计算（2） 实体化的方法 —建立临时关系 代价：各个运算的代价加上中间结果写到磁盘的代价。(nr/fr) 流水线的方法 —不建临时关系，一个操作的结果传给下一个操作作为输入。

54 6.4 表达式计算（3） 流水线的实现： 需求驱动 — 在操作树的顶端将数据往上拉。 生产者驱动 — 将数据从操作树的底层往上推
6.4 表达式计算（3） 流水线的实现： 需求驱动 — 在操作树的顶端将数据往上拉。 生产者驱动 — 将数据从操作树的底层往上推 需求驱动的流水线方法比生产者驱动的流水线方法使用更广泛，因为它更容易实现。

55 6.4 表达式计算（4） 说明： 例 若连接运算的左端输入来自流水线， 流水线技术限制了实现操作的可用算法。 则不可用排序-归并连接算法，
6.4 表达式计算（4） 说明： 流水线技术限制了实现操作的可用算法。 例 若连接运算的左端输入来自流水线， 则不可用排序-归并连接算法， 可用索引嵌套循环连接算法。 若连接运算的两端输入均来自流水线，则限制更大。 并非所有情况下都是流水线方法的代价小于实体化方法的代价，因为流水线方法对于运算的实现算法有限制。

56 6.5 关系表达式转换 查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。 查询优化的过程：
6.5 关系表达式转换 查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。 查询优化的过程： 代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。   查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。

57 6.5.1 表达式的等价性 两个表达式等价：产生的结果关系具有相同的属性集和相同的元组集。
表达式的等价性 两个表达式等价：产生的结果关系具有相同的属性集和相同的元组集。 例 Пcustomer_name (σbranch-city=”Brooklyn” (branch|><|(account |><| depositor))) 等价于 Пcustomer_name ((σbranch-city=”Brooklyn” (branch))|><|(account |><| depositor))

58 6.5.1 表达式的等价性（2） σbranch_city=”Brooklyn” Пcustomer_name branch account
表达式的等价性（2） Пcustomer_name σbranch_city=”Brooklyn” branch account depositor

59 等价规则 等价规则 将一个表达式转换为与之等价的另一个表达式的规则。 符号：θ、θ1、θ2等表示谓词， L1、L2、L3等表示属性列表， E、E1、E2等表示关系代数表达式。 关系名r是关系代数表达式的特例，在E可以出现的地方它就可以出现。

60 6.5.2 等价规则 （2） 1. 选择运算的级联：合取选择运算可分解为单个选择运算的序列。 σθ1∧θ2(E)=σ θ1(σ θ2(E))
1. 选择运算的级联：合取选择运算可分解为单个选择运算的序列。 σθ1∧θ2(E)=σ θ1(σ θ2(E)) 2. 选择运算满足交换律 σ θ1(σ θ2(E))=σ θ2(σ θ1(E)) 3. 投影运算的级联：投影运算序列中只有最后一个运算是需要的，其余的可省略。 ∏L1(∏L2(…(∏Ln(E))…))=∏ L1(E)

61 6.5.2 等价规则 （3） 4.选择与笛卡尔积以及theta连接相结合 a. σθ(E1×E2)=E1 |><| θE2
b. σθ1(E1 |><| θ2 E2)= E 1 |><| θ1 ∧ θ2 E2 5. theta连接运算满足交换律： E1 |><| θE2= E2 |><| θE1 自然连接也满足交换律 E1 |><| E2= E2 |><| E1

62 6.5.2 等价规则 （4） 6. 连接运算的结合律 a.自然连接运算满足结合律： (E1 |><| E2) |><| E3= E1 |><| (E2 |><| E3) b. theta连接具有以下方式的结合律： (E1 |><| θ1 E2) |><| θ2 ∧θ3 E3 =E1 |><| θ1 ∧θ3 (E2 |><| θ2 E3) 其中θ2只涉及E2与E3的属性。 由于任意一个条件都可为空，因此笛卡尔积运算也具有结合律。

63 6.5.2 等价规则 （5） 7. 选择运算在下面两个条件下对theta连接运算具有分配律：
a.当选择条件θ0的所有属性只涉及参与连接运算的表达式之一(E1)时： σθ0(E1 |><| θE2)= (σθ0(E1)) |><| θE2 b.当选择条件θ1只涉及E1的属性，选择条件θ2只涉及E2的属性时： σ θ1 ∧ θ2(E1 |><| θE2) = (σ θ1(E1)) |><| θ(σ θ2(E2))

64 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)))

65 6.5.2 等价规则 （7） 9. 集合运算并与交满足交换律 E1∪E2= E2∪E1 E1∩E2= E2∩E1 集合差运算不满足交换律
10.集合运算并与交满足结合律 (E1∪E2)∪E3= E1∪(E2∪E3) (E1∩E2)∩E3= E1∩(E2∩E3) 集合差运算不满足结合律

66 6.5.2 等价规则 （8） 11. 选择运算对并、交、差运算具有分配律： σp（E1 - E2）=σp（E1）- σp（E2）
进一步有： σp（E1 - E2）=σp（E1）- E2 σp（E1∩E2）=σp（E1）∩E2 但对于∪不成立。

67 6.5.2 等价规则 （9） 12. 投影运算对并运算具有分配律 ∏L(E1∪E2)= (∏L(E1) )∪(∏L(E2) )
最小的等价规则集：若一个等价规则集中的任何一条规则都不能由其它规则结合起来导出，则称该等价规则集为最小的等价规则集。

68 6.5.2 等价规则 （10） 例 Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000 (branch |><| (account |><| depositor))) 规则6 a ==> Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000 ((branch |><| account) |><| depositor)) 规则7 a ==> Пcustomer-name((σbranch_city=”Brooklyn”∧balance>1000 (branch |><| account)) |><| depositor)

69 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)

70 6.5.2等价规则 （12） 说明：  规则只说明两个表达式等价，并不说明哪一个更好。  连接的次序很重要，好的连接次序序列产生小的中间结果。  规则的使用会产生大量的等价表达式，优化器要采用适当的技术来减少所产生的表达式的数量。

71 6.6 选择执行计划 关系代数表达式的基础上，执行计划进一步说明：  每个运算的实现算法  各运算的执行顺序  是否采用流水线技术 注意：每个运算的最小代价算法组合起来不一定是整个表达式的最佳算法，必须考虑各个运算之间的相互作用。

72 6.6 选择执行计划（2） 两类主要的优化算法：  基于代价的方法  启发式方法

73 6.6.1基于代价的优化 通过使用等价规则为给定的查询语句产生一系列查询执行计划，并选择其中代价最小或接近最小的。 等价于给定查询的不同查询计划可能很多，因此优化的代价太大，所以：  采用一些巧妙的技术来减少需要考虑的表达式的数目。  采用启发式方法来减少需考虑的表达式的数目。

74 6.6.1基于代价的优化（2） 减少需要考虑的表达式数目的技术 只考虑左深连接次序 r1 r2 r3 r4 r5 左深连接树 非左深连接树

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

76 6.6.2 启发式优化 运用启发式规则，对关系代数表达式进行等价变换。 常用的规则：  尽早进行选择运算  尽早进行投影运算  避免进行笛卡尔积运算  ………..

77 6.6.2 启发式优化（2） 启发式优化的步骤: 1.将合取选择分解为单个选择运算的序列。这有助于将选择运算往查询树下层移。
2.把选择运算在查询树上下推到最早可能执行的地方。 例如，尽可能将σθ(r|><| s)转换成σθ ( r) |><|s或r|><|σθ(s) 3. 通过使用|><|的结合律，重新组织查询树，使得具有限制比较严格的选择运算的叶结点关系首先执行。 4.将跟有选择条件的笛卡尔积运算替换成连接运算。 5.将投影属性加以分解并在查询树上尽可能往下推。必要时可以引入新的投影运算。 6.识别那些可用流水方式执行其运算的子树，并采用流水线方法执行之。

78 6.6.3 嵌套子查询的优化 复杂嵌套子查询的优化相当困难，许多优化器对于嵌套子查询的优化仅做了少量的工作。 from borrower
例 select customer-name from borrower where exists ( select * from depositor where depositor.customer-name = borrower.customer-name ) SQL概念上按以下方式执行查询：计算外层查询的from子句中的关系的笛卡尔积，然后对该笛卡尔积的每个元组用位于where子句中的谓词进行测试。本例中，即测试子查询运算结果是否为空。

79 6.6.3 嵌套子查询的优化（2） 相关执行:概念上将位于where子句中的嵌套子查询处理成获取参数并且返回单独值或值的集合（可能为空集）的函数。参数是嵌套子查询中用到的外层查询的变量（称作相关变量）。 相关执行效率不高，因为对于外层查询的每一个元组都要进行一次内层子查询的运算，从而可能导致大量的随机磁盘I/O操作。 去除相关：用一个具有连接的查询（可能使用临时关系）去替代嵌套子查询。 有效的连接算法有助于避免昂贵的随机I/O操作。

80 6.6.3 嵌套子查询的优化（3） from borrower where exists ( select * from depositor
例 select customer-name from borrower where exists ( select * from depositor where depositor.customer-name = borrower.customer-name )  select customer-name from borrower, depositor where depositor.customer-name = borrower.customer-name

81 6.6.3 嵌套子查询的优化（4） 更复杂的情况：不能将嵌套子查询关系直接移入外层查询的from子句里，需要先建立一个包含嵌套查询结果（但没有用取自外层查询的相关变量进行选择操作）的临时关系，然后将这个临时表与外层查询进行连接。

82 6.6.3 嵌套子查询的优化（5） from borrower where loan-number > 1000
例 select customer-name from borrower where loan-number > 1000 and exists ( select * from depositor where depositor.customer-name = borrower.customer-name and account-number <1000) ==〉create table t1 as select distinct customer-name where account-number <1000 select customer-name form borrower, t1 and t1.customer-name = borrower.customer-name

83 6.6.3 嵌套子查询的优化（6） 当嵌套子查询使用聚集、或嵌套子查询的结果用于等值测试、或嵌套子查询与外部查询的关联条件是not exists时，去除相关操作会更复杂。

84 课程实习 目的： 1. 了解数据库管理系统底层的存储管理与数据管理部件，它所提供的接口。 2. 进行查询处理系统设计与实现的实际训练。 任务： 1. 设计与实现一个简化的查询处理系统，对SQL语句进行分析处理，优化，产生执行结果。 2. 分析、比较不同的查询执行计划的执行性能。

85 课程实习（2） 基础环境： COBASE核心 —— 存储管理和数据管理子系统 SQL语言 翻译处理 存储管理 与数据管理 SQL语句
单元组接口 存储管理 与数据管理

86 课程实习（3） 说明： 1．二至三人一组，自由结合。 2．适当控制系统的规模和难度，只处理有限形式的SQL查询。 3．集中做与查询处理密切相关的工作，简化其他部分。 4．注意中间结果，和比较、分析结果的输出，充分展示你的工作的特色。

87 课程实习（4） 提交： 1．查询处理系统规格定义 2．设计说明书 3．使用说明书 4．比较分析和总结报告 5．可运行的系统