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

《基于mapreduce模式的多表联查算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于MapReduce模式的多表联查算法高泽，李常宝，杨淙钧，刘忠麟，艾中良（华北计算技术研究所，北京100191）摘要：多表关联查询是进行数据挖掘与分析的有效技术手段。随着大数据时代的到来，当前的数据分析技术在进行海量数据多表联查操作时存在明显的性能瓶颈，为此提出一种基于MapReduce计算模型的多表联查算法UGS用以提升多表关联查询效率。实验表明，在海量数据背景下，该算法的查询效率明显优于大数据领域的SparkSQL，Hive及关系型数据库的MySQL。.jyqkin以上，两表规模达到百万条时，运行2h仍未得到结果

2、。1.2分布式处理引擎的实现分布式并行计算实现方式主要基于大数据技术体系中的MapReduce模式展开，目前方法主要有Hive[4]，Spark[5]两种方式。1.2.1MapReduce编程模型概述MapReduce编程模型以（Key，Value）元组为基本单位展开数据处理，整个处理过程分为Map、Reduce两个阶段：Map阶段处理输入数据并将处理结果基于Key值通过哈希计算映射到Reduce处理节点；Reduce阶段处理本地数据并输出结果。由于相同Key值的哈希计算结果是确定的，因此，每个Reduce处理节点上完整

3、保存了该key值的所有数据，编程人员在只需在每个Reduce节点处理本地数据即可完成对全局数据的处理。1.2.2分布式处理引擎执行多表联查Hive提供SQL查询接口，通过对用户输入的查询任务进行语法树解析，将SQL查询转化成Hadoop的MapReduce任务集，基于MapReduce展开数据处理[6]，由于MapReduce存在中间数据磁盘读写瓶颈，从而在很大程度上限制了Hive的执行效率。Spark分析引擎针对Hadoop的MapReduce中间数据磁盘读写瓶颈基于内存计算展开优化，使得同样功能的任务在大部分情况下比

4、Hadoop执行效率更优，Spark在执行多表关联查询时采用优化的笛卡尔积关联算法，虽然性能较传统的笛卡尔积有所优化，但是复杂度依旧为笛卡尔积的O（C1C2），并且空间复杂度为O（C1C2）。Hive在进行数据关联查询时，单作业单机数据规模超过2000000×10000000时，执行时间在1min以上，存在较大的优化空间；Spark对Hive的执行过程进行了基于内存的执行效率优化，但关联计算过程存在内存占用不可控的问题，当单作业单机数据规模超过20000000×100000000时，会因内存溢出导致关联查询无法完成，数据

5、规模相对较小时也存在一定的运行效率优化空间。因此需要设计一种空间膨胀相对可控，并且时间复杂度更低的算法来提高海量数据多表关联效率，从而提升海量分析能力。2算法的设计与实现2.1算法思路本算法主要借助MapReduce计算模型展开，在Map阶段，对各表记录添加标记，并将各表数据采用相同的散列算法进行映射分发，使各表相同的Key值被集中到相同的处理节点上；在Reduce阶段，基于各表标记进行关联结果筛选，本地化获取关联查询结果集。算法介绍如下：算法名：UGS（UnionGroupandSegmentation）算法。输入参数

6、：参与关联查询的表路径及关联条件集，关联查询结果输出路径。输出数据：关联查询结果。执行步骤：在上述实例中，算法在集群上的执行过程如下：（1）在Map阶段通过数据格式变换，将参与关联查询的各表数据统一为相同格式。将联合查询条件中的Key单独抽取出来，其他数据存放在OtherRecord中，并添加标记以记录的TableID，Map阶段输出为（Key，TableID，OtherRecord）。（2）在Reduce阶段，输入Map阶段的输出结果，对Key值相同的记录进行关联筛选，如果某个Key存在于所有表中，那么是1条或多条（可

7、能存在1个Key在某一table下存在多行）有效的结果。并将结果按表格式处理后输出。算法首先需要遍历数据，对每条数据通过Key计算出Reduce标识，Reduce端完成数据收集后，在每个Re?duce内通过排序将Key相同的记录整合在一起然后进行检索条件的完备性判断。在这种计算模式下，假设有N张表参与联查，第i张表的数据量为Ci，共有M个Map和R个Reduce参与并发计算。2.2基于Spark的算法实现本文基于大数据分析引擎Spark展开算法实现，首先介绍Spark相关的几个概念和操作：SparkContext：Spa

8、rk程序的入口，可以在声明时定义各种系统参数，如集群主节点位置，单个任务使用的最大内存量，需要核心数等等。RDD（ResilientDistributedDatasets）：弹性分布式数据集，它是Spark系统提供的一种分布式内存抽象，可以支持基于工作集的应用，同时具有数据流模型自动容错，位置感知调度和可伸缩性的特点