mapreduce连接查询的i/o代价研究

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