1.简介¶

Join是以表为输入，将表进行笛卡尔积并利用Filter过滤输出的操作。

在关系数据库中，通过将表进行拆分，从而减少重复量和冗余信息。Foreign Key就是一种形式。

将表拆分后，通过Join将拆分的表进行合并，从而得到期望的信息。

从数据传输的方面来看，Join有两种实现方式：

传输raw data：优点是运算结束后无需再从表中获取数据，缺点是可能传输开销较大。
传输record id：也称之为late materialization，它只传输必要的数据和record id，在完成Join后再从表中获取数据。该方案的本意是减少传输的开销，但尤其在分布式数据库中，由于不同数据库间通过网络连接，因此效率可能不如传输raw data。

从实现算法来说，JOIN有三种实现方式：

Nested Loop Join
Sort-Merge Join
Hash Join

本文中提到的outer table指的是进行运算的两张表规模较小的表，而inner table为规模较大的表。

2.Nested Loop Join¶

简单来说就是利用两个for循环对两张表进行循环扫描，从而合并满足条件的tuple。

对于有M个pages、m个tuple的表A和N个pages、n个tuple的表B来说，其复杂度为 $M+(m*N)$ ，含义为表A总共需要取出M个pages，其每个tuple都要令表B取出M次pages。

对于M=1000、m=100,000和N=500、n=40,000的表来说，若pages的大小为4kb，那么这两张表的大小为6MB。

通过计算，其I/O复杂度为500+(40000*1000)=40,000,500，即大约1.1小时。

常见的优化方法是基于利用更大的单位block进行扫描，而不是pages。

假设可缓存B个page，那么利用B-2个page缓存其中一个table，一个page扫描另外一个table以及一个page存储输出。其复杂度为 $M+(\lceil M/(B-2)\rceil *N)$ 。

3.Sort-Merge Join¶

先对两张表进行排序，利用两个游标指向有序的表，对于匹配的tuple进行合并。

sort R,S on join keys
cursor_R -> R_sorted,cursor_S -> S——sorted
while cursor_R and cursor_S:
    if cursor_R > cursor_S:
        cursor_S ++
    if cursor_R < cursor_S:
        cursor_R ++
    elif cursor_R == cursor_S:
        emit
        cursor_S ++

对于两个阶段，其复杂度为：

Sort Table R： $O(2\times N \times\lceil log_KM \rceil)$
Sort Table S： $O(2\times N \times\lceil log_KN \rceil)$
Merge： $O(M+N)$

4.Hash Join¶

对outer table建立哈希表，然后对inner table进行顺序扫描，所有与inner table匹配的值都可以在哈希表的其中一个分区找到。

常见优化：在对inner table扫描时，利用布隆过滤器提前查询哈希表中是否有该key。

5.Grace Hash Join¶

Hash Join中采用对outer table建立哈希表是因为需要尽可能在内存中存放outer table，否则会在磁盘中产生许多随机I/O。

如果outer table过大，Hash Join的性能就不是很理想。

Grace Hash Join通过对inner table也建立哈希表Hash Join的在该场景下进行了优化。

Grace Hash Join的算法很简单，通过对inner table和outer table建立哈希表，然后取出两表相同key的bucket，然后对它们进行nested loop join。

6.总结¶

对于上述介绍的算法，其复杂度与例子对应的时间如下表：

Algorithm	I/O Cost	Example
Nested Loop Join	M+(m*N)	1.3h
Block Nested Loop Join	M+(M*N)	50s
Sort-Merge Join	M+N+(sort cost)	0.59s
Hash Join	3*(N+M)	0.45s

对于Sort-Merge Join来说，需要通过元数据来判断是否有数据倾斜。同时除非表已经是有序的，此时Sort-Merge Join的性能更好，否则其他情况下，Hash Join的表现都更好。