本周，谷歌團隊在arXiv上傳了一篇論文，探討用機器學習取代數據庫索引，引發了大量的關注和討論。作者還概述了如何使用這一思想來替換數據庫系統的其他組件和操作，包括排序和連接。如果成功，數據系統的開發方式將會徹底改變。

“如果這項研究取得更多的成果，將來有一天我們很可能回過頭看然后說，索引是最先倒下的，接著是其他的數據庫組件（排序算法、查詢優化、連接），它們都逐漸被神經網絡取代。”紐約州立大學布法羅分校的計算機科學和工程教授Murat Demirbas這樣說。

文章描述了一個非常有前景且十分有趣的方向，題目讀來也頗有小說的感覺——“The Case for Learned Index Structures”。

這篇論文旨在證明“機器學習模型有潛力大幅超越當前最先進的數據庫索引，提供好很多的性能”。

斯坦福大學Chirs Manning教授發表Twitter，評論稱谷歌團隊這篇論文用機器學習替代傳統算法，而且“一口吃掉一大塊”

索引（Index），就是一種對數據庫表中一列或多列的值進行排序的結構，使用索引可以快速訪問數據庫表中的特定信息。數據庫的索引好比圖書的目錄，目錄能讓你在看書時不把整本書看完就快速找到需要的信息，索引也能讓數據庫程序迅速地找到表中的數據，而不必將整個數據庫掃描完。

但是，數據庫在應用索引時，對數據本身并不了解，數據相當于一個黑盒，而不了解數據的分布，造成了很大的浪費。

舉例來說，如果鍵的范圍在0到500m之間，比起用哈希，直接把鍵當索引速度可能更快。如果知道了數據的累積分布函數（CDF），“CDF*鍵*記錄大小”可能約等于要查找的記錄的位置，這一點也適用于其他數據分布的情況。

數據的累積分布函數（CDF）可以作為索引

作者在論文中表示，精確了解數據分布，可以大幅優化當前數據庫系統使用的幾乎所有索引結構。

但是，精確了解數據分布，數據庫就成了“白盒”，失去了可重用性。這樣一來就需要檢查數據，每次都從頭開始設計索引。

于是，谷歌研究人員想到了機器學習方法，并使用其中最強的一種——神經網絡，去學習數據分布，并用學到的知識預測數據的分布。

這樣一種折中的方法，讓數據索引變得“data-aware”，由此獲得性能的提升。

他們將神經網絡應用于三種索引類型：B樹，用于處理范圍查詢；哈希映射（Hash-map），用于點查找查詢；以及Bloom-filter，用于設置包含檢查。下面著重介紹一下作者如何用神經網絡替代B樹。

B樹提供了一種有效的分層索引。從概念上講，B-tree將一個鍵映射到一個頁面。因此，我們可以用一個模型，也進行鍵的位置映射，而對于錯誤范圍，我們可以做一個二進制搜索（或擴展環搜索）的變體來定位頁面。

要知道min_error和max-error，就用擁有的數據來訓練模型。數據是靜態的，神經網絡進行預測，然后從這些錯誤中學習。即使簡單的邏輯回歸也可以用于簡單的分布。

在測試時，作者將機器學習索引與B樹進行比較，他們使用了3個真實世界數據集，其中網絡日志數據集（Weblogs）對索引而言極具挑戰性，包含了200多萬個日志條目，是很多年的大學網站的請求，而且每個請求都有單一的時間戳，數據中含有非常復雜的時間模式，包括課程安排、周末、假期、午餐休息、部門活動、學期休息，這些都是非常難以學習的。

從上圖可見，對于網絡日志數據，機器學習索引帶來的速度提升最高達到了53%，對應的體積也有76%的縮小，相比之下誤差范圍稍有加大。

用機器學習模型替換B樹的好處是：

• 索引結構更小：更少的主內存或L1緩存

• 查找速度更快：因為索引變小了

• 更強的并行性（TPU），而不是B-樹中的分層if語句

這里有一個關鍵點，那就是用計算換內存，計算越來越便宜，CPU-SIMD/GPU/TPU的功能越來越強大，作者甚至指出，“運行神經網絡的高昂成本在未來可以忽略不計——谷歌TPU能夠在一個周期內最高完成上萬次神經網絡運算。有人聲稱，到2025年CPU的性能將提高1000倍，基于摩爾定律的CPU在本質上將不復存在。利用神經網絡取代分支重索引結構，數據庫可以從這些硬件的發展趨勢中受益。”

論文還介紹了幾個策略來提高機器學習索引的性能，包括使用遞歸模型索引、分層模型和混合模型。機器學習方法都帶來了能效提升，具體的評估結果請參考論文。

需要指出，作者并不認為機器學習索引結構可以完全替代傳統索引。“我們論述了一種建立索引的新方法，它完善了現有的研究，并且為該領域數十年的研究開辟了一個新方向。”

作者還概述了如何使用這一思想來替換數據庫系統的其他組件和操作，包括排序和連接。如果成功，數據系統的開發方式將會徹底改變。

摘要

索引就是模型：B-Tree-Index可以被看作一個將鍵（key）映射到排序數組中記錄位置的模型，哈希索引可以被看作將鍵映射到未分類數組中記錄位置的模型，而BitMap-Index可以被看作查看數據記錄是否存在的模型。

在這篇探索性研究論文中，我們從這個前提出發，假設所有現有的索引結構都可以用其他類型的模型來代替，包括深度學習模型，也即文中所謂的“機器學習索引”（learned indexes）。

本文關鍵思想是，一個模型可以學習排序順序或查找鍵的結構，并使用這個信號來有效預測記錄的位置或記錄是否存在。我們從理論上分析了在哪些條件下機器學習索引的性能優于傳統索引結構，描述了設計機器學習索引的主要挑戰。

我們在幾個真實世界的數據集上做了測試，初步結果表明，通過使用神經網絡，我們在速度上能比緩存優化的B樹快70％，同時內存節省了一個數量級。更重要的是，我們相信用機器學習模型取代數據管理系統核心組件的想法，對未來的系統設計有著深遠的影響，這項工作僅僅展現了未來無限可能的一瞥。