Join是SQL语句中的常用操作，良好的表结构能够将数据分散在不同的表中，使其符合某种范式，减少表冗余、更新容错等。而建立表和表之间关系的最佳方式就是Join操作。

对于Spark来说有3中Join的实现，每种Join对应着不同的应用场景：

1. Broadcast Hash Join ：适合一张较小的表和一张大表进行join
2. Shuffle Hash Join : 适合一张小表和一张大表进行join，或者是两张小表之间的join
3. Sort Merge Join ：适合两张较大的表之间进行join

Hash Join

先来看看这样一条SQL语句：

select * from order,item where item.id = order.i_id

• 确定Build Table以及Probe Table：这个概念比较重要，Build Table使用join key构建Hash Table，而Probe Table使用join key进行探测，探测成功就可以join在一起。通常情况下，小表会作为Build Table，大表作为Probe Table。此事例中item为Build Table，order为Probe Table；很简单一个Join节点，参与join的两张表是item和order，join key分别是item.id以及order.i_id。现在假设这个Join采用的是hash join算法，整个过程会经历三步：
• 构建Hash Table：依次读取Build Table（item）的数据，对于每一行数据根据join key（item.id）进行hash，hash到对应的Bucket，生成hash table中的一条记录。数据缓存在内存中，如果内存放不下需要dump到外存；
• 探测：再依次扫描Probe Table（order）的数据，使用相同的hash函数映射Hash Table中的记录，映射成功之后再检查join条件（也就是该key 是否有数据），如果匹配成功就可以将两者join在一起

基本流程可以参考上图，这里有两个小问题需要关注：

• hash join性能如何？很显然，hash join基本都只扫描两表一次，可以认为o(a+b)
• 为什么Build Table选择小表？道理很简单，因为构建的Hash Table最好能全部加载在内存，效率最高；这也决定了hash join算法只适合至少一个小表的join场景，对于两个大表的join场景并不适用。

而在分布式环境下，表会被分割为多份分配到不同机器上执行，这就要求对 Hash join 方案进行改造。

hash join分布式改造一般有两种经典方案：

1. broadcast hash join：将其中一张小表广播分发到另一张大表所在的分区节点上，分别并发地与其上的分区记录进行hash join。broadcast适用于小表很小，可以直接广播的场景