作者 | 琰琰

 編輯 | 王曄

8月18日，VLDB 2021公布了今年的論文獲獎情況，SFU王健楠教授及博士生團隊（王笑盈，曲昌博，吳畏遠）獲得年度最佳EA&B論文獎。

VLDB （Very Large Data Base ），與 SIGMOD、ICDE 被公認為數(shù)據(jù)管理與數(shù)據(jù)庫領域的三大國際頂尖學術(shù)會議。8月18日，VLDB 2021采用線上線下結(jié)合的方式在丹麥哥本哈根正式開幕。VLDB的研究論文分為三個類別，王健楠團隊獲得了實驗、分析與基準（Experiment, Analysis and Benchmark ，EA&B）類別的最佳論文。

王健楠是SFU計算機系的副教授。他于2013 年在清華大學獲得博士學位，2013 年 -2015 年間在加州大學伯克利分校AMPLab進行博士后階段的研究工作。他領導開發(fā)的數(shù)據(jù)準備工具dataprep.ai 目前已經(jīng)有近 20 萬的下載量。

所獲獎項包括加拿大計算機協(xié)會授予的杰出青年獎 （2020），IEEE授予的數(shù)據(jù)工程新星獎（2018），ACM SIGMOD 最佳演示獎（2016），CCF最佳博士論文獎（2013）以及Google PhD Fellowship （2011）。他為VLDB 2021副主編，將在VLDB 2023大會擔任共同主席。

其本次獲獎論文題目為“Are We Ready for Learned Cardinality Estimation"（《通過機器學習的基數(shù)估計技術(shù)成熟了嗎？》），與騰訊周慶慶合著完成。

VLDB組委會認為，這篇研究工作概述了不同的基于學習的方法在數(shù)據(jù)庫產(chǎn)品中應用的可能性及優(yōu)缺點，幾乎覆蓋了實際使用環(huán)境中可能出現(xiàn)的情況。此外，該工作提出了可用于改善現(xiàn)有相關研究的方法，并進一步指出了未來需要的研究方向，為ML for DB研究領域的發(fā)展做出了重要貢獻。

1

研究概要

近幾年，機器學習以及深度學習方面技術(shù)的進步以及在其它領域內(nèi)被成功應用的先例，讓 ML for DB 這個課題變得越來越火，今年VLDB會議的Keynote，Workshop，Tutorial以及Session都在討論這個話題。

王健楠告訴AI科技評論，基于學習的方法（Learned Methods）是數(shù)據(jù)庫領域的熱門研究方向，但是現(xiàn)有研究過于關注模型的準確度，而忽略了其在部署到實際數(shù)據(jù)庫系統(tǒng)時可能會面臨的問題。這篇論文希望扭轉(zhuǎn)當前的研究重心，讓大家關注“如何如何降低模型成本？如何提高模型更可信性？”等重要問題。

按照目前ML for DB課題的發(fā)展情況來看，5-10年之后要么是研究人員發(fā)現(xiàn)模型并不能被真正的使用在生產(chǎn)環(huán)境中，漸漸的失去對該課題的研究興趣；要么是主流的數(shù)據(jù)庫系統(tǒng)開始大規(guī)模采用機器學習模型，并大幅提升了系統(tǒng)性能。

要想將第二種情況變?yōu)楝F(xiàn)實，王健楠團隊認為我們現(xiàn)在需要回答一個核心問題，即基于機器學習的方法是否已經(jīng)可以使用在數(shù)據(jù)庫產(chǎn)品中？如果不行，需要從哪些方面進行提升？

在本篇論文中，研究團隊從基數(shù)估計模塊入手，探究了基于機器學習的基數(shù)估計方法是否可用于數(shù)據(jù)庫產(chǎn)品這個問題。基數(shù)估計 (Cardinality Estimation)是數(shù)據(jù)庫優(yōu)化器（optimizer）中非常重要的一個模塊，該模塊會向優(yōu)化器提供查詢（query）可能返回的行數(shù)，從而引導查詢計劃（query plan）的選擇，并直接影響甚至決定查詢的速度。

由于現(xiàn)有基數(shù)估計方法很難做到精確估計，有時甚至會引起較大誤差，從而減緩查詢速度，因此基數(shù)估計一直被稱為數(shù)據(jù)庫優(yōu)化器的“阿喀琉斯之踵”（意為“致命要害”）。

目前采用機器學習或深度學習來預測基數(shù)的研究方法不在少數(shù)，并且這些方法在準確度上也展現(xiàn)了超越傳統(tǒng)數(shù)據(jù)庫中基數(shù)估計方法的極大潛能。

2

研究方法

在論文中，作者選擇了5個先進且不同的基于學習的模型，通過實驗評估了其在數(shù)據(jù)庫產(chǎn)品應用的可能性、可能引發(fā)的問題，并進一步為數(shù)據(jù)庫中除基數(shù)估計之外的其它模塊應用機器學習提供參考。實驗主要分成三個部分：

1、基于學習的方法是否適合靜態(tài)環(huán)境？

靜態(tài)環(huán)境是指數(shù)據(jù)庫中的數(shù)據(jù)不進行更新的狀態(tài)。作者首先評估了靜態(tài)環(huán)境下，基于學習的基數(shù)估計方法與傳統(tǒng)方法在準確度和效率（包括訓練時間和推斷時間）兩個維度上的實驗結(jié)果。

實驗選取了3個廣泛應用的數(shù)據(jù)庫產(chǎn)品和6個常用以及最新的傳統(tǒng)基數(shù)估計方法作為基準，并且選擇了4個常用的且具有不同屬性的數(shù)據(jù)集。通過研究現(xiàn)有工作中的SQL查詢生成方法，作者提出了一個更能涵蓋所有可能的查詢生成框架，并通過它來生成實驗所需要的訓練和測試數(shù)據(jù)。

q誤差比較結(jié)果

實驗表明，學習的方法在幾乎所有的數(shù)據(jù)庫系統(tǒng)中都比傳統(tǒng)方法的準確度更高，最好的學習的方法可以在最大q-誤差指標上超過傳統(tǒng)方法14x，在Census、Forest、Power和DMV數(shù)據(jù)集上，三個數(shù)據(jù)庫系統(tǒng)上分別達到28x、51x、938x和1758x。

在所有學習的方法中，Naru最穩(wěn)健、準確度最高，其最大誤差均保持在200以內(nèi)。

在訓練時間和推理時間方面，這些高精度學習方法與DBMS產(chǎn)品進行了比較。如下圖，三個DBMS都可以在1或2毫秒內(nèi)完成整個過程，相較于擬合整個數(shù)據(jù)分布來估算基數(shù)的學習方法，通過回歸模型的方法能夠達到與DBMS相似或更好的查詢效率。

DeepDB中的SPN模型在三個較大的數(shù)據(jù)集上需要大約25ms，在Census數(shù)據(jù)集中平均需要5ms。Naru的推理過程包括一個漸進式抽樣機制，需要將模型運行數(shù)千次才能得到準確的結(jié)果。它的總時間對運行的設備很敏感，在GPU上需要5到15毫秒，CPU的速度可以慢20倍。

超參數(shù)調(diào)整是學習方法的另一個成本。如果沒有超參數(shù)調(diào)整，學習的模型可能會表現(xiàn)得非常糟糕。實驗發(fā)現(xiàn)，對于同一種方法，具有不同超參數(shù)的模型之間的最大q誤差與最小q誤差之比可以達到10的5次方。

一般情況下，我們需要訓練多個模型才能找到最佳超參數(shù)。如上圖，Naru在帶有GPU的DMV上訓練單個模型用了4個多小時。如果訓練了五個模型，Naru可能需要20多個小時（幾乎一天）進行超參數(shù)調(diào)整。

主要結(jié)論：基于機器學習的方法在準確率上相比于傳統(tǒng)方法有比較大的提升。然而相比于傳統(tǒng)方法，除了 [Selectivity estimation for range predicates using lightweight models] 中的LW-XGB以外，機器學習方法需要更多的時間去訓練模型，同時在模型運行的時候也會更慢。

2、學習的方法是否是適合動態(tài)環(huán)境？

“數(shù)據(jù)更新”在現(xiàn)實生產(chǎn)環(huán)境的數(shù)據(jù)庫中時常會發(fā)生，這使得基數(shù)估計器常處于一個“動態(tài)”變化之中。

為了更加公平的比較基于學習的方法和現(xiàn)有的數(shù)據(jù)庫產(chǎn)品，需要在模型中引入一個動態(tài)的框架。作者在本文提出了一個在動態(tài)環(huán)境中符合數(shù)據(jù)和模型更新速度的評估基數(shù)估計模塊的方法，并且設計了一系列實驗探討了基于學習類的方法在真實環(huán)境中應該能夠如何調(diào)整。

以下為DBMS與不同數(shù)據(jù)集動態(tài)環(huán)境下的5種學習方法。

T表示數(shù)據(jù)集的更新頻率：高、中、低

可以發(fā)現(xiàn)，與學習的方法相比，DBMS具有更穩(wěn)定的性能。其原因是DBMS的更新時間非常短，幾乎所有查詢都是在更新的統(tǒng)計數(shù)據(jù)上運行的，而很多學習的方法無法跟上快速的數(shù)據(jù)更新，即使可以其性能也次于DBMS。

例如，當DMV T=50 min時，DBMS-A的性能比DeepDB高出約100倍，因為更新的DeepDB模型無法很好地捕捉相關性變化。

作者進一步探討了學習的方法的更新次數(shù)和準確性之間的相關性。實驗表明，當 Census T=10min，F(xiàn)orest T=100min時，“Dynamic”（代表Naru在10K查詢中的性能）是先下降后逐漸回升的，這表明訓練時間增加，模型更新緩慢，使未更新的模型執(zhí)行了更多的查詢。雖然多次迭代改進了更新模型的性能，但損害了整體性能。

使用GPU是否能夠改進Naru和LW-NN。實驗表明，當Forest T =100min，DMV T=500min時，在GPU的幫助下，LW-NN在Forest和DMV上分別提高了約10倍和2倍。其原因是：

（1）使用GPU，LW-NN的訓練時間提高了20倍；

（2） 高效訓練的LW-NN（500個epoch）可以獲得更好的準確性。

Naru在DMV上改進了2倍，在Forest中沒有改進。這是因為更新時間越短，更新模型的查詢就越多，1個步態(tài)不足以讓Naru獲得更好的更新模型。

主要結(jié)論：機器學習方法需要更久的時間去更新模型，因此往往會跟不上數(shù)據(jù)更新的速度。與此同時，不同機器學習方法的估計誤差在不同的數(shù)據(jù)集上有所差異，并沒有一個顯著的最優(yōu)方法。

3、可能出現(xiàn)錯誤的幾種情況

機器學習和深度學習模型的可解釋性差一直被學術(shù)界所詬病。可解釋性差，意味著研究人員很難評估模型什么表現(xiàn)佳，什么時候表現(xiàn)不佳，從而導致用戶難以信任和使用它們。

在本篇論文中，作者重點分析了不同的基于學習的基數(shù)估計方法出現(xiàn)較大誤差的幾種情況，從中發(fā)現(xiàn)了模型一些不符合邏輯的行為，并提出了一套提升模型可信性的邏輯規(guī)則。

如下圖，相關性、分配和域名大小會在不同程度上影響q-誤差的分布。

相關性：當改變相關參數(shù)時，所有方法都傾向于在數(shù)據(jù)集上產(chǎn)生更大的q-誤差。如圖(a)顯示了指數(shù)分布s =1.0和域大小 d=1000時，不同相關度上前1% q誤差的趨勢分布情況。很明顯，所有圖中的箱線圖都有隨 c 增加而上升的趨勢。

分配：當改變第一列分布和基礎相關性設置時，每個學習的方法都發(fā)生了不同的變化。當s從0.0變?yōu)?.0，同時修正相關性c=1.0和域大小d=1000時，頂部1%的q-誤差分布趨勢如圖10b所示。

域名大?。?/span>不同的域大?。╯=1.0和c=1.0）在數(shù)據(jù)集上生成的最大的1%q誤差分布，如上圖，Naru可能會在每個域大小上使用不同的模型體系結(jié)構(gòu)，以滿足相同的1%大小預算。

在實驗研究中，作者發(fā)現(xiàn)部分模型出現(xiàn)了一些不合邏輯的行為。例如，當查詢謂詞的范圍從[320, 800] 縮減到 [340, 740] 時，實際基數(shù)減少了，但LW-XGB估計的基數(shù)增加了60.8%。這種不合理的邏輯規(guī)則可能會給DBMS開發(fā)人員和用戶帶來麻煩。

受到深度學習解釋領域的工作的啟發(fā)，作者提出了五個基本規(guī)則，這些規(guī)則簡單直觀，可作為一般基數(shù)估計器的評估標準：

(1） 單調(diào)性：使用更大（或更?。┑闹^詞，估計結(jié)果不應增加（或減少）；

(2） 一致性：一個查詢的預測值應等于其分段查詢預測值之和；

(3） 穩(wěn)定性：對于同一查詢，來自同一模型的預測結(jié)果都應該是相同的；

(4） Fidelity-A：查詢整個域的結(jié)果應為1；

(5） Fidelity-B：對于具有無效謂詞的查詢，結(jié)果應為0。

主要結(jié)論：我們發(fā)現(xiàn)所有機器學習方法會在數(shù)據(jù)有較高的相關性時產(chǎn)生較大的誤差。與此同時，黑箱模型導致了無法解釋誤差的來源。

3

研究結(jié)論

雖然目前基于學習方法的基數(shù)估計方法還不能夠投入使用，但是以上實驗驗證了其在準確度方面的潛力以及對數(shù)據(jù)庫優(yōu)化器可能帶來的巨大的影響力。為了能夠真正的將其部署到真實的數(shù)據(jù)庫產(chǎn)品中，作者在認為未來需要重點解決兩個問題：

1.提升模型訓練和查詢速度

通過實驗可以看到，當前大部分的機器學習模型與數(shù)據(jù)庫產(chǎn)品相比，無論從訓練還是查詢時間上都有較大的差距，同時針對于模型本身的參數(shù)調(diào)優(yōu)的步驟也會花費數(shù)據(jù)庫管理員一定的時間和精力。并且由于更新速度過慢，很多準確度很高的模型無法處理高速變化的數(shù)據(jù)，因此提升模型的訓練以及查詢速度是部署該類方法到數(shù)據(jù)庫產(chǎn)品中的重要前提。

2. 提升模型解釋性

現(xiàn)有的基于學習模型的方法大多基于復雜的黑盒模型，很難預測它們何時會出問題，如果出現(xiàn)問題也很難進行調(diào)試。我們在實驗中展示了傳統(tǒng)方法出現(xià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)雷鋒網(wǎng)雷鋒網(wǎng)

雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。