分布式数据库查询策略的优化方法

王立峰

摘要：分布式数据库是数据库和计算机网络技术有机的结合，它可以将不同区域的资源进行共享，从而有效的提高工作效率。从逻辑上讲分布式数据库是一个整体，具有冗余性和分布性，使得查询数据变得较为麻烦，因此如何优化分布式数据库的查询策略，提高其查询效率成为该文的一个研究重点。

关键词：分布式数据库；查询策略；优化方法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）21-4967-02

1 绪论

从物理上来讲，分布式数据库的数据分布在计算机的各个不同站点上，这些数据是一个逻辑的整体，同由分布式数据库进行全局的管理。分布式数据库的作用主要是存储数据和方便、快捷的查询数据，因此查询策略的优化已经成为了分布式数据库的一个核心问题。该文主要论述了分布式数据库的查询策略以及一些有效的优化方法和提高策略。

2 分布式数据库及查询优化分析

分布式数据库系统从物理上来讲是分散的，而从逻辑上来讲是一个统一的系统，它是将分布在不同站点上的逻辑单位通过计算机网络连接起来。按照数据模型的类型，分布式数据库系统可以分为同构同质型DDBS、同构异质型DDBS以及异构型DDBS三种[1]。同构同质型DDBS中多种数据库类型采用了同样的型号，而且数据库内的数据模型属于一个类型；同构异质型DDBS数据库内的数据模型采用的也是同一型号，但是数据库类型却不相同；异构型DDBS中的数据库类型和数据模型均不一样。

按照分布式数据库的控制系统可以将分布式数据库系统分为集中式DDBS、分散性DDBS以及可变型DDBS。集中式DDBS在一个节点上保存全局的控制信息，所以容易实现整个分布式系统的数据一致性；但是这一种分布式系统存在一定的单点故障，一旦存放全局控制信息的节点出现问题，整个分布式系统将不能继续使用。分散性DDBS在每个节点上都保存了全局控制信息的一个副本，虽然这样可以保证整个分布式系统的稳定性，但是却难以保证所有节点上数据的一致性。可变型DDBS综合了上述两种分布式系统的优势，只有一部分节点保存全局控制信息，这些节点被称为主节点；没有保存全局控制信息的节点称为辅节点。

对分布式数据库系统而言，数据库中数据的分布性使其查询操作比一般的数据库更加复杂，而且目前还没有一种能够适用于所有分布式数据库系统的有效方案。从众多的数据查询方法中找到一种最优方案就成了衡量分布式数据库系统的重要依据。一般而言，衡量数据查询方法优劣的重要依据是查询代价和响应时间，即在数据查询期间，数据查询操作所耗费的处理器代价是否足够小，数据查询的响应时间是否足够短。除此之外，分布式数据库数据的分布性，使得在进行数据查询的优化时，还要考虑网络通信因素。在对分布式数据库的查询策略优化时，一般有两种优化目标[2]：降低查询代价或缩短数据查询的响应时间。查询代价由处理器的执行时间和输入/输出的处理时间两部分组成，在降低网络通信代价的同时可以减小查询代价，从而起到优化分布式数据库查询操作的作用。分布式数据库能够进行数据的并行查询，并行处理操作降低了查询时间。

在分布式数据库系统中，查询操作主要有远程查询、本地查询以及全局查询三种类型。本地查询只在本节点上查询数据库数据，远程查询可能在其他节点上查询数据，全局查询会在多个节点上查询数据，所以可以认为是局部查询和全局查询的结合。远程查询和全局查询会查询其他节点上的数据，所以会涉及到网络通信，研究查询优化算法时，这二者是经常需要研究的该节点。进行远程查询时，由于不同节点的通信代价不同，所以选择不同的分布式数据库节点可能会得到不同的查询效率，如何选择分布式节点以得到最小的查询代价，就是查询优化的一个重要问题。全局查询会涉及到多个节点，比远程查询更复杂；为使执行全局查询时得到较好的优化结果，通常要完成四种优化策略[3]：（1） 数据副本个数的确定。分布式数据库的数据一般是冗余存储的，即一份数据可能保存到多个分布式节点上。如果一个查询涉及到的所有数据都只有一份副本，那么此查询过程就可以称为非冗余具体化，否则的话就称为冗余具体化。当查询数据有多个副本时，不同的数据片段会影响查询效率，所以首先需要确定查询数据的副本个数。（2） 确定操作顺序。分布式数据查询一般包括投影、选择以及排序等操作，选择和投影操作会从全部数据集中选择一小部分数据，会减少查询的数据量，所以一般可以先执行；连接等查询操作会增加数据量，而且会涉及到多个分片，所以一般后执行。（3） 确定执行方法和执行节点。有的操作会产生比较大的时间开销或代价，所以可以选择其替代方案；同时要尽量选择系统空闲、效率比较高的节点执行查询操作。

分布式数据库查询操作从过程上分为四层[4]：分布式数据查询分解、数据库数据的本地化、全局优化以及局部优化。

作为分布式数据库查询优化的第一层，查询分解（query decomposition）的作用是将全局模式中转换为SQL语句。数据库数据的本地化（data loclization）根据数据库的分片信息，把全局查询转换为数据库分片上的查询，从而实现全局查询操作的本地化。全局优化（global optimization）从本地化查询中找到一个最佳的查询次序，以尽量降低查询的代价；在全局优化过程中，对数据库表的连接操作进行优化将是一个重要方向；经过全局优化后，原来的数据会变为一个经过优化的、数据库分片上的关系代数查询。局部优化（local optimization）在每个分布式节点上执行数据分片的查询，并进行此节点上的优化。这四层在分布式数据查询优化上起到的作用是不尽相同的，第二层和第三层是优化的核心；不论是哪层的优化操作，都离不开对连接操作的优化，连接操作由于会涉及到在多个节点间进行数据传输，所以会有较大的网络通信开销，当前处理连接操作的优化算法主要分为基于连接的查询优化算法和基于非连接的查询优化算法。

3 基于哈希算法的分布式查询优化方法

分布式数据库的数据关系一般会分布到不同节点上，如果要对两个关系做连接操作，最佳情况是尽可能少的传输数据；只要节点上存储的数据和应用的相关性越大，连接操作所涉及的数据传输就越小，这种依赖关系称为“站点依赖”。如果两个关系不满足站点依赖，就需要先将元组个数少的那个关系复制到另外一个关系所在的节点上，然后进行连接操作。如果两个关系元组个数都很多，那么就需要对它们进行数据分片，Hash算法是一种有效的数据分片方法。

Hash算法对要进行连接操作的某属性进行运算，计算此关系中所有元组的Hash值，并把Hash值相同的元组放到同一个节点上，在每个节点上的关系片段都满足站点依赖关系。最简单的Hash函数是对关系进行取模运算，并将Hash值为奇数的元组划分到同一节点，Hash值为偶数的元组分到其他节点。对于多个关系的运算，Hash算法会首先分析这些关系在某一属性列上的元组值，如果多数元组值呈现奇偶均匀分布，那么就可以对这些关系进行模2取余操作，并按照简单Hash函数的元组划分策略进行分配。如果在这一属性列上的元组值呈现大小写字母均匀分布，那么可以类似的将Hash值为大写字母的元组分配到一个站点，Hash值为小写字母的元组分配到另外一个站点。

当分布式数据库关系的个数多于两个时，利用Hash算法划分元组的情况更加复杂。以三个关系R1、R2以及R3为例，它们的元组可能分布在两个、三个甚至更多的节点上；元组分布的节点越多，越难以选择合适的Hash函数，此处先考虑两个节点的情况。当只有两个节点时，这三个关系的连接可能是相同属性列的连接，也可能是不同属性列的连接；当对相同属性列进行连接时相对简单，可以先求得元组在某一属性列上的Hash值，然后对这三个关系进行划分，得到满足站点依赖关系的分布式数据。当对不同属性列进行连接操作时，由于连接操作是在两个不同属性上进行的，所以只选择一个Hash函数会得到两组不同、可能有冲突的Hash值，也就是说一个关系上的同一元组，根据不同的属性列得到的分配节点可能不同，既可能被分配到节点1，也可能被分配到节点2，无疑会造成困扰。对这种问题的解决方法是[5]：以某一属性列作为关键词，对其做Hash运算后，分别将关系R1、R2分配到节点1和节点2上，然后再用同一个Hash函数对另外一个属性列做Hash运算，并分别将关系R2、R3分配到节点1和节点2上；此时关系R2上的元组虽然可能分布在节点1和节点2上，但R1和R3都完全分布在一个节点上，使占原来2/3的数据完全满足站点依赖关系，从而提高了分布式数据查询的效率。对于多于三个的关系时，对相同属性的连接操作也比较简单；当要连接的是不同的属性时，可以先对要连接的属性列进行分组，再对每组的属性按照上面的方法进行连接即可。

4 结论

本文首先讲述了分布式数据库系统，并分析了分布式数据库系统中可以进行查询优化之处，最后对分布式查询的方法进行了优化，提出一种基于哈希算法的分布式查询优化方法；本文提出的基于哈希算法的分布式查询优化方法可以有效优化分布式数据库查询效率，对后续研究有一定的参考价值。

参考文献：

[1] 朱建生，汪健雄，张军锋.基于NoSQL数据库的大数据查询技术的研究与应用[J].中国铁道科学，2014，1（16）.

[2] 于洪涛，钱磊.一种改进的分布式查询优化算法[J].计算机工程与应用，2013，6（8）.

[3] 赵荣.分布式数据库查询优化方法[J].科技视界，2013，5（28）.

[4] 何爱华，戚晓明.半联接计划的全局查询优化策略研究[J].重庆科技学院学报：自然科学版， 2012，5（1）.

[5] 邓松，林为民，张涛，马媛媛.基于禁忌GEP的分布式数据库查询优化算法[J].计算机与数字工程，2013，10（17）.