③数据组织优化.云数据管理系统中的数据被分布到多个节点进行管理，在进行查询特别是多表查询时，需要在各个节点间进行数据传输.如果较多的相关数据存储在一个节点上，那么网络传输代价就会减少，查询时间也会随之减少，因此数据的组织方式会对查询性能产生很大的影响[49].HadoopDB将数据从分布式文件系统导入到每个节点上的关系数据库系统中，这样可以在本地的关系数据库上分别执行连接[8].Hadoop++[5°]将数据组织优化模块植入Hadoop系统之上，主要关注两表连接时的查询优化.Had〇〇p++在数据导入时对输入数据建立"特洛伊"索引，并将具有相同连接键值的数据放入同一个数据分片中，这样在实现连接时不需要进行数据的网络传输.该方法没有修改Hadoop，而是在导入数据时进行数据的重新组织.C〇Had〇〇p[51]则是修改了Hadoop的数据组织方法，为每个文件增加了"Locator"属性来标识其位置，而所有具有相同"Locator"属性的文件的数据块将被组织到同一个数据节点集合中.
　　除了上述查询优化方法，目前还有部分工作对MapReduce的参数设置进行优化[52-53]，其中文献[2]通过分组的数目对reducer个数进行优化，而文献[53]则是通过估计MapReduce作业的执行时间提供对多个参数的基于代价的优化.总的来说，目前已有的优化工作主要集中在数据控制层和数据存储层，而且大部分是基于规则的优化，基于代价的优化工作还比较少，亟待相关研究成果.
　　3.2.4在线聚集
　　在线聚集（OnlineAggregation,OLA)在查询处理过程中根据采样数据估计查询结果，并返回真实结果所在的置信区间[54].在线聚集的最大优势是可在较短时间内计算出接近实际的查询结果，当置信度和置信区间达到用户要求时，查询即可提前停止.对于原本执行时间特别长而且对结果精确性要求不高的复杂查询，在线聚集可以大大缩短查询时间.在线聚集最初提出是在单表上进行聚集的相关操作[55-56]，后来该工作被扩展到多表连接基础上的聚集操作[57-59]以及并行环境中的连接聚集[6M1].在线聚集基于关系数据库提出，并在研究领域取得了丰富的成果，但是相关成果在关系数据库领域带来的市场价值却很有限，原因有两点：首先，OLA要求查询处理的数据以随机顺序出现，这与排序、索引等查询优化算法的原则相违背，因此在已有的关系数据库系统上实现OLA需要对其内核进行大规模改动；其次，OLA的最主要目标是缩短查询运行时间和节省软硬件资源，然而在一个非弹性的数据中心，这个目标的吸引力并不大.在云计算环境下，OLA技术又重新引起了人们的关注.一方面，云计算提供了一种pay-as^yoirgo的服务模式，节省计算资源直接意味着节省开销；另一方面，不同于传统的关系数据库，云数据管理系统内核轻量易于修改.目前在云计算上的OLA已经有一些初步的工作，主要是在MapReduce框架上实现大规模数据的查询估计.其相关技术包括MapReduce在线化、数据采样、查询结果估计和收敛程度计算，下面我们分别分析这些技术的已有工作．
　　(1)MapReduce在线化.传统的MapReduce数据流是一个批处理的过程，无论是map任务还是reduce任务，必须处理完所有数据后才产生输出结果，而且reduce任务也必须在所有的map任务完成后才开始执行.OLA要求数据流是一个在线处理的过程，处理完部分样本数据后就输出估计的查询结果，MapReduce的在线化处理[2-63]为云环境下的OLA提供了实现平台.文献[2]的MapReduce在线化主要面向"自增迭代"的算法，通过map定期传送数据给reduce实现作业内部的在线化，并通过集群"共享内存"实现作业之间的在线化.这种在线化方法结构简单，易于实现，但是其扩展性及容错性不及传统的MapReduce.Condie等人[3]基于操作器（operator)之间数据流水线实现了在线化的MapReduce系统HOP.HOP结合网络负载状况以及combme操作的压缩比等因素设计数据流控制机制，从而动态控制mapper与reducer之间的数据传输粒度.当一个查询由多个MapReduce作业构成时，生产作业根据任务执行进度定期调用reduce并生成快照文件（snapshot)，消费作业通过读取快照文件从而实现数据在作业之间的流水化.HOP保留了传统MapReduce的扩展性和容错性，比较适合作为在线聚集的实现平台
　　(2)数据采样.为了保证估计结果和置信区间的准确性和收敛速度，在线聚集要求采样数据具有随机性和无偏性[55-56].从关系数据表进行采样的方法主要有三类[56,64]:顺序扫描、索引扫描和索引采样.Wu等人[1]提出了从分布式数据表采样的方法，首先根据表在各节点上的分布情况计算每个节点应采样的数据量大小，然后在每个节点上进行索引采样.在云环境下，很多数据以块（block)为单位直接存储在分布式文件系统上，MapReduce处理数据也通常以块为单位，因此上述基于关系数据库的采样方法无法直接使用.目前很多MapReduce的在线聚集工作假设数据以随机顺序存储或者假设一个随机数据输入队列的存在[54'3，通过顺序扫描数据队列即可获得随机无偏的数据.然而当数据以聚集相关列的顺序存储时，简单的顺序扫描便无法获取随机数据，因此在云环境下如何从直接存储在分布式文件中的数据中进行随机采样仍然是亟待解决的问题.
　　(3)查询结果估计.查询估计方法应当具有无偏性和持续性[57].无偏性是指如果不断重复采样和估计的过程，估计值的数学期望应该等于实际查询结果.持续性是指随着采样和估计步数的不断增加，估计值应该逐渐接近实际查询结果.目前已有的查询结果估计算法可以分为两类，一类是通过样本和总体数据量的大小对样本的聚集结果进行扩展[61'64].假设查询语句为SELECT〇汐（())FROM了.设随机变量为|7"|X⑴，当元组^满足查询选择条件时，rr^rrsiow#⑴的取值为rrfrrdow(i〇,否则取值为0,则总体均值"即为聚集查询结果，总体方差为ff2.根据中心极限定理，当采样数据随机且无偏时，样本数据的均值^趋近一个均值为…方差为ff2/"的正态分布.设T"是总体表了的采样数据集合，那么总体查询结果可通过用T和T"的大小比例对全表数据的⑴之和进行扩展得到.这种方法实现简单，而且支持增量计算.但是需要预先得到总体表的数据量，而且查询结果的估计受数据分布和采样质量的影响较大.
　　为了解决上述问题，Pansare等人[54]提出了利用未知样本概率分布进行估计的方法，假设每个数据块在MapReduce中的调度时间和处理时间均与聚集结果相关，并针对每个数据块6/〇成构造随机变量乙=(^，f严，iProc).该方法利用贝叶斯公式，根据已处理完数据块的聚集值计算未处理样本数据聚集值的概率分布:P(0|X)=P(X|())(0)，其中，表示未处理样本的聚集值；X表示已经处理完样本的聚集值.总体的查询结果通过对P(0|X)积分进行估计.这种方法通过贝叶斯理论从一定程度上消除了采样数据不均衡所带来的问题，但是算法的假设较强，而且只能支持一个MapReduce作业的查询处理，不支持由多个MapReduce作业构成的多表聚集的结果估计.

---

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

---

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。