您好, 访客   登录/注册

基于MapReduce模式的多表联查算法

来源:用户上传      作者:

  摘 要: 多表关联查询是进行数据挖掘与分析的有效技术手段。随着大数据时代的到来,当前的数据分析技术在进行海量数据多表联查操作时存在明显的性能瓶颈,为此提出一种基于MapReduce计算模型的多表联查算法UGS用以提升多表关联查询效率。实验表明,在海量数据背景下,该算法的查询效率明显优于大数据领域的SparkSQL,Hive及关系型数据库的MySQL。
  关键词: MapReduce; 多表联查; 关联空间剪枝; Spark
  中图分类号: TN911?34 文献标识码: A 文章编号: 1004?373X(2015)14?0081?04
  在当今的生产生活中,围绕着每个人每件事都会产生大量的数据,而这些数据往往是分布在不同的数据文件中,想对这些数据进行处理分析就必然要用到多表联合查询,联合查询在实际的生产生活中非常有必要。当前的多表联合查询主要通过两种方式实现:一种是基于传统数据库的表JOIN方式,这种方式存在数据规模瓶颈问题,无法支撑大规模数据关联;另一种是基于大数据技术的多源数据融合[1]方式,虽然能够解决关联查询在数据规模方面的瓶颈问题,但在运行效率方面存在较大的优化空间,目前难以满足交互式查询需求。因此,针对当前多表关联查询领域存在的问题,本文提出了一种基于MapReduce计算模型[2]的新型多表联查方法;实验表明,在解决多表关联数据规模瓶颈的基础上,较当前大数据领域的多表关联模式能够显著提升运行效率。
  1 相关工作介绍
  当前多表关联查询主要借助2种方式实现:关系型数据库方式和分布式并行计算方式。下面通过一个关联查询实例对2种实现方式进行复杂性分析。假设2张待联查的表table1和table2,其中table1的数据量为C1条,table2的数据量为C2条。要求输出table1.Key =table2.Key的条件下2张表的所有行,即:“SELECT * FROM table1 INNER JOIN table2 ON table1.Key=table2.Key”。
  1.1 关系型数据库的实现
  传统关系型数据库的多表关联查询采用基于关联条件的集合相乘思路实现[3],针对table1的每行数据,在table2中对其关键字(Key)进行查找,如果找到满足条件的数据,那么把它们组合成一条新数据存储到结果数据集中。此时数据库需要处理的条数为C1C2,也就是说时间复杂度为O(C1C2)。在此模式下,两表规模均为10万条数据时其响应时间已经达到5 min以上,两表规模达到百万条时,运行2 h仍未得到结果。
  1.2 分布式处理引擎的实现
  分布式并行计算实现方式主要基于大数据技术体系中的MapReduce模式展开,目前方法主要有Hive[4],Spark[5]两种方式。
  1.2.1 MapReduce编程模型概述
  MapReduce编程模型以(Key,Value)元组为基本单位展开数据处理,整个处理过程分为Map、Reduce两个阶段:Map阶段处理输入数据并将处理结果基于Key值通过哈希计算映射到Reduce处理节点;Reduce阶段处理本地数据并输出结果。由于相同Key值的哈希计算结果是确定的,因此,每个Reduce处理节点上完整保存了该key值的所有数据,编程人员在只需在每个Reduce节点处理本地数据即可完成对全局数据的处理。
  1.2.2 分布式处理引擎执行多表联查
  Hive提供SQL查询接口,通过对用户输入的查询任务进行语法树解析,将SQL查询转化成Hadoop的MapReduce任务集,基于MapReduce展开数据处理[6],由于MapReduce存在中间数据磁盘读写瓶颈,从而在很大程度上限制了Hive的执行效率。Spark分析引擎针对Hadoop的MapReduce中间数据磁盘读写瓶颈基于内存计算展开优化,使得同样功能的任务在大部分情况下比Hadoop执行效率更优,Spark在执行多表关联查询时采用优化的笛卡尔积关联算法,虽然性能较传统的笛卡尔积有所优化,但是复杂度依旧为笛卡尔积的O(C1C2),并且空间复杂度为O(C1C2)。Hive在进行数据关联查询时,单作业单机数据规模超过2 000 000×10 000 000时,执行时间在1 min以上,存在较大的优化空间;Spark对Hive的执行过程进行了基于内存的执行效率优化,但关联计算过程存在内存占用不可控的问题,当单作业单机数据规模超过20 000 000[×]100 000 000时,会因内存溢出导致关联查询无法完成,数据规模相对较小时也存在一定的运行效率优化空间。
  因此需要设计一种空间膨胀相对可控,并且时间复杂度更低的算法来提高海量数据多表关联效率,从而提升海量分析能力。
  2 算法的设计与实现
  2.1 算法思路
  本算法主要借助MapReduce计算模型展开,在Map阶段,对各表记录添加来源标记,并将各表数据采用相同的散列算法进行映射分发,使各表相同的Key值被集中到相同的处理节点上;在Reduce阶段,基于各表标记进行关联结果筛选,本地化获取关联查询结果集。算法介绍如下:
  算法名:UGS(Union Group and Segmentation)算法。
  输入参数:参与关联查询的表路径及关联条件集,关联查询结果输出路径。
  输出数据:关联查询结果。
  执行步骤:在上述实例中,算法在集群上的执行过程如下:
  (1) 在Map阶段通过数据格式变换,将参与关联查询的各表数据统一为相同格式。将联合查询条件中的Key单独抽取出来,其他数据存放在OtherRecord中,并添加标记以记录来源的TableID,Map阶段输出为 (Key,TableID,OtherRecord)。
转载注明来源:https://www.xzbu.com/8/view-11762928.htm