1. 连接类型

Spark JoinType定义有7种Join连接类型：

case "inner" => Inner //内连接
case "outer" | "full" | "fullouter" => FullOuter //全外连接
case "leftouter" | "left" => LeftOuter //左外连接
case "rightouter" | "right" => RightOuter //右外连接
case "leftsemi" | "semi" => LeftSemi //左半连接
case "leftanti" | "anti" => LeftAnti //左反连接
case "cross" => Cross //笛卡尔积

1.Inner Join：内连接，两表等值JoinKey连接

2.Full Outer Join：外连接，两表没有匹配的行自动补Null，是两个表行数的总和

3.Left Outer Join：左连接，左表上没有匹配上的行自动补Null

4.Right Outer Join：右连接，右表上没有匹配上的行自动补Null

5.Left Semi Join：只输出在连接关系上匹配的数据行即可

• 等价于select T1 from T1 left join T2 where T2 is not null

• 等价于select T1 from T1 inner join T2，与Inner Join区别：只关心匹配是否存在，而不返回被匹配表的具体数据
  

6.Left Anti Join：输出左连接关系上没有匹配上的数据行

• 等价于select T1 from T1 left join T2 where T2 is null
  

7.Cross Join：笛卡尔积，是两个表行数的乘积

2.连接算法

1. Nested Loop Join嵌套循环连接(NLJ, Nested Loop Join)：​​双循环结构，使用两个嵌套for循环依次扫描两表的数据记录判断

• 外层for循环：负责遍历左表(驱动表)的每一条数据

• 内层for循环：负责遍历右表(基表)的所有记录，依次判断JoinKey 是否满足关联条件
  

2. Sort Merge Join排序归并连接(SMJ，Sort Merge Join)：先排序+后归并，

• 排序阶段：Join两表按照JoinKey升序排列，若数据已有序(或为索引)，则可跳过该步骤

• 归并阶段：双指针遍历，使用两个指针分别指向排序后的两表起始位置，逐个比较JoinKey

  • JoinKey相等：找到两表中所有连续相同键的行(称为块)，生成这些块的笛卡尔积作为连接结果

  • JoinKey不等：移动较小键的指针，直到找到匹配的键或遍历结束
    

Hash Join哈希连接(HJ，Hash Join)：Build阶段+Probe阶段，核心：基于Hash Map实现构件表扫描复杂度将至O(1)

• Build阶段：

  • 构建表(小表)的JoinKey应用哈希函数，生成哈希值

  • 将键和对应的行数据存入哈希表的对应​​桶(Bucket)​​中，若多个键哈希冲突，使用链表连续保存

• Probe阶段：

  • 探测表(大表)的JoinKey应用哈希函数，找到对应的哈希桶

  • 在哈希桶内精准匹配键值，若匹配成功则合并结果

对比	NestedLoopJoin	SortMergeJoin	HashJoin
时间复杂度	O(N*M)	O(N logN + M logN + N+M)	O(N +M）（1.哈希表在内存:2.无哈希冲突)
空间复杂度	0(1）(无额外存储)	O(N+M）（排序内存/磁盘)	O(M）(构建哈希表)
是否需要排序	不需要	需要预先排序	不需要 (但需哈希分桶)
适用连接条件	等值、非等值(如<,>)	等值、范围(需排序后合并）	仅等值连接 (依赖哈希碰撞)
内存消耗	低	中等 (排序占用)	高 (需存储哈希表)
最佳数据规模	小表驱动大表(尤其小表可放入内存)	大数据集 (分布式友好)	中等数据集（内存足够存哈希表)
分布式场景适用性	差 (需跨节点全量数据循环)	优(Spark默认选择)	中等（需广播或分阶段处理哈希表)

2. Spark Join方式

分布式环境，两表的join计算增加网络分发，数据在网络中分发主要有两种方式：

• Shuffle：两表数据在集群做全量的数据分发

• Broadcast(广播)：将小表封装到广播变量，大表数据无需移动，可在本地完成join计算

下图展示Spark的五种连接计算方式，默认连接策略为ShuffleSortMergeJoin，适合大规模数据且无需广播，连接策略的选择核心在JoinSelection 类实现。

连接方式	连接条件	支持Join类型	是否Shuffle/Sort	适用数据规模	性能
Shuffle sort Merge	等值	ALL	Shuffle + Sort	大规模	中等
Cartesian Product	等值/非等值	仅inner/cross join	Shuffle	小表	极差
Shuffle Hash Join	等值	ALL	Shuffle	中等规模	较优
Broadcast NestedLoop	等值/非等值	ALL	无	小表＋非等值条件	较差
Broadcast HashJoin	等值	不支持full join	无	小表+大表	最优

3.连接树结构

连接树(Join Tree)是一个二叉树，刻画每个表的Join顺序，叶子节点代表被连接的表，非叶子节点代表Join算子，根据树形结构可分为：

• 左深树(Left-Deep Tree)：树形结构向左倾斜，Join节点的右侧只能是叶子节点，很多数据库默认将左深树作为Join Reorder的搜索空间

• 右深树(Right-Deep Tree)：树形结构向右倾斜，左深树的镜像，Join节点的左侧只能是叶子节点

• 锯齿树(ZigZag Tree)：介于左深树和右深树之间，叶子节点在左右节点交换

• 浓密树(Bushy Tree)：结构最灵活，表可以按照任意顺序Join连接