摘  要：自分布式数据库诞生以来，人们对于分布式数据库查询优化的研究就一直处于进行时。由于分布式数据库物理上分布而逻辑上集中等特性，其查询优化问题较集中式数据库来说要复杂很多，因此查询优化对于分布式数据库来说一直是一个重要问题。本文首先概述了分布式数据库的特性以及分布式查询处理优化的若干知识，随后总结了目前该领域内五种主流的查询优化策略，接着简单介绍了三种尚处于研究中的查询优化改进方案，最后在文章末尾作出结论和课程总结。

关键词：分布式数据库；查询处理；优化算法      

      分布式数据库系统是物理上分布而逻辑上集中的数据库系统。物理上分布是指分布式数据库系统中的数据分布在由网络连接起来的、地理位置分散的不同站点上逻辑上集中是指各数据库站点之间在逻辑上是一个整体,并由统一的数据库管理系统进行管理,同时各站点又具有管理本地数据的能力。

      考虑到分布式数据库系统具备的物理分散性和逻辑上集中性特征，可以将其看为计算机网络和数据库系统相结合的数据库系统，综合来看共包含两个重要的组成部分:分布式数据库和分布式数据库管理系统。其中分布式数据库是计算机网络环境中各场地或站点上数据库的逻辑集合。传统方式的数据库系统为集中式数据库系统,而分布式数据库系统中的各场地数据库为局部数据库。分布式数据库是一组结构化的数据集合,逻辑上属于同一系统,而物理上分布在计算机网络的各个不同站点上，其中最大的特点是这组数据所具有的分布性和逻辑协调性。

      分布式数据库管理系统和集中式数据库管理系统一样,是分布式数据库系统中的一组软件。负责管理分布式环境下逻辑集成数据的存取、一致性、有效性、完整性等。同时由于分布式数据库的分布性,所以在管理机制上还必须具有计算机网络通讯协议上的分布管理特性。因此,分布式数据库管理系统比集中式数据库管理系统更加复杂。

      查询操作是数据库中最基本也是最常用的操作，通常用户最关心的问题也是如何高效、快速的从数据库中查询出需要的数据，因此，对于查询操作的优化一直是数据库系统的热点问题之一。

      关于分布式查询处理问题是由E-Wong最先提出的，其实质是通过数据分析和数据交互，将分布式查询这一问题转化为局部的数据条目查询。在传统的集中式数据库系统中，执行查询的代价用处理查询的CPU代价和计算机I/O 代价来进行衡量。而在分布式数据库系统中，由于系统是由分散在网络中的多个站点上的计算机组成，这就使得分布式数据库系统执行查询的预期代价除了要考虑 CPU 代价和 I/O代价外，还要考虑数据在网络上的通信代价。综合来看分布式数据库的查询优化主要从两个方面来着手，一方面是降低查询总代价，另一方面是缩短响应时间。

      由于分布式数据库系统的网络分布性，不同的分布式查询优化算法的查询费用以及并行处理速度也是大不相同。另外由于分布式数据库系统的分布性和冗余性，使得分布式数据库的查询优化相比集中式数据库而言更加多样、更加复杂。因此，分布式数据库系统的查询优化不仅直接影响分布式数据库系统的性能，而且还对增加分布式数据库的效率和可靠性起着重要作用，相对于集中式数据库系统，分布式数据库系统的查询优化更加具有研究价值。

      由于分布式数据库的分布透明性，使得用户在进行数据的查询时，不必去知道关系是否被分片、有无副本、数据的具体物理存放位置等，对用户而言，查询的过程同集中式数据库一样。为了方便下文介绍分布式数据库的查询优化解决方案，在此定义查询结构的四个层次，自上而下分别为查询分解、数据本地化、全局优化、局部优化。

图1  分布式查询结构

      其中数据本地化和全局优化阶段是分布式数据库查询优化的重点。

      自从分布式数据库系统问世以来，大量学者一直在对分布式数据库的查询优化进行大量的研究并且提出了一些大家公认的经典算法，由于很多算法基本都是针对某一具体情况而实现的优化，具有一定的局限性，但作为本科学习分布式数据库的起步阶段，在这些算法中仍有很多值得探讨与学习的地方。

      在集中式数据库查询还是在分布式数据库查询中，选择、投影和连接是最常用的三种操作。对于选择和投影，集中式数据库与分布式数据库对这两种操作的优化处理思路基本一致，但是连接操作则不同。分布式数据库系统的数据是分散存储在网络中的不同站点上的，而数据之间的连接操作必然会涉及到站点间的通信及数据传输，因此对于连接操作的优化成为了分布式数据库查询优化的优化思路之一。此外，分布式数据库查询优化的其它思路还包括：利用关系代数的等价原则对查询进行优化；利用代价模型查询图和贪心思想相结合实现优化；以多表连接查询的特征为基础,对粒子进行树形编码以实现全局的优化策略。

      该算法的基本思想是先将目标查询问题转换为关系代数表达式，然后基于关系代数等价变换的优化算法使用启发式优化方法对关系代数表达式进行优化[1]。

      在对传统的集中式数据库查询优化学习的过程和实践中，其发挥的优化作用不言而喻。类比在分布式数据库系统的查询过程中，最花费时间和空间的运算必然也是笛卡儿积和连接操作，为此，沿用传统优化过程中的三条启发式规则，用于对表达式进行转换，以减少中间关系的大小：

a.  尽可能早地执行选择操作；

b.  尽可能早地执行投影操作；  

c.  避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并起来一起做。

      算法首先利用关系代数等价变换规则，把查询树中的连接和合并操作尽可能上提，选择和投影操作尽可能下移到片段的定义处。然后判断是水平分片还是垂直分片，若为水平分片，则把分片条件与选择条件进行比较，去掉存在矛盾的片段，如果只剩下一个片段，就可以去掉一个并操作。若为垂直分片，则把片段的属性集与投影操作所涉及的属性集进行比较，去掉无关的所有片段。如果只剩下一个垂直片段，就可以去掉一个连接操作，从而达到优化查询的目的。

      网络中两个站点间进行连接操作时，需要将一个站点的关系通过网络传输到另一站点与在该站点上的关系进行连接操作。在这个过程中，如果传输整个关系，那么网络传输中的数据量会很大，网络本身复杂多变，如果一次性传输较大的数据量定会产生不少问题。

      而在实际的连接操作中，并非所有的数据都参与连接操作。因此为减少传输数据量，可以禁止那些不参与或者无用的数据在网络中传输，而半连接操作就是针对这一问题提出来的，它要实现的目标是减少进行连接操作关系的数据量，从而减少在网络上的传输的数据量，但同时在某种程度上会增加通信的次数以及本地处理的时间。所以在以网络传输费用为主要优化对象的情况下，使用半连接操作效果更好。在现实中广域网环境中，数据在网络上的传输速度要比计算机上的数据库处理速度慢很多，这样在广域网的分布式数据库查询操作情况中，查询优化的目标往往是尽可能地减少网络传输的总费用，基于该种情况多选择半连接算法作为主要的查询优化算法。共有三种代表性算法：

1）SDD—1 算法[2][3]：算法主要分为基本算法和后优化算法两部分.SDD-1基本算法主要依据比较缩减程序的关键因素———费用、效率、收益估算, 算法最后得出半连接缩减程序集合, 由该集合给出最收益执行策略。SDD-1后优化算法主要是修正SDD-1基本算法得到的解, 使得到的最收益执行策略更合理、更节约时间，最后将所有站点得到的数据进行整合就能获取最终的查询结果。

2）WPERF＋算法[4]：是W[5]算法和PERF算法[6]的综合版，优化目标是在保证结果正确性的基上尽可能减少查询过程产生的网络流量来优化查询。

3）二分劈开缩减算法[7]：基于高速网环境下，以响应时间作为优化准则，既考虑了数据的传输代价，又考虑了数据的局部处理代价，最大限度地运用并行性，使得响应时间得以减少。

      为了使数据的传输代价和数据的局部处理代价达到最小 , 最大限度地实现站点间局部操作的并行性 , 并不急于在一个站点上形成半连接运算后得到的连接结果 , 而是用二分劈开条件把完全半连接缩减的关系分为两半 , 随后把具有相同条件的数据被送到一个站点进行连接 , 最终形成分布在两个站点上的连接结果 , 避免了在一个站点上形成大的连接结果 , 提高了并行性。由于分布式的复合查询是由许多分解到下层的这样的简单查询组成的，因此这种并行效果会逐渐向上传递到上层，最终提高整体查询的响应速度和处理效率。

      半连接操作倾向于通过减少网络上的数据传输量以提高查询速度，但在另一方面会造成通信次数的增加以及本地处理时间的增加。而在高速局域网下，由于数据在站点间的传输时间通常要比局部处理时间要短，所以减少局部时间就成为查询优化的关键问题，在这种情况下采用直接连接算法的效果会比较好，下面介绍三种代表性算法：

1）分片复制算法：首先选择分布式数据库系统的一组站点，将某一参加查询的关系进行分 

片并将所得片段都传递到该组站点上，每个站点独立进行关系的连接操作，而最后站点操作结果的并集即为查询结果。

2）Hash划分算法[8]：选则一个合适的Hash 函数，然后对关系的某一属性或者属性集的元组值应用Hash函数，将具有相同Hash结果的元组放置到同一个站点，这样就能够得到相应关系的水平片段。从而经过Hash划分的每一个关系的元组都会根据该元组Hash结果存放到多个不同的站点上而组成相应关系的水平片段。

3）Partition算法：利用分布式数据库的分布性特点，在涉及到多个关系的连接操作中，该算法通过对两个或多个关系在同一连接属性上进行进行有效的片段划分，来提高连接操作的并行性，以此降低整个查询的响应时间。然而对于海量数据以及关系较多连接属性各不相同的查询而言，这种算法的效果并不理想。

      根据查询操作装化为等价的查询图，按照相同划分属性合并规则不断合并迭代，保证最终查询图内的关系数量相当以及各子查询所需时间的均衡，其中连接查询操作按照查询图的结构又可细分为树查询、环查询、星型查询和链查询，下面介绍两种代表性算法：

1）CHAIN算法：对于可以将查询转换为链形结构的查询图中，从所有连接的关系中选择连接代价最小的两个关系进行连接，连接形成的新关系放入剩下没有进行连接的关系中，然后在从这些关系中选择代价最小的两个关系进行连接，局部最优的累加最终达到全局最优,最终能够找到最少的连接代价序列。

2）Kruskal算法：该算法是一种贪心算法，对于非链型查询图情况下的优化效果较好。特点在于巧用了构造最小生成树的算法，即从一个带权的图中寻找最小代价的生成树，各边相连的两个关系连接代价作为带权图中各边的权值。算法的基本思路假设一个有关系的查询图，首先计算所有边的权值，构造最小生成树的过程是选择其中一条具有具小权值的边,然后将该边上的两关系合并为一个新的关系，记录连接两个关系的代价并将新关系加入到图中，同时删去被连接的两个关系及其对应的边，再次选择一条最小权值的边，重复以上步骤，直到查询图只有一个顶点，即得到查询图最少连接代价。类比最小生成树算法应用的广泛性，该算法对于不同查询图都能找到连接代价最小的查询序列，可以实现最大程度的优化。

      粒子群优化(PSO)算法是一种随机全局优化算法, 是以多表连接查询的特征为基础,对粒子进行树形编码的一种分布式数据查询方式[9]。与传统的随机算法不同，PSO 算法将问题的解抽象为粒子，不是从单个点，而是从一个粒子群体开始搜索，同时粒子具有“记忆”和“学习”的能力，通过迭代过程中粒子间的合作与竞争，能使整个粒子群不断向最优区域搜索。研究表明，使用粒子群算法优化后的查询策略比原始查询策略的查询执行代价低，有效地增加了系统的查询效率，适合解决组合优化领域的一些典型问题。

      本质上蚁群算法属于进化算法中一种特殊的启发式全局优化算法，具有分布计算、启发式搜索和信息正反馈的特征，适合解决多维动态优化问题[10]。在蚁群算法中，每一个个体都会通过释放信息素的方式对周边环境信息改变，而且个体也能够对周边环境的变化进行实时感知，通过环境实现相互通讯。具体操作过程为：将连接操作进行拆分，寻找最优的查询方案即寻找最优的连接路径，即类比于蚁群问题中的寻找最优路径问题。在蚁群问题中通过代价估计模型计算连接代价作为蚁群算法中的路径权值，利用蚁群算法在寻找最优路径上的优点进行查询优化，在搜索过程中，利用分布式计算，可以实现多个体并行计算，有助于提升计算能力和运行效率。目前该解决方案仍处于研究阶段，但大量的实验结果已表明，该算法不仅有效，而且具有较好的寻优能力，当在连接元组数增多时依然有更好的表现，查询时间有效缩减。目前衍生出来的比较常见的蚁群算法还包括基本蚁群算法AS、最大最小蚁群算法MMAS、最好最差蚁群算法BWAS等[11]。

      该算法和蚁群算法有相似之处，均借助于自然界中诸如蚂蚁、蜜蜂等群聚类动物群体内的动物自治体模式[12]，所谓动物自治体，就是通过对实体进行模拟，构建相应的结构来重现动物感知环境变化时所做出的自我调节及快速适应的过程，将动物自治体的模式与结构、鱼类活动与分布式数据库特点相结合，从而提出了用于解决优化问题的人工鱼群算法[13]。

图2  动物自治体结构

      从简化分布式多连接查询的搜索空间入手，首先通过策略选择算法降低搜索空间的复杂度，然后采用该算法模拟鱼的觅食、聚群和追尾行为，利用它对极值敏感、反应迅速且同时具备较强的察觉并逃离局部极值的能力等优势在鱼群中构造单个人工鱼个体的局部寻优能力，最终达到全局最优状态即实现分布式数据库的最优多连接查询。

      遗传算法（GA）是一种借鉴生物进化规律演化而成的随机化搜索方法，可以通过对自然进化过程的模拟，寻求最优解。其基本原理是生物学中的选择、交叉、变异和遗传等进化现象，本身具有自适应性和自学习型的特点，在大数据处理中有着良好的适用性，经常被用于解决最优化问题。

      顾名思义，并行GA-MMAS是一个将遗传算法与蚁群算法结合并实现并行化查询处理的解决方案，它能够充分发挥分布式计算集群优势，缩短算法执行时间[14]。算法思想为：先将种群分割成多个大小相等的子种群，保证每个线程独立完成子种群遗传操作，保留从其他种群获取的待交流个体，依照串行GA选择机制，选出进化父体，以本地进化父体与待交流个体完成子种群间交流。在预设进化次数完成后，主线程会对所有子种群的局部最优解进行归约，最终得到全局较优解，再经MMAS算法全局寻优，得到全局最优查询序列。

      在分布式数据库领域，查询优化始终是一个热门研究问题。论文对分布式数据库查询处理相关技术进行了研究,分析了分布式查询处理和优化的相关内容,其中涉及了查询处理的层次结构和分布式查询优化算法的分类。在讨论查询优化的算法中，作者在前人已有关于分布式查询优化算法研究的基础上，综述了五类比较经典的分布式查询优化算法，此外对三种比较新的改进算法进行了简单的介绍，其未来的发展前景尚需要时间来检验，相信人们在当今数据爆炸增长的时代对于速度的追求是无止境的！

[1] 陆海晶. 分布式数据库系统查询优化算法的研究[D]. 辽宁工程技术大学, 2007

[2] 谢旭升,陈复兴.基于并行的SDD-1算法的改进[J].山西大学学报(自然科学版),2013,36(03):338-343.

[3] 聂林娣.分布式数据库查询优化策略研究[J].电脑知识与技术:学术交流,2006（6）:5-6.

[4] 冯祖洪,徐宗本.WPERF+:一种有效的分布式查询处理优化算法[J].工程数学学报,2004,21（5）:797-802.

[5] Yu, C. T.1;Chang, C. C.1.Distributed Query Processing.[J].ACM Computing Surveys, 1984,vol.16,No.4

[6] Ming-Syan Chen, Philip S Yu. Combining join and semi join operations for distributed query processing[J].IEEE Transactions on Knowledge and Data Engineering,1993;5(3):534-542

[7] 张时鹏,陶世群.大规模数据库的一种新的分布式查询优化算法──二分劈开缩减[J].计算机工程与设计,1998(04):60-64.

[8] De Witt,D.J.,and Gerber,R. Multiprocessor hash-based join algorithms[A]. In Proceedings

of the 11th International Conference on Very Large Data Bases[C], 1985:151-164

[9] 陈一栋.分布式数据库查询优化算法研究与实现[D].长沙理工大学,2008.

[10] 崔峰峰,南振岐.基于蚁群算法的分布式数据库查询优化方法[J].计算机时代,2014(05):47-49.

[11] 周 莹.基于多蚁群遗传算法的分布式数据库查询优化研究[D].上海师范大学，2016.

[12] S.W.Wilson. Knowledge growth in an artificial animal[C]. Proceedings of an International Conference on Genetic Algorithms and Their Application,1985:16~23.

[13]袁月. 基于改进鱼群算法的分布式数据库多连接查询优化的研究[D].安徽理工大学,2017.

[14] 张静波.以并行遗传与蚁群算法为核心的分布式数据库优化[J].通讯世界,2018(01):268-269.