# 53.3\. PostgreSQL 里的基因查詢優化(GEQO) GEQO模塊是試圖解決類似著名的旅行商問題(TSP)的查詢優化問題的。 可能的查詢規劃被當作整數字符串進行編碼。每個字符串代表查詢里面一個關系到下一個關系的連接的順序。例如，下面的連接樹 ``` /\ /\ 2 /\ 3 4 1 ``` 是用整數字符串'4-1-3-2'編碼的，這就是說，首先連接關系'4'和'1'，然后'3'，然后是'2'， 這里的 1, 2, 3, 4 都是PostgreSQL優化器里的關系標識(ID)。 在PostgreSQL里的GEQO實現的一些特性是： * 使用_穩定狀態_的 GA(替換全體中最小適應性的個體，而不是整代的替換) 允許向改進了的查詢規劃快速逼近。這一點對在合理時間內處理查詢是非常重要的； * _邊緣重組交叉_的使用特別適于在用GA解決TSP問題時保持邊緣損失最低。 * 否決了把突變作為基因操作符的做法，這樣生成合法的TSP漫游時不需要修復機制。 GEQO模塊的一部分是采用的 D.Whitley 的 Genitor 算法。 GEQO模塊讓PostgreSQL查詢優化器可以通過非窮舉搜索有效地支持大的連接查詢。 ## 53.3.1\. GEQO生成的候選規劃 GEQO規劃過程使用標準的規劃器代碼生成各個獨立表的掃描規劃。 然后用遺傳算法生成連接規劃。正如上面講到的，每個候選的連接規劃由基本表的連接序列表示。 在初始階段， GEQO簡單的生成一些隨機的連接序列。 對每個連接序列，調用標準的規劃器代碼評估以這樣的連接序列執行查詢的成本。 （對連接序列的每一個步驟，考慮所有可能的三種連接策略；并且所有初期決定的關系掃描規劃也是有效的。 評估值是所有這些可能性中最廉價的。 ） 評估成本更低的連接序列被認為比代價高的那些連接序列"更加合適"。基因算法淘汰那些最不合適的候選。 然后通過組合最合適的基因生成新的候選，即通過隨機選擇一部分低成本的連接序列去產生作為候選的新的序列。 這個過程不斷重復直到考慮過的連接序列達到一個預設的值，然后在搜索期間找到的最好的結果作為最終生成的執行計劃。 這個過程天生是不確定的，因為在選擇初期總群以及隨后對最佳候補實施"突變"時都帶有隨機性。 為了避免被選中的計劃發生令人驚訝的變化，每次GEQO算法執行都根據當前[geqo_seed](#calibre_link-531)參數的設置開始一個隨機數生成器。 只要`geqo_seed`以及其他GEQO參數保持固定，對一個給定的查詢(以及其他規劃器輸入，比如統計信息)將生成相同的執行計劃。 如果要嘗試不同的搜索路徑，可以嘗試改變`geqo_seed`。 ## 53.3.2\. PostgreSQL GEQO未來的實現任務 還需要一些工作來改進基因算法的參數設置。 在文件`src/backend/optimizer/geqo/geqo_main.c`里的過程 `gimme_pool_size`和 `gimme_number_generations` 在設置參數時不得不為兩個競爭需求做出折衷： * 查詢規劃的優化 * 計算處理時間 在當前的實現中，每個候選連接序列的適應性是通過運行標準規劃器的連接選擇和代價評估代碼從頭開始評估的。 當不同的候選使用相似的連接子序列，將有大量的工作會重復。 通過保持子序列的代價評估值可以顯著的提升速度。問題在于要避免為了保持這個狀態而不合理的內存擴展。 在最基本的層面上，并不清楚用給 TSP 涉及的 GA 算法解決查詢優化的問題是否合適。 在 TSP 的情況下，與任何子字符串(部分旅游)相關的開銷都是獨立于旅游的其它部分的，但是目前，這一點對于查詢優化是不同的。 因此，可以懷疑邊緣重組交叉是否最有效的突變過程。