CN105095455A - 一种数据连接优化方法和数据运算系统 - Google Patents

Abstract

本发明实施例提供一种数据连接优化方法和数据运算系统，涉及通信领域，能够解决现有的提高数据连接效率的连接方法存在的使用范围局限的问题。该方法将数据连接操作划分为两个MapReduce阶段，第一阶段对连接元素的取值进行统计，确定连接元素所属的频繁取值集合，第二阶段的Map在计算节点的内存中载入查询向量以及连接元素的频繁取值集合之间的交集运算，确定数据库中的某个记录是否需要引起连接操作，这样不需要引起连接操作的元素的键值对就不需要发送至Reduce节点。本发明实施例用于面向MapReduce的数据连接优化。

Description

一种数据连接优化方法和数据运算系统

技术领域

本发明涉及通信领域，尤其涉及一种数据连接优化方法和数据运算系统。

背景技术

在数据处理中，数据的连接操作是非常常见且耗时的。例如有两个数据库R和S，R包含数据条目A和B，记为R(A，B)，S包含数据条目B和C，记为S(B，C)。表示R和S之间的连接操作，连接条件是R.B＝S.B。MapReduce是当下大数据处理技术中的主流编程模型，将数据处理任务抽象为map任务和reduce任务，在map阶段完成对数据的过滤处理，在reduce阶段完成为数据的聚集处理。

在该MapReduce编程模型中，最简单的等值连接操作为reducesidejoin，其中，在reducesidejoin中，R和S的所有元素都得传输给reduce，这对于网络资源的消耗较大，但是，有些数据是可以不用传输的，例如对于R.B中某一个取值，若该值在S.B中不出现时是不需要传输给reduce的，为了优化MapReduce中连接的效率，业界引入了mapsidejoin、Semijoin等连接优化方法。

其中，在mapsidejoin这种连接方法中，可以选择R和S中较小的一个表，假设为R，再将R复制多份，让每个map节点的内存中存在一份，然后只扫描大表S，这样对于S中的每一条记录，在哈希表中查找是否有相同的key记录如果有，则连接后输出即可，但是这种连接方法只适用于两个待连接表中一个表非常大，另一个表非常小，以至于小表可以直接存放到内存中，但是当两个表都非常大时，就会撑爆map节点的内存，使用范围局限；在Semijoin连接方法中，也是选取一个小表，假设为R，先将R.B抽取出来，保存到文件T中，并将文件T存放至内存中，在map阶段，将T复制到各个map节点上，然后检查S.B的每个取值，若其值不在T中，则将S中对应的记录过滤掉，其余的记录采用与mapsidejoin相同的操作，这样也会存在mapsidejoin中使用范围局限的问题。

发明内容

本发明实施例提供一种数据连接优化方法和数据运算系统，能够解决现有的提高数据连接效率的连接方法存在的使用范围局限的问题。

第一方面，提供一种数据连接优化方法，包括：

m₁个第一Map节点分别统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果，并将所述统计结果发送至所述中心节点，使得所述中心节点将所述统计结果发送至n₁个第一Reduce节点，其中同一连接元素的统计结果发送至同一第一Reduce节点；

所述n₁个第一Reduce节点分别根据所述统计结果获取各自的Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数，根据所述记录总数与预设的阈值确定所述连接元素所属的第一集合，并将所述第一集合发送至所述中心节点，所述第一集合用于表征所述连接元素的频繁取值情况；

所述中心节点对所述第一集合中的连接元素重新排序，得到相应的第二集合，并对所述第二集合中的连接元素执行向量插入操作，获取所述第二集合对应的查询向量；

所述中心节点重新将所述数据库分配给m₂个第二Map节点，并将所述第一集合和所述查询向量发送给所述m₂个第二Map节点；

所述m₂个第二Map节点分别根据分配的第二数据块中的记录和所述查询向量确定所述记录中的连接元素所属的第一集合，并根据所述第一集合之间针对所述连接元素的交集运算确定是否对所述连接元素进行连接操作。

结合第一方面，在第一方面的第一种可能实现的方式中，所述m₁个第一Map节点分别统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果包括：

所述m₁个第一Map节点分别调用map函数从所述第一数据块中抽取出每一条包括所述连接元素的记录，并输出第一键值对，所述第一键值对包括所述连接元素、表征所述连接元素的数据来源的标识和计数，所述计数为1；

针对所述第一数据块中同一连接元素，将所述表征所述连接元素的数据来源的标识相同的所述第一键值对中的计数累加，得到所述第一数据块中相同数据来源的同一连接元素对应的记录的数量。

结合第一方面或第一方面的第一种可能实现的方式，在第一方面的第二种可能实现的方式中，若所述数据库包括第一数据库和第二数据库，则所述根据所述记录总数与预设的阈值确定所述连接元素所属的第一集合包括：

当所述第一Reduce节点中所述连接元素来源于所述第一数据库的第一记录总数小于所述阈值，且来源于所述第二数据库的第二记录总数小于所述阈值时，若所述第一记录总数不等于零，则确定所述连接元素所属的第一集合为集合R_thin，若所述第二记录总数不为零，则确定所述连接元素所属的第一集合为集合S_thin，所述集合R_thin和所述集合S_thin均包括所述第一数据库和所述第二数据库中稀疏出现的连接元素；

若所述第一记录总数大于或等于所述阈值，且所述第一记录总数大于或等于所述第二记录总数，则确定所述连接元素所属的第一集合为集合R_den，所述集合R_den包括在所述第一数据库中高频出现，并且出现次数大于所述第二数据库中的出现次数的连接元素；若且所述第二记录总数不为零，则确定所述连接元素所属的第一集合为集合S_Rden，所述集合S_Rden包括在所述第二数据库中有出现，但属于所述集合R_den的连接元素；

若所述第二记录总数大于或等于所述阈值，且所述第二记录总数大于或等于所述第一记录总数，则确定所述连接元素所属的第一集合为集合S_den，所述集合S_den包括在所述第二数据库中高频出现，并且出现次数大于所述第一数据库中的出现次数的连接元素；若且所述第一记录总数不为零，则确定所述连接元素所属的第一集合为集合R_Sden，所述集合R_Sden包括在所述第一数据库中有出现，但属于所述集合S_den的连接元素。

结合第一方面的第二种可能实现的方式，在第二方面的第三种可能实现的方式中，所述中心节点对所述第一集合中的连接元素重新排序，得到相应的第二集合，并对所述第二集合中的连接元素执行向量插入操作，获取所述第二集合对应的查询向量包括：

所述中心节点对所述第一集合为所述集合R_den、所述集合R_Sden、所述集合S_den和所述集合S_Rden中的连接元素，按照所述连接元素值的大小重新排序，得到相应的第二集合，并记录所述连接元素在所述第二集合中的位置；

针对所述集合R_den、所述集合S_Rden、所述集合S_den和所述集合S_Rden相应的第二集合，根据预定义的初始向量对所述第二集合中的每个连接元素执行所述向量插入操作，获取所述第二集合对应的查询向量。

结合第一方面的第三种可能实现的方式，在第一方面的第四种可能实现的方式中，在根据分配的第二数据块中的记录和所述查询向量确定所述记录中的连接元素所属的第一集合后，所述方法还包括：

所述m₂个第二Map节点分别生成所述连接元素对应的第二键值对，所述第二键值对包括所述连接元素、表征所述连接元素数据来源的标识、所述连接元素所属的第一集合的标识以及所述连接元素对应的非连接元素。

结合第一方面的第四种可能实现的方式，在第一方面的第五种可能实现的方式中，所述根据所述第一集合之间针对所述连接元素的交集运算确定是否对所述连接元素进行连接操作包括：

在确定所述记录中的连接元素所属的第一集合后，若根据所述查询向量确定所述连接元素不在与所述第一集合交集不为空的另一第一集合中，则确定不对所述连接元素进行连接操作。

结合第一方面的第五种可能实现的方式，在第一方面的第六种可能实现的方式中，所述方法还包括：

所述m₂个第二Map节点分别根据所述第二键值对所属的第一集合确定所述第二键值对相应的第二Reduce节点的范围，并将所述第二键值对发送至所述范围内的n₂个第二Reduce节点；

所述n₂个第二Reduce节点分别根据所述第二键值对所属的第一集合将所述第二键值对归为不同的队列，并对所述队列中的第二键值对进行连接操作。

结合第一方面的第六种可能实现的方式，在第一方面的第七种可能实现的方式中，所述m₂个第二Map节点分别根据所述第二键值对所属的第一集合确定所述第二键值对相应的第二Reduce节点的范围，并将所述第二键值对发送至所述范围内的n₂个第二Reduce节点包括：

若所述连接元素属于所述集合S_thin或所述集合R_thin，则将相同的所述连接元素对应的第二键值对发送至同一第二Reduce节点；

若所述连接元素属于所述集合R_den，则所述第二Map节点将所述连接元素对应的第二键值对随机发送至编号位于第一范围内的任一第二Reduce节点，所述第一范围为起始Reduce编号，至所述起始Reduce编号与所述第一数据库中所述连接元素的记录总数与每个Reduce节点平均处理的记录数的比值的和之间的编号；

若所述连接元素属于所述集合S_den，则所述第二Map节点将所述连接元素对应的第二键值对随机发送至编号位于第二范围内的任一第二Reduce节点，所述第二范围为起始Reduce编号，至所述起始Reduce编号与所述第二数据库中所述连接元素的记录总数与每个Reduce节点平均处理的记录数的比值的和之间的编号；

若所述连接元素属于所述集合R_Sden，则所述第二Map节点将所述连接元素对应的第二键值对广播给编号位于第三范围内的所有第二Reduce节点，所述第三范围为起始Reduce节点编号，至所述起始Reduce编号与所述第二数据库中所述连接元素的记录总数与每个Reduce节点平均处理的记录数的比值的和之间的编号；

若所述连接元素属于所述集合S_Rden，则所述第二Map节点将所述连接元素对应的第二键值对广播给编号位于第四范围内的所有第二Reduce节点，所述第四范围为起始第二Reduce编号，至所述起始第二Reduce编号与所述第一数据库中所述连接元素的记录总数与每个第二Reduce节点平均处理的记录数的比值的和之间的编号。

结合第一方面的第七种可能实现的方式，在第一方面的第八种可能实现的方式中，所述每个第二Reduce节点平均处理的记录数为：所述第一数据库的文件大小与所述第一数据库中单条记录大小的比值，加上所述第二数据库的文件大小与所述第二数据库中的单条记录大小的比值的和，与所述第二Reduce节点的数量的比值。

结合第一方面的第七种可能实现的方式或第八种可能实现的方式，在第一方面的第九种可能实现的方式中，所述根据所述第二键值对所属的第一集合将所述第二键值对归为不同的队列，并对所述队列中的第二键值对进行连接操作包括：

对属于所述集合R_den的连接元素对应的第二键值对组成的队列和属于所述集合S_Rden的连接元素对应的键值对组合的队列进行连接操作；

对属于所述集合R_Sden的连接元素对应的第二键值对组成的队列和属于所述集合S_den的连接元素对应的键值对组成的队列进行连接操作；

对属于所述集合R_thin的连接元素对应的第二键值对组成的队列和属于所述集合S_thin的连接元素对应的键值对组成的队列进行连接操作。

第二方面，提供一种数据运算系统，包括m₁个Map节点、n₁个第一Reduce节点、中心节点、m₂个第二Map节点，其中：

所述m₁个Map节点，分别用于统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果，并将所述统计结果发送至所述中心节点，使得所述中心节点将所述统计结果发送至n₁个第一Reduce节点，其中同一连接元素的统计结果发送至同一第一Reduce节点；

所述n₁个第一Reduce节点，分别用于根据所述统计结果获取各自的Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数，根据所述记录总数与预设的阈值确定所述连接元素所属的第一集合，并将所述第一集合发送至所述中心节点，所述第一集合用于表征所述连接元素的频繁取值情况；

所述中心节点，用于对所述第一集合中的连接元素重新排序，得到相应的第二集合，并对所述第二集合中的连接元素执行向量插入操作，获取所述第二集合对应的查询向量；

所述中心节点，还用于重新将所述数据库分配给m₂个第二Map节点，并将所述第一集合和所述查询向量发送给所述m₂个第二Map节点；

所述m₂个第二Map节点，分别用于根据分配的第二数据块中的记录和所述查询向量确定所述记录中的连接元素所属的第一集合，并根据所述第一集合之间针对所述连接元素的交集运算确定是否对所述连接元素进行连接操作。

本发明实施例提供一种数据连接优化方法和数据运算系统，m₁个第一Map节点分别统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果，并将统计结果发送至中心节点，使得中心节点将统计结果发送至n₁个第一Reduce节点，其中同一连接元素的统计结果发送至同一Reduce节点；n₁个Reduce节点分别根据统计结果获取各自的Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数，根据记录总数与预设的阈值确定连接元素所属的第一集合，并将第一集合发送至中心节点，第一集合用于表征连接元素的频繁取值情况；中心节点对第一集合中的连接元素重新排序，得到相应的第二集合，并对第二集合中的连接元素执行向量插入操作，获取第二集合对应的查询向量；中心节点重新将数据库分配给m₂个第二Map节点，并将第一集合和查询向量发送给m₂个第二Map节点；m₂个第二Map节点分别根据分配的第二数据块中的记录和查询向量确定记录中的连接元素所属的第一集合，并根据第一集合之间针对连接元素的交集运算确定是否对连接元素进行连接操作；这样一来，通过向量插入操作判断连接元素所属的第一集合，进而根据连接元素的交集运算可确定该连接元素是否要引起连接操作，即需不需要传递至Reduce节点，以减少网络传输，这样不局限于现有技术中在一个表较大，一个表较小的情况下确定是否传输记录来减小网络传输，能够解决现有的提高数据连接效率的连接方法存在的使用范围局限的问题。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例提供的一种数据运算系统的结构示意图；

图2为本发明实施例提供的一种数据连接优化方法的流程示意图；

图3为本发明实施例提供的另一种数据连接优化方法的流程示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明实施例提供一种数据运算系统1，如图1所示，包括：m₁个第一Map节点、n₁个第一Reduce节点、中心节点和m₂个第二Map节点，其中：

m₁个Map节点，分别用于统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果，并将统计结果发送至中心节点，使得中心节点将统计结果发送至n₁个第一Reduce节点，其中同一连接元素的统计结果发送至同一第一Reduce节点；

n₁个第一Reduce节点，分别用于根据统计结果获取各自的Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数，根据记录总数与预设的阈值确定连接元素所属的第一集合，并将第一集合发送至中心节点，第一集合用于表征连接元素的频繁取值情况；

中心节点，用于对第一集合中的连接元素重新排序，得到相应的第二集合，并对第二集合中的连接元素执行向量插入操作，获取第二集合对应的查询向量；

中心节点，还用于重新将数据库分配给m₂个第二Map节点，并将第一集合和查询向量发送给m₂个第二Map节点；

m₂个第二Map节点，分别用于根据分配的第二数据块中的记录和查询向量确定记录中的连接元素所属的第一集合，并根据第一集合之间针对连接元素的交集运算确定是否对连接元素进行连接操作。

这样一来，通过向量插入操作判断连接元素是否要引起连接操作，即需不需要传递至第二Reduce节点，以减少网络传输，这样不局限于现有技术中在一个表较大，一个表较小的情况下确定是否传输记录来减小网络传输，能够解决现有的提高数据连连接效率的连接方法存在的使用范围局限的问题。

基于上述数据运算系统，下面对本数据运算系统执行的方法作以具体说明，因此，本发明实施例提供一种数据连接优化方法，如图2所示，包括：

201、m₁个第一Map节点分别统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果，并将统计结果发送至中心节点，使得中心节点将统计结果发送至n₁个第一Reduce节点，其中同一连接元素的统计结果发送至同一第一Reduce节点。

202、n₁个第一Reduce节点分别根据统计结果获取各自的Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数，根据记录总数与预设的阈值确定连接元素所属的第一集合，并将第一集合发送至中心节点，第一集合用于表征连接元素的频繁取值情况。

203、中心节点对第一集合中的连接元素重新排序，得到相应的第二集合，并对第二集合中的连接元素执行向量插入操作，获取第二集合对应的查询向量。

204、中心节点重新将数据库分配给m₂个第二Map节点，并将第一集合和查询向量发送给m₂个第二Map节点；

205、m₂个第二Map节点分别根据分配的第二数据块中的记录和查询向量确定记录中的连接元素所属的第一集合，并根据第一集合之间针对连接元素的交集运算确定是否对连接元素进行连接操作。

具体而言,本发明实施例可通过两阶段的MapReduce过程实现确定某一连接元素的记录是否要引起连接操作，即需不需要传递至Reduce节点，以减少网络传输。第一阶段的MapReduce主要是对连接元素的取值进行统计，第二阶段的MapReduce根据第一阶段的统计结果完成连接操作。

假设有两个数据库R和S，R包含数据条目A和B，记为R(A，B)，S包含数据条目B和C，记为S(B，C)。表示R和S之间的连接操作，连接条件是R.B＝S.B，第一阶段的MapReduce只对R.B和S.B进行处理，也就是只处理连接元素，节点之间传递的数据也只与连接元素B相关，与R.A和S.C无关。

具体实现的过程中，以上述数据库R为第一数据库，数据库S为第二数据库为例，在步骤201之前，即在m₁个第一Map节点获取统计结果之前，中心节点上的主程序可先将数据库R和数据库S分为M₁个数据块，并将其分配给m₁个第一Map节点，每个第一Map节点处理M₁/m₁块数据，即M₁/m₁个第一数据块。

在步骤201中，对于m₁个第一Map节点来说，m₁个第一Map节点分别统计中心节点对数据库R和数据库S分配的第一数据块中来源于同一数据库的同一连接元素B对应的记录，以获取统计结果。

具体地，第一Map节点可以调用map函数从第一数据块中抽取出每一条包括连接元素B的记录，并输出第一键值对，该第一键值对包括连接元素B、表征连接元素数据来源的标识和计数，计数为1。

示例性的，第一Map节点调用map函数，抽取出数据库R或数据库S中的每一条记录，对于R中的记录，输出(key，0:1)；对于数据库S中的记录，输出(key，1:1)；其中，key的值为连接元素B的取值，value部分的值由tag：val组成，tag标识了数据来源(0代表来自数据库R，1代表来自数据库S)，计数1表示B的取值出现了一次。

第一Map节点再针对第一数据块中同一连接元素，将表征连接元素的数据来源的标识相同的第一键值对中的计数累加，得到第一数据块中相同数据来源的同一连接元素对应的记录的数量。这一阶段，可称为shuffle阶段，即针对相同的key,若value.tag相同，则将value.val进行累加，最终，当所有的map任务都结束时，生成数据格式为(key,tag:val)的中间文件，其中tag标识了该第一数据块中的连接元素的数据来源为R或S，val表示输出到该中间文件中key和tag相同的记录数。

所有的第一Map节点再将生成的数据格式发送给中心节点(主程序)，启动Reduce过程。中心节点按照定义好的哈希函数，依据连接元素的哈希结果将统计结果发送至n₁个第一Reduce节点，其中，同一连接元素的统计结果即对应的数据格式发送至同一第一Reduce节点。

在步骤202中，第一Reduce节点再根据统计结果获取该第一Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数。具体地，第一Reduce节点的Reduce任务检查接收到的数据格式，对key和tag相同的记录执行val的累积操作，累积的结果如果表示为(key，tag：val)，可包括(key，0：val_R)和(key，1：val_S)，其中，key表示连接元素B的值，0和1表示数据来源，val_R表示数据库R中B的取值为key时的记录总数，val_S表示数据库S中B的取值为key时的记录总数。

这时第一阶段的Reduce任务结束，并输出最终结果，即执行步骤202中的根据记录总数与预设的阈值确定连接元素所属的第一集合。

具体地，最终结果的记录规则可以为：

对于每一个连接元素key：

当第一Reduce节点中连接元素来源于第一数据库的第一记录总数小于阈值，且来源于第二数据库的第二记录总数小于阈值时，若第一记录总数不等于零，则确定连接元素所属的第一集合为集合R_thin，若第二记录总数不为零，则确定连接元素所属的第一集合为集合S_thin，集合R_thin和集合S_thin均包括第一数据库和第二数据库中稀疏出现的连接元素。也可以表示为：当val_R<Θ&&val_S<Θ时，若val_R≠0，则记录R_thin＝R_thin∪{key}；若val_S≠0，则记录S_thin＝S_thin∪{key}；Θ表示阈值，当然，如果val_R和val_S同时不为零，就将该key同时记录至集合R_thin和集合S_thin中；

否则，若第一记录总数大于或等于阈值，且第一记录总数大于或等于第二记录总数，则确定连接元素所属的第一集合为集合R_den，集合R_den包括在第一数据库中高频出现，并且出现次数大于第二数据库中的出现次数的连接元素；若且第二记录总数不为零，则确定连接元素所属的第一集合为集合S_Rden，集合S_Rden包括在第二数据库中有出现，但属于集合R_den的连接元素，也可以表示为：若val_R>＝Θ&&val_R>＝val_S：则记录R_den＝R_den∪{(key，val_R)}；若val_S≠0，记录S_Rden＝S_Rden∪{(key，val_R)}；

若第二记录总数大于或等于阈值，且第二记录总数大于或等于第一记录总数，则确定连接元素所属的第一集合为集合S_den，集合S_den包括在第二数据库中高频出现，并且出现次数大于第一数据库中的出现次数的连接元素；若且第一记录总数不为零，则确定连接元素所属的第一集合为集合R_Sden，集合R_Sden包括在第一数据库中有出现，但属于集合S_den的连接元素，也可以表示为：若val_S>＝Θ&&val_S>＝val_R：则记录S_den＝S_den∪{(key，val_S)}；若val_R≠0，记录R_Sden＝R_Sden∪{(key，val_S)}；

因此，当第一阶段的MapReduce执行完毕后，一共生成了六个集合，其标识及含义如下表1所示：

表1

从上述定义及集合的生成过程，集合之间针对key的交集运算有如下表2所示结果：

表2

进一步的，第一Reduce节点再将第一集合发送至中心节点，并开始进入第二阶段的MapReduce，第二阶段的MapReduce执行连接操作。

但是，在执行第二阶段的MapReduce之前，中心节点的主程序先进入准备阶段，即执行步骤203，对第一阶段Reduce的结果进行进一步的处理，处理方式如下：

中心节点对第一集合中的连接元素重新排序，得到相应的第二集合，并对第二集合中的连接元素执行向量插入操作，获取第二集合对应的查询向量。

具体地，中心节点可对第一集合为集合R_den、集合R_Sden、集合S_den和集合S_Rden中的连接元素，按照连接元素值的大小重新排序，得到相应的第二集合，并记录连接元素在第二集合中的位置，记为seq(key)，生成的第二集合可相应的表示为集合R‘_den、集合R’_Sden、集合S‘_den和集合S’_Rden，其中的元素可表示为{(key，seq(key))}。

这里不对集合R_thin和集合S_thin进行处理，是由于属于稀疏取值的集合R_thin和集合S_thin可与现有技术相同，将其连接元素对应的键值对都发送至第二Reduce节点进行连接操作。其中，第二Reduce节点可可能与第一Reduce节点相同，也可能不同。

而对于集合R_den、集合R_Sden、集合S_den和集合S_Rden相应的第二集合，根据预定义的初始向量对第二集合中的每个连接元素执行向量插入操作，获取第二集合对应的查询向量。具体地，对于集合R_den、集合R_Sden、集合S_den和集合S_Rden，假设定义的初始BloomFilter向量，分别记为：对于集合R‘_den中的每一个元素执行向量中的插入操作，对于集合R’_Sden中的每一个元素执行向量中的插入操作，对于集合S‘_den中的每一个元素执行向量中的插入操作，和对集合S’_Rden中的每一个元素执行向量中的插入操作，最终生成4个BloomFliter向量，即查询向量，并且这4个向量均有如下性质：若某个元素key在某个BloomFilter向量中的查询结果lookup(key)为假，则该key肯定不在该BloomFilter向量对应的集合中。

数据运算系统进入第二阶段的MapReduce过程，具体可以如下：

在步骤204中，中心节点先重新将数据库分配给m₂个第二Map节点，并将第一集合和查询向量发送给m₂个第二Map节点。这里需要将数据路重新分配给m₂个第二Map节点是由于第二阶段进行Map操作的节点数和工作量不同，需要重新对数据库分配节点。

具体地，中心节点中的主程序先将数据库R和数据库S重新分为M₂块，并将其分配给m₂个Map节点，每个节点处理M₂/m₂块数据。主程序还将第一集合为集合R_den、集合R_Sden、集合S_den和集合S_Rden的集合以及查询向量发送给m₂个Map节点，每个Map节点将集合R_den、集合R_Sden、集合S_den、集合S_Rden以及缓存至内存，以便对其分块数据执行map操作。

与第一阶段的对数据块执行的map操作不同的是，第二阶段的map操作不仅与R.B和S.B有关，还与R.A和R.C有关。

在步骤205中，m₂个Map节点分别根据分配的第二数据块中的记录和查询向量确定记录中的连接元素所属的第一集合，并根据第一集合之间针对连接元素的交集运算确定是否对连接元素进行连接操作。

其中，在根据分配的第二数据块中的记录和查询向量确定记录中的连接元素所属的第一集合后，可生成连接元素对应的第二键值对，第二键值对包括连接元素、表征连接元素数据来源的标识、连接元素所属的第一集合的标识以及连接元素对应的非连接元素。具体可以为Map节点抽取出第二数据块中的记录，并根据查询向量确定记录中的连接元素所属的第一集合，生成形式为(key，value)的第二键值对，其中，key为连接元素B的值，value是一个形如(tagS，tagF，val)的复合值，tagS标识记录来源于数据库R或数据库S，tagF标识key属于六个集合R_den、R_Sden、R_thin、S_den、S_Rden和S_thin中的哪一个，val记录非连接元素的值。

具体地，根据查询向量确定连接元素所属的第一集合的过程可以为：

对于R中的某个记录，记R.B的取值为key，记R.A为val；

a)若 则key∈R_thin，生成的第二键值对为(key，0：R_thin：val)，也就是说，R中的某个记录中的key通过查询确定其既不在R_den中，也不在R_Sden中时，那么key属于集合R_thin，可按照传统的方式将key对应的第二键值对发送至Reduce进行连接操作；

b)否则，当时，若则key∈R_Sden，即如果key不在集合R_thin和集合R_den中，那么key在集合R_Sden中，这时若则不做处理，也就是说，如果在集合R_Sden中没有查询到该key，则确定该key不引起连接操作。这是由于根据上述表2中的集合运算，集合R_Sden只与集合S_den的交集不为空，因此当key∈R_Sden时，如果该key的取值不在集合S_den中，那么确定该key不引起连接操作，故而不需要传递该key对应的第二键值对；否则，如果该key在集合S_den中，那么确定该key引起连接操作，需要将其对应的第二键值对发送至第二Reduce节点，且第二键值对为(key，0：R_Sden：val)；

c)否则，key∈R_den，即key不在集合R_thin和集合R_Sden时，那么key∈R_den，但是若则确定该key不引起连接操作，不需要传递至第二Reduce节点，这是由于集合R_den只与集合S_Rden的交集不为空，这样当key∈R_den时，如果该key的取值不在集合S_Rden中，那么确定该值不引起连接操作，故而不需要传递至第二Reduce节点。由于key还属于高频出现的取值，因此不需要传递的数据记录较多，对于网络优化的作用比较明显；否则，如果该key在集合S_Rden中，那么该值需要引起连接操作，生成的第二键值对为(key，0：S_Rden：val)；

同理，对于数据库S中的某个记录，记S.B的取值为key，记S.C为val；

a)若 则key∈S_thin，生成的第二键值对为(key，1：S_thin：val)，确定其引起连接操作；

b)否则，当时，若则key∈S_Rden；

若则由于集合S_Rden只与集合R_den的交集不为空，则当key∈S_Rden时，若该取值不在集合R_den，则确定该值不引起连接操作，不需要将其传递至Reduce；

c)否则，当且时，key∈S_den；

若则由于集合S_den只与集合R_Sden的交集不为空，则当key∈S_den时，若该取值不在集合R_Sden，则确定该值不引起连接操作，不需要将其传递至Reduce；

否则，如果该取值在集合R_Sden中，那么可生成的第二键值对为(key，1：R_Sden：val)。

这样一来，对于确定不引起连接操作的键值对则不发送至Reduce，可减少网络中需要传递的数据，提高网络传输的效率，相比于现有技术中数据连接操作的mapsidejoin或SemiJoin来说，本申请不限定数据库的大小，适合任意场景。

因此，本发明实施例提供一种数据连接优化方法，m₁个第一Map节点，分别用于统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果，并将统计结果发送至中心节点，使得中心节点将统计结果发送至n₁个第一Reduce节点，其中同一连接元素的统计结果发送至同一第一Reduce节点；第一Reduce节点分别根据统计结果获取各自的Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数，根据记录总数与预设的阈值确定连接元素所属的第一集合，并将第一集合发送至中心节点，第一集合用于表征连接元素的频繁取值情况；中心节点对第一集合中的连接元素重新排序，得到相应的第二集合，并对第二集合中的连接元素执行向量插入操作，获取第二集合对应的查询向量；中心节点重新将数据库分配给m₂个第二Map节点，并将第一集合和查询向量发送给m₂个第二Map节点；m₂个第二Map节点分别根据分配的第二数据块中的记录和查询向量确定记录中的连接元素所属的第一集合，并根据第一集合之间针对连接元素的交集运算确定是否对连接元素进行连接操作；这样一来，通过向量插入操作判断连接元素是否要引起连接操作，即需不需要传递至第二Reduce节点，以减少网络传输，这样不局限于现有技术中在一个表较大，一个表较小的情况下确定是否传输记录来减小网络传输，能够解决现有的提高数据连连接效率的连接方法存在的使用范围局限的问题。

对于现有技术中的数据连接操作的mapsidejoin或SemiJoin来说，其不仅存在适用部分场景的问题，还存在负载均衡的问题。这是由于在其Map和Reduce的工作模式中，Reduce阶段是按照key的取值来进行任务分派的，相同key值的记录被传递至同一个Reduce节点，这样对于连接元素B来说，如果某几个B的取值的数据记录特别多，那么负责这些值的Reduce节点上分派的任务会比较重，从而造成Reduce任务分配不均，Reduce节点的负载不均衡。

因此，为了解决负载不均衡的问题，在上述实施例为了减少网络传输的基础上，在第二阶段的Map阶段执行后生成第二键值对后，可将需要传递的第二键值对按照如下规则发送给P个第二Reduce节点，对于不同集合的连接元素的第二键值对，对应发送给其中的n₂个第二Reduce节点，P为所有集合的元素对应的第二键值对发送的n₂个第二Reduce节点的和。

因此，如图3所示，上述方法实施例还包括：

206、m₂个第二Map节点分别根据第二键值对所属的第一集合确定第二键值对相应的第二Reduce节点的范围，并将第二键值对发送至该范围内的n₂个第二Reduce节点。

207、n₂个第二Reduce节点分别根据第二键值对所属的第一集合将第二键值对归为不同的队列，并对队列中的第二键值对进行连接操作。

在步骤206中，首先，定义每个第二Reduce节点平均处理P_avg条记录，且P_avg为：数据库R的文件大小与数据库R中的单条记录大小的比值，加上数据库S的文件大小与数据库S中的单条记录大小的比值的和，与第二Reduce节点的数量的比值，可表示为：[R文件大小/单条记录大小+S文件大小/单条记录大小]/P。

这样，如果第二键值对中的value：tagF＝S_thin或R_thin，即若连接元素属于集合S_thin或集合R_thin，则将相同的连接元素对应的第二键值对发送至同一第二Reduce节点，即按照传统的方式将相同的连接元素对应的第二键值对都发送给第二Reduce节点进行连接处理操作。这是由于当key属于稀疏取值时，将其按照传统的方式分配给第二Reduce节点不会引起负载不均衡；

如果第二键值对中的连接元素属于集合R_den，则将连接元素对应的第二键值对随机发送至编号位于第一范围内的任一第二Reduce节点，第一范围为起始Reduce编号，至起始Reduce编号与第一数据库中连接元素的记录总数与每个第二Reduce节点平均处理的记录数的比值的和之间的编号，可表示为：[seq(key)modP，(seq(key)+val_R/P_avg)modP]；如果第二键值对中的连接元素属于集合S_den，则将连接元素对应的第二键值对随机发送至编号位于第二范围内的任一第二Reduce节点，第二范围为起始Reduce编号，至起始Reduce编号与第二数据库中连接元素的记录总数与每个第二Reduce节点平均处理的记录数的比值的和之间的编号，可表示为：[seq(key)modP，(seq(key)+val_S/P_avg)modP]。

这样，当key属于高频取值时，若将其按照传统的方式分配给第二Reduce节点，则被指派给高频的取值的第二Reduce节点负载会远大于其它节点，为此，本申请将高频取值挑选出来，并按照高频取值出现的次数按需地为其分配第二Reduce节点，缓解取值分布不均带来的负载均衡问题。

若连接元素属于集合R_Sden，则将连接元素对应的第二键值对广播给编号位于第三范围内的所有第二Reduce节点，第三范围为起始第二Reduce节点编号，至起始Reduce编号与第二数据库中连接元素的记录总数与每个第二Reduce节点平均处理的记录数的比值的和之间的编号，可表示为：[seq(key)modP，(seq(key)+val_S/P_avg)modP]；若连接元素属于集合S_Rden，则将连接元素对应的第二键值对广播给编号位于第四范围内的所有第二Reduce节点，第四范围为起始Reduce编号，至起始Reduce编号与第一数据库中连接元素的记录总数与每个第二Reduce节点平均处理的记录数的比值的和之间的编号，可表示为：[seq(key)modP，(seq(key)+val_R/P_avg)modP]。

这样，由于集合R_Sden中的key是数据库R中的稀疏元素，集合S_Rden中的key是数据库S中的稀疏元素，因此，选择将集合R_Sden或集合S_Rden中的记录进行广播给第二Reduce节点给网络带来的压力较小。

在步骤207中，第二Reduce节点读取分配到该节点的第二键值对，依据第二键值对中标识其所属的第一集合的标识将第二键值对归为不同的队列，并对队列中的第二键值对进行连接操作。

具体地，对属于集合R_den的连接元素对应的第二键值对组成的队列和属于集合S_Rden的连接元素对应的键值对组合的队列进行连接操作；对属于集合R_Sden的连接元素对应的第二键值对组成的队列和属于集合S_den的连接元素对应的键值对组成的队列进行连接操作；对属于集合R_thin的连接元素对应的第二键值对组成的队列和属于集合S_thin的连接元素对应的键值对组成的队列进行连接操作。当然，连接操作的条件为key相同，并且key.tagS不同，即交集为空的集合之间无需做连接操作。

示例性的，依据第二键值对中的value：tagF将第二键值对放入6个队列，tagF不同的，放入不同的队列，并记这6个队列为QR_den、QR_Sden、QR_thin、QS_den、QS_Rden以及QS_thin。而后，根据集合的交集运算，将队列QR_den和QS_Rden、QR_Sden和QS_den、QR_thin和QS_thin进行连接操作。

因此，本发明实施例还可通过识别key的出现频度，按需地分配第二Reduce节点，缓解了取值分布不均带来的负载均衡问题。

在本申请所提供的几个实施例中，应该理解到，所揭露的终端和方法，可以通过其它的方式实现。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理包括，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用硬件加软件功能单元的形式实现。

上述以软件功能单元的形式实现的集成的单元，可以存储在一个计算机可读取存储介质中。上述软件功能单元存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(Read-OnlyMemory，简称ROM)、随机存取存储器(RandomAccessMemory，简称RAM)、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

Claims (11)

1.一种数据连接优化方法，其特征在于，包括：

m₁个第一Map节点分别统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果，并将所述统计结果发送至所述中心节点，使得所述中心节点将所述统计结果发送至n₁个第一Reduce节点，其中同一连接元素的统计结果发送至同一第一Reduce节点；

所述n₁个第一Reduce节点分别根据所述统计结果获取各自的Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数，根据所述记录总数与预设的阈值确定所述连接元素所属的第一集合，并将所述第一集合发送至所述中心节点，所述第一集合用于表征所述连接元素的频繁取值情况；

所述中心节点对所述第一集合中的连接元素重新排序，得到相应的第二集合，并对所述第二集合中的连接元素执行向量插入操作，获取所述第二集合对应的查询向量；

所述中心节点重新将所述数据库分配给m₂个第二Map节点，并将所述第一集合和所述查询向量发送给所述m₂个第二Map节点；

所述m₂个第二Map节点分别根据分配的第二数据块中的记录和所述查询向量确定所述记录中的连接元素所属的第一集合，并根据所述第一集合之间针对所述连接元素的交集运算确定是否对所述连接元素进行连接操作。

2.根据权利要求1所述的数据连接优化方法，其特征在于，所述m₁个第一Map节点分别统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果包括：

所述m₁个第一Map节点分别调用map函数从所述第一数据块中抽取出每一条包括所述连接元素的记录，并输出第一键值对，所述第一键值对包括所述连接元素、表征所述连接元素的数据来源的标识和计数，所述计数为1；

针对所述第一数据块中同一连接元素，将所述表征所述连接元素的数据来源的标识相同的所述第一键值对中的计数累加，得到所述第一数据块中相同数据来源的同一连接元素对应的记录的数量。

3.根据权利要求1或2所述的数据连接优化方法，其特征在于，若所述数据库包括第一数据库和第二数据库，则所述根据所述记录总数与预设的阈值确定所述连接元素所属的第一集合包括：

当所述第一Reduce节点中所述连接元素来源于所述第一数据库的第一记录总数小于所述阈值，且来源于所述第二数据库的第二记录总数小于所述阈值时，若所述第一记录总数不等于零，则确定所述连接元素所属的第一集合为集合R_thin，若所述第二记录总数不为零，则确定所述连接元素所属的第一集合为集合S_thin，所述集合R_thin和所述集合S_thin均包括所述第一数据库和所述第二数据库中稀疏出现的连接元素；

若所述第一记录总数大于或等于所述阈值，且所述第一记录总数大于或等于所述第二记录总数，则确定所述连接元素所属的第一集合为集合R_den，所述集合R_den包括在所述第一数据库中高频出现，并且出现次数大于所述第二数据库中的出现次数的连接元素；若且所述第二记录总数不为零，则确定所述连接元素所属的第一集合为集合S_Rden，所述集合S_Rden包括在所述第二数据库中有出现，但属于所述集合R_den的连接元素；

若所述第二记录总数大于或等于所述阈值，且所述第二记录总数大于或等于所述第一记录总数，则确定所述连接元素所属的第一集合为集合S_den，所述集合S_den包括在所述第二数据库中高频出现，并且出现次数大于所述第一数据库中的出现次数的连接元素；若且所述第一记录总数不为零，则确定所述连接元素所属的第一集合为集合R_Sden，所述集合R_Sden包括在所述第一数据库中有出现，但属于所述集合S_den的连接元素。

4.根据权利要求3所述的数据连接优化方法，其特征在于，所述中心节点对所述第一集合中的连接元素重新排序，得到相应的第二集合，并对所述第二集合中的连接元素执行向量插入操作，获取所述第二集合对应的查询向量包括：

所述中心节点对所述第一集合为所述集合R_den、所述集合R_Sden、所述集合S_den和所述集合S_Rden中的连接元素，按照所述连接元素值的大小重新排序，得到相应的第二集合，并记录所述连接元素在所述第二集合中的位置；

针对所述集合R_den、所述集合S_Rden、所述集合S_den和所述集合S_Rden相应的第二集合，根据预定义的初始向量对所述第二集合中的每个连接元素执行所述向量插入操作，获取所述第二集合对应的查询向量。

5.根据权利要求4所述的数据连接优化方法，其特征在于，在根据分配的第二数据块中的记录和所述查询向量确定所述记录中的连接元素所属的第一集合后，所述方法还包括：

所述m₂个第二Map节点分别生成所述连接元素对应的第二键值对，所述第二键值对包括所述连接元素、表征所述连接元素数据来源的标识、所述连接元素所属的第一集合的标识以及所述连接元素对应的非连接元素。

6.根据权利要求5所述的数据连接优化方法，其特征在于，所述根据所述第一集合之间针对所述连接元素的交集运算确定是否对所述连接元素进行连接操作包括：

在确定所述记录中的连接元素所属的第一集合后，若根据所述查询向量确定所述连接元素不在与所述第一集合交集不为空的另一第一集合中，则确定不对所述连接元素进行连接操作。

7.根据权利要求6所述的数据连接优化方法，其特征在于，所述方法还包括：

所述m₂个第二Map节点分别根据所述第二键值对所属的第一集合确定所述第二键值对相应的第二Reduce节点的范围，并将所述第二键值对发送至所述范围内的n₂个第二Reduce节点；

所述n₂个第二Reduce节点分别根据所述第二键值对所属的第一集合将所述第二键值对归为不同的队列，并对所述队列中的第二键值对进行连接操作。

8.根据权利要求7所述的数据连接优化方法，其特征在于，所述m₂个第二Map节点分别根据所述第二键值对所属的第一集合确定所述第二键值对相应的第二Reduce节点的范围，并将所述第二键值对发送至所述范围内的n₂个第二Reduce节点包括：

若所述连接元素属于所述集合S_thin或所述集合R_thin，则所述第二Map节点将相同的所述连接元素对应的第二键值对发送至同一第二Reduce节点；

若所述连接元素属于所述集合R_den，则所述第二Map节点将所述连接元素对应的第二键值对随机发送至编号位于第一范围内的任一第二Reduce节点，所述第一范围为起始Reduce编号，至所述起始Reduce编号与所述第一数据库中所述连接元素的记录总数与每个Reduce节点平均处理的记录数的比值的和之间的编号；

若所述连接元素属于所述集合S_den，则所述第二Map节点将所述连接元素对应的第二键值对随机发送至编号位于第二范围内的任一第二Reduce节点，所述第二范围为起始Reduce编号，至所述起始Reduce编号与所述第二数据库中所述连接元素的记录总数与每个Reduce节点平均处理的记录数的比值的和之间的编号；

若所述连接元素属于所述集合R_Sden，则所述第二Map节点将所述连接元素对应的第二键值对广播给编号位于第三范围内的所有第二Reduce节点，所述第三范围为起始Reduce节点编号，至所述起始Reduce编号与所述第二数据库中所述连接元素的记录总数与每个Reduce节点平均处理的记录数的比值的和之间的编号；

若所述连接元素属于所述集合S_Rden，则所述第二Map节点将所述连接元素对应的第二键值对广播给编号位于第四范围内的所有第二Reduce节点，所述第四范围为起始而第二Reduce编号，至所述起始第二Reduce编号与所述第一数据库中所述连接元素的记录总数与每个第二Reduce节点平均处理的记录数的比值的和之间的编号。

9.根据权利要求8所述的数据连接优化方法，其特征在于，所述每个第二Reduce节点平均处理的记录数为：所述第一数据库的文件大小与所述第一数据库中单条记录大小的比值，加上所述第二数据库的文件大小与所述第二数据库中的单条记录大小的比值的和，与所述第二Reduce节点的数量的比值。

10.根据权利要求8或9所述的数据连接优化方法，其特征在于，所述根据所述第二键值对所属的第一集合将所述第二键值对归为不同的队列，并对所述队列中的第二键值对进行连接操作包括：

对属于所述集合R_den的连接元素对应的第二键值对组成的队列和属于所述集合S_Rden的连接元素对应的键值对组合的队列进行连接操作；

对属于所述集合R_Sden的连接元素对应的第二键值对组成的队列和属于所述集合S_den的连接元素对应的键值对组成的队列进行连接操作；

对属于所述集合R_thin的连接元素对应的第二键值对组成的队列和属于所述集合S_thin的连接元素对应的键值对组成的队列进行连接操作。

11.一种数据运算系统，其特征在于，包括m₁个Map节点、n₁个第一Reduce节点、中心节点、m₂个第二Map节点，其中：

所述m₁个Map节点，分别用于统计中心节点对数据库分配的第一数据块中来源于同一数据库的同一连接元素对应的记录，以获取统计结果，并将所述统计结果发送至所述中心节点，使得所述中心节点将所述统计结果发送至n₁个第一Reduce节点，其中同一连接元素的统计结果发送至同一第一Reduce节点；

所述n₁个第一Reduce节点，分别用于根据所述统计结果获取各自的Reduce节点中来源于同一数据库的连接元素对应的记录的记录总数，根据所述记录总数与预设的阈值确定所述连接元素所属的第一集合，并将所述第一集合发送至所述中心节点，所述第一集合用于表征所述连接元素的频繁取值情况；

所述中心节点，用于对所述第一集合中的连接元素重新排序，得到相应的第二集合，并对所述第二集合中的连接元素执行向量插入操作，获取所述第二集合对应的查询向量；

所述中心节点，还用于重新将所述数据库分配给m₂个第二Map节点，并将所述第一集合和所述查询向量发送给所述m₂个第二Map节点；

所述m₂个第二Map节点，分别用于根据分配的第二数据块中的记录和所述查询向量确定所述记录中的连接元素所属的第一集合，并根据所述第一集合之间针对所述连接元素的交集运算确定是否对所述连接元素进行连接操作。