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

来源：软件学报杂志2015年第6期北京时间：

作者：宋杰,李甜甜,朱志良,鲍玉斌,于戈

单位：宋杰，东北大学 软件学院, 辽宁 沈阳 11081911,李甜甜，东北大学 信息科学与工程学院, 辽宁 沈阳 11081902,朱志良，东北大学 软件学院, 辽宁 沈阳 11081903,鲍玉斌，东北大学 信息科学与工程学院, 辽宁 沈阳 11081904,于戈，东北大学 信息科学与工程学院, 辽宁 沈阳 11081905

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

关键词：连接查询;MapReduce;I/O代价模型;查询优化

基金资助：国家自然科学基金(61433008, 61202088, 61402090); 教育部高等学校博士学科点专项科研基金(20130042120006);中国博士后科学基金面上项目(2013M540232); 中央高校基本科研业务费重大科技创新项目(N120817001); 辽宁省博士启动基金(201403314)