基于连接依赖信息的分布式连接查询优化算法

赵宇兰 柳欣

摘 要： 分析分布式数据库中站点依赖算法和片段复制算法的特性，提出基于连接依赖信息的多连接查询优化算法。该算法中，连接依赖信息用于逻辑判定基于多个站点的连接查询是否对站点依赖，以避免不必要的通信代价；片段复制用于重新分布站点数据，确保局部连接处理满足站点依赖；利用SQL应用的本地性和站点间多线程的高度并行性以缩减网络通信代价和局部计算代价。实验结果证明了该算法的有效性。

关键词： 分布式数据库； 站点依赖； 连接依赖； 片段复制

中图分类号： TN915.1?34； TP311.133.1 文献标识码： A 文章编号： 1004?373X（2016）05?0028?05

0 引 言

分布式环境下的连接查询优化是当今数据库理论研究的一个热点问题。由于分布式数据库中数据的冗余性和数据分布的复杂性，全局查询往往涉及多个站点上的关系或关系片段，此时不仅要考虑站点之间数据传输所产生的通信代价，还要兼顾基于站点的局部处理代价，这无疑增加了查询处理和优化技术的难度。为了有效地处理分布式连接操作，国内外文献提出了多种算法，通常分为半连接算法和直接连接算法。典型的半连接算法有SDD?1算法[1]、AHY算法[2]、双向半连接算法[3?4]等，这些算法通过半连接操作缩减站点间数据的传输量，但由于需要二次数据传输，当二次数据传输的总量不小于传输站点上某个关系或关系片段的数据量时，算法将失效。典型的直接连接算法有R*算法[5?6]、利用站点依赖信息（Placement Dependency，PD）的算法[7]等。R*算法直接处理连接操作，通过穷举所有可能的连接策略，将全局连接操作分解为每个站点上的局部连接操作，最后选择一个最优的连接策略作为执行策略，但穷举的计算方法耗时长，且要传输的关系或关系片段的数据量大时该算法的处理效率将不理想。PD算法弥补了R*算法的不足，该算法有效利用了局部查询的本地化特征，在一个设计精良的分布式数据库中可以实现全局连接查询的零数据传输处理。但如果全局连接操作引用的关系片段在不同站点中存在相关联的元组时，该算法将失效。

本文借鉴了PD算法在并行处理方面的优越性，提出了基于连接依赖信息（Join Dependency，JD）的连接查询优化算法。该算法利用连接依赖信息判断基于多站点的数据分布是否符合站点依赖，以降低远程访问的次数，对于不满足连接依赖的站点数据，则采用片段复制方法重新分布数据，确保其适用站点依赖算法。站点间关系或者关系片段的复制时间开销是该算法的惟一通信代价，但是这种代价会被站点间多线程的高度并行所弥补。

3 实验设计与实验结果分析

实验使用的硬件环境为Intel? CoreTM i5?3230M CPU @2.60 GHz（2 600 MHz），内存为4 GB，SCSI硬盘1 TB，转速为10 000 r/min。操作系统为GNU/Linux，开发环境为JDK1.6，在实验环境中，采用上述所列配置Hadoop集群工作站，共计3台，其中1台为MapReduce主节点，作为HDFS名称节点，另外2台为MapReduce从节点，作为HDFS数据节点。

使用LUBM工具分别生成50，150，300所大学的测试数据，并在Hadoop集群工作站中部署测试数据，使测试数据的分布满足站点依赖。分别从LUBM的14个标准查询中选取其中6个查询语句进行测试实验。LUBM数据集文件大小如表5所示。

本实验重点比较PD算法、JD算法和R*算法在数据集LUBM（50）、LUBM（150）和LUBM（300）上的查询性能。通过比较6个标准查询的计划生成代价和查询响应时间，验证算法的有效性。每个算法执行5次，取其均值。对比实验结果如表6～表8所示。

从实验对比结果可见，在数据量较小的情况下，基于JD算法的计划生成代价稍劣于PD算法，但要优于[R*]算法。随着数据量的增加，基于[R*]算法的查询计划生成代价值呈指数级增长，查询性能急剧恶化，而JD算法的计划生成代价仍近似于PD算法。这是由于[R*]算法不考虑站点依赖问题，需要将各站点的关系或者关系的片段分别复制到指定站点执行局部处理，然后选择总代价最小的策略作为最优策略，站点间的通信代价和局部处理代价随着数据量增加而急剧上升，查询效率急剧下降。

下面对三种算法在数据集LUBM（300）上的查询响应时间进行对比分析，实验进行5次，取平均值，实验结果如图2所示。

由图2可以看出，JD算法具有较好的查询响应时间，在大数据量环境下，与PD算法的响应时间差别不大，但明显优于R*算法。因此，本文提出的基于连接依赖信息的连接查询优化算法是可行的，具有较好的寻优效果和实际价值。

4 结 语

本文在分析利用站点依赖信息的算法和分片复制算法特性的基础上提出了利用连接依赖信息的分布式连接查询优化算法。算法的测试与结果表明，在基于多站点的连接查询中，该算法可极大地缩减网络的通信代价和局部计算代价。尤其当基于连接查询的大部分元组都能在本地站点找到，仅有少量元组需要从远程站点获取时，该算法可获得最佳性能。反之，该算法将退化为R*算法。

由于本文提出的算法的查询优化过程没有考虑查询结果向目标站点的传输代价，因此在连接操作返回的元组数较大的情况下，将产生额外的通信开销，从而给该算法带来负面影响。

参考文献

[1] 赵光亮.基于半连接算法的分布式数据库系统查询优化技术[D].杭州：浙江工业大学，2013.

[2] 钱磊，于洪涛.改进的半连接查询优化算法[J].燕山大学学报，2012，36（2）：178?182.

[3] 魏士伟，黄文明，康亚娜，等.分布式数据库中基于半连接的查询优化算法研究[J].计算机应用，2007，27（6）：34?39.

[4] 仝武宁，冉崇善，李宏斌.半连接查询优化算法的研究[J].计算机工程与设计，2011，32（3）：972?975.

[5] 陈钟，叶雪梅，青宪，等.一种改进的分布式数据库查询优化算法[J].计算机应用，2008，28（2）：233?237.

[6] FAN Y Y， MI X F. Distributed database system query optimization algorithm research [C]// Proceedings of 2010 3rd IEEE International Conference on Computer Science and Information Technology. Chengdu， China： IEEE， 2010： 657?660.

[7] KUMAR T V， VIKRAM S， AJAY K V. Distributed query processing plans generation using genetic algorithm [C]// Procee?dings of 2010 International Conference on Data Storage and Data Engineering. Bangalore： IEEE， 2010： 38?45.

[8] 邵佩英.分布式数据库系统及其应用[M].3版.北京：科学出版社，2012：123?127.

[9] 龚浩.分布式数据库查询处理和优化算法的研究[D].重庆：重庆大学，2005.

[10] 张瑞芳.分布式数据库的查询优化方法设计与实现[D].成都：电子科技大学，2010.

[11] OSMAN R， KNOTTENBELT W J. Database system performance evaluation models： a survey [J]. Performance evaluation， 2012， 69（10）： 471?493.