Journal of Frontiers of Computer Science and Technology ›› 2017, Vol. 11 ›› Issue (5): 752-767.DOI: 10.3778/j.issn.1673-9418.1604022

Previous Articles     Next Articles

Join Query Optimization Based on MapReduce under Skewed Data

ZHANG Jingwei1,2, SHANG Hongjia1, QIAN Junyan1, ZHOU Ping3, YANG Qing3+   

  1. 1. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
    2. Guangxi Cooperative Innovation Center of Cloud Computing and Big Data, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
    3. Guangxi Key Laboratory of Automatic Measurement Technology and Instrument, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
  • Online:2017-05-01 Published:2017-05-04

非均匀数据分布下的MapReduce连接查询算法优化

张敬伟1,2,尚宏佳1,钱俊彦1,周  萍3,杨  青3+   

  1. 1. 桂林电子科技大学 广西可信软件重点实验室,广西 桂林 541004
    2. 桂林电子科技大学 广西云计算与大数据协同创新中心,广西 桂林 541004
    3. 桂林电子科技大学 广西自动检测技术与仪器重点实验室,广西 桂林 541004

Abstract: MapReduce, a classic distributed computing environment, can improve the performance of join query on large-scale data, but when the join attributes do not follow a uniform distribution, the pure hash strategy in traditional MapReduce will lead to load imbalance over computing nodes, which will reduce the performance of overall task. Aiming at the data skew problem in the join query, this paper studies the join query optimization based on MapReduce computing framework. Firstly, this paper conducts experimental analysis for the improved repartitioning join query algorithm, studies the execution phases of join query based on traditional MapReduce computing framework, and finds the performance bottlenecks of join query on MapReduce computing framework when data do not follow a uniform distribution. Based on the above, this paper designs and implements an improved join query optimization algorithm, which is based on an execution strategy by integrating the combination segmentation method and equilibrium partitioning method. The experimental results show that the proposed optimization method provides a good solution for distributed join query on large-scale skewed datasets, and presents an excellent time performance and scalability.

Key words: join query, MapReduce, skewed data

摘要: MapReduce分布式计算框架有助于提升大规模数据连接查询的效率,但当连接属性分布不均匀时,其简单的散列策略容易导致计算节点间负载不均衡,影响作业的整体性能。针对连接查询操作中的数据倾斜问题,研究了MapReduce框架下大规模数据连接查询操作的优化算法。首先对经典的改进重分区连接查询算法进行实验分析,研究了传统MapReduce计算框架下连接查询操作的执行流程,找出了基于MapReduce计算框架的连接查询算法在数据分布不均匀时的性能瓶颈;进而提出了组合分割平衡分区优化策略,设计并实现了基于组合分割平衡分区优化策略的改进型连接查询算法。实验结果表明,提出的优化策略在大规模数据的连接查询处理上很好地解决了数据倾斜带来的性能影响,具有好的时间性能和可扩展性。

关键词: 连接查询, MapReduce, 数据倾斜