48.3. PostgreSQL 裡的基因查詢優化（GEQO）

GEQO 模塊是試圖解決類似漫遊推銷員問題（TSP）的查詢優化問題的。 可能的查詢規劃被當作整數字串進行編碼。每個字串代表查詢裡面一個關系到下一個關系的 連接的順序。 例如，下面的查詢樹

   /\
  /\ 2
 /\ 3
4  1

是用整數字串 '4-1-3-2' 編碼的， 這就是說，首先聯接關系 '4' 和 '1'，然後 '3'，然後是 '2'， 這裡的 1，2，3，4都是 PostgreSQL 優化器裡的關系標識（ID）。

GEQO 模塊的一部分是採用的 D. Whitley 的 Genitor 算法。

在 PostgreSQL 裡的 GEQO 實現的一些特性是：

• 使用 穩定狀態（steady state）的 GA （替換全體中最小健康度的個體，而不是整代的替換）允許向改進了的查詢規劃快速逼近。 這一點對在合理時間內處理查詢是非常重要的；

• 邊緣重組交叉（edge recombination crossover）的使用特別適于在用 GA解決 TSP 問題時保持邊緣損失最低。

  譯注: TSP 是旅行推銷員問題的意思

• 否決了把突變（Mutation）作為基因操作符的做法，這樣生成合法的 TSP 漫遊時不需要修復機制。

GEQO 模塊讓 PostgreSQL 查詢優化器可以通過非窮舉搜索有效地支持大的連接查詢。