5 min read

XI. Query Processing

memset0

Jun 8, 2025

Basic Steps in Query Processing

查询处理的基本步骤
- 解析(parsing) 和 翻译(translation)：将查询语句转化为内部表示，然后转化为关系代数．
- 优化(optimization)：在所有的等价计划中选择一个最小成本的．
- 执行(evaluation)：执行查询计划并返回查询的答案．

Measures of Query Cost

查询成本的主要因素
- 磁盘存取（在大型数据库中，通常是主要代价，也是我们需要理论分析的）．
- 执行查询所需要的 CPU 时间．
- 在并行/分布式数据库系统中的网络通信代价．
在下文中，我们只考虑 块传输时间 和 寻道时间 作为成本度量．
- $t_{T}$ ：传输一个块的时间．
- $t_{S}$ ：单次寻道时间．
- $b$ 次块传输和 $S$ 次寻道的总成本为 $b \times t_{T} + S \times t_{S}$ ．
在一些查询处理过程中，主存中缓冲区的大小会影响查询成本．
- 默认讨论最坏情况——使用最少的内存开销．

Cost of Selection Operations

A1（线性搜索）：一次初始寻道加上 $b$ 个块传输． $t_{S} + b \times t_{T}$ ．
A1’（线性搜索，键属性等值比较）：最多一条记录满足要求，因此找到之后就可以停止，平均只需要一半的块传输（最坏情况下仍然需要 $b$ 次）． $t_{S} + (b/2)t_{T}$ ．
A2（主索引，键属性等值比较）：设 $h_{i}$ 为索引高度，需要 $h_{i} + 1$ 次 I/O 操作，每次操作对应一次寻道和一次块传输． $\left( h_{i} + 1 \right) \times \left( t_{T} + t_{S} \right)$ ．
A3（主索引，非键属性等值比较）：需要 $h_{i}$ 次 I/O 操作，最后因为是主索引，可以假定目标块都是连续存储的． $h_{i} \times \left( t_{T} + t_{S} \right) + t_{S} + b \times t_{T}$ ．
A4（辅助索引，键属性等值比较）：这种情况和主索引类似． $\left( h_{i} + 1 \right) \times \left( t_{S} + t_{T} \right)$ ．
A4’（辅助索引，非键属性等值比较）：设 $n$ 为所取记录数，这 $n$ 个记录的指针存储在 $m$ 个块中（因为 B+ 树的叶子可能存了不止一个块的数据）．则最坏情况下每个记录都在不同的块中，因此每条记录都需要一次额外的 I/O 操作． $\left( h_{i} + m + n \right) \times \left( t_{S} + t_{T} \right)$ ．
A5（主索引，比较）：与 A3 的情况类似．TBD
A6（辅助索引，比较）：与 A4” 的情况类似．TBD

Measures of Join Operations

算法	等值连接	非等值连接
Nested-Loop Join	支持	支持
Block Nested-Loop Join	支持	支持
Indexed Nested-Loop Join	支持	视索引而定
Merge Join	支持	本课程中不支持
Hash Join	支持	不支持

Nested-Loop Join

用于计算 $\theta$ 连接 $r\Join_{\theta}s$ ；称 $r$ 为 外关系(outer relation)， $s$ 为 内关系(inner relation)．
不需要索引，代价是时间开销大，对于每一对元组都需要检查．
最坏情况：内存只能容纳两个关系中的各一个块，则成本为 $\left( n_{r} + b_{r} \right) \times t_{S} + \left( n_{r} \times b_{s} + b_{r} \right) \times t_{T}$ ．
- 外关系遍历需要 $b_{r} \times \left( t_{S} + t_{T} \right)$ ，因为每轮都需要重新寻道．
- 对于 $n_{r}$ 个外关系元组中的每一个，都需要对内关系做一次扫描，共花费 $n_{r} \times \left( t_{S} + b_{s} \times t_{T} \right)$ ．
最好情况：若内关系能完全放入内存，成本可降低为 $2 \times t_{S} + \left( b_{r} + b_{s} \right) \times t_{T}$ ．
- 一开始先用 $t_{S} + b_{s} \times t_{T}$ 的代价将内关系全部读入内存，之后读入外关系时就不需要重新寻道．

Block Nested-Loop Join

最坏情况： $2b_{r} \times t_{S} + \left( b_{r} \times b_{s} + b_{r} \right) \times t_{T}$ ．
设用内存中的 $M - 2$ 个块来储存外关系，则成本可降低为： $2\left\lceil {b_{r}\text{ / }(M - 2)} \right\rceil \times t_{S} + \left( \left\lceil {b_{r}\text{ / }(M - 2)} \right\rceil \times b_{s} + b_{r} \right) \times t_{T}$ ．
- 这里 $M - 2$ 个块用于存储外关系，剩下一个块用于存储内关系，一个块用于结果输出．
- 具体做法是：每轮都取出 $M - 2$ 个块，然后需要 $2 \times t_{s} + \left( b_{s} + b_{r,i} \right) \times t_{T}$ 的代价进行处理（其中 $\sum b_{r,i} = b_{r}$ ），每次都需要重新寻道．
最好情况：退化为 nested-loop join 的最好情况， $2 \times t_{S} + \left( b_{r} + b_{s} \right) \times t_{T}$ ．
结论：
- 扫描时交替进行向前/向后循环，以利用缓冲区中的剩余块．
- 如果两个关系都不能完全放入内存中，那么将小关系作为外关系的效率更高．

Indexed Nested-Loop Join

条件：如果 (1) 连接是等值连接或者自然连接或者 (2) 内关系的连接属性上有索引（也可以专门为连接操作而建立），就可以用 index lookup 替换 file scan．
最坏情况：缓冲区仅能容纳 $r$ 的一个块，并且对于 $r$ 中的每个元组都需要在 $s$ 上进行一次索引查找． $b_{r} \times \left( t_{T} + t_{S} \right) + n_{r} \times c$ ，其中 $c$ 是使用连接条件进行索引查找的成本（需要另使用前面的方法计算）．

Merge Join

若两个关系都已经排序，则可使用类似归并排序的方法计算连接．如果关系未排序则需加上事先排序的代价．
条件：仅可用于等值连接和自然连接．
设分别为 $r$ 和 $s$ 分配了 $M$ 个块中的 $x_{r}$ 和 $x_{s}$ 个块（ $x_{r} + x_{s} + 1 = M$ ），则成本为： $\left( \left\lceil {b_{r}\text{ / }x_{r}} \right\rceil + \left\lceil {b_{s}\text{ / }x_{s}} \right\rceil \right) \times t_{S} + \left( b_{r} + b_{s} \right) \times t_{T}$ ．

Hash Join

本质上是分治的思想，通过哈希函数将两个关系的选择条件进行分区，只考虑在对应分区之间进行 build & probe．
使用哈希函数 $h$ 将关系中的连接属性映射到 $\left\{ 0,1,\ldots,n_{h} \right\}$ 上．
称外关系 $r$ 为 prob input，内关系 $s$ 为 build input．
算法流程：
- (1) partition：依次对 $r,s$ 进行分区并写回磁盘中．
- (2) build & probe：对于 $s$ 的每个分区 $s_{i}$ ，将其全部载入内存中，并遍历 $r_{i}$ 中的每个块依次载入内存中并进行连接．
为了确保 $S$ 中的单个分区都能被载入到内存中，一般取 $n_{h} \geq \left\lceil {b_{s}\text{ / }M} \right\rceil \times f$ ，取 $f = 1.2$ （下界）．
- $f$ 的选择动机在于哈希函数的分区不一定均匀，这不是一个绝对保险的选择．
- $R$ 中的分区无需载入内存，这里不需要考虑．
在分区过程中，要求 $n_{h} < M - 1$ （上界）；否则需要进行，则在分区时需要进行递归分区，否则需要进行 递归分区(recursive partitioning)．
综上， $\left\lceil {b_{s}\text{ / }M} \right\rceil \times f < n_{h} < M - 1$ ，合并可得条件 $M > \sqrt{b_{s}}$ ．

在不进行递归分区的情况下，使用 Hash-Join 最多能处理多大的关系？

对于 12M 内存，块大小设置为 4K．则内存中最多可放下 3K (= 12M / 4K) 个块，可对最大 3K $\times$ 3K 个块的关系进行分区并哈希连接，也就是 3K $\times$ 3K $\times$ 4K = 36G 大小的关系．

Problem: 练习卷1 T10

Assuming the table $r$ and $s$ has 256 and 1024 blocks respectively. Each block has 4K bytes. To do natural join $r$ and $s$ with the Hash Join algorithm, what is the approximate minimum memory needed to avoid recursive partitioning?

(A) 64K bytes　　(B) 128K bytes　　(C) 1M bytes　　(D) 2M bytes

Answer

A．易错选 B．

成本计算：
- 不考虑递归分区，保证没有哈希表溢出：
  - block-transfer
    - partition：关系中的每个块都需要从磁盘中取出，共 $b_{s} + b_{r}$ 次块传输；还需要按分区进行写回，并且 $n_{h}$ 个分区中的每一个都可能剩一个只装满了部分的块，共需 $b_{s} + b_{r} + 2n_{h}$ 次块传输．
    - build & probe：刚才每个写回的块都刚好需要被取出一次，共 $b_{s} + b_{r} + 2n_{h}$ 次块传输．
    - 成本： $\left( 3\left( b_{s} + b_{r} \right) + 4n_{h} \right) \times t_{T}$ ，这里的 $4n_{h}$ 非常小，有时可能忽略不计．
  - seek
    - partition：假设为输入输出缓冲区各分配了 $b_{b}$ 个块，则划分总共需要 $2\left( \left\lceil {b_{s}\text{ / }b_{b}} \right\rceil + \left\lceil {b_{r}\text{ / }b_{b}} \right\rceil \right)$ 次寻道．
    - build & probe：对于每个分区只需要进行一次寻道，总共 $2n_{h}$ 次．
    - 成本： $\left( 2\left( \left\lceil {b_{s}\text{ / }b_{b}} \right\rceil + \left\lceil {b_{r}\text{ / }b_{b}} \right\rceil \right) + 2n_{h} \right) \times t_{S}$ ．
- 递归分区的情况，每一次递归预计可以减小为原来的 $1/\left( \left\lfloor {M/b_{b}} \right\rfloor - 1 \right)$ 大小，共需要 $d = \left\lceil {\log_{\left\lfloor {M/b_{b}} \right\rfloor - 1}\left( b_{s} \right)} \right\rceil$ 次递归（这里的 $n_{h}$ 相关项忽略不计）．
  - block-transfer：
    - partition： $2\left( b_{s} + b_{r} \right) \times d$ 次块传输．
    - build & probe： $\left( b_{s} + b_{r} \right)$ 次块传输．
  - seek： $2\left( \left\lceil {b_{r}\text{ / }b_{b}} \right\rceil + \left\lceil {b_{s}\text{ / }b_{b}} \right\rceil \right) \times d \times t_{S}$ ．

Sorting

External Merge Sort

对于无法放入内存的关系，可以考虑使用 外部排序(external sort-merge)．
算法流程（简单版本）：
- Step 1：（初始化）每次读入 $M$ 个块到内存中，并在内存中进行排序，记为一个 run $R_{i}$ ，然后写回磁盘．设完成初始化后得到的 runs 总个数为 $N_{0}$ ．
- Step 2：（归并）
  - 如果 $N_{0} < M$ ，可以分配 $N_{0}$ 个块用于归并，再用一个块作为输出缓冲区．
  - 如果 $N_{0} \geq M$ ，则需要进行递归合并，在每一轮中，可合并连续的 $M - 1$ 个 runs，并让 runs 的总数量变为 $\left\lceil {N\text{ / }(M - 1)} \right\rceil$ ，递归直到所有 runs 合并为一个．
成本分析（简单版本）：
- 总 Runs 个数： $N_{0} = \left\lceil {b_{r}\text{ / }M} \right\rceil$ ．
- 总合并轮数： $d = \left\lceil {\log_{M - 1}\left( b_{r}\text{ / }M \right)} \right\rceil$ ．
- block-transfer：考虑对每个块进行分析，在每一轮中需要先读出再写入，不过需要注意最后一轮中不需要计算写入成本．共 $b_{r}(2d + 1) \times t_{T}$ ．
- seek：在初始化阶段一连 $M$ 个在读写时都只需要一次寻道，后面的话则仍是每个块一次，共 $\left( 2\left\lceil {b_{r}\text{ / }M} \right\rceil + b_{r}(2d - 1) \right) \times t_{S}$ ．
成本分析（升级版本）：
- Motivation：为了进一步减少寻道成本，将输入和输出缓冲区的大小都设置为 $b_{b}$ 个块，这样内存中就只能放下 $\left\lfloor {M\text{ / }b_{b}} \right\rfloor$ 个 runs 了．
- block-transfer：共 $b_{r}\left( 2\left\lceil {\log_{\left\lfloor {M\text{ / }b_{b}} \right\rfloor - 1}\left( b_{r}\text{ / }M \right)} \right\rceil + 1 \right)$ 次．
- seek：共 $2\left\lceil {b_{r}\text{ / }M} \right\rceil + \left\lceil {b_{r}\text{ / }b_{b}} \right\rceil\left( 2\left\lceil {\log_{\left\lfloor {M\text{ / }b_{b}} \right\rfloor - 1}\left( b_{r}\text{ / }M \right)} \right\rceil - 1 \right)$ 次．（前半部分是初始化，后半部分逐轮从每个 run 中读入块，每次读入都需要重新寻道；写入也需要重新寻道）
- 注意：默认不考虑最后一轮写回的 block-transfer 和 seek 成本．