一個端到端的基于深度學習的查詢優(yōu)化引擎

孫佶 李國良

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

關鍵詞：數據庫;查詢優(yōu)化;深度學習;強化學習

中圖分類號：TP311.13? 文獻標識碼：A? 文章編號：1673-260X（2019）01-0001-05

1 背景介紹

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

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

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

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

本文有如下貢獻：

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

（2）設計一個數據表表示和基數估計聯合卷積神經網絡及其訓練方式，能夠提高模型的泛化并且支持數據更新之后的遷移學習.

（3）基于多集合卷積神經網絡設計出一個新的基于Q網絡的強化學習方法.

（4）設計一個查詢計劃生成器的校驗模塊，并且在校驗失敗之后能夠高效異步更新網絡模型.

2 系統概述

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

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

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

3 系統組件

3.1 基數估計模塊

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

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

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

之所以選擇的是平均而不是求和是因為這樣結果不會因為集合元素個數變化而變化.最終，模型拼接來自數據表，連接鍵，謂詞網絡的向量輸入給最后的輸出層MLP.除了輸出層，所有的MLP模塊都是兩層全連接神經網絡，激活函數是ReLU（x）=max（0，x）.對于輸出層MLP，模型最后一層使用sigmoid=1/（1+exp（-x））作為激活函數并且只輸出一個[0，1]之間的值.對于目標基數使用如下方法進行正則化：首先取log成為分布更加均勻的值，然后使用min-max方法正則化成為[0，1]之間的值，這種正則化方式是可逆的，之后可以從網絡輸出將基數恢復出來.訓練使得平均Q錯誤最小.

3.2 數據表示與基數估計聯合訓練

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

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

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

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

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

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

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

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

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

3.4 查詢計劃驗證模塊

這部分的目的是在運行中驗證模型對于當前來的查詢是否有效，如果失效，則需要更新模型參數.這部分需要使用生成計劃效果估計，最終基數估計，總代價估計，離線重訓練這四個部分.

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

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

參考文獻：

〔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.