偏斜连接优化

优化偏斜连接

The Problem

一组 MapReduce 作业完成 2 个大型数据表的联接，该作业首先根据联接键对表进行排序，然后将它们联接。Map 器将具有特定键的所有行分配给同一 Reducer。

例如，假设我们的表 A 的键列为“ id”，其值分别为 1、2、3 和 4，表 B 的键列为相似的列，其值分别为 1、2 和 3.
我们要进行与以下查询相对应的联接

• 从 A 中选择 A.id 加入 A.id = B.id 的 B

一组 Map 器读取表，然后根据键将它们提供给 Reducers。例如，键为 1 的行转到 Reducer R1，键为 2 的行转到 Reducer R2，依此类推。这些 Reducer 对 A 和 B 的值进行叉积运算，然后写入输出。 Reducer R4 从 A 获取行，但不会产生任何结果。

现在，我们假设 A 高度偏向于 id =1.减速器 R2 和 R3 将快速完成，但 R1 将持续很长时间，因此成为瓶颈。如果用户了解有关偏斜的信息，可以手动避免瓶颈，如下所示：

做两个单独的查询

• 从 A.id = B.id 上的 A 加入 B 中选择 A.id，其中 A.id<> 1;

• 从 A.id = B.id 的连接 B 中选择 A.id，其中 A.id = 1 和 B.id = 1；

第一个查询不会有任何偏差，因此所有的 Reducer 都将在大约同一时间完成。如果我们假设 B 仅有几行，且 B.id = 1，那么它将适合内存。因此，可以通过将 B 值存储在内存中的哈希表中来高效地完成连接。这样，联接可以由 Mapper 本身完成，数据不必传递到 Reducer。然后可以将两个查询的部分结果合并以得到最终结果。

• Advantages

• 如果少量的倾斜键占了很大一部分数据，它们将不会成为瓶颈。

• Disadvantages

• 表 A 和 B 必须被读取和处理两次。

  • 由于部分结果，结果也必须读取和写入两次。

  • 用户需要了解数据中的偏斜，并手动执行上述过程。

我们可以通过尝试减少偏斜键的处理来进一步改善这一点。首先读取 B 并将具有键 1 的行存储在内存中的哈希表中。现在运行一组 Map 器以读取 A 并执行以下操作：

• 如果它具有键 1，则使用 B 的哈希版本来计算结果。

• 对于所有其他键，将其发送到执行联接的 reducer。该化简器还将从 Map 器获得 B 行。

这样，我们最终只能读取 B 两次。 A 中的倾斜键仅由 Mapper 读取和处理，而不发送给 reducer。 A 中的其余键仅通过一个 Map/Reduce。

假设 B 的行很少，而键在 A 中倾斜。因此可以将这些行加载到内存中。

Hive Enhancements

*原始计划：*偏斜数据将从列表存储区中获取(请参阅List Bucketing设计文档)。 Hive 语法将没有任何补充。

*实现：*从 Hive 0.10.0 开始，可以将表创建为倾斜或更改为倾斜(在这种情况下，将倾斜在 ALTER 语句之后创建的分区)。此外，倾斜的表可以通过指定 STORED AS DIRECTORIES 选项来使用列表存储桶功能。有关详细信息，请参见 DDL 文档：Create Table，Skewed Tables和倾斜或存储为目录的变更表。