6.6 排序合并连接

简单的排序连接

已知将要连接的关系R(X,Y)和S(Y,Z),并且已知有M块内存用作缓冲区，我们按照下面步骤： 1. 用Y作为排序关键字，使用两阶段多路合并排序算法（或者其他排序？）对R进行排序。
2. 类似地对S做排序
3. 归并排好序的R和S，我们仅用两个缓冲区，一个给R的当前块，另一个给S的当前块。重复执行下面步骤:
1. 在当前R和S的块的前端查找连接属性Y的最小值y
2. 如果y在另一个关系的前部没有出现，那么删除具有排序关键字y的元组。
3. 否则，找出两个关系中具有排序关键字y的所有元组。如果需要，从排序的R和/或S中读取块，知道我们确定每一个关系中都不再有y的副本。最多可以用M个缓冲区来做这件事情。
4. 输出通过连接R和S中具有共同的Y-值y的元组所能形成的所有元组
5. 如果一个关系在内存已没有未考虑的元组，就重新加载为那个关系而设的缓冲区。