随着信息技术的快速发展和数据爆炸式的增长, 传统数据库性能已经远远满足不了大数据时代对系统高性能的需求[1]。传统的并行数据库由于容错性和结点规模的限制, 已经不能满足日益增长的海量数据查询需求[2], 具有高扩展性、容错性和易用性的Map Reduce架构被提出[3]。但是Map Reduce架构在关系型数据查询性能上较并行数据库存在劣势[4], 主要原因是Map Reduce架构没有充分利用关系型数据模式, 导致网络开销大。本文提出的混合Map Reduce环境下基于数据划分的查询优化, 是通过结合并行数据库的查询优化技术和Map Reduee架构出色的容错性和扩展性来提升系统查询性能。
数据划分是混合Map Reduce环境下查询性能提升的关键。数据划分指在网络结点中数据存储的方式, 划分方法采用数据全复制、数据独立水平划分和数据协同水平划分等。一些关系查询操作, 如连接操作和聚集操作, 需要数据在结点之间进行重划分操作, 而重划分涉及到大量数据移动, 其网络开销和I/O开销非常巨大[5]。混合架构较Map Reduce架构的性能优势是将开销较大的关系查询操作下划到本地数据库中进行。对于连接操作, 若查询所涉及到的表采用协同水平划分, 则操作同样可以下划到本地数据库中进行。
传统的数据划分技术通常针对简单数据模型, 并且依赖人工分析, 对复杂的数据模型很难确定如何得到最优划分, 因此亟需自动化的数据划分方案。在分布式数据库领域, 文献[6]提出为数据划分提供建议工具, 即划分建议器 (partition recommender) 。但是针对混合Map Reduce架构还没有数据划分建议器的研究。
划分建议器是针对预期查询任务流对数据的划分提出建议, 将系统的总开销最小化。划分建议器需要满足下列需求, 以期达到查询优化的目标:
1) 针对预期任务量给出最佳分区方案, 即对于一定的查询负载, 查询的总代价最小, 体现在所需的总的查询时间最小化。
2) 给出的划分建议是对表是否进行结点全复制, 或表根据属性列划分提出建议方案, 将相似查询负载的代价最小化。
3) 将划分建议器集成到并行查询优化器底层, 使系统依据数据划分建议和数据的具体划分决定查询优化方案。
混合Map Reduce架构上的划分建议器[7], 实现了Map Reduce和数据库混合架构上数据划分方案的智能化求解, 提升了系统查询效率。
划分建议器作为混合架构系统插件, 以数据集和查询负载的统计信息为输入, 为混合架构系统提供最佳划分方案, 混合架构系统依据具体情况, 按照最佳划分方案进行Join优化, 提高了查询效率。
划分建议器与混合架构系统整合后的处理流程, 如下图所示。图中, 1) 为用户的查询输人流, 即具体的查询负载;2) 代表混合架构系统传递给划分建议器的系统信息, 包括系统网络传输速率、数据库扫描速度、Map Reduce网络开销和系统查询计划等, 划分建议器根据这些信息修改代价评估函数的参数, 根据代价评估函数来搜索划分方案空间;3) 表示划分建议器向混合架构提出最佳划分方案, 查询优化器根据划分建议决定优化策略;4) 代表优化器按照划分建议生成最佳查询计划, 返回用户查询结果。
划分建议器包含三个关键组成部分:
1) 生成包含所有划分方案的搜索空间。
2) 高效的空间搜索算法。
3) 划分代价评估函数。
针对元信息管理模块和查询优化器模块增加数据划分配置文件, 记录每张表的划分情况, 在Hy DB的查询优化器上增加表划分约束, 按照表划分情况决定具体的查询执行计划。划分建议器得到最佳划分方案后, 需把最佳划分方案用于系统的实际数据划分中, 使混合架构根据具体划分策略进行查询优化, 保持查询方案与划分建议一致。
划分方案空间为指定数据集所有的划分方案集合。对于复杂的数据集, 采用多叉树的方法来枚举所有划分方案, 得到划分方案空间。每一个非叶结点对应一张关系表的一种划分方式, 叶结点对应最终划分方案。如图2所示用多叉树的方法来描述一个划分方案空间。
图2所示是一棵划分方案树。从根结点到叶结点的路径就是一个完整的数据划分方案。在遍历树的过程中, 计算每个结点的代价, 从中选取代价最小的结点。当整棵多叉树遍历完成, 从根结点到代价最小的叶子结点的完整路径即为最优划分方案。
划分建议器采用基于优先级的划分方案空问生成策略, 根据查询负载中对表关键列的请求次数建立优先级, 涉及到查询越多的关键列的优先级越高。在生成划分方案空间时, 按照关键列的优先级决定其在兄弟结点中的排名, 优先级越高, 其位置越靠前。划分建议器深度优先搜索解决方案时, 先搜到的叶结点就是最佳划分方案。
算法采用分支限界法来减少所搜索的空间大小。深度优先搜索生成树并计算cost代价, 当生成第一个最终cost结点时, 将该代价存放在intercost中。然后搜索其他子树, 若计算的cost大于该intercost, 则剪除该子树。若到达叶结点后costd小于intercost, 则更新intercost。算法中增加了过滤条件, 减少了搜索空间。
实验对遍历搜索 (traverse) 、带剪枝的搜索算法 (pruning) 和基于优先级的生成树上的剪枝搜索 (priorityand pruning) 三种搜索算法进行对比。
遍历搜索 (traverse) 为了得到最佳划分方案, 每次都将全部节点搜索一遍, 遍历搜索的比例为1, 运行时间与搜索空间的大小有关, 遍历搜索时间最长, 剪枝算法 (pruning) 为节省开支, 剪去了一定的分支节点, 故剪枝算法搜索比例和算法时间都要优于遍历搜索。基于优先级的剪枝搜索算法 (priorityand pruning) 在生成树的过程中对划分可能进行了优化, 多叉树中靠左边的结点效率通常好于右边的结点, 其搜索的结点数目随数据增长变化不大, 实际搜索空间比例反而变低, 运行时间较前两种算法要短很多。通过空间搜索算法实验, 验证了本文基于优先级的剪枝算法的搜索效率优于其他两种算法, 在时间和空间上节省了开销。
本文提出并实现了混合架构上划分建议器模型。根据混合架构的特点, 对不同划分方案进行代价评估, 选择查询负载下总体时间代价最小的划分方案, 减少了系统查询开销。依据划分建议器模型, 提出了划分方案搜索算法, 采用剪枝和基于优先级的生成树策略等优化技术, 大大提高了算法的搜索效率。另外, 对数据划分后如何使各个结点负载均衡, 对数据集提出索引建议等, 都是未来研究的方向。
摘要：本文对大规模网络存储环境涉及的查询及优化等关键技术进行深入研究, 提出了基于代价优先的生成策略和空间搜索算法, 减少了划分建议器生成最优方案的时间。通过实验验证了划分建议器的有效性, 使系统的整体查询代价最小, 显著提高了系统性能。
关键词：查询策略,查询优化,划分建议器
[1] Dean J, Ghemawat S.Map Reduce:simplied data processingon large clusters[J].Communications ofthe ACM, 2008, 51.
[2] Stonebraker M, Abadi D, De Witt D J, et a1.Map Reduce andparallel DBMSs:friends or foes?[J].Communications ofthe ACM, 2010
[3] 孙广中, 肖锋, 熊曦.Map Roduce模型的调度及袢错机制研究[J].微电子学与汁算机, 2007.
[4] 周敏.Map Reduce综述:硕士学位论文.广州:暨南大学2008.
[5] Dean J, Ghemawat S.Map Reduce:a flexible data processingtool[J].Communications ofthe ACM, 2010.
[6] 覃左言, 朱青, 李伏.Hy DB:结合Map Reduce和并行数据库的混合Saa S架构[J].小型微型计算机系统, 2012, 3 (3) :5l2.518.
[7] 董西成.Hadoop技术内幕:深入解析Map Reduce架构设计与实现原理[J].机械工业出版社, 2013.
推荐阅读：
大数据环境论文06-09
大数据背景下的大学英语写作教学改革探索05-29
行业大数据建设方案05-28
大数据时代背景下05-30
大数据时代的口号06-08
大数据社会治理创新06-15
政务服务大数据功能06-30
大数据分析实验室方案06-01
大数据在旅游业的应用06-30
数据结构和算法06-10
