支援版本:目前 (17) / 16 / 15 / 14 / 13
開發版本:devel
不支援的版本:12 / 11 / 10 / 9.6 / 9.5 / 9.4 / 9.3 / 9.2 / 9.1 / 9.0 / 8.4 / 8.3 / 8.2 / 8.1 / 8.0 / 7.4 / 7.3 / 7.2 / 7.1

60.3. 基因查詢最佳化 (GEQO) 在 PostgreSQL 中 #

這個GEQO模組將查詢最佳化問題視為眾所周知的旅行推銷員問題 (TSP)。可能的查詢計畫被編碼為整數字串。每個字串代表從查詢的一個關係到下一個關係的聯結順序。例如,聯結樹

   /\
  /\ 2
 /\ 3
4  1

由整數字串「4-1-3-2」編碼,這表示先聯結關係「4」和「1」,然後聯結「3」,然後聯結「2」,其中 1、2、3、4 是 PostgreSQL 最佳化器中的關係 ID。

PostgreSQLGEQO實作的具體特徵是

  • 使用穩態GA(替換群體中最不適合的個體,而不是整代替換) 允許快速收斂到改進的查詢計畫。這對於在合理的時間內處理查詢至關重要;

  • 使用邊緣重組交叉,這特別適合保持低邊緣損失以解決TSP透過GA;

  • 突變作為基因運算子已被棄用,因此不需要修復機制來產生合法的TSP路線。

部分的GEQO模組改編自 D. Whitley 的 Genitor 演算法。

這個GEQO模組允許 PostgreSQL 查詢最佳化器透過非窮舉搜尋有效地支援大型聯結查詢。

60.3.1. 使用 GEQO 產生可能的計畫GEQO #

這個GEQO規劃過程使用標準規劃器程式碼來產生掃描個別關係的計畫。然後使用基因方法開發聯結計畫。如上所示,每個候選聯結計畫都由一個序列表示,用於聯結基本關係。在初始階段,GEQO程式碼只是隨機產生一些可能的聯結序列。對於考慮的每個聯結序列,都會呼叫標準規劃器程式碼來估計使用該聯結序列執行查詢的成本。(對於聯結序列的每個步驟,都會考慮所有三種可能的聯結策略;並且所有最初確定的關係掃描計畫都可用。估計成本是這些可能性中最便宜的。) 估計成本較低的聯結序列被認為比成本較高的聯結序列「更適合」。基因演算法會捨棄最不適合的候選者。然後透過組合更適合的候選者的基因來產生新的候選者 - 也就是說,透過使用已知低成本聯結序列的隨機選擇部分來建立新的序列以供考慮。重複此過程,直到考慮了預設數量的聯結序列;然後使用在搜尋期間任何時間找到的最佳序列來產生完成的計畫。

由於在初始群體選擇和隨後的最佳候選者的「突變」期間所做的隨機選擇,此過程本質上是不確定的。為了避免所選計畫的令人驚訝的變化,GEQO 演算法的每次執行都會使用目前的 geqo_seed 參數設定重新啟動其亂數產生器。只要 geqo_seed 和其他 GEQO 參數保持固定,就會為給定的查詢 (以及其他規劃器輸入,例如統計資料) 產生相同的計畫。若要試驗不同的搜尋路徑,請嘗試變更 geqo_seed

60.3.2. PostgreSQL 未來的實作任務GEQO #

仍需要改進基因演算法的參數設定。在檔案 src/backend/optimizer/geqo/geqo_main.c 中的 gimme_pool_sizegimme_number_generations 函式中,我們必須為參數設定找到一個平衡點,以滿足兩個相互競爭的需求:

  • 查詢計畫的最佳化

  • 運算時間

在目前的實作中,每個候選的連接序列的適應度(fitness)是透過從頭開始執行標準計畫器的連接選擇和成本估算程式碼來估算的。如果不同的候選方案使用相似的連接子序列,則會重複大量工作。通過保留子連接的成本估算,可以顯著加快速度。問題在於避免花費不合理的記憶體量來保留該狀態。

在更基本的層面上,使用為 TSP 設計的 GA 演算法來解決查詢最佳化問題是否合適尚不清楚。在 TSP 的情況下,與任何子字串(部分路徑)相關的成本與路徑的其餘部分無關,但對於查詢最佳化而言,情況並非如此。因此,邊緣重組交叉是否是最有效的突變程序,值得懷疑。

提交更正

如果您在文件中發現任何不正確、與您使用特定功能時的體驗不符或需要進一步澄清的地方,請使用此表單來回報文件問題。