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

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

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

這篇論文旨在證明“機器學(xué)習(xí)模型有潛力大幅超越當(dāng)前最先進的數(shù)據(jù)庫索引，提供好很多的性能”。

斯坦福大學(xué)Chirs Manning教授發(fā)表Twitter，評論稱谷歌團隊這篇論文用機器學(xué)習(xí)替代傳統(tǒng)算法，而且“一口吃掉一大塊”

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

但是，數(shù)據(jù)庫在應(yīng)用索引時，對數(shù)據(jù)本身并不了解，數(shù)據(jù)相當(dāng)于一個黑盒，而不了解數(shù)據(jù)的分布，造成了很大的浪費。

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

數(shù)據(jù)的累積分布函數(shù)（CDF）可以作為索引

作者在論文中表示，精確了解數(shù)據(jù)分布，可以大幅優(yōu)化當(dāng)前數(shù)據(jù)庫系統(tǒng)使用的幾乎所有索引結(jié)構(gòu)。

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

于是，谷歌研究人員想到了機器學(xué)習(xí)方法，并使用其中最強的一種——神經(jīng)網(wǎng)絡(luò)，去學(xué)習(xí)數(shù)據(jù)分布，并用學(xué)到的知識預(yù)測數(shù)據(jù)的分布。

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

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

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

要知道m(xù)in_error和max-error，就用擁有的數(shù)據(jù)來訓(xùn)練模型。數(shù)據(jù)是靜態(tài)的，神經(jīng)網(wǎng)絡(luò)進行預(yù)測，然后從這些錯誤中學(xué)習(xí)。即使簡單的邏輯回歸也可以用于簡單的分布。

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

從上圖可見，對于網(wǎng)絡(luò)日志數(shù)據(jù)，機器學(xué)習(xí)索引帶來的速度提升最高達到了53%，對應(yīng)的體積也有76%的縮小，相比之下誤差范圍稍有加大。

用機器學(xué)習(xí)模型替換B樹的好處是：

• 索引結(jié)構(gòu)更?。焊俚闹鲀?nèi)存或L1緩存

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

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

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

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

需要指出，作者并不認為機器學(xué)習(xí)索引結(jié)構(gòu)可以完全替代傳統(tǒng)索引?！拔覀冋撌隽艘环N建立索引的新方法，它完善了現(xiàn)有的研究，并且為該領(lǐng)域數(shù)十年的研究開辟了一個新方向?！?/span>

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

摘要

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

在這篇探索性研究論文中，我們從這個前提出發(fā)，假設(shè)所有現(xiàn)有的索引結(jié)構(gòu)都可以用其他類型的模型來代替，包括深度學(xué)習(xí)模型，也即文中所謂的“機器學(xué)習(xí)索引”（learned indexes）。

本文關(guān)鍵思想是，一個模型可以學(xué)習(xí)排序順序或查找鍵的結(jié)構(gòu)，并使用這個信號來有效預(yù)測記錄的位置或記錄是否存在。我們從理論上分析了在哪些條件下機器學(xué)習(xí)索引的性能優(yōu)于傳統(tǒng)索引結(jié)構(gòu)，描述了設(shè)計機器學(xué)習(xí)索引的主要挑戰(zhàn)。

我們在幾個真實世界的數(shù)據(jù)集上做了測試，初步結(jié)果表明，通過使用神經(jīng)網(wǎng)絡(luò)，我們在速度上能比緩存優(yōu)化的B樹快70％，同時內(nèi)存節(jié)省了一個數(shù)量級。更重要的是，我們相信用機器學(xué)習(xí)模型取代數(shù)據(jù)管理系統(tǒng)核心組件的想法，對未來的系統(tǒng)設(shè)計有著深遠的影響，這項工作僅僅展現(xiàn)了未來無限可能的一瞥。