[ 永遠的UNIX > PostgreSQL7.0手冊-開發者手冊 -63. 數據庫系統裡的基因查詢優化 ]

[ 永遠的UNIX::UNIX技術資料的寶庫 ] GB | BIG5

首頁 > 數據庫 > 其它 > 正文

PostgreSQL7.0手冊-開發者手冊 -63. 數據庫系統裡的基因查詢優化

編譯：何偉平 laser@zhengmai.com.cn (2001-04-21 23:35:00)

第六十三章.　數據庫系統裡的基因查詢優化
內容　
作為復雜優化問題的查詢處理　
基因算法　（GA）　
Postgres　裡的基因查詢優化（GEQO）　
Postgres　GEQO未來的實現任務　
作者：由德國弗來堡礦業及技術大學自動控制系　Martin　Utesch　書寫．
作為復雜優化問題的查詢處理
在所有關系型操作符裡，最難以處理和優化的一個是　join．一個查詢需要回答的可選規劃的數目將隨著該查詢包含的　join　的個數呈指數增長．在訪問關系的分支時的進一步的優化措施是由多種多樣的　聯接方法(join　methods)　（例如，在　Postgres　裡的嵌套循環，索引掃描，融合聯接等（nested　loop,　index　scan,　merge　join　））來支持處理獨立　join　（聯接）和多種多樣的　索引(indices)　（如，Postgres裡的　r-tree，b-tree，散列（hash））．　
目前　Postgres　優化器的實現在候選策略空間裡執行一個近似完全搜索　(near-　exhaustive　search)　．這個查詢優化技術對包含有極廣的查詢需要的數據庫應用領域，例如人工智能等，支持得不夠．　

德國弗來堡礦業及技術大學自動控制系的成員在試圖把Postgres　DBMS　作為用一個電力網維護中做決策支持的知識庫系統的端時，碰到了上面的問題．該　DBMS　需要為知識庫系統的推導機處理很大的　join　（聯接）查詢．　

在可能的查詢規劃空間裡進行檢索的惡劣性能引起了人們對發展新的優化技術的需要．　

在隨的內容裡，我們提出一個　基因算法　(Genetic　Algorithm)　的實現作為解決數據庫查詢優化問題的一個選擇．　
　

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

基因算法（GA）
GA　是一種啟發式的優化法（heuristic　optimization　method），它是通過既定的隨機搜索進行操作．優化問題的可能的解的集合被認為是個體　(individuals)　組成的的　人群(population)　．一個個體對它的環境的適應程度由它的健康度（fitness）表示．　
一個個體在搜索空間裡的參照物是用染色體（chromosomes）表示的，實際上那是一套字符串．一個基因　（gene）是染色體的一個片段，基因對被優化的單個參數進行編碼．對一個基因的典型的編碼可以是　二進制　（binary）或整數（integer）。　

通過仿真進化過程的重組　（recombination）。突變　（mutation），和選擇　（selection）找到新一代的搜索點，它們的平均健康度要比它們的祖先好．　

根據　"comp.ai.genetic"　FAQ，我們不論怎強調　GA　在解決一個問題時不是純隨機搜索都不過份．GA　使用隨機處理，但是結果明顯不是隨機的（比隨機更好）．　

GA　結構化框圖：
---------------------------

P(t)　　　　generation　of　ancestors　at　a　time　t
P''(t)　　generation　of　descendants　at　a　time　t

+=========================================+
|>>>>>>>>>>>　　Algorithm　GA　　<<<<<<<<<<<<<<|
+=========================================+
|　INITIALIZE　t　:=　0　　　　　　　　　　　　　　　　　　　　　　　|
+=========================================+
|　INITIALIZE　P(t)　　　　　　　　　　　　　　　　　　　　　　　　　|
+=========================================+
|　evalute　FITNESS　of　P(t)　　　　　　　　　　　　　　　　　|
+=========================================+
|　while　not　STOPPING　CRITERION　do　　　　　　　　　|
|　　　+-------------------------------------+
|　　　|　P'(t)　　:=　RECOMBINATION{P(t)}　　　　　　　|
|　　　+-------------------------------------+
|　　　|　P''(t)　:=　MUTATION{P'(t)}　　　　　　　　　　　|
|　　　+-------------------------------------+
|　　　|　P(t+1)　:=　SELECTION{P''(t)　+　P(t)}　　|
|　　　+-------------------------------------+
|　　　|　evalute　FITNESS　of　P''(t)　　　　　　　　　　　|
|　　　+-------------------------------------+
|　　　|　t　:=　t　+　1　　　　　　　　　　　　　　　　　　　　　　　　　　|
+===+=====================================+

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

Postgres　裡的基因查詢優化（GEQO）
GEQO　模塊是試圖解決類似漫遊推銷員問題（TSP）的查詢優化問題的．可能的查詢規劃被當作整數字串進行編碼．每個字串代表查詢裡面一個關系到下一個關系的　join　的順序．例如，下面的查詢樹　
　　　　　　　/\
　　　　　　/\　2
　　　　　/\　3
　　　　4　　1
是用整數字串　'4-1-3-2'　編碼的，這就是說，首先聯接關系　'4'　和　'1'，然　'3'，然是　'2'，這裡的　1，2，3，4都是　Postgres　裡的關系標識（relids）。　
GEQO　模塊的一部分是採用的　D.　Whitley　的　Genitor　算法．　

在　Postgres　裡的　GEQO　實現的一些特性是：　

穩定狀態　(steady　state)　GA　的使用（替換全體中最小健康度的個體，而不是整代的替換）允許向改進了的查詢規劃快速逼近．這一點對在有效時間內處理查詢是非常重要的；
邊緣重組交叉　(edge　recombination　crossover　)　的使用特別適在用GA　解決　TSP　問題時保持邊緣損失最低。
否決了把突變（Mutation）作為基因操作符的做法，這樣生成合法的　TSP　漫遊時不需要修復機制．

與　Postgres　的查詢優化器實現相比較，GEQO　模塊對Postgres　DBMS　有下面的貢獻：　
通過非完全搜索對大的　join　（聯接）查詢進行操作；
改善了查詢規劃的開銷尺寸的近似值，因為不需要做規劃融合了（GEQO　模塊把查詢規劃的開銷當作一個個體來評估）．

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

PostgresGEQO　未來的實現任務
基本改進
改進查詢處理完的內存釋放
在處理大　join　（聯接）查詢時，用基因查詢優化的時間看來只是　Postgres　通過過程　MemoryContextFree（在文件　backend/utils/mmgr/mcxt.c　裡）釋放內存的　一小部分（fraction）．跟蹤調試顯示釋放內存的工作陷在文件　backend/utils/mmgr/oset.c　裡的過程　OrderedElemPop　裡的一個循環裡了．在使用普通　Postgres　查詢優化算法處理長的查詢時也會產生這個問題．
改善基因算法參數設置
在文件　backend/optimizer/geqo/geqo_params.c　裡的過程　gimme_pool_size　和　gimme_number_generations，我們在設置參數時不得不為兩個競爭條件做出折衷：　
查詢規劃的優化　
計算處理時間

尋找解決整數溢出的更好的辦法
在文件　backend/optimizer/geqo/geqo_eval.c　裡的過程　geqo_joinrel_size，目前對防止　MAXINT　溢出的方法（hack）是把　Postgres　的整數值　rel->size　to　設置為它的對數．對　backend/nodes/relation.h　裡的　Rel　的變動顯然將嚴重影響整個　Postgres　的實現．
尋找解決內存耗盡的辦法
當一個查詢裡的關系超過　10　個時將導致內存的耗盡．在文件　backend/optimizer/geqo/geqo_eval.c裡的過程　gimme_tree　是被遞歸調用的．可能我忘記了正確地釋放某些東西了，但是我不知道是什．當然　join　的rel　數據結構隨著更多的關系打包進入之會越長越大．歡迎任何建議　:-(
參考
GEQ　算法的參考信息．　
The　Hitch-Hiker's　Guide　to　Evolutionary　Computation,　Jg　Heitkter　和　David　Beasley，　InterNet　resource,　The　Design　and　Implementation　of　the　Postgres　Query　Optimizer,　Z.　Fong,　University　of　California,　Berkeley　Computer　Science　Department,　Fundamentals　of　Database　Systems,　R.　Elmasri　and　S.　Navathe,　The　Benjamin/Cummings　Pub.,　Inc..　

comp.ai.genetic　上的FAQ可以在　Encore拿到．
文件　planner/Report.ps　在　'postgres-papers'　發布版裡．

--------------------------------------------------------------------------------

(http://www.fanqiang.com) 進入【UNIX論壇】

相關文章

===更多相關===

★ 樊強制作歡迎分享 ★