两个阶段，将R和S按照连接关键字进行排序；扫描排序好的元组进行比较，outer relation R扫描一次。
（排序连接也有outer 和inner吗？）

三个阶段，分区（可选）、排序和合并。

分区

两种方法隐形分区和显性分区

• 隐形分区：被加载到数据库后按连接键对数据进行分区；不需要额外传递数据
• 显性分区：只对outer relation进行分区，在不同的CPU cores进行在分配；可以用上节的基数分区。

排序

以前都用快速排序，当然现在还在用
下面介绍一些利用NUMA和并行结构的排序算法

缓存敏感排序

level 1：寄存器排序
level 2：cache排序：将1的输入合并到适合CPU缓存 运行；重复直到排序的占一半（输入输出各一半）
level 3：out-of-cache排序：2运行超过缓存大小时使用

Level 1 sorting networks

对排序键的抽象模型：

• 有和要排序的元素(列表)数量相同的固定的线路
• 对现代CPU更高效，因为数据依赖少没有分支

• 在分支上用SIMD的MIN/MAX操作

  
  
  
  

  SIMD操作无法在一个寄存器中进行，不能行内排序，只能在寄存器间进行，

  
  
  有四个寄存器时，需要10次MAX/MIN操作，8次shuffle（怎么算的呢，要是按对角互换的话不是6次吗）

level 2 Bitonic Merge Network

二分合并网络
像一个排序网络，能把两个本地排序的列表合并成一个全局排序列表.
逐渐合并更大的表扩展网络 知道一半的缓存

a从小到大排序，b从大到小排序，通过上图的路径分布方式，能用最少的MAX/MIN操作把两个有序序列进行合并排序。

level 3 多路合并 Multi-Way Merge

用Bitonic merge networks，把流程分解为任务——每个核一个worker，把任务和高速缓存大小的FIFO队列链接在一起。

当输入队列或输出队列满时，任务块会被阻塞，merge阻塞。

合并阶段

齐步循环遍历外表和内表，然后比较连接键。
如果有重复的值，可能需要回溯。
如果核有自独立的输出buffer，不同的核可以无同步并行。
下面介绍一些排序合并连接的变体

Multi-Way Sort-Merge 多路排序合并

外表：每个核用level1/level2在本地数据上并行排序；把排序好的数据用多路合并（level3）跨核重新分布。（也就是各个核心先自己排序，然后合并成全局有序，再把这些数据按序分给各个核）
内表：和外表一样
合并：在每个核上进行内表和外表的块的匹配合并。直接将四块数据用多通道方式使用更多层的Bitonic Merge Networks进行合并。

Multi-Pass Sort-Merge

外表：和上面的一样进行排序；排完序之后不再重新分布
内表：和外表一样
合并：在外表的多个块和内表的多个块之间的全局合并连接（外表中的一块用内表的所有块进行匹配）

Massively Parallel Sort-Merge

外表：对外表进行范围分区，然后跨核重新分配，分配后每个核再对自己的数据进行排序（也就是说这个还是全局排序的，只不过是先按范围分配，各个核再排序）
内表：不再重新分配，每个核就把自己的本地数据给排序了
排序：跨区合并连接，外表的整个和内表的一段之间的合并，外表的浅色部分全部扫描，而只扫描内表的第一个浅色部分

Hyper对于并行的规则：

1. 不要随机写到非本地内存：数据分块，重新分布，每个核排自己本地的数据
2. 在非本地内存上只做连续读：硬件可以预取来隐藏巨量延迟
3. 不要等待其他核：防止细粒度的latch或同步障碍