一种分布式数据库系统的跨节点查询优化方法及系统

摘要

本发明公开了一种分布式数据库系统的跨节点查询优化系统，包括：全局查询总代价最低要求模块，查询分解及本地化模块，多因素决策的模糊评估模块，连接建立模块，局部优化模块，Bp神经网络自适应优化模块，全局优化模块。在此系统的基础上，提出了一种分布式数据库系统的跨节点查询优化方法，实现了在局部优化阶段对每个分片查询路径进行优化判决，以及在全局优化阶段对全部分片查询路径进行Bp神经网络自适应优化。本发明通过对每个分片查询路径的优化，降低全局优化的计算负担，使得全局查询具有更快的查询速度，并通过定义全局优化代价函数使得查询总代价可控。

说明书

技术领域

本发明涉及分布式数据库系统技术领域，特别是指一种分布式数据库系统的跨节点查询优化方法及系统。

背景技术

分布式数据库系统是计算机网络与数据库系统的有机结合。由于涉及大量数据在网络上的传输，因此查询处理和优化就成为分布式数据库提高查询性能的关键因素。查询处理和优化就是通过合理的算法尽量减少通信的信息量，从而提高查询的响应时间性能以及减少系统开销。分布式查询优化相比传统的单机优化方法拥有更好的数据可靠性，更快的查询速度以及可扩展的存储容量。分布式查询优化一般需要进行：查询分解、数据本地化、局部优化、全局优化。

在分布式数据库系统上的一般查询步骤为：根据用户的查询内容进行查询分解，初始化查询路径，检查本地是否有此数据库，如果有则在本地执行；如果没有则全局查询处理模块根据查询路径来选择一台处理本查询最优化的节点，即选择一个有该数据库且所操纵的表的查询代价最小的数据库节点。并与优化的节点建立连接，将查询命令发送到优化的节点上去执行。

在此过程中，由于分布式数据库系统存在于网络环境，所以必须考虑节点之间的通信代价和分布式计算处理。目前的查询分解、数据本地化、局部优化、全局优化四步骤的方法，在通信代价的开销及查询执行的实际代价上仍然无法满足用户需求，得到的并非分布式数据库系统中全局最优的执行节点。

发明内容

有鉴于此，本发明的目的在于提出一种分布式数据库系统的跨节点查询优化方法及系统，提高查询的响应时间性能。

基于上述目的本发明提供的一种分布式数据库系统的跨节点查询优化方法，包括：

确定全局查询总代价以及全局查询总代价最低要求；

在局部优化阶段：

通过数据本地化及查询分解的步骤将查询问题落在合适的片段上；

通过多因素决策的模糊评估判定多个影响因素中对降低查询代价贡献最大的影响因素；

进行连接建立，即在当前的分片查询路径中，根据对降低查询代价贡献最大的影响因素，查找到查询代价最小的数据库节点并与之建立连接进行查询，从而得到片段上的查询结果；

在与片段上的查询结果有关的各个数据库节点进行局部优化；

在全局优化阶段：

定义全局优化代价函数；

采用Bp神经网络求得全局优化代价函数的最小值，使得输出满足全局查询总代价逼近全局查询总代价最低要求，其中，Bp神经网络的输入为片段上的查询结果；

进行全局优化并最终输出最优的全局查询路径。

在一些实施方式中，所述确定全局查询总代价以及全局查询总代价最低要求的步骤中，将全局查询总代价最低要求定义为查询时间误差估计和查询响应时间的加权和，即C_min＝w₁·t_e+w₂·t_r，其中，C_min是指全局查询总代价最低要求，t_e是指查询时间误差估计，其为全部网络时延及时钟漂移引起的查询时间误差之和的估计，t_r是指查询响应时间，其是从用户提交查询请求到收到完整的返回信息的平均时间，并有w₁+w₂＝1。

在一些实施方式中，，所述多因素决策的模糊评估至少包括以下过程：

构建多因素决策的模糊评估模型；

对每个分片查询路径进行优化判决；

评估结果作为局部优化的输入。

在一些实施方式中，所述构建多因素决策的模糊评估模型至少包括以下步骤：

定义每个分片查询路径中共有I个影响因素能够降低查询代价；

定义在I个影响因素共同作用下得到的查询代价函数为F(x_I)，其中x_I为为函数输入；

定义其优化目标函数，即min{F(x_i)}，用于判定对降低查询代价贡献最大的影响因素。

在一些实施方式中，所述对每个分片查询路径进行优化判决至少包括以下步骤：

对min{F(x_i)}进行求解得到一组u_i，其中u_i为优化目标函数解析式中的一个参数，其表示第i(i≤I)个影响因素对降低查询代价的贡献；

选取其中最大的u_i，判定对应第i个影响因素对降低查询代价贡献最大；

查找当前的分片查询路径中，在第i个影响因素作用下查询代价最小的数据库节点并与之建立连接进行查询。

在一些实施方式中，所述的Bp神经网络设计为一个3层的前馈神经网络N，各层均有连接权向量，用梯度下降法对BP神经网络的各层的连接权向量进行求解，最终输出即为最优的全局查询路径。

本发明提供的一种分布式数据库系统的跨节点查询优化系统，包括：

全局查询总代价最低要求模块，用于在全局总代价定义确定全局查询总代价以及全局查询总代价最低要求；

本地化及查询分解模块，用于将查询问题落在合适的片段上；

多因素决策的模糊评估模块，用于通过构建多因素决策的模糊评估模型，判定多个影响因素中对降低查询代价贡献最大的影响因素；

连接建立模块，用于在当前的分片查询路径中，根据对降低查询代价贡献最大的影响因素，查找到查询代价最小的数据库节点并与之建立连接进行查询；从而得到片段上的查询结果；

局部优化模块，用于在与片段上的查询结果有关的各个数据库节点进行局部优化；

Bp神经网络自适应优化模块，用于定义全局优化代价函数，并采用Bp神经网络求得全局优化代价函数的最小值，使得输出满足全局查询总代价逼近全局查询总代价最低要求，其中，Bp神经网络的输入为片段上的查询结果；

全局优化模块，用于进行全局优化并最终输出最优的全局查询路径。

在一些实施方式中，所述全局查询总代价最低要求模块，用于将全局查询总代价最低要求定义为查询时间误差估计和查询响应时间的加权和，即C_min＝w₁·t_e+w₂·t_r，其中，C_min是指全局查询总代价最低要求，t_e是指查询时间误差估计，其为全部网络时延及时钟漂移引起的查询时间误差之和的估计，t_r是指查询响应时间，其是从用户提交查询请求到收到完整的返回信息的平均时间，并有w₁+w₂＝1。

在一些实施方式中，所述多因素决策的模糊评估模块，包括：

模型构建模块，用于构建多因素决策的模糊评估模型；

优化判决模块，用于对每个分片查询路径进行优化判决；

局部优化输入模块，用于将评估结果作为局部优化的输入。

在一些实施方式中，所述模型构建模块包括：

影响因素定义模块，用于定义每个分片查询路径中共有I个影响因素能够降低查询代价；

查询代价函数定义模块，用于定义在I个影响因素共同作用下得到的查询代价函数为F(x_I)，其中x_I为函数输入；

优化目标函数定义模块，用于定义其优化目标函数，即min{F(x_i)}，其用于判定对降低查询代价贡献最大的影响因素。

在一些实施方式中，所述优化判决模块包括：

求解模块，用于对min{F(x_i)}进行求解得到一组u_i，其中u_i为优化目标函数解析式中的一个参数，其表示第i(i≤I)个影响因素对降低查询代价的贡献；

影响因素判定模块，用于选取其中最大的u_i，判定对应第i个影响因素对降低查询代价贡献最大；

查询连接模块，用于查找当前的分片查询路径中，在第i个影响因素作用下查询代价最小的数据库节点并与之建立连接进行查询。

在一些实施方式中，所述Bp神经网络自适应优化模块包括:

Bp神经网络设计模块，用于将Bp神经网络设计为一个3层的前馈神经网络，各层均有连接权向量；

各层参数求解模块，用于利用梯度下降法对BP神经网络的各层的连接权向量进行求解。

从上面所述可以看出，本发明提供的分布式数据库系统的跨节点查询优化方法及系统可以实现：

1、对每个分片查询路径进行优化判决，即在多个影响因素中通过计算判决出对降低查询代价贡献最大的影响因素，并用该影响因素做出优化判决，降低全局优化的计算负担，从而提高全局上的查询速度。

2、对全部分片查询路径进行Bp神经网络自适应优化，即设定全局查询总代价最低要求，在实际的全局查询总代价满足所述全局查询总代价最低要求的情况下，在神经网络中自适应的调整各层的权值，从而在全局上实现查询的自适应最优化。由于最低要求是事先设定好的，故，这样做可使得全局查询代价可控。

附图说明

图1为现有方案实施例流程示意图；

图2为本发明提供的分布式数据库系统的跨节点查询优化方法实施例的流程示意图；

图3为本发明提供的分布式数据库系统的跨节点查询优化系统实施例的模块结构示意图；

图4为本发明提供的分布式数据库系统的跨节点查询优化方法实施例的步骤S230的进一步具体流程示意图；

图5为本发明提供的分布式数据库系统的跨节点查询优化方法实施例的步骤S310的进一步具体流程示意图；

图6为本发明提供的分布式数据库系统的跨节点查询优化系统实施例的模块430的进一步具体结构示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本发明进一步详细说明。

需要说明的是，本发明实施例中所有使用“第一”和“第二”的表述均是为了区分两个相同名称非相同的实体或者非相同的参量，可见“第一”“第二”仅为了表述的方便，不应理解为对本发明实施例的限定，后续实施例对此不再一一说明。

本发明提出了一种分布式数据库系统的跨节点查询优化方法，本方法通过构建多因素决策的模糊评估模型，用于对每个分片查询路径进行优化判决，并定义全局优化的代价函数，用于对全局查询路径进行自适应优化，达到满足全局查询总代价最低要求的目的。

总体来说，本方法包含三大阶段，各阶段名称及其主要完成功能为：

第一阶段：全局查询总代价定义阶段100，用于定义全局优化阶段所需要的参数；

第二阶段：局部优化阶段200，用于对每个分片查询路径进行优化判决；

第三阶段：全局优化阶段300，用于找出分片查询路径的最佳操作次序，包括使得代价函数最小。

参照附图2，为本发明提供的分布式数据库系统的跨节点查询优化方法实施例流程示意图。

每一阶段的详细步骤如下：

在第一阶段，即全局查询总代价定义阶段100中：

步骤S110，确定全局查询总代价C以及全局查询总代价最低要求C_min。

将全局查询总代价最低要求定义为查询时间误差估计t_e和查询响应时间t_r的加权和，即C_min＝w₁·t_e+w₂·t_r，其中t_e为查询时间误差估计，即全部网络时延及时钟漂移引起的查询时间误差之和的估计；t_r为查询响应时间，即从用户提交查询请求到收到完整的返回信息的平均时间，并有w₁+w₂＝1。

在第二阶段，即局部优化阶段200中：

步骤S210，进行查询分解，

即将查询问题(例如SQL语句)，转换成一个定义在全局关系上的关系代数表达式。

步骤S220，进行数据本地化，

即把定义在全局关系上的关系代数表达式具体化，落实到合适的(使尽可能做到本地化或近地化)片段上进行查询。检查本地是否有此数据库，如果本地有此数据库，则在本地执行查询；如果本地没有此数据库，则通过全局查询从而选择一台处理本查询最优化的节点。

步骤S230，进行多因素决策的模糊评估(无论查询结果是否在本地)，判定多个影响因素中对降低查询代价贡献最大的影响因素。

首先构建一个多因素决策的模糊评估模型，用于对共计N个分片查询路径进行优化判决；接着在查询分解和数据本地化后进行多因素决策模糊评估，得到评估结果，即对降低查询代价贡献最大的影响因素，作为在查询代价最小的数据库节点上进行局部优化的输入。

步骤S240，进行连接建立，

即在当前的分片查询路径中，根据对降低查询代价贡献最大的影响因素，查找到查询代价最小的数据库节点并与之建立连接进行查询，从而得到片段上的查询结果。

步骤S250，在与片段上的查询结果有关的各个数据库节点进行局部优化，

即将多因素决策的模糊评估的评估结果作为局部优化的输入，在与片段上的查询结果有关的各个数据库节点进行局部优化。局部优化的输出是在片段上的查询结果，即最优分片查询路径。

在第三阶段，即全局优化阶段300中：

步骤S310，进行Bp神经网络自适应优化，

其输入是在片段上的查询结果，即最优分片查询路径。由于全局查询总代价C表示的是实际操作中全局消耗的总代价，定义E(w)为全局优化代价函数，表示全局查询总代价误差。在应用中，理想情况是C可以无限逼近全局查询总代价最低要求C_min，即我们期望E(w)尽可能小，基于此，对上述全局优化代价函数E(w)采用BP神经网络求得其最小值。

步骤S320，进行全局优化并最终输出最优的全局查询路径。

从上述实施例可以看出，本发明提供的分布式数据库系统的跨节点查询优化方法的优点在于，通过对每个分片查询路径的优化，降低全局优化的计算负担，使得全局查询具有更快的查询速度，并通过定义全局优化代价函数使得查询总代价可控。

较佳的，参照附图4，为本发明提供的分布式数据库系统的跨节点查询优化方法实施例的步骤S230的进一步具体流程示意图。

所述进行多因素决策的模糊评估的步骤S230还可以进一步包括以下步骤：

步骤S231，定义每个分片查询路径中共有I个影响因素(如节点间网络时延、数据库尺度等)能够降低查询代价；

步骤S232，定义多因素决策的模糊评估模型如下：

假设F(x_I)为在I个影响因素共同作用下得到的查询代价函数，其中x_I为查询代价函数输入；

步骤S233，定义优化准则为：加权距离平方总和最小。因此定义其优化目标函数为：

$>min\left\{F\left(x_i\right)\right\}=u_i^2\underset{j=1}{\overset{n}{\Sigma }}{w}_j{(1-M_{ij})}^2+{(1-u_i)}^2\underset{j=1}{\overset{n}{\Sigma }}{w}_j{M_{ij}}^2$>

其中，u_i为第i(i≤I)个影响因素对降低查询代价的贡献，w_j为i(i≤I)个影响因素对应的初始权重，M_IN为I个影响因素和N个分片查询路径构成一个I*N矩阵并归一化后得到的矩阵，M_ij为归一化后的矩阵M_IN中的元素。

步骤S234，对步骤S233中定义的优化目标函数进行求解得到一组u_i，选取最大的u_i并判定对应的第i个影响因素对降低查询代价贡献最大；

步骤S235，得到多因素决策的模糊评估的评估结果，多因素决策的模糊评估的输出是i。

通过上述处理步骤，可以人为定义对降低查询代价有所贡献的I个影响因素，使得通过经验人为避免一些不重要的影响因素对总体计算的干扰。判断出对降低查询代价贡献最大的影响因素后，即可进一步排除其余影响因素对总体计算的干扰，从而逐步降低运算时间。

较佳的，参照附图5，为本发明提供的分布式数据库系统的跨节点查询优化方法实施例的步骤S310的进一步具体流程示意图。

所述进行Bp神经网络自适应优化的步骤S310还可以进一步包括以下步骤：

步骤S311，将全局优化代价函数定义为：

$>E\left(w\right)=\frac{1}{2}\underset{i=1}{\overset{I}{\Sigma }}{(d_i^w-y_i^w)}^2$>

其中，E(w)为全局优化代价函数，表示全局查询总代价误差；

w(w≤W)为全局查询结果中包含分片查询路径的个数；

i为局部优化阶段求得的多因素决策的模糊评估的结果，即第i个影响因素；

为分片查询路径w中第i个影响因素作用下的全局查询总代价理想值；

为分片查询路径w中第i个影响因素作用下的全局查询总代价实际输出值。

步骤S312，将BP神经网络设计为一个3层的前馈神经网络，第一层是输入单元，第二层称为隐含层，第三层称为输出层。X表示网络的输入向量，对应N个分片查询路径，w₁、w₂、w₃分别表示网络各层的连接权向量，F₁、F₂、F₃表示3层对应的激活函数。

则第一层神经元的输出为：O₁＝F₁(Xw₁)

第二层神经元的输出为：O₂＝F₂F₁(Xw₁)w₂

输出层神经元的输出为：O₃＝F₃(F₂F₁(Xw₁)w₂)w₃

其中激活函数均定义为sigmoid函数：

$>F=\frac{1}{1+e^x}$>

步骤S313，用梯度下降法对BP神经网络的各层的连接权向量进行求解并更新。

步骤S314，最终输出层的输出即为最优的全局查询路径，即加权后的分片查询路径。

通过上述处理步骤，可通过计算自适应的调整BP神经网络的各层的连接权向量，提高了全局查询的效率和可靠性。

需要特别指出的是，上述方法实施例中的各个步骤均可以相互交叉、替换、增加、删减，因此，这些合理的排列组合变换之于所述方法也应当属于本发明的保护范围，并且不应将本发明的保护范围局限在所述实施例之上。

本发明另一方面还提出了一种分布式数据库系统的跨节点查询优化系统400，实现了在分布式并行系统中进行查询时降低数据I/O次数和负载均衡的目的，参照附图3，为本发明提供的分布式数据库系统的跨节点查询优化系统400实施例模块示意图。

所述分布式数据库系统的跨节点查询优化系统400包括：

全局查询总代价最低要求模块410，用于在全局总代价定义确定全局查询总代价以及全局查询总代价最低要求；

查询分解及本地化模块420，用于将查询问题落在合适的片段上；

多因素决策的模糊评估模块430，用于通过构建多因素决策的模糊评估模型，判定多个影响因素中对降低查询代价贡献最大的影响因素；

连接建立模块440，用于在当前的分片查询路径中，根据对降低查询代价贡献最大的影响因素，查找到查询代价最小的数据库节点并与之建立连接进行查询；从而得到片段上的查询结果；

局部优化模块450，用于在与片段上的查询结果有关的各个数据库节点进行局部优化；

Bp神经网络自适应优化模块460，用于定义全局优化代价函数，并采用Bp神经网络求得全局优化代价函数的最小值，使得输出满足全局查询总代价逼近全局查询总代价最低要求，其中，Bp神经网络的输入为片段上的查询结果；

全局优化模块470，用于进行全局优化并最终输出最优的全局查询路径。

从上述实施例可以看出，本发明提供的分布式数据库系统的跨节点查询优化系统400，其优点在于，通过对每个分片查询路径的优化，降低全局优化的计算负担，使得全局查询具有更快的查询速度，并通过定义全局优化代价函数使得查询总代价可控。

较佳的，所述全局查询总代价最低要求模块410，还可用于将全局查询总代价最低要求定义为查询时间误差估计和查询响应时间的加权和，即C_min＝w₁·t_e+w₂·t_r，其中，C_min是指全局查询总代价最低要求，t_e是指查询时间误差估计，其为全部网络时延及时钟漂移引起的查询时间误差之和的估计，t_r是指查询响应时间，其是从用户提交查询请求到收到完整的返回信息的平均时间，并有w₁+w₂＝1。

较佳的，参照附图6，为本发明提供的分布式数据库系统的跨节点查询优化系统400实施例的模块430的进一步具体结构示意图。

所述多因素决策的模糊评估模块430，还可以进一步包括以下模块：

模型构建模块431，用于构建多因素决策的模糊评估模型；

优化判决模块432，用于对每个分片查询路径进行优化判决；

局部优化输入模块433，用于将评估结果作为局部优化的输入。

进一步的，所述模型构建模块431，还可以进一步包括以下模块：

影响因素定义模块4311，用于定义每个分片查询路径中共有I个影响因素能够降低查询代价；

查询代价函数定义模块4312，用于定义在I个影响因素共同作用下得到的查询代价函数为F(x_I)，其中x_I为函数输入；

优化目标函数定义模块4313，用于定义其优化目标函数，即min{F(x_i)}其用于判定对降低查询代价贡献最大的影响因素。

进一步的，所述优化判决模块432，还可以进一步包括以下模块：

求解模块4321，用于对min{F(x_i)}进行求解得到一组u_i，其中u_i为优化目标函数解析式中的一个参数，其表示第i(i≤I)个影响因素对降低查询代价的贡献；

影响因素判定模块4322，用于选取其中最大的u_i，判定对应第i个影响因素对降低查询代价贡献最大；

查询连接模块4323，用于查找当前的分片查询路径中，在第i个影响因素作用下查询代价最小的数据库节点并与之建立连接进行查询。

通过上述处理步骤，可以人为定义对降低查询代价有所贡献的I个影响因素，使得通过经验人为避免一些不重要的影响因素对总体计算的干扰。判断出对降低查询代价贡献最大的影响因素后，即可进一步排除其余影响因素对总体计算的干扰，从而逐步降低运算时间。

较佳的，Bp神经网络自适应优化模块，还可以进一步包括以下模块：

Bp神经网络设计模块，用于将Bp神经网络设计为一个3层的前馈神经网络，各层均有连接权向量；

各层参数求解模块，用于利用梯度下降法对BP神经网络的各层的连接权向量进行求解并更新。

通过上述处理步骤，可通过计算自适应的调整BP神经网络的各层的连接权向量，提高了全局查询的效率和可靠性。

下面参照附图2，简要介绍采用本发明提供的分布式数据库系统的跨节点查询优化系统400进行分布式数据库系统的跨节点查询优化方法：

所述分布式数据库系统的跨节点查询优化方法，包括：

在第一阶段，即全局查询总代价定义阶段100中：

步骤S110，全局查询总代价最低要求模块410确定全局查询总代价C以及全局查询总代价最低要求C_min。

在第二阶段，即局部优化阶段200中：

步骤S210，查询分解及本地化模块420进行查询分解，即将查询问题(例如SQL语句)，转换成一个定义在全局关系上的关系代数表达式。

步骤S220，查询分解及本地化模块420进行数据本地化，即把定义在全局关系上的关系代数表达式具体化，落实到合适的(使尽可能做到本地化或近地化)片段上进行查询。

步骤S230，多因素决策的模糊评估模块430进行多因素决策的模糊评估(无论查询结果是否在本地)，判定多个影响因素中对降低查询代价贡献最大的影响因素。

步骤S240，连接建立模块440进行连接建立，即在当前的分片查询路径中，根据对降低查询代价贡献最大的影响因素，查找到查询代价最小的数据库节点并与之建立连接进行查询，从而得到片段上的查询结果。

步骤S250，局部优化模块450在与片段上的查询结果有关的各个数据库节点进行局部优化，即将多因素决策的模糊评估的评估结果作为局部优化的输入，由拥有与查询有关的片段的各个站点进行局部优化。局部优化的输出是在片段上的查询结果，即最优分片查询路径

在第三阶段，即全局优化阶段300中：

步骤S310，Bp神经网络自适应优化模块460进行Bp神经网络自适应优化，其输入是在片段上的查询结果，即最优分片查询路径。定义全局优化代价函数并采用BP神经网络求得其最小值。

步骤S320，全局优化模块470进行全局优化并最终输出最优的全局查询路径。

所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本公开的范围(包括权利要求)被限于这些例子；在本发明的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，并存在如上所述的本发明的不同方面的许多其它变化，为了简明它们没有在细节中提供。因此，凡在本发明的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本发明的保护范围之内。