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

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 就可以了。

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

内容来源:灯塔大数据

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JetpropelledSnake

Django学习笔记之Django QuerySet的方法

1325
来自专栏码农分享

SQL Server 多表数据增量获取和发布 4

最关键的在于获取捕获表信息(系统表中间_CT结尾的数据)。 根据网上资料查取,找到了获取当前捕获表时间区间范围内数据的方式。 见[SQL Server 多表...

1572
来自专栏IMWeb前端团队

Redux源码解析系列(四)-- combineReducers

本文作者:IMWeb 黄qiong 原文出处:IMWeb社区 未经同意,禁止转载 combindeReducer 字面意思就是用来合并reducer的...

2007
来自专栏JAVA后端开发

给mybatis添加自动建表,自动加字段的功能

以前项目用惯了hibernate,jpa,它有个自动建表功能,只要在PO里加上配置就可以了,感觉很爽. 但现在用mybatis,发现没有该功能,每次都加个字段...

5193
来自专栏青玉伏案

Oracle常用函数

前一段时间学习Oracle 时做的学习笔记,整理了一下,下面是分享的Oracle常用函数的部分笔记,以后还会分享其他部分的笔记,请大家批评指正。 1.Oracl...

2119
来自专栏郭霖

Android数据库高手秘籍(八)——使用LitePal的聚合函数

上一篇文章当中,我们已经把LitePal查询操作的所有用法都学习完了,很显然,LitePal帮我们提供了非常强大的查询API,使得我们可以极度轻松地完成各种类型...

3377
来自专栏JackieZheng

Hadoop阅读笔记(六)——洞悉Hadoop序列化机制Writable

  酒,是个好东西,前提要适量。今天参加了公司的年会,主题就是吃、喝、吹,除了那些天生话唠外,大部分人需要加点酒来作催化剂,让一个平时沉默寡言的码农也能成为一个...

2335
来自专栏编程

这或许是对小白最友好的python入门了吧——9,数字深入体验

先给大家介绍一个函数:range(),这个函数是用来干嘛的呢?很简单,数数的,怎么数呢,我先给大家演示一下: for num in range(1,5): ...

2159
来自专栏性能与架构

Mysql order by排序优化

1. 加大max_length_for_sort_data参数的设置 在MySQL中,排序算法分为两种,一是只加载排序字段到内存,排序完成后再到表中取其他字段,...

3635
来自专栏顶级程序员

MySQL 全文索引应用简明教程

本文从以下几个方面介绍下MySQL全文索引的基础知识: MySQL全文索引的几个注意事项 全文索引的语法 几种搜索类型的简介 几种搜索类型的实例 全文索引的几个...

38910

扫码关注云+社区

领取腾讯云代金券