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 实际上完成两个工作,其中一个是计算前面提到的单元函数值,也就是集合的大小;另一个就是计算集合的合取函数值,然后通过单元函数和合取函数求解集合的析取函数值。
内容来源:灯塔大数据