随着现代企业和互联网应用中数据种类的迅速增多,各种各样的数据规模已经呈现出了指数级增长的趋势。在数据增长的同时,更多复杂的处理要求也在出现。在Web应用中,逐渐出现了对大规模数据进行查询和分析的任务。对于这种数据处理要求,不管是传统的集中式还是分布式技术都不能提出有效和高效的解决方案。因为对海量的数据进行复杂的处理要求超出了传统关系型数据库的能力范围之内。相反地,大规模集群被越来越多地应用于数据密集型计算中。这主要归于集群性能上的三个特点：(1)可伸缩性：集群可以按照不同应用的具体需求增加或减少执行任务的机器节点。(2)容错性：集群中数据一般会有3个备份。当原数据所在节点出现错误的时候,系统会终止当前节点上的所有操作,到一个有备份数据的节点上继续执行之前的操作。(3)高可用性：在程序访问的集群节点出现故障的时候,不中断任务的执行,从其他节点继续当前任务,保证使集群的高可用性。基于大规模集群的这些优点,我们在上面进行了数据连接(join)操作的研究工作。连接是数据库的经典操作之一,它极好地解决了从有共同属性的多表中提取信息的问题。因此连接算法一直在各种应用中发挥着极大的作用。本文主要有以下三方面的贡献：1.本文比较了Map、Reduce和Shuffle三个阶段在执行连接算子时的代价,并对性能瓶颈进行了分析。文中在大规模集群的环境下,基于Map/Reduce编程模型,实现了直观连接操作的过程。之后通过一系列的实验测试,比较Map、Shuffle和Reduce这三个步骤的处理代价,并从中找出直观连接算法实现的性能瓶颈在于Shuffle过程中大量的数据传输。2.本文提出了一种预散列(hash)处理技术来优化直观连接算法的性能。预处理的时候,把输入数据按照连接属性的散列值重新排列,具有相同散列值的元组存放在一起。经过预处理之后的数据在Shuffle的过程中会减少数据传输的次数,从而提高连接操作的性能。3.针对星型连接,本文提出了一种预散列索引分块技术来提高星型连接的执行效率。优化算法在对数据进行预散列的过程中生成索引,然后利用索引在星型连接操作中过滤掉一些不必要的数据,减少Shuffle阶段的传输数据量和Reduce阶段的计算量。从算法的代价模型与最后的实验数据可以看出,本文所提出的两种连接优化方法都能够在大规模集群上利用Map/Reduce编程模型有效地提高连接操作的执行效率。