高级数据库二十：并行JOIN算法（Sorting）

我会带着你远行 2022-05-31 23:35 212阅读 0赞

# Parallel Join Algorithms (Sorting) #

## 背景 ##

关于Join的其他背景可以查看上一篇讲[Hash Join][]的文章。

### SINGLE INSTRUCTION, MULTIPLE DATA (SIMD) ###

有一系列的CPU指令允许处理器同时在多个数据点上执行相同的操作。

目前的AMD和Intel CPU均具有ISA和微体系结构，支持SIMD操作。

优点：

*  如果一个算法可以被矢量化（如，神经网络中的矩阵运算，高斯消元的矩阵运算），则可以显着地提升性能和资源利用率。

缺点：

*  一个算法不是特别容易被矢量化的。使用SIMD实现算法仍然大部分是手动过程，而不能用编译器自动完成。
 *  SIMD可能对数据对齐有限制。
 *  将数据收集到SIMD寄存器并将其分散到正确的位置是比较困难或低效的。

### 为啥不用GPU ###

说到了矢量化的例子，我举了神经网络中的矩阵运算，对神经网络有一定了解的人都知道，神经网络中的运算用GPU更合适，那么为什么不在这儿使用GPU加速呢？

因为在DRAM和GPU之间来回移动数据比PCI-E总线慢。

*  有一些更新的支持GPU的DBMS  
    
    
     *  例子：MapD，SQream，Kinetica
 *  新兴的可共享CPU内存的协处理器可能会改变这一点。  
    
    
     *  例子：AMD的APU（这玩意儿性能不亚于GPU，散热还比GPU低），Intel的Knights Landing

## SORT-MERGE JOIN ##

阶段1：排序

*  根据连接键对R和S的元组进行排序。

阶段2：合并

*  扫描已排序的关系并比较元组。
 *  外部关系R只需扫描一次。

![15159368660268.jpg][]

排序总是代价最高的部分。我们可以利用新的硬件尽可能地加快速度。

*  使用尽可能多的CPU内核。
 *  请注意NUMA限制，读取别的机器的数据将花费更多的时间，从而成为一个瓶颈。

## PARALLEL SORT-MERGE JOIN ##

阶段1：分区（可选）

*  将R分区并将其分配给工worker/core。
 *  一般是通过key来决定分区的

阶段2：排序

*  根据连接键对R和S的元组进行排序。

阶段3：合并

*  扫描已排序的关系并比较元组。
 *  外部关系R只需扫描一次。

### PARTITIONING阶段 ###

将输入数据分块并分配给核心。总体的思想和方法与Hash Join一致，同样也是可选操作。

*  显式与隐式

显式：仅分配外部关系并在不同的CPU内核之间重新分配。可以使用我们上次谈到的相同的基数分区方法。

### SORT阶段 ###

创建两个输入关系的排序块元组运行。曾经，Quicksort就足够了。

但NUMA和并行架构需要我们更加小心，应该使用别的算法。

#### CACHE-CONSCIOUS SORTING ####

等级＃1：寄存器排序

*  适合CPU寄存器的分类运行。
 *  将数据切成适度大小存入CPU寄存器，使用SIMD对数据进行排序。

级别2：缓存排序

*  将级别1的输出合并到适合CPU的运行中  
    缓存。
 *  重复，直到有序的数据占有了1/2高速缓存大小（因为输入输出各占一半）。

级别3：缓存外排序

*  2级运行超过缓存大小时使用。

##### SORTING NETWORKS #####

排序键的抽象模型。

*  对于具有相同数量元素的列表，始终固定布线“路径”。
 *  在路径的交汇处使用SIMD的MIN/MAX操作。
 *  相比于qsort等排序，数据依赖性有限且没有分支（if、for等），因此可以在现代CPU上高效执行。

![15159659238392.jpg][]

![15159660177364.jpg][]

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

之所以这样快的原因是减少了程序中的结构和分支，可以通过管道不停地直接运行，所以尽管shuffle的代价非常大，这样仍然比qsort快。

对于4个寄存器，通过10次MIN/MAX操作（5次MIN操作和5次MAX操作）就可以完成排序。

我不是很懂8次（4×2）SHUFFLE就能将一个4×4的转化成这样，我总觉得6次就够了。

##### [BITONIC MERGE NETWORK][] #####

就像一个排序网络，但它可以将两个本地排序的列表合并成一个全局排序的列表。

再通过扩展网络来逐步合并更大的列表（½个缓存大小）。

英特尔通过设计了SISD，使得运行速度提高2.25-3.5倍。

![15159668410020.jpg][]

a列表是从小打到排序的，b列表是从大到小排序的。通过上图的路径拍布方式，比较能够用最小的MIN/MAX操作将两个排序过的序列进行合并排序。

#### MULTI-WAY MERGING ####

使用Bitonic Merge Networks，但将流程分解成任务。

*  每个核心仍然有一个工作线程。
 *  将任务与高速缓存大小的FIFO队列链接在一起。

当输入队列为空或输出队列已满时，任务块将被阻塞，即，MERGE操作会被堵塞，而不是输出的时候被阻塞。

虽然需要更多的CPU指令，但带宽和计算会达到平衡。

![15159673575364.jpg][]

### MERGE阶段 ###

循环遍历外部表和内部表，并比较连接键。  
如果有重复，可能需要回溯。  
如果有独立的输出缓冲区，可以在不同步内核的情况下并行完成。

#### Multi-Way Sort-Merge ####

外表

*  每个core在本地数据（级别＃1 /＃2）上并行排序。
 *  使用多路合并（级别＃3）在core之间重新分配排序的运行。

内表

*  与外表相同。

![15159679574210.jpg][]

用相同的姿势获得另一个表的排序结果。

合并阶段在每个核心的外部/内部表格的匹配对之间进行。

![15159680106108.jpg][]

关于这个redistribution，我保持一定的疑问。如果是按照比例切，那么本地数据1的浅色部分可能会大于本地数据2的深色部分，则是不可行的。如果按值来切，那么可能会分布不均匀，但是是可行的。

#### MULTI-PASS SORT-MERGE ####

外表

*  M-WAY同样的＃1 /＃2排序。
 *  但是，不经过重新分配，它使用多通道朴素合并。
 *  可以这么理解它和M-Way的区别：M-Way根据一定的比例对排序过的本地数据进行redistribution，将划分重新分块之后再进行Bitonic Merge Networks；而M-Pass则是不经过redistribution，直接将四块数据用多通道的方式使用更多层的Bitonic Merge Networks来进行合并。

内表

*  与外表相同。

合并阶段是在外部表格和内部表格的匹配对之间进行的。

#### [MASSIVELY PARALLEL SORT-MERGE][] ####

外表

*  范围分区外表并重新分配给核心。
 *  每个核心在其分区上并行排序。

内表

*  不像外表一样重新分配。
 *  每个核心对其本地数据进行排序。

合并阶段是在外部表的整个排序运行和内部表的一段之间。如图所示，外表的浅色部分全部扫描，而内表的每个分区只扫描浅色部分（在这儿要扫描4个分区的浅色部分）。

![15159711542706.jpg][]

关于这个redistribution，因为明确地说了是按照范围划分的，所以正确性有保证。

## HYPER’s RULES FOR PARALLELIZATION ##

规则1：不要随机写入非本地内存

*  分块数据，重新分配，然后每个核心对本地数据进行排序/处理。

规则2：只对非本地内存执行顺序读取

*  这允许硬件预取器隐藏远程访问延迟。

规则3：没有core应该等待另一个core

*  避免细粒锁定或同步屏障。

## 参考资料 ##

[课件][Link 1]  
论文参见课件

[Hash Join]: http://blog.csdn.net/u013007900/article/details/79055303
[15159368660268.jpg]: https://lh3.googleusercontent.com/-xjnCkYAh4-s/WlvlIpKvwmI/AAAAAAAAAiA/FoV2bmlshb0cF64NhA6GiWH1MpJsfJ0dQCHMYCw/I/15159368660268.jpg
[15159659238392.jpg]: https://lh3.googleusercontent.com/-WdwxOTCiCnI/WlvlI5b4egI/AAAAAAAAAiE/YjIuGXjkbo425zfxoR2KLieY-eLdJDiigCHMYCw/I/15159659238392.jpg
[15159660177364.jpg]: https://lh3.googleusercontent.com/-ZEv8HIloNdo/WlvlJEk5_gI/AAAAAAAAAiI/3Dv1AGGf8aMtfL51GrVDyrHo43s95TbhwCHMYCw/I/15159660177364.jpg
[BITONIC MERGE NETWORK]: http://www.vldb.org/pvldb/1/1454171.pdf
[15159668410020.jpg]: https://lh3.googleusercontent.com/-izCqlz2oVo4/WlvlJXyUd7I/AAAAAAAAAiM/rHydaNHRYlU8G2ARdnkge6_itnA8weLoACHMYCw/I/15159668410020.jpg
[15159673575364.jpg]: https://lh3.googleusercontent.com/-e_eWluXEWN4/WlvlJ0hW3jI/AAAAAAAAAiQ/wPhe7KzpXRA3kX170Eskc22xCgT-anJ0wCHMYCw/I/15159673575364.jpg
[15159679574210.jpg]: https://lh3.googleusercontent.com/-4z2ps9TtxkI/WlvlKJ_kqnI/AAAAAAAAAiU/BpM3vSMSx-o8X2ytqKlU4SIJekWfjPQ4QCHMYCw/I/15159679574210.jpg
[15159680106108.jpg]: https://lh3.googleusercontent.com/-D3Qfyf40dds/WlvlKTx_NZI/AAAAAAAAAiY/uu74eJbqhych9tl6UaGIa6WppSls3DU6ACHMYCw/I/15159680106108.jpg
[MASSIVELY PARALLEL SORT-MERGE]: http://15721.courses.cs.cmu.edu/spring2016/papers/p1064-albutiu.pdf
[15159711542706.jpg]: https://lh3.googleusercontent.com/-xVbQiTLApUg/WlvlK9Nc7PI/AAAAAAAAAic/ESzGB2KRbDMkHl1AwUO4NgLQSw5JQVopwCHMYCw/I/15159711542706.jpg
[Link 1]: http://15721.courses.cs.cmu.edu/spring2017/slides/19-sortmergejoins.pdf