外排序与执行

一、外部 Merge 排序

1.1 从二路归并到多路归并

外部排序的基本形式是最基本的二路外部归并排序：每次只归并两个 run，需要 3 个缓冲页，其中 2 个输入缓冲区、1 个输出缓冲区。

如果内存中有 $B$ 个 pages，就没有必要只做二路归并，而是可以做 $B-1$ 路归并：

1. Pass 0：一次性读入 $B$ 个页，在内存中排序后写回磁盘，形成初始 run
2. Pass 1,2,…：用 $B-1$ 个 buffer page 作为输入缓冲区
3. 最后 1 个 buffer page 作为输出缓冲区
4. 每一趟最多同时归并 $B-1$ 个 run

外排序中真正贵的是磁盘 I/O。内存越大，一次能归并的 run 越多，扫描磁盘的趟数就越少。

算法大致如下：

1
2
3
4
5
6
7
8
9
Proc exsort(file)
  Read B pages into memory, sort them, write out a run
  While the number of runs at end of previous pass > 1
    while there are runs to be merged from previous pass
      choose next B-1 runs
      read each run into an input buffer, one page at a time
      merge the runs and write to the output buffer
      force output buffer to disk one page at a time
endproc

1.2 I/O 代价分析

设文件共有 $N$ 页，内存缓冲区大小为 $B$ 页。

Pass 0 之后初始 run 的个数为：

之后每一趟最多将 $B-1$ 个 run 归并为 1 个 run，因此归并趟数为：

再加上 Pass 0，数据总扫描遍数为：

每一遍扫描都要读一遍、写一遍，所以总 I/O 代价为：

公式里最关键的是底数 $B-1$。缓冲区稍微变大一点，归并趟数可能就少一整趟，而每少一趟就是少 $2N$ 次 I/O。

二、外排序的优化

2.1 减少初始 run 的个数

在 Pass 0 中，可以用一些技巧让初始 run 的平均长度从 $B$ 页提高到约 $2B$ 页。

基本做法：

• 1 页作为输入缓冲区
• 1 页作为输出缓冲区
• 剩下 $B-2$ 页作为当前排序缓冲区
• 先将数据调入当前排序缓冲区并排序
• 不断输出大于当前输出值的最小记录，同时从输入缓冲区补充新数据
• 当当前缓冲区里没有可选数据时，这个 run 结束

这个思想本质上类似“置换选择”：不是机械地每 $B$ 页切一个 run，而是尽量利用后续输入数据延长当前 run。

例如数据到来顺序为：

1
3, 10, 5, 2, 8, 12, 4

在当前缓冲区中先排序，输出 3 后，如果新进入的数据还能接在当前 run 后面，就继续输出；如果太小，例如 2 已经小于当前 run 的输出位置，就只能留到下一个 run。

2.2 块 I/O

如果一次只读写一个 page，磁头移动和 I/O 调度的开销仍然很大。实际系统中常用块 I/O：

• 以一个 block 为单位读写
• 一个 block 由若干 page 组成
• 连续读写可以减少磁头移动次数，提高单页读写速度

设：

• $B$ 是总缓冲页数
• $b$ 是一个块中包含的 page 数

由于每个输入 run 都要分配一个块缓冲区，输出也要分配一个块缓冲区，所以一次最多归并：

个 run。

如果初始 run 的平均长度已经优化到 $2B$，则初始 run 数约为：

总扫描遍数变为：

2.3 双缓冲区

排序总时间不仅包括 I/O 时间，也包括 CPU 排序和归并比较的时间。前面的基本方法中，CPU 计算和 I/O 往往是串行的。

双缓冲区的思想是：

• 每个 run 分配两个缓冲区
• 一个缓冲区进行 I/O
• 另一个缓冲区同时供 CPU 处理
• 等 CPU 处理完当前缓冲区时，另一个缓冲区的数据已经读好

这样可以把一部分 CPU 时间和 I/O 时间重叠起来，提高整体吞吐。

数据库系统里很多优化都不是换一个更复杂的算法，而是让硬件资源不要互相等待。双缓冲区就是让 CPU 和磁盘同时忙起来。

2.4 利用 B+ 树进行排序

如果表上已经有 B+ 树索引，可以直接利用索引顺序来得到排序结果。

聚集索引：

• 磁盘上的数据本身已经按照索引键排序
• 上层又有索引结构可以快速定位
• 查询和排序性能都很好

非聚集索引：

• data entry 是有序的
• 但真实元组在磁盘上的物理位置是杂乱的
• 按索引顺序取元组时，可能频繁随机读磁盘页

若：

• $N$ 为数据页数量
• $p$ 为每页平均记录数
• $f$ 为 data entry 中每条记录长度与真实记录长度的比例

非聚集索引排序的大致代价可记为：

聚集索引很适合顺序输出；非聚集索引虽然 index entry 有序，但访问真实数据时可能变成大量随机 I/O，因此未必划算。

三、关系操作的执行概述

3.1 查询操作的基本类型

查询执行由一系列关系操作组成，主要包括：

• 选择（Selection）
• 投影（Projection）
• 连接（Join）
• 集合操作（Set Operation）
• 聚集操作（Aggregation）

每一种操作都有多种实现方法。查询优化器的任务就是根据数据规模、索引、排序情况、缓冲区大小等信息，为每个操作选择合适的实现方式。

3.2 影响算法性能的因素

主要因素包括：

• 表的大小
• 表是否有索引
• 数据是否已经排序
• 索引是否是聚集索引
• 缓冲区大小
• 缓冲区替换策略

常见的三类基本技术：

1. Iteration：逐个检查表或 data entry 中的数据
2. Indexing：利用索引快速找到满足条件的元组
3. Partitioning：将关系分区，常用排序或哈希降低操作代价

3.3 访问路径

访问路径（Access Path）指从关系表中访问记录的方法。

常见访问路径：

• 文件扫描（File Scan）
• 索引 + 选择匹配条件，例如 attr op value

索引访问要求索引建立在 attr 上，op 可以是 <、<=、=、>=、> 等。

访问路径的选择率（selectivity）可以理解为访问该路径需要读的总页数，包括索引页和数据页。优化器的目标是选择访问页数尽可能少的路径。

本节例子沿用两张表：

1
2
Sailors(sid: integer, sname: string, rating: integer, age: real)
Reserves(sid: integer, bid: integer, day: date, rname: string)

假设：

• Reserves 每条记录 40 字节，每页 100 条，共 1000 页
• Sailors 每条记录 50 字节，每页 80 条，共 500 页
• 代价只考虑 I/O 页数，忽略输出结果大小

四、选择操作

4.1 没有索引，数据不排序

例如：

1
2
3
SELECT *
FROM Reserves R
WHERE R.rname = 'Joe';

对应关系代数操作为：

如果没有索引，且数据没有排序，只能扫描整个表。

对 Reserves：

这种方法选择率差，代价较大。

4.2 没有索引，数据已排序

如果数据按照选择属性排序，可以使用折半查找。

对 1000 页数据：

次 I/O 就可以找到起始位置。

如果条件是 attr > 5，则先找到 5 所在位置，再从该位置向后顺序扫描。

实际数据库中，数据排序往往是和索引绑定在一起的。单独维持一个完全排序的数据文件，插入和删除的代价会很高。

4.3 使用 B+ 树索引

使用 B+ 树索引的查询过程：

1. 从根节点向下找到约束值所在的叶节点
2. 从对应 data entry 开始向后检查
3. 找到所有满足条件的 data entry
4. 根据 data entry 中的 RID 找到真实元组

代价分析：

• 找到起始叶节点通常只需 2-3 次 I/O
• 后续主要代价取决于结果数量，以及索引是否聚集

若索引是聚集索引，满足条件的元组通常连续存放，读取代价较小。

若索引是非聚集索引，满足条件的元组可能分散在许多页上，最坏情况下每条结果都要读一个新页。

例：查询条件 rname < "c%"，结果约占表大小的 10%。

非聚集索引有时会比全表扫描还差。尤其是结果很多时，RID 指向的物理页到处跳，磁盘 I/O 会非常碎。

4.4 使用 Hash 索引

Hash 索引适合相等选择。

执行过程：

1. 根据选择值计算哈希值
2. 找到对应桶
3. 在桶内检测 data entry
4. 根据 RID 从数据文件取回真实元组

如果 Hash 索引不是聚集的，且有 10 个缓冲区、100 个查询结果：

• 找到对应 RID 的代价约为 1-2 次 I/O
• 找真实元组的代价可能是 1-100 次 I/O
• 如果先对 pageid 排序，可以减少重复调入同一页的问题

五、一般选择条件

5.1 CNF 形式

一般选择条件是由逻辑连接符 $\land$ 和 $\lor$ 连接的表达式。

一个基本项（term）形式为：

1
2
attr1 op attr2
attr1 op value

CNF（Conjunctive Normal Form，合取范式）：

• 由 $\land$ 连接若干 conjunct
• 一个 conjunct 可以由 $\lor$ 连接若干 term
• 如果 conjunct 中包含 $\lor$，就称为包含 disjunction

例如：

可转换为：

5.2 复合索引与选择条件

假设选择条件为：

不同索引的效果不同：

• Hash 索引建在 <rname,bid,sid> 上：可以直接检索完整条件，但不能很好支持只查 rname='Joe' AND bid=5
• B+ 树索引建在 <rname,bid,sid> 上：既可支持完整条件，也可支持前缀条件 rname='Joe' AND bid=5
• 索引建在 <bid,sid> 上：可以先按这两个属性检索，再检查 rname
• 如果 <bid,sid> 和 rname 上都有索引：两种方式都可行，需要根据选择率决定

复合索引最重要的是“前缀”。B+ 树按属性顺序排序，所以前缀条件有用；跳过第一列直接查后面的列，通常就用不上这个索引。

5.3 不包含 disjunction 的选择

如果选择条件不包含 $\lor$，可以：

1. 文件扫描
2. 用选择率最高的 primary conjunct 先通过索引查询
3. 再用其他非 primary conjunct 对结果筛选

如果有多个索引同时满足条件：

1. 分别用每个索引找出候选 RID 集合
2. 将 RID 集合求交
3. 再用其他 conjunct 过滤

例如：

如果在 day 和 sid 上都有索引，可以分别执行两个选择，再对结果求交，最后检查 bid。

实际系统中的 RID 集合求交：

5.4 包含 disjunction 的选择

如果选择条件中有 $\lor$，处理会更复杂。

基本原则：

• 如果某一项必须全表扫描，则整个 disjunction 往往难以避免全表扫描
• 如果每一项都有可用索引，则可以分别走索引，再把结果合并
• 如果 disjunction 外层还有 AND 条件，可以先用 AND 中选择率更高的部分缩小范围

例：

1
day < 8/9/94 OR rname = 'Joe'

如果 day 没有索引，需要扫描整个表，则整个条件通常也要扫描整个表。

但：

1
(day < 8/9/94 OR rname = 'Joe') AND sid = 3

如果 sid 上有索引，则可以先查 sid=3，再对候选结果判断前半部分。

六、投影操作

6.1 投影的主要功能

例如：

1
2
SELECT DISTINCT R.sid, R.bid
FROM Reserves R;

对应：

投影操作做两件事：

1. 去掉不需要的属性
2. 删除重复元组

删除重复元组通常依赖两种方法：

• 排序
• Hashing

6.2 基于排序的投影

基本过程：

1. 扫描关系 $R$，只保留需要的属性，生成中间数据集
2. 对中间数据集排序
3. 扫描排序结果，相邻重复元组只保留一个

代价分析：

• 原始表大小为 $M$
• 投影后的中间结果大小为 $T$
• 扫描并写出中间结果代价为 $M+T$
• 排序代价约为 $O(T\log T)$
• 最后去重扫描代价为 $O(T)$

对 Reserves：

• 原表 1000 页
• 原记录长 40 字节
• sid + bid 长度为 10 字节
• 投影后中间结果约 $T=250$ 页

若普通执行：

优化方法：

• 将第一步与外排序的 Pass 0 合并
• 每次 merge 时顺便删除重复元组

若有 20 页缓冲区：

• Pass 0 代价：$1000+250$
• 产生 7 个 run
• Pass 1 代价：$250$
• 总代价约 $1500$

6.3 基于 Hashing 的投影

基于 Hashing 的投影分为两个阶段。

第一阶段：分区

• 逐条读入数据
• 1 块作为输入缓冲区
• $B-1$ 块作为输出缓冲区
• 用哈希函数将投影后的元组映射到不同分区

第二阶段：重复数据删除

• 将每个分区读入内存
• 用第二个哈希函数 $H_2$ 在内存中去重
• 将去重结果写回磁盘
• 清理内存，处理下一个分区

若内存足够大，第二阶段可以在内存中完成：

对前面的例子：

6.4 排序投影与 Hash 投影比较

如果所需属性已经包含在某个索引中，也可以直接在索引上做投影，无需访问真实数据页。因为索引中的数据本身有序，去重也比较方便。

七、连接操作

7.1 Join 的基本含义

例：

1
2
3
SELECT *
FROM Reserves R, Sailors S
WHERE R.sid = S.sid;

连接操作可以看作：

1. 先做笛卡尔积
2. 再按连接条件选择
3. 最后做投影

但直接做笛卡尔积代价太高，因此数据库会使用专门的 Join 算法。

常见 Join 方法：

• 简单嵌套循环 Join
• 块嵌套循环 Join
• 索引嵌套循环 Join
• Sort-Merge Join
• Hash Join

设：

• $R$ 有 $M$ 页，每页 $P_R$ 个元组
• $S$ 有 $N$ 页，每页 $P_S$ 个元组
• 前面例子中 $M=1000$，$P_R=100$，$N=500$，$P_S=80$

7.2 简单嵌套循环 Join

算法：

1
2
3
4
for each tuple r in R:
  for each tuple s in S:
    if r.i == s.j:
      add <r,s> to result

其中：

• $R$ 是 outer 关系
• $S$ 是 inner 关系

若按元组为单位循环，代价为：

代入例子：

这显然非常大。

两个优化：

1. 每次读 outer 的一页，而不是一条元组，代价变为 $M+M\cdot N$
2. outer 关系选择较小的表

7.3 块嵌套循环 Join

算法思想：

1
2
3
for each block of B-2 pages of R:
  for each page of S:
    join all matching tuples in R-block and S-page

缓冲区安排：

• $B-2$ 页用于 outer 关系的一块
• 1 页用于 inner 关系输入
• 1 页用于输出

代价为：

例：

• $M=1000$
• $N=500$
• 缓冲区 $B=100$

若 $B=90$：

若改用 Sailors 作为 outer：

块嵌套循环 Join 的关键是减少 inner 关系被重复扫描的次数。outer 关系越小、缓冲区越大，效果越好。

7.4 索引嵌套循环 Join

算法：

1
2
3
for each tuple r in R:
  find matching tuple s in S using index on S
  add <r,s> to result

基本思想是在 inner 关系上利用索引，快速找到满足连接条件的元组。

如果 inner 上是 B+ 树索引：

• 找到叶节点约需 2-4 次 I/O

如果 inner 上是 Hash 索引：

• 找到桶约需 1-2 次 I/O

如果索引是聚集的，读结果元组代价较小；如果非聚集，则代价取决于匹配元组数量和物理分布。

例：

• 若 Sailors.sid 上有 Hash 索引
• sid 是键，每次只有一个匹配结果
• 每次索引访问约 1.2 次 I/O

则以 Reserves 为 outer：

若 Reserves.sid 上有 Hash 索引，以 Sailors 为 outer：

如果每个 sailor 平均对应 2.5 条 reserves，且索引非聚集，读取真实记录代价可能在 1 到 2.5 之间浮动。

7.5 Sort-Merge Join

Sort-Merge Join 的基本思想：

1. 先将两个关系按照连接属性排序
2. 两个指针分别从两个关系开头向后扫描
3. 找到连接属性值相同的分区
4. 对相同分区内的元组做 Join
5. 输出结果

代价：

• $R$ 排序：$O(M\log M)$
• $S$ 排序：$O(N\log N)$
• Merge 阶段：$M+N$

例：

• $M=1000$
• $N=500$
• 缓冲区为 100 页

排序代价：

Merge 阶段：

总计：

一个优化：如果缓冲区足够大，可以把排序阶段最后一趟 merge 和 Join 阶段的 merge 合并。若某次 Pass 中两个关系的 run 数之和 $L$ 小于缓冲区大小，就可以直接把这些 run 同时调入缓冲区并完成 Join。

7.6 Hash Join

Hash Join 分为两个阶段。

Partitioning 阶段：

• 用同一个哈希函数对两个关系的连接属性分别分区
• 相同哈希值的元组会进入对应分区

Probing 阶段：

• 对每一对对应分区分别处理
• 将较小分区读入内存，构建哈希表
• 扫描另一个分区，用相同连接属性 probe 哈希表
• 输出匹配结果

代价：

• 分区阶段读写两个关系：$2(M+N)$
• Probing 阶段再读一遍：$M+N$

总计：

例：

如果某个 partition 超过缓冲区大小，可以对该 partition 再次分区。

7.7 Hybrid Hash Join

当缓冲区足够大时，可以进一步优化 Hash Join：

• 分区时，将 outer 关系的第一个分区直接留在内存中
• 当 inner 关系读入并分区时，第一个分区的 probing 已经可以完成
• 这样减少了一部分写回磁盘和重新读入的 I/O

例：

• $R=500$ 页
• $S=1000$ 页
• 缓冲区 300 页
• 分成两个分区

混合 Hash Join 代价约为：

如果一个关系能整个放入缓冲区，则 Join 代价可以降低到只扫描两个关系一遍。

7.8 Join 算法比较

Hash Join vs Block Nested Loop Join

• 如果一个关系能整个放入缓冲区，两者代价类似
• 如果两个关系都不能完整放入缓冲区，Block Nested Loop 需要多次扫描 inner 表，而 Hash Join 的扫描次数较固定

Hash Join vs Sort-Merge Join

• 若 $B>\sqrt{M}$，且数据分布均匀，Hash Join 可达到 $3(M+N)$
• 若 $B>\sqrt{N}$，且数据分布均匀，Sort-Merge Join 也可达到 $3(M+N)$
• Sort-Merge Join 对数据分布不太敏感，并且输出有序
• 如果缓冲区大小位于 $\sqrt{N}$ 与 $\sqrt{M}$ 之间，Hash Join 往往更好

7.9 一般 Join 条件

若连接条件为：

可以：

• 用 Index Nested Loop Join：在 inner 关系上建立复合索引，如 <sid,rname>
• 用 Sort-Merge Join：分别按 <sid,rname> 与 <sid,sname> 排序

若连接条件为：

可以使用 Index Nested Loop Join，但 Sort-Merge Join 和 Hash Join 不太适用。

等值连接最适合 Hash Join；排序连接适合等值连接，也能顺便得到有序结果；非等值连接往往更依赖索引。

八、集合操作与聚集操作

8.1 集合操作

集合操作包括：

其中：

• $R \cap S$ 和 $R \times S$ 可以看作特殊 Join
• $R \cup S$ 和 $R-S$ 的核心都是发现两个关系中相同的元组

实现方法主要有两类：

• 通过排序
• 通过 Hash

8.2 聚集操作

SQL-92 中常见聚集操作：

• AVG
• MIN
• MAX
• SUM
• COUNT

例如：

1
2
SELECT AVG(S.age)
FROM Sailors S;

基本实现方法是扫描整个表，并在扫描过程中维护所需统计信息。

8.3 Group By

例如：

1
2
3
SELECT AVG(S.age)
FROM Sailors S
GROUP BY rating;

需要先按照 rating 分组，再在每组内聚集。

主要实现方法：

• 基于排序
• 基于 Hashing
• 基于索引

如果所有属性都出现在索引中，可以不访问物理表；如果 GROUP BY 属性上有索引，则可以利用索引的顺序完成排序和分组。

九、缓冲区对查询执行的影响

缓冲区大小会显著影响执行方法选择：

• 多个操作并行执行时，每个操作能使用的空间会减少
• 非聚集索引通过 data entry 访问物理页时，可能频繁调入不同数据页
• 如果访问有规律，可以用更好的调度策略减少 I/O

对简单 Nested Loop Join：

• 如果整个 inner 关系可以调入缓冲区，则不需要特别考虑替换策略
• 如果不能，LRU 可能造成大量 I/O
• MRU 有时更合适，因为 inner 关系中前 $B-2$ 页可以尽量保留在缓冲区中

对 Block Nested Loop Join：

• 替换策略影响较小，因为访问模式比较固定

对 Index Nested Loop Join：

• 如果 inner 关系索引不是聚集的，可以先对 outer 关系中的数据排序
• 这样可以减少 inner 关系中数据页的重复读取

同一个 Join 算法，在不同缓冲区大小下代价可能完全不同。所以优化器不只看算法名，还要结合当前可用内存。

十、查询优化入门

10.1 为什么需要查询优化

每个查询都有多种实现方法，DBMS 必须选出其中代价最小的访问方法。查询优化器就是用来解决这个问题的。

查询处理过程可以概括为：

1
2
3
4
5
6
7
查询语句
  -> 查询解析器
  -> 查询优化器
       -> 计划生成器
       -> 计划代价评估
       -> 数据字典管理
  -> 查询计划执行器

查询优化的基本思路：

1. 列出表达式的各种执行方案
2. 为每种访问计划计算代价
3. 选择代价最小的访问计划

实际 DBMS 中，优化器是非常复杂的模块，需要同时处理逻辑等价变换、物理算法选择、连接顺序枚举和代价估计。

10.2 查询访问计划

查询访问计划是一棵扩充的关系代数树，每个节点不仅标明关系操作，还标明：

• 对关系的访问方法
• 操作的具体执行方法
• 是否流水线执行

例：

1
2
3
4
5
SELECT S.sname
FROM Reserves R, Sailors S
WHERE R.sid = S.sid
  AND R.bid = 100
  AND S.rating > 5;

关系代数表达式可写为：

如果选择和投影结果直接传给下一个操作，不生成中间表，称为 Pipeline / on-the-fly。

如果结果先写成中间表，再供后续操作使用，称为物化（Materialization）。

10.3 循环访问接口

为了统一不同操作的访问方法，数据库通常为算子提供循环访问接口：

• open()：初始化操作，分配缓冲区
• get_next()：取出下一个输入元组
• close()：释放资源

这个接口天然支持 Pipeline：上层算子需要下一条数据时，调用下层算子的 get_next()。

十一、System R 优化器与数据字典

11.1 System R 优化器

System R 是第一个关系数据库管理系统，它的优化器对后来的关系数据库影响很大。

主要特点：

• 使用数据库对象的统计信息估测查询代价
• 主要考虑两个关系的 Join
• inner 关系通常是原始表
• 用启发式方法减少候选访问计划数量
• 不考虑嵌套查询优化
• 投影操作中一般不做重复元组删除
• 代价模型同时考虑 CPU 和 I/O

System R 的重要性不只是实现了一个系统，而是奠定了“基于代价的优化器”这个思路。

11.2 系统数据字典

一般 DBMS 都提供系统数据字典，也称为：

• System Catalog
• Catalog
• Data Dictionary

数据字典本身也存储为数据库表，用来记录数据库中各种对象的信息。

对每个关系，系统信息包括：

• 关系名
• 属性名
• 属性类型
• 索引名
• 约束描述

对每个索引，系统信息包括：

• 索引名
• 索引结构类型
• 索引建立属性
• 数据排列方式

对每个视图，系统信息包括：

• 视图名
• 视图定义
• 约束检查方式

此外，关系和索引的统计信息也保存在系统中：

• 关系中元组数量
• 关系页数
• 索引中不同键值数量
• 索引大小、高度和范围

这些信息正是优化器做代价估计的基础。

十二、优化例子

12.1 先做选择

前面例子的直接访问计划可能先做 Join：

再做：

如果 Join 使用简单嵌套循环，代价可能高达：

由于后续选择和投影采用 on-the-fly，不再产生额外 I/O，所以总代价仍约为 501000。

优化思想：Pushing selections，即先做选择，减少参与 Join 的关系大小。

假设：

• 缓冲区只有 5 页
• Reserves 上选择结果为 10 页
• Sailors 上选择结果为 250 页

若先分别选择并写临时表，再用 Sort-Merge Join：

• 扫描并写选择结果：$1000+10+500+250$
• 两个关系排序：$2\cdot 2\cdot 10 + 2\cdot 4\cdot 250 = 2040$
• Merge 阶段：$260$

总代价：

若用 Block Nested Loop Join：

总计约：

相比 501000 已经大幅下降。

12.2 利用索引

如果：

• Reserves.bid 上有静态聚集 Hash 索引
• Sailors.sid 上有 Hash 索引

则可以：

1. 用 Reserves.bid=100 的 Hash 索引先找出候选结果
2. 不把 Reserves 的选择结果物化
3. 以它为 outer，去 Sailors.sid 的索引中找匹配元组
4. S.rating>5 可以在 Join 后 on-the-fly 检查

这里有一个看似反直觉的点：

如果把 rating>5 提前到 Join 之前，可能会破坏对 Sailors.sid 索引的充分利用，因为中间表没有索引。

若 Sailors.sid 是键索引，每次查询只有一个结果，Hash 索引访问代价约为 1.2-2.2 次 I/O。

估算总代价：

如果 Sailors 上的索引是聚集的，性能还可以更好。

12.3 少量查询结果

如果查询为：

1
2
3
4
5
6
SELECT S.sname
FROM Reserves R, Sailors S
WHERE R.sid = S.sid
  AND R.bid = 100
  AND S.rating > 5
  AND R.day = '8/9/94';

若对 Reserves 的选择只产生一条结果，则可以：

1. 用 bid=100 的 Hash 索引找到候选
2. on-the-fly 检查 day='8/9/94'
3. 对这一条结果用 sid 去 Sailors 的索引中查找
4. 检查 rating>5

这种访问计划代价可能只有约 11 次 I/O。

查询优化不是简单地“选择一定要提前”或“索引一定要用”。真正的问题是：哪个操作提前之后，能不能减少后续代价；如果产生了中间表，原来的索引是否还存在。这就是优化器难的地方。

• Previous
  网络训练
• Next
  多项式环