1 mysql支持的join算法

1.1 Nested Loop Join

Nested-Loop Join的思想就是通过双层循环比较数据来获得结果； 其中左表为外循环，右表为内循环，左表为驱动表。其实现逻辑简单粗暴，可以理解为两层 for 循环，小表在外环，大表在内环，数据比较的次数 = 小表记录数 * 大表记录数。

//select * from t1 inner join t2 on t1.a= t2.a;

List<结果> lists = new ArrayList<>();
for(t2 t2 : t2){  //外层循环
    for(t1 t1 : t1){  //内循环
        if(t2.a().equals(t1.a())){  //条件匹配
            //存放结果到结果集
            结果 = t1的字段 + t2的字段
            lists.add(结果集);
        }
    }
}

1.2 Index Nested-Loop Join

优化思路：内表为大表，可在 join 字段上建立索引，减少内表数据的扫描次数。

执行流程：
0. 前置条件：外表 t2 已在连接用的 a 字段以建立索引；
1. 从外表 t1 中读取一行数据 R；
2. 使用 R 中的a 字段和内表 t2 的 a 字段进行索引关联查找；
3. 根据索引到的记录取出表 t2 中满足条件的行，跟 R 组成一行，作为结果集的一部分；
4. 重复执行步骤 1 到 3，直到表 t1 循环结束。

可见，通过索引的建立，避免了对大表进行全表扫描，加快了查询速度。

1.3 Block Nested-Loop Join

优化思路：通过一次性缓存多条数据，减少外层表的循环次数。

t1 为小表时的执行流程：
1. 把t1 表查询的字段数据整个读入线程内存 join_buffer 中；
2. 扫描表 t2，把表 t2 中的每一行取出来，跟 join_buffer 中的 数据做对比，满足 join 条件的，作为结果集的一部分返回。

t1为大表时的执行流程： 
1. 扫描表 t1，顺序读取一定长度的数据行放入 join_buffer 中；
2. 扫描表 t2，把 t2 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 join 条件的，作为结果集的一部分返回；
3. 清空 join_buffer；
4. 顺序读取 t1 表下一批次数据放入 join_buffer 中，重复步骤2

2. Oracle的join算法

• Nested Loop Join，嵌套循环
• Hash Join，将两个表中较小的一个在内存中构造一个 Hash 表（对JoinKey），扫描另一个表
• Sort Merge Join，将两个表排序，然后再进行 join

DB2和SQL Server也使用这三种方式join算法。

2.1 Hash Join

Hash Join的使用场景：

• 适合于小表与大表连接、返回大型结果集的连接
• 只能用于等值连接，且只能在 CBO 优化器模式下

在 inner/ left/ right join，以及union/ group by 等 都会使用 hash join 进行操作。

实现原理:

Hash Join 中的小表称之为 hash 表，大表称为探查表，以小表作为驱动表。

• 两个输入：
  • build input（也叫做 outer input），小表
  • probe input（也叫做 inner input），大表
• 两个阶段：
  • Build（构造）阶段，处理 build input
  • Probe（探测）阶段，探测 probe input

build 阶段，主要是构造哈希表（hash table）：

• 在 inner/ left/ right join等操作中，表关联字段作为hash key
• 在 group by 操作中，group by 的字段作为 hash key；
• 在 union 或其它去重操作中，hash key包括所有的 select 字段。

一个hash值对应到 hash table 中的hash buckets。多个 hash buckets 可以使用链表数据结构连接起来。

Probe 阶段，从 probe inpu t中取出每一行记录，根据key值生成hash值，从build阶段构造的hash table中搜索对应的hash bucket。

• Grace Hash join

在内存足够大的情况下，建立的哈希表整体都放在内存中。

当小表数据量大到内存无法容纳时，会分别将 build input 和 probe input 切分成多个分区（partition），这样就将一个大的 Hash Join 切分成了多个独立且互相不影响的 Hash Join。

Hash Join的性能和资源消耗：

Hash join 效率最高，因为只要对两张表扫描一次。

Hash join 的主要资源消耗在于CPU。因其在内存中创建临时的 hash 表并进行 hash 计算时，都需要做大量的 hash 操作。

2.2 Merge Join

Merge join前需要确保两个关联表都是按照关联的字段进行排序；如果关联字段有索引并且排序一致，则可直接进行Merge Join操作。

通常用在数据没有索引但是已经排序的情况下，如果不需要排序操作，Merge Join本身的速度很快。

由于两表数据都要先做排序，再做merge，因此效率相对较差。
merge join的资源消耗主要在于磁盘I/O(扫描表或索引)。

3. Hive的join算法

• Reduce Join

在 Hive 中也叫 Common Join 或 Shuffle Join。

Shuffle 阶段主要根据 Key 值 hash 分组，推送到不同的 Reduce 阶段。

• Map Join

如果一张大表一张小表，就可以将小表放到内存里，在map端做join

Map Join可以进行不等值的连接操作。

• SMB(Sort-Merge-Buket) Join

首先进行排序，继而合并，然后放到所对应的bucket中去。

bucket 就是按key进行hash，相同值的都放到一个bucket文件中去

4. SparkSQL的join算法

• shuffle hash join
• broadcast hash join
• sort merge join

前两者都属于hash join，只不过在hash join之前需要先shuffle还是先broadcast。

shuffler hash join 类似Grace Hash join，先根据join key进行分区，再hash join。

broadcast hash join 是将小表广播分发到大表所在的分区节点上,与分区记录进行hash join。

Sort-Merge Join：

shuffle阶段：将两张大表根据join key进行重新分区

sort阶段：对单个分区节点的两表数据，分别进行排序

merge阶段：对排好序的两张分区表数据执行join操作。

理论上数据经过shuffle之后是不需要sort的，可以直接merge。

sort merge join适合两张大表进行Join。

以上为数据库常见的JOIN算法，「分布式技术专题」是国产数据库hubble团队精心整编，专题会持续更新，欢迎大家保持关注。