連接優(yōu)化是數據庫領域最重要的研究問題之一.傳統(tǒng)的連接優(yōu)化方法一般應用基礎啟發(fā)式規(guī)則,他們通常搜索代價很高,并且很難發(fā)現最優(yōu)的執(zhí)行計劃.主要原因有兩個:（1）這些基于規(guī)則的優(yōu)化方法只能探索解空間的一個子集,（2）他們沒有利用歷史信息,不能夠很好地衡量執(zhí)行計劃的代價,經常重復選擇相同的糟糕計劃.為了解決以上兩個問題,我們提出RLO （reinforcement learning optimization）,一個基于強化學習的連接優(yōu)化方法.我們將連接優(yōu)化問題建模成馬爾可夫（Markov）決策過程,并且使用深度Q-學習來估計每一種可能的執(zhí)行計劃的執(zhí)行代價.為了進一步增強RLO的有效性,我們提出了基于樹形結構的嵌入方法和集束搜索策略來盡量避免錯過最好的執(zhí)行計劃.我們在Apache Calcite和Postgres上實現了RLO.實驗表明:（1）在Apache Calcite上,與一系列剪枝的啟發(fā)式算法相比, RLO搜索計劃的效率為它們的10⁵6倍,并且生成的計劃能更快地執(zhí)行（80%的加速）;（2）與原生的Postgres相比, RLO搜索計劃的效率是其14倍,并且在端到端的... 

【文章來源】：中國科學:信息科學. 2020,50(05)北大核心CSCD

【文章頁數】：12 頁

【部分圖文】：

(網絡版彩圖)RLO優(yōu)化器框架

(5)最后優(yōu)化器按傳統(tǒng)方法[3]添加Agg,Group等計劃節(jié)點,便得到最終的物理計劃,交由執(zhí)行器執(zhí)行,并返回查詢結果.在這個過程中,我們可以收集實際的執(zhí)行數據,對神經網絡進行微調(fine-tuning)[15],實現從反饋中學習.接下來,我們按照以上的執(zhí)行步驟依次介紹:狀態(tài)與動作的表征(3.3小節(jié)),Q值的計算(3.4小節(jié)),搜索新動作(3.5小節(jié))以及網絡微調(3.6小節(jié)).

其次,RLO算法的搜索效率在關系數目較多的時候占有較大的優(yōu)勢.例如對于較多的關系數,RLO和DQ算法實現了極大的提速:RLO最多可以比EX快104倍,比ZZ快100倍,比LD,RD快10倍以上.平均來說,當關系數大于6時,RLO算法比EX快2867倍,比ZZ快56倍,比LD,RD快5.6倍.原因與我們之前的分析相同,RLO具有貪心算法的時間復雜度,遠快于動態(tài)規(guī)劃.另外,GD,QP一直保持著最小的優(yōu)化時間,這是因為它們剪枝的策略太嚴格,忽略了大部分的解空間,這會導致較差的執(zhí)行效率(參見4.2.2小節(jié)).最后,RLO的搜索效率略差于DQ算法.例如RLO的平均搜索時間為DQ的1.1倍.這是因為RLO采用了集束搜索策略,即RLO在每步決策時保存多個動作.但是帶來的好處是RLO的執(zhí)行效率更高(參見4.2.2小節(jié)).


本文編號：3252587