學(xué)習(xí)型數(shù)據(jù)庫索引推薦技術(shù)綜述

楊國平,喬少杰,屈露露,韓 楠,魏盛杰,元昌安

(1.成都信息工程大學(xué) 軟件工程學(xué)院， 成都 610225； 2.成都信息工程大學(xué) 管理學(xué)院， 成都 610103；3.四川音樂學(xué)院 數(shù)字媒體藝術(shù)四川省重點(diǎn)實(shí)驗(yàn)室， 成都 610021；4.廣西教育學(xué)院, 南寧 530023)

0 引言

人工智能(artificial intelligence,AI)和數(shù)據(jù)庫(database,DB)在過去的50年中得到了廣泛的研究[1-3]。首先，數(shù)據(jù)庫系統(tǒng)在許多應(yīng)用中得到了廣泛的應(yīng)用，因?yàn)閿?shù)據(jù)庫通過提供用戶友好的聲明式查詢范例和封裝復(fù)雜的查詢優(yōu)化函數(shù)而易于使用。其次，人工智能最近取得突破得益于三大驅(qū)動(dòng)力：大規(guī)模數(shù)據(jù)、新算法和高計(jì)算能力。此外，人工智能和數(shù)據(jù)庫可以相互受益[4-5]。

傳統(tǒng)的數(shù)據(jù)庫技術(shù)往往依賴于人工算法或人工干預(yù)，如數(shù)據(jù)庫參數(shù)調(diào)整、故障診斷、索引推薦等[6]。但在大數(shù)據(jù)時(shí)代，數(shù)據(jù)庫實(shí)例較多，腳本更復(fù)雜，數(shù)據(jù)量更大，傳統(tǒng)的數(shù)據(jù)庫索引技術(shù)很難滿足大數(shù)據(jù)的需求，比如云數(shù)據(jù)庫中有數(shù)以百萬計(jì)的數(shù)據(jù)庫實(shí)例，DBA(database administrator)不可能完全控制百萬計(jì)的數(shù)據(jù)庫實(shí)例，一旦DBA對管理疏忽，后果不堪設(shè)想，而且不同實(shí)例的應(yīng)用和用戶使用水平也有很大差異。傳統(tǒng)的算法很難泛化，人工干預(yù)難以處理更多的案例。

機(jī)器學(xué)習(xí)可以通過學(xué)習(xí)歷史數(shù)據(jù)中的關(guān)系，輔助DBA做決策。機(jī)器學(xué)習(xí)技術(shù)在許多科學(xué)研究領(lǐng)域得到了廣泛的應(yīng)用[7-9]，機(jī)器學(xué)習(xí)也為數(shù)據(jù)庫索引優(yōu)化技術(shù)提供了新的可能性，比如傳統(tǒng)的機(jī)器學(xué)習(xí)模型：線性傳回歸[10]、隨機(jī)森林[11]、支持向量機(jī)[12]和集成學(xué)習(xí)[13]等，從歷史數(shù)據(jù)中積累“經(jīng)驗(yàn)”，可以提高解決復(fù)雜問題的能力。但是傳統(tǒng)的機(jī)器學(xué)習(xí)模型只能描述一個(gè)層次的學(xué)習(xí)過程，而且相對簡單，例如簡單的線性回歸模型難以求解高階參數(shù)和連續(xù)參數(shù)空間[14]，于是深度學(xué)習(xí)(deep learning,DL)與強(qiáng)化學(xué)習(xí)(reinforcement learning,RL)被提出，有學(xué)者將DL與RL結(jié)合，變成深度強(qiáng)化學(xué)習(xí)(deep reinforcement learning,DRL)，使用DRL模型可以解決NP-hard問題，因?yàn)樗梢运阉鼾嫶蟮慕饪臻g。人工智能可以使數(shù)據(jù)庫更加智能化(AI4DB)，使用人工智能去優(yōu)化數(shù)據(jù)庫(如代價(jià)估計(jì)、連接順序選擇、節(jié)點(diǎn)調(diào)整、索引和視圖推薦等)是目前以及未來的研究熱點(diǎn)。

基于索引推薦的不同階段，本文將其分為索引生成與索引選擇兩部分。索引生成是為了生成滿足數(shù)據(jù)庫的索引數(shù)據(jù)結(jié)構(gòu)，而索引選擇是選擇建立索引的方案。本文對索引生成技術(shù)和索引選擇技術(shù)進(jìn)行綜述。索引對于提高復(fù)雜數(shù)據(jù)集的搜索和查詢?nèi)蝿?wù)效率非常重要，特別是在處理事務(wù)負(fù)載時(shí)，將索引嵌入適當(dāng)?shù)牧锌梢院艽蟪潭壬咸岣咛幚硇蔥15]。

傳統(tǒng)數(shù)據(jù)庫采用通用的索引結(jié)構(gòu)(如：B-Tree)，這種索引結(jié)構(gòu)只能讓搜索數(shù)據(jù)時(shí)的速度有保障，但它沒有利用數(shù)據(jù)之間的分布以及數(shù)據(jù)庫中其他信息。此外，數(shù)據(jù)集越大，索引也就越大，很容易造成空間浪費(fèi)。因此，需要一種高效的索引技術(shù)來支持?jǐn)?shù)據(jù)庫的應(yīng)用。

對于索引選擇，首先定義索引選擇問題如下：假設(shè)存在表集合T，令C表示T中所含表的列集合，其中，某一列c上的索引大小為Size(c),c∈C。給定一個(gè)查詢集合Q，給某一查詢q在列c上建索引的獎(jiǎng)勵(lì)定義為Reward(q,c),其中q∈Q,c∈C,再給定一個(gè)空間限制S，索引選擇的目的就是找到一個(gè)列子集C*去構(gòu)建索引，要使獎(jiǎng)勵(lì)Reward達(dá)到最大且索引總大小不得超過S，形式化表示如下：Maximize ∑ Reward(q∈Q,c∈C*),且∑ Size(c∈C*)≤S。這里有幾個(gè)挑戰(zhàn)。一是如何估計(jì)獎(jiǎng)勵(lì)Reward(q,c)，一個(gè)常規(guī)的方法是使用一個(gè)假設(shè)的索引，它將索引信息添加到數(shù)據(jù)庫管理系統(tǒng)(DBMS)的數(shù)據(jù)字典中，而不是創(chuàng)建實(shí)際的索引，從而使DBMS中的查詢優(yōu)化器能夠識別索引的存在并估計(jì)查詢執(zhí)行的代價(jià)，而不必建立真正的索引。一個(gè)索引的估計(jì)獎(jiǎng)勵(lì)是在有或沒有假設(shè)索引的情況下，查詢執(zhí)行的估計(jì)代價(jià)之差。二是解決優(yōu)化問題，有2個(gè)主要的解決方案來解決這些問題：靜態(tài)索引選擇和動(dòng)態(tài)索引選擇。靜態(tài)索引選擇方法要求DBA提供一個(gè)通用的查詢負(fù)載，并通過分析這個(gè)工作負(fù)載來選擇索引方案。動(dòng)態(tài)索引選擇方法對數(shù)據(jù)庫進(jìn)行監(jiān)控，根據(jù)工作負(fù)載的變化選擇索引方案。靜態(tài)方法和動(dòng)態(tài)方法的主要區(qū)別在于靜態(tài)方法只選擇和物化一個(gè)索引計(jì)劃，而動(dòng)態(tài)方法則根據(jù)工作負(fù)載的變化動(dòng)態(tài)地創(chuàng)建或刪除一些索引。

1 索引生成技術(shù)

傳統(tǒng)的數(shù)據(jù)庫是由數(shù)據(jù)庫架構(gòu)師根據(jù)自己的經(jīng)驗(yàn)設(shè)計(jì)的，但數(shù)據(jù)庫架構(gòu)師只能探索有限的設(shè)計(jì)空間。傳統(tǒng)或非人工智能索引方法，如位圖索引，基于樹的索引等，這些方法是可以滿足用戶的基本需求的，但它們無法對用戶行為或者大數(shù)據(jù)進(jìn)行預(yù)測，而且通用的傳統(tǒng)索引結(jié)構(gòu)無法對特定的業(yè)務(wù)有極好的表現(xiàn)，因?yàn)樗鼈儫o法學(xué)習(xí)數(shù)據(jù)的分布以及其他數(shù)據(jù)庫內(nèi)部信息，因此，有一些索引生成技術(shù)被提出。數(shù)據(jù)庫社區(qū)和機(jī)器學(xué)習(xí)社區(qū)研究基于學(xué)習(xí)的結(jié)構(gòu)，例如基于學(xué)習(xí)的B樹，使用基于學(xué)習(xí)的模型代替?zhèn)鹘y(tǒng)索引以減小索引大小并提高性能。下面對索引生成技術(shù)展開綜述(見表1)，分別為基于學(xué)習(xí)的范圍索引、基于學(xué)習(xí)的哈希索引、基于學(xué)習(xí)的布隆過濾器等6個(gè)方面進(jìn)行綜述。

表1 索引生成技術(shù)相關(guān)工作總結(jié)

1.1 基于學(xué)習(xí)的范圍索引

Kraska等[16]認(rèn)為“索引即模型”，其中B+樹索引可以看作是將每個(gè)查詢鍵映射到其頁面的模型，如圖1所示。B樹是一個(gè)模型，或者在機(jī)器學(xué)習(xí)術(shù)語中是一個(gè)回歸樹：它將鍵映射到一個(gè)具有最小和最大誤差的區(qū)域，并保證如果該鍵存在，則可以在該區(qū)域中找到它。其中最小誤差(min_err)為0，最大誤差(max_err)為頁面大小(page_size)。對于有序數(shù)組，較大的位置下標(biāo)意味著較大的鍵值，并且范圍索引需要與累積分布函數(shù)相近。

圖1 “索引即模型”概念圖

基于上述觀察，Kraska等[16]提出了一種遞歸模型索引，它使用基于學(xué)習(xí)的模型來估計(jì)一個(gè)鍵的頁面編號。該方法在內(nèi)存環(huán)境下的性能優(yōu)于B+樹，但不支持?jǐn)?shù)據(jù)更新，對二級索引支持較差。為了支持二級索引，Wu等[17]提出了一種基于學(xué)習(xí)的二級索引機(jī)制，它利用分層回歸搜索樹(TRS)來捕獲列相關(guān)性和異常值，每個(gè)葉節(jié)點(diǎn)包含線性回歸模型，該模型將目標(biāo)值映射到相關(guān)值，每個(gè)內(nèi)部節(jié)點(diǎn)維護(hù)固定數(shù)量的指向子節(jié)點(diǎn)的指針。該模型有3個(gè)步驟來響應(yīng)查詢：(1) 搜索TRS樹以將目標(biāo)列映射到現(xiàn)有索引，(2) 利用現(xiàn)有索引獲取候選元組，(3) 最后驗(yàn)證元組。該方法在內(nèi)存和基于磁盤的DBMS中都有效?！白詈笠挥⒗锼阉鳌笔腔趯W(xué)習(xí)的模型替換B樹的一個(gè)最大挑戰(zhàn)，比如，從誤差的數(shù)量級上來看，使用單個(gè)模型將預(yù)測誤差從100 M數(shù)量級降到數(shù)百數(shù)量級往往很困難。然而，將誤差從100 M數(shù)量級減到10 K數(shù)量級卻簡單得多。針對這個(gè)問題，Kraska等[16]還提出了層次模型，在每個(gè)階段，輸入的變量都是模型，并基于輸入選擇另一個(gè)模型，直到最后階段，模型的輸出為記錄的位置。這樣，每個(gè)模型負(fù)責(zé)一塊區(qū)域，可以更好地降低預(yù)測誤差。另外，遞歸模型[16]也可以根據(jù)場景，實(shí)現(xiàn)混合模型使用。給定一個(gè)索引配置，它將階段數(shù)和每個(gè)階段的模型數(shù)指定為大小數(shù)組，算法1展示了混合模型端到端的訓(xùn)練算法流程。

算法1：混合端到端訓(xùn)練法

輸入：閾值(threshold),階段數(shù)組(stages[]),復(fù)雜神經(jīng)網(wǎng)絡(luò)(NN_complexity),記錄數(shù)據(jù)(record),索引模型(Model index[][])

輸出：索引(trained index)

1:M←stages.size; tmp_record[][]← all_data;#初始化

2: fori←1 toMdo

3: forj←1 to stages[i] do

4: index[i][j]←new NN trained on tmp_records[i][j];

5: ifi

6: forr∈tmp_records[i][j] do

7:p←index[i][j](r.key)/stages[i+1];

8: tmp_records[i+1][p].add(r);

9: forj←1 to index[M].size do

10: index[M][j].calc_err(tmp_records[M][j]);

11: if index[M][j].max_abs_err > threshold then

12: index[M][j]= new B-Tree on tmp_records[M][j];

13:return index;

對于算法1，從整個(gè)數(shù)據(jù)集初始化(第1行)開始，它首先訓(xùn)練頂層節(jié)點(diǎn)模型(第2～4行)?；趯@個(gè)頂層節(jié)點(diǎn)模型的預(yù)測，它從下一階段(第5～8行)選擇模型，并添加屬于該模型的所有鍵(第8行)。最后，在混合索引的情況下，如果絕對值的最小/最大誤差高于預(yù)定義的閾值(第9～12行)，則通過用B樹替換神經(jīng)網(wǎng)絡(luò)模型來優(yōu)化索引。

Galakatos等[18]提出的另一個(gè)基于學(xué)習(xí)的索引Fitting-tree，提供了嚴(yán)格的誤差界限和可預(yù)測的性能，它支持2種數(shù)據(jù)插入策略。對于原地插入策略，F(xiàn)itting-tree在頁面的每一端保留額外的插入空間，以使原地插入不會(huì)超過頁面誤差。然而，插入大的片段代價(jià)可能很高。對于增量插入策略，在每個(gè)段中保持一個(gè)固定大小的緩沖區(qū)，并且這些鍵將被插入緩沖區(qū)并進(jìn)行排序。一旦緩沖區(qū)溢出，它就必須拆分和合并這些段。與Fitting-tree類似，Alex索引[19]也為插入的鍵保留空間。不同的是，Alex索引中的保留空間是分散的，插入的鍵直接放在模型預(yù)測的位置。如果該位置被占用，則會(huì)插入更多的間隙(對于有間隙的數(shù)組)或擴(kuò)展自身(對于壓縮內(nèi)存數(shù)組)。Alex索引可以更靈活地在空間和效率之間做出權(quán)衡。

Tang等[20]提出了一個(gè)稱為Doraemon的工作負(fù)載感知索引。Doraemon可以通過在訓(xùn)練數(shù)據(jù)中復(fù)制多個(gè)頻繁訪問的查詢來合并讀模式，并且頻繁查詢比其他查詢對誤差的影響更大，優(yōu)化程度更高。Doraemon重復(fù)使用預(yù)訓(xùn)練模型，這些模型所用的數(shù)據(jù)具有相似的分布，相似的數(shù)據(jù)分布需要相似的模型結(jié)構(gòu)。

針對并行數(shù)據(jù)庫，并行B樹進(jìn)行范圍分區(qū)的數(shù)據(jù)遷移是一種解決方案，范圍分區(qū)和鏈?zhǔn)椒蔷奂北镜慕Y(jié)合提供了高可用性，同時(shí)保持了可擴(kuò)展性。Luo等[21]提出了一種利用并行B樹(簡稱Fat-Btree)實(shí)現(xiàn)可擴(kuò)展性的方法，單個(gè)Fat-Btree提供了所有處理器單元中主數(shù)據(jù)和備份數(shù)據(jù)的訪問路徑，大大減少了故障切換時(shí)間。此外，它支持動(dòng)態(tài)負(fù)載平衡從而無需進(jìn)行物理數(shù)據(jù)遷移，并提高了處理索引的內(nèi)存空間利用率。

1.2 基于學(xué)習(xí)的哈希索引

在基于非易失性內(nèi)存(non-volatile memory,NVM)的索引設(shè)計(jì)中，基于哈希的結(jié)構(gòu)是最有前途的候選結(jié)構(gòu)之一，因?yàn)樗梢猿浞掷肗VM的字節(jié)可尋址特性來執(zhí)行具有恒定時(shí)間復(fù)雜度的查詢操作。哈希映射的索引盡可能避免沖突，因?yàn)闆_突嚴(yán)重影響性能和存儲(chǔ)需求，可以使用基于學(xué)習(xí)的方案以減少?zèng)_突的數(shù)量。Kraska等[16]建議將鍵的CDF(cumulative distribution function)近似為散列函數(shù)，以將所有鍵均勻地分布在每個(gè)散列桶中并減少?zèng)_突?；诠５倪B接算法通常包含2個(gè)階段：分區(qū)階段和分區(qū)連接階段。Harris等[22]描述了使用最優(yōu)多屬性哈希(multi-attribute hash,MAH)索引來降低分區(qū)階段(基于哈希連接算法)的平均代價(jià)的過程，通過完全消除最常見的連接查詢的分區(qū)階段來達(dá)到目的，并證明了該技術(shù)可以擴(kuò)展到包括數(shù)據(jù)的多個(gè)副本，每個(gè)副本具有不同的MAH索引方案組織，并且這進(jìn)一步降低了執(zhí)行hash-join算法的分區(qū)階段的平均成本。

Ma等[23]發(fā)現(xiàn)“再散列操作”可能會(huì)在NVM上產(chǎn)生大量的寫活動(dòng)，這對NVM的續(xù)航能力是有害的，并且會(huì)導(dǎo)致性能急劇下降。此外，無法對基于散列的索引有效地進(jìn)行范圍查詢操作。于是，Ma等[23]提出了一種基于哈希的索引方案，對于NVM是友好的，稱為“Bucket Hash”，用于基于 NVM的內(nèi)存數(shù)據(jù)庫。具體來說，為了減少再散列 操作的延遲，其使用多個(gè)小桶而不是更大的桶。為了最大限度地減少NVM寫入的次數(shù)，Bucket Hash在進(jìn)行再散列操作期間，會(huì)使大約一半的條目重新散列到新的存儲(chǔ)桶中，并且將這些桶維護(hù)為一個(gè)排序的鏈表。由于鏈表存在搜索效率低下的問題，引入了一種輔助結(jié)構(gòu)來提高查詢操作的性能。此外，結(jié)合輔助結(jié)構(gòu)和排序鏈表，該索引方案可以使范圍查詢操作易于管理。

1.3 基于學(xué)習(xí)的布隆過濾器

布隆過濾器(bloom filter，BF)是一個(gè)常用的索引，用來判斷一個(gè)值是否存在于給定的集合中。但是傳統(tǒng)的BF可能會(huì)由于位數(shù)組和哈希函數(shù)而占用大量內(nèi)存。BF可以加速對數(shù)結(jié)構(gòu)合并(logarithmic structure merge，LSM)樹中的點(diǎn)查找速率，主要通過減少對不包含所需鍵的層訪問來實(shí)現(xiàn)。在 LSM樹中，在查詢樹的每一層時(shí)都會(huì)使用BF，因此，隨著數(shù)據(jù)大小(以及樹的高度)的增長，CPU的代價(jià)也會(huì)增加。為了減小BF所占地內(nèi)存，Kraska等[16]提出了一種基于學(xué)習(xí)的BF，訓(xùn)練一個(gè)二分類器來判斷數(shù)據(jù)集中是否存在查詢。新的查詢需要首先通過分類器，未通過的應(yīng)該進(jìn)一步通過傳統(tǒng)的BF，以保證不存在假負(fù)例。為了解決LSM樹中BF不斷增加的CPU代價(jià)，Zhu等[24]建議在BF內(nèi)部和跨BF以及不同層之間積極地重復(fù)使用哈希計(jì)算，并且通過分析和實(shí)驗(yàn)，表明該方法可以保持接近理想的錯(cuò)誤率，同時(shí)運(yùn)行時(shí)間明顯減少。然后，使用散列共享來降低查詢的CPU代價(jià)，導(dǎo)致在LSM樹中查找性能提高10%。

對于高維數(shù)據(jù)集，逐個(gè)搜索一組BF會(huì)耗費(fèi)空間和時(shí)間。Macke等[25]提出一種用于多維數(shù)據(jù)的、高效的、基于學(xué)習(xí)的布隆過濾器。對于屬性嵌入，通過字符級循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)表示高基數(shù)(high-cardinality)屬性中的值，以減小模型大小。此外，他們選擇最好的分類器去逼近閾值以最大化真正例率和假正例率之間的KL散度(Kullback-Leibler divergence)。為了減少噪聲對索引數(shù)據(jù)的影響，為每個(gè)正例訓(xùn)練樣本引入了一個(gè)移位參數(shù)。

1.4 基于學(xué)習(xí)的鍵值對存儲(chǔ)

Idreos等[26-27]表明鍵值存儲(chǔ)(KV-store)中的數(shù)據(jù)結(jié)構(gòu)可以從基本組件構(gòu)建，基于學(xué)習(xí)的代價(jià)模型可以指導(dǎo)構(gòu)建方向，如圖2所示，從性能權(quán)衡到數(shù)據(jù)結(jié)構(gòu)、鍵值存儲(chǔ)豐富的應(yīng)用程序。設(shè)計(jì)空間可以用所有基本設(shè)計(jì)組件(例如柵欄指針、鏈接和時(shí)間分區(qū))來描述，而設(shè)計(jì)連續(xù)體是設(shè)計(jì)空間的一個(gè)子空間，它連接多個(gè)設(shè)計(jì)。為了設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，首先確定總代價(jià)的閾值以及可以調(diào)整哪個(gè)節(jié)點(diǎn)來緩解它，然后向一個(gè)具體的方面調(diào)整節(jié)點(diǎn)，直到達(dá)到其閾值或總代價(jià)達(dá)到最小值。這個(gè)過程類似于梯度下降，可以自動(dòng)進(jìn)行。

圖2 從性能權(quán)衡到數(shù)據(jù)結(jié)構(gòu)、鍵值存儲(chǔ)豐富的應(yīng)用示意圖

許多現(xiàn)代關(guān)系型數(shù)據(jù)庫(DBMS)架構(gòu)需要從存儲(chǔ)中轉(zhuǎn)移之后再進(jìn)行處理。鑒于數(shù)據(jù)量不斷增加，數(shù)據(jù)傳輸速度成為可擴(kuò)展性的限制因素。相鄰數(shù)據(jù)處理(neighbor data process，NDP)和智能/計(jì)算存儲(chǔ)成為有希望的解決方案，這些解決方案允許執(zhí)行分離原地操作、減少數(shù)據(jù)傳輸和更好的帶寬利用率。然而，并非每個(gè)操作都適合原地執(zhí)行，需要仔細(xì)配置和優(yōu)化。Christian等[28]提出了一種基于NDP的KV存儲(chǔ)查詢優(yōu)化代價(jià)模型。他們?yōu)橛?jì)算存儲(chǔ)提供了NDP感知代價(jià)模型的案例，在這種設(shè)置中，DBMS操作具有主機(jī)和 NDP風(fēng)格，并且需要自動(dòng)選擇。此外，他們提出了一個(gè)初始的NDP感知代價(jià)模型。只要給定基本工作量，代價(jià)模型估計(jì)代價(jià)基本正確，從而產(chǎn)生適當(dāng)?shù)膱?zhí)行計(jì)劃選擇。

1.5 基于學(xué)習(xí)的空間索引

傳統(tǒng)的空間索引，例如R-tree、kd-tree、G-tree，無法捕捉底層數(shù)據(jù)的分布，可以通過基于學(xué)習(xí)的技術(shù)進(jìn)一步優(yōu)化查找時(shí)間和空間開銷。例如，Wang等[29]提出了一種基于學(xué)習(xí)的ZM索引，該索引首先將多維地理空間點(diǎn)映射為具有Z排序的一維向量，然后構(gòu)建神經(jīng)網(wǎng)絡(luò)索引以擬合分布并預(yù)測查詢位置。

1.6 基于學(xué)習(xí)的高維數(shù)據(jù)索引

高維數(shù)據(jù)上的最近鄰搜索(nearest neighbor search,NNS)問題旨在有效地找到查詢中最近的k個(gè)點(diǎn)。解決近似NNS問題的傳統(tǒng)方法可以分為三類，包括基于哈希的索引、基于分區(qū)的索引和基于圖的索引。一些學(xué)者[30-32]通過使用機(jī)器學(xué)習(xí)技術(shù)改進(jìn)了前2種方法。Schlemper等[31]提出了一種端到端的深度散列方法，該方法使用有監(jiān)督的卷積神經(jīng)網(wǎng)絡(luò)，它結(jié)合了2種損失：相似性損失和比特率損失，因此它可以同時(shí)將數(shù)據(jù)離散化并最小化碰撞概率。Sablayrolles等[32]提出了一種類似的端到端深度學(xué)習(xí)架構(gòu)，該架構(gòu)學(xué)習(xí)催化劑功能以提高后續(xù)編碼階段的質(zhì)量，引入了源自Kozachenko-Leonenko微分熵估計(jì)器的損失，以支持球形輸出空間中的均勻性。Dong等[30]減少高維空間分區(qū)問題以權(quán)衡圖分區(qū)和監(jiān)督分類問題。首先使用圖劃分算法 KaHIP將KNN(K近鄰)圖劃分為平衡的小分區(qū)，然后學(xué)習(xí)神經(jīng)模型來預(yù)測查詢的KKN落入分區(qū)的概率，并搜索概率較大的分區(qū)。

2 索引選擇技術(shù)

在DBMS中，建立索引的方案有若干種，每種方案帶來的檢索速度與時(shí)間/空間消耗都不一樣，通過多方面考慮，權(quán)衡選擇一個(gè)最佳索引是很困難的，可以證明索引選擇問題是一個(gè)NP完全問題[33]。此外，許多開發(fā)者把索引應(yīng)用到不同場景中，開發(fā)了原型系統(tǒng)，提出了很多優(yōu)化的解法[33]。下面我們分別綜述4類索引選擇技術(shù)：1) 不需要DBA干預(yù)的在線方法[34-35]；2) 有 DBA 參與的離線方法；3) 半自動(dòng)化的索引選擇；4) 基于機(jī)器學(xué)習(xí)的索引選擇(見表2)。

表2 索引選擇技術(shù)相關(guān)工作總結(jié)

2.1 在線方法

在線方法的有3個(gè)步驟：工作負(fù)載分析、索引方案選擇、索引方案實(shí)現(xiàn)，這3個(gè)步驟的循環(huán)進(jìn)行，可以對工作負(fù)載的變化做自動(dòng)調(diào)整。Lühring等[34]給出了一個(gè)基于“觀察-預(yù)測-反應(yīng)”循環(huán)的軟索引自治管理方法，它可以在當(dāng)前配置上自動(dòng)根據(jù)環(huán)境實(shí)現(xiàn)索引結(jié)構(gòu)，并在線自動(dòng)調(diào)整框架本身的性能。

1) 工作負(fù)載分析：在線方法實(shí)時(shí)監(jiān)控工作負(fù)載，并對單個(gè)查詢分析。對于單個(gè)查詢，通過對其中的SELECT，WHERE，ORDER BY和GROUP BY子句進(jìn)行分析，提取可索引列，然后采用與DB2 Advisor[35]相同的方法枚舉候選索引方案，并對索引方案的空間大小進(jìn)行估計(jì)，其使用這個(gè)索引帶來的時(shí)間減少量為獎(jiǎng)勵(lì)，獎(jiǎng)勵(lì)越大越好。對于工作負(fù)載的分析，將對單個(gè)查詢的分析結(jié)果合并即可。

2) 索引方案選擇：Toumi等[36]使用靜態(tài)方法和增量動(dòng)態(tài)方法引入了位圖連接索引選擇問題 (bitmap join index selection problem，BJISP)的一種新的多目標(biāo)公式。首先，提出了靜態(tài)BJISP的多目標(biāo)公式，稱為SMBJISP，它創(chuàng)建了一個(gè)使用兩個(gè)目標(biāo)函數(shù)，并從頭開始構(gòu)建位圖連接索引的解決方案集，這些目標(biāo)函數(shù)將查詢負(fù)載代價(jià)和受上限約束的存儲(chǔ)大小降至最低。其次，引入了一種稱為IMBJISP的BJISP增量動(dòng)態(tài)多目標(biāo)公式。此公式假設(shè)存在實(shí)際解決方案(即針對查詢工作負(fù)載生成并實(shí)施最佳解決方案)，并以增量動(dòng)態(tài)方式考慮查詢工作負(fù)載的更新。Schnaitte等提出COLT[37]，它支持基于當(dāng)前索引方案自動(dòng)在線實(shí)現(xiàn)新索引。 它將索引選擇問題建模為在離線索引選擇中描述的背包問題，并應(yīng)用動(dòng)態(tài)規(guī)劃來獲得索引方案。一旦得出最終的指標(biāo)方案，將立即對其進(jìn)行物化。但是，傳統(tǒng)的在線方法沒有考慮DBA的經(jīng)驗(yàn)。此外，索引方案的不斷變化可能會(huì)影響DBMS的穩(wěn)定性并導(dǎo)致高開銷。

3) 索引方案實(shí)現(xiàn)：Lühring等[34]將索引實(shí)現(xiàn)過程延后進(jìn)行，即在系統(tǒng)空閑時(shí)間執(zhí)行。為了索引效果盡快體現(xiàn)，在反應(yīng)期引入了兩個(gè)操作IndexBuildScan和SwitchPlan。IndexBuildScan對通常的表掃描算法進(jìn)行了擴(kuò)展，將要生成的索引集合作為一個(gè)額外的輸入，在掃描的同時(shí)建立索引。SwitchPlan允許在執(zhí)行與創(chuàng)建索引的查詢再次執(zhí)行時(shí)，使用最新創(chuàng)建的索引。例如，對于嵌套循環(huán)連接，內(nèi)層循環(huán)的表會(huì)被掃描多次，第二次掃描時(shí)，就可以利用先前建好的索引。

根據(jù)表2以及對上述典型在線方法實(shí)現(xiàn)的分析，優(yōu)點(diǎn)是在線法可以根據(jù)負(fù)載變化及時(shí)調(diào)整索引，也能在一定程度上減輕DBA的負(fù)擔(dān)。然而，也有明顯的缺點(diǎn)，即沒有充分利用DBA的經(jīng)驗(yàn)，而且需要系統(tǒng)持續(xù)運(yùn)行，會(huì)長時(shí)間占用系統(tǒng)資源。同時(shí)，連續(xù)調(diào)整也具有一定的盲目性。此類方法適應(yīng)能力為中等。

2.2 離線方法

此方法依賴DBA從查詢?nèi)罩局羞x擇一些頻繁的查詢作為代表工作負(fù)載，并使用工作負(fù)載來選擇索引。Chaudhuri等[38]為Microsoft SQL服務(wù)器提出了一個(gè)索引選擇工具AutoAdmin，主要原理是為每個(gè)查詢選擇性能良好的索引方案，然后擴(kuò)展到查詢集合Q中的多個(gè)查詢。首先，對于每個(gè)查詢qi∈Q，AutoAdmin從SQL查詢中提取可索引的列。其次，AutoAdmin使用一個(gè)原生的枚舉算法使索引列集合作為候選，例如，I= {{i1,i2,i3,i4},{i3,i4,i5,i6},…}。然后AutoAdmin選擇I中對該查詢具有最高收益的索引方案。然后，對于每個(gè)查詢，都有相應(yīng)的最優(yōu)索引策略，對于Q中的所有查詢，AutoAdmin根據(jù)收益選擇top-k方案。接下來，對于每個(gè)top-k方案，AutoAdmin使用貪心算法增量添加可索引列，直到大小等于閾值B。最后，將選擇具有最高收益且在存儲(chǔ)預(yù)算內(nèi)的方案。

根據(jù)表2以及對上述典型離線方法實(shí)現(xiàn)的分析，優(yōu)點(diǎn)是離線法能夠充分利用DBA的反饋。但是，無法處理工作負(fù)載的動(dòng)態(tài)變化，并且加重了DBA的負(fù)擔(dān)。此類方法適應(yīng)能力低?？梢钥吹剑x線方法與在線方法的優(yōu)缺點(diǎn)相反。

2.3 半自動(dòng)方法

由于在線和離線方法都存在一定的不足，于是，Schnaitter等[39]提出了一種被稱為工作負(fù)載反饋索引調(diào)整(workload feedback index tuning，WFIT)的方案，該方案基于半自動(dòng)索引調(diào)整(semi-automatic index tuning)，將在線方法和離線方法結(jié)合起來，充分利用二者各自的優(yōu)點(diǎn)。既減輕了DBA選擇典型工作負(fù)載的工作量，充分利用了調(diào)優(yōu)器的計(jì)算能力，同時(shí)，還將DBA的專業(yè)知識應(yīng)用在內(nèi)，實(shí)現(xiàn)迭代的索引調(diào)整方法。它可以實(shí)時(shí)監(jiān)控DBMS，動(dòng)態(tài)分析工作負(fù)載并列舉了一些候選方案來調(diào)整索引結(jié)構(gòu)。但是在實(shí)施索引方案之前，WFIT需要 DBA 判斷是否應(yīng)該對列進(jìn)行索引。然后在后續(xù)的索引選擇過程中，WFIT會(huì)根據(jù)DBA的經(jīng)驗(yàn)，從索引方案中剔除不應(yīng)該被索引的列。同樣，它也可以將應(yīng)該被索引的列添加到索引方案中。

根據(jù)表2以及對上述典型半自動(dòng)方法實(shí)現(xiàn)的分析，優(yōu)點(diǎn)是半自動(dòng)法可以減輕DBA的負(fù)擔(dān)以及充分利用DBA的專業(yè)知識；缺點(diǎn)為沒有考慮工作方案對整體的影響。此類方法適應(yīng)能力為中等。

2.4 基于學(xué)習(xí)的方法

給定一個(gè)工作負(fù)載，索引選擇的任務(wù)是決定創(chuàng)建索引的屬性使處理工作負(fù)載的好處最大。通常，由于空間約束和索引維護(hù)成本，會(huì)給出要?jiǎng)?chuàng)建的索引數(shù)量的上限，因此簡單地為所有列創(chuàng)建索引不是一個(gè)好的選項(xiàng)。當(dāng)然，目標(biāo)是在不需要管理員的情況下，以自動(dòng)的方式提出適當(dāng)?shù)乃饕x擇。

Sharma等[40]基于深度強(qiáng)化學(xué)習(xí)(deep reinforcement learning,DRL)進(jìn)行數(shù)據(jù)庫自動(dòng)管理，總結(jié)了應(yīng)用DRL來訓(xùn)練神經(jīng)網(wǎng)絡(luò)接管管理過程，本質(zhì)上，必須定義一個(gè)所謂的問題環(huán)境，由以下4個(gè)組件組成：① 神經(jīng)網(wǎng)絡(luò)的輸入。這通常是具有查詢特征的當(dāng)前工作負(fù)載，系統(tǒng)應(yīng)該針對該工作負(fù)載以及配置的當(dāng)前狀態(tài)進(jìn)行優(yōu)化；② 可以采取的一系列行動(dòng)。操作可以是在某個(gè)列上創(chuàng)建輔助索引或更改數(shù)據(jù)庫緩沖區(qū)的大小。此類操作是從當(dāng)前系統(tǒng)配置到新系統(tǒng)配置的轉(zhuǎn)換；③ 獎(jiǎng)勵(lì)函數(shù)，評定所采取動(dòng)作的影響。例如，可以將采取新配置(動(dòng)作)后的運(yùn)行時(shí)間與目前的最佳配置進(jìn)行比較。改善越高，回報(bào)的正獎(jiǎng)勵(lì)越高。如果性能下降，則返回負(fù)獎(jiǎng)勵(lì)；④ 引導(dǎo)學(xué)習(xí)過程的超參數(shù)。這包括神經(jīng)網(wǎng)絡(luò)的屬性(例如，隱藏層數(shù)、每層節(jié)點(diǎn)數(shù))以及學(xué)習(xí)過程的屬性，如迭代次數(shù)。

基于機(jī)器學(xué)習(xí)的索引選擇方法會(huì)自動(dòng)從歷史數(shù)據(jù)而不是DBA的反饋中學(xué)習(xí)經(jīng)驗(yàn)。Pedrozo等[33]提出了一種基于學(xué)習(xí)分類器系統(tǒng)(learning classifier system，LCS)和遺傳算法的索引選擇方法(index tuning with learning classifier system，ITLCS)，并且ITLCS結(jié)合了強(qiáng)化學(xué)習(xí)算法。ITLCS使用LCS來創(chuàng)建和更新基于規(guī)則表示的知識，并生成覆蓋數(shù)據(jù)庫中絕大多數(shù)情況的索引。在經(jīng)典的LCS中，基因算法將每個(gè)分類器當(dāng)作一個(gè)單獨(dú)的個(gè)體，并將低適應(yīng)度的分類器替換為高適應(yīng)度的分類器。每個(gè)分類器進(jìn)行監(jiān)督學(xué)習(xí)，輸入是選擇的索引，輸出是性能分?jǐn)?shù)。每個(gè)分類器對應(yīng)一組判斷規(guī)則表示，包含引導(dǎo)詞(Condition)和結(jié)果(Action)兩部分，遵循“IF-THEN ”的格式，即如果滿足某條件，就采取某個(gè)動(dòng)作。每個(gè)分類器的染色體上有16個(gè)基因編碼、16個(gè)引導(dǎo)詞以及1個(gè)執(zhí)行結(jié)果。引導(dǎo)詞表示一些環(huán)境特征，比如表中或列上是否存在索引、查詢語句等；結(jié)果表示對索引執(zhí)行的操作，如創(chuàng)建、更新等。每個(gè)分類器都有適應(yīng)度指標(biāo)，指標(biāo)用于衡量對環(huán)境的適應(yīng)度，指標(biāo)的值越高，說明分類器可能被使用或者持續(xù)被使用。

ITLCS的工作流程大致分為4步：① 探測器從環(huán)境中探測信息，規(guī)則和信息處理系統(tǒng)將對探測到的信息進(jìn)行處理，分類器試圖將信息與引導(dǎo)詞組合(此處信息對應(yīng)于索引選擇定義中的查詢q)；② 如果滿足條件的分類器數(shù)量大于1，它們將在環(huán)境中相互競爭，算法將會(huì)選取指標(biāo)最高的那個(gè)分類器；③ 被選擇的分類器將會(huì)采取結(jié)果(動(dòng)作，即索引選擇定義中的c)，然后從環(huán)境中接收反饋信息，并對所選分類器進(jìn)行獎(jiǎng)懲(即索引選擇定義中的Reward)，最后對所有分類器收取存活代價(jià)，降低其強(qiáng)度；④ 使用遺傳算法產(chǎn)生新的后代分類器，并淘汰掉不合適的分類器。

ITLCS將DBA與索引選擇進(jìn)行了解耦，使強(qiáng)化學(xué)習(xí)對分類器做決策，可以解決NP-hard問題。ICLCS能夠適應(yīng)工作負(fù)載的變化，推薦策略根據(jù)環(huán)境進(jìn)行動(dòng)態(tài)變化，提高了效率。然而，ITLCS的選擇過程主要依賴于遺傳算法，強(qiáng)化學(xué)習(xí)只是為其提供了能在更大的搜索空間S求解的方案，并未將基于學(xué)習(xí)的方法深入應(yīng)用到問題的求解過程中。其次，ITLCS使用遺傳算法來消除LCS規(guī)則并生成復(fù)合規(guī)則作為最終的索引策略。但是，很難生成規(guī)則。針對規(guī)則生成難的問題，Sadri等[40]提出了一種基于強(qiáng)化學(xué)習(xí)的索引選擇方法。首先，在沒有專家規(guī)則的情況下，將工作量特征表示為查詢的到達(dá)率，將列特征表示為每列的訪問頻率和選擇性。其次，使用馬爾可夫決策過程模型從查詢、列和輸出一組動(dòng)作的特征中學(xué)習(xí)，這些動(dòng)作表示創(chuàng)建/刪除索引。

然而，計(jì)算機(jī)系統(tǒng)的配置空間對于傳統(tǒng)和自動(dòng)調(diào)整策略具有挑戰(zhàn)性。Welborn等[42]探討了如何使用特定任務(wù)的歸納偏置來增強(qiáng)基于學(xué)習(xí)的索引選擇，特別是通過將這些歸納偏置編碼為更好的動(dòng)作結(jié)構(gòu)。當(dāng)問題根據(jù)排列學(xué)習(xí)重新表述時(shí)，就會(huì)出現(xiàn)索引選擇特定的動(dòng)作表示，并且依靠最近的動(dòng)作來學(xué)習(xí)關(guān)于排列的強(qiáng)化學(xué)習(xí)(reinforcement learning,RL)策略。通過這種方法，構(gòu)建了一個(gè)索引代理，它能夠?qū)崿F(xiàn)改進(jìn)的索引并使用特定于任務(wù)的統(tǒng)計(jì)數(shù)據(jù)驗(yàn)證其行為。與其他方法相比，該代理可以找到在相同延遲水平下最多減少40%的配置，并表示出更直觀的索引行為。

對于NoSQL數(shù)據(jù)庫，Yao等[43]提出了一種新的索引選擇方法。針對不同的工作負(fù)載，選擇不同的索引及其不同的參數(shù)來優(yōu)化數(shù)據(jù)庫性能。該方法構(gòu)建深度強(qiáng)化學(xué)習(xí)模型，為給定的固定工作負(fù)載選擇最佳索引并適應(yīng)不斷變化的工作負(fù)載。實(shí)驗(yàn)結(jié)果表明，深度強(qiáng)化學(xué)習(xí)索引選擇方法(deep reinforcement learning index selection approach,DRLISA)比傳統(tǒng)的單索引結(jié)構(gòu)在不同程度上提高了性能。該方法選擇索引配置比手動(dòng)選擇索引更合理，并且可以應(yīng)對NoSQL數(shù)據(jù)庫智能索引選擇問題。與單一索引結(jié)構(gòu)不同，DRLISA支持在動(dòng)態(tài)工作負(fù)載下選擇索引結(jié)構(gòu)及其參數(shù)。此外，該方法顯示出其強(qiáng)大的可擴(kuò)展性，體現(xiàn)在可以將其他索引添加到索引集中，將動(dòng)作添加到動(dòng)作集中或修改不同情況下的獎(jiǎng)勵(lì)評估函數(shù)作為擴(kuò)展。強(qiáng)大的可擴(kuò)展性DRLISA符合NoSQL數(shù)據(jù)庫的概念。DRLISA可以為NoSQL索引選擇問題帶來新的啟發(fā)。

根據(jù)表2以及對上述典型基于學(xué)習(xí)的方法實(shí)現(xiàn)分析，基于學(xué)習(xí)的方法能夠適應(yīng)工作負(fù)載的變化，并且推薦策略能夠動(dòng)態(tài)變化。然而，基于DRL的索引選擇法通常需要結(jié)合其他算法(如遺傳算法)，并且強(qiáng)依賴于獎(jiǎng)勵(lì)函數(shù)。

3 結(jié)論

綜述了索引推薦相關(guān)技術(shù)，包含2個(gè)階段，第一階段是索引生成技術(shù)，第二階段是索引選擇。索引生成技術(shù)敘述了范圍索引、哈希模型索引、基于學(xué)習(xí)的布隆過濾，索引選擇技術(shù)分別敘述了離線、在線、半自動(dòng)化和基于學(xué)習(xí)的方法。目前已有大量的機(jī)器學(xué)習(xí)算法，可以嘗試將不同的模型運(yùn)用到索引推薦中。下一步的研究方向是考慮多維索引，并且從理論上證明學(xué)習(xí)型索引的正確性。對于動(dòng)態(tài)變化的工作負(fù)載，要求基于學(xué)習(xí)的模型具有很強(qiáng)的泛化能力；DBA工作經(jīng)驗(yàn)是很有價(jià)值的知識，如何學(xué)習(xí)這些知識并進(jìn)行應(yīng)用也是一個(gè)需要解決的問題。