查询处理

概述

查询处理的基本步骤：

  1. 语法分析与翻译
    查询处理中系统首先必须把查询语句翻译成系统的内部表示形式。该翻译过程类似于编译器的语法分析器所做的工作。在此过程中，语法分析器检查用户查询的语法，验证查询中出现的关系名是数据库中的关系名等。
    系统构造该查询语句的语法分析树表示，然后将之翻译成关系代数表达式。
  2. 优化
    查询执行引擎（query-execution engine）接受一个查询执行计划（query-execution engine），执行该计划并把结果返回给查询。
    给定查询的不同执行计划会有不同的代价。我们不能寄希望于用户写出具有最高效率执行计划的查询语句。相反，构造具有最小查询执行代价的查询执行计划应当是系统的责任。这项工作叫作查询优化。
  3. 执行

查询代价的度量

查询处理的代价可以通过该查询对各种资源的使用情况进行度量，这些资源包括磁盘存取、执行一个查询所用CPU时间，还有在并行/分布式数据库系统中的通信代价
在大型数据库系统中，在磁盘上存取数据的代价通常是最主要的代价，因为磁盘存取比内存操作速度慢。此外，CPU速度的提升比磁盘速度的提升要快的多，这样很可能花费在磁盘存取上的时间仍将决定整个查询的时间。
我们用传送磁盘块数以及搜索磁盘次数来度量查询计算计划的代价：
假设磁盘子系统传输一个块的数据平均消耗$t_T$秒，
磁盘块平均访问时间（磁盘搜索时间加上旋转延迟）为$t_S$秒，
则一次传输$b$个块以及执行$S$次磁盘搜索的操作将消耗秒
$t_T$和$t_S$的值必须针对所使用的磁盘系统进行计算，而如今高端磁盘的典型数值通常是$t_S = 4$毫秒和$t_T = 0.1$毫秒。

选择运算

使用文件扫描和索引的选择

  • 文件扫描（file scan）：
    在查询处理中，文件扫描是存取数据最低级的操作。文件扫描是用于定位、检索满足选择条件的记录的搜索算法。在关系系统中，若关系保存在单个专用的文件中，采用文件扫描就可以读取整个关系。
    线性搜索和二分搜索属于文件扫描
  • 索引扫描（index scan）：
    使用索引的搜索算法称为索引扫描。我们用选择谓词来指导我们在查询处理中使用哪个索引。
  1. 线性搜索（linear search）：
    系统扫描每一个文件块，对所有记录都进行测试，看它们是否满足选择条件。
    开销： 一次初始搜索加上$b_r$个块运输，$b_r$表示在文件中的块数量
    若使用码属性值比较，则平均开销： 因为最多一条记录满足条件，所以只要找到所需的记录，扫描就可以终止。在最坏的情况下，仍需要$b_r$个块传输。
    虽然线性搜索比其他实现操作的算法速度要慢，但它可用于任何文件，不用管该文件的顺序、索引的可用性，以及选择操作的种类。
  2. 二分搜索（binary search）：
    只有在等值比较且按序排列的情况下可以用
    开销：
  3. $B^+$树，主索引，码属性，等值比较：
    开销：
    $h_i$表示索引的高度。索引查找穿越树的高度，再加上一次I/O来取记录；每个这样的I/O操作需要一次搜索和块传输
  4. $B^+$树，主索引，非码属性，等值比较：
    开销：
    树的每层一次搜索，第一个块一次搜索。$b$是包含具有指定搜索码记录的块数。
  5. $B^+$树，辅助索引，码属性，等值比较：
    开销：
    这种情形和主索引相似
  6. $B^+$树，辅助索引，非码属性，等值比较：
    开销：
    $n$是记录数，索引查找的代价和4类似，但是每条记录可能在不同的块上，这需要每条记录一次搜索。如果$n$值比较大，代价可能会非常高。
  7. $B^+$树，主索引，比较：
    开销：
    和主索引，非码属性，等值比较情形一样
    形如$A geq v$，我们在索引中寻找值$v$，以检索出满足条件$A = v$的首条记录。从该元组开始到文件末尾进行一次文件扫描就返回所有满足该条件的元组。形如$A > v$，文件扫描从第一条满足$A > v$的记录开始。
    若为$A < v 或 A leq v$的比较式，从文件头开始进行文件扫描，直到遇上首条满足$A = v 或 A > v$的元组为止。
  8. $B^+$树，辅助索引，比较：
    开销：
    和辅助索引，非码属性，等值比较情形一样
    对于$ leq$情形，扫描最底层索引块是从最小值开始直到$v$为止
    对于$ geq$情形，扫描是从$v$开始直到最大值为止
    辅助索引提供了指向记录的指针，但我们需要使用指针以取得实际的记录。由于连续的记录可能存在于不同的磁盘块中，因此每取一条记录可能需要一次I/O操作，即需要一次磁盘搜索和一次块传输。
    如果检索得到的记录数很大的话，使用辅助索引的代价甚至比线性搜索还要大，因此辅助索引应该仅在选择得到的记录很少时使用。

复杂选择的实现

合取选择（Conjunctive Selections)

利用一个索引实现：

  1. 从上述的选择运算中选出对于$sigma_{theta_i}(r)$开销最小的算法来查找$theta_i$
  2. 在内存缓冲区中，我们通过测试每条检索到的记录是否满足其余的简单条件。

在这个事件中，如何去选取第一个条件是十分重要的

使用组合索引的合取选择：
使用合适的组合索引(composite index)，即在多个属性上建立的一个索引来检索。

析取选择（Disjunctive Selections)

通过标识符的交：

  • 线性扫描
  • 如果在析取选择中所有条件上均有相应的存取路径存在，则逐个扫描索引获取满足单个条件的元组指针。检索到的所有指针的并集就是指向满足析取条件的额所有元组的指针集。然后利用这些指针检索实际的记录

取反

  • 线性扫描
  • 如果有相应的存取路径：
    利用索引找到符合的记录，$sigma_{neg theta}(r) 就是在$r$中对条件$theta$取值为假的元组的集合

删除重复值

重复值的删除可以通过散列或分类来实现

排序

数据排序在数据库系统中有重要的作用：

  1. SQL查询会指明对结果进行排序
  2. 当输入的关系已排序时，关系运算中的一些运算（如连接运算）能够得到高效实现。

通过在排序码上建立索引，然后使用该索引按序读取关系，可以完成对关系的排序。然而，这一过程仅仅在逻辑上通过索引对关系排序，而没有在物理上排序。因此，顺序读取元组可能导致每读一个元组就要访问一次磁盘。

外部排序归并算法

对于内存中能够完全容纳关系的话，可以利用标准的排序技术（如快速排序）

对不能全部放在内存中的关系的排序称为外排序（external sorting）。外排序中最常用的技术是外部排序归并（external sort-merge)算法。

令$M$表示内存缓冲区中可以用于排序的块数，即内存的缓冲区能容纳的磁盘块数。

  1. 建立多个排好序的归并段（run）。每个归并段都是排序过的，但仅包含关系中的部分记录。

    1
    2
    3
    4
    5
    6
    7
    i = 0;
    repeat
          读入关系的$M$块数据或剩下的不足$M$块数据；
          在内存中对关系的这一部分进行排序；
          将排好序的数据写到归并段文件$R_i$中；
          $i = i + 1$
    until 到达关系末尾

  2. 对归并段进行归并，暂时假定归并段的总数$N$小于$M$,这样我们可以为每个归并段文件分配一个块，此外剩下的空间还应能容纳存放结果的一个块。为$N$个归并段文件$R_i$各分配一个内存缓冲块，并分别读入一个数据块：

    1
    2
    3
    4
    5
    6
    repeat
          在所有缓冲块中按序挑选第一个元组；
          把该元组作为输出写出，并将其从缓冲块中删除；
          if 任何一个归并段文件$R_i$的缓冲块为空并且没有到达$R_i$末尾
               then 读入$R_i$的下一块到相应的缓冲块
    until 所有的缓冲块均为空

  3. 如果关系比内存大的多，则在第一阶段可能产生$M$个甚至更多的归并段，在这种情况下，归并操作需要分多躺进行。由于内存足以容纳$M - 1$个缓冲块，因此每趟归并可以用$M - 1$个归并段作为输入
    最初的那趟归并过程：头$M - 1$个归并段如前第2⃣️点所述进行归并得到一个归并段作为下一趟的输入。接下来的$M - 1$个归并段类似的进行归并，如此下去，知道所有的初始归并段都处理过为止。此时，归并段的数目减少到原来的$1/(M - 1)$，如果归并后的归并段数目仍大于等于$M$，则以上一趟归并创建的归并段作为输入进行下一趟归并，直到归并段数目小于$M$

外部排序归并的代价分析

假定$b_r$表示关系$r$中记录的磁盘块数，$M$表示内存缓冲区中可以用于排序的块数，$b_b$表示缓冲块（每次读取$b_b$块从每个归并段。

  • 磁盘块传输的总数：
  • 磁盘搜索的总次数：

连接运算

嵌套循环连接(Nested-Loop Join)

最简单的连接算法

1
2
3
4
5
6
for each 元组 $t_r$ in r do begin
         for each 元组 $t_s$ in s do begin
                  测试元组对（t_r, t_s)是否满足连接条件theta
                  如果满足，把t_r t_s加到结果中
         end
end

关系$r$称为连接的外层关系（outer relation），而$s$称为连接的内层关系（inner relation）。
与选择算法中使用的线性文件扫描算法类似，嵌套循环连接算法不要求有索引，并且不管连接条件是什么，该算法均可以使用。将其变为自然连接只需要删除$t_r t_s$的重复属性。 嵌套连接算法的代价很大，因为该算法逐个检查两个关系中的每一对元组。*

我们假设$n_r$和$n_s$分别表示$r$和$s$中的元组数，$b_r$和$b_s$分别代表包含关系$r$和$s$中元组的磁盘块数
在最坏的情况下，缓冲区只能容纳每个关系的一个数据块：

  • 共需$n_r * b_s + b_r$次块传输
  • 共需$n_r + b_r$次磁盘搜索，*对每次扫描内层关系$s$我们只需一次磁盘搜索，读取关系$r$一共需要$b_r$次磁盘搜索

在最好的情况下，内存有足够的空间同时容纳两个关系，此时每一数据块只需读一次

  • $b_r + b_s$块传输
  • 2次磁盘搜索

如果只有一个关系能完全放在内存中，那么把内层关系作为这个关系来处理是有好处的。因为这样内层循环只需要读一次，如果把$s$小到可以装入内存，那么我们的策略只需$b_r + b_s$次块传输和两次磁盘搜索，其代价与两个关系能同时装入内存的情形相同。

块嵌套循环连接（Block Nested-Loop Join)

因缓冲区太小而内存不足以完全容纳任何一个关系时，如果我们以块的方式而不是以元组的方式处理关系，仍然可以减少不少块读写次数

1
2
3
4
5
6
7
8
9
10
for each 块 B_r of r do begin
    for each 块 B_s of s do begin
       for each 元组 t_r in B_r do begin
          for each 元组 t_s in B_s do begin
              测试元组对(t_r, t_s)是否满足连接条件
              如果满足，把t_r * t_s加到结果中
          end
       end
    end
end

在最坏的情况下：

  • 共需$b_r * b_s + b_r$次块传输
  • 共需$2b_r$次磁盘搜索

在最好的情况下，内存能够容纳内层关系:

  • $b_r + b_s$次块传输
  • 2次磁盘搜索

进一步改进嵌套循环和块嵌套循环：通过对内层循环轮流做向前、向后的扫描。该扫描方法对磁盘块读写请求进行排序，使得上一次扫描时留在缓冲区的数据可以重用，从而减少磁盘存取次数

索引嵌套循环连接（Indexed Nested Loop Join)

在嵌套循环连接中，若在内层循环的连接属性上有索引，则可以用索引查找替代文件扫描。对于外层关系$r$的每一个元组$t_r$，可以利用索引查找$s$中和元组$t_r$满足连接的元组

最坏的情况下，缓冲区只能容纳关系$r$的一块和索引的一块。
这种状况下，连接的开销为：$b_r + n_r c$次*块传输和磁盘搜索
$c$是使用连接条件对关系$s$进行单次选择操作的代价

代价公式表明，如果两个关系$r, s$上均有索引时，一般把元组较少的关系做外层关系时效果更好

归并连接(Merge Join)

归并连接算法（又称排序—归并—连接（sort-merge join)算法）可用于计算自然连接和等值连接

假设所有集合$S_s$都能被装进内存，这时的开销是：

  • $b_r + b_s$次磁盘块传输
  • 次磁盘搜索

*若任意一个输入关系$r$或$s$未能按属性排序，那么必须先对它们排序。

散列连接（Hash-Join）

类似于归并连接算法，散列连接算法可用于实现自然连接和等值连接。
在散列连接算法中，用散列函数$h$来划分两个关系的元组

基本思想：如果关系$r$的一个元组与关系$s$的一个元组满足连接条件，那么它们在连接属性上就会有相同的值。若该值经散列函数映射到$i$，则关系$r$的那个元组必在$r_i$中，而关系$s$中的元组必在$s_i$中。因此，$r_i$中的元组$r$只需要与$s_i$中的元组$s$相比较，而没有必要与其他任何划分里的元组$s$相比较。

关系$s$被称为构造用输入（build input），关系$r$被称为探查用输入（probe input）

应选择足够大的$n_h$值，以使对于任意的$i$，内存中可以容纳构造用输入关系的划分$s_i$中的元组以及划分上的散列索引。
一般我们使$n = lceil b_s/M rceil f$，$f$被称为*避让因子(fudge factor)，一般$f$在1.2左右来避开溢出情况。

散列连接的代价：

  • $3(b_r + b_s) + 4 * n_h$ 块传输
  • 次磁盘搜索

其他运算

去除重复(Duplicate Elimination)

  • 我们可以用排序方式很容易地实现去除重复：
    最坏情况去除重复的代价估计与最坏情况对该关系的排序代价估计一样
  • 也可以用散列来实现去除重复：
    其代价估算与散列连接中构造用输入关系的处理（划分以及读入每个划分）的代价一样

投影(Projection)

聚集(Aggregation)

聚集运算可以用去除重复类似的方法来实现，我们使用排序或散列。但是，我们不是去除在分组属性上有相同值的元组，而是将之聚集成组，并对每一组应用聚集运算以获取结果。
如果结果集的元组可以装入内存，则基于排序的实现方法与基于散列的实现方法不必将元组写到磁盘上