Chapter 11 : Query Processing¶

约 7290 个字 10 张图片预计阅读时间 36 分钟

Basic Steps in Query Processing¶

查询处理（Query Processing）是数据库系统中最重要的功能之一。查询处理的基本步骤如下：

解析（Parsing）和翻译（Translation）
- 将查询语句翻译为系统能够理解的内部形式，后来被翻译为关系代数
- 解析器（Parser）检查符号和关系
优化（Optimization）
- 在所有等价的求值/执行方法中选择成本最低的
求值/执行（Evaluation）
- 查询执行引擎（Query-Execution Engine）负责生成并执行查询求值计划，以及返回查询结果

Measures of Query Cost¶

查询成本通常以回答查询的总运行时间来衡量
- 影响因素包括磁盘访问，CPU，甚至网络传输
通常磁盘访问是成本的主要来源，也是相对来说更容易估计的
我们需要考虑：
- 寻道次数 / 平均寻道时间
- 读取块数 / 平均读取块时间
- 写入块数 / 平均写入块时间
- 写入块的时间比读入块的时间更大，因为需要在写入数据之后读一遍为了确保写入正确
在估计查询求值计划的成本时，我们用块传输个数（Number of Blocks Transfers）和磁盘寻道次数（Number of Seeks）这两个因素来衡量。我们用 \(t_T,t_S\) 分别表示传输一个数据块的平均时间和平均块访问时间（磁盘寻道时间 + 旋转时延）。所以，假如某个运算需要传输 \(b\) 个数据块和 \(S\) 次磁盘寻道，那么所需时间为 \(b\times t_T+S\times t_S\)
- 其中 \(t_S\) 和 \(t_T\) 取决于数据存储的位置
有几种算法可以通过使用额外的缓冲区空间来减少磁盘 IO
- 缓冲区可用的实际内存量取决于其他并发查询和 OS 进程，仅在执行期间知道
- 我们经常使用最坏情况估计，假设只有操作所需的最小内存量可用
所需数据可能已经驻留在缓冲区中，从而避免了磁盘 I/O
- 但很难考虑成本估算

Selection Operation¶

在查询处理中，文件扫描（File Scans）是访问数据的最底层操作，是一种定位和检索满足选择条件的搜索算法

在一个选择运算中，最简单的算法是线性搜索（Linear Search）（标记为 A1）：系统扫描每个文件块，检验所有的记录，看它们是否满足选择条件

Selection Using Indices¶

使用索引的搜索算法被称为索引扫描（Index Scan），这一类算法包括：

A2（聚集索引，键上的相等条件）：使用索引检索满足对应相等条件的单个记录
A3（聚集索引，非键属性的相等条件）：和前一种情况的区别是需要获取多个记录，而这些记录必须在文件中被连续存储，因为文件是按搜索键排序的
A4（二级索引，相等条件）：分为两种情况
- 键上的相等条件：和 A2 类似
- 非键属性的相等条件：每个记录可能位于不同的块内，导致每检索一条记录需要一次 I/O 操作，而 I/O 操作包含一次寻道和一次块传输。在最坏情况下，成本为 \((h_i+n)\cdot (t_S+t_T)\)，其中 \(n\) 为获取的记录数，\(h_i\) 为 B+ 树的高度，且假设每个记录都位于不同的硬盘块，且这些硬盘块是随机排序的

Selection Involving Comparisons¶

有以下算法可以处理形如 \(\sigma_{A\leq v}(r)\) 的选择：

A5（聚集索引，比较条件）
- 对于形如 \(A>v\) 或 \(A\geq v\) 的比较，可以先找到 \(v\) 的索引，以找到第一个满足条件的元组；然后从该元组出发进行文件扫描，直到文件末尾结束
- 而对于形如 \(A<v\) 或 \(A\leq v\) 的比较，则不需要先进行索引查找，而是先从文件开头进行文件扫描，直到发现第一个满足 \(A=v\) 或 \(A>v\) 的索引。而在这种情况下，索引显得不是特别有用
A6（二级索引，比较条件）：正如前面所说，该方法访问单个记录的成本太高，因此很少被使用，除非选择的记录很少

以上算法的估计成本如下图所示：

Implementation of Complex Selections¶

目前我们只考虑了形如 \(A\text{ op }B\) 的简单选择条件，其中 op 是比较运算符。现在来考虑更复杂的选择谓词：

合取（Conjunction）：\(\sigma_{\theta_1\land\theta_2\land\cdots\land\theta_n}(r)\)
析取（Disjunction)：\(\sigma_{\theta_1\lor\theta_2\lor\cdots\lor\theta_n}(r)\)
否定（Negation）：\(\sigma_{\neg\theta}(r)\)

相应的算法有：

A7（使用单索引的合取选择）：
- 先确定对于某个简单条件而言，某个属性是否存在一条访问路径（Access Path）（即是否存在对应的索引结构）。如果有的话就可以用 A2-A6 里面的算法来检索满足条件的记录。接下来在内存缓冲区中检验被检索到的记录是否满足其余简单条件，以完成整个运算
- 为了节省成本，对于每个简单条件 \(\theta_i\)，我们从 A1-A6 中挑选出 \(\sigma_{\theta_i}(r)\) 成本最低的算法
A8（使用复合索引的合取选择）：如果选择条件涉及到多个属性的相等比较，且有这些属性构成的复合索引的话，那么索引就能被直接搜索到。这时我们就用 A2-A4 里面的算法。
A9（使用标识符交集的合取选择）：
- 所有记录标识符（Record Indentifier）（或记录指针）的交集为一组指向满足合取条件的元组的指针
- 该算法的成本包括单独的索引扫描，以及检索记录的成本。可通过对指针排序来降低成本
A10（使用标识符并集的析取选择）：类似 A9

Sorting¶

我们可以通过构建一个基于搜索键的索引，然后根据索引读取关系实现对关系的排序。但这么做只是对关系进行逻辑层面的排序，而我们希望的是对关系进行物理层面上的排序。如果主存能够容得下所有数据的话，那我们可以直接用在算法课上学到的排序算法（比如快排）实现排序；但如果容不下的话，则需要更高级的方法，外部-归并排序是个比较好的算法

外部排序基本思想在 ADS 中已经详细介绍过了，这里就不再赘述了，这里给一个例子：

Cost Analysis¶

先计算硬盘访问成本：
- 令 \(b_r\) 为包含关系 \(r\) 元组的块数。第一阶段需要对每个块进行一次读操作和一次写操作，因此共计 \(2b_r\) 次块传输
- 初始的 Run 数为 \(\lceil\frac{b_r}{M}\rceil\)
- 合并时，一次从数据块中读取一个 Run 会带来大量的寻道操作，为降低寻道次数，我们为每个输入 Run 和输出 Run 分配 \(b_b\) 个更大的缓存块，因此每一趟可以合并 \(\lfloor\frac{M}{b_b}−1\rfloor\) 个 Run，也就是说每次合并后的 Run 数降低到原来的 \(\lfloor\frac{M}{b_b}−1\rfloor\)
- 总的合并趟数为 \(\lceil\log⁡_{\lfloor\frac{M}{b_b}−1\rfloor}(\frac{b_r}{M})\rceil\)
- 每一趟都要对每个数据块进行一次读操作和一次写操作，除了以下两种情况
  - 最后一趟得到的输出无需写入硬盘
  - 有些 Run 可能在某一趟中既不被读取也不被写入，在这里我们忽略这个特殊情况
- 总的块传输次数为：\(b_R(2\lceil\log⁡_{\lfloor\frac{M}{b_b}−1\rfloor}(\frac{b_r}{M})\rceil+1)\)
再计算磁盘寻道成本：
- Run 生成时需要为每个趟进行读和写的操作
- 每趟合并需要分别大约 \(\lceil\frac{b_r}{b_b}\rceil\) 次用于读取和写入数据的寻道，即共计 \(2\lceil\frac{b_r}{b_b}\rceil\) 次寻道（除了最后一趟）
- 总的寻道数为：\(2\lceil\frac{b_r}{M}\rceil+\lceil\frac{b_r}{b_b}\rceil(2\lceil\log_{\lfloor\frac{M}{b_b}−1\rfloor}(\frac{b_r}{M})\rceil+1)\)

Join Operation¶

Nested-Loop Join¶

嵌套循环连接（Nested-Loop Join）的算法（计算 Theta 连接 \(r\Join\theta_s\)）如下所示：

其中关系 \(r\) 被称为外层关系（Outer Relation），\(s\) 被称为内层关系（Inner Relation）。该算法里面用到了符号 \(t_r\cdot t_s\)，表示 \(t_r,t_s\) 两个元组根据相同属性值拼接后构成的元组
该算法不要求用到索引，且适用于任何连接条件
我们可以将该算法扩展至计算自然连接——只要在 Theta 连接后的结果的基础上去除 \(t_r\cdot t_s\) 的重复属性即可
该算法成本较高，因为需要检验两个关系中的每一个元组对，总共有 \(n_r\cdot n_s\) 个元组对（其中 \(n_r,n_s\) 分别表示 \(r,s\) 的元组数）
在最坏情况下，缓冲区只能为每个关系保存一个块，因此需要 \(n_r\cdot b_s+b_r\) 次块传输（\(b_r,b_s\) 分别表示包含 \(r,s\) 元组的块数）和 \(n_r+b_r\) 次寻道
在最好情况下，内存能够同时存放两个关系，因此仅需 \(b_r+b_s\) 次块传输和 2 次寻道
如果内存仅能保存一个完整的关系，那么最好让内层关系 \(s\) 放在内存中，因为这样内层关系只需读一次就行了。此时的成本和最好情况下的一致

Block Nested-Loop Join¶

如果缓冲区太小，无法容得下任何一个完整的关系，那我们可以通过按块读取关系，而不是按元组读取关系来节省块的访问次数。这便是块嵌套循环连接（Block Nested-Loop Join）算法：

在最坏情况下，对于外层关系的每个块，只能读取一个内层关系的块，因此需要 \(b_r⋅b_s+b_r\) 次块传输，以及 \(2b_r\) 次寻道。不难发现，将更小的关系作为外层关系会使运算更为高效
在最好情况下，当内层关系可被内存容纳时，此时仅需 \(b_r+b_s\) 次块传输和 2 次寻道

块嵌套循环的性能还能通过以下方法进一步提升：

如果自然连接或相等连接中的连接属性构成了内层关系的键，那么对于每个外层关系的元组，当发现第一个匹配的元组时，内层循环能够马上就终止
在块嵌套循环中，我们用内存能够容纳（且为内层关系和输出预留足够空间）的最大的数据块。换句话说，假设有 \(M\) 个内存块，那么我们每次从外层关系读取 \(M−2\) 个数据块。这样能够降低扫描内部关系的次数（从 \(b_r\) 降到 \(\lceil\frac{b_r}{M−2}\rceil\)，并且此时的成本为 \(\lceil\frac{b_r}{M−2}\rceil\cdot b_s+b_r\) 次块传输和 \(2\lceil\frac{b_r}{M−2}\rceil\) 寻道
我们可以交替地前后扫描循环，这样可以对硬盘块进行排序，使得留在缓冲区的数据能够被再次使用，从而降低硬盘访问次数
如果内层循环连接属性上的索引可用的话，那么可以用更高效的索引查找来替代文件扫描，下面就来介绍这种方法

Indexed Nested-Loop Join¶

上述用索引查找替代文件扫描的连接方法被称为索引嵌套循环连接（Indexed Nested-Loop Join）。该方法的成本为：

对于外层关系 \(r\) 的每一个元组，都要对 \(s\) 的索引进行一次查找，并检索到相关的元组
在最坏情况下，缓冲区的空间仅能容纳 \(r\) 的一个块以及索引的一个块，那么读取 \(r\) 需要 \(b_r\) 次 I/O 操作（包括一次寻道和一次块传输）。所以此时连接的成本为 \(b_r(t_T+t_S)+n_r\cdot c\)，其中 \(c\) 为使用连接条件对 \(s\) 的单个选择所需的成本

Merge Join¶

归并连接（Merge Join）算法如下所示：

其中，\(\text{JoinAttrs}\) 指代 \(R\cap S\)

下图展示的是进行合并排序的两个排好序的关系，它们的连接属性为 \(a1\)：

该算法要求 \(S_s\) 中的元组能够被主存容纳。如果 \(S_s\) 的大小超过可用内存的大小的话，那么可以采用块嵌套循环连接，匹配连接属性值相同的，分别来自 \(r,s\) 的两个块

如果输入关系 \(r,s\) \(h_i\) 没有基于连接属性进行排序的话，那么就需要先对它们进行排序

Cost Analysis¶

一旦关系是排好序的（这里指的是物理层面上的），那么相同连接属性值的元组的顺序是连续的，因此每个元组只需读取一次，从而每个块也只需读取一次。那么块传输数量为 \(b_r+b_s\)

假设为每个关系分配了 \(b_b\) 个缓存块，那么磁盘寻道次数为 \(\lceil\frac{b_r}{b_b}\rceil+\lceil\frac{b_s}{b_b}\rceil\)。由于相比块传输，寻道成本更高，因此我们应尽可能为每个关系分配多个缓存块

Hybrid Merge Join¶

如果连接属性上有二级索引的话，那我们可对未排好序的元组执行一种合并连接的变体。该算法通过索引对记录进行扫描，这样的检索顺序就是排好序的。但该方法有一个显著的缺陷：由于记录可能分散在各个文件块内，因此每次元组访问都会带来一次硬盘块访问，成本相当高

为避免这种成本，我们采用一种混合合并连接（Hybrid Merge-Join）的技术，将索引和合并连接结合起来。基于上述假设（并假设二级索引用到 B+ 树），我们根据二级 B+ 树索引的叶子项来合并排好序的关系，得到的结果文件包含了来自排好序的关系的元组，以及该元组在未排好序的关系中的地址。然后该结果文件会根据这些地址进行排序，这样就能以物理存储顺序高效检索对应的元组，从而完成连接操作

Hash Join¶

哈希连接（Hash-Join）使用哈希函数 \(h\) 来划分两个关系中的元组，具体来说是将连接属性具有相同哈希值的元组放在一个集合内。我们假设：

\(h\) 是一个将 \(\text{JoinAttrs}\) 值映射到 \(\{0,1,\cdots,n_h\}\) 的哈希函数，其中 \(\text{JoinAttrs}\) 是 \(r,s\) 在自然连接中的共同属性
\(r_0,r_1,\cdots,r_{n_h}\) 表示对 \(r\) 元组的划分，每个划分初始均为空，且每个元组 \(t_r\in r\) 被放在划分 \(r_i\) 内，其中 \(i=h(t_r[\text{JoinAttrs}])\)
\(s_0,s_1,\cdots,s_{n_h}\) 表示对 \(s\) 元组的划分，每个划分初始均为空，且每个元组 \(t_s\in s\) 被放在划分 \(s_i\) 内，其中 \(i=h(t_s[\text{JoinAttrs}])\)

哈希连接的基本思想是：假设来自 \(r\) 的元组和来自 \(s\) 的元组满足连接条件，也就是说它们有相同的连接属性值。如果这个值通过哈希函数映射到值 \(i\)，那么来自 \(r\) 的元组被归入到划分 \(r_i\)，来自 \(s\) 的元组被归入到划分 \(s_i\)。所以 \(r_i\) 中的元组仅需和 \(s_i\) 中的元组进行比较，无需考虑其他划分下的元组

哈希连接的算法如下所示：

划分好关系后，就要对每个划分对 \(i(i=0,\cdots,n_h)\) 执行单独的索引嵌套循环连接。具体来说，首先要为每个 \(s_i\) 构建（Build）一个哈希索引；然后从 \(r_i\) 中探测（Probe）（即查找）对应的元组。因此关系 \(s,r\) 分别叫做构建输入和探测输入
\(s_i\) 的哈希索引的构建是在内存中进行的，所以无需到硬盘中访问元组。注意用于构建哈希索引的哈希函数必须和用于划分的哈希函数不同，但也仅作用在连接属性上。在索引嵌套循环连接中，系统使用哈希索引来检索与探测输入中的记录匹配的记录
构建和探测阶段都仅需一趟即可
\(n_h\) 的大小必须足够大，使得对于每个 \(i\)，在构建关系的划分 \(s_i\) 的元组和该划分的哈希索引能够被内存容纳。但没必要让探测关系的划分被内存完全容纳。所以我们让更小的那个关系作为构建关系
如果构建关系包含 \(b_s\) 个块，每个划分的大小不超过 \(M\)，那么划分数量 \(n_h\) 至少为 \(\lceil\frac{b_s}{M}\rceil\)
- 通常我们选取 \(n_h\) 为 \(\lceil\frac{b_s}{M}\rceil\times f\)，其中 \(f\) 被称为修正因子（Fudge Factor），一般大约为 1.2

Recursive Partitioning¶

如果 \(n_h\geq\) 块数，关系就无法在一趟内被划分完毕，因为没有足够多的缓存块。因而划分过程需要花多趟完成——在每一趟中，只要能为输出留够缓存的话，就划分出尽可能多的划分。从某趟中得到的每个桶会在下一趟中被单独读取和划分，以创建更小的划分。注意每一趟用到的哈希函数是不同的。系统将会重复进行划分操作，直到构建输入的每个划分都能被内存容纳得下为止。这样的划分过程称为递归划分（Recursive Partitioning）

当 \(M>n_h+1\)，即 \(M>\frac{b_s}{M}+1\)（可简化为 \(M>\sqrt{b_s}\)）时，该关系就无需进行递归划分了

Cost Analysis¶

假如不用递归划分的话，

对两个关系 \(r,s\) 的划分需要一次读和一次写操作，因此共计 \(2(b_r+b_s)\) 次块传输。而构建和探测阶段需要读取每个划分一次，因此需要另外 \(b_r+b_s\) 次块传输。而划分所占据的块数可能略多于 \(b_r+b_s\)，因此会出现一些内容仅部分占满的数据块。对于每个关系，访问这样的数据块至多会带来 \(2n_h\) 的开销。因而总的块传输为 \(3(b_r+b_s)+2n_h\) 次，其中 \(4n_h\) 通常比前一项小很多，可以忽略不计
假如为输入和输出缓冲区分配了 \(b_b\) 个块，那么划分需要 \(2(\lceil\frac{b_r}{b_b}\rceil+\lceil\frac{b_s}{b_b}\rceil)\) 次寻道。而在构建和探测阶段中，对于每个关系的 \(n_h\) 个划分，各仅需一次寻道。因此总计 \(2(\lceil\frac{b_r}{b_b}\rceil+\lceil\frac{b_s}{b_b}\rceil)+2n_h\) 次寻道

但假如用到递归划分的话，

每一趟划分会将划分的数量减少到原来的 \(\lceil\frac{M}{b_b}−1\rceil\)，且预计趟数为 \(\lceil\log⁡\lfloor\frac{M}{b_b}−1\rfloor\frac{b_s}{M}\rceil\)
在每一趟中，\(s\) 中的每个块都要被读和写一次，因此在划分 \(s\) 时的块传输次数为 \(2b_s\lceil\log⁡\lfloor\frac{M}{b_b}−1\rfloor\frac{b_s}{M}\rceil\)。划分 \(r\) 时所需的块传输次数和划分 \(s\) 时的基本一致，因此总的块传输次数为：\(2(b_r+b_s)\lceil\log⁡\lfloor\frac{M}{b_b}−1\rfloor\frac{b_s}{M}\rceil+b_r+b_s\)。
我们忽略在构建和探测阶段需要的少量寻道，总的寻道次数为 \(2(\lceil\frac{b_r}{b_b}\rceil+\lceil\frac{b_s}{b_b}\rceil)\lceil\log⁡\lfloor\frac{M}{b_b}−1\rfloor\frac{b_s}{M}\rceil\)

如果主存容量足够大，可以放得下整个构建输入的话，那么 \(n_h=0\)，无需对关系进行划分。此时仅需 \(b_r+b_s\) 次块传输和 2 次寻道

Other Operations¶

Duplicate Elimination¶

要想消除重复项，我们可以先对关系进行排序。排序之后，相同的元组就会出现在相邻的位置上，但只保留其中一份拷贝。在外部排序归并中，我们可以在创建 Run 时，且在将 Run 写入硬盘前发现并移除重复项，从而减少块传输次数。生下来的重复项能够在合并阶段被消除，这样最终排好序的 Run 就不会包含重复项了。所以在最坏情况下消除重复项的成本和在最坏情况下对关系排序的成本一样

在哈希连接算法中，我们也可以用哈希来去重。在为每个划分构建哈希索引时，我们仅插入那些不存在的元组，否则就丢掉这个元组。当划分的所有元组都被处理过后，就讲它的哈希索引写入到结果中。所以此时去重的成本和处理构建关系的成本一样

Projection¶

整个关系进行（广义）投影操作，就要对每个元组进行投影。这样很容易出现重复项，需要去重，就和上面所讲的一样了

Aggregation¶

聚合运算的实现和去重类似，同样可以使用排序或哈希，但是要基于用于分组的属性
实现聚合运算的成本和对聚合函数进行去重操作的成本一致
在聚合运算分组的同时，就要为分好的每个组进行处理
- 对于 SUM、MIN 和 MAX，当同一组内发现两个元组时，当在同一分组中发现两个元组时，系统会将它们替换为一个单独的元组，该元组分别包含被聚合列的 SUM、MIN 和 MAX
- 对于 COUNT 运算，它会为每个已找到元组的组维护一个运行时的计数值
- 对于 AVG 运算，则通过即时计算总和与计数值来实现，最终将总和除以计数以得出平均值

Set Operations¶

集合运算包括并、交、差。对于这些运算，仅需对两个排好序的关系进行一次扫描即可，因此块传输次数为 \(b_r+b_s\)
在最坏情况下，如果每个关系仅有一个块缓冲区的话，那么还需要 \(b_r+b_s\) 次寻道。所以可通过分配额外的缓存块来降低寻道次数。
如果关系没有排好序的话，那么还要考虑排序的成本。
也可以用哈希来实现集合运算：先对两个关系分别进行划分，且要使用相同的哈希函数，然后分情况讨论
- \(r\cup s\)
  - 为 \(r_i\) 构建在内存上的哈希索引
  - 当 \(s_i\) 中的元组没有出现时，就向哈希索引加入该元组
  - 将哈希索引的元组加到结果中
- \(r\cap s\)
  - 为 \(r_i\) 构建在内存上的哈希索引
  - 对于 \(s_i\) 的每个元组，探测哈希索引，如果该元组出现在哈希索引中的话，就输出该元组
- \(r−s\)
  - 为 \(r_i\) 构建在内存上的哈希索引
  - 对于 \(s_i\) 的每个元组，当它在哈希索引中出现时，就从哈希索引中删除该元组
  - 将哈希索引的元组加到结果中

Outer Join¶

有两种实现外连接运算的方法：

先计算 \(r\Join s\)，然后加上 \(r⟕_{\theta}s\) 和 \(r⟖_{\theta}s\) 中额外出现的元组，这样就够成了完整的 \(r⟗_{\theta}s\)
- 计算 \(r⟕_{\theta}s\) 时可以先算 \(r\Join_{\theta}s\)，将结果临时存放在关系 \(q_1\) 内；然后计算 \(r−\prod_R(q_1)\) 获取那些没有参与到 Theta 连接的 \(r\) 的元组，对这些元组用 null 值填充后加入到 \(q_1\) 中，得到最终结果
- 由于 \(r⟖_{\theta}s\) 等价于 \(s⟕_{\theta}r\)，所以计算步骤同上，不再赘述
修改原有的连接算法
- 将嵌套循环连接算法进行扩展，用来计算左外连接：对于外层关系中没有和任何内层关系中的元组匹配的元组，用 null 值对其填充后将其写入到输出中。然而该方法很难扩展到全外连接
- 可以通过扩展合并连接和哈希连接来计算外连接
  - 在合并连接算法中，实现外连接所需的成本和实现对应的一般连接的成本基本一致，唯一的区别是结果的规模不同

Evaluation of Expressions¶

前面我们考虑的都是单步的关系运算，对于如何对包含多步运算的表达式进行求值，具体有以下两种方法：

物化（Materialization）：按照合适的顺序，一次对一个运算求值。每次求值的结果需要被物化（Materialized) 为一个临时关系，用于之后的求值。该方法的缺点就是构造的临时关系必须要被写入硬盘里
流水线（Pipelining）：同时对多个运算求值，某个运算的结果将马上传递给下一个运算，无需将结果存在临时关系里

Materialization¶

最易于直观理解如何对一个表达式求值的方式是观察该表达式在运算符树（Operator Tree）上的图画表示。比如对于表达式 \(\prod_{\text{name}}(\sigma_{\text{building}=\text{Watson}}(\text{department})\Join\text{instructor})\)，它的运算符树如下所示：

假如要应用物化方法的话，我们从这棵树最底层的运算出发进行求值，具体可用前面介绍过的算法来执行运算，然后将结果存储在临时关系里。接着就拿这个临时关系，或者（可能需要）原来存储在数据库里的关系，继续执行上一层的运算。重复这一步骤，直到完成对根节点的运算为止，此时得到整个表达式的最终结果。上述的求值过程称为物化求值（Materialized Evaluation）

物化求值的成本不仅包括所有运算的成本总和，还得考虑将中间结果写入硬盘所需的成本。如果能用双缓冲区（Double Buffering）（使用两个缓存区，一个继续执行算法的同时，另一个将数据写入到硬盘中，从而做到 CPU 活动和 I/O 活动的并行）的话，能够使算法更加高效地执行。而寻道次数则可通过为输出缓存区分配额外的块来降低

Pipelining¶

使用流水线的求值过程称为流水线求值（Pipelined Evaluation）。为运算创建流水线带来的好处有：

消除了从临时关系中读取和写入所需的成本，从而减少查询求值的成本
如果查询求值计划中的根运算符与其输入以流水线方式结合，那么能够快速生成查询结果

流水线的执行方式有：

需求驱动型流水线（Demand-Driven Pipeline）：
- 系统会反复向流水线顶端的操作请求元组
- 每当一个操作接收到元组请求时，它会计算出下一个（或下一批）待返回的元组并将其返回
- 若该操作的输入未采用流水线方式，则可根据输入关系计算待返回的后续元组，同时系统会记录已返回的数据状态
- 若存在流水线式的输入，则该操作还会向其流水线输入端发起元组请求
- 利用从流水线输入端获取的元组数据，该操作将计算出输出结果并向上传递给父级操作
- 每个操作都能以一个迭代器（Iterator）的形式实现，该迭代器提供以下功能：open()、next() 和 close()
- 在调用 open() 之后，每次调用 next() 将返回该操作的下一个输出元组。操作的实现会相应地对其输入调用 open() 和next()，以便在需要时获取其输入元组。函数 close() 用于告知迭代器不再需要更多元组
- 迭代器在执行过程中保持其状态（State）不变，使得连续的 next() 请求能够接收到连续的结果元组
生产者驱动型流水线（Producer-Driven Pipeline）：
- 操作不会等待请求来生成元组，而是主动积极地生成元组
- 每个操作被建模为系统内的独立进程或线程，它从其流水线输入中获取元组流，并为输出生成相应的元组流

Chapter 11 : Query Processing¶

Basic Steps in Query Processing¶

Measures of Query Cost¶

Selection Operation¶

Selection Using Indices¶

Selection Involving Comparisons¶

Implementation of Complex Selections¶

Sorting¶

Cost Analysis¶

Join Operation¶

Nested-Loop Join¶

Block Nested-Loop Join¶

Indexed Nested-Loop Join¶

Merge Join¶

Cost Analysis¶

Hybrid Merge Join¶

Hash Join¶

Recursive Partitioning¶

Cost Analysis¶

Other Operations¶

Duplicate Elimination¶

Projection¶

Aggregation¶

Set Operations¶

Outer Join¶

Evaluation of Expressions¶

Materialization¶

Pipelining¶

评论