云数据管理系统中查询技术研究综述

　　摘要：作为一种全新的互联网应用模式，云计算在工业界和学术界备受关注.人们可以通过终端设备便捷地获取云端服务，并以按需使用的方式获得存储资源、计算资源以及软硬件资源.云计算的发展带来了一系列挑战性问题，而云数据的管理问题首当其冲.文中结合云数据的特点提出了一个云数据管理系统的框架，并在此基础上从索引管理、查询处理、查询优化以及在线聚集等几个方面对云数据管理系统中查询技术的研究工作进行了总结分析，指明了该领域面临的挑战和未来的研究工作.

　　关键词：云计算；云数据管理；查询处理；查询优化；索引管理；在线聚集

　　Abstract：As a revolutionary application mode in the internet，cloud computing has attracted more and more attentions from both industry and academia. Users can obtain cloud service conveniently through terminals，and access resources of storage, computing and hardware in the Pa>-As-You-Go model. The development of cloud computing brings about a series of challenging problems，data management in the cloud is of great importance. In this paper，we propose a framework of cloud data management system. Based on this framework，the key research works of query techniques in tloud data management system are classified and surveyed from several aspects: index management， query processing，query optimization and online aggregation. At last，the suggestions for future research are put forward.

　　Keywords：cloud computing; cloud data management; query processing; query optimization;index management； online aggregation 

　　引言

　　云计算是当今信息产业备受关注的一种全新领先的计算模式.在云计算模式下，企业和个人可以根据自己的需要购买存储设备和计算能力，而不用花费大量资金购买大规模高性能计算机，这使得用户

　　在软硬件维护以及升级上的成本投入大大减少.作为一项有望大幅降低成本的新兴技术，云计算受到了众多信息业巨头的关注：Amazon、Google、IBM、微软等公司都对云计算的研发进行了大规模的投入.与此同时，云计算的发展也产生了一系列新的挑战性问题，云数据管理是亟待解决的问题之一.

　　随着信息产业的发展，企业和各种组织产生的数据量快速增长.据IDC(互联网数据中心）统计，2011年全球产生的数据量达到1.8ZB，比2010年增长了1ZB①如何对这些海量数据进行有效管理和分析以获取数据背后潜在的巨大价值，是目前互联网、通信和生物医学等诸多领域面临的问题.传统数据管理系统中的很多技术对于如此大规模的数据管理往往不再有效，而且相关软硬件以及维护的昂贵成本也是让大部分企业望洋兴叹.云环境是由大量性能普通、价格便宜的计算节点组成的一种无共享大规模并行处理环境[1]，所以从成本和性能两方面考虑，越来越多的组织更愿意把数据中心从昂贵的高性能计算集群转移到公有云或私有云环境中.

　　另一方面，随着Web2.0和普适计算应用的流行，其"瘦客户端+服务"的运行模式对服务器端的计算能力和数据处理能力要求越来越高.在这种模式下，用户通过浏览器就可获得各种各样的服务，所有的计算都交由服务器端执行.为支持这些应用，服务系统需要存储、索引和备份海量的异构万维网页面、用户访问日志以及用户信息，并且还要保证对这些数据进行快速准确的访问[2].同时，服务系统所要处理的数据不仅包括产品和客户信息等结构化数据，还包含大量半结构和非结构化数据.在上述应用需求的推动下，云数据管理系统应运而生.

　　目前，随着Google、Yahoo!、Facebook等企业的推动，出现了不少基于云计算平台的数据管理系统，而且大部分系统已经投入生产环境使用[-4].与传统数据库系统相比，目前云数据管理系统提供的接口有很多限制，只提供简单的数据存取接口或者极小化的查询语言，这增加了用户使用的难度，也增加了开发人员的负担.同时，相比于传统的分布式关系数据库，云数据管理系统的查询性能也有很大的提升空间[5-6].如何在现有云计算平台的基础上，完善云数据管理系统的查询功能并提高其数据处理的性能，是目前备受关注的挑战性问题.

　　本文第2节对云数据查询技术进行概述；第3节提出云数据管理系统的基本框架并依据该框架对云数据查询的关键性技术进行总结分析；第4和第5节对未来工作进行展望并对全文工作进行总结.

　　2云数据查询处理概述

　　与传统关系数据库中的数据查询相比，云数据管理系统中的查询处理特点鲜明.本节阐述云数据管理系统的应用场景，结合已有的云数据管理系统和相关研究工作，对云环境中数据的特性进行了分析，指出云数据查询处理技术的目标，并总结云数据管理系统中查询技术的特征与面临的挑战.

　　2.1云数据管理系统的应用场景

　　与传统的关系数据库相比，云数据管理系统具有良好的扩展性和容错性，利用云计算平台中大规模计算资源和存储资源管理海量异构数据，为用户提供高性价比的数据管理方式.目前云数据管理系统在实际生产环境中得到了广泛的应用，主要集中在两个方面:海量数据分析和大规模Web数据管理.

　　数据分析主要用于生成报表、数据挖掘和决策支持等.与事务型数据处理不同，在分析型的数据处理中，数据是一次写多次读的，更新操作较少.数据分析可以在并行数据库上完成，但是随着数据规模的扩大以及对性能要求的提高，并行数据库系统的维护需耗费大量的资金及人力.云数据管理系统在扩展性和性价比上均占有天然的优势，其中类BigTable系统[7](BigTable、HBase②、Hypertable?)、HadoopDB[8]和Hive[9]等支持MapReduce框架的系统是面向数据分析型应用的.

　　随着Web2.0技术的发展，超大规模和高并发的社交网站逐渐兴起，参与人数迅速攀升.以微博网站Twiter为例，2010年2月用户每日发送的微博数量是5千万，而到了2011年3月用户每日发送的微博数量达到1亿4千万④，用户和网站交互产生大量动态信息.这种海量Web数据管理应用要求数据库能够满足高并发的数据读写和高效实时的数据访问，同时要求数据库具备可扩展性以应付数据的不断快速增长.关系数据库在这些需求面前显得力不从心，云数据管理系统则以灵活的扩展性和高性能的数据读写受到Web2.0网站的青睐，其中Cassandra?、CouchDB⑥和PNUTS[4]等系统广泛应用在Face-book、Twitter和Yahoo!等大型网站中.

　　2.2云数据的特点

　　云计算将大量用网络连接的计算资源进行统一管理和调度，以服务的方式为用户提供计算资源、存储资源和软硬件资源，其最鲜明的特点是可扩展性、高可用性和按需服务性.云计算环境中存储和管理的数据具备如下特点[1，8，10-11]：

　　(1)海量性.随着移动设备的普及、传感器技术的发展以及社交网络的扩大，云计算平台存储和管理的数据量十分庞大，了B级别和PB级别的数据规模十分常见.

　　(2)种类多样性.随着Web2.0的兴起，互联网应用不断推陈出新.一些新兴应用领域（微博、社交网络等）所处理的数据除了传统数据库里的结构化数据，还包括半结构化数据和非结构化数据，使得云计算平台中的数据种类纷繁多样.

　　(3)异地备份.数据的高可用性是云计算的重要特征之一，而这种面临软硬件错误的高水平容错性是通过对用户透明的数据异地备份实现的.

　　云数据的特征导致了传统的关系数据库无法满足其多样化的应用需求.云数据管理系统必须提供灵活的数据模型以有效管理多样化的数据，并针对数据分布和冗余的特性设计相应的存储方式和查询优化策略，从而向用户提供"按需所取"、可靠的、高性能的数据存取与查询服务.

　　2.3云数据查询处理的目标

　　为了提供高效可靠的云数据管理服务，云数据的查询处理技术需要达到以下目标

　　(1)可扩展性.云平台的规模大小不一，小的私有云平台规模为十几个节点，大的公有云平台规模可达到几千个节点①[15].此外，云计算提供的是一种"按需计费"的服务方式，随着应用需求的变化，云平台的规模也会发生变化.这就要求云数据管理系统中的查询处理及优化算法具备良好的扩展性，不仅能够扩展到庞大规模的云平台上，而且能够实现资源的可动态增长及其带来的性能提升.

　　(2)可用性.云平台由大量廉价计算机构成，与高性能服务器构成的分布式系统相比，云平台的硬件出错率较高.云数据管理系统需要将软硬件错误看成系统运行的常态，错误发生时既要保证数据不丢失，又要保证数据的读写操作能够正常进行.

　　(3)在异构环境运行的能力.随着应用的发展以及数据量的不断增长，云平台势必要通过增加新的节点来提高计算和存储能力.因此，保证一个云平台中所有节点的硬件配置同构是非常困难的.即使

　　在一个硬件配置相同的环境中，不同节点的软硬件性能也会出现波动[16].云数据的查询技术要有在异构环境运行的能力，从而避免性能较差的节点影响整个系统的运行效率这种"木桶效应"的出现.

　　(4)丰富灵活的用户接口.一方面，云数据管理系统要提供SQL接口，这样习惯于关系数据库查询语言的用户不必重新学习新的接口或者编程方法，而原来基于关系数据库的各种应用也可以平滑的转移到云上；另一方面，云数据管理系统还要提供UDF(UserDefinedFunction)接口，用户可以根据业务需求自己定义数据查询操作.

　　(5)高效的数据存取性能.云数据管理系统的软硬件成本远远低于高性能分布式数据库，其处理海量数据的效率也是云计算用户关注的重要问题.云数据管理系统应当针对云数据的特点设计数据分布策略和查询优化相关算法，从而提高其管理海量数据的能力．

　　云数据管理系统可以通过云计算平台的资源虚拟以及MapRedUCe[15]框架的使用而得到良好的扩展性和可用性，也可以在并行任务调度过程中采取投机任务（speculativetask)[16]等措施保证其在异构环境中运行的能力.从支持的查询接口看，目前大部分云数据管理系统只提供了简单的数据存取接口或者极小化的查询语言，这限制了其对复杂数据查询和分析的支持.从查询性能来看，目前云数据管理系统的查询优化主要针对键值进行，而对非键值的查询主要是依靠批量的全表扫描.因此，用户接口和查询性能是目前云数据管理系统亟待提高的两个方面．

　　2.4云数据管理系统中查询处理的特征

　　传统关系数据库中的查询技术无法同时满足上节提到的目标，特别是可扩展性和可用性.现有的云数据管理系统的查询技术和传统关系数据库系统的查询技术在处理的数据类型、容错性和支持接口等方面表现出明显差异，表1从多个方面对二者进行了对比?

　　传统关系数据库的查询主要面向结构化数据，其数据模型基于关系模型.云数据管理系统处理的数据对象除了结构化数据，还包括半结构化和非结构化数据，其数据模型包括key-value模型、文档模型和简化的关系模型[3+9].之所以称其为简化的数据模型是因为它虽然以表的形式管理数据，但不提供实体完整性和参照完整性.除此以外，关系数据库的数据模型是一种模式优先（schema-fcst)的逻辑结构，即在数据入库之前设计好数据模式.而云数据管理系统中的数据模型是从数据到模式（from-data-to^schema)数据模式可以是松散的、滞后的，可以在数据入库时根据数据内容定义数据模式.

　　查询容错是指一个查询运行过程中出现了硬件错误，该查询不必重新开始.传统的关系数据库系统一般不保证查询容错.云数据管理系统把硬件错误看成一种常态，它同时保证数据容错和查询容错.因为云平台上硬件错误率较高，如果每次出现错误都需要重启查询，那么一个耗时较长的查询很可能无法完成.从服务方式来看，传统关系数据库是一种pay-before-yoirgo的方式，即通过需求分析设计数据库模式并构建数据库软硬件，并在较长时间内保持相对稳定，因此查询优化的目标是在已有的软硬件环境下获得最好的查询性能.而云数据管理系统是一种paya-yoirgo的方式，用户根据使用的计算资源和存储资源向服务提供商付费，因而查询优化的目标是如何利用更少的计算资源获得用户期望的查询性能.从查询接口和查询优化技术来看，关系数据库支持复杂的SQL语言，而且查询优化技术也非常成熟.相比之下，现有的云数据管理系统支持的查询语言比较匮乏，而且已有的查询优化技术主要集中在基于规则的优化，因此在这两个方面亟待加强.

　　3云数据管理系统中查询技术研究

　　作为一种新型数据管理技术，云数据管理系统的研究仍处于起步阶段.这种新兴的数据管理技术可以扩展到大量廉价节点上，为用户提供按需所取、高性价比的数据管理服务.本节首先提出云数据管理系统的整体框架，然后从数据存储与索引技术、查询处理及优化、在线聚集几个方面对云数据查询相关工作和研究成果进行分析总结.

　　3.1云数据管理系统基本框架

　　为了有效管理海量、种类多样的云数据，并提供"按需所取"的云服务，云数据管理系统必须具有可扩展性、可裁剪性、可用性以及在异构环境中运行的能力.这使得云数据管理系统在面临查询处理、查询优化和索引管理等问题时采用不同于传统数据库的全新解决方法.同时，一些在传统数据库中提出但是没有得到广泛应用的研究问题在云环境下显现出重要的意义，例如查询进程估计和在线聚集等.目前已有的数据管理系统大都面向某一类特定应用，因此系统架构和实现方式各有不同.我们结合云计算中数据管理应用的特点以及数据查询处理的目标，提出了云数据管理系统的整体架构，如图1所示，该架构被划分为5个部分.

　　(1)应用接口层.负责接收用户提交的请求并交给查询处理层相应的模块进行处理.提供查询语言接口、用户自定义接口UDF(key/value操作）、数据分析和在线聚集等应用.用户不仅可以通过查询接口和UDF接口进行数据操作，还可以通过可视化工具执行数据分析和在线聚集.

　　(2)查询处理层.对上层提交的查询语句进行解析和逻辑优化后转化成操作符树，进而生成MapReduce执行计划；如果上层提交的是用户自定义操作，则直接生成MapReduce执行计划.如何根据查询类型和数据分布等信息生成合适的查询计划，以及如何利用云数据的特点对查询计划进行逻辑优化是查询处理层的主要任务，也是云数据管理领域备受关注的研究问题.

　　()数据控制层.该层主要负责3个方面的工作：利用全局索引和元数据信息进行数据定位；备份数据的一致性处理和数据迁移；在线聚集过程中进行数据采样和进程估计.数据层涉及到查询执行和在线聚集的核心部分，目前的研究工作主要围绕查询处理优化、索引构建、数据采样和查询结果估计．

　　(4)数据存储层.负责数据的实际存储以及在各节点范围内数据的索引设计、缓冲区管理和曰志管理.存储层的节点可通过多种方式组织，例如主-从结构或者点对点结构等，主要通过不同的通信协议体现.无论采用哪种结构，数据都被分区到多个节点存储.如何在保证数据分布均衡的情况下提高每个节点上数据存取的效率是存储层必须解决的问题．

　　(5)服务管理模块.负责元数据的管理、操作管理和系统监控.元数据管理部分为查询处理层提供访问接口，同时保证元数据与数据模式之间的一致性.操作管理主要面向数据控制层，包括数据读写锁机制、容错机制以及负载均衡.系统监控模块从数据

　　存储层收集监控信息，并通过图形界面将其展示给用户.资源分配模块负责管理系统中的负载，节点能够被动态地添加或删除以适应工作负载的变化.

　　3.2云数据管理系统关键技术研究

　　依据云数据管理系统的整体框架，可以看出云数据的查询领域存在许多研究问题：数据存储与索引设计、基于MapReduce的查询处理、查询优化、在线聚集过程中的数据采样与置信区间计算等.目前索引管理、查询处理、查询优化以及在线聚集等问题已经得到了初步的研究，本节对目前已有的相关工作进行分析总结.

　　3.2.1索引技术

　　现有的云数据管理系统大都以key-value方式存储数据，能够提供基于键值的快速查询，但是对于非键值的查询只能通过全表扫描来完成.尽管可以通过MapReduce实现并发扫描，但是面对海量数据，对于选择度比较高的查询来说，全表扫描的效率仍然比较低.目前很多学者对云数据管理系统中的索引技术进行了研究.根据索引的实现方式，本文把已有的索引分成3类：双层索引[17-21、二级索引①②[22]和基于线性化技术的全局索引[23].

　　(1)双层索引

　　云数据管理系统中的双层索引框架由Wu等人[17]在2009年提出，后续双层索引方案的研究工作大都基于该框架，其结构如图2所示.索引由局部索引和全局索引两部分构成.为每个节点的数据建立局部索弓I，该索引只负责本地节点上的数据.除局部索引外，每个计算节点还要共享一部分存储空间来存储全局索引.全局索引依据局部索引构建，由于存储空间的限制和查询效率的要求，并不是所有的局部索引都发布到全局索引中，而是按照一定的规则对索引节点进行选择.

　　根据全局索引的组织方式，双层索引可以分成两类：P2P结构的双层索引和集中式结构的双层索引.如表2所示，前3种方案的全局索引均采用P2P结构的覆盖网络[17-19]，这种方式易于实现可扩展性，使系统能够同时支持大规模的查询.但是也存在一些不足：首先，维护P2P网络需要一定的代价，查询时往往需要较高的网络传输代价；其次，对于主从结构（masterslave)的云数据管理系统，实现这种索引要重新构建一个P2P网络，会增加原有系统的负担.基于上述原因，文献[20-21]在全局索引中采用了集中式的索引方式.EMINC[2°]在每个节点建立KD树作为局部索引，其中每个索引节点被看成一个多维度的立方体，全局索引利用R树对这些立方体进行索引.当索引维度比较高，或者索引数据量比较大时，R树各个节点之间的重叠部分较多，查询时会产生大量的误判（falsepositive)结果.为解决这一问题，文献[21]的全局索引采用带bloomfilter的R树.进行查询时，首先通过bloomfilter来验证，如果查询点不在其中，则不再进行R树查询.这样减少了误判的几率，从而提高查询效率.上述各种索引技术方案具有较好的扩展性，但总的来说实现过程比较复杂，索引更新维护的代价比较高.特别是对于数据更新比较频繁的应用，对系统性能的影响较大.

　　(2)二级索引

　　二级索引（secondaryindex)方案主要应用于key-value存储的云数据库管理系统中，如Bigtbale、HBase等.在这类系统中，针对非键值列的二级索引通过为索引列构建索引表实现.索引表中的键值由原数据表中键值和索引列的组合构成，实现索引列与原有键值的映射.查询过程中，首先根据查询条件在索引表找到相应键值的列表，然后根据这些键值到原数据表中定位所需数据.目前基于二级索引的实现方案主要有ITHBase①、IHBase②和CCIndex?.其中ITHBase和IHBase均是开源的实现方案，二者实现方式相似，都从HBase源码级别进行扩展，重新定义和实现了客户端和服务端的处理逻辑，具有强侵入性.与IHBase相比，ITHbase更关注数据一致性，其重要特性之一是事务性.

　　ITHBase和IHBase两种方案中的索引表仅存放索引列与原表的键值信息.在查询过程中，先通过查询索引表得到键值，再根据键值到原表查找数据.由于得到的键值大都是随机的，所以需要进行大量的随机查找才能得到最终的查询结果，效率较低.为了减少随机查询带来的开销，Z〇u等人提出了另外

　　一种二级索引方案：互补聚簇式索引（ComplementalClusteringIndex),简称CCIndex[22].CCIndex把数据的详细信息也存放在索引表中，查询时可以直接在索引表中通过顺序扫描找到相应的数据，从而大大减少查询时间.然而把详细信息存储在索引表中会造成存储空间的增加.为了尽可能地减少存储空间的开销，作者把HDFS文件块备份数设为1来保证存储空间不会增加太多，但同时数据的容错性又成了新的问题.为了解决这一问题，作者创建了聚簇检验表（clusteringchecktable),和索引表一起来实现错误发生后的快速恢复.同时，CCIndex还给出了一种查询优化机制以支持多维查询.该优化机制主要利用HBase中的一些元数据信息（region-tc-serverinformation)来估算子查询结果的大小，根据估算结果生成合适的查询计划，从而减少查询时间.

　　二级索引方案易于实现，维护代价较低，但也存在一些不足：当索引列较多时，存储开销比较大；索引更新代价比较高，会影响系统的吞吐量；索引对多维查询的支持效率较低.

　　(3)基于线性化技术的全局索引

　　上述两类索引方案均需维护特定的索引结构，当数据更新十分频繁时，索引更新维护的代价很高.在保证系统性能的前提下，为降低索引更新维护的代价，文献[23]提出了一种基于空间目标排序的索引方案.其基本思想是：按照一定的规则将覆盖整个研究区域的范围划分为大小相等的格子，并给每一个格子分配相应的编号，用这些编号为空间目标生成一组具有代表意义的数字.其思想是将々维空间的实体映射到一维空间，从而可以利用比较成熟的一维索引技术.常见的用一维数值对多维空间目标进行排序的方法有Z排序、HUber曲线、位置键等.这些技术的思路基本相同，利用一个线性序列来填充空间，构造一种空间填充曲线.文献[23]以HBase作为数据存储方案，用Z排序技术对数据进行排序，以Zialue作为每条记录的键值.单纯的Z排序方法在搜索过程中会带来一些不必要的搜索空间（falsepositivesearch),作者在此基础上利用KD树或四叉树对多维数据空间进行划分，根据最长公共前缀计算每个子空间的名称，并以此作为索引项对各个子空间的数据进行索引，从而提高搜索效率.但是，该方法在进行空间划分的过程中会产生数据一致性的问题.虽然目前有相应的解决方案[24]，但是实现起来仍比较复杂，并且带来额外的负担.而且当数据分布不均匀时，KD树和四叉树的深度会很大，影响查询效率.

　　3.2.2查询处理

　　从支持的查询接口和查询语言来看，早期的云数据管理系统，例如BigTTable、HBase和Cassandra仅支持一些基本的数据插入和获取接口31°].随后很多公司和研究机构在丰富查询语句上开展了工作并提出一些"类-SQL语言，，，例如Yahoo丨的PigLatin[25]，Facebook的HQL[9]，微软的SCOPE[26]和Dryad-LINQ[27]以及IBM的JAQL[28]等等.从查询处理算法来看，目前针对云数据的查询处理和优化主要集中在基于MapReduce框架的查询处理.MapReduce天然地支持分组聚集操作和选择操作，而连接操作的实现则比较复杂.在分布式环境下数据传输和数据倾斜等问题的出现使得在MapReduce上实现连接成为一个非常具有挑战性的问题，下面主要对云数据的连接查询工作进行深入的总结分析.已有的相关工作主要分为两类，一类是直接在MapReduce上实现连接[9,25,28-33]，一类是修改MapReduce框架使之更利于连接的实现3-35].下面我们分别介绍这两类工作.

　　(1)基于原始MapReduce的连接算法

　　这类算法通过设计Map函数、Reduce函数和数据流来完成连接，涉及到的连接方式包括两表等值连接[9,25,28-29]、两表0连接[3°]、多表等值连接[1-32]和两表集合相似性连接[3°]3种类型.如表3所示，我们首先对两表等值连接的算法进行分析比较.设参加连接的两个表分别为只和S，并且只为其中数据量较小的表.?

　　标准重分区算法[9'25'28_29].该算法类似于〇8皿3中的排序^合并算法，由一个MapReduce作业构成.Mapper读入两个表的数据文件，并根据查询条件对数据进行过滤.输出的键值对中，键值是连接的列值，数值部分包括记录值和标签两部分，标签用于标识该记录来自哪个表.在reduce的混洗（shuffle)过程中，具有相同连接值的记录被分区到同一个reducer上.针对每一个连接值，reducer根据标签把记录分成两个集合，然后计算两个集合元素的向量积从而完成连接.标准重分区算法在现有云数据管理系统比较常见，Pig、Hive和Jaql均实现了这种算法[8,5,8].该算法的一个潜在问题是针对某个连接键值计算向量积时，两个表的相关数据都要放入内存进行缓存.当连接键值基数比较少或者出现数据倾斜时，会导致某个连接键值对应的数据量较大，一方面可能会造成内存溢出，另一方面造成计算资源分布不均匀.

　　改进的重分区算法[29].为了解决标准重分区算法的内存缓存问题，该算法从两个方面进行了改进：首先，map阶段输出的键值由连接的列值和表名的标签值混合构成，标签值放到键值中可以保证在reduce阶段进行排序时，来自其中一个表的数据总是排在另一个表的前面.其次，在计算卡氏积时，内存中只缓存较小表的数据，而另一个大表的数据以数据流的方式读入内存.这样，算法对内存大小的要求大大降低.

　　广播算法['25'28%].该算法将两个表中较小的一个以广播的形式传输到另一个表数据所在的节点上，然后在每个节点上直接进行连接.算法由一个只有map函数而reduce函数为空的MapReduce作业完成.作业初始化阶段对小表只进行数据广播，然后在Map阶段直接对数据进行Hash连接.由于广播算法没有reduce操作，因此避免了混洗过程中的数据传输和排序.当进行连接的两个表数据量相差很大时，广播小表的数据传输代价将会大大小于混洗过程中的数据传输代价，从而提高连接效率.

　　半连接算法[29].半连接算法基于广播算法进行改进，旨在减少广播过程中的数据传输量.广播的表只中并不是所有的数据都会参与连接，因此在传输数据之前通过半连接操作去除部分数据.该算法由3个MapReduce作业构成.第1个作业主要扫描S表并生成其连接键值文件S.M^.第2个作业根据文件S.M中的键值过滤只中每个子表的数据，生成一系列的数据文件第3个作业依据过滤后的只表数据执行广播算法.尽管半连接算法减少了广播过程中的数据传输量，但增加了对表S和只的扫描.因此具体选择哪种算法要根据连接表的大小以及连接键值的分布情况决定.

　　分片半连接算法[29].该算法将半连接的粒度缩小到S的每个分片子表&'，它同样由3个MapReduce作业构成.第1个作业生成S的链接键值文件，与前一个算法不同的是这个作业只有map操作，针对每个子表没生成连接键值文件Sz.k第2个作业执行半连接，针对每个没，根据只的匹配记录文件和标记生成与子表没相对应的广播数据文件只s,.第3个作业只有map操作，每个mapper读入对应的数据文件并直接进行连接操作.与普通的半连接算法相比，分片半连接算法在广播过程中数据传输量较少，但是需要为每个子表Sz过滤一次只.

　　冗余重分区算法[30].该算法使用一个二维矩阵表示两表的笛卡尔积，通过将满足连接条件的元素设定为"真"表示各种不同连接类型的结果.所有的连接均由一个MapReduce作业完成，通过均衡每个reducer任务输入和输出的数据量来达到减少查询执行时间的目的.算法根据reducer任务的个数r将二维矩阵分成r个大小均衡的区域，每个reducer负责产生相应区域的连接结果，其输入的数据量则等于区域矩形的周长之半.与以往的连接算法不同，在冗余重分区算法中，一个记录可能被重定向到多个reducer任务的区域中.算法正是通过这种冗余重定向实现了非等值连接，并减轻了数据倾斜的影响，但增加了混洗过程中的数据传输量

　　除了两表等值连接，多表等值连接在数据分析和决策支持中的应用也非常广泛，星形连接和链式连接是主要的两种连接形式.文献[31]提出了一种基于"数据冗余传输"的算法.该算法只包含一个MapReduce作业，数据的冗余传输在map之后的混洗过程中进行，冗余传输的次数和方式则由"mapkey"决定.Map键值是多个连接属性的集合，其中每个连接属性对应着一个共享值（share)，表示该属性Hash后的桶数.Mapper输出的每个键值对可能传输到多个reducer，其个数由Map键值中没有被该表覆盖的连接属性共享值的乘积决定.在reduce阶段，直接对传输到本地的数据进行连接.这种算法比较适合星形连接或者表数不多的链式连接，随着链式连接的表数不断增多，传输代价也成倍增加.文献[32]提出了一种利用二部图进行连接的算法，该算法主要应用在链式连接上设参加链式连接表的个数为w,首先使用w个MapReduce作业为每个表生成一个二部图，然后执行2("-1)个作业根据二部图按照和链式连接相反的顺序减少每个表参与连接的记录数，最后利用浓密树提高连接的并行度，这样最少再执行W-1)个作业执行连接.该算法从最大程度上减少了连接过程中的数据传输量，但是需要的MapReduce作业个数较多.

　　与等值连接不同，集合相似性连接要求计算两个表（或者集合）中所有元素的相似度，因此减少数据传输的方法比等值连接复杂.文献[33]提出了一种使用MapReduce实现集合相似性连接的算法，利用"前缀过滤"[36]原则减少参加连接的候选数据对.该算法包括3个步骤：第1步计算用于前缀过滤的全局词项排序，包括两个MapReduce作业，分别用于统计和排序，第2步利用词项排序执行前缀过滤并生成连接结果的行键值对（row-IDpar)，第3步根据行键值对取得实际的连接结果，这两步各使用一个MapReduce作业.该算法通过前缀过滤减少了连接过程中的数据传输代价，但其应用范围比较固定，适用于字符串类型的相似连接.