一種改進(jìn)的數(shù)據(jù)庫查詢優(yōu)化算法

申華

摘要：數(shù)據(jù)庫查詢優(yōu)化技術(shù)對(duì)提高數(shù)據(jù)庫的查詢效率，增強(qiáng)數(shù)據(jù)庫性能有重要作用。針對(duì)大型數(shù)據(jù)庫中多表連接查詢效率低的問題，提出了一種基于粒子群算法的改進(jìn)查詢優(yōu)化算法。針對(duì)多表連接查詢的特征，對(duì)粒子采用樹形編碼的方式，并提出了一種計(jì)算數(shù)據(jù)庫查詢執(zhí)行代價(jià)的模型。實(shí)驗(yàn)表明，使用粒子群算法優(yōu)化后的查詢策略比原始查詢策略的查詢執(zhí)行代價(jià)低，有效提高了系統(tǒng)的查詢效率。

關(guān)鍵詞：查詢優(yōu)化；粒子群算法；執(zhí)行代價(jià)估計(jì)；樹形編碼

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 概述

數(shù)據(jù)庫查詢優(yōu)化技術(shù)致力于研究如何高效、迅速的從大型數(shù)據(jù)庫中檢索出需要的信息。大型數(shù)據(jù)庫中數(shù)據(jù)分別被存在不同的表中，查詢時(shí)經(jīng)常需要進(jìn)行多表連接查詢，當(dāng)表的數(shù)量很多的時(shí)候查詢的代價(jià)會(huì)呈指數(shù)增長(zhǎng)[1]。因此研究如何降低多表連接查詢時(shí)的執(zhí)行代價(jià)，是提高系統(tǒng)性能及查詢效率的關(guān)鍵。

目前對(duì)查詢優(yōu)化技術(shù)的改進(jìn)主要有兩個(gè)方向：第一，使用確定算法改進(jìn)，如：動(dòng)態(tài)規(guī)劃[2]、貪心算法[3]等。第二，使用隨機(jī)算法，該算法是在解空間內(nèi)通過隨機(jī)方法求得近似最優(yōu)解，如：遺傳算法[4-5]、粒子群算法[6]等。當(dāng)數(shù)據(jù)庫表文件較少時(shí)，使用確定性算法是較好的選擇，而針對(duì)大型數(shù)據(jù)庫，表文件非常多時(shí)，隨機(jī)算法效率更高更有優(yōu)勢(shì)。

為提高多表連接查詢的效率，該文使用粒子群算法對(duì)數(shù)據(jù)庫的查詢策略進(jìn)行優(yōu)化。使用樹形編碼的方法對(duì)多連接查詢問題進(jìn)行編碼，種群中一個(gè)粒子表示一種表的連接順序，設(shè)計(jì)了多表查詢的執(zhí)行代價(jià)模型作為適應(yīng)度函數(shù)，然后進(jìn)行迭代計(jì)算得到優(yōu)化后的解。實(shí)驗(yàn)表明優(yōu)化后的查詢執(zhí)行代價(jià)有顯著下降。

2 查詢優(yōu)化技術(shù)概述

查詢優(yōu)化（Query Optimization）是指在數(shù)據(jù)庫執(zhí)行查詢操作的過程中使系統(tǒng)執(zhí)行代價(jià)及時(shí)間消耗盡可能小，從而提高查詢操作的執(zhí)行效率[7-9]。一個(gè)復(fù)雜的查詢一般包含多種可行的查詢策略，通常用戶無法直接準(zhǔn)確的寫出最優(yōu)的查詢語句，使用查詢優(yōu)化方法在多種可行的查詢策略中選取出最優(yōu)的策略，對(duì)提高查詢效率有重要的意義。

多連接查詢（Multi-Join Query，MJQ）是將數(shù)據(jù)庫中多張表按一定的規(guī)則連接而成的關(guān)系表達(dá)式。多表連接查詢因關(guān)系數(shù)據(jù)庫的廣泛應(yīng)用而成為查詢優(yōu)化技術(shù)研究的重點(diǎn)。

3 查詢執(zhí)行代價(jià)計(jì)算

查詢優(yōu)化首先需要生成一個(gè)和給定查詢語句查詢結(jié)果相同的解空間，使用語法樹可以方便的表示出數(shù)據(jù)庫中表的連接順序，該文使用左線性語法樹來生成解空間，當(dāng)有n個(gè)連接操作時(shí)，所生成的解空間有（n+1） ！種可行解。

解空間確定好后，需準(zhǔn)確的計(jì)算出解空間中每個(gè)可行解的執(zhí)行代價(jià)，該文提出的代價(jià)估計(jì)如下：

假設(shè)多連接查詢中共有n個(gè)關(guān)系，其語法樹的內(nèi)部結(jié)點(diǎn)個(gè)數(shù)為[ti]，則查詢的執(zhí)行代價(jià)即為語法樹內(nèi)部結(jié)點(diǎn)個(gè)數(shù)的總和。

即首先計(jì)算每個(gè)粒子的執(zhí)行代價(jià)，再對(duì)所求得的值取倒數(shù)即為適應(yīng)度函數(shù)值。當(dāng)粒子的執(zhí)行代價(jià)越小時(shí)，適應(yīng)度越高。

4.3 改進(jìn)的查詢優(yōu)化算法的實(shí)現(xiàn)步驟

1） 對(duì)原始查詢語句進(jìn)行編碼。

2） 初始化種群，即在問題的解空間中，隨機(jī)給粒子賦予初始值。

3） 取執(zhí)行代價(jià)的倒數(shù)作為適應(yīng)度函數(shù)。

4） 使用粒子群算法進(jìn)行迭代尋優(yōu)。

5） 終止條件。當(dāng)?shù)_(dá)到設(shè)定的代數(shù)，或者達(dá)到設(shè)置的精度要求則結(jié)束算法。

5 實(shí)驗(yàn)結(jié)果及分析

5.1 實(shí)驗(yàn)數(shù)據(jù)庫概述

本文從一個(gè)大型的工程數(shù)據(jù)庫中獲取部分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)庫中，為了查詢包含不同信息的報(bào)表，而這最多需要對(duì)5個(gè)關(guān)系表進(jìn)行連接查詢。這5個(gè)關(guān)系表為h_beian（合同備案表）、h_gaikuang（工程概況表）、h_tezheng（工程特征表）、h_shouche（《手冊(cè)》表）、h_jiancha（履約檢查表）。

假設(shè)一個(gè)查詢語句如下：

由圖3可以看出，適應(yīng)度值隨著迭代次數(shù)的增加呈現(xiàn)上升趨勢(shì)且變化趨于平緩，說明基于粒子群算法的查詢優(yōu)化算法收斂。經(jīng)過優(yōu)化后執(zhí)行代價(jià)為868的粒子所表示的查詢語句，即為所得的解。

由實(shí)驗(yàn)可看出經(jīng)過粒子群算法優(yōu)化后的查詢語句比原始查詢語句的執(zhí)行代價(jià)有了顯著的下降，隨著表的數(shù)目及表內(nèi)數(shù)據(jù)的增加，經(jīng)過優(yōu)化后的效果會(huì)更加明顯。

6 總結(jié)

多連接查詢優(yōu)化問題是一個(gè)NP問題，隨著數(shù)據(jù)庫存儲(chǔ)的信息量越來越巨大，，數(shù)據(jù)庫中數(shù)據(jù)表的數(shù)量和關(guān)系元組的數(shù)量也越來越多，查詢優(yōu)化技術(shù)具有重大的研究意義。該文分析了多連接查詢優(yōu)化問題，并結(jié)合多連接的特點(diǎn)，使用粒子群算法改進(jìn)了查詢方法，并且結(jié)合執(zhí)行代價(jià)估計(jì)的統(tǒng)計(jì)信息和連接結(jié)果的代價(jià)估計(jì)方法提出了代價(jià)估計(jì)模型。最后在實(shí)際的工程數(shù)據(jù)庫中使用改進(jìn)查詢優(yōu)化算法進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法降低了數(shù)據(jù)庫查詢的執(zhí)行代價(jià)，驗(yàn)證了算法的有效性。

參考文獻(xiàn)：

[1] 郭麗英.數(shù)據(jù)庫中查詢重寫及基于遺傳算法的多連接查詢優(yōu)化研究[D].沈陽：東北大學(xué)，2008：23-25.

[2] 王軍祥.動(dòng)態(tài)規(guī)劃算法原理及應(yīng)用研究[J].電腦知識(shí)與技術(shù)，2006，36：38-41.

[3] 董軍軍.動(dòng)態(tài)規(guī)劃算法和貪心算法的比較與分析[J].軟件導(dǎo)刊，2008，2：81-83.

[4] 金貴.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006：126-352.

[5] 曹陽，方強(qiáng).基于遺傳算法的多連接表達(dá)式并行查詢優(yōu)化[J].軟件學(xué)報(bào)，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] 魏士偉，黃文明，康業(yè)娜，等.分布式數(shù)據(jù)庫中基于半連接的查詢優(yōu)化算法研究明[J].計(jì)算機(jī)應(yīng)用，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] 趙曉東.基于遺傳算法的分布式數(shù)據(jù)庫多連接查詢優(yōu)化的研究[D].長(zhǎng)春：長(zhǎng)春理工大學(xué)，2005.

5） 終止條件。當(dāng)?shù)_(dá)到設(shè)定的代數(shù)，或者達(dá)到設(shè)置的精度要求則結(jié)束算法。

5 實(shí)驗(yàn)結(jié)果及分析

5.1 實(shí)驗(yàn)數(shù)據(jù)庫概述

本文從一個(gè)大型的工程數(shù)據(jù)庫中獲取部分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)庫中，為了查詢包含不同信息的報(bào)表，而這最多需要對(duì)5個(gè)關(guān)系表進(jìn)行連接查詢。這5個(gè)關(guān)系表為h_beian（合同備案表）、h_gaikuang（工程概況表）、h_tezheng（工程特征表）、h_shouche（《手冊(cè)》表）、h_jiancha（履約檢查表）。

假設(shè)一個(gè)查詢語句如下：

由圖3可以看出，適應(yīng)度值隨著迭代次數(shù)的增加呈現(xiàn)上升趨勢(shì)且變化趨于平緩，說明基于粒子群算法的查詢優(yōu)化算法收斂。經(jīng)過優(yōu)化后執(zhí)行代價(jià)為868的粒子所表示的查詢語句，即為所得的解。

由實(shí)驗(yàn)可看出經(jīng)過粒子群算法優(yōu)化后的查詢語句比原始查詢語句的執(zhí)行代價(jià)有了顯著的下降，隨著表的數(shù)目及表內(nèi)數(shù)據(jù)的增加，經(jīng)過優(yōu)化后的效果會(huì)更加明顯。

6 總結(jié)

多連接查詢優(yōu)化問題是一個(gè)NP問題，隨著數(shù)據(jù)庫存儲(chǔ)的信息量越來越巨大，，數(shù)據(jù)庫中數(shù)據(jù)表的數(shù)量和關(guān)系元組的數(shù)量也越來越多，查詢優(yōu)化技術(shù)具有重大的研究意義。該文分析了多連接查詢優(yōu)化問題，并結(jié)合多連接的特點(diǎn)，使用粒子群算法改進(jìn)了查詢方法，并且結(jié)合執(zhí)行代價(jià)估計(jì)的統(tǒng)計(jì)信息和連接結(jié)果的代價(jià)估計(jì)方法提出了代價(jià)估計(jì)模型。最后在實(shí)際的工程數(shù)據(jù)庫中使用改進(jìn)查詢優(yōu)化算法進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法降低了數(shù)據(jù)庫查詢的執(zhí)行代價(jià)，驗(yàn)證了算法的有效性。

參考文獻(xiàn)：

[1] 郭麗英.數(shù)據(jù)庫中查詢重寫及基于遺傳算法的多連接查詢優(yōu)化研究[D].沈陽：東北大學(xué)，2008：23-25.

[2] 王軍祥.動(dòng)態(tài)規(guī)劃算法原理及應(yīng)用研究[J].電腦知識(shí)與技術(shù)，2006，36：38-41.

[3] 董軍軍.動(dòng)態(tài)規(guī)劃算法和貪心算法的比較與分析[J].軟件導(dǎo)刊，2008，2：81-83.

[4] 金貴.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006：126-352.

[5] 曹陽，方強(qiáng).基于遺傳算法的多連接表達(dá)式并行查詢優(yōu)化[J].軟件學(xué)報(bào)，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] 魏士偉，黃文明，康業(yè)娜，等.分布式數(shù)據(jù)庫中基于半連接的查詢優(yōu)化算法研究明[J].計(jì)算機(jī)應(yīng)用，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] 趙曉東.基于遺傳算法的分布式數(shù)據(jù)庫多連接查詢優(yōu)化的研究[D].長(zhǎng)春：長(zhǎng)春理工大學(xué)，2005.

5） 終止條件。當(dāng)?shù)_(dá)到設(shè)定的代數(shù)，或者達(dá)到設(shè)置的精度要求則結(jié)束算法。

5 實(shí)驗(yàn)結(jié)果及分析

5.1 實(shí)驗(yàn)數(shù)據(jù)庫概述

本文從一個(gè)大型的工程數(shù)據(jù)庫中獲取部分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)庫中，為了查詢包含不同信息的報(bào)表，而這最多需要對(duì)5個(gè)關(guān)系表進(jìn)行連接查詢。這5個(gè)關(guān)系表為h_beian（合同備案表）、h_gaikuang（工程概況表）、h_tezheng（工程特征表）、h_shouche（《手冊(cè)》表）、h_jiancha（履約檢查表）。

假設(shè)一個(gè)查詢語句如下：

由圖3可以看出，適應(yīng)度值隨著迭代次數(shù)的增加呈現(xiàn)上升趨勢(shì)且變化趨于平緩，說明基于粒子群算法的查詢優(yōu)化算法收斂。經(jīng)過優(yōu)化后執(zhí)行代價(jià)為868的粒子所表示的查詢語句，即為所得的解。

由實(shí)驗(yàn)可看出經(jīng)過粒子群算法優(yōu)化后的查詢語句比原始查詢語句的執(zhí)行代價(jià)有了顯著的下降，隨著表的數(shù)目及表內(nèi)數(shù)據(jù)的增加，經(jīng)過優(yōu)化后的效果會(huì)更加明顯。

6 總結(jié)

多連接查詢優(yōu)化問題是一個(gè)NP問題，隨著數(shù)據(jù)庫存儲(chǔ)的信息量越來越巨大，，數(shù)據(jù)庫中數(shù)據(jù)表的數(shù)量和關(guān)系元組的數(shù)量也越來越多，查詢優(yōu)化技術(shù)具有重大的研究意義。該文分析了多連接查詢優(yōu)化問題，并結(jié)合多連接的特點(diǎn)，使用粒子群算法改進(jìn)了查詢方法，并且結(jié)合執(zhí)行代價(jià)估計(jì)的統(tǒng)計(jì)信息和連接結(jié)果的代價(jià)估計(jì)方法提出了代價(jià)估計(jì)模型。最后在實(shí)際的工程數(shù)據(jù)庫中使用改進(jìn)查詢優(yōu)化算法進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法降低了數(shù)據(jù)庫查詢的執(zhí)行代價(jià)，驗(yàn)證了算法的有效性。

參考文獻(xiàn)：

[1] 郭麗英.數(shù)據(jù)庫中查詢重寫及基于遺傳算法的多連接查詢優(yōu)化研究[D].沈陽：東北大學(xué)，2008：23-25.

[2] 王軍祥.動(dòng)態(tài)規(guī)劃算法原理及應(yīng)用研究[J].電腦知識(shí)與技術(shù)，2006，36：38-41.

[3] 董軍軍.動(dòng)態(tài)規(guī)劃算法和貪心算法的比較與分析[J].軟件導(dǎo)刊，2008，2：81-83.

[4] 金貴.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006：126-352.

[5] 曹陽，方強(qiáng).基于遺傳算法的多連接表達(dá)式并行查詢優(yōu)化[J].軟件學(xué)報(bào)，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] 魏士偉，黃文明，康業(yè)娜，等.分布式數(shù)據(jù)庫中基于半連接的查詢優(yōu)化算法研究明[J].計(jì)算機(jī)應(yīng)用，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] 趙曉東.基于遺傳算法的分布式數(shù)據(jù)庫多連接查詢優(yōu)化的研究[D].長(zhǎng)春：長(zhǎng)春理工大學(xué)，2005.