如何評價 2017 年 Jeff Dean 的關於使用 deep learning 做索引的論文？

01-16

Paper 連接：https://www.arxiv-vanity.com/papers/1712.01208v1/
===========
提問者在提問時附加的個人觀點：

在文章顯示，此方法能讓 deep learning 對數據分布進行學習，再對齊進行優化，從而得到比 B tree 做索引快 70% 的搜索速度。

（注意：該個人觀點可能存在偏差或錯誤，不應視為問題的一部分；但知乎小管家有對刪除大段文字進行主觀臆斷的自由裁量權，所以社區通常不直接刪除問題描述中的提問者添加的可能在真實性和可靠性方面存在缺陷的文本。）

周末仔細讀了一遍論文，來分享下思路和具體細節。加上個人的一些評論，希望對大家有幫助和啟發。

有沒有想過用機器學習的方式解決系統設計中的問題？這是個蠻有趣的命題，它的難點在哪兒呢：系統里的演算法或數據結構往往是確定性的，顯式的（我們清楚地知道輸入和輸出間的映射關係），而機器學習中的模型是依賴於輸入數據訓練出來的（下文會看到事實上數據結構的建立也是依賴於數據的），並且存在一定的誤差（而很多時候系統模塊有嚴格限制條件）。雖然在系統設計時應該考慮所有（最壞）數據的情況，但是在做系統優化的時候，通常會通過一些特殊性來對系統做特定的設計。這裡的特殊性包括數據特殊性和使用特殊性。數據特殊，比如對給定範圍且沒有重複的數組排序，可以直接用bitmap。使用特殊，例如由於業務場景，讀寫比例相差很多（每周只更新一次），實現某種數據結構的時候可以把讀實現成O(1)，寫實現成O(n)，而標準實現往往是在保證均攤最優情況下讓各操作複雜度盡量接近，因為假設各操作使用頻率相近。而大多數時候只可能知道使用特殊性，卻很難知道數據的特殊性。這裡很自然的思路就是通過數據訓練出一個機器學習的模型（由於多層神經網路的泛化能力這裡考慮神經網路模型）去encode這種特殊性（如果存在），然後對比看看用這個模型是不是能有些優勢，如縮短計算映射的時間，減少存儲等等。當然，如果這種映射關係能被人理解，也可以更好地去實現系統模塊。

這篇paper就試圖用這個想法去優化索引 (Index) 問題。首先，索引的過程本身就是模型：Range Index索引可以看做是從給定key到一個排序數組position的預測過程，Point Index索引可以看做是從給定key到一個未排序數組的position的預測過程，Existence Index索引可以看做是預測一個給定key是否存在（0或1）。這樣一來，索引系統是可替換的，我們可以直接用ML模型去替換現有的索引模塊實現。其次，數據特殊性對索引設計的影響明顯。假設用於Range Index的key的範圍是1-100M，那麼可以用特殊的hash函數（直接把key本身當成是offset）去做索引而不必再用B-Tree。然而，用ML模型去做索引也可能存在一些問題：

Semantic Guarantees. 通過數據訓練得到機器學習的模型是存在誤差的，但是我們設計的索引經常需要滿足嚴格的限制條件。舉例來說，bloom-filter的優勢之一是可能會有把不存在的錯判成存在（False Positive）但絕不會把存在的錯判成不存在（False Negative）。
Overfitting. 如果避免模型的overfitting？換句話說，如果當前訓練的模型只能memorize當前數據形態而並不能generalize新的數據，該怎麼辦？
No Specialization. 如果數據並沒有任何特殊性，如完全隨機或者不能被我們的設計模型架構所歸納，該如何處理？另一種情況是，新的數據破壞了之前模型歸納出的特殊性，比如新的數據來源於一個新的或者是變化了的distribution。
Evaluate Efficiency. 模型的inference過程相比顯式索引數據結構的計算更昂貴。

順著上面的思路，帶著這四個問題，具體來探索一下資料庫系統中的三類索引：Range Index ，Point Index和Existence Index。這裡考慮到篇幅所限，只說Range Index（完整的paper note可以去我的博客）。

Range Index. 資料庫系統通常使用B-Tree或B+-Tree來實現range index。查詢時給定一個key（或一些定義range的keys），B-Tree會索引到包含該key的對應範圍的葉子節點，在葉子節點內對key進行搜索。如果該key在索引中存在，就會得到其對應的position。這裡position代表指向邏輯頁的一個offset或pointer 。一般在一個邏輯頁內的records會用一個key來index。如圖所示，輸入是一個key，輸出是對應要查詢record的position的區間 $[pos, pos + pagesize]$ 。

有趣的是，在機器學習的觀點下，B-Tree索引實際上可以看成是一個regression tree模型，這個模型（B-Tree）的建立過程也是依賴數據的，只不過它不是通過梯度下降的方式得到的，而是通過預先定義的法則（insert函數）。如下圖2，對於輸入x，模型預測出一個 $pos_{pred}$ ，若區間 $[pos_{pred} - minerr, pos_{pred} + maxerr]$ 中包含這個record，那麼預測準確，其中minerr的期望是0（這時pos就是record的位置），maxerr的期望是pagesize（這時record的位置在 $pos+pagesize$ ）。那麼minerr和maxerr在模型中具體如何計算呢？對於訓練數據（現有的 $（key，pos）$ )，計算出每一組pospred和和pos的正負差，然後取最大的正差就是maxerr，負差就是minerr。這裡並不需要考慮不在索引中的key，因為B-Tree本身也不能保證在新的key insert後搜索出來的pos和insert前的pos的差距在 $[0,pagesize]$ （insert前B-Tree根本找不到這個key！）。

用圖2的模型代替圖1的B-Tree能否學到數據特殊性從而優化查詢過程呢？假設有1M個key（取值從1M到2M），那麼可以直接用一個等價關係（線性模型）代替B-Tree，也就能把log(n)的複雜度減少成常數複雜度。同樣的，如果(key, pos)是一個拋物線，那麼神經網路模型也可以通過常數複雜度進行預測。考慮到神經網路的泛化能力，如果數據具有特殊性，那麼用模型代替B-Tree就能減少查詢複雜度。具體B-Tree複雜度和神經網路模型複雜度的時間分析可以參考原文2.1。

更進一步，還可以從概率的角度來思考range index這個問題。Range index實際上是描述一個數據點到一個有序數組的函數關係，也就是說這個函數關係"模擬"出了數據的累計分布函數（CDF）。因此，可以這麼來定義這個函數： $p=CDF(key)?N$ ，其中p是position，CDF(x)是 $Prob(X<=key)$ ，N是所有的key的總數。CDF函數可以簡單理解成一種描述概率函數的wrapper函數，它描述隨機變數X在小於一個key條件下的概率和。有了CDF，就能很容易地描述一個區間X的概率和： $CDF(key2)?CDF(key1)=Prob(key1<=X<=key2)$ ，它能夠幫助進一步深入地研究概率分布理論。這麼來理解此處的"模擬"就明白了：假設我們把pos和key的函數關係寫成 $p=F(key)?N$ ，其中 $F$ 是一個任意函數。那麼 $F$ 滿足以下性質：

$設p1=F(key1)?N和p2=F(key2)?N$

$p1?p2=(F(key1)?F(key2))?N=F(key1 - key2)?N$

最後這個等式由range index滿足，因為range index映射到的pos是一個在有序數列里。而巧合的是累計分布函數（CDF）也滿足這個性質。雖然滿足這個性質的函數不一定要是CDF，但是如果能把一個更強假設的函數（CDF）學習出來，那麼一定也滿足range index的功能！使用這個更強假設（CDF）的好處是：擬合數據的CDF函數是一個active的研究方向，可以受益於已有的研究成果。

基於這個想法，讓我們先拋開擬合CDF，嘗試用一個簡單的兩層全連接神經網路（每層32個neurons + ReLU acitivation）訓練了一個200M的web-server log records，x是timestamp，label是對應B-Tree索引到的position。並測試了用訓練得到的模型的預測時間，latency大約是80000 ns，throughput是每秒1250次預測。很遺憾，這比不用索引遍歷還要慢。然而B-Tree的索引時間大概是300 ns。那麼問題出在哪兒呢？首先，這裡用了Tensorflow做訓練和預測，Tensorflow是位較大規模的神經網路做的優化，但並不適用於這裡的小網路，並且python層因為用swig做膠水層會造成一定的latency開銷。其次，機器學習中的樹模型（比如B-Tree模型）能夠更好地記住數據特徵，因為它能不斷的split data space。而這裡用的神經網路模型能夠很快地學習出一個做地還不錯的模型，但是很難做到局部數據上的準確（這裡可以用overfitting來理解）。為了保證精度，我們要train更多的epoch，並且使用更深的網路來訓練。這裡還有一個原因導致需要用更深的網路來盡量達到樹模型的精度：訓練目標不僅要降低每個預測position和label間誤差的平均，更重要的是要讓訓練出來模型的minerr和maxerr盡量小，也就是讓預測出來的position在真正的page內（注意這裡並沒有把minerr和maxerr加到優化函數里，而只是假定預測精度越小，這兩err越小）。同時，B-Tree是cache-efficient的：能把很少的上層節點放入cache。而對於全連接神經網路模型，要把模型都載入到內存，並且權重不是稀疏的！

為了嘗試解決以上的問題，文中首先提出了Learning Index Framework（LIF）。LIF就是一個索引優化系統，給定一套索引數據，LIF自動生成多組超參數，並且自動地優化並測試，找出最優的一組配置。訓練時，LIF任然用了TensorFlow，而在inference時LIF根據訓練打包的模型，用code-generation（用特定的模型結構減少運行時開銷，比如剪枝、去掉多餘的if-else、direct memory access等，這裡不展開。如果對資料庫系統了解的同學應該比較熟悉）自動生成了相應C++的程序，這裡實現具體的細節可以參考21。這樣，可以把inference的開銷減少到30 ns。

Recursive Model Indexes(RMI). 既然LIF可以在很短的時間裡完成預測，我們就可以考慮用更複雜的模型來嘗試替換B-Tree索引了。上文提到，單個全連接網路並不能達到很好地準確度。事實上，如下圖所示，全連接神經網路模型雖然可以從整體上較好地擬合出整體數據分布，但由於每個數據個體本身的隨機性，卻很難同時在局部也準確擬合出個體數據，文中把這個問題稱作the last-mile accuracy問題。換句話說，對於一個100M條記錄的數據集，我們可以先用單個簡單的模型把誤差控制在10K並不困難，然後對於局部數據，再用另外的模型進行預測把誤差從10K降低到100。因此這裡的思路就是用多模型來解決the last-mile accuracy問題，這裡的多模型的思路並不是boosting，而是來源於混合專家網路（下文用MoE，可以參考51)。

MoE是90年代初提出的模型，下面先來介紹一下MoE模型的思想。真實情況下，數據往往來源於不同的概率分布，即使是單個概率分布也會隨著時間變化。舉個例子，比如股票價格，很難用一個連續的函數擬合分段函數（每天或每小時的變化曲線），也很難用一個分段函數去擬合一個連續函數（每月或每年整體的變化趨勢曲線）。而如同上文所分析的，真實的數據分布函數往往是介於兩者之間的：總體上滿足一個變化趨勢，但是局部卻是分段函數（每天數據的分段函數可能都不同），因為這時隨機因素更顯著。MoE的想法是能否把數據partition，然後對於不同的數據，用不同的模型（稱Expert）來進行擬合。這裡需要特別指出的是，對數據本身的特徵做partition並不一定能解決問題，而是應該根據不同的x和y之間的關係來對x做partition。

比如在上圖的例子中，8個數據點來自兩個拋物線，如果只根據數據本身做partition（右側黃線），並不能很好地把數據partition在兩個拋物線上，而左邊的藍線才是一個更好的parition。所以MoE的想法就是把x和y之間的關係定義到目標優化函數中，然後訓練出不同的Expert來擬合不同的數據。如下圖裡，Gating Network可以認為是賦予每個Expert的權重，比如可以從輸入接一個神經網路得到Softmax概率或Attention當成權重。然後對於這一個特定的輸入，只訓練在這個Attention下（或者Softmax較大概率）的Expert模型。換句話說，當某個Expert1表現比另一個Expert2好，反向傳播時（ $y\_{pred} - y$ 更接近）Expert1對應Attention的權重就會更高，這樣下去對於這個輸入MoE就更加依賴於Expert1了。就好比小學一年級老師給大家一份數學卷子，學生A比學生B做的好，以後只要是數學題，老師都會重點培養A，讓他成為一個數學特長生。而B可能更擅長語文，這就是MoE的基本思想。這裡需要注意兩點，不同於boosting，在預測時MoE對於不同的輸入分配給各個模型的權重是不同的（softmax的概率或者attention）。而boosting一旦模型訓練完成，在預測時分配給每個模型的權重是完全一樣的。另一點，MoE有個很好的性質：雖然在訓練的時候由於模型很多，參數也很多。但是在預測時候模型的參數並不隨著模型複雜度的增加而增加，因此計算開銷也不回增加，因為我們總是能Gating Network找出幾個相應的Experts來做預測。這種稀疏性對於能夠成功替換B-Tree索引至關重要！

回到論文，文中提出了一種特定的MoE模型（文中稱作Recursive Regression Model）：RMI包含從頂到下M層，每一層包含 MlMl 個Experts和一個Gating策略 $M_{l} ? f_{l?1}(x) / N$ ，每一層的Loss function是 $L_{l}=∑_{(x,y)}(f^{M_{l} f_{l?1}(x)/N}(x)?y)^2$ ，也就是說對於特定的(x, y)，RMI委託特定路徑的M個experts來對特定範圍的x進行訓練和預測，很好地解決了the last-mile accuracy問題。可以看到，這個MoE的特殊性在於，除了最下層的experts，其他層的所有experts的訓練目標都是為了做Gating。我們可以看成是學一個attention（只有一個非零）的Gating Network，而只有最下層的expert才是做預測真正的experts。這裡能這麼假設的原因在於對於最下層，相近position範圍內的數據分布一致（上一段提到我們通過x和y的關係來對x來做partition，這裡通過除了最下層的所有experts層重新組織x來做這種partition使得在一個連續範圍內的y的x被partition在了一起），用單個模型就夠了（這裡可以做進一步優化：在最下層前學出一個稀疏向量或者真正的attention）。需要注意的是，這裡的分層模型並不是樹，因為每個父節點也可能指向其他父節點的孩子。另外，在頂層expert可以用ReLU neural這種泛化表達能力更強但擬合性稍差的網路，而底層expert可以用擬合性更強的線性回歸模型。

本文開始提到No Specialization的問題：如果數據本身是隨機的，RMI模型並不能歸納出數據中的分布規律，應該怎麼辦？這裡的思路就是rollback到B-Tree Index（下文會看到對於Point Index和Existence Index都會有類似處理來解決No Specialization問題）。由於RMI模型的稀疏性和LIF的高效率，即使對於這種情況，加入RMI的range index效率也並不會降低太多。整個訓練過程見下圖，文中是分stage訓練的（也可以用end-to-end），訓練時可以用grid search和一些best practice來tuning hyper-parameter。我們知道，在訓練完RMI後，能得到每個experts的minerr和maxerr。我們可以用它們來和預先給定的threshold（比如設成pagesize）對比，當成rollback的條件。更重要的是，它們能夠優化索引搜索過程。通常的B-Tree在找到輸入key的offset後會用binary search（也有其他的方式如Quaternary Search但是效率提高不明顯）。而RMI模型預測出來的position可以用作更準確的pivot來進一步提高搜索record的性能。論文中提出了Model Binary Search，Biased Search和Biased Quaternary Search，這部分比較簡單，就不展開說了，可以參考論文3.4。

論文中用了四個數據集來做了實驗，分別是Weblogs（日誌數據，用timestamp建索引，這個最符合真實複雜環境）, Maps（地圖數據用經度建索引，雖然這個也是真實數據，但是相對更規則）, Web-documents（真實的document數據）和合成的Lognormal（採樣生成的數據，為了模擬真實環境中的長尾分布）。其中Weblogs、Maps和Lognormal數據使用整數來當索引的，而Web-documents是用字元串來當索引的（因為不連續）。下面分別列出了四組數據的實驗效果。在每組數據集的實驗中，論文以pagesize=128作為baseline，分別給出了Learned Index與B-Tree Index索引時間（Model列表示搜索position的時間+Search列表示搜索record的時間）的對比、索引內存佔用的對比以及索引誤差。在最後一組Web-document數據的實驗里，文中對比了不同的搜索策略，因為對於string的binary search會更耗時，所以上文提出的搜索策略能夠更明顯地提高效率。這裡Learned Index只用了兩層的RMI，Learned Indexed Complex表示第一層用了兩層全連接的網路，而不帶Complex的沒有用hidden layer。而第二層都使用了linear model，論文對第二層里不同的experts數目做了不同的實驗。

總的來說，在索引的內存佔用上大大有了顯著減少。在索引時間上，在特定的配置下也能有一些提升（最後一組實驗比較有說服力，因為我們的初衷是找出人們發現不了數據特殊性）。可以看到，這裡實驗用的RMI只有兩層，而且誤差不穩定。猜想是如果更深的RMI，精度提出和時間效率提升以及內存佔用提升相比並沒有太好，當然未來可以進一步採樣模型壓縮來優化。

回到本文最開始提到的四個問題。我們已經通過例子討論了如何解決Semantic Guarantees和Evaluate Efficiency。那麼learned index如何處理Overfitting和No Specialization問題呢？對於overfitting，論文的假設是要被新索引的key依然滿足CDF。比如對於Learned Range Index的 insert操作，如果新的key也同樣來源於訓練出的CDF分布，那麼我們並不需要重新訓練，直接insert到預測出來的position就行了。而B-Tree則需要O(log N)甚至re-balance。但RMI解決the last-mile accuracy的方式決定了learned index並不能很好地generalize，這是可以進一步完善的地方。而對於No Specialization的數據索引，雖然learned index並不能generalize，但能在當前情況下提高查詢效率，減少內存使用。對於OLAP為主的系統，更新索引的操作本來就是定期進行，可以這時再重新訓練模型，這時訓練的初值可以使用之前訓練出來的權重。如果OLTP數據更新更頻繁的系統，可以採用delta-index的一些技術，增量地更新learned index。文中還提到當CDF分布變化時的模型處理，這裡不展開介紹了，詳見3.7.1。另外對於面向disk索引的資料庫系統來說，邏輯頁並不是真正的物理頁（從而不能滿足前文分析的性質），論文中也給出了幾個可能可行的方式優化，詳見3.7.2。

說來巧合，其實類似的問題去年和同事討論過。在Pivotal的時候，我和幾個同事結合ML和DB做過一些嘗試，比如用SQL寫推薦系統，通過Transaction Log檢測作弊用戶和異常行為並集成到查詢層。也經常討論，如果用資料庫系統去實現深度學習，可行嗎？有哪些優勢？我們從存儲，計算，表達問題的泛化能力等幾方面討論過很多次，但每次都沒有很好地去切入。現在想來，有點慚愧，因為我當時更關注的是如何用資料庫里的一些技術做ML，而不是如何用ML來優化資料庫設計。一次，明哥問我能不能用ML嘗試優化plan，減少查詢次數，能否對各類的join做些優化。我們討論到索引優化，但遺憾的是當時並沒有深入。不過，就像paper里所斷言的，this is a fruitful direction for future research。

拋磚引玉

1. 個人很喜歡這個idea，很新鮮，有啟發性，學習數據分布可以減少索引的大小這個idea真的很有趣。

2. 如果集成進數據查詢系統，我覺得工程難度適中。一方面這不容易，這個功能不比數據分析，寫Python把數據一口氣讀進TF跑模型然後做預測。查詢講究高效，需要一些hardcore的代碼集成進查詢執行引擎。一方面又不難，這篇文章里提到，他們用了簡單的模型，不要用大廠的深度學習平台大炮去打小蚊子。簡單模型自己寫一個也還行。

不過hardcore集成就意味著不好做一個松耦合的插件輕鬆與現有系統集成，PostgreSQL好像有索引插件機制來著？

3. 實際效果我存疑。我覺得這個idea嚴重依賴於數據分布。文章里給了這麼個示意圖：

如果key的value和position真的符合這樣的一個分布，那麼這個曲線看起來可以用多項式回歸就很好地擬合，和B+樹比，O(n)的存儲空間變成constant的參數數量，O(logn)的查詢複雜度變成constant的模型計算時間，那確實很好。但如果是下圖這麼一個數據分布

幾乎隨機。筆者認為用機器學習模型，就算是深度神經網路也很難擬合地很好，參數多容易過擬合。同樣的，對於非數值型的key不好建模。結果就像文章的Figure6里提到的，預測的方差非常大，性能不穩定。

4 不穩定使得應用場景受限。

4.1 對數據的分布有非隨機性要求，使得這個技術不適合在線的OLTP業務，因為OLTP業務有很強的隨機性。有可能給ID查數據有效果，但對於其他選擇條件，有可能就不那麼好了。數據倉庫這種離線查詢，數據都重新組織過一遍的，分布是可以了，但用列存儲連數據本身都能壓縮幾倍的，還輪得上這麼點索引壓縮嗎。

4.2 關係資料庫里查詢優化的cost based optimization可能不準。查詢優化的原理是枚舉所有可能的查詢計劃，然後根據建好的cost model挑最好的。如果現在有這個索引這個Access method，現在這個索引如果真的性能方差那麼大，那cost model怎麼都不會準的，找到的最優查詢計劃也就很有可能是錯的了。

5. 雖然說了這麼多壞話，我覺得還是有很大應用空間的。可以作為一個索引的新標準加入SQL，也可以單獨用來集成進Nosql里，而且混合的索引又保證了worst case performance。

6. 從寫作風格來說，個人認為這是很資料庫的一篇論文。

這篇文章應當是一個引領新潮流的工作。如果將ML理解為一個建模方法，那麼用其來應對複雜多變的workload其實是很吸引人的idea。從近期計算機系統和資料庫類的會議文章來看，人們也慢慢開始用ML來解決傳統的系統設計經驗帶來的sub-optimal solution的問題。在索引、緩存演算法還是負載均衡等問題中，高性能往往來源於演算法本身對workload的假設與實際情況的高度契合。以緩存演算法為例，脫離workload特性談某種緩存策略更優都是耍流氓，那如果AI能夠準確建模當前workload特性，那麼對於選擇甚至構造一種最優策略都大有裨益。

但用ML解決此類問題依然存在顯著問題。建模複雜問題往往需要複雜模型，而複雜模型的計算存儲效率依然是問題，ML community自己也在研究模型壓縮等問題。如果說僅僅進行預測的計算量還不算大的話，訓練開銷則不可忽視。類似於這篇文章中的假設，對於負載相對不變的情況，模型是不需要重新訓練，訓練開銷也許不是什麼大事，但是個人覺得這類問題對於ML的需求其實比較弱。更多的實際情況應該是workload在變化，怎麼識別concept drift並高效調整模型，從而給出更優的策略。

總的來說，ML對諸多研究領域都帶來許多新機會和新挑戰。有ML這個新工具，很多問題得以更精確建模和解決。ML本身的問題，比如對硬體性能的高需求，演算法的可靠性可解釋性也使得在真正使用之前還需要做很多工作。

給我的啟發是，如果用機器學習的思路審視當今的SQL/NoSQL/NewSQL設計中的方方面面，那麼我們是否可以將TradeOff發揮到極致，以一種自適應地方式解決所有問題？

現階段機器學習代表著先進生產力，考慮到以往資料庫設計中的很多經驗性的做法，在人工智慧時代，這些專家經驗還有剩餘價值？

今天可以用深度學習解決查詢時優化（CMU/Pelotondb），明天可以用深度學習建索引(Google)，那麼分庫分表、自適應底層存儲結構、Cache/Buffer自動調整還會遠嗎？

從長遠來看，現實世界的很多場景，我們都可以用數據為之建模，瑣碎的經驗所產生的效益將遠低於數據驅動所帶來的價值。

按照jeff dean在NIPS上的talk說的，他認為所有系統裡面用heuristic的工作都可以通過訓練一個網路解決。

相信這也會成為系統領域這幾年的研究熱點，現在不是有MLSys嘛，以後可以搞一個SysML。

指引存儲引擎研究的一個新方向，側重只讀索引的優化，首先解決的也是Google自家的海量搜索業務需求，順便給Google自家的TPU晶元寫了一篇軟文。

軟體系統優化餘地所剩無幾倒逼硬體更新，從而催生新的軟體設計。存儲引擎這塊，leveldb/rocksdb(LSM-tree)

mongodb(btree)

mysql(b+tree)

tokudb(fractal tree)

已經針對不同讀寫特點優化到一個很難逾越的高度，根據RUM那篇論文，讀開銷、寫開銷和空間開銷就是一個不可能三角，只能三者取其二。

接下來的思路是什麼呢？

被朋友圈的小夥伴頻繁問起這個問題，正好對數據挖掘和資料庫都略懂一些，談談我得想法:

1. 空間減小的僅僅是索引，而在整個資料庫中 value 才是大頭，所以通過減小索引來節省內存，效果大打折扣，真的要做就必須索引和value都壓縮才行

(比如我們的TerarkDB)

2. 資料庫的其中一個關鍵指標是 99% latency，也就是最差情況的延遲，這種機制下最差情況很難保證(基於概率的模型)

3. 當數據分布發生變化的時候，性能會急劇下降，需要重新訓練模型，也就是說默認是一個離線的壓縮，需要通過複雜的工程手段支持在線

4. AI 在資料庫領域的應用，我認為應該在智能 DBA 領域，如自動根據負載和場景自動調整參數，自動災備，冗餘，熔斷，安全，審計等等

5. 認同文中提到的通過越來越便宜的計算資源，換取更好的壓縮率和性能(TPU或GPU加速，達到更好的效果)，跟我們的方向倒是一致

總結下來，這是一個有意思的嘗試，到目的只能說為了找場景而AI，同時宣傳自家TPU...

原文鏈接：Learned Index Structures 論文解讀

資料庫的索引和機器學習里的預測模型其實有一些相似之處，比如 B 樹是把 key 映射到一個有序數組中的某個位置，Hash 索引是把 key 映射到一個一個無序數組中的某個位置，bitmap 是把 key 映射成是一個布爾值（存在與否）。

這些事，似乎拿預測模型都是可以做的。Yes, but…B 樹那是精確的映射關係，和預測模型能一樣嗎？

所以這就是本論文 NB 的地方了，以上的想法是可以實現的。實驗表明，在某些數據集上，用 RM-Index 預測模型代替 B 樹之類的數據結構，可以提升 70% 的速度、並節約相當可觀的空間。

範圍索引

B 樹和一個預測 model 是很相似的：

B 樹能定位某行數據所在的 page，可以看作是確定了一個區間：[pos, pos + pagesize]
預測模型也能做相似的事，假設我們把預測錯誤率成功 bound 在 min/max_err 以內，那麼也就可以確定，數據位於區間 [pos - min_err, pos + max_err]

一圖以概之：

於是問題變成，如何把預測錯誤率 bound 在 max_err 以內？

答案非常簡單！通過訓練。你可以把訓練集的上的 error 降到多小都行，只要你模型的表現力足夠強。這個問題和絕大多數機器學習的問題都不同，我們只要照顧好訓練集（也就是被索引的數據）就可以了，沒有測試集！當然也就不會有過擬合，模型的泛化能力是不用考慮的，比想像的簡單吧！

說到模型表現力強，很容易想到神經網路。除此以外，NN 還帶來了另一個好處，在 GPU（或其他專用晶元，比如 Google 的 TPU）上，NN 能獲得驚人的計算速度。NN 的結構決定了它並行起來非常快，時間複雜度上把 O(logn) 的 B 樹等甩在身後。

說到這裡，我們來做個思維拓展：如果把 key 作為橫軸，key 在有序數組中的位置 pos 作為縱軸，畫出目標函數的曲線，那應該長成這個樣子：

這是一個 CDF (累積分布函數，累積的是各個 key 對應數據的長度）。從這個角度看，無論是 B 樹還是預測模型都是在擬合這個函數，只是 approach 完全不同。

這時候再回頭看我們熟悉的 B 樹，有沒有一點頓悟—— Aha! 這不是就是決策樹嗎？

遞歸模型索引 RM-Index

以上已經說完了核心思想，接下來就是要找到一個合適的預測模型來代替 B 樹。實驗發現，直接上 DNN 效果並不好：單次計算時間太長，而且網路很龐大，retrain（增刪改）代價很大。

Naive 的預測模型之所以做的不好，一個重要原因是：把如此大的數據量的誤差 bound 在 min/max_err 之內，實在太難了（所謂 last mile 問題）。為解決這個問題，決策樹給我們做了個很好的提示，如果一個模型解決不了問題，就再加幾層。

舉個例子：為 100M 記錄訓練一個足夠精確的預測器太難，那就分成 3 層樹狀結構。根節點分類器把記錄分出 100 份，每份大約有 1M 記錄；第二層再分出 100 份，每份大約只剩 10K 記錄；第三層再分出 100 份，每份大約有 100 條記錄——假設 100 條紀錄足夠把誤差在 min/max_err 之內。

注意，上圖並不是一棵樹，例如 Model 2.1 和 2.2 都可以選擇 Model 3.2 作為下一層的分類模型。

這樣做的好處是，每層要做的事情簡單多了（每層 precision gain = 100），模型可以變得簡單得多。每個 NN 模型就像一個精通自己領域的專家，他只要學習某個很小子集的 keys 就可以了。這也同時解決了 last mile 難題，大不了為這一百左右個 keys 過擬合一下也無妨。

混合索引

上圖中的三層網路結構還帶來一個額外的優勢：每個 Model 其實是獨立的，我們可以用除了 NN 以外的預測方法代替之，包括線性回歸等簡單演算法，甚至是 B 樹。

事實上，最後選用了兩種 Model：

簡單的神經網路（0～2 層全連接的 hidden layer，ReLU 激發函數，每層最多 32 個神經元）
當葉節點的 NN 模型 error rate 超過閾值時，替換成 B 樹

訓練演算法如下，

簡單說就是：

固定整個 RM-Index 的結構，比如層數、每層 Model 數量等（可以用網格法調參）；
用全部數據訓練根節點，然後用根節點分類後的數據訓練第二層模型，再用第二層分類後的數據訓練第三層；
對於第三層（葉節點），如果 max_error 大於預設的閾值，就換成 B 樹。

有了 Step 3，這個 RM-Index 的分類能力也就有了下界，即使面對純雜訊數據（毫無規律可循），至少能和 B 樹保持差不多的性能。

索引的 keys 常常是字元串，而我們前文說的 NN 模型的輸入是向量。Luckily，字元串向量化是 ML 里研究很多的一個課題了，這裡不再討論，有興趣的可以看下原論文（拋磚引玉為主）。

測試結果

為了對比 RM-Index 和 B 樹的性能，論文作者找了 4 個數據集，分別用 RM-Index 和 B 樹作二級索引。

Weblogs 數據集：訪問時間 timestamp -&> log entry （約 200M）
Maps 數據集：緯度 longitude -&> locations （約 200M）
Web-documents 數據集：documents（字元串）-&> document-id（約 10M）
Lognormal 數據集：按對數正態分布隨機生成的數據

測試中用了不同參數的 Learned Index 和 B 樹，B 樹也用了一個高度優化的實現。

總體來說，Size savings 都相當可觀（下降 1～2 個數量級），而速度也有所優化，最多能快 1 倍。

對於每個數據集，論文都給出了詳細的測試結果，有興趣的同學請看原文。

可以說是符合預期的，個人看法是：

因為演算法 Step 3 的幫助，即使不經過調優，性能至少不輸 B 樹；
肯定能省下許多空間，因為 B 樹是基於比較的查找，葉結點要保存 key 的內容，key 越多索引越大；而 NN 完全不受這個制約。

但暫且不要太激動，這只是查找性能。索引的維護（增／刪／改）代價如何也是要考慮的。用作者原話說，這是 learned index 的阿喀琉斯之踵，因為 NN 模型的 retrain 代價是不可預測的，這是多數 ML 演算法和傳統演算法一個很大的不同點。對此，作者意見如下：

如果恰好新的數據已經能被成功預測了，那就不用 retrain 了；但這太理想化，我們為達到 last mile 做的那些 overfitting 也導致了這個模型泛化性堪憂。
如果一定要 retrain，一個簡單有效的優化是：把變更數據累積起來先放著，批量訓練；
此外，retrain 可以借鑒一些 warm-start 的方法加快訓練過程。

其他索引結構

論文中這部分沒有詳細展開，因為原理和前文幾乎沒有區別，僅僅換一種用法。

Point Index

拳打完 B 樹再來腳踢 hash-map。大家都知道 hash-map 兼具 O(1) 的高效率和低效的空間使用率，想快就要減少碰撞，於是要犧牲更多的空間。所謂空間換時間。即使是 Google 的 Dense-hashmap 也會有 78% 的 overhead。

解決方案如圖所示，用 RM-Index 模型替換掉 hash function。其思想是，利用數據的某些內在特徵，幫助它找到一個最均勻（uniform）的映射方式，而不是用哈希徹底隨機化。

在三個數據集上的測試表明，這一方法的確提升了 slot 的空間利用率，減少了很多空 slot，減少的比例約 -6% ~ -78%。

Existence Index

這回輪到的是 bloom filter，有兩種思路：

直接用一個二分類模型判斷是否存在；
和上一小節的原理類似，把 hash 函數替換成 RMI 模型。

後記

在 Jeff Dean 大神的光環之下，這篇文章很快引起熱烈的討論。

不得不說，這個腦洞開的很大，令人為之一振。一直在人們心中只能做「模糊」預測的 ML 演算法竟然能代替經典的 B 樹，放在 10 年前估計會被噴到體無完膚。

論文的亮點在於，大家一直在「訓練——預測」這樣一個思維下作 ML 而忽視了一點：至少對於已知的數據，ML 演算法也是能輸出一個確定的結果的！換句話說，在全集上訓練，把錯誤率強行 bound 住其實很容易。

下面說說優缺點。

Learned index 對於規律性強的數據是大殺器，作這種數據的二級索引再合適不過了。內在規律越強，就意味著 B 樹、哈希這些通用演算法浪費的越多，這也是 ML 演算法能撿到便宜的地方。

就像很多 DBMS 引入全文索引一樣，未來的 DBMS 也也可以嘗試給用戶更多其他選項，為某些特別有規律的 column 建立非 B 樹／Hash 的二級索引。甚至可以讓 DMBS 智能化，自己嘗試尋找一些規律，將 B 樹索引透明的替換成其他索引。

缺點也是明顯的：增刪改代價難以控制，可想而知，對於規律性不那麼明顯的數據，這足以抹平它查找的速度優勢。但我相信之後會有更多改進的 index 模型出現，把這個代價儘可能減少。

一句話總結個人看法：

B 樹作為通用索引的地位仍然難以撼動，但特定數據場景下，learned index 將成為一個有力的補充。

不久後就會出現：

The Case for Learned Consistent Hashing

The Case for Learned Backup And Restore

The Case for Learned Crash Recovery

The Case for Learned Higher Availability

The Case for Learned Logs

The Case for Learned Replication

...

不太適用於DBMS而很適用於data warehouse。原因很簡單，資料庫要支持的是大量update操作，而這篇paper假設的是已知所有數據然後搞了個DL模型（把這個模型替換成任意的統計模型都是可以的）算了一下分布，而得到這個分布之後我們自然可以通過density來建立出更好的index。

btree也可以用於data warehouse，而跟這個paper思想很不相同的是，btree足夠general，不假設任何的data locality，訪問任何數據無論數據分布以及訪問頻率都在N(logN)內完成。由於不假設任何數據分布，btree也沒有做壓縮。然而ML模型本身就是可以看成對數據進行壓縮的一種手段，因此文中用DL實驗跑出來發現節約了很多memory也是不足為奇。

其實現有的類似idea的paper已經很多了，比如perfect hashing等等。

要搞DBMS的話database cracking是一條出路，當然也有work在做workload prediction然後動態調整資料庫的結構，比如locking protocol的方式，比如index的選擇等等。這些都是DBMS的經典問題了。

話說回來還是挺看好這篇paper的，思路新穎，完美的把ML跟database結合起來，citation肯定會很高，能在資料庫領域能夠帶動一波follow-up work。

歡迎大家討論。

1.代碼和數據一樣，都是數據。

2.代碼可以生成數據，數據也可以生成代碼。兩者是互換的，等價的。

3.模型可以理解是動態生成的數據，也可以互換成為動態生成的代碼。

4.在context不變下，軟體是可變的硬體（含微碼）。在context可變下，AI是可變的軟體。

簡單喵了一下論文，看到了這個圖。

意思是把K-V結構裡面的哈希函數換成了一個model，感覺這個思路可以解決用傳統演算法很難處理的一些問題（比如碰撞，優化負載因子等等）

感覺這個思路擴展開來可以對很多傳統演算法已經解決的問題進行優化，很有意思。

也想做這種事，首先，你要擁有強大至極的基礎設施，國內在基礎設施建設方面...

今天剛好看見我之前關於index的論文被這paper cite了，隨手讀了一下，結果一上知乎就看見這paper了...