首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每周学点大数据 | No.41 join 操作

每周学点大数据 | No.41 join 操作

作者头像
灯塔大数据
发布2018-04-04 17:56:25
7250
发布2018-04-04 17:56:25
举报
文章被收录于专栏:灯塔大数据灯塔大数据

No.41期

join 操作

Mr. 王:第一个话题就是 join 操作。 join 操作在数据库中还是非常常见的。

小可:这个 join 指的是笛卡儿积操作吗?

Mr. 王:还不一样,但是我们要从笛卡儿积说起。

先来回顾一下笛卡儿积操作。在数据库中,数据的基本单位就是元组。比如在学生成绩的数据库中,表头是学号、学生姓名和成绩,那么元组就是<0001,张三,99>、<0002,李四,90>这样的。

如果元组为r = (r1,…,rn)、s= (s1,…,sm),则定义r与s 的串接为:

rs= (r1,…,rn,s1,…,sm)

下面给出笛卡儿积的定义。

有两个关系R、S,其度分别为n,m,则它们的笛卡儿积是所有这样的元组集合:元组的前n个分量是R 中的一个元组,后m 个分量是S 中的一个元组。

R×S 的度为R 与S 的度之和,R×S 的元组个数为R 和S 的元组个数的乘积。

而R×S 这个集合为:

小可:嗯,笛卡儿积就是将 R 和 S 中的元组两两进行串接。

Mr. 王:笛卡儿积是各种连接操作的原型操作,如果给笛卡儿积操作添加各种限制条件,就是数据库中的各种连接操作 join。

连接的一种抽象表示叫作θ-join。

θ 是一个算术比较符号,当 θ 是等号时,这个连接为等值连接。

比如在这个例子中, θ 就定义为B<D,可以看到右边是连接结果。 这里还有一个很常用且很重要的连接,叫作自然连接。

自然连接是连接那些在相同的列上面有着相同的属性的元组。与等值连接的不同之处在于,自然连接要在结果中去掉重复的属性,而等值连接则不必。

小可:嗯,在自然连接中, r 和 s 中都有的 B 属性和 D 属性在其结果中被去掉了。

Mr. 王:在数据库系统的各种操作中,连接开销非常大,所需要的 CPU 资源和内存资源,甚至是保存中间结果的磁盘资源都是非常多的,于是我们产生了一个很自然的想法,就是做并行连接操作。

其实在 MapReduce 出现之前,就已经出现了很多解决高开销的连接操作办法;在 MapReduce出现之后,它也被用来解决并行连接问题。在这个方面也发表过很多篇论文,比如:

Map-Reduce-Merge: SimplifedRelational Data Processing on Large Clusters SIGMOD 07

Semi-join Computation on Distributed File Systems UsingMap-Reduce-Merge Model SAC10

Optimizing joins in a map-reduce environment VLDB09, EDBT2010

A Comparison of Join Algorithms for Log Processing in MapReduceSIGMOD 10

各种算法的实现思路如下表所示。

在本质上,这些算法是传统关系型数据库中连接算法的并行实现版本。

小可:在这些并行实现里面,除了 Map 和Reduce,还多了一个 Merge。

Mr. 王:没错,这些算法在得到 MapReduce 执行结果之后,要额外经历一个 Merge 过程,才能得到最终的连接结果。

比如Sort-Merge join, Mapper 对两个表分别进行一次区间 partition,生成排序的区间桶,每个桶对应一个 Reducer。

然后 Reducer 会从 Mapper 中读取桶,这些桶是落在同一个区间内的数据,接下来进行归并,相当于把两个表分别进行了一次归并排序。最后 Merge 操作对这些排好序的桶执行 Sort merge join。

Hashjoin 与之类似, Mapper 对两个表分别进行一次 Hash partition,生成排序的 Hash 桶,每个桶对应一个 Reducer。

会从所有的 Mapper 中读取桶,使用 Hash 表分组和聚集这些记录,当然这要选取和 Mapper 一样的 Hash 函数,无须进行排序。等到了 Merge 阶段,只需要进行内存的 Hash Join 就可以了。

小可摇了摇头,说:这一段没太听明白,都是一些很抽象的概念。

内容来源:灯塔大数据

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-06-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 灯塔大数据 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
数据库
云数据库为企业提供了完善的关系型数据库、非关系型数据库、分析型数据库和数据库生态工具。您可以通过产品选择和组合搭建,轻松实现高可靠、高可用性、高性能等数据库需求。云数据库服务也可大幅减少您的运维工作量,更专注于业务发展,让企业一站式享受数据上云及分布式架构的技术红利!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档