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

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-06-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

TensorFlow应用实战 | TensorFlow基础知识

hw = tf.constant("Hello World! Mtianyan love TensorFlow!")

1634
来自专栏丁科的专栏

Pytorch 学习笔记之自定义 Module

pytorch 是一个基于 python 的深度学习库。pytorch 源码库的抽象层次少,结构清晰,代码量适中。相比于非常工程化的 tensorflow,py...

4.1K2
来自专栏简书专栏

基于tensorflow的一元一次方程回归预测

安装tensorflow命令:pip install tensorflow 下面一段代码能够成功运行,则说明安装tensorflow环境成功。

994
来自专栏漫漫深度学习路

tensorflow学习笔记(三十三):ExponentialMovingAverage

ExponentialMovingAverage Some training algorithms, such as GradientDescent and M...

4856
来自专栏Script Boy (CN-SIMO)

Java中随机数的产生方式与原理

查阅随机数相关资料,特做整理 首先说一下java中产生随机数的几种方式 在j2se中我们可以使用Math.random()方法来产生一个随机数,这个产生的随机数...

2630
来自专栏应兆康的专栏

100个Numpy练习【4】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

4658
来自专栏数据结构与算法

1080 线段树练习 单点修改及区间查询

1080 线段树练习 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description 一...

2804
来自专栏LhWorld哥陪你聊算法

【推荐系统篇】--推荐系统之训练模型

经过之前的训练数据的构建可以得到所有特征值为1的模型文件,本文将继续构建训练数据特征并构建模型。

1551
来自专栏极客猴

Django 学习笔记之模型高级用法(下)

除了抽象模型,在模型中定义的字段都会成为表中的列。如果我们需要给模型指定其他一些信息,例如排序方式、数据库表名等,就需要用到 Meta。Meta 是一个可选的类...

912
来自专栏人工智能LeadAI

Python 设计模式初探

本文章是在阅读精通Python设计模式(中文版)(https://book.douban.com/subject/26829015/),以及阅读 Mask R-...

3576

扫码关注云+社区