學界 | Jeff Dean新提出機器學習索引替代B-Trees:可提速3倍

 2017-12-13 11:51:00.0

原標題:學界 | Jeff Dean新提出機器學習索引替代B-Trees:可提速3倍

選自arXiv

Jeff Dean 的最新論文中把索引視爲模型,探索了深度學習模型學習的索引優於傳統索引結構的條件。初步結果表明,藉助神經網絡學習索引可以超過緩存優化的 B-Trees 高達 70%的速度,同時爲若干個真實數據集節省一個數量級的內存。作者認爲這個方法將徹底革新傳統的數據庫系統的開發方式。

無論什麼時候,高效的數據訪問方式都是必需的,所以索引的結構就成爲了關鍵。此外,目前存在多種索引的選擇來解決各種訪問模式的需求。例如 B-Trees 是範圍請求最好的選擇(例如在特定時間線上索引所有的數據記錄),哈希表(Hash-Maps)在性能上很難打敗基於鍵值的搜索方法,而布隆過濾器 (Bloom Filter) 通常用於檢測是否存在某條記錄。由於索引對於數據庫系統和其它一些應用的重要性,過去幾十年來,它們已經廣泛地發展爲更高的內存、緩存和 CPU 效率 [28, 48, 22, 11] 的方法。

在這篇論文中,作者探索了包括神經網絡的學習模型(learned model)在多大程度上可以取代傳統的索引結構(包括從 B-Trees 到布隆過濾器)。這可能看起來有點反直覺,因爲機器學習無法爲作者提供傳統意義上使用索引的語義保證(semantic guarantee),並且最強大的機器學習模型——神經網絡通常被認爲其評估過程非常耗能。然而,作者認爲這些問題都不是問題。相反,作者認爲使用學習模型的建議擁有很大的潛在價值,特別是對於下一代的硬件。

從語義保證方面來說,索引已經在很大程度上類似於學習模型,從而能很直接地被其它類型的模型所取代(例如神經網絡)。例如,一個 B-Tree 可以被看成一個模型,把鍵作爲輸入,並預測數據記錄的位置。一個布隆過濾器可以看成一個二值分類器,預測一個鍵是否存在於一個集合中。

從性能方面來說,作者觀察到所有的 CPU 都已經擁有了強大的單指令多數據(SIMD)功能,並且可以推測很多移動設備都將很快擁有 GPU 或 TPU。同樣,由於通過神經網絡(而不是通用指令集)能很容易地擴展並行數學運算的受限集,推測 CPU-SIMD/GPU/TPU 將迅速變得很強大也是合理的。從而執行一個神經網絡的高耗能在未來將是可忽略的。例如,英偉達和谷歌的 TPU 都已經可以在單次循環中運行成千上萬次神經網絡運算 [3]。此外,據說 GPU 到 2025 年時將達到 1000 倍的性能提升,儘管 CPU 的摩爾定律已經基本失效 [5]。通過使用神經網絡取代分支複雜的索引架構,這些硬件進化趨勢可以爲數據庫帶來很高的效益。

需要注意的是,作者並沒有說要用學習到的索引結構完全取代傳統的索引結構。更準確地說,他們概述了一種建立索引的新方法,可以作爲當前工作的補充,並將開闢一個新的研究方向。雖然只聚焦於只讀分析型負載,但他們還概述瞭如何將這個想法擴展以加速寫入繁重的負載的索引建立。此外還簡要地概述了同樣的理論如何用於取代數據庫系統的其它組件和操作,包括分類和合並。如果成功了,將徹底革新傳統的數據庫系統的開發方式。

本論文的其餘部分概述如下:下一節中作者使用 B-Trees 作爲實例介紹了學習索引的整體想法。第 4 節中,作者將這一想法擴展到哈希索引,在第 5 節擴展到布隆過濾器。所有章節包含一個單獨的評估,並列舉開放的挑戰。最後章節 6 中討論了相關工作,章節 7 給出結論。

圖 1:爲什麼 B-Trees 是模型

這篇論文只關注兩種模型:簡單的神經網絡(帶有 0 到 2 個全連接隱藏層、ReLU 激活函數以及最高 32 個神經元的層寬)和 B-Trees(也稱爲決策樹)。在索引配置給定的情況下,即指定階段的數量和每個階段模型的數量作爲一個大小(size)的數組,混合索引的端到端訓練如算法 1 所示。

從整個數據集(第三行)開始,它首先訓練頂部節點模型。基於這一頂部節點模型的預測,然後從下一個階段(第 9 行和第 10 行)中選取模型,並添加所有屬於該模型(第 10 行)的鍵。最後,在混合索引的情況中,如果絕對最小/最大誤差高於預定義閾值(第 11-14 行),則用 B-Tree 替代 NN 模型來優化索引。

注意,作者爲最後階段的每個模型保存了標準誤差和最小、最大誤差。這樣做的好處是可以根據每個鍵的使用模型單獨地限制搜索空間。此外,人們可能想知道如何設置混合端到端訓練的不同參數,包括階段的數量和寬度、神經網絡配置(即隱藏層的數量和寬度)和替代 B-Tree 節點的閾值。通常,這些參數可以使用簡單的網格搜索進行優化。並且,可以根據最佳實踐顯著地限制搜索空間。例如,作者發現 128 或 256(B-Tree 的典型頁面大小)的閾值運行良好。此外,對於 CPU 我們很少提供多出 1 或 2 個全連接隱藏層和每層 8 到 128 個神經元的神經網絡。最終,在模型容量相當低的情況下,可以用較少的數據樣本訓練較高級別的模型階段,這大大加快了訓練進程。

注意,混合索引允許把學習索引的最差表現限定爲 B-Trees 的表現。也就是說,在不可能學習數據分佈的情況下,所有模型將自動被 B-Trees 替代,使它成爲一個實際上完整的 B-Tree(不同階段之間有一些額外的開銷等等,但性能總體是相似的)。

圖 4:圖數據:學習索引 vs B-Tree

圖 9:傳統哈希表 vs 學習哈希表

圖 10:模型 vs 隨機哈希表

論文:The Case for Learned Index Structures

論文鏈接:https://arxiv.org/abs/1712.01208

摘要:索引即是模型:B-Tree-Index 可被看作一個模型,把鍵(Key)映射到排序數組中的記錄位置;Hash-Index 可被看作一個模型,把鍵映射到未排序數組中的記錄位置;BitMap-Index 也可被看作一個模型,指明數據記錄是否存在。在這篇探索性的論文中,我們從這一前提出發,假定所有現存的索引結構皆可由其他模型替代,包括我們稱之爲「學習索引」(learned indexes)的深度學習模型。本論文的核心思想是一個模型可以學習排序順序或查找鍵的結構,並使用這一信號有效地預測記錄的位置或存在。我們從理論上分析了學習索引在什麼條件下表現優於傳統索引結構,並描述了設計學習索引結構的主要挑戰。我們的初步結果表明,藉助神經網絡,我們能夠超過緩存優化的 B-Trees 高達 70%的速度,同時爲若干個真實數據集節省一個數量級的內存。更重要的是,我們相信通過學習模型取代數據管理系統核心組件的想法對於未來的系統設計有着深遠的影響,而且這項工作僅僅展示了所有可能性中的一部分。


文章來源:機器之心