Spark中的三种Join策略

介绍

Spark通常使用三种Join策略方式

1. Broadcast Hash Join（BHJ）
2. Shuffle Hash Join（SHJ）
3. Sort Merge Join（SMJ）

Broadcast Hash Join

当小表与大表进行Join操作时，为了避免shuffle操作，将小表的所有数据分发到每个节点与大表进行Join操作，尽管牺牲了空间，但是避免了耗时的Shuffle操作。

1. 表需要broadcast，那么必须小于spark.sql.autoBroadcastJoinThreshold配置的值（默认是10M），或者明确添加broadcast join hint。
2. base table不能broadcast，例如在left outer join中，仅仅right表可以broadcast
3. 这种算法仅仅用来broadcast小表，否则数据的传输可能比shuffle操作成本高
4. broadcast也需要到driver，如果有太多的broadcast，对driver内存也是压力

Shuffle Hash Join

因为broadcast策略首先是收集数据到driver节点，然后分发到每个executor节点，当表太大时，broadcastchelve将会给driver和executor造成很大压力。
Shuffle Hash Join会减少对driver和exeuctor的压力，操作步骤如下：

1. 两张表分别按照连接列进行重组，目的是相同连接列的记录分配到同一个分区
2. 两张表的小表分区构造成hash表，大表根据相应的记录进行映射

Sort Merge Join

上面两种发现适应一定大小的表，但是当两张表足够大时，上面方法对内存造成很大压力，这是因为当两张表做Hash Join时，其中一张表必须完成加载到内存中。
当两张表很大时，Spark SQL使用一种新的算法来做Join操作，叫做Sort Merge Join，这种算法并不会加载所有的数据，然后开始Hash Join，而是在Join之前进行数据排序。
两张表需要进行数据重组，保证相同连接列值到一个分区中，当分区好数据后，排序分区中的数据，然后相应的记录进行关联。
不管表分区多大，Sort Merge Join并不会加载一张表的所有数据到内存。