分布式数据库查询处理和优化算法

摘 要：随着大数据时代的到来和云服务的发展，分布式数据库系统（DDBS）的应用越来越普遍化，分布式数据库系统是通过分布式查询处理与分布式数据库（DDB）交互的综合性应用。无论是集中式数据库系统，还是分布式数据库。数据的查询处理都贯穿于整个应用项目的始终，而查询处理的优化也就显得非常重要。分布式数据库的数据具有分布性和冗余度的特点。这样在处理查询优化时一些技术的实现和问题的思考就相对复杂。本文从分布式数据库查询处理基本原理出发，对各优化策略和算法进行了阐述，并且针对性的提出了各个算法选择的思路和途径。

关键词：分布式数据库；查询优化

中图分类号：TP311.13

分布式数据库系统是在集中式数据库技术的基础上结合计算机网络相关技术，与集中式数据库的最大区别是：分布式数据库中的数据是分散性存储在网络中不同场所（结点），并且每个场地的数据库都有独立处理能力。并且可以在局部完成功能应用，除此之外，每个场地也要参与全局应用程序的执行，全局应用程序是通过已有的网络拓扑进行通信来访问各个场地的数据。在实际应用和操作当中，其实是感觉不到这个分布式网络存在的，操作的仍然是一个整体数据库系统[1]，这说明，分布式数据库物理上是分散各个网络节点上的，但逻辑上仍是同一数据库系统的数据集。这样就导致了在优化处理过程中与集中数据库系统的一些区别：

在集中式数据库中，查询优化是基于关系代数的优化整合，是一元运算符运算，主要目标是尽量减少数据冗余。

在分布式数据库中，网络数据的异步传输通信会有一定的代价，是二元运算符操作。需要通过冗余数据提高系统可靠性，从而改善系统性能。

基于分布式数据库系统中数据的分散性和冗余性，决定了其查询处理的优化也具有一定的复杂性。在实际应用当中，分布式查询处理和优化在整个项目周期中对工程质量的保证也是非常重要的环节。

1 分布式数据库查询处理代价分析

分布式数据库的查询处理操作是基于多点进行的数据传递，这样的数据查询也是并行化处理的一种。分布式数据库查询优化的目标是确保整个传输处理成本尽可能的小，主要包括CPU处理成本、I/O和通信开销[2]。对于不同的网络拓扑类型可以设计不同的查询处理算法。主要分两种情况考虑：

（1）在一般的远程网络通信中，网络传输的通信时间往往比本地局部数据处理时间要长，因而可以忽略本地的数据处理时间，以网络传输的通信时间为主要优化方向，那么减少传输的数据量和传输次数即为主要目标和途径。

（2）在高速的局域网络中，网络传输非常快，相比局部的处理时间就短很多。这种情况下减少局部处理时间是主要的优化方向。

一般以响应时间作为网络传输的一个重要指标。响应时间包括通信和处理时间。根据网络类型的不同各有侧重点。

基于以上分析，分布式数据查询的代价可以归结为CPU代价、I/O和网络通信代价之和。

网络通讯代价和数据传输量和网络传输速率相关。其公式可以估算为：

T=C0+C1*P （1）

C0为两端通信初始化的总时间，C1为网络传输速率，P为传输数据的总量。

2 分布式数据库查询处理过程

分布式数据库系统中查询处理需要考虑：

先将查询转换为等价的关系代数表达式，然后从各等价表达式中选择最优代数表达式进行查询优化处理。

需要涉及到网络各节点之间的数据交互，选择最优的节点路径和数据传输方式。

2.1 查询分类处理

分布式环境的查询类型包括本地查询、远程查询和全局查询，本地查询即局部查询，它同集中式数据库的优化技术一致。远程和全局查询描述如下：

（1）远程查询。单点数据的远程通信。若数据是冗余分配的，要减少查询处理的通信代价应该尽可能的选择从发出查询的节点最近的节点上的数据或者数据片作为查询对象

（2）全局查询。多点数据处理，其过程为：首先要确定查询对象，然后根据可用访问路径和必要的算法确定二元操作连接以及并操作的次序，最后确定执行节点（站点），需要考虑通信代价、执行效率以及查询速度，选择原则为：尽量选择距离提供站点数据的站点较近的站点；另外尽量选择较空闲的站点执行查询。

总之，选择最佳的查询处理策略，要确定好必要的物理片段以执行查询，也要确定在查询处理中各操作执行的次序和执行站点，此外，还取决于具体实现算法的操作。

从分布式数据库系统体系结构，分布式查询处理过程有四个层次：查询分解、数据本地化、全局优化和局部优化，其层次结构如图1。

图1 分布式查询层次

3 分布式查询优化算法

分布式数据库中查询优化是围绕着查询策略优化和局部处理的优化展开的。不同的结构、不同的应用中执行策略也不相同，系统资源的消耗和传输响应时间也有差异。

查询优化的基本方法有二：查询转化和查询映射。

查询转化：例如：连接或投影等关系操作，执行顺序不同。

查询映射：使用优化算法实现关系操作、访问设备。

本文主要阐述分布式数据库系统的查询处理半连接方法。

3.1 半连接查询优化基本方法

半连接方法是利用连接和投影操作产生的一种关系代数，主要适用于带宽较低的远程广域网络。其基本原理是网络中仅传输参与连接的数据，而不传递其他无用数据或者不参与连接数据[3]。数据传输为片段或整个关系，此为一种冗余方法。

设有两个关系R和S，分别属于不同站点。在属性R.A=S.B上做半连接操作。表示为如下形式：

R∝A=BS=∏（R∞A=BS）=R∞A=B（∏B（S））

采用直接连接方法进行R∞A=BS，通过两站点关系进行连接按公式（1）得此过程代价：

T全=C0+C1*size（B）*card（R） （2）

使用半连接方法，需要两次数据传输，整个过程的代价：

T半=2C0+C1*（size（B）*val（B[s]）+size（R?）*card（R?）） （3）

sizeB表示B属性的长度；val（B[s]）表示关系S中属性B上不同值的个数；card（R?）表示为R?的元组数。

一般情况下，有T半

3.2 二次半连接算法

在实际应用中，有时候请求结果集存放的站点不是请求站点，在结果集数据量较大时，会造成数据传输网络堵塞，导致网络负载不均衡，通信次数和响应时间增加。

二次半连接在半连接算法的基础上进行改进，用以进一步减少通信数据量，提高各站点通信并行性。其算法如下图：

图2 二次半连接算法

（1）在站点B做关系S在R和S连接属性B的投影∏B（S）。

（2）将∏B（S）发送到站点A。

（3）站点A依据接收到的投影值计算半连接结果R?=R∞A=B∏B（S）。

（4）R?的投影为∏A（R?）。

（5）发送∏A（R?）到站点B。

（6）在B站点执行∏A（R?）∞A=BS连接操作。

二次半连接算法在请求站点时比半连接算法增加一次连接过程，可以为A、B属性进行排序，在所属的站点也进行排序或者索引用以减少连接的开销，这样在请求站点传输数据的时候，按属性传输可以减少请求站点连接时间。在大型的分布式数据库系统中，二次半连接算法在传输量和响应时间的性能优化上相比版连接算法效果更明显。

3.3 其他算法

分布式数据库中除了半连接算法还有许多其他的优化算法。如：利用半连接缩减元组大小和减少数据传输的SDD-1算法的优化、基于遗传算法的优化、基于查询图和收益代价比因子的贪心算法的优化和粗糙集的查询优化等。

4 结束语

分布式查询优化算法的研究重点是如今高速发展的分布式应用系统和云计算平台。本文分析了分布式数据库查询优化处理的原理和过程，并针对其主要代价进行分析，基于查询优化的主要因素，对具体问题选择合适的优化算法。综合考虑，选择代价最小的优化方案来进行处理。

此外，虽然分布式数据库系统的环境是复杂的，但随着Web的发展及其技术内容的综合性也越来越丰富，对于研究分布式数据库系统的查询优化技术也会越来越优秀，即使在今后的发展中还存在许多问题需要研究和解决。随着物联网和大数量的不断发展，分布式查询优化技术的发展必将越来越完善。

参考文献：

[1]于秀霞，赵建平.分布式数据库直接连接查询优化算法的研究[J].长春理工大学学报，2005.

[2]钱磊.分布式数据库多连接查询优化算法研究[D].燕山大学，2012.

[3]孙婷婷.分布式数据库多连接查询优化算法的研究[D].曲阜师范大学，2010.

作者简介：张鹏宇（1982.06-）.男，河南郑州人，工程硕士在读，讲师，研究方向：软件工程。

作者单位：河南职业技术学院，郑州 450000；郑州大学信息工程学院，郑州 450000