張 洲 ,金培權 ,謝?？?/p>

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

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

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

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

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

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

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

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

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

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

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

1 面向一維范圍查詢的學習索引

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

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

1.1 面向主索引的學習索引

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

1) 初次嘗試.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig.2 Index structure of FITing-Tree圖2 FITing-Tree 索引結構

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

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

Fig.3 Index structure of ALEX圖3 ALEX 索引結構

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

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

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

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

Fig.4 Index structure of XIndex圖4 XIndex 索引結構

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

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

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

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

1.2 面向二級索引的學習索引

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

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

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

1.3 現有學習索引技術的對比

表1 給出了目前具有代表性的學習索引,并總結了不同索引之間的技術差異.

Table 1 Technology comparison of learned indexes表1 學習索引技術對比

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

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

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

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

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

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

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

與B+樹相比,學習索引額外引入了機器學習模型以提升索引性能.學習索引之所以能夠提升性能,其關鍵之處在于:

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

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

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

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

同時,與B+樹相比,學習索引也存在一些額外代價,總結如下.

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

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

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

2 面向多維范圍查詢的學習索引

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

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

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

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

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

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

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

Table 3 Comparison of learned multi-dimensional indexes表3 學習多維索引對比

3 面向點查詢的學習索引

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

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

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

3.2 局部敏感哈希

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

3.3 倒排索引

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

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

Fig.7 Index structure of Pavo圖7 Pavo 索引結構

4 面向存在查詢的學習索引

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

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

Fig.8 Original learned Bloom filter (left) and sandwiched learned Bloom filter (right)圖8 原始學習布隆過濾器(左)和三明治結構學習布隆過濾器(右)

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

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

5 面向學習索引的測試基準

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

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

6 研究展望

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

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

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

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

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

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

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

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

7 結束語

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