今天在看 PostgreSQL 的文件時，發�有個章節在講�用基因演算法(Genetic Algorithms) 來最佳化資料庫的查詢方法(Query Plan)，就來介紹一下 PostgreSQL 是如何應用的。

所謂的 Query Plan(查詢方法)，是指資料庫管�程�如何由�存的 Table 中，�出使用者想�的資料。Query Plan中最難以處�的是 Join 這個動作。Join 這個動作，簡而言之就是把兩個相關的 Table ��一張大的 Table；例如我們有一個 Table 記錄 "人�-居�城市"，�一個"人�-喜好"，今天如果我們�找出"��北��喜歡寫 Blog"的人，就�以利用 Join 這個指令，以人�當作索引值，��一張�時具有我們所需�資料的 Table。

Join 有很多種方法�以�到，最差的狀�就是把所有的�能性都列出來，�刪掉�正確的。舉例來說，�� Table 有一�筆，喜好資料也有一�筆，那麼就先產生一百�筆的表格，�一一刪去；相�的，如果我們知�人�都沒有�覆�居�城市表格中，�一個人也�會有一筆資料��個人也�有一個喜好，那麼甚至�能幾�筆就�出來了。

但並�是�一個 Query Plan 都是如此的顯而易見，當需�比�的 Table 越來越多，到底是先 Join 哪一個 Table�先 Join 哪兩個 Join 完的�果，會變�一個需�把全部的�能性都列出來，�知�哪個最好的�題，我們稱這種解法��"窮盡�"(Exhaustiive Search)，��就是得把所有的組�都找出來�行。

更慘的是 Query Plan 的數��隨著 Table 的增加而大幅增加，當需� Join 的 Table 由兩個變三個�四個甚至到�幾個時， Query Plan 的總�就� 1*2*3*4 這樣呈指數�長，到最後�找出所有的�能解答本身所花的時間，��好都比資料庫查詢時間來得長了。

在德國的 University of Mining and Technology 自動控制學院設計了一個電力控制系統，用 PostgreSQL 來當作決策系統的資料庫，但是因為決策系統需��用大�的 Join 來進行推�的�算，為了兼顧效率，他們把基因演算法引入資料庫的設計之中，用來快速產生有效率的 Query Plan。

關於基因演算法的基本概念在此略�，請�考本站相關文章。

Query Plan 最佳化的作法和著�的 Traveling Salesman Problem(TSP) �題很類似，先將�能的解法變�數字的字串，例如 4-1-3-2 就表示先讓 Table 4 和 Table 1 � Join，�和 Table 3�2 � Join。

演化時採用穩態演化，也就是�次�把表�最差的一個 Plan 淘汰掉；而�代的產生則是�用 "edge recombination crossover[註二]"，而�變的機制在這裡並�使用。

�用基因演算法，資料庫�以在��的時間中找出有效的 Query Plan來進行 Join 的動作，然而除了找出最好的 Query Plan 之外，電腦的的Computation Time也是一個很��的因素，��的�數�於系統也會有��的影響。

從這個例��以看到基因演算法所�用的場�，還是脫離�開"在��的時間"�"複雜度高的狀�下"�"找到���接�的解法"的特色。

註一：PostgreSQL 是一個 GPL 的資料庫，最早是由 Berkeley 所發展的，如今和 MySQL �為網路上最�歡迎的 GPL 資料庫軟體，官方網站在 http://www.postgresql.org。

註二：關於 edge recombination crossover 的說明，請�考這裡。

�考資料：
Genetic Query Optimization

相關閱讀：
上�的�藥─基因演算法(一)
上�的�藥─基因演算法(二)

在å�¦ä¸€å€‹blog寫文章時，都會有一種脫力的感覺。ä¸�知é�“是ä¸�是寫文章太用力的關係，大概是覺得有讀者壓力就會很大å�§…