孫佶 李國良

摘要：數(shù)據(jù)庫查詢優(yōu)化迄今已經(jīng)在數(shù)據(jù)庫領(lǐng)域廣泛研究數(shù)十年，一個(gè)好的查詢優(yōu)化器對于數(shù)據(jù)庫性能來說是至關(guān)重要的，但是不論是傳統(tǒng)的基于統(tǒng)計(jì)和采樣的基數(shù)估計(jì)還是多表連接物理計(jì)劃生成，在一些真實(shí)數(shù)據(jù)集上效果依然不盡如人意.深度學(xué)習(xí)是當(dāng)前被廣泛研究和使用的基于神經(jīng)網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)算法，但是將深度學(xué)習(xí)應(yīng)用到數(shù)據(jù)庫系統(tǒng)中卻是學(xué)術(shù)界近幾年剛開始的嘗試.我們結(jié)合傳統(tǒng)主流數(shù)據(jù)庫查詢優(yōu)化器的架構(gòu)以及學(xué)術(shù)界最近的數(shù)據(jù)庫查詢優(yōu)化進(jìn)展，分析了目前查詢優(yōu)化所面臨的痛點(diǎn)，并且利用深度神經(jīng)網(wǎng)絡(luò)模型和深度強(qiáng)化學(xué)習(xí)模型分別提升數(shù)據(jù)庫查詢基數(shù)估計(jì)和查詢計(jì)劃生成的時(shí)間性能和效果，最后，我們提出基于規(guī)則和基于置信度的兩種計(jì)劃驗(yàn)證方法以及高效異步模型更新方法.我們提出的端到端的基于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫查詢優(yōu)化引擎在標(biāo)準(zhǔn)測試集和真實(shí)數(shù)據(jù)機(jī)上的性能和效果要顯著優(yōu)于傳統(tǒng)數(shù)據(jù)庫Postgresql中的優(yōu)化器.

關(guān)鍵詞：數(shù)據(jù)庫;查詢優(yōu)化;深度學(xué)習(xí);強(qiáng)化學(xué)習(xí)

中圖分類號：TP311.13? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2019）01-0001-05

1 背景介紹

查詢優(yōu)化器是數(shù)據(jù)庫系統(tǒng)中的一個(gè)組件，用來為查詢選擇一個(gè)高效的執(zhí)行策略以使得資源消耗最小.當(dāng)前，多表連接查詢優(yōu)化是查詢優(yōu)化的重要任務(wù)，用戶輸入的包含多表的連接查詢對于不同的查詢執(zhí)行計(jì)劃有著非常不同的代價(jià)消耗.在數(shù)據(jù)庫中，查詢優(yōu)化器會估計(jì)若干表連接的最終結(jié)果大小即“基數(shù)”，由于表連接的代價(jià)和連接“基數(shù)”有著明顯的正相關(guān)關(guān)系，所以傳統(tǒng)優(yōu)化器可以通過基數(shù)來選擇合適的查詢順序來執(zhí)行當(dāng)前的多表連接查詢.

傳統(tǒng)數(shù)據(jù)庫中基于代價(jià)的多表連接查詢順序選擇以動態(tài)規(guī)劃方法和一些啟發(fā)式算法為主，以經(jīng)典數(shù)據(jù)庫Postgresql為例，其連接順序選擇算法包括“LEFT-DEEP”和遺傳算法兩種[1]，但是這兩種方法存在以下問題：（1）“LEFT-DEEP”動態(tài)規(guī)劃算法在多表情況下效率很低，并且生成的“LEFT-DEEP”查詢計(jì)劃是次優(yōu)的.（2）遺傳算法能夠保證效率，但由于啟發(fā)式算法的特點(diǎn)，產(chǎn)生的查詢計(jì)劃往往比動態(tài)規(guī)劃算法要差.（3）Postgresql采用的是靜態(tài)查詢計(jì)劃生成方法，即使對于一條查詢語句優(yōu)化失效，系統(tǒng)也無法利用真實(shí)的計(jì)劃執(zhí)行性能獲得反饋來動態(tài)調(diào)整優(yōu)化策略.（4）傳統(tǒng)優(yōu)化器往往基于一個(gè)線性的代價(jià)模型作為估計(jì)的代價(jià)，但是真實(shí)環(huán)境下代價(jià)和基數(shù)之間的關(guān)系更加復(fù)雜，線性估計(jì)經(jīng)常導(dǎo)致生成的查詢計(jì)劃是次優(yōu)的.

經(jīng)過近四十年的發(fā)展，數(shù)據(jù)庫系統(tǒng)依然受困于糟糕的查詢計(jì)劃，而次優(yōu)的查詢計(jì)劃除了次優(yōu)的查詢優(yōu)化生成器因素之外通常還會由糟糕的基數(shù)估計(jì)導(dǎo)致[2].基本上所有的工業(yè)級別的數(shù)據(jù)管理系統(tǒng)依賴于一些定長的、針對屬性的統(tǒng)計(jì)信息以及一些諸如均勻性，獨(dú)立性，包含性，特定常量的強(qiáng)假設(shè)，大多數(shù)數(shù)據(jù)庫系統(tǒng)嘗試將任意一個(gè)大的數(shù)據(jù)庫擬合到一個(gè)常量大小的空間里，所以這些方法對于交叉連接的查詢會失效.對于真實(shí)的數(shù)據(jù)集來說，基數(shù)估計(jì)錯(cuò)誤往往是很大的.這些錯(cuò)誤導(dǎo)致了查詢效率低下并且性能無法預(yù)測.另一種很有前景的替代基于直方圖估計(jì)的方法是采樣，因?yàn)樗梢詸z測出任意的關(guān)聯(lián)性從而生成準(zhǔn)確的基數(shù)估計(jì).然而，盡管已經(jīng)被研究了數(shù)十年，很少有系統(tǒng)在生產(chǎn)中實(shí)際采用采樣的方法估計(jì)基數(shù).其中一個(gè)原因是過去的內(nèi)存空間很小，采樣技術(shù)由于隨機(jī)磁盤讀寫的代價(jià)太高而不現(xiàn)實(shí).另一個(gè)原因是無論采樣多少條記錄，對于估計(jì)多表查詢的結(jié)果基數(shù)也是不夠的，如果增加一個(gè)連接表會快速減少采樣結(jié)果的數(shù)量，那么系統(tǒng)使用采樣進(jìn)行基數(shù)估計(jì)也是不可行的.最近的工作利用連接的表的索引大大增加了采樣估計(jì)結(jié)果的準(zhǔn)確度，減少了采樣的代價(jià)，按時(shí)如果在缺少索引的情況下依然會退化，結(jié)果的準(zhǔn)確性變得不可預(yù)測，甚至?xí)?dǎo)致很大的錯(cuò)誤.在采樣數(shù)據(jù)和統(tǒng)計(jì)信息缺少的情況下，傳統(tǒng)算法很難對執(zhí)行結(jié)果行數(shù)進(jìn)行準(zhǔn)確估計(jì).

基于上述背景，本文提出一個(gè)新穎的基于端到端深度神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)庫查詢優(yōu)化引擎.針對基數(shù)估計(jì)不準(zhǔn)的問題，我們利用一個(gè)深度多集合卷積神經(jīng)網(wǎng)絡(luò)（MSCN）[7]與卷積神經(jīng)網(wǎng)絡(luò)（CNN）[10]構(gòu)成的聯(lián)合訓(xùn)練網(wǎng)絡(luò)模型實(shí)現(xiàn)對任意查詢的基數(shù)準(zhǔn)確估計(jì)，MSCN模型層數(shù)少效率高，具有很強(qiáng)的查詢特征表達(dá)能力，能夠?qū)崿F(xiàn)對實(shí)際負(fù)載查詢基數(shù)的精確估計(jì);而CNN可以利用卷積核實(shí)現(xiàn)對于數(shù)據(jù)表的特征抽取.針對傳統(tǒng)數(shù)據(jù)庫多表連接查詢優(yōu)化算法效率低，效果次優(yōu)的問題，本文使用一個(gè)深度強(qiáng)化Q-學(xué)習(xí)模型來構(gòu)建新型的多表連接查詢計(jì)劃優(yōu)化引擎[6，8]，該查詢優(yōu)化具有高效率，強(qiáng)魯棒性，動態(tài)靈活的特點(diǎn)，而且能夠增量在線調(diào)節(jié)模型使得查詢計(jì)劃生成器能夠隨著負(fù)載變化而進(jìn)化.本文提出的引擎沒有對代價(jià)模型做更多的考慮，這是由于（1）基于強(qiáng)化學(xué)習(xí)的優(yōu)化器在啟動訓(xùn)練中能夠從實(shí)際執(zhí)行中獲得反饋進(jìn)行自我調(diào)整從而對代價(jià)模型有著很強(qiáng)的魯棒性，（2）基數(shù)估計(jì)的精度要比代價(jià)模型更加重要.我們在真實(shí)測試集“JOB”上將我們的引擎與Postgresql從基數(shù)估計(jì)，多表連接順序選擇，執(zhí)行計(jì)劃生成效率三個(gè)方面進(jìn)行了對比，實(shí)驗(yàn)顯示我們的優(yōu)化引擎無論在效率還是效果都有顯著提高.

本文有如下貢獻(xiàn)：

（1）提出一個(gè)端到端的基于深度學(xué)習(xí)的查詢優(yōu)化框架.

（2）設(shè)計(jì)一個(gè)數(shù)據(jù)表表示和基數(shù)估計(jì)聯(lián)合卷積神經(jīng)網(wǎng)絡(luò)及其訓(xùn)練方式，能夠提高模型的泛化并且支持?jǐn)?shù)據(jù)更新之后的遷移學(xué)習(xí).

（3）基于多集合卷積神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)出一個(gè)新的基于Q網(wǎng)絡(luò)的強(qiáng)化學(xué)習(xí)方法.

（4）設(shè)計(jì)一個(gè)查詢計(jì)劃生成器的校驗(yàn)?zāi)K，并且在校驗(yàn)失敗之后能夠高效異步更新網(wǎng)絡(luò)模型.

2 系統(tǒng)概述

訓(xùn)練：整個(gè)系統(tǒng)分為如下圖所示的幾個(gè)部分，作為一個(gè)端到端的查詢優(yōu)化引擎，系統(tǒng)支持冷啟動，每部分的網(wǎng)絡(luò)都有其特定的功能而可以分階段訓(xùn)練，面對復(fù)雜的場景具有高效靈活易部署的特點(diǎn).部署在一個(gè)數(shù)據(jù)庫上時(shí)，首先使用配套的訓(xùn)練集生成器生成訓(xùn)練查詢語句，通過實(shí)際執(zhí)行獲得每條語句的真實(shí)執(zhí)行代價(jià)和真實(shí)結(jié)果基數(shù)，然后訓(xùn)練多集合卷積網(wǎng)絡(luò)直到驗(yàn)證數(shù)據(jù)集上的Q錯(cuò)誤達(dá)到最小的值后停止訓(xùn)練.在執(zhí)行計(jì)劃生成部分，對每一條語句建立一個(gè)連接邊池，每一步從池子中選擇一條邊作為動作，生成的當(dāng)前計(jì)劃作為查詢語句輸入之前訓(xùn)練好的基數(shù)估計(jì)網(wǎng)絡(luò)計(jì)算當(dāng)前子查詢估計(jì)的基數(shù)，之后再使用選擇的代價(jià)模型計(jì)算代價(jià)作為回報(bào)，使用回報(bào)和當(dāng)前Q網(wǎng)絡(luò)計(jì)算下一個(gè)狀態(tài)對應(yīng)的Q值，將這個(gè)值與直接使用歷史Q網(wǎng)絡(luò)計(jì)算出的下個(gè)狀態(tài)的Q值的差值作為損失函數(shù)來訓(xùn)練網(wǎng)絡(luò).注意到每條語句結(jié)束之后對應(yīng)的完整的計(jì)劃都有個(gè)真實(shí)的代價(jià)，直接根據(jù)這個(gè)真實(shí)的代價(jià)可以對Q網(wǎng)絡(luò)進(jìn)行細(xì)調(diào)節(jié)使得模型對于不同代價(jià)模型的魯棒性更好.

應(yīng)用：對于任意一條SQL語句，首先抽取其所有的連接邊放入一個(gè)池子，任意選取一個(gè)表作為初始狀態(tài)，使用深度強(qiáng)化學(xué)習(xí)模型中獲得狀態(tài)對應(yīng)的一個(gè)動作（下一個(gè)需要連接的表），生成的兩表連接作為下一個(gè)狀態(tài)，輸入模型獲得進(jìn)一步的連接，循環(huán)上述步驟直到所有連接都已經(jīng)使用，輸出一個(gè)優(yōu)化之后的執(zhí)行計(jì)劃.這個(gè)執(zhí)行計(jì)劃可以交給傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)來選擇合適的物理操作，然后執(zhí)行操作，返回結(jié)果.

驗(yàn)證計(jì)劃：和基數(shù)估計(jì)相比，執(zhí)行計(jì)劃生成是個(gè)更加復(fù)雜的問題，所以會不可避免地出現(xiàn)對于某些查詢語句生成次優(yōu)的執(zhí)行計(jì)劃甚至于查詢優(yōu)化失效的情況.但是幸運(yùn)的是，深度強(qiáng)化學(xué)習(xí)可以針對每一條查詢語句進(jìn)行快速的增量訓(xùn)練.對于每一條查詢語句，利用用戶指定的規(guī)則或者當(dāng)前執(zhí)行計(jì)劃的置信度判斷是否失效，如果可能失效，比較當(dāng)前生成計(jì)劃和傳統(tǒng)查詢優(yōu)化器生成的計(jì)劃總代價(jià)，如果比傳統(tǒng)優(yōu)化器生成的計(jì)劃代價(jià)要高則利用當(dāng)前的查詢進(jìn)行訓(xùn)練來更新Q-網(wǎng)絡(luò).模型驗(yàn)證和更新基本不會影響整體優(yōu)化效率，因?yàn)椋?）訓(xùn)練單條語句的效率很高，只有幾十毫秒的量級.（2）模型不需要同步更新，舊的模型可以繼續(xù)優(yōu)化新來的查詢，當(dāng)模型更新完成之后，將新的參數(shù)更新到活動空間中即可.

3 系統(tǒng)組件

3.1 基數(shù)估計(jì)模塊

Andreas Kipf[7]等提出的多集合卷積神經(jīng)網(wǎng)絡(luò)（MSCN）是一種較為有效的深度學(xué)習(xí)模型來估計(jì)查詢代價(jià)，該網(wǎng)絡(luò)能夠利用查詢語句的表示和集合語義學(xué)習(xí)查詢的特征和真實(shí)的結(jié)果基數(shù).MSCN解決了基于采樣方法在缺少有效采樣情況下無法工作的問題，并且能夠有效獲得連接的多表的相關(guān)性.但是MSCN模型也具有泛化能力不足，依賴記憶等缺點(diǎn).

基于集合的查詢表示：一條表連接查詢語句包括三個(gè)部分，數(shù)據(jù)源，連接條件（相等連接），查詢條件.首先收集整個(gè)數(shù)據(jù)庫中所有的數(shù)據(jù)屬性構(gòu)造一個(gè)屬性全集，根據(jù)這個(gè)全集對查詢屬性進(jìn)行獨(dú)熱編碼.數(shù)據(jù)源根據(jù)數(shù)據(jù)表全集進(jìn)行獨(dú)熱編碼，查詢條件的比較操作則根據(jù)操作全集進(jìn)行獨(dú)熱編碼，查詢條件右值如果是數(shù)值型則利用表中的統(tǒng)計(jì)信息歸一化成0和1之間的浮點(diǎn)型數(shù)值，如果是字符串則使用訓(xùn)練出來的單詞編碼.對于一張數(shù)據(jù)表，除了獨(dú)熱編碼表之外還需要額外的信息來幫助模型理解查詢條件，比如當(dāng)前查詢中每個(gè)數(shù)據(jù)表有多少行被查詢條件選中或者是采樣中選中位置設(shè)為1的一個(gè)位圖向量，但是無論是選擇率還是位圖都不能反映表的重要內(nèi)容信息，如果希望神經(jīng)網(wǎng)絡(luò)能夠?qū)W習(xí)到數(shù)據(jù)的高階內(nèi)容和規(guī)律而達(dá)到泛化和快速收斂的目的，必須要包含更多的信息，否則模型只是一個(gè)“記憶”的過程而且容易發(fā)生采樣向量全零的問題，這部分內(nèi)容由下一個(gè)小節(jié)（數(shù)據(jù)表示與基數(shù)估計(jì)聯(lián)合訓(xùn)練）來介紹.

MSCN模型介紹：多集合卷積模型是基于在排列不變的集合S上的任何函數(shù)f（S）都可以分解成 ？籽[∑x∈s？覬（x）]，可以使用多層神經(jīng)網(wǎng)絡(luò)（MLPs）來描述參數(shù)？籽和？覬并且依賴它們的函數(shù)擬合能力學(xué)習(xí)映射f（S）.對于查詢的表示包括了多個(gè)集合，對于每一個(gè)集合，都可以學(xué)習(xí)一個(gè)神經(jīng)網(wǎng)絡(luò)MLPs（vs）.集合中的每一個(gè)元素都會經(jīng)過一個(gè)MLP的變換：

之所以選擇的是平均而不是求和是因?yàn)檫@樣結(jié)果不會因?yàn)榧显貍€(gè)數(shù)變化而變化.最終，模型拼接來自數(shù)據(jù)表，連接鍵，謂詞網(wǎng)絡(luò)的向量輸入給最后的輸出層MLP.除了輸出層，所有的MLP模塊都是兩層全連接神經(jīng)網(wǎng)絡(luò)，激活函數(shù)是ReLU（x）=max（0，x）.對于輸出層MLP，模型最后一層使用sigmoid=1/（1+exp（-x））作為激活函數(shù)并且只輸出一個(gè)[0，1]之間的值.對于目標(biāo)基數(shù)使用如下方法進(jìn)行正則化：首先取log成為分布更加均勻的值，然后使用min-max方法正則化成為[0，1]之間的值，這種正則化方式是可逆的，之后可以從網(wǎng)絡(luò)輸出將基數(shù)恢復(fù)出來.訓(xùn)練使得平均Q錯(cuò)誤最小.

3.2 數(shù)據(jù)表示與基數(shù)估計(jì)聯(lián)合訓(xùn)練

數(shù)據(jù)表特征編碼：一維深度卷積神經(jīng)網(wǎng)絡(luò)要求輸入向量為定長定高，假設(shè)定長N為表的行數(shù)，表的屬性個(gè)數(shù)作為通道數(shù)設(shè)定為M（M是數(shù)據(jù)庫中所有數(shù)據(jù)表最大的行向量的長度）.對于行數(shù)大于N的數(shù)據(jù)表，采樣N條記錄，反之，對于行數(shù)不足N的數(shù)據(jù)表，使用0值擴(kuò)充至N長度向量.類似地，對于一行向量長度不足M的數(shù)據(jù)表使用0值擴(kuò)充.每個(gè)數(shù)據(jù)表中，數(shù)值型的值可以采用最大最小正則化表示，類別型數(shù)據(jù)使用獨(dú)熱編碼表示.對于字符串類型值，則需要借助其他屬性以及數(shù)據(jù)庫中主鍵外鍵連接關(guān)系訓(xùn)練一個(gè)嵌入式特征編碼，原理和自然語言處理中的分布式詞向量構(gòu)造類似，使在數(shù)據(jù)庫全表上有潛在連接關(guān)系的兩個(gè)值編碼的余弦距離接近.數(shù)據(jù)表中所有的元素添加表名作為前綴加入詞庫，直接關(guān)聯(lián)的主鍵和外鍵當(dāng)作是同一個(gè)詞（選擇主鍵的表名作為前綴），掃描全數(shù)據(jù)庫，生成訓(xùn)練元組，每個(gè)元組看作是自然語言中的一句話，使用神經(jīng)網(wǎng)絡(luò)語言模型（NNLM）[9]進(jìn)行訓(xùn)練.

訓(xùn)練集生成：和傳統(tǒng)MSCN一樣，本模型也可以在獲得實(shí)際負(fù)載之前訓(xùn)練模型.方法是根據(jù)模式信息生成隨機(jī)的查詢并且從實(shí)際的數(shù)據(jù)庫中逐個(gè)選取值.一個(gè)訓(xùn)練實(shí)例包括表標(biāo)號，連接謂詞，基表謂詞，和查詢真實(shí)的基數(shù).訓(xùn)練集分為兩部分，一部分只包含涉及小于等于兩個(gè)表的查詢用于聯(lián)合訓(xùn)練數(shù)據(jù)表表示，另一部分各種規(guī)模查詢均勻分布用于MSCN模型的訓(xùn)練.具體地，訓(xùn)練集查詢生成器首先均勻選取連接數(shù)量|Jq|并且均勻選取一個(gè)具有至少一個(gè)連接的數(shù)據(jù)表.如果|Jq|>0，均勻選擇一個(gè)可以和之前選擇表連接的新表，添加對應(yīng)的連接邊，重復(fù)這個(gè)過程|Jq|次.對于查詢中的每個(gè)基表，均勻選擇|Ptq|個(gè)查詢條件（0<=|Ptq|<=非鍵列的數(shù)量）.對于每個(gè)謂詞，均勻從三種操作（=，<或者>）中選擇一個(gè)，并且從對應(yīng)的列中選擇一個(gè)真實(shí)值.最后對這些隨機(jī)查詢進(jìn)行去重，并且實(shí)際執(zhí)行獲得真實(shí)的基數(shù).

數(shù)據(jù)表編碼模型結(jié)構(gòu)：編碼結(jié)構(gòu)由兩個(gè)一維卷積層構(gòu)成，第一個(gè)卷積層，輸入每個(gè)值都已經(jīng)編碼的數(shù)據(jù)表，表的行數(shù)作為向量長度，表的列數(shù)作為表的高度（卷積通道數(shù)），第一層使用10個(gè)卷積核心增加向量的通道數(shù)，輸出之后經(jīng)過一層非線性激活層，再使用池化層減少向量長度.這個(gè)過程再做一次，最后將一個(gè)“高而短”的向量扁平化成一維且經(jīng)過一層線性全連接網(wǎng)絡(luò)輸出.

訓(xùn)練過程：由于訓(xùn)練數(shù)據(jù)表特征表示的輸入很大，每一個(gè)批次的訓(xùn)練要消耗很多計(jì)算資源，所以訓(xùn)練這部分網(wǎng)絡(luò)的時(shí)候不適合使用很大的查詢，所以第一階段聯(lián)合訓(xùn)練過程只選擇涉及兩個(gè)表以下的查詢，這種短查詢足夠覆蓋每個(gè)查詢條件對于單表選擇的影響以及每兩表之間的連接關(guān)系.第一階段結(jié)束之后，表的表示將被記錄在內(nèi)存中并且不再變化.之后使用所有生成的訓(xùn)練集，將3.1中的表集合表示成表序號獨(dú)熱編碼和數(shù)據(jù)表特征表示拼接的形式送入多集合卷積網(wǎng)絡(luò)進(jìn)行訓(xùn)練，對上層網(wǎng)絡(luò)參數(shù)進(jìn)行微調(diào)直到測試Q-錯(cuò)誤達(dá)到最小.

3.3 查詢計(jì)劃優(yōu)化模塊

Sanjay Krishnan等[8]證明使用強(qiáng)化學(xué)習(xí)優(yōu)化查詢連接順序的方法是可行的，但是這篇文章沒有提供具體的Q網(wǎng)絡(luò)設(shè)計(jì)細(xì)節(jié)，查詢語句編碼也過于簡單無法獲得連接條件，查詢條件以及數(shù)據(jù)表的高層內(nèi)容信息.為了提高模型精度和魯棒性，本文設(shè)計(jì)了一個(gè)基于多集合卷積神經(jīng)網(wǎng)絡(luò)的高效的Q網(wǎng)絡(luò)并且說明訓(xùn)練方法.

狀態(tài)編碼：強(qiáng)化學(xué)習(xí)過程中影響下一步連接決策的因素有當(dāng)前已經(jīng)連接數(shù)據(jù)表生成的中間結(jié)果，下一步可選的連接邊集合，下一步每一步連接的代價(jià)以及未來可能的代價(jià)期望.使用基數(shù)估計(jì)模塊提供的編碼方式完全可以滿足強(qiáng)化學(xué)習(xí)的狀態(tài)表示，即采用表集合，連接鍵集合和查詢條件謂詞集合來表示.

Q網(wǎng)絡(luò)設(shè)計(jì)：對于同一個(gè)連接圖，基于基數(shù)估計(jì)模塊訓(xùn)練出來的數(shù)據(jù)表表示以及底層的三個(gè)多集合卷積網(wǎng)絡(luò)可以復(fù)用，而且由于同一個(gè)數(shù)據(jù)庫中數(shù)據(jù)分布和數(shù)據(jù)表之間的連接關(guān)系也是不變的，所以底層網(wǎng)絡(luò)的網(wǎng)絡(luò)參數(shù)也可以復(fù)用.這里我們在原有的上層MSCN網(wǎng)絡(luò)下部增加了一個(gè)新的MSCN網(wǎng)絡(luò)，將最后一個(gè)激活函數(shù)修改為輸出函數(shù)Softmax輸出多個(gè)概率分布用來選擇動作.上層網(wǎng)絡(luò)如下圖所示：

公式中？茲是上層Q網(wǎng)絡(luò)的網(wǎng)絡(luò)參數(shù)，？琢是衰減系數(shù)，G是狀態(tài)，a是選擇的連接動作，Q是Q-學(xué)習(xí)的值.對于產(chǎn)生的每一個(gè)新狀態(tài)，我們利用之前訓(xùn)練出來的基數(shù)估計(jì)和代價(jià)估計(jì)器生成的代價(jià)作為代價(jià)，這個(gè)代價(jià)要比Postgres估計(jì)器生成的代價(jià)更加準(zhǔn)確，而在線生成訓(xùn)練集比使用離線的動態(tài)規(guī)劃代價(jià)表中的子計(jì)劃收斂更快.而在驗(yàn)證階段使用失效查詢語句在線訓(xùn)練更新Q網(wǎng)絡(luò)的時(shí)候，需要的僅僅是查詢語句本身以及最終執(zhí)行完的實(shí)際代價(jià)，中間的代價(jià)從代價(jià)估計(jì)器中獲得或者直接設(shè)置為0效率更高.

3.4 查詢計(jì)劃驗(yàn)證模塊

這部分的目的是在運(yùn)行中驗(yàn)證模型對于當(dāng)前來的查詢是否有效，如果失效，則需要更新模型參數(shù).這部分需要使用生成計(jì)劃效果估計(jì)，最終基數(shù)估計(jì)，總代價(jià)估計(jì)，離線重訓(xùn)練這四個(gè)部分.

基于規(guī)則驗(yàn)證：用戶可以對每個(gè)數(shù)據(jù)庫設(shè)置一些計(jì)劃驗(yàn)證啟動規(guī)則，比如某種查詢的執(zhí)行時(shí)間期望上界，當(dāng)這些規(guī)則被違反之后，系統(tǒng)會另開一個(gè)異步進(jìn)程去進(jìn)行驗(yàn)證，如果發(fā)現(xiàn)優(yōu)化器對于當(dāng)前查詢語句失效，那么就會啟動模型細(xì)致調(diào)節(jié)，調(diào)節(jié)的時(shí)候確保Q網(wǎng)絡(luò)的底下兩層參數(shù)不動，只調(diào)整最后輸出層的參數(shù)，這樣可以在確保有效調(diào)節(jié)的基礎(chǔ)上大大提高訓(xùn)練效率，使得調(diào)整之后的模型能夠盡快應(yīng)用.模型訓(xùn)練完成之后，凍結(jié)數(shù)據(jù)庫更新內(nèi)存中對應(yīng)位置的參數(shù)，凍結(jié)時(shí)間非常短（亞毫秒級別）.

基于置信度驗(yàn)證：基于深度強(qiáng)化學(xué)習(xí)本身可以做到利用置信度自動檢測模型對于當(dāng)前查詢是否適用.方法是每一個(gè)連接決策的時(shí)候在Q網(wǎng)絡(luò)輸出層的分布進(jìn)行采樣，獲得最小Q值區(qū)域的累積概率，將這個(gè)概率當(dāng)作是下一個(gè)選擇的連接的置信度，把一條完整語句生成計(jì)劃的過程中最小的一個(gè)置信度作為當(dāng)前語句的置信度，如果這個(gè)置信度小于一個(gè)閾值，那么就可以判定模型參數(shù)需要更新.

參考文獻(xiàn)：

〔1〕Gregory Smith. PostgreSQL 9.0 High Performance[M]. Packt Publishing，2010.

〔2〕Viktor Leis， et al. How Good Are Query Optimizers， Really？[C]. Proceedings of the VLDB Endowment，2015，9-3：204-215.

〔3〕Viktor Leis， et al. Cardinality Estimation Done Right： Index-Based Join Sampling[C]. 7th Biennial Conference on Innovative Data Systems Research （CIDR ‘17）， 2017.

〔4〕W. Wu， et al. Predicting query execution time： Are optimizer cost models really unusable？ Data Engineering （ICDE）， 2013， 1081–1092.

〔5〕R. Bellman. Dynamic programming[M]. Princeton University Press， 1957.

〔6〕V. Mnih， et al. Human-level control through deep reinforcement learning. In Nature. Nature Research， 2015.

〔7〕Andreas Kipf， etal. Learned Cardinalities： Estimating Correlated Joins with Deep Learning[C]. 9th Biennial Conference on Innovative Data Systems Research （CIDR ‘19）， 2019.

〔8〕Sanjay Krishnan， et al. Learning to Optimize Join Queries With Deep Reinforcement Learning[DB]. CoRR， 2018， abs/1808.03196.

〔9〕Yoshua Bengio， et al. A Neural Probabilistic Language Model[C]. Journal of Machine Learning Research， 2003， 1137–1155.

〔10〕Alex Krizhevsky， et al. ImageNet Classification with Deep Convolutional Neural Networks[C]. NIPS， 2012， 1106-1114.