這個GEQO模組將查詢最佳化問題視為眾所周知的旅行推銷員問題 (Traveling Salesman Problem,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 的情況下,與任何子字串(部分路徑)相關聯的成本與路徑的其餘部分無關,但這對於查詢最佳化來說肯定不是真的。因此,邊緣重組交叉是否是最有效的突變程序是值得懷疑的。
如果您在文件中發現任何不正確、與特定功能的使用經驗不符或需要進一步澄清的地方,請使用此表單回報文件問題。