該GEQO模組將查詢最佳化問題視為眾所周知的旅行推銷員問題 (TSP). 可能的查詢計劃被編碼為整數字符串。每個字串表示從查詢中的一個關係到下一個關係的連線順序。例如,連線樹
/\ /\ 2 /\ 3 4 1
由整數字符串“4-1-3-2”編碼,這意味著首先連線關係“4”和“1”,然後是“3”,然後是“2”,其中 1、2、3、4 是 PostgreSQL 最佳化器中的關係 ID。
PostgreSQL 中GEQO實現的一些特點是:
使用穩態GA(替換群體中最不適應的個體,而不是整體世代替換)允許快速收斂到改進的查詢計劃。這對於在合理時間內處理查詢至關重要;
使用邊緣重組交叉,特別適用於透過TSP解決GA;
問題時保持低邊緣損失。TSP變異作為遺傳運算元已被棄用,因此不需要修復機制來生成合法的
遍歷。GEQO模組的部分內容改編自 D. Whitley 的 Genitor 演算法。
該GEQO模組允許 PostgreSQL 查詢最佳化器透過非窮舉搜尋有效地支援大型連線查詢。
該GEQO規劃過程使用標準規劃器程式碼為單個關係的掃描生成計劃。然後使用遺傳方法開發連線計劃。如上所示,每個候選連線計劃都由一個連線基本關係的序列表示。在初始階段,GEQO程式碼只是隨機生成一些可能的連線序列。對於考慮的每個連線序列,呼叫標準規劃器程式碼來估計使用該連線序列執行查詢的成本。(對於連線序列的每個步驟,考慮所有三種可能的連線策略;並且所有最初確定的關係掃描計劃都可用。估計成本是這些可能性中最便宜的。)估計成本較低的連線序列被認為是比成本較高的連線序列“更適合”。遺傳演算法會丟棄最不適合的候選者。然後透過組合更適合候選者的基因來生成新的候選者——即,透過使用已知低成本連線序列的隨機選擇部分來建立新的序列以供考慮。這個過程重複,直到考慮了預設數量的連線序列;然後使用在搜尋過程中任何時候發現的最佳序列來生成最終計劃。
由於在初始種群選擇和隨後最佳候選者的“變異”過程中都進行了隨機選擇,因此此過程本質上是不確定的。為避免所選計劃發生意外更改,GEQO 演算法的每次執行都會使用當前的geqo_seed引數設定重新啟動其隨機數生成器。只要geqo_seed
和其他 GEQO 引數保持固定,對於給定的查詢(以及其他規劃器輸入,例如統計資訊),將生成相同的計劃。要嘗試不同的搜尋路徑,請嘗試更改geqo_seed
。
仍需要努力改進遺傳演算法引數設定。在檔案src/backend/optimizer/geqo/geqo_main.c
中,例程gimme_pool_size
和gimme_number_generations
,我們必須為引數設定找到一個折衷方案,以滿足兩個相互競爭的需求:
查詢計劃的最優性
計算時間
在當前實現中,每個候選連線序列的適應度是透過從頭執行標準規劃器的連線選擇和成本估算程式碼來估算的。在不同候選者使用相似的連線子序列的程度上,會重複大量工作。透過保留子連線的成本估算,可以顯著加快速度。問題在於避免在保留該狀態上花費不合理的記憶體。
在更基本的層面上,用為 TSP 設計的 GA 演算法解決查詢最佳化是否合適尚不清楚。在 TSP 情況下,與任何子字串(部分遍歷)相關的成本與遍歷的其餘部分無關,但對於查詢最佳化來說肯定不是這樣。因此,邊緣重組交叉是否是最有效的變異過程值得懷疑。
如果您發現文件中存在不正確、與您使用特定功能的經驗不符或需要進一步澄清的任何內容,請使用此表格報告文件問題。