數(shù)據(jù)庫查詢優(yōu)化算法淺析

【摘 要】數(shù)據(jù)庫系統(tǒng)在實際工作中應用非常廣泛，對數(shù)據(jù)庫進行查詢優(yōu)化對推動計算機技術的發(fā)展具有十分重要的意義。并行數(shù)據(jù)庫查詢優(yōu)化的研究主要圍繞具有多個JOIN操作的復雜關系數(shù)據(jù)庫查詢的優(yōu)化問題進行，本文主要對并行數(shù)據(jù)庫查詢優(yōu)化技術進行探索。

【關鍵詞】查詢優(yōu)化；并行數(shù)據(jù)庫；語義查詢；機群

1 引言

并行數(shù)據(jù)庫查詢優(yōu)化主要圍繞具有多個JOIN 操作的復雜關系數(shù)據(jù)庫查詢（簡稱MJ查詢）的優(yōu)化問題進行研究。1990年，Schneider等研究了查詢樹模型，提出了左線性樹（Left-Deep Trees）、右線性樹（RIGHT-Deep Trees）和濃密樹（Bushy Trees）的概念。一個MJ查詢可以表示為一個查詢樹T=（V，E），其中V是結點集合，E是邊集合。每個葉子結點表示一個關系，每個內(nèi)結點表示一個JOIN操作，同時表示這個JOIN操作的結果關系，每條邊表示一個JOIN操作，JOIN謂詞也可以由邊來表示，即MJ查詢的查詢樹是一個二叉樹。查詢樹分為三類左線性樹、右線性樹和濃密樹。

語義查詢優(yōu)化技術，將一個查詢變換成一個或數(shù)個語義等價的查詢，進而尋找并執(zhí)行這些等價查詢中具有較好實現(xiàn)策略的一個；基于遺傳算法的并行優(yōu)化算法主要是基于機群并行數(shù)據(jù)庫中關系存儲的選擇、多連接查詢優(yōu)化和查詢處理等關鍵技術。

2 左線性樹查詢優(yōu)化算法（簡稱LDT算法）

LDT方法把兩個JOIN關系分為內(nèi)關系和外關系，把HASH-JOIN分為BUILD和PROBE兩個基本操作，BUILD操作掃描內(nèi)關系，建立HASH表；PROBE操作掃描外關系，搜索匹配HASH表，完成JOIN操作。具體算法如下：

（1）搜索給定MJ查詢的左線性樹空間，選擇具有最小響應時間的優(yōu)化左線性樹T；

（2）由T產(chǎn)生數(shù)據(jù)相關圖DG；

（3）根據(jù)DG產(chǎn)生優(yōu)化并行查詢執(zhí)行計劃P；

（4）運行優(yōu)化查詢計劃P。

3 右線性樹的查詢優(yōu)化算法

由于MJ查詢的左線性樹優(yōu)化并行查詢算法最多只允許兩個JOIN操作并行執(zhí)行，存在明顯局限性。為此，Schneider等研究了基于右線性樹的MJ查詢優(yōu)化問題，并給出了基于右線性樹的查詢化化算法（簡稱RDT算法）。該算法類似于LDT算法，RDT算法產(chǎn)生的查詢執(zhí)行計劃具有相當高的并行性，所以N個JOIN操作皆可并行執(zhí)行。

該算法基本思想是：在BUILD階段，每個JOIN關系被分成兩部分，一部分進入內(nèi)存，建立HASH表，另一部分留駐外存，等以后處理；在PROBE階段，每個JOIN操作的結果也被分成兩部分，一部分直接用來進行下一個JOIN操作的PROBE處理，另一部分存入外存，等以后處理。

4 基于濃密樹的查詢優(yōu)化算法

濃密樹GBT（General-Bushy-Tree）的MJ查詢優(yōu)化算法的查詢計劃分為同步和非同步兩類。在同步查詢計劃中，一個MJ查詢的處理過程劃分為多個同步執(zhí)行階段，各個同步執(zhí)行階段順序執(zhí)行。在每一同步執(zhí)行階段，多個JOIN操作并行執(zhí)行，其他的查詢計劃稱為非同步執(zhí)行計劃。

文獻[2]以同步執(zhí)行計劃為目標，提出了三種產(chǎn)生優(yōu)化同步執(zhí)行計劃的啟發(fā)工MJ查詢優(yōu)化算法，第一個算法稱之為GP算法，是一種貪心算法，算法思想核心是同步執(zhí)行段的劃分，循環(huán)地為每一同步執(zhí)行階段選擇盡量多的可并行執(zhí)行的JOIN操作。該算法時間復雜性較大，為解決此問題，繼而提出算法GPt，它僅產(chǎn)生如下類型的計劃：只有第一同步執(zhí)行階段并行執(zhí)行多個JOIN，其余同步執(zhí)行階段僅執(zhí)行一個JOIN操作。

GBT查詢優(yōu)化方法具備了很高的并行性，但該執(zhí)行計劃空間十分龐大，因此查詢優(yōu)化算法的開銷也非常大。

5 語義查詢優(yōu)化方法

語義查詢比較有趣，它不同于上述優(yōu)化方法。所謂語義優(yōu)化是指對一指定的查詢問題，寫出不同的查詢語句，從中挑出DBMS能夠為之找到最高效實現(xiàn)方法的語句。據(jù)統(tǒng)計，語義完整性規(guī)則可能占一個數(shù)據(jù)庫系統(tǒng)的概念模式描述內(nèi)容的80%。

語義優(yōu)化的實現(xiàn)，遵照以下步驟：確立約束目標，即確定對哪些關系應增加補充約束或者引入索引，或者引入、刪除哪些關系；選擇完整性約束；產(chǎn)生屬性上的新約束；約束合并；查詢約束的消除；形成等價的語義查詢。有文獻的對比實驗表明，利用語義完整性規(guī)則進行查詢優(yōu)化，能夠顯著地提高效率。

6 遺傳算法

遺傳算法（Genetic Algorithm，GA）是近年發(fā)展起來的一種嶄新的全局優(yōu)化算法，1962年由Holland教授首次提出，它借用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應性的提高。這一點體現(xiàn)了自然界中“物競天擇、適者生存”的進化過程。

傳統(tǒng)的遺傳算法中有關并行調(diào)度的討論和代價估算是基于無共享資源的體系結構，首先，關系的分布算法在選擇關系的分布屬性、分布方式和處理機集合時，充分考慮了機群系統(tǒng)中引起數(shù)據(jù)重分布的因素，減少了額外的通信開銷；同時兼顧了并行系統(tǒng)中的三種并行。其次，查詢優(yōu)化部分，提出了基于遺傳算法的機群環(huán)下多連接查詢的并行優(yōu)化算法（簡稱BGA）。該算法研究了資源分配在查詢執(zhí)行代價估算中的作用和方法，提高了查詢優(yōu)化的效優(yōu)選法。與此同時，為了節(jié)省風絡通信的開銷，查詢計劃代價模型的計算將網(wǎng)絡的通信代價考慮在內(nèi)，充分利用了查詢中各關系的物理存儲信息，減小了不必要的通信開銷。

7 結論

傳統(tǒng)的并行數(shù)據(jù)庫查詢優(yōu)化技術有基于左線性樹、右線性樹、濃密樹、操作森林的并行數(shù)據(jù)庫查詢優(yōu)化，各有優(yōu)劣。目前使用的遺傳算法進行查詢優(yōu)化的方法中，我們認為仍存在兩個問題：（1）在估算查詢計劃的代價時，沒有考慮資源的分配情況，數(shù)據(jù)操作間的并行性得不到充分的開發(fā)；（2）在無共享體系結構的查詢優(yōu)化中，沒有考慮網(wǎng)絡的通信代價，無法避免額外的通信開銷。

算法研究方面，遺傳算法才剛起步，A算法、A*算法、模擬退火算法、神經(jīng)網(wǎng)絡算法在計算機的諸多方面都取得了巨大的成績，但在并行數(shù)據(jù)庫的查詢優(yōu)化方面基本還是一個空白，仍需積極探索。

參考文獻

[1]厲陽春.基于線性濃密樹的并行數(shù)據(jù)庫查詢優(yōu)化算法[J].湖南理工學院學報：自然科學版，2006，19（1）：20-23

[2]玄萍.并行數(shù)據(jù)庫查詢優(yōu)化的遺傳算法[R].哈爾濱：黑龍江大學，2004

[3]許新華，胡世港，唐勝群等.數(shù)據(jù)查詢優(yōu)化技術的歷史、現(xiàn)狀與未來[J].計算機工程與應用，2009，45（18）：156-161

作者簡介：譚玲麗，女，湖北武漢人。漢族。碩士。武漢東湖學院計算機科學學院，講師。研究方向：軟件工程，數(shù)據(jù)庫技術。