利用基因演算法來最佳化資料庫

今天在看 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

相關閱讀:
上帝的靈藥─基因演算法(一)
上帝的靈藥─基因演算法(二)

Advertisements