一种改进的数据库查询优化算法

申华

摘要：数据库查询优化技术对提高数据库的查询效率，增强数据库性能有重要作用。针对大型数据库中多表连接查询效率低的问题，提出了一种基于粒子群算法的改进查询优化算法。针对多表连接查询的特征，对粒子采用树形编码的方式，并提出了一种计算数据库查询执行代价的模型。实验表明，使用粒子群算法优化后的查询策略比原始查询策略的查询执行代价低，有效提高了系统的查询效率。

关键词：查询优化；粒子群算法；执行代价估计；树形编码

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）25-5806-04

An Improved Database Query Optimization Algorithm

SHEN Hua

（South China Institute of Software Engineering，Guangzhou University， Guangzhou 510990，China）

Abstract：Database query optimization techniques plays an important role in the query efficiency of the database and enhancement of database performance .Aiming at the problem of Low efficiency in a large database of multi-table join query， this thesis proposes an improved query optimization algorithm based on particle swarm optimization algorithm. According to the characteristics of the multi-table join query， using tree coding method to theparticle， and put forward the calculation of database query execution cost model. Experiments show that use of particle swarm algorithm optimized query strategy has lower cost than the original query strategy， the improved model effectively improve the query efficiency of the system.

Key words：query optimization； particle swarm optimization； execution cost estimation； tree encoding

1 概述

数据库查询优化技术致力于研究如何高效、迅速的从大型数据库中检索出需要的信息。大型数据库中数据分别被存在不同的表中，查询时经常需要进行多表连接查询，当表的数量很多的时候查询的代价会呈指数增长[1]。因此研究如何降低多表连接查询时的执行代价，是提高系统性能及查询效率的关键。

目前对查询优化技术的改进主要有两个方向：第一，使用确定算法改进，如：动态规划[2]、贪心算法[3]等。第二，使用随机算法，该算法是在解空间内通过随机方法求得近似最优解，如：遗传算法[4-5]、粒子群算法[6]等。当数据库表文件较少时，使用确定性算法是较好的选择，而针对大型数据库，表文件非常多时，随机算法效率更高更有优势。

为提高多表连接查询的效率，该文使用粒子群算法对数据库的查询策略进行优化。使用树形编码的方法对多连接查询问题进行编码，种群中一个粒子表示一种表的连接顺序，设计了多表查询的执行代价模型作为适应度函数，然后进行迭代计算得到优化后的解。实验表明优化后的查询执行代价有显著下降。

2 查询优化技术概述

查询优化（Query Optimization）是指在数据库执行查询操作的过程中使系统执行代价及时间消耗尽可能小，从而提高查询操作的执行效率[7-9]。一个复杂的查询一般包含多种可行的查询策略，通常用户无法直接准确的写出最优的查询语句，使用查询优化方法在多种可行的查询策略中选取出最优的策略，对提高查询效率有重要的意义。

多连接查询（Multi-Join Query，MJQ）是将数据库中多张表按一定的规则连接而成的关系表达式。多表连接查询因关系数据库的广泛应用而成为查询优化技术研究的重点。

3 查询执行代价计算

查询优化首先需要生成一个和给定查询语句查询结果相同的解空间，使用语法树可以方便的表示出数据库中表的连接顺序，该文使用左线性语法树来生成解空间，当有n个连接操作时，所生成的解空间有（n+1） ！种可行解。

解空间确定好后，需准确的计算出解空间中每个可行解的执行代价，该文提出的代价估计如下：

假设多连接查询中共有n个关系，其语法树的内部结点个数为[ti]，则查询的执行代价即为语法树内部结点个数的总和。

即首先计算每个粒子的执行代价，再对所求得的值取倒数即为适应度函数值。当粒子的执行代价越小时，适应度越高。

4.3 改进的查询优化算法的实现步骤

1） 对原始查询语句进行编码。

2） 初始化种群，即在问题的解空间中，随机给粒子赋予初始值。

3） 取执行代价的倒数作为适应度函数。

4） 使用粒子群算法进行迭代寻优。

5） 终止条件。当迭代达到设定的代数，或者达到设置的精度要求则结束算法。

5 实验结果及分析

5.1 实验数据库概述

本文从一个大型的工程数据库中获取部分数据进行实验，该数据库中，为了查询包含不同信息的报表，而这最多需要对5个关系表进行连接查询。这5个关系表为h_beian（合同备案表）、h_gaikuang（工程概况表）、h_tezheng（工程特征表）、h_shouche（《手册》表）、h_jiancha（履约检查表）。

假设一个查询语句如下：

由图3可以看出，适应度值随着迭代次数的增加呈现上升趋势且变化趋于平缓，说明基于粒子群算法的查询优化算法收敛。经过优化后执行代价为868的粒子所表示的查询语句，即为所得的解。

由实验可看出经过粒子群算法优化后的查询语句比原始查询语句的执行代价有了显著的下降，随着表的数目及表内数据的增加，经过优化后的效果会更加明显。

6 总结

多连接查询优化问题是一个NP问题，随着数据库存储的信息量越来越巨大，，数据库中数据表的数量和关系元组的数量也越来越多，查询优化技术具有重大的研究意义。该文分析了多连接查询优化问题，并结合多连接的特点，使用粒子群算法改进了查询方法，并且结合执行代价估计的统计信息和连接结果的代价估计方法提出了代价估计模型。最后在实际的工程数据库中使用改进查询优化算法进行了实验，实验结果表明改进的算法降低了数据库查询的执行代价，验证了算法的有效性。

参考文献：

[1] 郭丽英.数据库中查询重写及基于遗传算法的多连接查询优化研究[D].沈阳：东北大学，2008：23-25.

[2] 王军祥.动态规划算法原理及应用研究[J].电脑知识与技术，2006，36：38-41.

[3] 董军军.动态规划算法和贪心算法的比较与分析[J].软件导刊，2008，2：81-83.

[4] 金贵.算法导论[M].北京：机械工业出版社，2006：126-352.

[5] 曹阳，方强.基于遗传算法的多连接表达式并行查询优化[J].软件学报，2002，13（2）：250-257.

[6] SHI Y，EBERHART R C.Particle swarm optimization：developments，applications and resource[C].Proceedings of Congress on Evolutionary Computation，Piscatawary，NJ，USA：IEEE press，2001，1：81-86.

[7] Zheng X，Chen H，Wu Z，et al.Dynamie query optimization approach for semantic database grid[J].Journal of Computer Science and Technology，2006，（4）：67-73.

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

[9] CHEN M，YU P.Optimization of parallel execution for multi-join queries[J].IEEE Trans Kowledge and Data Eng，1996，8（3）：416- 428.

[10] 赵晓东.基于遗传算法的分布式数据库多连接查询优化的研究[D].长春：长春理工大学，2005.

5） 终止条件。当迭代达到设定的代数，或者达到设置的精度要求则结束算法。

5 实验结果及分析

5.1 实验数据库概述

本文从一个大型的工程数据库中获取部分数据进行实验，该数据库中，为了查询包含不同信息的报表，而这最多需要对5个关系表进行连接查询。这5个关系表为h_beian（合同备案表）、h_gaikuang（工程概况表）、h_tezheng（工程特征表）、h_shouche（《手册》表）、h_jiancha（履约检查表）。

假设一个查询语句如下：

由图3可以看出，适应度值随着迭代次数的增加呈现上升趋势且变化趋于平缓，说明基于粒子群算法的查询优化算法收敛。经过优化后执行代价为868的粒子所表示的查询语句，即为所得的解。

由实验可看出经过粒子群算法优化后的查询语句比原始查询语句的执行代价有了显著的下降，随着表的数目及表内数据的增加，经过优化后的效果会更加明显。

6 总结

多连接查询优化问题是一个NP问题，随着数据库存储的信息量越来越巨大，，数据库中数据表的数量和关系元组的数量也越来越多，查询优化技术具有重大的研究意义。该文分析了多连接查询优化问题，并结合多连接的特点，使用粒子群算法改进了查询方法，并且结合执行代价估计的统计信息和连接结果的代价估计方法提出了代价估计模型。最后在实际的工程数据库中使用改进查询优化算法进行了实验，实验结果表明改进的算法降低了数据库查询的执行代价，验证了算法的有效性。

参考文献：

[1] 郭丽英.数据库中查询重写及基于遗传算法的多连接查询优化研究[D].沈阳：东北大学，2008：23-25.

[2] 王军祥.动态规划算法原理及应用研究[J].电脑知识与技术，2006，36：38-41.

[3] 董军军.动态规划算法和贪心算法的比较与分析[J].软件导刊，2008，2：81-83.

[4] 金贵.算法导论[M].北京：机械工业出版社，2006：126-352.

[5] 曹阳，方强.基于遗传算法的多连接表达式并行查询优化[J].软件学报，2002，13（2）：250-257.

[6] SHI Y，EBERHART R C.Particle swarm optimization：developments，applications and resource[C].Proceedings of Congress on Evolutionary Computation，Piscatawary，NJ，USA：IEEE press，2001，1：81-86.

[7] Zheng X，Chen H，Wu Z，et al.Dynamie query optimization approach for semantic database grid[J].Journal of Computer Science and Technology，2006，（4）：67-73.

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

[9] CHEN M，YU P.Optimization of parallel execution for multi-join queries[J].IEEE Trans Kowledge and Data Eng，1996，8（3）：416- 428.

[10] 赵晓东.基于遗传算法的分布式数据库多连接查询优化的研究[D].长春：长春理工大学，2005.

5） 终止条件。当迭代达到设定的代数，或者达到设置的精度要求则结束算法。

5 实验结果及分析

5.1 实验数据库概述

本文从一个大型的工程数据库中获取部分数据进行实验，该数据库中，为了查询包含不同信息的报表，而这最多需要对5个关系表进行连接查询。这5个关系表为h_beian（合同备案表）、h_gaikuang（工程概况表）、h_tezheng（工程特征表）、h_shouche（《手册》表）、h_jiancha（履约检查表）。

假设一个查询语句如下：

由图3可以看出，适应度值随着迭代次数的增加呈现上升趋势且变化趋于平缓，说明基于粒子群算法的查询优化算法收敛。经过优化后执行代价为868的粒子所表示的查询语句，即为所得的解。

由实验可看出经过粒子群算法优化后的查询语句比原始查询语句的执行代价有了显著的下降，随着表的数目及表内数据的增加，经过优化后的效果会更加明显。

6 总结

多连接查询优化问题是一个NP问题，随着数据库存储的信息量越来越巨大，，数据库中数据表的数量和关系元组的数量也越来越多，查询优化技术具有重大的研究意义。该文分析了多连接查询优化问题，并结合多连接的特点，使用粒子群算法改进了查询方法，并且结合执行代价估计的统计信息和连接结果的代价估计方法提出了代价估计模型。最后在实际的工程数据库中使用改进查询优化算法进行了实验，实验结果表明改进的算法降低了数据库查询的执行代价，验证了算法的有效性。

参考文献：

[1] 郭丽英.数据库中查询重写及基于遗传算法的多连接查询优化研究[D].沈阳：东北大学，2008：23-25.

[2] 王军祥.动态规划算法原理及应用研究[J].电脑知识与技术，2006，36：38-41.

[3] 董军军.动态规划算法和贪心算法的比较与分析[J].软件导刊，2008，2：81-83.

[4] 金贵.算法导论[M].北京：机械工业出版社，2006：126-352.

[5] 曹阳，方强.基于遗传算法的多连接表达式并行查询优化[J].软件学报，2002，13（2）：250-257.

[6] SHI Y，EBERHART R C.Particle swarm optimization：developments，applications and resource[C].Proceedings of Congress on Evolutionary Computation，Piscatawary，NJ，USA：IEEE press，2001，1：81-86.

[7] Zheng X，Chen H，Wu Z，et al.Dynamie query optimization approach for semantic database grid[J].Journal of Computer Science and Technology，2006，（4）：67-73.

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

[9] CHEN M，YU P.Optimization of parallel execution for multi-join queries[J].IEEE Trans Kowledge and Data Eng，1996，8（3）：416- 428.

[10] 赵晓东.基于遗传算法的分布式数据库多连接查询优化的研究[D].长春：长春理工大学，2005.