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

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

【文章頁(yè)數(shù)】：12 頁(yè)

【部分圖文】：

(網(wǎng)絡(luò)版彩圖)RLO優(yōu)化器框架

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

其次,RLO算法的搜索效率在關(guān)系數(shù)目較多的時(shí)候占有較大的優(yōu)勢(shì).例如對(duì)于較多的關(guān)系數(shù),RLO和DQ算法實(shí)現(xiàn)了極大的提速:RLO最多可以比EX快104倍,比ZZ快100倍,比LD,RD快10倍以上.平均來說,當(dāng)關(guān)系數(shù)大于6時(shí),RLO算法比EX快2867倍,比ZZ快56倍,比LD,RD快5.6倍.原因與我們之前的分析相同,RLO具有貪心算法的時(shí)間復(fù)雜度,遠(yuǎn)快于動(dòng)態(tài)規(guī)劃.另外,GD,QP一直保持著最小的優(yōu)化時(shí)間,這是因?yàn)樗鼈兗糁Φ牟呗蕴珖?yán)格,忽略了大部分的解空間,這會(huì)導(dǎo)致較差的執(zhí)行效率(參見4.2.2小節(jié)).最后,RLO的搜索效率略差于DQ算法.例如RLO的平均搜索時(shí)間為DQ的1.1倍.這是因?yàn)镽LO采用了集束搜索策略,即RLO在每步?jīng)Q策時(shí)保存多個(gè)動(dòng)作.但是帶來的好處是RLO的執(zhí)行效率更高(參見4.2.2小節(jié)).


本文編號(hào)：3252587