麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁 > 數據庫 > PostgreSQL > 正文

PostgreSQL7.0手冊-開發者手冊 -63. 數據庫系統里的基因查詢優化

2019-09-08 23:34:06
字體：大 中 小
來源：轉載
供稿：網友
第六十三章.　數據庫系統里的基因查詢優化
內容　
作為復雜優化問題的查詢處理　
基因算法　（GA）　
Postgres　里的基因查詢優化（GEQO）　
Postgres　GEQO未來的實現任務　
作者：由德國弗來堡礦業及技術大學自動控制系　Martin　Utesch　書寫．
作為復雜優化問題的查詢處理
在所有關系型操作符里，最難以處理和優化的一個是　join．一個查詢需要回答的可選規劃的數目將隨著該查詢包含的　join　的個數呈指數增長．在訪問關系的分支時的進一步的優化措施是由多種多樣的　聯接方法(join　methods)　（例如，在　Postgres　里的嵌套循環，索引掃描，融合聯接等（nested　loop,　index　scan,　merge　join　））來支持處理獨立　join　（聯接）和多種多樣的　索引(indices)　（如，Postgres里的　r-tree，b-tree，散列（hash））．　
目前　Postgres　優化器的實現在候選策略空間里執行一個近似完全搜索　(near-　exhaustive　search)　．這個查詢優化技術對包含有極廣的查詢需要的數據庫應用領域，例如人工智能等，支持得不夠．　

德國弗來堡礦業及技術大學自動控制系的成員在試圖把Postgres　DBMS　作為用于一個電力網維護中做決策支持的知識庫系統的后端時，碰到了上面的問題．該　DBMS　需要為知識庫系統的推導機處理很大的　join　（聯接）查詢．　

在可能的查詢規劃空間里進行檢索的惡劣性能引起了人們對發展新的優化技術的需要．　

在隨后的內容里，我們提出一個　基因算法　(Genetic　Algorithm)　的實現作為解決數據庫查詢優化問題的一個選擇．　
　


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

基因算法（GA）
GA　是一種啟發式的優化法（heuristic　optimization　method），它是通過既定的隨機搜索進行操作．優化問題的可能的解的集合被認為是個體　(individuals)　組成的的　人群(population)　．一個個體對它的環境的適應程度由它的健康度（fitness）表示．　
一個個體在搜索空間里的參照物是用染色體（chromosomes）表示的，實際上那是一套字符串．一個基因　（gene）是染色體的一個片段，基因對被優化的單個參數進行編碼．對一個基因的典型的編碼可以是　二進制　（binary）或整數（integer）。　

通過仿真進化過程的重組　（recombination）。突變　（mutation），和選擇　（selection）找到新一代的搜索點，它們的平均健康度要比它們的祖先好．　

根據　"comp.ai.genetic"　FAQ，我們不論怎么強調　GA　在解決一個問題時不是純隨機搜索都不過份．GA　使用隨機處理，但是結果明顯不是隨機的（比隨機更好）．　

GA　結構化框圖：
---------------------------

P(t)　　　　generation　of　ancestors　at　a　time　t
P''(t)　　generation　of　descendants　at　a　time　t

+=========================================+
|>>>>>>>>>>>　　Algorithm　GA　　<<<<<<<<<<<<<<|
+=========================================+
|　INITIALIZE　t　:=　0　　　　　　　　　　　　　　　　　　　　　　　|
+=========================================+
|　INITIALIZE　P(t)　　　　　　　　　　　　　　　　　　　　　　　　　|
+=========================================+
|　evalute　FITNESS　of　P(t)　　　　　　　　　　　　　　　　　|
+=========================================+
|　while　not　STOPPING　CRITERION　do　　　　　　　　　|
|　　　+-------------------------------------+
|　　　|　P'(t)　　:=　RECOMBINATION{P(t)}　　　　　　　|
|　　　+-------------------------------------+
|　　　|　P''(t)　:=　MUTATION{P'(t)}　　　　　　　　　　　|
|　　　+-------------------------------------+
|　　　|　P(t+1)　:=　SELECTION{P''(t)　+　P(t)}　　|
|　　　+-------------------------------------+
|　　　|　evalute　FITNESS　of　P''(t)　　　　　　　　　　　|
|　　　+-------------------------------------+
|　　　|　t　:=　t　+　1　　　　　　　　　　　　　　　　　　　　　　　　　　|
+===+=====================================+

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

Postgres　里的基因查詢優化（GEQO）
GEQO　模塊是試圖解決類似漫游推銷員問題（TSP）的查詢優化問題的．可能的查詢規劃被當作整數字串進行編碼．每個字串代表查詢里面一個關系到下一個關系的　join　的順序．例如，下面的查詢樹　
　　　　　　　//
　　　　　　//　2
　　　　　//　3
　　　　4　　1
是用整數字串　'4-1-3-2'　編碼的，這就是說，首先聯接關系　'4'　和　'1'，然后　'3'，然后是　'2'，這里的　1，2，3，4都是　Postgres　里的關系標識（relids）。　
GEQO　模塊的一部分是采用的　D.　Whitley　的　Genitor　算法．　

在　Postgres　里的　GEQO　實現的一些特性是：　

穩定狀態　(steady　state)　GA　的使用（替換全體中最小健康度的個體，而不是整代的替換）允許向改進了的查詢規劃快速逼近．這一點對在有效時間內處理查詢是非常重要的；
邊緣重組交叉　(edge　recombination　crossover　)　的使用特別適于在用GA　解決　TSP　問題時保持邊緣損失最低。
否決了把突變（Mutation）作為基因操作符的做法，這樣生成合法的　TSP　漫游時不需要修復機制．

與　Postgres　的查詢優化器實現相比較，GEQO　模塊對Postgres　DBMS　有下面的貢獻：　
通過非完全搜索對大的　join　（聯接）查詢進行操作；
改善了查詢規劃的開銷尺寸的近似值，因為不需要做規劃融合了（GEQO　模塊把查詢規劃的開銷當作一個個體來評估）．

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

PostgresGEQO　未來的實現任務
基本改進
改進查詢處理完后的內存釋放
在處理大　join　（聯接）查詢時，用于基因查詢優化的時間看來只是　Postgres　通過過程　MemoryContextFree（在文件　backend/utils/mmgr/mcxt.c　里）釋放內存的　一小部分（fraction）．跟蹤調試顯示釋放內存的工作陷在文件　backend/utils/mmgr/oset.c　里的過程　OrderedElemPop　里的一個循環里了．在使用普通　Postgres　查詢優化算法處理長的查詢時也會產生這個問題．
改善基因算法參數設置
在文件　backend/optimizer/geqo/geqo_params.c　里的過程　gimme_pool_size　和　gimme_number_generations，我們在設置參數時不得不為兩個競爭條件做出折衷：　
查詢規劃的優化　
計算處理時間

尋找解決整數溢出的更好的辦法
在文件　backend/optimizer/geqo/geqo_eval.c　里的過程　geqo_joinrel_size，目前對防止　MAXINT　溢出的方法（hack）是把　Postgres　的整數值　rel->size　to　設置為它的對數．對　backend/nodes/relation.h　里的　Rel　的變動顯然將嚴重影響整個　Postgres　的實現．
尋找解決內存耗盡的辦法
當一個查詢里的關系超過　10　個時將導致內存的耗盡．在文件　backend/optimizer/geqo/geqo_eval.c里的過程　gimme_tree　是被遞歸調用的．可能我忘記了正確地釋放某些東西了，但是我不知道是什么．當然　join　的rel　數據結構隨著更多的關系打包進入之后會越長越大．歡迎任何建議　:-(
參考
GEQ　算法的參考信息．　
The　Hitch-Hiker's　Guide　to　Evolutionary　Computation,　J 主站蜘蛛池模板： 久久草在线看 | 超碰人人做人人爱 | 欧美一级做性受免费大片免费 | 精品国产91久久久久久久妲己 | 亚洲特黄a级毛片在线播放 久久久入口 | 亚洲午夜一区二区三区 | 亚洲精品a级 | 亚洲国产成人久久一区www妖精 | qyl在线视频精品免费观看 | av中文字幕免费在线观看 | 男女羞羞的视频 | 久色亚洲 | 大学生一级毛片在线视频 | 99视频有精品 | 在线播放亚洲精品 | 欧美一级视频免费看 | 久久老司机精品视频 | 成年人视频免费 | 中国老女人一级毛片视频 | 一级电影在线免费观看 | 91精品久久久久久久 | 中文字幕一区在线观看视频 | 欧美精品一区二区三区在线 | a免费视频 | 黑人三级毛片 | 国产在线a | 91精品国产综合久久久动漫日韩 | 最新在线中文字幕 | 精品一区二区久久久久久按摩 | 久久精品一区二区三区四区五区 | 久久精品一级片 | 成人在线97 | 亚洲国产中文字幕 | 鲁丝片一区二区三区免费入口 | 黄色片在线免费播放 | 在线免费91 | 国产午夜精品久久久久久久蜜臀 | 日本一区二区在线 | 亚洲网站在线观看视频 | av电影免费观看 | 一区二区久久电影 |