每周学点大数据 | No.42 Hash join

No.42期

Hash join

Mr. 王：那我们就来看看 Hash join 具体是怎么做的吧。

两个表直接拿过来，我们不对其做任何排序和预处理。对这两个表进行一些随机分割，然后 Mapper 会去读取这些分割好的表块，并将它们划分为 Hash 桶。最后这些 Hash 桶根据相应的 Hash 值归入相应的 Reducer 中。

在 Reducer 中，将归入一个 Reducer 中的两个表的表块合并成一个表。于是每个 Reducer 的输入对应的就是相同的 Hash 值，因此就可以放到同一个Merger 里面去进行合并，此时只要进行传统的内存 Hash join 就可以了。

另外还有一种方法，是在 MapReduce 的扩展模块 Hive 中的一种合并方法，叫作 repartitionjoin。这是专门针对 MapReduce 提出的一种并行 join 方法。假设 L、 R 分别为两个输入的表，我们将其规范化成 key-value 对。

小可：可是此时，什么是 key、什么是 value 呢？

Mr. 王：很自然的，我们将要做连接的键值作为 key，一般就是两个表中相同的属性。经过 Map，相当于将这些 key-value 对根据 key 进行了分组。

通过洗牌，这些具有相同 Key 的元组就被分到了相同的组中，不管它是来自表 L 还是表 R。而在 Reducer 中，同一个 Reducer 收到的就是具有相同 key 的元组，可以直接根据表的名字做笛卡儿积。最后把结果组合起来输出就可以了。

小可：这个方法听起来不错，思路很清晰。

Mr. 王：不过这个方法也是有其缺点的。在算法的执行过程中，有可能需要缓存所有的记录这可能导致内存溢出。

小可：那么现在有什么好的解决办法了吗？

Mr. 王：这里有一个解决方案，首先在 Map 部分，我们将输出键值设为连接键和表名的一个组合。在 Partition 函数里面， HashCode 仅从连接键进行计算。

可以看出，使用前面的办法已经可以基于 MapReduce 来完成表的并行 join 操作了。

Mr.王：还有一个问题，我们前面一直讨论的是等值连接或者自然连接，而在很多应用背景中，都会提到一个叫作“相似连接”的概念。

小可：这个相似要怎么解释呢？

Mr. 王：比如你使用 Google 要查找某内容，但是输错了一个字母， Google 会提示你输入的是不是某个常用的候选值。这就是相似查询。

在传统的关系型数据库查询中，自然连接或者等值连接都可以严格地通过判等进行连接，而当执行相似的或者模糊判等操作时，它的计算时间一定会比精确比较更慢。于是我们定义了以下问题。

问题：一对来自两个数据集的记录，如果它们的相似性超过一定的程度，那么它们应该被连接，相似度可以根据特定应用来定义。

现在你能不能试着对这个问题给出一个朴素的解法呢？

小可：我觉得可以试着这样做，用 Mapper 将两个表分别 Map 到不同的键值上去，然后将它们的组合送到 Reducer 中，在 Reducer 中进行比较，我们观察它们的相似性是不是足够大，如果足够大就进行组合。

Mr. 王：这个做法虽然很简单，但是如果有 K 个块的话，我们就需要有 K2 个 Reducer，这是十分消耗计算资源的。它的中转数据也是很大的，有 K(R+S)个。所以这个方法虽然正确，但是太耗时了。

在实际的计算中，我们可以根据表中记录所具有的一定性质，来使用一些更加聪明的办法，使问题的求解变得更加高效。

我们举一个多元相似的例子。

假设有两个集合 M1 和 M2。下面的表示法表示 M1 中有 2 个 a、1 个 b、3 个 c；M2 中有 1 个 a、2 个 c、 2 个 d。

衡量这样的集合的相似度有一些比较经典的判据，比如：

Jaccard 相似度

Cosine 相似度

Dice 相似度

常见的计算也有如下几种。

• 单元函数

• 合取函数

• 析取函数

有了这些预备知识，我们就可以利用 MapReduce 来增加相似连接的可扩展性了。

在这里MapReduce 实际上完成两个工作，其中一个是计算前面提到的单元函数值，也就是集合的大小；另一个就是计算集合的合取函数值，然后通过单元函数和合取函数求解集合的析取函数值。

内容来源：灯塔大数据