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