Chapter 46. 基因查詢優化

Table of Contents
46.1. 作為複雜優化問題的查詢處理
46.2. 基因算法
46.3. PostgreSQL 裡的基因查詢優化(GEQO
46.4. 進一步閱讀

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

46.1. 作為複雜優化問題的查詢處理

在所有關係型操作符裡,最難以處理和優化的一個是連接。 一個查詢需要回答的可選規劃的數目將隨著該查詢包含的連接的個數呈指數增長。 在訪問關係的分支時的進一步的優化措施是由多種多樣的連接方法(join methods) (例,在 PostgreSQL 裡的嵌套循環,索引掃瞄,融合連接等) 來支援處理獨立的連接和多種多樣的索引, 如, PostgreSQL 裡的 r-tree,b-tree,散列(hash))。

目前 PostgreSQL 優化器的實現在候選策略空間裡執行一個 近似窮舉搜索(near-exhaustive search)。 這個算法最早是在 "System R" 資料庫中引入的, 它生成一個近乎最優的連接順序,但是如果查詢中的連接增長得很大, 它可能會消耗大量得時間和內存空間。 這樣就使普通的 PostgreSQL 查詢優化器不適合那種連接了大量資料表的查詢。

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

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

在隨後的內容裡,我們描述了一個 基因算法(Genetic Algorithm), 這個算法用一種對涉及大量連接的查詢很有效的方式解決了連接順序的問題。