简介

   SQL的查询分为两个过程。一是SQL语句解析，二是SQL语句执行。第一个过程会将SQL涉及的操作进行分解，并应用一些代数理论，将查询过程进行一些优化，比如将选择操作提前，这样可以减少后续操作的数据量。第二个过程会根据关系的一些元数据和目前可用的内存等参数，选择合适的查询算法。本教程会详细介绍SQL的各种查询算法及适用场景。

    SQL查询算法大致分为一趟算法，两趟算法和多趟算法，一趟算法只需读一次磁盘，但需要较多内存。两趟算法需要先读一次磁盘，在内存中对数据进行某些处理后将处理的结果写会磁盘，再读取一次进行最终的处理。多躺算法和两趟算法原理一致，只不过需要更多次读写操作，本教程重点描述一趟算法和两趟算法。

为描述算法的性能和使用场景，需要一些参数用于描述，主要有三个参数：

B(R):关系R的所有元组所需的块的数目。

T(R):关系R的元组数目

 V(R,a)：关系R中a对应列上不同值的数目

关系的操作符可以分为三大类，如下：

1 一次单个元组，一元操作。这类操作（选择和投影）不需要一次在内存中装入整个关系，甚至也不需要关系的大部分。这样，我们一次读一个磁盘块，使用内存缓冲区产生输出。

2 整个关系，一元操作。这类操作（分组和去重）需要一次从内存中看到所有或大部分元组。

3 整个关系，二元操作。这类操作比如交集，并集，差集，连接等。

一趟算法

一次单个元组

一次单个元组的选择运算和投影运算较为简单，一次读取R的一个数据块到内存缓冲区即可，无论B(R)有多大，我们只要求输入缓冲区满足即可,如下图所示

整个关系的一元操作

消除重复

为了消除重复，我们可以一次一个的读取R的每一块，但对于每一个元组，我们需要判定：

1 这是我们第一次看到这个元组，这是将它复制到输出

2 我们从前没见过这个元组，这时不必输出它

如下图所示，我们需要一个缓冲区来存储关系R中的非重复元组，所以要求

分组

分组操作给我们零个或多个分组属性以及可能的一个或多个聚集属性。如果我们在内存中为每一个组创建一个项，我们就可以一次一块地扫描R的元组，并根据每一个元组的值来更新对应的聚集属性，常见的聚集属性包括最小值，最大值，count，平均值等。

整个关系的二元操作

关系的二元操作(R和S)包含并，交，差，积和连接。一般要求将一个较小的关系S读入内存，另一个关系一次一块的进行处理，这样只需要满足即可

集合并

我们将S读到内存的M-1个缓冲区并建立一个查找结果，其查找关键字是整个元组。所有这些元组也都将复制到输出。然后我们一次一块的将R的每一块读到第M个缓冲区。对于R的每一个元组t，我们观察t是否在S中，如果不在，我们就将t复制到输出。如果t在S中，忽略即可。

集合交

将S读到M-1个缓冲区并建立整个元组作为查找关键字的查找结果。读取R的每一个块，并且对R的每一个元组t，观察t是否也在S中，如果在，我们将t复制到输出，如果不在，则忽略t。

集合差

将S读到M-1个缓冲区并建立整个元组作为查找关键字的查找结果。

为计算R-S，我们读取R的每一个块并检查块中的每一个元组t。如果t在S中，那么忽略t。如果t不在S中，则将t复制到输出。

为计算S-R，我们读取R的每一个块，并以此检查每一个元组t。如果t在S中，那么我们从内存S的副本里删除t，而如果t不在S中，不做任何处理。在考虑完R的每一个元组后，将S中剩余的元组复制到输出。

包并

这个比较特殊，对R和S都一次一块的进行处理，并将每一个元组都复制到输出即可。

包交

将S读到M-1个缓冲区，我们把每一个不同的元组与一个计数联系起来，其初始值是该元组在S中出现的次数。元组t的多个副本并不分别存储。接着，我们读取R的每一块，并对R的每一个元组t，我们观察t是否在S中出现。如果不出现，那么我们忽略t。如果t在S中出现，并且与t对应的计数值仍为正值，那么我们输出t并将计数减1.如果t在S中出现，但是它的计数器已经到0，那么我们仍不输出t。

包差

为计算S-R，我们将S的元组读到内存中，并统计每个不同元组出现的次数。对R的每个元组t，观察t是否在S中出现，如果是，我们将对应的计数减1.组后，我们将内存中计数是正数的每一个元组复制到输出，并且复制它的次数等于其计数。

为计算R-S，我们也将S复制到内存，对R的每一个元组t，我们观察t是否在S中出现。如果不出现，我们将t复制到输出。如果t确实在S中出现，那么我们看与t对应的计数c的当前值。如果c=0，那么我们将t复制到输出。如果c>0,那么不将t复制到输出，但是将c值减1.

积

将S读到内存的M-1个缓冲区，不需要特殊的数据结构。然后读取R的每一个块，并且对R的每一个元组t，将t与内存中S的每一个元组连接并输出。

自然连接

假设R(X,Y)与S(Y,Z)连接。读取S的所有元组，并且用它们构造一个以Y的属性为查找关键字的内存查找结构，将内存的M-1块用于这一目的。将R的每一块读到剩下的一个缓冲区中，对R的每一个元组t，利用查找结构找到S中与t在Y的所有属性上相符合的元组。对于S中每一个匹配的元组，将它与t连接后形成一个新的元组并输出。

嵌套循环连接

该算法其实思路很简单，即嵌套循环遍历两个关系的所有元组。算法优点是可以适用于任何大小的关系，没必要有一个关系必须能装入内存中，具体来说，遍历的时候可以按元组依次遍历，也可以按块依次遍历，原理都一样。按块遍历的算法如下：

分析一下上面的算法，外层迭代次数书B(S)/M-1,每一次迭代时，我们读取S的M-1个块和R的B(R)个块，总的磁盘读取数量为B(S)(M-1+B(R))/(M-1),近似为B(S)B(R)/M.

迄今为止的算法总结如下：

基于排序的两趟算法

原理是利用外部排序算法的思路，对一个很大的关系R（无法一次读到内存）进行排序，排序过程中完成关系的各种操作，可大致分为两个阶段：

阶段1:不断将R中的元组放入M个缓冲区，利用内存排序算法对它们进行排序，并将排序得到的子表存入磁盘

阶段2:将排好序的字表进行归并。在这个阶段，最多能对M-1个有序字表进行归并，这就限制了R的大小。即需要满足,或者近似为。

该算法称为两阶段多路归并排序（Two-Phase，Multiway Merge-Sort），简称TPMMS。

利用排序去除重复

采取上述TPMMS的思路，在第二趟中，我们不断地复制每一块的第一个未考虑的元组t到输出，并将输入块中所有的t删除即可。

利用排序进行分组和聚集

1 将R的元组每次读取M块到内存，用L的分组属性作为排序关键字，对每M块排序，并将每一个排好序的子表写到磁盘

2 为每一个子表使用一个内存缓冲区，并首先将每一个子表的第一个块装入其缓冲区

3 在缓冲区可以获得的第一个元组中反复查找关键字的最小值。这个最小值v称为下一分组，我们为它：

a）准备在这个分组的列表L上计算所有聚集

b）检查每个排序关键字为v的元组，并且累计所需聚集

c）如果一个缓冲区空了，则用同一个子表的下一个块替换它

d)当不再有关键字为v的元组时，输出一个由L的分组属性和对应聚集值构成的元组。

基于排序的并算法

1 在第一趟的时候，创建R和S的排序子表

2 为R和S的每一个子表使用一个内存缓冲区，用对应子表的第一块初始化各缓冲区

3 重复地在所有缓冲区中查找剩余的第一个元组t。将t复制到输出，并从缓冲区删除t的所有副本。

基于排序的交和差算法

大体思路都是一样的，具体差异如下：

对于集合交，如果t在R和S中同时出现就输出t

对于包交，输出t的次数是它在R和S中出现的最小次数

对于集合差，R-S，当其仅当t出现在R中但不在S中时输出t

对于包差，R-S，输出t的次数是t在R中出现的次数减去S中出现的次数

基于排序的连接算法

1 用R和S的公共属性Y作为排序关键字，用TPMMS对R进行排序

2 用TPMMS对S进行排序

3 归并排好序的R和S，我们需要两个缓冲区

a）在当前R和S的块的前端寻找Y的最小值y

b）如果y在另一个关系中没有出现，删除关键字为Y的元组

c）否则，找出两个关系中关键字为y的所有元组。

d）输出通过连接R和S中拒用共同y值的元组

e）如果一个关系在内存中已没有未考虑的元组，就重新加载一个新的块

上述算法的磁盘I/O数为5 * (B(R)+B(S)),实际上，如果内存够大，可以将两个关系一起在内存中用TPMMS进行排序，排序后直接对所有块进行归并操作，没必要将关系再写会磁盘，这样磁盘I/O数会变成3*(B(R)+B(S))

基于排序的算法总结如下：

基于散列的两趟算法

基于散列的算法和基于排序的方法类似，也是将关系R分成很多小的关系来单独处理，但散列不会对这些子关系进行排序，而是将其散列到不同的桶中，因为散列函数是根据关键字计算的，所有有相同关键字的元组都在一个桶中，这样就可以一次一个桶进行处理。只要一个桶的元组数目小到能装入内存，我们就可以用一趟算法来处理相应的操作，不再赘述，相应操作的性能如下：

基于索引的两趟算法

如果一个关系的元组紧缩到能存储这些元组的尽可能少的块中，那么这个关系就是“聚簇”的，我们迄今为止所做的分析都假设关系是“聚簇”的。假如关系R上有一个索引，如果该索引某个固定值的所有元组都出现在能容纳它们的尽可能少的块中，则称该索引为聚簇索引。请注意一个非聚簇的关系不能够有一个聚簇索引，但一个聚簇的关系可以有非聚簇索引。

基于索引的选择

如果R没有索引，那么选择操作的磁盘I/O最好只能是B(R)。如果R不是一个聚簇的关系，磁盘I/O甚至可能是T(R)。对于特定值的查询，如果这个属性正好有索引并且是聚簇的，需要的磁盘I/O为B(R)/V(R,a);如果是非聚簇的，需要的磁盘I/O为T(R)/V(R,a)

基于索引的连接

考虑R(X,Y)和S(Y，Z),假设S有一个属性Y的索引，那么计算这个连接的一种方式是检查R的每一个块，并考虑R中的每一个元组t，利用索引找到与t对应的元组并进行连接操作。假设R是聚簇的，我们需要B(R)次磁盘I/O来获取R的所有元组，如果是非聚簇的，则需要T(R)次磁盘I/O。对R的每一个元组，我们必须读取S的T(S)/V(S,Y)个元组。如果S在Y上有一个非聚簇的索引，则需要的磁盘I/O为T(R)T(S)/V(S,Y);如果S在Y上有一个聚簇索引，则需要的磁盘I/O为T(R)B(S)/V(S,Y)。

假如R和S在Y上的索引都是有序的，只需依次顺序读取两个关系的所有块进行比较即可，磁盘I/O为B(R)+B(S);如果只有一个关系上的索引是有序的，可以对另一个关系先用TPMMS算法进行排序并写会，然后再一起进行merge，效率也非常高。