兩個(gè)階段，將R和S按照連接關(guān)鍵字進(jìn)行排序；掃描排序好的元組進(jìn)行比較，outer relation R掃描一次。
（排序連接也有outer 和inner嗎？）
三個(gè)階段，分區(qū)（可選）、排序和合并。
分區(qū)
兩種方法隱形分區(qū)和顯性分區(qū)
- 隱形分區(qū)：被加載到數(shù)據(jù)庫后按連接鍵對(duì)數(shù)據(jù)進(jìn)行分區(qū)；不需要額外傳遞數(shù)據(jù)
- 顯性分區(qū)：只對(duì)outer relation進(jìn)行分區(qū)，在不同的CPU cores進(jìn)行在分配；可以用上節(jié)的基數(shù)分區(qū)。
排序
以前都用快速排序，當(dāng)然現(xiàn)在還在用
下面介紹一些利用NUMA和并行結(jié)構(gòu)的排序算法
緩存敏感排序
level 1：寄存器排序
level 2：cache排序：將1的輸入合并到適合CPU緩存 運(yùn)行；重復(fù)直到排序的占一半（輸入輸出各一半）
level 3：out-of-cache排序：2運(yùn)行超過緩存大小時(shí)使用
Level 1 sorting networks
對(duì)排序鍵的抽象模型：
- 有和要排序的元素(列表)數(shù)量相同的固定的線路
- 對(duì)現(xiàn)代CPU更高效，因?yàn)閿?shù)據(jù)依賴少?zèng)]有分支
-
在分支上用SIMD的MIN/MAX操作
SIMD操作無法在一個(gè)寄存器中進(jìn)行，不能行內(nèi)排序，只能在寄存器間進(jìn)行，
有四個(gè)寄存器時(shí)，需要10次MAX/MIN操作，8次shuffle（怎么算的呢，要是按對(duì)角互換的話不是6次嗎）
level 2 Bitonic Merge Network
二分合并網(wǎng)絡(luò)
像一個(gè)排序網(wǎng)絡(luò)，能把兩個(gè)本地排序的列表合并成一個(gè)全局排序列表.
逐漸合并更大的表擴(kuò)展網(wǎng)絡(luò) 知道一半的緩存
a從小到大排序，b從大到小排序，通過上圖的路徑分布方式，能用最少的MAX/MIN操作把兩個(gè)有序序列進(jìn)行合并排序。
level 3 多路合并 Multi-Way Merge
用Bitonic merge networks，把流程分解為任務(wù)——每個(gè)核一個(gè)worker，把任務(wù)和高速緩存大小的FIFO隊(duì)列鏈接在一起。
當(dāng)輸入隊(duì)列或輸出隊(duì)列滿時(shí)，任務(wù)塊會(huì)被阻塞，merge阻塞。
合并階段
齊步循環(huán)遍歷外表和內(nèi)表，然后比較連接鍵。
如果有重復(fù)的值，可能需要回溯。
如果核有自獨(dú)立的輸出buffer，不同的核可以無同步并行。
下面介紹一些排序合并連接的變體
Multi-Way Sort-Merge 多路排序合并
外表：每個(gè)核用level1/level2在本地?cái)?shù)據(jù)上并行排序；把排序好的數(shù)據(jù)用多路合并（level3）跨核重新分布。（也就是各個(gè)核心先自己排序，然后合并成全局有序，再把這些數(shù)據(jù)按序分給各個(gè)核）
內(nèi)表：和外表一樣
合并：在每個(gè)核上進(jìn)行內(nèi)表和外表的塊的匹配合并。直接將四塊數(shù)據(jù)用多通道方式使用更多層的Bitonic Merge Networks進(jìn)行合并。
Multi-Pass Sort-Merge
外表：和上面的一樣進(jìn)行排序；排完序之后不再重新分布
內(nèi)表：和外表一樣
合并：在外表的多個(gè)塊和內(nèi)表的多個(gè)塊之間的全局合并連接（外表中的一塊用內(nèi)表的所有塊進(jìn)行匹配）
Massively Parallel Sort-Merge
外表：對(duì)外表進(jìn)行范圍分區(qū)，然后跨核重新分配，分配后每個(gè)核再對(duì)自己的數(shù)據(jù)進(jìn)行排序（也就是說這個(gè)還是全局排序的，只不過是先按范圍分配，各個(gè)核再排序）
內(nèi)表：不再重新分配，每個(gè)核就把自己的本地?cái)?shù)據(jù)給排序了
排序：跨區(qū)合并連接，外表的整個(gè)和內(nèi)表的一段之間的合并，外表的淺色部分全部掃描，而只掃描內(nèi)表的第一個(gè)淺色部分
Hyper對(duì)于并行的規(guī)則：
- 不要隨機(jī)寫到非本地內(nèi)存：數(shù)據(jù)分塊，重新分布，每個(gè)核排自己本地的數(shù)據(jù)
- 在非本地內(nèi)存上只做連續(xù)讀：硬件可以預(yù)取來隱藏巨量延遲
- 不要等待其他核：防止細(xì)粒度的latch或同步障礙
