0
| 本文作者： 知情人士 | 2021-08-19 17:44 |
作者 | 琰琰
8月18日，VLDB 2021公布了今年的論文獲獎(jiǎng)情況，SFU王健楠教授及博士生團(tuán)隊(duì)（王笑盈，曲昌博，吳畏遠(yuǎn)）獲得年度最佳EA&B論文獎(jiǎng)。
VLDB （Very Large Data Base ），與 SIGMOD、ICDE 被公認(rèn)為數(shù)據(jù)管理與數(shù)據(jù)庫(kù)領(lǐng)域的三大國(guó)際頂尖學(xué)術(shù)會(huì)議。8月18日，VLDB 2021采用線上線下結(jié)合的方式在丹麥哥本哈根正式開幕。VLDB的研究論文分為三個(gè)類別，王健楠團(tuán)隊(duì)獲得了實(shí)驗(yàn)、分析與基準(zhǔn)（Experiment, Analysis and Benchmark ，EA&B）類別的最佳論文。
王健楠是SFU計(jì)算機(jī)系的副教授。他于2013 年在清華大學(xué)獲得博士學(xué)位，2013 年 -2015 年間在加州大學(xué)伯克利分校AMPLab進(jìn)行博士后階段的研究工作。他領(lǐng)導(dǎo)開發(fā)的數(shù)據(jù)準(zhǔn)備工具dataprep.ai 目前已經(jīng)有近 20 萬的下載量。
所獲獎(jiǎng)項(xiàng)包括加拿大計(jì)算機(jī)協(xié)會(huì)授予的杰出青年獎(jiǎng) （2020），IEEE授予的數(shù)據(jù)工程新星獎(jiǎng)（2018），ACM SIGMOD 最佳演示獎(jiǎng)（2016），CCF最佳博士論文獎(jiǎng)（2013）以及Google PhD Fellowship （2011）。他為VLDB 2021副主編，將在VLDB 2023大會(huì)擔(dān)任共同主席。
其本次獲獎(jiǎng)?wù)撐念}目為“Are We Ready for Learned Cardinality Estimation"（《通過機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)成熟了嗎？》），與騰訊周慶慶合著完成。
VLDB組委會(huì)認(rèn)為，這篇研究工作概述了不同的基于學(xué)習(xí)的方法在數(shù)據(jù)庫(kù)產(chǎn)品中應(yīng)用的可能性及優(yōu)缺點(diǎn)，幾乎覆蓋了實(shí)際使用環(huán)境中可能出現(xiàn)的情況。此外，該工作提出了可用于改善現(xiàn)有相關(guān)研究的方法，并進(jìn)一步指出了未來需要的研究方向，為ML for DB研究領(lǐng)域的發(fā)展做出了重要貢獻(xiàn)。
研究概要
近幾年，機(jī)器學(xué)習(xí)以及深度學(xué)習(xí)方面技術(shù)的進(jìn)步以及在其它領(lǐng)域內(nèi)被成功應(yīng)用的先例，讓 ML for DB 這個(gè)課題變得越來越火，今年VLDB會(huì)議的Keynote，Workshop，Tutorial以及Session都在討論這個(gè)話題。
王健楠告訴AI科技評(píng)論，基于學(xué)習(xí)的方法（Learned Methods）是數(shù)據(jù)庫(kù)領(lǐng)域的熱門研究方向，但是現(xiàn)有研究過于關(guān)注模型的準(zhǔn)確度，而忽略了其在部署到實(shí)際數(shù)據(jù)庫(kù)系統(tǒng)時(shí)可能會(huì)面臨的問題。這篇論文希望扭轉(zhuǎn)當(dāng)前的研究重心，讓大家關(guān)注“如何如何降低模型成本？如何提高模型更可信性？”等重要問題。
按照目前ML for DB課題的發(fā)展情況來看，5-10年之后要么是研究人員發(fā)現(xiàn)模型并不能被真正的使用在生產(chǎn)環(huán)境中，漸漸的失去對(duì)該課題的研究興趣；要么是主流的數(shù)據(jù)庫(kù)系統(tǒng)開始大規(guī)模采用機(jī)器學(xué)習(xí)模型，并大幅提升了系統(tǒng)性能。
要想將第二種情況變?yōu)楝F(xiàn)實(shí)，王健楠團(tuán)隊(duì)認(rèn)為我們現(xiàn)在需要回答一個(gè)核心問題，即基于機(jī)器學(xué)習(xí)的方法是否已經(jīng)可以使用在數(shù)據(jù)庫(kù)產(chǎn)品中？如果不行，需要從哪些方面進(jìn)行提升？
在本篇論文中，研究團(tuán)隊(duì)從基數(shù)估計(jì)模塊入手，探究了基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)方法是否可用于數(shù)據(jù)庫(kù)產(chǎn)品這個(gè)問題。基數(shù)估計(jì) (Cardinality Estimation)是數(shù)據(jù)庫(kù)優(yōu)化器（optimizer）中非常重要的一個(gè)模塊，該模塊會(huì)向優(yōu)化器提供查詢（query）可能返回的行數(shù)，從而引導(dǎo)查詢計(jì)劃（query plan）的選擇，并直接影響甚至決定查詢的速度。
由于現(xiàn)有基數(shù)估計(jì)方法很難做到精確估計(jì)，有時(shí)甚至?xí)疠^大誤差，從而減緩查詢速度，因此基數(shù)估計(jì)一直被稱為數(shù)據(jù)庫(kù)優(yōu)化器的“阿喀琉斯之踵”（意為“致命要害”）。
目前采用機(jī)器學(xué)習(xí)或深度學(xué)習(xí)來預(yù)測(cè)基數(shù)的研究方法不在少數(shù)，并且這些方法在準(zhǔn)確度上也展現(xiàn)了超越傳統(tǒng)數(shù)據(jù)庫(kù)中基數(shù)估計(jì)方法的極大潛能。
研究方法
在論文中，作者選擇了5個(gè)先進(jìn)且不同的基于學(xué)習(xí)的模型，通過實(shí)驗(yàn)評(píng)估了其在數(shù)據(jù)庫(kù)產(chǎn)品應(yīng)用的可能性、可能引發(fā)的問題，并進(jìn)一步為數(shù)據(jù)庫(kù)中除基數(shù)估計(jì)之外的其它模塊應(yīng)用機(jī)器學(xué)習(xí)提供參考。實(shí)驗(yàn)主要分成三個(gè)部分：
1、基于學(xué)習(xí)的方法是否適合靜態(tài)環(huán)境？
靜態(tài)環(huán)境是指數(shù)據(jù)庫(kù)中的數(shù)據(jù)不進(jìn)行更新的狀態(tài)。作者首先評(píng)估了靜態(tài)環(huán)境下，基于學(xué)習(xí)的基數(shù)估計(jì)方法與傳統(tǒng)方法在準(zhǔn)確度和效率（包括訓(xùn)練時(shí)間和推斷時(shí)間）兩個(gè)維度上的實(shí)驗(yàn)結(jié)果。
實(shí)驗(yàn)選取了3個(gè)廣泛應(yīng)用的數(shù)據(jù)庫(kù)產(chǎn)品和6個(gè)常用以及最新的傳統(tǒng)基數(shù)估計(jì)方法作為基準(zhǔn)，并且選擇了4個(gè)常用的且具有不同屬性的數(shù)據(jù)集。通過研究現(xiàn)有工作中的SQL查詢生成方法，作者提出了一個(gè)更能涵蓋所有可能的查詢生成框架，并通過它來生成實(shí)驗(yàn)所需要的訓(xùn)練和測(cè)試數(shù)據(jù)。
q誤差比較結(jié)果
實(shí)驗(yàn)表明，學(xué)習(xí)的方法在幾乎所有的數(shù)據(jù)庫(kù)系統(tǒng)中都比傳統(tǒng)方法的準(zhǔn)確度更高，最好的學(xué)習(xí)的方法可以在最大q-誤差指標(biāo)上超過傳統(tǒng)方法14x，在Census、Forest、Power和DMV數(shù)據(jù)集上，三個(gè)數(shù)據(jù)庫(kù)系統(tǒng)上分別達(dá)到28x、51x、938x和1758x。
在所有學(xué)習(xí)的方法中，Naru最穩(wěn)健、準(zhǔn)確度最高，其最大誤差均保持在200以內(nèi)。
在訓(xùn)練時(shí)間和推理時(shí)間方面，這些高精度學(xué)習(xí)方法與DBMS產(chǎn)品進(jìn)行了比較。如下圖，三個(gè)DBMS都可以在1或2毫秒內(nèi)完成整個(gè)過程，相較于擬合整個(gè)數(shù)據(jù)分布來估算基數(shù)的學(xué)習(xí)方法，通過回歸模型的方法能夠達(dá)到與DBMS相似或更好的查詢效率。
DeepDB中的SPN模型在三個(gè)較大的數(shù)據(jù)集上需要大約25ms，在Census數(shù)據(jù)集中平均需要5ms。Naru的推理過程包括一個(gè)漸進(jìn)式抽樣機(jī)制，需要將模型運(yùn)行數(shù)千次才能得到準(zhǔn)確的結(jié)果。它的總時(shí)間對(duì)運(yùn)行的設(shè)備很敏感，在GPU上需要5到15毫秒，CPU的速度可以慢20倍。
超參數(shù)調(diào)整是學(xué)習(xí)方法的另一個(gè)成本。如果沒有超參數(shù)調(diào)整，學(xué)習(xí)的模型可能會(huì)表現(xiàn)得非常糟糕。實(shí)驗(yàn)發(fā)現(xiàn)，對(duì)于同一種方法，具有不同超參數(shù)的模型之間的最大q誤差與最小q誤差之比可以達(dá)到10的5次方。
一般情況下，我們需要訓(xùn)練多個(gè)模型才能找到最佳超參數(shù)。如上圖，Naru在帶有GPU的DMV上訓(xùn)練單個(gè)模型用了4個(gè)多小時(shí)。如果訓(xùn)練了五個(gè)模型，Naru可能需要20多個(gè)小時(shí)（幾乎一天）進(jìn)行超參數(shù)調(diào)整。
主要結(jié)論：基于機(jī)器學(xué)習(xí)的方法在準(zhǔn)確率上相比于傳統(tǒng)方法有比較大的提升。然而相比于傳統(tǒng)方法，除了 [Selectivity estimation for range predicates using lightweight models] 中的LW-XGB以外，機(jī)器學(xué)習(xí)方法需要更多的時(shí)間去訓(xùn)練模型，同時(shí)在模型運(yùn)行的時(shí)候也會(huì)更慢。
2、學(xué)習(xí)的方法是否是適合動(dòng)態(tài)環(huán)境？
“數(shù)據(jù)更新”在現(xiàn)實(shí)生產(chǎn)環(huán)境的數(shù)據(jù)庫(kù)中時(shí)常會(huì)發(fā)生，這使得基數(shù)估計(jì)器常處于一個(gè)“動(dòng)態(tài)”變化之中。
為了更加公平的比較基于學(xué)習(xí)的方法和現(xiàn)有的數(shù)據(jù)庫(kù)產(chǎn)品，需要在模型中引入一個(gè)動(dòng)態(tài)的框架。作者在本文提出了一個(gè)在動(dòng)態(tài)環(huán)境中符合數(shù)據(jù)和模型更新速度的評(píng)估基數(shù)估計(jì)模塊的方法，并且設(shè)計(jì)了一系列實(shí)驗(yàn)探討了基于學(xué)習(xí)類的方法在真實(shí)環(huán)境中應(yīng)該能夠如何調(diào)整。
以下為DBMS與不同數(shù)據(jù)集動(dòng)態(tài)環(huán)境下的5種學(xué)習(xí)方法。
T表示數(shù)據(jù)集的更新頻率：高、中、低
可以發(fā)現(xiàn)，與學(xué)習(xí)的方法相比，DBMS具有更穩(wěn)定的性能。其原因是DBMS的更新時(shí)間非常短，幾乎所有查詢都是在更新的統(tǒng)計(jì)數(shù)據(jù)上運(yùn)行的，而很多學(xué)習(xí)的方法無法跟上快速的數(shù)據(jù)更新，即使可以其性能也次于DBMS。
例如，當(dāng)DMV T=50 min時(shí)，DBMS-A的性能比DeepDB高出約100倍，因?yàn)楦碌腄eepDB模型無法很好地捕捉相關(guān)性變化。
作者進(jìn)一步探討了學(xué)習(xí)的方法的更新次數(shù)和準(zhǔn)確性之間的相關(guān)性。實(shí)驗(yàn)表明，當(dāng) Census T=10min，F(xiàn)orest T=100min時(shí)，“Dynamic”（代表Naru在10K查詢中的性能）是先下降后逐漸回升的，這表明訓(xùn)練時(shí)間增加，模型更新緩慢，使未更新的模型執(zhí)行了更多的查詢。雖然多次迭代改進(jìn)了更新模型的性能，但損害了整體性能。
使用GPU是否能夠改進(jìn)Naru和LW-NN。實(shí)驗(yàn)表明，當(dāng)Forest T =100min，DMV T=500min時(shí)，在GPU的幫助下，LW-NN在Forest和DMV上分別提高了約10倍和2倍。其原因是：
Naru在DMV上改進(jìn)了2倍，在Forest中沒有改進(jìn)。這是因?yàn)楦聲r(shí)間越短，更新模型的查詢就越多，1個(gè)步態(tài)不足以讓Naru獲得更好的更新模型。
主要結(jié)論：機(jī)器學(xué)習(xí)方法需要更久的時(shí)間去更新模型，因此往往會(huì)跟不上數(shù)據(jù)更新的速度。與此同時(shí)，不同機(jī)器學(xué)習(xí)方法的估計(jì)誤差在不同的數(shù)據(jù)集上有所差異，并沒有一個(gè)顯著的最優(yōu)方法。
3、可能出現(xiàn)錯(cuò)誤的幾種情況
機(jī)器學(xué)習(xí)和深度學(xué)習(xí)模型的可解釋性差一直被學(xué)術(shù)界所詬病。可解釋性差，意味著研究人員很難評(píng)估模型什么表現(xiàn)佳，什么時(shí)候表現(xiàn)不佳，從而導(dǎo)致用戶難以信任和使用它們。
在本篇論文中，作者重點(diǎn)分析了不同的基于學(xué)習(xí)的基數(shù)估計(jì)方法出現(xiàn)較大誤差的幾種情況，從中發(fā)現(xiàn)了模型一些不符合邏輯的行為，并提出了一套提升模型可信性的邏輯規(guī)則。
如下圖，相關(guān)性、分配和域名大小會(huì)在不同程度上影響q-誤差的分布。
相關(guān)性：當(dāng)改變相關(guān)參數(shù)時(shí)，所有方法都傾向于在數(shù)據(jù)集上產(chǎn)生更大的q-誤差。如圖(a)顯示了指數(shù)分布s =1.0和域大小 d=1000時(shí)，不同相關(guān)度上前1% q誤差的趨勢(shì)分布情況。很明顯，所有圖中的箱線圖都有隨 c 增加而上升的趨勢(shì)。
分配：當(dāng)改變第一列分布和基礎(chǔ)相關(guān)性設(shè)置時(shí)，每個(gè)學(xué)習(xí)的方法都發(fā)生了不同的變化。當(dāng)s從0.0變?yōu)?.0，同時(shí)修正相關(guān)性c=1.0和域大小d=1000時(shí)，頂部1%的q-誤差分布趨勢(shì)如圖10b所示。
域名大?。?/span>不同的域大小（s=1.0和c=1.0）在數(shù)據(jù)集上生成的最大的1%q誤差分布，如上圖，Naru可能會(huì)在每個(gè)域大小上使用不同的模型體系結(jié)構(gòu)，以滿足相同的1%大小預(yù)算。
在實(shí)驗(yàn)研究中，作者發(fā)現(xiàn)部分模型出現(xiàn)了一些不合邏輯的行為。例如，當(dāng)查詢謂詞的范圍從[320, 800] 縮減到 [340, 740] 時(shí)，實(shí)際基數(shù)減少了，但LW-XGB估計(jì)的基數(shù)增加了60.8%。這種不合理的邏輯規(guī)則可能會(huì)給DBMS開發(fā)人員和用戶帶來麻煩。
受到深度學(xué)習(xí)解釋領(lǐng)域的工作的啟發(fā)，作者提出了五個(gè)基本規(guī)則，這些規(guī)則簡(jiǎn)單直觀，可作為一般基數(shù)估計(jì)器的評(píng)估標(biāo)準(zhǔn)：
(1） 單調(diào)性：使用更大（或更小）的謂詞，估計(jì)結(jié)果不應(yīng)增加（或減少）；
(2） 一致性：一個(gè)查詢的預(yù)測(cè)值應(yīng)等于其分段查詢預(yù)測(cè)值之和；
(3） 穩(wěn)定性：對(duì)于同一查詢，來自同一模型的預(yù)測(cè)結(jié)果都應(yīng)該是相同的；
(4） Fidelity-A：查詢整個(gè)域的結(jié)果應(yīng)為1；
(5） Fidelity-B：對(duì)于具有無效謂詞的查詢，結(jié)果應(yīng)為0。
主要結(jié)論：我們發(fā)現(xiàn)所有機(jī)器學(xué)習(xí)方法會(huì)在數(shù)據(jù)有較高的相關(guān)性時(shí)產(chǎn)生較大的誤差。與此同時(shí)，黑箱模型導(dǎo)致了無法解釋誤差的來源。
研究結(jié)論
雖然目前基于學(xué)習(xí)方法的基數(shù)估計(jì)方法還不能夠投入使用，但是以上實(shí)驗(yàn)驗(yàn)證了其在準(zhǔn)確度方面的潛力以及對(duì)數(shù)據(jù)庫(kù)優(yōu)化器可能帶來的巨大的影響力。為了能夠真正的將其部署到真實(shí)的數(shù)據(jù)庫(kù)產(chǎn)品中，作者在認(rèn)為未來需要重點(diǎn)解決兩個(gè)問題：
1.提升模型訓(xùn)練和查詢速度
通過實(shí)驗(yàn)可以看到，當(dāng)前大部分的機(jī)器學(xué)習(xí)模型與數(shù)據(jù)庫(kù)產(chǎn)品相比，無論從訓(xùn)練還是查詢時(shí)間上都有較大的差距，同時(shí)針對(duì)于模型本身的參數(shù)調(diào)優(yōu)的步驟也會(huì)花費(fèi)數(shù)據(jù)庫(kù)管理員一定的時(shí)間和精力。并且由于更新速度過慢，很多準(zhǔn)確度很高的模型無法處理高速變化的數(shù)據(jù)，因此提升模型的訓(xùn)練以及查詢速度是部署該類方法到數(shù)據(jù)庫(kù)產(chǎn)品中的重要前提。
2. 提升模型解釋性
現(xiàn)有的基于學(xué)習(xí)模型的方法大多基于復(fù)雜的黑盒模型，很難預(yù)測(cè)它們何時(shí)會(huì)出問題，如果出現(xiàn)問題也很難進(jìn)行調(diào)試。我們?cè)趯?shí)驗(yàn)中展示了傳統(tǒng)方法出現(xiàn)的一些不符合邏輯的行為，這些都會(huì)成為把它們投入到真實(shí)使用中的障礙。因此，提升模型解釋性在將來會(huì)是一個(gè)非常重要的課題，我們認(rèn)為一方面可以從研究更為透明的模型入手，另一方面也可以投入更多的精力在模型解釋和調(diào)試上。
論文鏈接：http://www.vldb.org/pvldb/vol14/p1640-wang.pdf
代碼鏈接：https://github.com/sfu-db/AreCELearnedYet
官網(wǎng)鏈接：https://vldb.org/2021/?conference-awards
雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
