PostgreSQL 將查詢處理看成是一個(gè)復(fù)雜的優(yōu)化問題

在所有關(guān)系操作符中，最難于處理和優(yōu)化的是連接?？赡艿牟樵冇?jì)劃數(shù)目以查詢中連接數(shù)量的指數(shù)增長。對各種各樣處理獨(dú)立連接的連接方法（如PostgreSQL中的嵌套循環(huán)、哈希連接、歸并連接）和多種關(guān)系訪問方法的indexes（如PostgreSQL中的 B 樹、哈希、GiST 和 GIN）的支持也進(jìn)一步加重了優(yōu)化的負(fù)擔(dān)。

通常的PostgreSQL查詢優(yōu)化器會(huì)執(zhí)行一次在可選策略空間上的近似窮舉搜索。這個(gè)算法最早由 IBM 的系統(tǒng) R 數(shù)據(jù)庫引入，它能產(chǎn)生接近最優(yōu)的連接順序，但是當(dāng)查詢中的連接數(shù)增長到很大時(shí)，該算法需要大量的時(shí)間和內(nèi)存空間。這使得普通的PostgreSQL查詢優(yōu)化器不適合需要連接大量表的查詢。

德國弗萊堡的礦業(yè)大學(xué)自動(dòng)控制學(xué)院在使用PostgreSQL作為電力網(wǎng)格維護(hù)決策支持知識(shí)系統(tǒng)的后端時(shí)遇到了一些問題。DBMS 需要為知識(shí)系統(tǒng)中的推理機(jī)器處理大量連接查詢。這些查詢中的連接數(shù)不可能用普通的查詢優(yōu)化器來處理。

接下來我們將介紹一種遺傳算法的實(shí)現(xiàn)，它被用來以一種更有效率的方式為涉及大量連接的查詢解決連接順序問題。