## 3.3  关系算子的实现和代价

前一小节我们介绍了关系数据库系统的查询处理包含查询解析、查询优化和查询执行三个步骤。关系数据库系统的查询执行采用流水线的方式，依次执行物理执行计划中的每个关系算子。每种关系算子有不同的物理实现方式，不同的实现方式适合不同的场景。合理地选择关系算子的实现方式有利于实现高效的查询处理。因此，我们要能够评估每种关系算子的实现算法的代价。在查询处理过程中，关系算子的代价主要是指执行过程中对各种计算资源的消耗，包括磁盘I/O，CPU时间和网络通信。对于数据存放于磁盘的集中式关系型数据库系统，磁盘I/O是查询处理最主要的代价。因此，本节使用关系算子执行过程中使用的磁盘I/O数目作为代价度量的指标。


### 3.3.1 选择运算算法和代价
```SQL
[例3.2] 查询姓名为沐辰的学生信息。
SELECT *
FROM Student
WHERE Sname = '沐辰' ;
```
上述查询语句中包含选择运算，其执行过程是扫描整个学生表Student并选出满足选择条件的目标记录。通常根据关系在选择条件上有无索引可以将关系扫描分为全表扫描和索引扫描两类。假设学生表Student的记录存放在B个物理页中，每个物理页中包含多个学生的信息，物理页通过主键属性（学号Sno）的B+树聚簇索引结构进行组织，主键索引的B+树层高为L。

选择运算的两种实现方法和代价，描述如下：

* 全表扫描（Table Scan）：当在学生姓名（Sname）上没有索引时，选择运算采用全表扫描。首先定位到学生表Student的第一个物理页的位置，然后依次读取每一个物理页到内存中，之后对读入内存中的每个元组进行检索，最后输出满足条件的元组。全表扫描需要读取学生表的所有物理页，因此磁盘I/O代价为B，即cost=B。不管是等值选择还是范围选择，磁盘I/O代价都为B。
* 索引扫描（Index Scan）：当在学生姓名（Sname）上存在索引时，选择运算采用索引扫描。假设在学生表的学生姓名属性（Sname）上构建了一个基于B+树的非聚簇索引，其索引的层高为L。首先基于Sname上的B+树索引找到多个满足选择条件的元组所在的叶子结点，然后通过叶子结点上的指针找到这些元组对应的物理页，并依次读入内存，之后对内存中的每个元组进行检索，输出满足条件的元组。整个执行过程中，需要读取B+树索引中从根结点到叶子结点的L个物理块，以及读取多个符合选择条件元组所在的物理页数。假设有V个元组符合查询条件，也就是索引的选择基数为V（有V个元组的Sname='沐辰'），最坏的情况是V个元组存放在不同的物理页中。整个运算过程需要读取L+V个物理页，因此索引扫描的磁盘I/O代价为L+V。如果选择条件是基于主键（学号Sno）的等值查询，选择运算默认使用索引扫描。由于只有唯一一个符合选择条件的元组，因此其磁盘I/O代价为L+1。对于范围选择，不管是基于聚集索引还是非聚集索引的索引扫描，首先需要通过B+树查找出运算符为等值运算时的元组所在的叶子节点，然后通过B+树叶子节点链表搜索有该叶子节点之前或之后的所有满足范围选择条件的叶子节点，之后将依次读取对应的物理页到内存并检索出目标元组。假设符合范围选择条件的元组有n个，则其磁盘I/O代价为L+n。

基于上述描述可以得出：小表的选择运算通常采用全表扫描算法，尤其是物理页极少的关系表；对于大表的选择运算，如果有索引结构且索引的选择基数较低时，通常采用索引扫描算法；如果索引选择基数较高（符合选择条件的元组较多）或者查找的元组均匀地存储在B个物理页中，那么索引扫描算法性能则不如全表扫描算法。因为，此时的索引扫描不仅要读取表的物理页，还要对B+树进行扫描。


### 3.3.2 投影运算算法

```SQL
[例3.3] 查询学生表中学生所在的系。
SELECT DISTINCT Dept 
FROM Student;
```

该查询语句中包含选择运算和投影运算，首先通过全表扫描算法依次读取Student表的元组，得到每个元组的Dept值，然后使用投影运算算法对得到的Dept值进行去重。

投影运算的关键是对属性列的值进行去重。为了便于去重操作，需先对属性值进行排序。目前，排序算法可以分为内排序和外排序。内排序算法用于所有数据都能存放于内存的情况，常用的算法有快速排序、插入排序、冒泡排序和堆排序等；外排序算法用于数据量太大而不能全部存放于内存的情况，常用的算法有两阶段多路归并排序算法。关系数据库管理系统的投影运算通常采用外排序算法。

外部排序算法的步骤如下：

* 第一步生成归并段：将所有数据分成多个内部已排序的归并段。假设生成k个归并段，那么首先从磁盘中读取第一个分段的数据，采用内排序算法进行排序，然后将排好序的分段写回磁盘，最后重复上述操作直到处理完k个归并段。整个过程涉及一次读数据和一次写数据，假设数据占用了B个物理页，则此阶段的I/O代价为2B。
* 第二步多路归并排序：将所有归并段合并成一个排好序的大段。首先读取每个归并段的第一个数据，计算出最小的值作为输出；然后取最小值所在归并段的下一个数据，重复上述过程计算出最小的值；最后依次找出k个归并段中的所有数据。整个过程涉及一次读数据，因此I/O代价为B。

投影运算的去重操作在外部排序的第二步中实现，即输出的最小值不重复。投影运算算法的I/O代价为2B+B，即cost=3B。


### 3.3.3 连接运算算法

```SQL
[例3.4] 查询学生及其选修课程的信息。
SELECT * 
FROM Student S, SC R
WHERE S.Sno = R.Sno;
```

上述查询语句是Student表（S表）与SC表（R表）在主码Sno上的等值连接运算。常用的连接运算算法有：嵌套循环连接（Nested Loop Join）、排序合并连接（Merge Join）、散列连接（Hash Join）以及索引连接（Index Join）。下面将分别进行介绍。

（1） 嵌套循环连接

这是连接运算最简单直观的算法。算法的思想为：首先读取左表S的第一个元组，然后将该元组与右表R的所有元组进行等值连接条件检查，如果两个元组在连接属性Sno上相等，则串接后作为结果输出，之后依次读取S表余下的元组重复上述操作。这其实是一个双层嵌套循环的过程。

在关系数据库系统中，数据的存取是按照物理页读入内存的，而不是按元组读入的，因此，实际的嵌套循环连接算法步骤如下（假设内存可以容纳M个物理块）：

* 第一步， 首先读取左表S的M-1个物理块到内存中；然后读取右表R的1个物理块到内存，之后依次检查内存中S表的所有元组与R表的所有元组是否满足连接条件，如果满足则输出；最后读取右表R余下的物理块并重复上述操作；
* 第二步，读取左表S余下的物理块并重复第一步的操作。

嵌套循环连接算法的伪代码如下所示。

```C
/*嵌套循环连接算法伪代码*/
Do load M-1 blocks(MS) from S into memory //读取左表S的M-1个物理页到内存
	Do load One block(MR) from R into memory //读取右表R的1个物理页到内存
		For each tuple s in MS Do
			For each tuple r in MR Do
				If(s.joinkey = r.joinkey) //如果s和r在连接属性上的值相等，则输出两个连接结果
				Then output(s,r);
			End
		End
	Repeat;
Repeat;
```
假设S表占据B(S)个物理页，R表占据B(R)个物理页，那么嵌套循环连接算法的磁盘I/O代价为：cost=B(S)+B(S)B(R)/(M-1)。该算法的执行代价比较高，尤其是对两张大表的等值连接。通常，采用嵌套循环连接算法时会选择较小的表（占用页数较少的表）作为左表S，这样可以减少算法的I/O代价。如果B(S)小于M-1，那么I/O代价仅为B(S)+B(R)。

（2） 排序合并连接

排序合并连接算法是等值连接常用的算法。该算法的步骤如下：

* 第一步，使用外排序算法对Student表（S表）和SC表（R表）按连接属性Sno进行排序；
* 第二步，首先读取S表和R表的多个物理页到内存中；然后依次读取内存中两个表的元组进行连接条件检查。如果两个元组的Sno相等，则将它们串接起来进行输入，再读取S表的下一个元组继续进行检查；如果两个元组的Sno不相等，则读取Sno较小元组所在表的下一个元组，再进行连接条件检查。如果某张表在内存中的元组被处理完，那么从磁盘读取该表的物理页到内存，重复之前的操作直到某个表的所有元组被扫描结束。

该算法的伪代码如下：

```C
/*排序连接算法伪代码*/
Sort S and R by Join key //用连接属性作为排序关键字，对S和R表进行排序
Do load blocks(MS) from S and blocks(MR) from R into memory //读取S表的MS个物理页，R表的MR个物理页到内存
	Read the first tuple s from MS
	Read the first tuple r from MR
	While s != NULL && r != NULL
		If (s.joinkey = r.joinkey) //如果s和r在连接属性上的值相等，则输出两个连接结果
			output(s,r)  
			Read next tuple s from MS
		ElseIf (s.joinkey < r.joinkey)
			Read next tuple s from MS
		ElseIf (s.joinkey > r.joinkey)
			Read next tuple r from MR		
	End
Repeat;
```
该算法的I/O代价为：cost=5(B(S)+B(R))，其中，第一步排好序的S表和R表需写入磁盘，其执行代价为4(B(S)+B(R))；第二步中S表和R表只扫描一次，其I/O代价为B(S)+B(R)。排序合并连接算法适用于两个表已经按照连接属性排序的场景，此时它的I/O代价仅为B(S)+B(R)。

（3） 散列连接

散列连接算法的思想是：首先利用基于连接属性Sno的散列函数将S表和R表分别划分成多个小表（S1,S2,S3...Si..）和（R1,R2,R3...Ri...），S和R每个对应小表中的Sno取值范围一致，即Si表中元组的Sno与Ri表中元组的Sno取值一致；然后分别对S和R的对应小表做连接操作，直到处理完所有对应的S小表和R小表并输出连接结果。

散列连接算法的步骤如下（假设内存能够容纳M个物理页）：

* 第一步， 连接属性Sno作为散列关键字，利用相同的Hash函数分别将S表和R表划分成M-1个小表。对于S表的预处理，每次读取一个物理页到内存，利用Hash函数将物理页中的元组写入对应的Hash桶中（总共有M-1个Hash桶），最后再将Hash桶中的元组写入磁盘物理页中。利用同样的方法对R表进行预处理；
* 第二步， 读取S表和R表的第一个小表S1，R1的所有物理页到内存，然后依次检查内存中S1表的所有元组与R1表的所有元组是否满足连接条件，如果满足则输出串接结果，之后重复上述操作直到处理完S表和R表的所有小表。

该算法的伪代码如下：

```C
/*散列连接算法伪代码*/
//对S表利用散列函数Hash进行划分
Do load blocks(MS) from S into memory
	For each tuple s in MS Do
		i = Hash(joinkey)
		Si = Si union s	
	End
Repeat;
//对R表利用散列函数Hash进行划分
Do load blocks(MR) from R into memory
	For each tuple r in MR Do
		i = Hash(joinkey)
		Ri = Ri union r	
	End
Repeat;
//对S表和R表的每一个小表进行连接
For i=0:N
	Do load blocks from Si and Ri into memory
	 For each tuple s in Si Do
		For each tuple r in Ri Do
			If(s.joinkey = r.joinkey)
			Then output(s,r);
		End
	End
End
```
该算法的I/O代价为：cost=3(B(S)+B(R))，其中，第一步需要分别对S表和R表进行一次读和一次写，其I/O代价为2(B(S)+B(R))，第二步需要对S表和R表读一次，其I/O代价为B(S)+B(R)。上面介绍的散列连接算法假设两个表的对应小表在第二步中可以完全放入内存中。如果不需要这个前提条件的散列连接算法以及改进算法可以参见其他参考资料。

（4）索引连接

索引连接算法是利用连接属性上的索引来实现连接操作。例3.4中，Student表（S表）在Sno上构建了B+树聚集索引，SC表（R表）在Sno和Cno上构建了B+树索引结构。SC表上的索引称为组合索引，该索引的层数为L，索引在Sno上的选择基数为V（平均有V个元组具有相同的Sno值）。

算法的执行步骤如下：

* 第一步，读取S表的第一个物理页到内存，获得内存中S表每个元组的Sno，然后根据R表的索引结构找到R表中具有相同Sno值的元组，之后将S表的元组与R表的元组进行串接作为输出结果；
* 第二步，读取S表剩余的物理页，并重复第一步操作。

该算法的伪代码如下：

```C
/*索引连接算法伪代码*/

Do load blocks(MS) from S into memory
For each tuple s in MS Do
	List r[] = Search R-index(s.joinkey)
	Do load sizeof(r[]) blocks(MR) from R into memory
	For each tuple r in r[]
		output(s,r)
	End
End
```

该算法的I/O代价为：cost=B(S)+|S|\*L\*V，其中|S|表示S表中的元组个数。整个执行过程中，S表只需要读取一次，其代价为B(S)，而对于S表中的每一个元组都需要读取一次R表的索引结构找到满足连接条件的叶子结点，然后根据叶子结点的指针读取R表的物理页，其I/O代价为|S|\*L\*V。

### 练习题

**1**. 思考：对于关系表R(a,b,c,d)，我们在属性b上创建了一个B树索引，那么投影操作$\Pi_{a,b}(R)$的执行是否可以利用该索引？如何利用该索引？

**2**. 思考：本章节使用外部排序（External Sorting）的方式实现了投影操作的去重。请你设计另一种去重的方法，不使用排序，仍然可以达到很高的效率。

**3**. 思考：本章节讲到的散列连接，可能会遇到数据分布不均匀的情况，比如在连接属性上取值为k的元组特别多，多到连内存都容纳不下。请问这种情况应该如何应对？

**4**. 思考：除了本章介绍的连接算法，你是否能想到其它高效的算法，它甚至在某些情况下比本章介绍的算法更快？

**5**. 思考：请为以下问题设计一个I/O代价低的算法：给定一张表R(a,b,c,d)，找到R中在属性a上发生次数少于k次的所有取值。（如果R中一共有n个元组在属性a上的取值为x，则称x在R中发生了n次；假设R很大，无法容纳于内存中；假设a的不同取值个数很多，这些取值也无法都容纳于内存中。）

**6.** 如本章节中提到的，嵌套循环算法的I/O代价可以表示为 B(R) + B(S)\*B(R)/M，其中B(R)代表外循环表的页数，B(S)代表内循环表的页数，M代表内存能容纳的页数。那么以下哪种方案无法提升该算法的效率？

 <ol type="A">
 <li>增加内存容量</li>
 <li>将小表放到内循环（作为S），大表放到外循环（作为R）</li>
 <li>将大表放到内循环（作为S），小表放到外循环（作为R）</li>
 <li>更换速度更快的硬盘</li>
 </ol>

**7.** 课程中介绍了两种连接操作执行算法，嵌套循环和散列连接。以下哪种场景更适合使用嵌套循环算法？

<ol type="A">
 <li>一张表很大，一张表很小。小的表几乎可以容纳到内存中。</li>
 <li>两张表都比较大，都无法容纳到内存中。</li>
 <li>两张表都比较小，都可以容纳到内存中。</li>
 <li>几乎在所有情况下，散列连接的效率都更高。</li>
 </ol>

**8.** 假设R表有1000行，S表有100行；每页可以容纳10行数据（无论R表或S表）；内存可以容纳3页；R表和S表均有x属性，并且在x属性上均创建了索引；假设x具备很高的辨识度并且分布均匀。那么，理论上实现R和S在x上的等值连接的最佳算法是：

<ol type="A">
 <li>嵌套循环</li>
 <li>散列连接</li>
 <li>索引连接</li>
 <li>都一样</li>
 </ol>

[**上一页<<**](chapter3.2-R.md) | [**>>下一页**](chapter3.4-R.md)







