中文摘要：

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

英文摘要：

The exponential growth of data has posed serious challenges to the data management and analysis. Join query is a common data analysis operation, and MapReduce is a programming model implemented for parallel processing on large-scale datascts. Therefore the research on MapReduce based join algorithms and its cost model has a certain academic significance and application value. This study believes that the I/O （including the network and the local I/O） cost is the main factor affecting the performance of MapReduee based join algorithm. Furthermore, as the I/O cost is determined by the feature of both datasets and join operation, the executed plan of multi-ways join could be optimized by evaluating the I/O cost of two-ways join. In the study, an I/O cost model of two-ways join is proposed and then formally defined as a simple extension to the existing MapReduce based join algorithms, resulting in six join algorithms and their I/O cost functions through write-box analysis. In addition, an selection algorithm to find the best executed plan of multi-ways join is presented. The correctness and accuracy of the I/O cost model are validated through a series of experiments. The experiment results suggest that the I/O cost can accurately reflect the algorithm performance.