Chapter 8. 基因查詢最佳化

Table of Contents
8.1. 作為復雜最佳化問題的查詢處理
8.2. 基因算法
8.3. PostgreSQL 裡的基因查詢最佳化(GEQO
8.4. 進一步閱讀

作者: 由德國弗來堡礦業及技術大學自動控制系 Martin Utesch() 寫作.

8.1. 作為復雜最佳化問題的查詢處理

在所有關聯式運算子裡,最難以處理和最佳化的一個是 連線. 一個查詢需要回答的可選規劃的數目將隨著該查詢包含 的連線的個數餘指數增長. 在存取關系的分支時的進一步的最佳化措施是由多種多樣的 連線方法(join methods) (例,在 PostgreSQL 裡的巢狀循環,索引掃描,融合連結等 (nested loop, index scan, merge join ))來支援處理獨立 的連線和多種多樣的索引 如, PostgreSQL 裡的 r-tree,b-tree,散列(hash)).

目前 PostgreSQL 最佳化器的實現在候選策略空間裡執行一個 近似窮舉搜尋(near- exhaustive search). 這個查詢最佳化技術對包含有極廣的查詢需要的資料庫應用領域, 例如人工智能等,支援得不夠.

德國弗來堡礦業及技術大學自動控制系的成員在試圖把 PostgreSQL DBMS 作為用於一個電力網維護中做決策支援的知識庫系統的後端時, 碰到了上面的問題. 該 DBMS 需要為知識庫系統的推導機處理很大的 連線查詢.

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

在隨後的內容裡,我們提出一個 基因算法(Genetic Algorithm) 的實現作為解決資料庫查詢最佳化問題的一個選擇.