學(xué)習(xí)索引:現(xiàn)狀與研究展望*

張 洲 ,金培權(quán) ,謝?？?/p>

1(中國科學(xué)技術(shù)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 合肥 230026)

2(電磁空間信息重點實驗室(中國科學(xué)院),安徽 合肥 230026)

索引是數(shù)據(jù)庫系統(tǒng)中用于提升數(shù)據(jù)存取性能的主要技術(shù)之一.傳統(tǒng)數(shù)據(jù)庫系統(tǒng)一般使用磁盤作為持久性存儲設(shè)備.但是由于磁盤的訪問延遲較高,磁盤I/O 次數(shù)成為影響數(shù)據(jù)庫系統(tǒng)性能的關(guān)鍵指標.如何快速地在磁盤中找到數(shù)據(jù),成為數(shù)據(jù)庫系統(tǒng)中的重要問題.自20 世紀70 年代以來,數(shù)據(jù)庫領(lǐng)域的研究人員提出了各種各樣的索引結(jié)構(gòu),用于滿足不同數(shù)據(jù)類型的存取性能需求.例如,著名的B+樹索引結(jié)構(gòu)[1]提供了O(logmn)的查詢時間復(fù)雜度(m為一個樹節(jié)點的容量)[2].通常情況下,B+樹索引的I/O 次數(shù)為3～4 次,遠遠優(yōu)于無索引的搜索算法(例如二分搜索).而且,由于數(shù)據(jù)在B+樹的葉節(jié)點中有序存儲,它也可以支持高效的范圍查詢.

傳統(tǒng)的B+樹索引是基于磁盤而設(shè)計的,即假設(shè)整個索引完全存儲在磁盤中.為了提升數(shù)據(jù)庫系統(tǒng)的讀寫性能,現(xiàn)代數(shù)據(jù)庫系統(tǒng)傾向于將整個索引緩存在內(nèi)存中.當數(shù)據(jù)庫規(guī)模較小時,緩存索引是可行的.然而,在大數(shù)據(jù)時代,數(shù)據(jù)量可能達到PB 級甚至百PB 級.例如,物聯(lián)網(wǎng)中的高頻傳感器采集數(shù)據(jù)、大型互聯(lián)網(wǎng)交易平臺的日志數(shù)據(jù)等每天都會產(chǎn)生大量的新數(shù)據(jù),使得數(shù)據(jù)庫規(guī)模極速增長.這種情況下,傳統(tǒng)的B+樹索引因其具有O(n)的空間復(fù)雜度將無法全部緩存在內(nèi)存,進而影響查詢性能.雖然近年來有研究者提出了內(nèi)存數(shù)據(jù)庫(main memory database)[3]來支持大數(shù)據(jù)的實時存取,但內(nèi)存數(shù)據(jù)庫的索引結(jié)構(gòu)[4,5]同樣也具有O(n)的空間復(fù)雜度.研究表明,在商用內(nèi)存數(shù)據(jù)庫中,索引占用了全部內(nèi)存空間的55%,嚴重侵占了數(shù)據(jù)庫系統(tǒng)的內(nèi)存資源[6].總體而言,傳統(tǒng)索引在大數(shù)據(jù)環(huán)境下呈現(xiàn)出兩個主要問題:(1) 空間代價過高.例如,B+樹索引需要借助O(n)規(guī)模的額外空間來索引原始的數(shù)據(jù),這對于大數(shù)據(jù)環(huán)境而言是難以容忍的.(2) 每次查詢需要多次的間接搜索.例如,B+樹中的每次查詢都需要訪問從樹根到葉節(jié)點路徑上的所有節(jié)點,這使得B+樹的查找性能在大規(guī)模數(shù)據(jù)集上將變得較差.

近年來,人工智能、機器學(xué)習(xí)技術(shù)的快速發(fā)展引起了數(shù)據(jù)庫領(lǐng)域的重視.如何借助人工智能、機器學(xué)習(xí)技術(shù)來優(yōu)化數(shù)據(jù)庫索引等傳統(tǒng)數(shù)據(jù)庫技術(shù),成為當前數(shù)據(jù)庫領(lǐng)域關(guān)注的熱點問題.MIT 的研究人員Kraska 等人在2018 年SIGMOD 會議上首次提出了學(xué)習(xí)索引(learned index)[7]的概念.他們將機器學(xué)習(xí)方法應(yīng)用于索引結(jié)構(gòu)中,目的是降低索引的空間代價,同時提升索引的查詢性能.傳統(tǒng)的B+樹索引使用簡單的if 語句遞歸地劃分空間,這一方法沒有利用數(shù)據(jù)的分布規(guī)律,具有次優(yōu)的空間代價和查詢性能;而學(xué)習(xí)索引則使用機器學(xué)習(xí)模型替代傳統(tǒng)的索引結(jié)構(gòu),可以大幅度地降低傳統(tǒng)索引的空間代價并提高查詢性能.

從目前的發(fā)展趨勢來看,學(xué)習(xí)索引因其理論上的優(yōu)勢,有望成為索引技術(shù)的下一代研究方向.近年來,國際數(shù)據(jù)庫界在這一方向上開展了大量研究,并取得了一系列成果.例如,SIGMOD 2020 就收錄了7 篇學(xué)習(xí)索引相關(guān)論文.但是,目前還沒有專門的綜述文章對學(xué)習(xí)索引這一研究方向進行系統(tǒng)總結(jié).本文對學(xué)習(xí)索引的現(xiàn)有研究工作進行了系統(tǒng)梳理和分類,介紹并對比了各種類型的學(xué)習(xí)索引技術(shù),并展望了未來研究方向,以期為相關(guān)的研究人員提供一定的參考.

與相關(guān)綜述性文獻的區(qū)別如下.

(1) 學(xué)習(xí)索引是當前國內(nèi)外較新的一個研究方向,目前還沒有專門針對學(xué)習(xí)索引的綜述文章.本文是第一篇系統(tǒng)總結(jié)學(xué)習(xí)索引研究進展的中文綜述.自2019 年以來的一些綜述文章關(guān)注于機器學(xué)習(xí)化數(shù)據(jù)庫技術(shù)[8-11],但它們只簡要介紹了學(xué)習(xí)索引的概念,沒有專門總結(jié)該方向的最新進展和發(fā)展趨勢.需要指出的是,學(xué)習(xí)索引的研究進展主要集中在近兩年,本文涵蓋了包含SIGMOD 2020 會議在內(nèi)的最新相關(guān)工作,提供了該方向較全面的研究工作總結(jié)和展望.

(2) 提出了一個新的學(xué)習(xí)索引研究分類框架.該框架從范圍查詢、點查詢、存在查詢、測試基準等方面對當前研究進行了分類和總結(jié),這一分類框架可以為后續(xù)研究提供參考.

(3) 討論了學(xué)習(xí)索引的未來發(fā)展趨勢,給出了7 個值得研究的未來方向,并進行了討論.這些方向基于我們對現(xiàn)有工作的深入思考,對相關(guān)研究人員有一定的參考價值.

本文前4 節(jié)分別介紹學(xué)習(xí)索引在面向一維范圍查詢的索引(見第1 節(jié))、面向多維范圍查詢的索引(見第2節(jié))、面向點查詢的索引(見第3 節(jié))以及面向存在查詢的索引(見第4 節(jié))中的相關(guān)工作.第5 節(jié)討論學(xué)習(xí)索引的測試基準.第6 節(jié)對學(xué)習(xí)索引的未來研究方向進行展望.最后,第7 節(jié)總結(jié)全文.

1 面向一維范圍查詢的學(xué)習(xí)索引

面向一維范圍查詢的索引結(jié)構(gòu),需要高效地支持插入、刪除、更新、點查詢和范圍查詢等操作.這一類型索引結(jié)構(gòu)的應(yīng)用最為普遍,被大多數(shù)通用型數(shù)據(jù)庫采納為默認索引.常見的面向一維范圍查詢的索引結(jié)構(gòu)有B+樹和日志結(jié)構(gòu)合并(log-structured merge,簡稱LSM)樹[12].目前,使用機器學(xué)習(xí)模型替代這一類型的索引結(jié)構(gòu)吸引了較多的關(guān)注,因此本節(jié)首先討論面向一維范圍查詢的學(xué)習(xí)索引方面的研究進展.

在第1.1 節(jié)中,我們首先介紹學(xué)習(xí)索引的基本思想和面向主索引的學(xué)習(xí)索引以及相關(guān)的優(yōu)化技術(shù).第1.2 節(jié)介紹面向二級索引的學(xué)習(xí)索引.第1.3 節(jié)對比分析已有的學(xué)習(xí)索引技術(shù)差異.最后,在第1.4 節(jié)中結(jié)合實驗結(jié)果對比傳統(tǒng)B+樹和學(xué)習(xí)索引,分析學(xué)習(xí)索引的優(yōu)勢和存在的不足.

1.1 面向主索引的學(xué)習(xí)索引

為了能夠高效地支持范圍查詢操作,面向一維范圍查詢的索引通常要求底層數(shù)據(jù)按照查找鍵有序存放.這類索引在傳統(tǒng)關(guān)系數(shù)據(jù)庫中稱為主索引(primary index).傳統(tǒng)DBMS 默認會在主碼上創(chuàng)建主索引.由于大多數(shù)數(shù)據(jù)庫應(yīng)用都會頻繁執(zhí)行基于主碼的查詢,因此主索引的優(yōu)化對于提升數(shù)據(jù)庫系統(tǒng)的查詢性能有著重要的價值.因此,早期的學(xué)習(xí)索引研究工作也大都集中在主索引上.

1) 初次嘗試.

B+樹是傳統(tǒng)數(shù)據(jù)庫系統(tǒng)中常見的一維索引結(jié)構(gòu).B+樹可以看作是一個模型,它的輸入是一個鍵,輸出是該鍵對應(yīng)的記錄在排序數(shù)組中的位置.B+樹不會索引排序記錄的每個鍵,而只索引一個內(nèi)存塊或磁盤頁中的第1個鍵.這有助于顯著減少索引存儲的鍵的數(shù)量,而不會對索引性能造成很大的影響.這一特性讓B+樹和大多數(shù)機器學(xué)習(xí)模型看起來很相似.可以將B+樹看作是一棵回歸樹(regression tree),它將一個鍵映射到一個具有最大誤差界限(error bound)(即內(nèi)存塊或磁盤頁大小)的數(shù)組位置,并保證:如果該鍵對應(yīng)的記錄存在,就可以在誤差范圍內(nèi)找到它[7].因此,用其他機器學(xué)習(xí)模型替代B+樹是可行的,只要這些模型也能夠提供類似的保證.顯然,所有的回歸模型都能夠提供類似的保證,包括線性回歸模型和神經(jīng)網(wǎng)絡(luò)模型.

首先考慮一個理想情況下的示例.假設(shè)數(shù)據(jù)庫中共有1 000 個記錄,它們使用整數(shù)型的鍵,分別對應(yīng)數(shù)字1～1000.在這種情況下,我們使用線性回歸模型替代B+樹索引,只需要保存模型的參數(shù)(即斜率和截距),具有O(1)的空間復(fù)雜度.由于模型能夠準確地預(yù)測出記錄位置,該模型查詢的時間復(fù)雜度也是O(1).此外,如果后續(xù)插入的數(shù)據(jù)仍然滿足這一規(guī)律,則模型不需要更新就可以繼續(xù)為新插入的數(shù)據(jù)提供索引支持.綜上所述,對于理想的情況,機器學(xué)習(xí)模型在空間代價、查詢性能和索引更新代價上全方面地優(yōu)于傳統(tǒng)的B+樹.然而,在大多數(shù)應(yīng)用中,數(shù)據(jù)的分布不是嚴格遵循某種規(guī)律的,數(shù)據(jù)分布的規(guī)律也不會如此簡單.總的來說,面向一維范圍查詢的學(xué)習(xí)索引的設(shè)計目標如下:在一個排序數(shù)組上,使用一個或一組模型有效地近似累積分布函數(shù)(cumulative distribution function,簡稱CDF),使用該模型可以高效地預(yù)測出給定鍵在數(shù)組中的位置.

Kraska 等人基于上述思想進行了學(xué)習(xí)索引的初次嘗試.他們使用Tensorflow[13]在一個Web 服務(wù)器日志記錄數(shù)據(jù)集上構(gòu)建了一個主索引[7],然后使用ReLU(rectified linear unit)激活函數(shù)訓(xùn)練了一個每層32 個神經(jīng)元的雙層全連接神經(jīng)網(wǎng)絡(luò),并以時間戳作為輸入預(yù)測記錄在排序數(shù)組中的位置.然而,實驗結(jié)果表明,該模型的平均執(zhí)行時間高達80ms,遠遠差于B+樹的300ns 和二分搜索的900ns 的搜索時間.總的來說,神經(jīng)網(wǎng)絡(luò)模型的低效率是由如下3 個方面的原因造成的.

(1) Tensorflow 的設(shè)計目標是高效地運行大規(guī)模的模型,而非小模型.并且,使用Tensorflow 需要承擔一個較大的調(diào)用開銷.

(2) 由于B+樹使用簡單的if 語句遞歸地劃分空間,所以它可以覆蓋所有的數(shù)據(jù),能夠為面向全體數(shù)據(jù)的查找提供固定的誤差范圍,而不必關(guān)系數(shù)據(jù)的具體分布特點.相比之下,機器學(xué)習(xí)模型只能保證當擬合CDF 曲線較好時取得較準確的查詢結(jié)果,但機器學(xué)習(xí)的預(yù)測難以做到百分之百的精確,這是因為現(xiàn)實世界的數(shù)據(jù)遵循統(tǒng)計學(xué)中著名的固定效應(yīng)(fixed effect)和隨機效應(yīng)(random effect)[14,15].因此,像神經(jīng)網(wǎng)絡(luò)、多項式回歸等模型能夠高效地將位置確定到數(shù)千的范圍,卻難以精確到單個記錄.

(3) B+樹的搜索計算代價較低,而神經(jīng)網(wǎng)絡(luò)模型的計算需要多次乘法操作,具有較高的計算代價.

為了解決上述問題,Kraska 等人[7]提出了學(xué)習(xí)索引框架(learning index framework,簡稱LIF)和遞歸模型索引(recursive model index,簡稱RMI).LIF 是一個索引合成系統(tǒng),用于生成索引配置、自動地優(yōu)化和測試索引.LIF能夠?qū)W習(xí)簡單的模型(例如線性回歸模型),并依賴Tensorflow 訓(xùn)練復(fù)雜的模型(例如神經(jīng)網(wǎng)絡(luò)模型).但是,LIF 在執(zhí)行模型時不使用Tensorflow,而是自動提取模型的權(quán)重并生成高效的C++索引代碼.LIF 的代碼生成是專為小模型設(shè)計的,它消除了Tensorflow 中管理大模型的所有不必要的開銷和工具[16].實驗結(jié)果表明,LIF 執(zhí)行簡單模型只需要30ns.

RMI 旨在解決學(xué)習(xí)索引的精度問題,它受到了混合專家模型[17]的啟發(fā).RMI 的結(jié)構(gòu)(如圖1 所示)是由多個模型組成的分層模型結(jié)構(gòu).其中,第1 層只有一個模型,其余每一層都包含多個模型.RMI 中的每一個模型都以鍵作為輸入,并返回一個位置.上層模型的輸出結(jié)果用于選擇下一層的模型,最后一層模型的輸出作為RMI 的輸出.RMI 的分層模型結(jié)構(gòu)有以下優(yōu)點.

(1) 與使用一個復(fù)雜的大模型相比,RMI 的執(zhí)行成本更低.與B+樹相比,上層模型的輸出直接用于選擇下層模型,不需要執(zhí)行額外的搜索.

(2) 它利用了之前實驗得到的結(jié)論,即機器學(xué)習(xí)模型可以擬合CDF 的大體形狀,這是RMI 中第1 層模型的作用.由于建立在整個數(shù)據(jù)集上的單一模型難以精確定位到單條記錄,RMI 將數(shù)據(jù)集劃分為更小的子空間,并在每個子空間上訓(xùn)練模型,從而提高查找精度.

(3) RMI 允許構(gòu)建混合使用多種模型,因此能夠充分利用不同模型的優(yōu)點.對于第1 層模型,使用神經(jīng)網(wǎng)絡(luò)是一種較好的選擇,因為神經(jīng)網(wǎng)絡(luò)通常能夠?qū)W習(xí)復(fù)雜的數(shù)據(jù)分布.RMI 的底層可以考慮線性回歸模型,因為線性回歸模型具有更低的空間代價和執(zhí)行成本.如果數(shù)據(jù)分布難以擬合為某種模型,葉節(jié)點允許退化為B+樹節(jié)點,這保證了學(xué)習(xí)索引的最差查找性能與B+樹相當.

Fig.1 Layered models in RMI圖1 RMI 中的分層模型

在RMI 輸出預(yù)測的位置后,還需要在排序數(shù)組中進行最后的搜索.RMI 最底層的每個模型在訓(xùn)練時會保存一個誤差界限,后續(xù)的搜索策略使用預(yù)測值作為中心點,在誤差范圍內(nèi)執(zhí)行二分搜索.Kraska 等人報告的實驗結(jié)果[7]令人振奮:在多個數(shù)據(jù)集上,學(xué)習(xí)索引的查找性能比B+樹快1.5 倍～3 倍,并且僅占用了比B+樹低2 個數(shù)量級的空間.

Kraska 等人提出的學(xué)習(xí)索引雖然具有較好的查找性能和較低的空間代價,但它也存在一些不足.

缺陷1.這類學(xué)習(xí)索引不支持插入操作,因為插入數(shù)據(jù)可能會違反模型預(yù)先保存的誤差閾值.同時,大量的新數(shù)據(jù)會改變鍵的分布,并導(dǎo)致模型過時,最終降低模型在查找時的預(yù)測精度.

缺陷2.在Kraska 等人提出的學(xué)習(xí)索引中,一個最底層模型覆蓋的數(shù)據(jù)集空間比B+樹的一個葉節(jié)點覆蓋的數(shù)據(jù)集空間更大,因此,如果模型的最大誤差較大,將導(dǎo)致在數(shù)據(jù)集上執(zhí)行二分搜索的代價變高.

缺陷3.這類學(xué)習(xí)索引要求底層數(shù)據(jù)按照查找鍵有序存儲,因此只能用作主索引.由于主索引在1 個表上只能存在1 個,因此如果需要在非碼屬性上建立多個學(xué)習(xí)索引,則無法實現(xiàn).而且,在非碼屬性上建立學(xué)習(xí)索引時也需要對數(shù)據(jù)進行排序,會帶來額外的排序、指針操作等代價.

2) 進一步的優(yōu)化策略.

針對上述缺陷,近兩年來研究人員提出了一系列的優(yōu)化方法.這些優(yōu)化方法大致可分為兩類:一是優(yōu)化面向主索引的學(xué)習(xí)索引,使其能夠克服缺陷1 和缺陷2;二是提出面向二級索引的學(xué)習(xí)索引.下面簡要介紹第1 類面向主索引的學(xué)習(xí)索引優(yōu)化策略,第2 類面向二級索引的學(xué)習(xí)索引將在第1.2 節(jié)中詳細加以討論.

(1) 基于緩沖區(qū)的插入策略與固定大小的模型誤差.FITing-Tree[18]使用分段線性函數(shù)(piece-wise linear function)擬合數(shù)據(jù)分布,其索引結(jié)構(gòu)如圖2 所示.FITing-Tree 將已排序的數(shù)據(jù)按范圍劃分成多個段(segment),每個段使用一個線性回歸模型進行擬合.FITing-Tree 的結(jié)構(gòu)與傳統(tǒng)的B+樹十分相似,所不同的是,其葉節(jié)點存儲每個段的起始鍵和斜率.與初版學(xué)習(xí)索引不同,FITing-Tree 設(shè)計了分段策略,它使用一個預(yù)先設(shè)置的誤差閾值作為參數(shù),在分段時保證每個段中的所有數(shù)據(jù)都能落在模型預(yù)測值的誤差范圍內(nèi);如果不能滿足給定的誤差閾值,則啟用一個新的段.通過分段策略,FITing-Tree 可以限制最壞情況下的查找性能.在對數(shù)據(jù)分段時,FITing-Tree提出了使用類似FSW(feasible space window)方法[19,20]的貪心算法,具有O(n)的時間復(fù)雜度和O(1)的空間代價.此外,該索引使用異地插入(out-of-place insertion)策略,在每個段內(nèi)部預(yù)留一個固定大小的緩沖區(qū),在緩沖區(qū)滿之后將緩沖區(qū)數(shù)據(jù)與段數(shù)據(jù)合并,重新執(zhí)行分段算法.實驗結(jié)果表明,FITing-Tree 只需要比B+樹低4 個數(shù)量級的空間代價就能夠達到與B+樹相近的查找性能.此外,FITing-Tree 具有優(yōu)于B+樹的構(gòu)造速度和略差于B+樹的插入性能(假定B+樹同樣使用基于緩沖區(qū)的插入策略).

Fig.2 Index structure of FITing-Tree圖2 FITing-Tree 索引結(jié)構(gòu)

(2) 就地插入(in-place insertion)策略.ALEX[21]提出了另一種支持插入的方案,即在葉節(jié)點的排序數(shù)組中預(yù)留一定的空隙.如圖3 所示,當需要插入一個新的鍵時,首先通過模型來預(yù)測插入的位置.如果這是正確的位置,即新插入的鍵在這個位置保持數(shù)組有序,并且這個位置是一個空隙,則直接將鍵插入到空隙中即可.這是插入的最佳情況,由于鍵被精確地放置在模型預(yù)測的位置,因此之后的基于模型的查找將直接命中.如果模型預(yù)測的位置不正確,ALEX 使用指數(shù)搜索來找到準確的插入位置.同樣,如果插入位置是空隙,那么我們直接在那里插入鍵;如果插入位置不是空隙,則通過將鍵沿最接近空隙的方向移動一個位置,在插入位置形成空隙.這種插入策略不僅具有優(yōu)秀的寫入性能,還提升了基于模型的查找性能.與初版學(xué)習(xí)索引的另一個區(qū)別是,ALEX 使用指數(shù)搜索(exponential search)替代二分搜索,這是由于,在ALEX 中的基于模型的查找更容易落在正確位置附近,所以指數(shù)搜索的性能更加優(yōu)秀.此外,ALEX 還提出使用PMA(packed memory array)[22]作為空隙數(shù)組的備選方案,PMA 能夠提供比空隙數(shù)組更優(yōu)秀的最差插入性能.

ALEX 提出使用動態(tài)RMI 模型,如圖3 所示.ALEX 被構(gòu)建之初包含一個雙層RMI 模型作為根模型,以及與葉節(jié)點一一對應(yīng)的葉子模型,所有模型都是線性回歸模型.在ALEX 中,隨著空隙數(shù)組中被插入更多的元素,數(shù)組中的空隙數(shù)量會減少,插入性能隨之下降.當空隙數(shù)組的密度達到閾值時,空隙數(shù)組會進行分裂.同時,原先對應(yīng)該葉節(jié)點的模型變?yōu)閮?nèi)部模型,并在分裂之后的數(shù)組上重新訓(xùn)練模型作為新的葉子模型.與初版學(xué)習(xí)索引相比,ALEX 將空間代價降低了3 000 倍,將查找性能提高了2.7 倍,同時提供了插入能力.與B+樹相比,ALEX 將空間代價降低了5 個數(shù)量級,將查找性能提高了3.5 倍,而且插入性能略微優(yōu)于B+樹.

Fig.3 Index structure of ALEX圖3 ALEX 索引結(jié)構(gòu)

AIDEL[23]采用與FITing-Tree[18]類似的索引結(jié)構(gòu)、給定的模型誤差和基于模型誤差的分段算法,它們唯一的區(qū)別是插入策略.AIDEL 通過與記錄綁定的排序列表(可視為溢出塊)來支持插入.當插入新數(shù)據(jù)時,AIDEL 首先基于模型找到目標位置,然后將數(shù)據(jù)插入到目標位置指向的排序列表中.由于排序數(shù)組中的數(shù)據(jù)沒有改變,所以插入不會影響模型的誤差.采用類似FITing-Tree 結(jié)構(gòu)的工作還有ASLM[24]和PGM-index[25],其中,ASLM 使用了不同的貪心分段算法,并且允許自適應(yīng)地選擇插入策略和更復(fù)雜的模型.

(3) 基于LSM 的插入策略與模型壓縮.PGM-index[25]從多個方面優(yōu)化了FITing-Tree[18].首先,對于數(shù)據(jù)分段,它提出使用在時間序列有損壓縮和相似度搜索中已被廣泛研究的流式算法[26-30]來替代FITing-Tree 中的貪心算法,這種算法已被證明能夠獲得最優(yōu)的分段線性模型,同時具有O(n)的最優(yōu)時間復(fù)雜度.其次,對于插入和刪除,PGM-index 提出像LSM 樹[12,31]那樣維護數(shù)據(jù),并在每一層都維護一個學(xué)習(xí)索引,只在觸發(fā)合并時更新對應(yīng)的模型.此外,PGM-index 還提出了壓縮的模型,分別為起始鍵和斜率提供無損壓縮.其中,由于初始鍵是排序數(shù)據(jù)集的子集,可使用已被廣泛研究的壓縮方法[32-34];對于斜率,PGM-index 專門設(shè)計了壓縮算法.PGM-index 還提出分布感知的學(xué)習(xí)索引,不僅學(xué)習(xí)數(shù)據(jù)分布,同時學(xué)習(xí)查詢負載分布[35],獲得了更優(yōu)的平均查詢性能.最后,PGMindex 與FITing-Tree 的一個共同優(yōu)點是,通過建立代價模型,它們可以幫助用戶確定每個分段的最大誤差閾值——該閾值滿足給定最大空間代價并達到最優(yōu)查詢性能或者滿足給定最差查詢性能并達到最小空間代價.實驗結(jié)果表明,與FITing-Tree 相比,PGM-index 將空間代價降低了75%;與B+樹相比,PGM-index 將查詢和更新性能提升了71%.

(4) 插值法(interpolation).與基于RMI 模型結(jié)構(gòu)的學(xué)習(xí)索引相比,使用分段線性函數(shù)擬合數(shù)據(jù)只需對數(shù)據(jù)進行一趟掃描即可完成索引構(gòu)建,并且允許自下而上構(gòu)建索引.插值法同樣具有這個優(yōu)點.事實上,樣條插值法(spline interpolation)[36]等同于分段線性函數(shù).RadixSpline[37]使用樣條插值法擬合數(shù)據(jù),并使用基數(shù)樹(radix tree)來索引樣條.Setiawan 等人進一步研究了切比雪夫插值法(Chebyshev interpolation)[38]和伯恩斯坦插值法(Bernstein interpolation)[39]在學(xué)習(xí)索引中的應(yīng)用[40].

(5) 并發(fā)數(shù)據(jù)結(jié)構(gòu).XIndex 索引[41](如圖4 所示)在解決前兩個缺陷的同時,還考慮了索引結(jié)構(gòu)的并發(fā)性.與之前的工作有所不同,它將最底層的模型與對應(yīng)的數(shù)據(jù)存儲在同一個數(shù)據(jù)結(jié)構(gòu)中,稱為組節(jié)點(group node).與FITing-Tree、ALEX 和PGM-index 相同,XIndex 的所有模型都使用線性回歸模型.此外,XIndex 也使用了與FITing-Tree 相同的異地插入策略,并將插入的數(shù)據(jù)存儲在緩沖區(qū)中.XIndex 的一個組節(jié)點中可以包含多個線性回歸模型,并使用一個預(yù)先設(shè)置的誤差閾值.隨著緩沖區(qū)中的數(shù)據(jù)合并到排序數(shù)據(jù)中,若模型的最大誤差超過誤差閾值,則在組節(jié)點中進行模型分裂;若模型數(shù)量達到組節(jié)點的模型數(shù)量上界,則觸發(fā)組節(jié)點分裂.

Fig.4 Index structure of XIndex圖4 XIndex 索引結(jié)構(gòu)

XIndex 的數(shù)據(jù)結(jié)構(gòu)支持高并發(fā).它采用已有的樂觀并發(fā)控制[42-44]、細粒度鎖[44-46]和RCU(read-copy-update)[47]技術(shù),并精心設(shè)計了一種兩階段合并(two-phase compaction)算法來支持并發(fā)操作.如圖5 所示,如果緩沖區(qū)需要合并到排序數(shù)組中,則執(zhí)行過程分可為合并階段和復(fù)制階段.在合并階段,首先建立一個新組,并將舊緩沖區(qū)凍結(jié),此后的數(shù)據(jù)將被插入到臨時緩沖區(qū)中,例如圖5 所示的K6.然后,舊排序數(shù)組和緩沖區(qū)中的數(shù)據(jù)被合并到新排序數(shù)組中,注意,此時,新排序數(shù)組中存儲的是指向舊數(shù)組中記錄的指針,而非真正的記錄.在合并階段,更新操作將在舊排序數(shù)組和緩沖區(qū)中執(zhí)行,例如圖5 所示的K2.然后,XIndex 在新組中訓(xùn)練模型.在完成訓(xùn)練后,XIndex使用RCU 屏障(RCU barrier)保證舊排序數(shù)組和緩沖區(qū)不再被訪問,并進入復(fù)制階段.在復(fù)制階段,XIndex 將新排序數(shù)組中的每個指針原子替換為最新的記錄值.最后,XIndex 回收舊組的內(nèi)存資源.組分割的過程與其類似,同樣分為兩個階段.實驗結(jié)果表明,與并發(fā)索引結(jié)構(gòu)Masstree[44]和Wormhole[43]相比,XIndex 的性能分別提升了3.2 倍和4.4 倍.

Fig.5 Two phases compaction in XIndex圖5 XIndex 中的兩階段合并

(6) 學(xué)習(xí)式數(shù)據(jù)劃分策略.上述優(yōu)化方法傾向于使用更簡單的模型,與它們的優(yōu)化方向相反,Dabble[48]使用多個神經(jīng)網(wǎng)絡(luò)模型.在數(shù)據(jù)空間劃分階段,Dabble 提出使用K-Means 算法將數(shù)據(jù)劃分為互不相交的K個區(qū)域.然后,對于每個區(qū)域,Dabble 使用一個兩層神經(jīng)網(wǎng)絡(luò)模型擬合數(shù)據(jù).最后,與PGM-index[25]相似,Dabble 使用LSM樹的延遲更新策略處理數(shù)據(jù)插入.

(7) 機器學(xué)習(xí)輔助的傳統(tǒng)索引結(jié)構(gòu).Llaveshi 等人提出保持B+樹索引結(jié)構(gòu)不變,并使用線性回歸模型在節(jié)點內(nèi)部加速搜索[49].這種索引結(jié)構(gòu)不是嚴格的學(xué)習(xí)索引結(jié)構(gòu),而是一種機器學(xué)習(xí)輔助的傳統(tǒng)索引結(jié)構(gòu).該方法提出了一種新的插入策略.由于模型只是節(jié)點的輔助組件,所以它延續(xù)了傳統(tǒng)B+樹節(jié)點的就地插入策略.由于插入數(shù)據(jù)可能會降低模型的精度,所以每個模型都會統(tǒng)計每次預(yù)測的誤差,當平均誤差超過一定閾值時,重新訓(xùn)練模型.這種策略的弊端是不能使用基于誤差范圍的二分搜索.IFB-Tree[50]同樣使用了學(xué)習(xí)索引的思想提升傳統(tǒng)B+樹的性能.它在建立索引時判斷每個節(jié)點是否是插值友好的,即節(jié)點中的所有數(shù)據(jù)使用插值搜索(interpolation search)的誤差都低于給定的閾值.如果節(jié)點被標記為插值友好,則在節(jié)點中使用插值搜索.與B+樹相比,IFB-Tree 提升了50%的查找性能.Qu 等人提出了一種B+樹與線性回歸模型混合的索引[51],該索引從數(shù)據(jù)集中剔除離群值(outlier)以提升線性回歸模型的預(yù)測精度,并使用B+樹索引離群值.

1.2 面向二級索引的學(xué)習(xí)索引

第1.1 節(jié)中介紹的學(xué)習(xí)索引要求底層數(shù)據(jù)按查找鍵有序存儲.如果將學(xué)習(xí)索引直接用作無序數(shù)據(jù)上的二級索引(secondary index),則需要將數(shù)據(jù)按查找鍵重新排序,并為每條記錄附加一個指針.在大規(guī)模數(shù)據(jù)集上,高昂的排序代價以及額外的指針存儲空間代價將大大降低學(xué)習(xí)索引在二級索引上的優(yōu)勢.

Wu 等人提出了一種關(guān)系型數(shù)據(jù)庫上的簡潔二級索引機制Hermit[52].該索引采用機器學(xué)習(xí)技術(shù)學(xué)習(xí)列之間隱藏的軟函數(shù)依賴(soft functional dependency)關(guān)系[53,54].如圖6 左所示,屬性1 是數(shù)據(jù)表的主碼,即記錄按照屬性1 的順序存儲.若已存在屬性2 的二級索引,且屬性3 與屬性2 存在相關(guān)性,那么對于屬性3 的二級索引,可用TRSTree 替代傳統(tǒng)的索引結(jié)構(gòu).TRS-Tree 使用分層回歸方法擬合屬性3 與屬性2 的關(guān)系,并使用樹結(jié)構(gòu)來索引一組回歸函數(shù),其結(jié)構(gòu)如圖6 右所示.TRS-Tree 是一個k叉樹結(jié)構(gòu),構(gòu)造算法均勻地將屬性3 的取值范圍劃分為k個均勻的子范圍,直到回歸模型能夠很好地估計子范圍覆蓋的條目對.它的葉節(jié)點與一個子范圍對應(yīng),并使用回歸模型將屬性3 的子范圍映射到屬性2 中的一組記錄.圖6 右的上半部分是一棵TRS-Tree,下半部分表示屬性3的取值范圍,字母A～F表示TRS-Tree 中模型對應(yīng)的取值范圍.TRS-Tree 使用用戶設(shè)置的誤差閾值,但是允許離群值的存在.每個葉節(jié)點使用一個離群值緩沖區(qū)保存這些離群值.當一個葉節(jié)點的離群值與范圍內(nèi)記錄總數(shù)的比例達到閾值時,就觸發(fā)節(jié)點分裂.

Fig.6 Hermit (left) and TRS-Tree (right,character A～F represents the key range corresponding to the model)圖6 Hermit(左)與TRS-Tree(右,字母A～F 表示模型對應(yīng)的屬性取值范圍)

Hermit 支持范圍查詢,查找過程分為3 步.首先,在TRS-Tree 中查找,返回一組屬性2 上的范圍(非離群值)和一組記錄標識符(離群值);然后,使用屬性2 的范圍作為輸入,在傳統(tǒng)索引上執(zhí)行查找,返回一組記錄標識符;最后,使用前兩步得到的記錄標識符獲取實際的記錄,并驗證記錄是否滿足查詢謂詞(query predicate),將滿足查詢謂詞的結(jié)果返回.實驗結(jié)果表明,Hermit 的查找性能略差于傳統(tǒng)二級索引,但是空間代價遠遠低于傳統(tǒng)二級索引,并且插入性能是B+樹的2 倍以上.Wu 等人測試了兩種擬合函數(shù),其中線性函數(shù)能夠獲得極低的空間代價,而Sigmoid 函數(shù)能夠擬合比較復(fù)雜的關(guān)系.注意,與面向主索引的學(xué)習(xí)索引有所不同,Hermit 中的模型學(xué)習(xí)的是兩個列之間的關(guān)系,而不是鍵的分布.使用Hermit 有兩個前提條件:兩個列之間存在某種聯(lián)系,并且其中一列已經(jīng)建立了索引.

1.3 現(xiàn)有學(xué)習(xí)索引技術(shù)的對比

表1 給出了目前具有代表性的學(xué)習(xí)索引,并總結(jié)了不同索引之間的技術(shù)差異.

Table 1 Technology comparison of learned indexes表1 學(xué)習(xí)索引技術(shù)對比

內(nèi)部節(jié)點的功能是索引葉節(jié)點,它需要能夠擬合CDF 的大體形狀.初始版本使用神經(jīng)網(wǎng)絡(luò)模型,能夠較好地擬合數(shù)據(jù)分布.但是,神經(jīng)網(wǎng)絡(luò)模型的執(zhí)行具有較高的乘法代價,而且訓(xùn)練速度較慢,所以初始版本的學(xué)習(xí)索引不支持插入操作.在后續(xù)的研究中,由線性回歸模型構(gòu)成的雙層RMI 模型被認為是較好的選擇.

葉節(jié)點的功能是擬合某一小段數(shù)據(jù),出于執(zhí)行代價、易于更新和空間代價的綜合考慮,線性回歸模型在當前是最優(yōu)選擇.

數(shù)據(jù)劃分是指底層數(shù)據(jù)的劃分策略.為支持插入操作,數(shù)據(jù)被分段存儲,每一段數(shù)據(jù)與一個葉節(jié)點的模型對應(yīng).為了使每一段數(shù)據(jù)都滿足用戶給定的誤差閾值,FITing-Tree[18]和PGM-index[25]使用串行的貪心算法執(zhí)行分段并訓(xùn)練模型,具有O(n)的時間復(fù)雜度.其他版本的學(xué)習(xí)索引使用等分策略,可以并行地在每個段中訓(xùn)練模型.

模型誤差是指葉節(jié)點的模型誤差,誤差的大小會影響后續(xù)的二分搜索性能.初始版本的學(xué)習(xí)索引沒有預(yù)先給定模型誤差,所以它的最差查找性能是不確定的.為了解決這一問題,FITing-Tree[18]和PGM-index[25]使用預(yù)先設(shè)置的誤差閾值串行執(zhí)行數(shù)據(jù)劃分.而XIndex[41]和Hermit[52]采用遞歸等分數(shù)據(jù)的策略,如果數(shù)據(jù)段中的模型誤差超過給定閾值,則等分數(shù)據(jù)并重新訓(xùn)練模型.這種方式雖然可以并行執(zhí)行,但是可能需要多次訓(xùn)練模型,性能優(yōu)劣取決于初次數(shù)據(jù)劃分.

在插入策略上,異地插入策略被廣泛采納,理由是異地插入不僅能夠分攤數(shù)據(jù)移位代價,還能夠分攤模型重訓(xùn)練代價,因為數(shù)據(jù)插入會改變模型的誤差.然而,異地插入不可避免地降低了查詢性能.AIDEL[23]使用與記錄綁定的溢出塊存儲新插入的數(shù)據(jù).理論上,與異地插入策略相比,溢出塊策略的插入性能略差,查找性能更好,但是溢出塊的管理比緩沖區(qū)更復(fù)雜.ALEX[21]使用空隙數(shù)組結(jié)構(gòu),配合使用就地插入策略和指數(shù)搜索策略,獲得了較優(yōu)的查找和插入性能.與表1 中涉及的方法不同,Hadian 等人提出使用就地插入策略,但是每次插入后不立即重新訓(xùn)練模型,而是在每個段中統(tǒng)計插入數(shù)量,并在查找時使用模型誤差加上插入數(shù)量作為二分搜索的界限[55].當某個段中的插入數(shù)量足夠多時,重新訓(xùn)練模型.Bilgram 等人為學(xué)習(xí)索引建立了代價模型,用于判斷何時進行重訓(xùn)練[56].

在節(jié)點分裂上,與傳統(tǒng)的B+樹不同,所有學(xué)習(xí)索引的分裂都是由模型觸發(fā)的.當一段數(shù)據(jù)對應(yīng)的模型不能滿足給定的誤差閾值時,觸發(fā)模型分裂.其中,XIndex[41]的一個組節(jié)點中可以包含多個模型,而在其他學(xué)習(xí)索引中一個數(shù)據(jù)段只對應(yīng)一個模型,在模型分裂的同時數(shù)據(jù)段也需要分裂.

1.4 與傳統(tǒng)B+樹索引的對比

與B+樹相比,學(xué)習(xí)索引額外引入了機器學(xué)習(xí)模型以提升索引性能.學(xué)習(xí)索引之所以能夠提升性能,其關(guān)鍵之處在于:

(1) 一個機器學(xué)習(xí)模型能夠覆蓋幾萬個鍵,這使得學(xué)習(xí)索引的葉節(jié)點數(shù)量遠遠小于B+樹.這有助于降低索引的空間代價.

(2) 機器學(xué)習(xí)模型能夠在幾萬個鍵中快速地將搜索范圍縮小到幾十個鍵.這是通過模型計算實現(xiàn)的,而不是通過傳統(tǒng)B+樹上的逐層鍵值比較和指針訪問操作來實現(xiàn),因此可以降低索引查找代價.

我們測試了在學(xué)習(xí)索引中最常用的模型——線性模型的擬合能力,測試時使用OptimalPLR 算法[25,30],這是一種O(n)時間復(fù)雜度的分段線性擬合算法,能夠獲得給定誤差邊界的最小分段數(shù)量,測試數(shù)據(jù)集為1 億個正態(tài)分布的浮點型隨機數(shù).測試結(jié)果見表2,在給定的誤差邊界下,一個線性模型所覆蓋的鍵數(shù)量遠高于B+樹節(jié)點,這意味著學(xué)習(xí)索引的葉節(jié)點數(shù)量遠少于B+樹索引,從而可以降低空間代價.同時,更少的葉節(jié)點意味著學(xué)習(xí)索引的樹高要低于B+樹索引,降低了學(xué)習(xí)索引的查找時間.

Table 2 The fitting power of the linear models表2 線性模型擬合能力

同時,與B+樹相比,學(xué)習(xí)索引也存在一些額外代價,總結(jié)如下.

(1) 模型計算代價.學(xué)習(xí)索引在查找過程中使用模型計算代替了傳統(tǒng)B+樹的鍵值比較和指針操作.當使用比較簡單的線性模型時,模型計算代價較小.但是,如果數(shù)據(jù)分布難以用線性模型進行擬合,必須使用復(fù)雜模型時,則會引入較大的計算代價.

(2) 模型擬合代價.學(xué)習(xí)索引借鑒機器學(xué)習(xí)的訓(xùn)練過程,通過學(xué)習(xí)數(shù)據(jù)的分布來構(gòu)建計算模型.為了保證模型的準確性,一般要求訓(xùn)練的數(shù)據(jù)要足夠大.這將導(dǎo)致較高的模型擬合代價,使得學(xué)習(xí)索引的構(gòu)建速度遠遠慢于B+樹索引.實驗結(jié)果表明,使用OptimalPLR 算法構(gòu)建學(xué)習(xí)索引的速度只相當于B+樹構(gòu)建速度的十分之一.而且,當索引的數(shù)據(jù)發(fā)生較大變化時,例如插入或刪除了大量鍵值,就需要對模型進行更新或者重建,這同樣會影響學(xué)習(xí)索引的性能.

(3) 數(shù)據(jù)移位代價.由于學(xué)習(xí)索引的葉節(jié)點遠遠大于B+樹節(jié)點,所以它在執(zhí)行插入時存在較大的數(shù)據(jù)移位代價.尤其是當模型預(yù)測的準確率較低時,數(shù)據(jù)移位的代價會更高.而如果重新構(gòu)建計算模型又會帶來較大的延遲.

2 面向多維范圍查詢的學(xué)習(xí)索引

多維查詢是指一次查詢涉及多個屬性維度.最經(jīng)典的多維查詢應(yīng)用是空間查詢.這類查詢返回二維平面空間中的一個矩形范圍.傳統(tǒng)的一維索引對于多維查詢不再有效,需要設(shè)計專門的索引結(jié)構(gòu),即多維索引或空間索引.目前關(guān)于空間索引已有大量研究成果,主要可分為以下3 類(詳細的多維索引研究報告可參考綜述文獻[57,58]).

第1 類索引將空間劃分為區(qū)域,并對這些區(qū)域建立索引,典型的索引結(jié)構(gòu)有KD 樹[59](面向k維空間)、四叉樹(quadtree)[60](面向二維空間)和八叉樹(octree)[61](面向三維空間).第2 類索引將數(shù)據(jù)集劃分為不同的子集,然后對這些子集進行索引,經(jīng)典的索引結(jié)構(gòu)有R 樹[62]及其變體[63-65].第3 類索引將多維空間轉(zhuǎn)換為一維空間,然后在一維空間上建立索引,典型的轉(zhuǎn)換方法有希爾伯特空間填充曲線(Hilbert space filling curve)[66]和Z順序曲線(Z-order curve)[66,67].這些結(jié)構(gòu)有的是專為二維或三維空間而設(shè)計,有的結(jié)構(gòu)可以適用于更高維空間,或者易于擴展到高維場景.

將學(xué)習(xí)索引的思想應(yīng)用到多維索引中并不容易,因為學(xué)習(xí)索引要求數(shù)據(jù)有序,而多維數(shù)據(jù)并不是天然有序的.一種直觀的解決方式是使用第3 類索引,即將多維空間上的數(shù)據(jù)投影到一維空間上,并在一維空間上建立學(xué)習(xí)索引.這種方法的難點在于投影策略的設(shè)計.如果使用簡單的多維CDF 作為映射函數(shù),那么具有相同映射值的兩個點可能在多維空間中相距很遠.所以,設(shè)計優(yōu)秀的映射函數(shù),或者說設(shè)計優(yōu)秀的數(shù)據(jù)布局(data layout)策略,是設(shè)計學(xué)習(xí)多維索引的關(guān)鍵.SageDB[68]提出將空間劃分為多維網(wǎng)格,數(shù)據(jù)按照網(wǎng)格進行排序,但SageDB 并沒有給出實現(xiàn)細節(jié).Wang 等人使用Z順序曲線進行投影,提出了學(xué)習(xí)ZM 索引[69],并在一維空間上建立RMI 模型.學(xué)習(xí)ZM 索引的查詢性能優(yōu)于R 樹,并且空間代價遠遠小于R 樹.

在空間查詢應(yīng)用中,除了查詢確定的空間范圍外,另一種常見的查詢方式是k-最近鄰(k-nearest neighbors,簡稱KNN)查詢.KNN 查詢返回距離某一點最近的k個目標.目前已有大量基于R 樹的KNN 查詢研究.然而,SageDB[68]和學(xué)習(xí)ZM 索引[69]都沒有關(guān)注KNN 查詢.ML-index[70]是一種支持KNN 查詢的多維學(xué)習(xí)索引,它使用的投影策略是一種基于iDistance 方法[71]的改進策略.ML-index 首先在多維空間中選擇一定數(shù)量的參考點進行分區(qū),每個參考點代表分區(qū)的中心.在iDistance 方法中,多維空間中的點被映射為該點到分區(qū)中心的距離加上分區(qū)編號與一個常數(shù)的乘積.然而,由于每個分區(qū)的大小不同,很難為這個常數(shù)找到合適的值.ML-index 使用偏移量替代這個乘積,解決了分區(qū)重疊問題.在得到的一維投影上,ML-index 構(gòu)建了一個由簡單回歸模型組成的RMI.ML-index 使用基于iDistance 的方法執(zhí)行KNN 查詢,并使用基于數(shù)據(jù)的范圍近似方法[72]執(zhí)行范圍查詢.ML-index 的空間代價遠小于傳統(tǒng)的多維索引,KNN 的查詢速度優(yōu)于iDistance 方法;與學(xué)習(xí)ZM 索引[69]相比,ML-index 在二維空間的性能略差,但在更高維的空間中性能更優(yōu).

LISA[73]結(jié)合了SageDB 和ML-index 的思想.它首先使用網(wǎng)格劃分數(shù)據(jù),然后借助一個映射函數(shù)將數(shù)據(jù)映射到一維空間.映射函數(shù)需要保證處于小編號網(wǎng)格單元中的點的映射值一定比處于大編號網(wǎng)格單元中的點的映射值小,LISA采取了與ML-index類似的基于勒貝格測度(Lebesgue measure)[74]的方法.在一維空間上,LISA將數(shù)據(jù)等分到一定數(shù)量的分片中,并訓(xùn)練一個分段線性回歸模型來預(yù)測分片.對于每個分片,LISA 還建立了一個局部模型來預(yù)測分頁.對于范圍查詢,LISA 首先得到與查詢矩形相交的單元格,并依照單元格將查詢矩形分成多個小矩形.對于每個小矩形,LISA 使用映射函數(shù)、分段線性回歸模型和局部模型獲取相關(guān)的頁面.對于KNN 查詢,LISA 使用格子回歸(lattice regression)模型[75]結(jié)合范圍查詢進行搜索.此外,LISA 還支持插入操作,它采取異地插入的方式將數(shù)據(jù)插入到模型預(yù)測的頁面中.實驗結(jié)果表明,與KD 樹和學(xué)習(xí)ZM 索引相比,LISA 具有略差的空間代價,但卻大幅度降低了查詢的I/O 代價;與R 樹相比,LISA 具有略優(yōu)的查詢I/O 代價和空間代價.

Flood[76]擴展了SageDB 中關(guān)于多維索引的優(yōu)化思想,它是網(wǎng)格索引(grid index)[76]的變體.與前面介紹的工作不同,它使用機器學(xué)習(xí)方法來調(diào)優(yōu)數(shù)據(jù)布局.對于d維空間中的數(shù)據(jù),Flood 首先對d個維度進行排序,并使用排序中的前d-1 維在數(shù)據(jù)上覆蓋一個d-1 維網(wǎng)格,使用第d維作為排序維給每個網(wǎng)格單元中的數(shù)據(jù)排序.給定一個查詢范圍,Flood 首先找到與查詢范圍的超矩形相交的網(wǎng)格單元,然后在每個網(wǎng)格單元中使用排序維確定需要掃描的范圍,最后掃描數(shù)據(jù)并過濾出與查詢相匹配的記錄.Flood 的網(wǎng)格布局有幾個需要調(diào)優(yōu)的參數(shù),分別是每個維度被劃分的列數(shù)以及選擇哪個維度作為排序維.這些參數(shù)很難調(diào)優(yōu),因為它們?nèi)Q于許多相互影響的因素,包裹查詢過濾器在維度上的頻率、每個維度上選擇系數(shù)的平均值和方差、維度之間的相關(guān)性、維度在查詢負載中的相關(guān)性等.Flood 首先隨機生成一些數(shù)據(jù)布局,并使用合成的數(shù)據(jù)集和查詢負載生成許多訓(xùn)練實例,使用得到的特征訓(xùn)練一個隨機森林回歸模型[77],最終生成一個成本模型.然后,Flood 迭代選擇排序維,并使用梯度下降搜索尋找每個維度的最優(yōu)列數(shù),得到d個布局,并使用成本模型在d個布局中選擇目標函數(shù)成本最低的布局.在每個網(wǎng)格單元內(nèi)部,Flood 使用分段線性回歸模型擬合依照排序維進行排序的數(shù)據(jù).實驗結(jié)果表明,Flood 比多種著名的空間索引[59,63,67,78,79]快40～250 倍,并節(jié)省了50 倍以上的空間.目前還有一些基于機器學(xué)習(xí)的數(shù)據(jù)布局調(diào)優(yōu)工作[80,81],但它們不屬于學(xué)習(xí)索引的范疇,因此本文不展開討論.

表3 給出了面向多維空間的學(xué)習(xí)索引對比情況.其中,SageDB 和學(xué)習(xí)ZM 索引使用了已有方法,ML-index和LISA 使用了改進的映射函數(shù),而Flood 則使用機器學(xué)習(xí)方法優(yōu)化數(shù)據(jù)布局.在將數(shù)據(jù)映射到一維空間后,這些索引普遍采用了前面討論過的RMI 和分段線性回歸模型.更進一步地,ML-index 和LISA 討論了如何支持KNN查詢,LISA 還探索了如何支持數(shù)據(jù)插入.

Table 3 Comparison of learned multi-dimensional indexes表3 學(xué)習(xí)多維索引對比

3 面向點查詢的學(xué)習(xí)索引

現(xiàn)實世界中存在著某些特定的應(yīng)用,它們不支持或不需要范圍查詢.針對這些應(yīng)用需求,人們設(shè)計了面向點查詢的索引結(jié)構(gòu).例如,哈希索引具有O(1)的查詢時間復(fù)雜度和空間復(fù)雜度,優(yōu)于B+樹索引結(jié)構(gòu);Trie 樹是一種面向字符串查詢的索引結(jié)構(gòu),被廣泛用于文本詞頻統(tǒng)計;倒排索引被廣泛應(yīng)用于搜索引擎中,使用文本反向檢索文檔.目前,學(xué)習(xí)索引在哈希索引和倒排索引中都已有一些研究,本節(jié)將介紹這些技術(shù).

3.1 傳統(tǒng)哈希索引

由于哈希索引本身就是一組函數(shù)模型且具有O(1)的查找性能,所以不能再使用之前的優(yōu)化思路,即使用模型代替索引以減少空間代價并提升預(yù)測精度.然而,哈希索引存在哈希沖突問題,這會導(dǎo)致索引性能的下降.完美哈希(perfect hashing)[82]和布谷鳥哈希(cuckoo hashing)[83]分別致力于在靜態(tài)數(shù)據(jù)集和動態(tài)數(shù)據(jù)集上減少哈希沖突.Kraska 等人提出,通過學(xué)習(xí)鍵的分布可以得到更好的哈希函數(shù),即能夠減少哈希沖突[7].與第1 節(jié)中面向一維范圍查詢的學(xué)習(xí)索引不同,學(xué)習(xí)哈希索引的目標是將學(xué)到的數(shù)據(jù)分布均勻地映射到給定數(shù)量的哈希桶中,這只需要將鍵的CDF 按照給定的哈希桶數(shù)量縮放即可.與面向范圍查詢的學(xué)習(xí)索引相同,學(xué)習(xí)哈希索引繼續(xù)使用RMI 模型學(xué)習(xí)鍵的分布.與簡單的哈希函數(shù)相比,學(xué)習(xí)哈希索引顯著降低了哈希沖突的概率.同時,與完美哈希的大小會隨著數(shù)據(jù)集大小的增長而有所不同相比,學(xué)習(xí)哈希索引的大小不會受到數(shù)據(jù)集大小的影響.然而,在較小的數(shù)據(jù)集上,學(xué)習(xí)哈希索引顯然在空間效率上不具備優(yōu)勢.

3.2 局部敏感哈希

局部敏感哈希(locality sensitive hashing,簡稱LSH)[84]與傳統(tǒng)的哈希索引不同,它利用哈希沖突加速近似最近鄰(approximate nearest neighbor,簡稱ANN)搜索.目前,LSH 在圖像檢索等高維數(shù)據(jù)檢索中得到了廣泛應(yīng)用.LSH 的主要思想是通過設(shè)計一個哈希函數(shù)使得高維空間中距離相近的兩點很大概率上具有一樣的哈希值.LSH 利用隨機投影或排列來生成與數(shù)據(jù)無關(guān)的哈希函數(shù),但這種方法容易遇到性能瓶頸和語義鴻溝(semantic gap)[85]問題.為了解決性能問題,人們提出了使用機器學(xué)習(xí)方法學(xué)習(xí)數(shù)據(jù)依賴,進而得到面向應(yīng)用的哈希函數(shù),從而生成更有效且緊湊的哈希碼[86,87],并保證語義一致性[88-91].為了實現(xiàn)這一目標,人們對機器學(xué)習(xí)模型進行了大量探索[92],包括使用卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network,簡稱CNN)作為哈希函數(shù)[93]等.與第3.1 節(jié)中的學(xué)習(xí)哈希索引不同,LSH 相關(guān)的工作通過學(xué)習(xí)數(shù)據(jù)分布來指導(dǎo)哈希函數(shù)的設(shè)計,并沒有改變基本的數(shù)據(jù)結(jié)構(gòu).本文主要關(guān)注使用機器學(xué)習(xí)模型替代索引結(jié)構(gòu)這一創(chuàng)新觀點,故不展開討論這部分內(nèi)容.而且,利用機器學(xué)習(xí)技術(shù)優(yōu)化LSH 已經(jīng)歷長久的研究,詳細內(nèi)容可參看綜述文獻[92].

3.3 倒排索引

倒排索引是文檔檢索中最常用的數(shù)據(jù)結(jié)構(gòu)之一,它存儲單詞到文檔的映射,從而可以快速檢索包含某些單詞的文檔.倒排索引目前已被廣泛應(yīng)用于搜索引擎[94,95].隨著互聯(lián)網(wǎng)中數(shù)據(jù)量的急速增長,存儲完整的倒排表需要巨大的空間代價.受到學(xué)習(xí)索引的啟發(fā),Oosterhuis 等人使用深度神經(jīng)網(wǎng)絡(luò)(deep neural network,簡稱DNN)模型學(xué)習(xí)得到一個布爾函數(shù)[96],該函數(shù)接受一個單詞項和一個文檔作為輸入,并預(yù)測該單詞項是否存在于該文檔中.然而,他們并沒有介紹學(xué)習(xí)布爾模型的具體細節(jié),而只是研究了如何應(yīng)用該模型.Oosterhuis 等人結(jié)合已有的倒排索引查詢優(yōu)化方法[97,98],并展示了一個優(yōu)秀的學(xué)習(xí)布爾模型能夠帶來巨大的空間收益.

單詞詞典是倒排索引的重要組成部分,它記錄在文檔集合中出現(xiàn)的單詞以及該單詞對應(yīng)的倒排列表在倒排文件中的位置信息.對于一個規(guī)模很大的文檔集合,單詞詞典包含大量不同單詞.因此,需要高效的數(shù)據(jù)結(jié)構(gòu)來加速單詞詞典中的查找,常用的結(jié)構(gòu)包括哈希、B+樹和Trie 樹等.受到Kraska 等人提出的學(xué)習(xí)哈希索引的啟發(fā),Pavo[99]使用基于循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network,簡稱RNN)的分層模型替代倒排索引中的哈希函數(shù).如圖7 所示,Pavo 使用類似RMI 的層次模型結(jié)構(gòu),其內(nèi)部的所有模型都采用RNN 模型,每個RNN 模型由一個單層的長短期記憶(long short-term memory,簡稱LSTM)層和一到兩個全連接層組成.每一層中的不同模型負責(zé)互不相交的數(shù)據(jù)子集,并在不同層中遞歸地劃分數(shù)據(jù)集.實驗結(jié)果表明,與傳統(tǒng)哈希索引相比,Pavo 具有更低的哈希沖突概率和更高的空間利用率,但是查詢速度慢3～4 倍.此外,在相同的模型參數(shù)量下,無監(jiān)督學(xué)習(xí)對數(shù)據(jù)分布的擬合效果優(yōu)于有監(jiān)督學(xué)習(xí).

Fig.7 Index structure of Pavo圖7 Pavo 索引結(jié)構(gòu)

4 面向存在查詢的學(xué)習(xí)索引

存在查詢用于判斷某一元素是否存在于一個集合中.最經(jīng)典的支持存在查詢的數(shù)據(jù)結(jié)構(gòu)是布隆過濾器(Bloom filter)[100].在數(shù)據(jù)庫中,布隆過濾器通常作為索引的輔助組件出現(xiàn).例如,谷歌的Bigtable[101]使用它判斷鍵是否存在于SSTable 中,從而避免不必要的磁盤查找;BF-Tree[102]使用它替代B+樹的葉節(jié)點,減少索引的空間占用.此外,它還被用于網(wǎng)絡(luò)安全等領(lǐng)域[103].布隆過濾器由一個二進制位向量和一組哈希函數(shù)組成,具有高插入性能、高查找性能、低空間占用等優(yōu)點.當插入一個新的元素時,布隆過濾器使用哈希函數(shù)將鍵映射得到一組數(shù)字,并在二進制位向量中將這組數(shù)字對應(yīng)的位置設(shè)為1.當查找某個元素時,如果元素對應(yīng)的一組哈希值在二進制向量中都為1,則布隆過濾器判定該元素存在于集合中,否則判定不存在.注意,由于存在哈希沖突,所以布隆過濾器只能保證假陰性概率(false negative rate,簡稱FNR)為0,但是假陽性概率(false positive rate,簡稱FPR)大于0.布隆過濾器的FPR 與空間代價呈負相關(guān),在大數(shù)據(jù)集上,為了獲取一個較低的FPR,需要很高的空間代價,這限制了布隆過濾器的空間效率.

Kraska 等人提出了學(xué)習(xí)布隆過濾器[7],通過學(xué)習(xí)數(shù)據(jù)分布降低哈希沖突的概率.注意,與第3 節(jié)中的學(xué)習(xí)哈希索引不同,學(xué)習(xí)哈希索引的目標是降低存在的鍵之間的沖突概率,而學(xué)習(xí)布隆過濾器的目標是降低存在的鍵與不存在的鍵之間的沖突概率.Kraska 等人提出的學(xué)習(xí)布隆過濾器將存在索引視為一個二元概率分類任務(wù),并訓(xùn)練一個RNN 模型預(yù)測鍵存在的概率.學(xué)習(xí)布隆過濾器使用一個概率閾值,當存在概率大于這個閾值時,則判定該鍵存在,否則判定不存在.通過調(diào)節(jié)概率閾值的大小,能夠獲得需要的FPR 大小.然而,與傳統(tǒng)布隆過濾器不同,使用RNN 模型和概率閾值不能保證FNR 為0,而且FNR 的大小與FPR 的大小呈負相關(guān).所以,如圖8 左所示,對于RNN 模型判定不存在的鍵,需要再使用一個后置布隆過濾器,從而將FNR 降為0.實驗結(jié)果表明,與傳統(tǒng)布隆過濾器相比,學(xué)習(xí)布隆過濾的空間效率更高.

Fig.8 Original learned Bloom filter (left) and sandwiched learned Bloom filter (right)圖8 原始學(xué)習(xí)布隆過濾器(左)和三明治結(jié)構(gòu)學(xué)習(xí)布隆過濾器(右)

Mitzenmacher 改進了學(xué)習(xí)布隆過濾器,提出了三明治結(jié)構(gòu)的學(xué)習(xí)布隆過濾器[104].除了使用一個后置布隆過濾器外,三明治結(jié)構(gòu)還使用了一個前置布隆過濾器,如圖8 右所示.由于后置布隆過濾器的大小與通過RNN 模型的假陰性元素數(shù)量呈正相關(guān),所以通過使用前置布隆過濾器消除更多的假陰性,能夠降低后置布隆過濾器的空間代價.三明治結(jié)構(gòu)的另一個優(yōu)點是它與Kraska 等人提出的學(xué)習(xí)布隆過濾器結(jié)構(gòu)相比具有更強的魯棒性.如果用于學(xué)習(xí)布隆過濾器的訓(xùn)練集和測試集具有不同的數(shù)據(jù)分布,那么RNN 模型的FNR 可能遠遠大于預(yù)期.增加一個前置布隆過濾器能夠緩解這個問題,因為它預(yù)先過濾了一部分假陰性元素.Ada-BF[105]提出利用RNN 模型輸出的概率評分的分布,自適應(yīng)地調(diào)整不同區(qū)域的哈希函數(shù)數(shù)量,從而調(diào)節(jié)不同區(qū)域的FPR,以獲得更好的整體FPR.

上述學(xué)習(xí)布隆過濾器只能應(yīng)用在靜態(tài)數(shù)據(jù)集上,因為它們需要預(yù)先學(xué)習(xí)數(shù)據(jù)集的數(shù)據(jù)分布.然而,許多應(yīng)用場景都需要支持數(shù)據(jù)集的動態(tài)更新,這要求布隆過濾器能夠支持高效的數(shù)據(jù)插入.Rae 等人使用元學(xué)習(xí)(metalearning)和記憶增強神經(jīng)網(wǎng)絡(luò)(memory-augmented neural network)[106,107]來解決這一問題,提出了神經(jīng)布隆過濾器[108].神經(jīng)布隆過濾器不是從零開始學(xué)習(xí),而是從公共數(shù)據(jù)分布的采樣中學(xué)習(xí),這適用于在公共數(shù)據(jù)的不同子集上實例化多個布隆過濾器的應(yīng)用程序.例如,Bigtable 為每個SSTable 文件應(yīng)用一個布隆過濾器[101].在數(shù)據(jù)庫應(yīng)用中,與布隆過濾器和布谷鳥過濾器(cuckoo filter)[109]相比,神經(jīng)布隆過濾器將空間代價降低了 30 倍.Bhattacharya 等人提出兩種方案以處理學(xué)習(xí)布隆過濾器中的數(shù)據(jù)插入[110]問題,第1 種方案是通過重訓(xùn)練異地插入的數(shù)據(jù),從而更新分類器模型;第2 種方案是使用動態(tài)分區(qū)布隆過濾器[111]來替代傳統(tǒng)布隆過濾器,其空間代價會隨著數(shù)據(jù)的插入而有所增長.

5 面向?qū)W習(xí)索引的測試基準

測試基準是進行實驗驗證的重要組件,包括數(shù)據(jù)集、負載和對比方案.使用公開的測試基準能夠使研究的實驗結(jié)果更具說服力.由于學(xué)習(xí)索引是近年來才出現(xiàn)的研究方向,因此目前只有較少的工作研究了面向?qū)W習(xí)索引的測試基準.SOSD[112]是一個面向一維范圍查詢的學(xué)習(xí)索引測試基準,它提供了RMI 模型的開源實現(xiàn).此外,它還提供了多種可選方案作為對比,包括直接應(yīng)用在排序數(shù)組上的動態(tài)搜索算法以及會占用額外空間的索引方案.其中,動態(tài)搜索算法包括二分搜索、基數(shù)二分搜索、插值搜索和最近提出的三點差值搜索[113];索引方案包括多種經(jīng)典的數(shù)據(jù)庫索引:自適應(yīng)基數(shù)樹[114]、流行的B+樹實現(xiàn)[115]以及FAST[116].除了上述對比方案以外,ALEX[21]、PGM-index[25]和XIndex[41]也提供了開源實現(xiàn).SOSD 包含8 種不同的數(shù)據(jù)集:圖書銷售人氣數(shù)據(jù)[117],Facebook 用戶ID 數(shù)據(jù)集的上采樣版本[118],OpenStreetMap[119]位置數(shù)據(jù)的對數(shù)正態(tài)分布、正態(tài)分布和均勻采樣版本,密集整數(shù),均勻分布稀疏整數(shù)和維基百科文章編輯時間戳[120].此外,使用Web 日志數(shù)據(jù)集或物聯(lián)網(wǎng)數(shù)據(jù)集[121]也是一種可選方案.

SOSD 僅提供了單一的一維范圍查詢負載,更復(fù)雜的工作負載可以考慮數(shù)據(jù)庫領(lǐng)域的流行測試基準.在針對索引插入的研究中,需要使用讀寫混合負載,可以選擇TPC-C[122]和YCSB[123]作為測試基準.對于多維查詢,可以選用公開的地圖數(shù)據(jù)集[119]或圖像數(shù)據(jù)集[124]以及TPC-H[125]測試基準.然而,對于倒排索引和布隆過濾器的研究,目前還缺乏公開的測試基準.

6 研究展望

雖然目前已有許多工作對學(xué)習(xí)索引進行了探索,但是與已經(jīng)經(jīng)歷了數(shù)十年發(fā)展的傳統(tǒng)數(shù)據(jù)庫索引相比,學(xué)習(xí)索引尚處于萌芽階段,還需要更多的研究與探索.特別是,學(xué)習(xí)索引尚處于實驗室測試階段,目前還沒有在生產(chǎn)環(huán)境中集成學(xué)習(xí)索引的實例,這需要數(shù)據(jù)庫社區(qū)與企業(yè)的更多參與和努力.基于我們對目前學(xué)習(xí)索引研究現(xiàn)狀的調(diào)研以及數(shù)據(jù)庫、大數(shù)據(jù)等領(lǐng)域的發(fā)展趨勢,本文認為下面的一些問題是未來值得探索的研究方向.

適合學(xué)習(xí)索引的機器學(xué)習(xí)模型.雖然已有工作針對學(xué)習(xí)索引提出了許多模型,但是這些模型的結(jié)構(gòu)比較單一,大多是基于Kraska 等人提出的模型結(jié)構(gòu).對于面向一維范圍查詢的學(xué)習(xí)索引,已有工作都直接使用RMI 模型或設(shè)計類似于RMI 的層次結(jié)構(gòu),而沒有進一步探索其他模型結(jié)構(gòu)的可能;而且,這些工作僅采用簡單的神經(jīng)網(wǎng)絡(luò)和線性回歸模型.雖然線性回歸模型具有易于更新、存儲代價低、計算量低等優(yōu)點,但是它并不能模擬所有的數(shù)據(jù)分布.同樣,對于學(xué)習(xí)布隆過濾器,已有工作都僅是基于Kraska 等人提出的學(xué)習(xí)布隆過濾器結(jié)構(gòu)進行優(yōu)化,并使用RNN 模型學(xué)習(xí)鍵存在的概率,仍然沒有研究者來探索將存在索引替換為其他機器學(xué)習(xí)模型的可能性.此外,學(xué)習(xí)索引的研究僅限于本文提到的幾種索引類型,而實際上,仍有其他類型的索引值得研究.例如,目前還沒有學(xué)習(xí)式的Trie 樹和基數(shù)樹.在眾多的機器學(xué)習(xí)模型中,如何選擇適合學(xué)習(xí)索引的機器學(xué)習(xí)模型是未來值得進一步探索的一個研究方向.

學(xué)習(xí)索引的模型調(diào)優(yōu)方法.傳統(tǒng)的索引僅需要調(diào)節(jié)少量直觀的參數(shù),例如B+樹的節(jié)點大小和填充率.使用機器學(xué)習(xí)模型替代傳統(tǒng)索引,使索引調(diào)參變得復(fù)雜,如何減少學(xué)習(xí)索引與用戶的交互、降低學(xué)習(xí)索引的調(diào)參難度是一個值得研究的方向.這方面的研究成果目前僅有CDFShop[126],它展示了RMI 模型的調(diào)參過程,并探索了自動化調(diào)參的可能性.然而,其他學(xué)習(xí)索引的自動化調(diào)參目前還是空白,有待進一步探索.此外,大多數(shù)學(xué)習(xí)索引僅學(xué)習(xí)數(shù)據(jù)分布或僅學(xué)習(xí)查詢負載分布,如何在一個模型中同時學(xué)習(xí)數(shù)據(jù)分布和查詢負載分布,還需要進一步加以研究.

可動態(tài)更新的學(xué)習(xí)索引.傳統(tǒng)的OLTP(online transaction processing)應(yīng)用往往要求索引能夠支持動態(tài)的數(shù)據(jù)更新,例如插入和刪除.由于機器學(xué)習(xí)模型大都需要在一個樣本數(shù)據(jù)集上學(xué)習(xí)得到分布規(guī)律,如果數(shù)據(jù)集動態(tài)地發(fā)生變化,也就意味著學(xué)習(xí)得到的分布規(guī)律也可能是動態(tài)變化的,由此將導(dǎo)致學(xué)習(xí)過程的代價劇增.正因為如此,目前大多數(shù)的學(xué)習(xí)索引并不能很好地支持數(shù)據(jù)集的動態(tài)更新.Kraska 等人提出的幾種學(xué)習(xí)索引都不支持數(shù)據(jù)插入.在面向一維范圍查詢的學(xué)習(xí)索引中,已有大量支持插入的學(xué)習(xí)索引變體.這些研究提出了多種方法來支持插入,包括基本的就地插入方法、基于空隙數(shù)組的方法、基于緩沖區(qū)的方法和基于LSM 的方法等.但是,哪種插入方法更好目前尚沒有定論,有待進一步的對比研究.此外,為了高效地支持插入,這些學(xué)習(xí)索引變體都采用簡單的分段線性回歸模型.然而,對于多維查詢、存在查詢、文本查詢等場景,簡單的線性回歸模型不再有效,需要采用更加復(fù)雜的模型,在這些索引類型上支持插入的難度更高,目前的研究進展尚處于起步階段.

學(xué)習(xí)索引與其他領(lǐng)域的結(jié)合.學(xué)習(xí)索引的思想不僅僅能夠用于數(shù)據(jù)庫索引,而且可以應(yīng)用在更多的領(lǐng)域中.在計算機視覺領(lǐng)域,IndexNet[127]利用學(xué)習(xí)索引的觀點設(shè)計通用的上采樣操作符,證明了它在圖像匹配方面的有效性.在生物信息學(xué)領(lǐng)域,LISA[128]將學(xué)習(xí)索引的思想應(yīng)用于DNA 序列搜索,它將該應(yīng)用中流行的索引結(jié)構(gòu)FM-index[129]替換為一個模型;與之類似,Sapling[130]利用學(xué)習(xí)索引思想加速基因組的查找,它將后綴數(shù)組的內(nèi)容建模為一個函數(shù),并使用分段線性模型以有效地近似這個函數(shù).此外,學(xué)習(xí)索引的思想還能夠加速排序算法,文獻[68,131]利用機器學(xué)習(xí)模型學(xué)習(xí)經(jīng)驗CDF,快速地將元素映射到排序位置的近似位置,與經(jīng)典排序算法相比獲得了明顯的性能提升.加速排序算法能夠使更多數(shù)據(jù)結(jié)構(gòu)和算法受益,例如database cracking[132].以上研究結(jié)果也進一步說明,學(xué)習(xí)索引思想擁有巨大的潛力,探索機器學(xué)習(xí)模型在更多數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用具有重大的意義.

分布式學(xué)習(xí)索引.目前,大多數(shù)學(xué)習(xí)索引的研究都是面向單線程負載的.想要高效地支持多線程負載,需要設(shè)計并發(fā)數(shù)據(jù)結(jié)構(gòu).理論上,大多數(shù)傳統(tǒng)并發(fā)數(shù)據(jù)結(jié)構(gòu)的設(shè)計思想仍可用于學(xué)習(xí)索引,但是需要進行一些調(diào)整.目前已有的工作僅有XIndex,它在學(xué)習(xí)索引結(jié)構(gòu)中應(yīng)用了細粒度鎖和樂觀并發(fā)控制技術(shù),這方面仍具有較大的研究空間.此外,隨著遠程直接內(nèi)存訪問(remote direct memory access,簡稱RDMA)技術(shù)[133]的出現(xiàn),節(jié)點間通信延遲能夠達到微秒級,這促進了分布式索引結(jié)構(gòu)的發(fā)展[134,135].使用分布式數(shù)據(jù)結(jié)構(gòu)的一個優(yōu)點是能夠?qū)⒂嬎阖撦d分攤到每個節(jié)點,而使用RDMA 技術(shù),甚至可以由客戶端分攤服務(wù)端的計算負載[134,136,137].對于計算量遠大于傳統(tǒng)索引的學(xué)習(xí)索引來說,設(shè)計一種基于RDMA 的分布式數(shù)據(jù)結(jié)構(gòu)是未來值得探索的一個方向.

學(xué)習(xí)索引與硬件加速的結(jié)合.使用機器學(xué)習(xí)模型替代傳統(tǒng)索引結(jié)構(gòu)的一個優(yōu)點是,它使得索引能夠利用計算機中的圖形處理器(graphics processing unit,簡稱GPU)或張量處理器(tensor processing unit,簡稱TPU)[138]的算力.然而,GPU 和TPU 具有較高的調(diào)用代價,考慮設(shè)計一種批量處理策略來分攤調(diào)用代價是一種可行的方案.目前這方面的研究還處于空白狀態(tài),研究如何高效地結(jié)合CPU 與GPU/TPU 是一個有潛力的研究方向.

面向非易失內(nèi)存的學(xué)習(xí)索引.非易失內(nèi)存(non-volatile memory,簡稱NVM)兼具內(nèi)存的低延遲、可字節(jié)尋址以及外存的持久存儲等優(yōu)點,有望在未來改變現(xiàn)有的存儲架構(gòu),使得搭建基于純內(nèi)存的內(nèi)存數(shù)據(jù)庫系統(tǒng)成為可能.近年來,NVM 技術(shù)取得了一定的突破,已經(jīng)誕生了商業(yè)產(chǎn)品Intel Optane DC 持久內(nèi)存[139].學(xué)習(xí)索引假設(shè)數(shù)據(jù)存儲在內(nèi)存中,它的預(yù)測精度達到了字節(jié)粒度,而不是傳統(tǒng)索引的磁盤塊粒度.NVM 能夠為學(xué)習(xí)索引帶來持久性、可字節(jié)尋址特性和更大的內(nèi)存空間,這些都是現(xiàn)有學(xué)習(xí)索引急需的特性.然而,為NVM 設(shè)計數(shù)據(jù)結(jié)構(gòu)存在許多額外的挑戰(zhàn).首先,為了提供持久性保證,需要使用更細粒度的持久化指令,例如clflush 和mfence 等;其次,NVM 是一種讀寫不均衡的存儲器,寫延遲一般高于讀延遲,因此需要設(shè)計NVM 寫友好的數(shù)據(jù)結(jié)構(gòu);最后,由于CPU 僅支持8 字節(jié)原子寫,對于超過8 字節(jié)的更新需要設(shè)計額外的方案來保證失敗原子性(failure atomicity).總體而言,雖然目前已有一些面向NVM 的索引研究,包括B+樹[140-143]、基數(shù)樹[144]、哈希索引[145-147]和混合結(jié)構(gòu)[148]等,但設(shè)計面向NVM 的學(xué)習(xí)索引還有許多問題尚未解決,是未來值得深入研究的一個方向.

7 結(jié)束語

學(xué)習(xí)索引嘗試使用機器學(xué)習(xí)模型直接替代傳統(tǒng)的數(shù)據(jù)庫索引結(jié)構(gòu),并提升查找性能和降低索引的空間代價.學(xué)習(xí)索引是目前機器學(xué)習(xí)和數(shù)據(jù)庫技術(shù)相結(jié)合的一個重要突破,因此一經(jīng)提出即引起了學(xué)術(shù)界的廣泛關(guān)注.本文綜述了學(xué)習(xí)索引的研究進展,并提出了學(xué)習(xí)索引的一個分類框架.基于該分類框架,本文詳細討論了各類學(xué)習(xí)索引的問題、進展和存在的缺陷.其中,第1 類是面向一維范圍查詢的學(xué)習(xí)索引,這一類學(xué)習(xí)索引得到了最多的關(guān)注,在插入策略和模型設(shè)計等方面得到了優(yōu)化.第2 類是面向多維范圍查詢的學(xué)習(xí)索引,這一類工作主要關(guān)注如何將多維空間數(shù)據(jù)投影到一維空間,并使用面向一維空間的機器學(xué)習(xí)模型進行學(xué)習(xí).第3 類是面向點查詢的學(xué)習(xí)索引,這一類工作關(guān)注如何使用機器學(xué)習(xí)方法降低或增加哈希沖突的概率.最后一類是存在索引,這一類工作將存在查詢建模為二元概率分類任務(wù).最后,本文還介紹了面向?qū)W習(xí)索引的測試基準研究進展,并對學(xué)習(xí)索引的未來研究方向進行了展望.