MapReduce连接查询的I/O代价研究

被引：10

作者：

宋杰 ^{[1
]}

李甜甜 ^{[2
]}

朱志良 ^{[1
]}

鲍玉斌 ^{[2
]}

于戈 ^{[2
]}

机构：

[1] 东北大学软件学院

[2] 东北大学信息科学与工程学院

来源：

软件学报 | 2015年 / 26卷 / 06期

基金：

中国博士后科学基金; 高等学校博士学科点专项科研基金;

关键词：

连接查询; Map Reduce; I/O代价模型; 查询优化;

D O I：

10.13328/j.cnki.jos.004586

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

数据的指数级增长给数据管理和分析带来了严峻的挑战.连接查询是数据分析中一种常用运算,而Map Reduce是一种用于大规模数据集并行处理的编程模型,研究基于Map Reduce的连接查询代价评估和查询优化,有着学术意义和应用价值.Map Reduce连接查询算法的性能主要取决于I/O代价(包括本地和网络I/O),而I/O代价与数据集以及连接运算的特征参数相关,通过对二元连接的I/O代价评估可以优化多元连接执行计划.基于此,首先提出了二元连接查询的I/O代价模型;随后,对现有二元连接算法进行形式化定义和简单扩展,归纳出6种基于Map Reduce连接查询算法,并通过算法白盒分析定义它们的I/O代价函数;最后,提出一种多元连接最优执行计划的选择算法.通过实验表明I/O代价模型的正确性且能够准确地反映算法的性能优劣.

引用

页码：1438 / 1456

页数：19

共 30 条

[1]

The google file system. Ghemawat S,Gobioff H,Leung S T. Proc of the19th ACM Symp on Operating Systems Principles (SOSP) . 2003

[2]

MapReduce[J] . Jeffrey Dean,Sanjay Ghemawat. &nbspCommunications of the ACM . 2008 (1)

[3]

Hadoop distributed file system. http://hadoop.apache.org/docs/stable1/hdfs_design.html . 2014

[4]

Processing theta-joins using MapReduce. Okcan A,Riedewald M. Proceedingsof ACM SIGMOD2007International Conference on Management of Data(SIGMOD’’11) . 2011

[5]

A comparison of join algorithms for log processing in MapReduce. Blanas S,Patel J M,Ercegovac V,et al. Proc of the ACM SIGMOD Int Conf on Management of Data . 2010

[6]

The Art of Computer Programming. Knuth D E. . 1973

[7]

Hadoop Map Reduce. http://hadoop.apache.org/docs/stable1/mapred_tutorial.html . 2014

[8]

Apache hive. http://hive.apache.org/ . 2014

[9] 海量数据上的近似连接聚集操作 [J].