跳转至

Chapter 11 Query Processing

文本统计：约 1103 个字 • 3 行代码

Info

本文参考 查询处理 - Zhroyn 的学习笔记

11.1 Basic Steps in Query Processing

  • 解析和翻译 (Parsing and translation)：先将查询转换为中序形式，再将其转换为关系代数，同时需要检查语法
  • 优化 (Optimization)：一句 SQL 查询可能有多个等价的关系代数表达式，需要估计代价，选择代价最小的评估计划
  • 评估 (Evaluation)：The query-execution engine takes a query-evaluation plan, executes that plan, and returns the answers to the query.

Example

初始的 SQL 语句为 

select name, title 
from instructor natural join (teaches natural join course)
where dept_name=‘Music’ and year = 2009;

转化为关系代数语句

\[ \Pi_{\text{name},\text{title}}(\sigma_{\text{dept}\_{name}=\text{"Music"}\cap\text{year}=2009}(\text{instructor}\bowtie(\text{teaches}\bowtie(\text{course})))) \]

对表达式进行优化

An evaluation plan defines exactly what algorithm is used for each operation, and how the execution of the operations is coordinated.

如果我们想要看到具体的查询方案，多数数据库系统都支持语句 explain <query>

Cost is generally measured as total elapsed time for answering query，有很多因素会影响时间消耗，比如说磁盘访问，CPU速度，网络连接等等，但是一般来说磁盘访问的时间占据主导，同时也是最好估计的那一个。

查询的代价来源有磁盘寻道 (seek)、块读取 (block read)、块写入 (block written)、CPU 等。在这里，我们将块读取和块写入合并为块传输 (block transfer)。

在计算代价时，我们只考虑 block transfer 和 seek，将其次数分别定义为 \(b\) 和 \(S\)，时间分别定义为 \(t_T\) 和 \(t_S\)，则代价为 \(b×t_T+S×t_S\)，通常 \(t_T<<t_S\)。

11.2 Select Operation

File Scan

A1 (linear search)

  • 假定所有的块都放在一起，因此只需要 seek 一次，最坏代价为 \(b_r×tT+t_S\)，平均代价为 \((b_r/2)×t_T+t_S\)，其中 \(b_r\) 为存储关系 \(r\) 的所有记录的块的数目

  • 线性搜索可以应用于任何情况，无论选择条件、文件中记录的顺序或索引的存在与否。

二分查找的局限性

由于数据通常不是连续存储的，因此二分查找通常没有意义。

例外情况：当有可用的索引时，二分查找可能比线性搜索更有效，但通常情况下，索引查找比二分查找更高效，因为索引查找所需的寻道次数更少。

Selections Using Indices

利用索引进行查找，所以查询条件必须要是索引的搜索键

A2 (primary B+-tree index, equality on key)

  • 使用 B+ 树搜索一条记录，搜索的是主索引，并且是键，只有一条记录
  • cost=\((h_i+1)×(t_T+t_S)\) 对于每一层需要一次寻找和传输时间，然后最后到文件中还需要有一次寻找和传输的时间

A3 (primary B+-tree index, equality on nonkey)

  • 因为是 nonkey，可能会搜索多条记录，且因为为主索引，想要的结果会存储在连续的块中
  • cost=\(h_i×(t_T+t_S)+t_S+t_T×b\)，其中 \(b\) 为包含匹配记录的块的数目

A4 (secondary B+-tree index, equality on key)

  • 并不是主索引（记录不是按照该值来排列的），但是为键（只有一条记录）

  • cost= \((h_i+1)×(t_T+t_S)\)

Selections Involving Comparisons

A4’ (secondary B+-tree index, equality on nonkey)

  • 会检索 \(n\) 条记录，不一定在同一个块上面，设共分布在 \(m\) 个块上
  • cost=\((h_i+m+n)×(t_T+t_S)\) 叶子节点存储的是 \(m\) 条记录的位置，每个记录都需要一次搜索和传输

A5 (primary B+-tree index, comparison)

  • 对于大于比较来说，代价为 \(h_i×(t_T+t_S)+t_S+t_T×b\)，对于小于比较来说，只需要从头扫描即可

A6 (secondary B+-tree index, comparison)

对于次级索引，我们只能一个个寻找，小于的话就从叶子节点的头开始找起，大于就先找到相应的起始点，然后往后寻找即可。这样每一个记录都需要一次 I/O 操作，可能还不如线性查找更快。

Implementation of Complex Selections

Conjunction: \(\sigma_{\theta_1\land\theta_2\land\dots\land\theta_n}(r)\)

A7 (conjunctive selection using one index)

  • Select a combination of \(\theta_i\) and algorithms A1 through A6 that results in the least cost for \(\sigma_{\theta_i} (r)\). 使用一个索引进行查找，然后对得到的结果进行检验

A8 (conjunctive selection using composite index)

  • Use appropriate composite (multiple-key) index if available. 将多个属性作为索引值进行查找

A9 (conjunctive selection by intersection of identifiers)

  • Requires indices with record pointers.
  • Use corresponding index for each condition, and take intersection of all the obtained sets of record pointers. 每一个索引得到的指针进行合取
  • Then fetch records from file
  • If some conditions do not have appropriate indices, apply test in memory.

Disjunction: \(\sigma_{\theta_1\lor\theta_2\lor\dots\lor\theta_n}(r)\)

A10 (disjunctive selection by union of identifiers).

整个思路与 A9 差不多，这里不再赘述

11.3 Sorting

We may build an index on the relation, and then use the index to read the relation in sorted order. May lead to one disk block access for each tuple.

For relations that fit in memory, techniques like quick-sort can be used. 如果可以直接放到内存中，那么可以直接通过快速排序完成

For relations that don’t fit in memory, external sort-merge is a good choice. 如果放不进去，那么就要采用外排序的方法。外排序的方法在 ADS 这门课中的 Lecture 15 中详细阐述

设内存页的数量为 \(M\)，在外部排序开始时，我们会依次将 \(b_r\) 个块读入内存，进行排序，然后写回磁盘，生成 \(⌈b_r/M⌉\) 归并段 (runs)。

如果归并段少于可用内存页 (\(N<M\))，则可以一次性将所有归并段的第一个块分别读入到 \(N\) 个缓冲页中，将合并结果输出到另一个缓冲页，每当 output buffer 满了就写回磁盘，只需要一次 pass 就可以完成合并。

如果归并段不少于可用内存页 (\(N≥M\))，则需要多次 pass，每次以 \(M−1\) 为单位将归并段分组，每组合并为一个新的归并段，这样每次 pass 后归并段的数量都会除以 \(M−1\)，直到最后只剩下一个归并段。

在这种简单的情况下，merge passes 的次数为 \(⌈\log_{⁡M−1}⌈b_r/M⌉⌉\)，整个外部排序的代价为：

block transfer 的代价

  • 创建归并段所需的 block transfer 为 \(2b_r\)，每次 pass 的 block transfer 也为 \(2b_r\)
  • 我们可以不考虑最终的 pass 的输出代价，因为它会输出到父操作而不是磁盘中，因此最终的 pass 的代价为 \(b_r\)
  • 因此，简单版的外部排序所需的 block transfer 次数为 \(2b_r⌈\log_{⁡M−1}⌈b_r/M⌉⌉+b_r=b_r(2⌈\log_{⁡M−1}⌈b_r/M⌉⌉+1)\)

seek 的代价

  • 在创建归并段时，读写归并段都需要一次 seek，因此总代价为 \(2⌈b_r/M⌉\)
  • 在合并归并段时，每次 pass 的代价都为 \(2b_r\)，除了最终的 pass
  • 因此，简单版的外部排序所需的 seek 次数为 \(2⌈b_r/M⌉+b_r(2⌈\log_{⁡M−1}⌈b_r/M⌉⌉−1)\)

这个版本的算法的问题是，每个归并段同时只处理一个块，导致在合并时每个块都需要一次 seek。我们考虑每个归并段同时读入 \(b_b\) 个块，这样的话，每次 pass 的 seek 次数就会下降到 \(2⌈b_r/b_b⌉\)，但同时，每次合并参与的段数量也会下降到 \(⌊M/b_b⌋−1\)，导致合并次数上升，最终代价变为：

  • block transfer: \(b_r(2⌈\log⁡⌊M/b_b⌋−1⌈b_r/M⌉⌉+1)\)
  • seek: \(2⌈b_r/M⌉+⌈b_r/b_b⌉(2⌈\log⁡_{⌊M/b_b⌋−1}⌈b_r/M⌉⌉−1)\)

11.4 Join Operation

Nested-Loop Join

\(r⋈_θs\) 的计算方法是逐一比较 \((t_r,t_s)\) 是否满足条件 \(θ\)。在顺序扫描的情况下：

  • 每进入一次外层循环的循环体，就会顺序读入内层关系的所有块，block transfer 的开销为 \(b_s\) 除以每次读入的块数目，seek 的开销为 1，最后的总开销会乘以外层循环的次数
  • 每当外层关系在内存中的块都已处理完毕，就会重新读入一次外层关系的块，block transfer 的总开销为 \(b_r\) 除以每次读入的块数目，seek 的开销与之相同（如果不切换的话就是 1）
  • 因此，block transfer 的代价为 外层循环次数 X 内层关系传输次数 + 外层关系传输次数，seek 的代价为 外层循环次数 + 外层关系传输次数。

具体的公式是：

(1) Nested-Loop Join: 对于 \(r\) 中的每个元组 \(t_r\)，都要扫描一遍 \(s\)

  • 在最坏的情况下，内存只能存下每个关系的一个块，此时因为需要频繁地切换 \(s\) 的块，block transfer 的代价为 \(n_r×b_s+b_r\)，seek 的代价为 \(n_r+b_r\)
  • 在最好的情况下，内存可以存下 \(s\) 的所有块，此时 block transfer 的代价为 \(b_s+b_r\)，seek 的代价为 \(2\)

(2) Block Nested-Loop Join: 最外两层循环是遍历 \(r\) 的块和 \(s\) 的块，最内两层循环是遍历块中 \(r\) 的元组和 \(s\) 的元组

  • 在最坏的情况下，\(n_r\) 被优化为了 \(b_r\)，block transfer 的代价变为 \(b_r×b_s+b_r\)，seek 的代价变为 \(2×b_r\)
  • 在最好的情况下，block transfer 的代价为 \(b_r+b_s\)，seek 的代价为 \(2\)
  • 在优化的算法中，每次外层关系可以读入 \(M−2\)个块，内层关系可以读入 1 个块，内存剩下一个块用作输出缓冲，此时 block transfer 的代价为 \(⌈b_r/(M−2)⌉×b_s+b_r\)，seek 的代价为 \(2⌈b_r/(M−2)⌉\)

(3) Indexed Nested-Loop Join: 当连接条件是相等时，或者连接是自然连接时，我们可以使用索引扫描来加速连接操作。此时连接操作的代价为 \(b_r(t_T+t_S)+n_r×c\)，其中 \(c\) 是查询索引并返回匹配元组的代价，一般是树的高度加一。

Merge Join

Merge-Join: 适用于等值连接和自然连接，具体做法就是先让两个关系在连接属性上排序，然后逐一比较合并。这样的话，block transfer 的代价为 \(b_r+b_s\)，seek 的代价为 \(⌈b_r/b_b⌉+⌈b_s/b_b⌉\) 或 \(⌈b_r/x_r⌉+⌈b_s/x_s⌉\)，其中 \(b_b\)、\(x_r\)、\(x_s\) 都是内存能够一次性读入的块数目，\(x_r+x_s=M\)。

Hybrid Merge-Join: 当一个关系有序，另一个关系在连接属性上拥有 secondary index (B+树索引) 时，可以先把排序关系和未排序关系 B+ 树的叶子做 merge，再按照未排序关系指针指向的地址排序（这样之后就可以顺序扫描），最后再将指针替换为记录，拼接成结果。

Hash Join

在 Hash-Join 中，我们可以把要 join 的属性按近似程度分类，这样只用比较同一类的属性就可以了，大大减少了比较的次数。

哈希函数 \(h\) 会对两个关系中具有共同连接属性 (JoinAttrs) 的元组进行分区 (partition)，将连接属性的值映射到 \(\{0, 1,⋯,n\}\)，\(r_i\) 中的元组只需要和 \(s_i\) 中的元组比较即可。

具体的过程如下

（1）Partition s using hashing function h. When partitioning a relation, one block of memory is reserved as the output buffer for each partition.

（2）Partition r similarly.

（3）For each i:

  • Load \(s_i\) into memory and build an in-memory hash index on it using the join attribute. This hash index uses a different hash function than the earlier one \(h\).
  • Read the tuples in \(r_i\) from the disk one by one. For each tuple tr locate each matching tuple \(t_s\) in \(s_i\) using the in-memory hash index. Output the concatenation of their attributes.

我们设小的关系为 \(s\)，称作 build input，大的关系为 \(r\)，称作 probe input。

Note

the value \(n\) and the hash function \(h\) is chosen such that each \(s_i\) should fit in memory. \(n\ge\lceil b_s/M\rceil\)

这样进行分区之后，在 \(r_i\) 中的元组只需要和 \(s_i\) 中的 block 的元组来比较即可，要求 \(s_i\) 必须可以直接放到内存中，减少搜索次数 。

一般最后一级的哈希函数是 \(n_h=⌈b_s/M⌉∗f\)，\(f\) 为修正因子（通常为 1.2）。

Recursive partitioning

Recursive partitioning required if number of partitions n is greater than number of pages \(M\) of memory.

Instead of partitioning n ways, use \(M – 1\) partitions for \(s\)

Further partition the \(M – 1\) partitions using a different hash function

Use same partitioning method on \(r\)

A relation does not need recursive partitioning if \(M > n_h + 1\), or equivalently \(M > (b_s/M) + 1\), which simplifies (approximately) to \(M > \sqrt{b_s}\).

如果不需要递归分区，哈希连接的代价是：

  • block transfers: \(3(b_r+b_s)+4n_h\)

对 \(r\) 和 \(s\) 的分区要求完全读取这两个关系，并随后将它们写回，此操作需要 \(2(b_r+b_s)\) 次块传输。构建和探测阶段各自读取每个分区一次，需要进一步进行 \(b_r+b_s\) 次块传输。由于部分填充的块，分区占用的块数可能会稍多于 \(b_r+b_s\)。访问这样的部分填充的块可能会为每个关系增加最多 \(2n_h\) 的开销，因为每个 \(n_h\) 分区都可能有一个必须写入和读回的部分填充的块

  • seek: \(2(⌈b_r/b_b⌉+⌈b_s/b_b⌉)+2n_h\)

假设为每个输入缓冲区和每个输出缓冲区分配 \(b_b\) 个块，分区阶段总共需要 \(2(⌈b_r/b_b⌉+⌈b_s/b_b⌉)\) 次查找。构建和探测阶段只需要对每个关系的 \(n_h\) 个分区进行一次查找，因为每个分区都可以按顺序读取

如果需要递归分区，哈希连接的代价是：

  • 对构建关系 \(s\) 进行分区，以便每个分区少于 \(M\) 个块所需的传递次数是 \(⌈\log⁡_{⌊M/b_b⌋−1}⌈b_s/M⌉⌉\)，因此最好选择较小的关系作为构建关系
  • block transfer: \(2(b_r+b_s)\lceil\log_{⁡⌊M/b_b⌋−1}⌈b_s/M⌉⌉+b_r+b_s\)
  • seek: \(2(⌈b_r/b_b⌉+⌈b_s/b_b⌉)\lceil\log⁡_{⌊M/b_b⌋−1}⌈b_s/M⌉⌉\)

如果所有东西都能放进主存里且不需要 partition，则 \(n_h=0\)，代价降低为 \(b_r+b_s\)。

11.5 Other Operation

Duplicate elimination can be implemented via hashing or sorting.

  • On sorting duplicates will come adjacent to each other, and all but one set of duplicates can be deleted.
  • Optimization: duplicates can be deleted during run generation as well as at intermediate merge steps in external sort-merge. 生成排序段的过程中就可以把重复的给去掉了
  • Hashing is similar – duplicates will come into the same bucket.

Projection:

  • perform projection on each tuple
  • followed by duplicate elimination.

Aggregation can be implemented in a manner similar to duplicate elimination.

  • Sorting or hashing can be used to bring tuples in the same group together, and then the aggregate functions can be applied on each group.

  • Optimization: combine tuples in the same group during run generation and intermediate merges, by computing partial aggregate values 生成排序段的过程生成局部的结果

Set operations (\(\cup\), \(\cap\) and \(-\)): can either use variant of merge-join after sorting, or variant of hash-join.

11.6 Evaluation of Expressions

如何指向相应的表达式有两种方法

Materialization(物化): generate results of an expression whose inputs are relations or are already computed, materialize (store) it on disk. Repeat.

Example

in figure below, compute and store \(\sigma_{building = \text{"Watson"}}(department)\)

then compute the store its join with instructor, and finally compute the projection on name.

Pipelining（流水线）: pass on tuples to parent operations even as an operation is being executed

Example

in previous expression tree, don’t store result of \(\sigma_{building = \text{"Watson"}}(department)\) instead, pass tuples directly to the join.. Similarly, don’t store result of join, pass tuples directly to projection.

Much cheaper than materialization: no need to store a temporary relation to disk.

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！