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

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

2(電磁空間信息重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院),安徽 合肥 230026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) 初次嘗試.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

XIndex 的數(shù)據(jù)結(jié)構(gòu)支持高并發(fā).它采用已有的樂(lè)觀并發(fā)控制[42-44]、細(xì)粒度鎖[44-46]和RCU(read-copy-update)[47]技術(shù),并精心設(shè)計(jì)了一種兩階段合并(two-phase compaction)算法來(lái)支持并發(fā)操作.如圖5 所示,如果緩沖區(qū)需要合并到排序數(shù)組中,則執(zhí)行過(guò)程分可為合并階段和復(fù)制階段.在合并階段,首先建立一個(gè)新組,并將舊緩沖區(qū)凍結(jié),此后的數(shù)據(jù)將被插入到臨時(shí)緩沖區(qū)中,例如圖5 所示的K6.然后,舊排序數(shù)組和緩沖區(qū)中的數(shù)據(jù)被合并到新排序數(shù)組中,注意,此時(shí),新排序數(shù)組中存儲(chǔ)的是指向舊數(shù)組中記錄的指針,而非真正的記錄.在合并階段,更新操作將在舊排序數(shù)組和緩沖區(qū)中執(zhí)行,例如圖5 所示的K2.然后,XIndex 在新組中訓(xùn)練模型.在完成訓(xùn)練后,XIndex使用RCU 屏障(RCU barrier)保證舊排序數(shù)組和緩沖區(qū)不再被訪問(wèn),并進(jìn)入復(fù)制階段.在復(fù)制階段,XIndex 將新排序數(shù)組中的每個(gè)指針原子替換為最新的記錄值.最后,XIndex 回收舊組的內(nèi)存資源.組分割的過(guò)程與其類似,同樣分為兩個(gè)階段.實(shí)驗(yàn)結(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)化方法傾向于使用更簡(jiǎn)單的模型,與它們的優(yōu)化方向相反,Dabble[48]使用多個(gè)神經(jīng)網(wǎng)絡(luò)模型.在數(shù)據(jù)空間劃分階段,Dabble 提出使用K-Means 算法將數(shù)據(jù)劃分為互不相交的K個(gè)區(qū)域.然后,對(duì)于每個(gè)區(qū)域,Dabble 使用一個(gè)兩層神經(jīng)網(wǎng)絡(luò)模型擬合數(shù)據(jù).最后,與PGM-index[25]相似,Dabble 使用LSM樹(shù)的延遲更新策略處理數(shù)據(jù)插入.

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

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

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

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

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 表示模型對(duì)應(yīng)的屬性取值范圍)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 局部敏感哈希

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

3.3 倒排索引

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

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

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

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

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

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

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

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

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

5 面向?qū)W習(xí)索引的測(cè)試基準(zhǔn)

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

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

6 研究展望

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

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

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

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

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

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

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

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

7 結(jié)束語(yǔ)

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