學習型數據庫索引推薦技術綜述

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

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

0 引言

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

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

機器學習可以通過學習歷史數據中的關系，輔助DBA做決策。機器學習技術在許多科學研究領域得到了廣泛的應用[7-9]，機器學習也為數據庫索引優化技術提供了新的可能性，比如傳統的機器學習模型：線性傳回歸[10]、隨機森林[11]、支持向量機[12]和集成學習[13]等，從歷史數據中積累“經驗”，可以提高解決復雜問題的能力。但是傳統的機器學習模型只能描述一個層次的學習過程，而且相對簡單，例如簡單的線性回歸模型難以求解高階參數和連續參數空間[14]，于是深度學習(deep learning,DL)與強化學習(reinforcement learning,RL)被提出，有學者將DL與RL結合，變成深度強化學習(deep reinforcement learning,DRL)，使用DRL模型可以解決NP-hard問題，因為它可以搜索龐大的解空間。人工智能可以使數據庫更加智能化(AI4DB)，使用人工智能去優化數據庫(如代價估計、連接順序選擇、節點調整、索引和視圖推薦等)是目前以及未來的研究熱點。

基于索引推薦的不同階段，本文將其分為索引生成與索引選擇兩部分。索引生成是為了生成滿足數據庫的索引數據結構，而索引選擇是選擇建立索引的方案。本文對索引生成技術和索引選擇技術進行綜述。索引對于提高復雜數據集的搜索和查詢任務效率非常重要，特別是在處理事務負載時，將索引嵌入適當的列可以很大程度上提高處理效率[15]。

傳統數據庫采用通用的索引結構(如：B-Tree)，這種索引結構只能讓搜索數據時的速度有保障，但它沒有利用數據之間的分布以及數據庫中其他信息。此外，數據集越大，索引也就越大，很容易造成空間浪費。因此，需要一種高效的索引技術來支持數據庫的應用。

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

1 索引生成技術

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

表1 索引生成技術相關工作總結

1.1 基于學習的范圍索引

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

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

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

算法1：混合端到端訓練法

輸入：閾值(threshold),階段數組(stages[]),復雜神經網絡(NN_complexity),記錄數據(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，從整個數據集初始化(第1行)開始，它首先訓練頂層節點模型(第2～4行)。基于對這個頂層節點模型的預測，它從下一階段(第5～8行)選擇模型，并添加屬于該模型的所有鍵(第8行)。最后，在混合索引的情況下，如果絕對值的最小/最大誤差高于預定義的閾值(第9～12行)，則通過用B樹替換神經網絡模型來優化索引。

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

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

針對并行數據庫，并行B樹進行范圍分區的數據遷移是一種解決方案，范圍分區和鏈式非聚集副本的結合提供了高可用性，同時保持了可擴展性。Luo等[21]提出了一種利用并行B樹(簡稱Fat-Btree)實現可擴展性的方法，單個Fat-Btree提供了所有處理器單元中主數據和備份數據的訪問路徑，大大減少了故障切換時間。此外，它支持動態負載平衡從而無需進行物理數據遷移，并提高了處理索引的內存空間利用率。

1.2 基于學習的哈希索引

在基于非易失性內存(non-volatile memory,NVM)的索引設計中，基于哈希的結構是最有前途的候選結構之一，因為它可以充分利用NVM的字節可尋址特性來執行具有恒定時間復雜度的查詢操作。哈希映射的索引盡可能避免沖突，因為沖突嚴重影響性能和存儲需求，可以使用基于學習的方案以減少沖突的數量。Kraska等[16]建議將鍵的CDF(cumulative distribution function)近似為散列函數，以將所有鍵均勻地分布在每個散列桶中并減少沖突。基于哈希的連接算法通常包含2個階段：分區階段和分區連接階段。Harris等[22]描述了使用最優多屬性哈希(multi-attribute hash,MAH)索引來降低分區階段(基于哈希連接算法)的平均代價的過程，通過完全消除最常見的連接查詢的分區階段來達到目的，并證明了該技術可以擴展到包括數據的多個副本，每個副本具有不同的MAH索引方案組織，并且這進一步降低了執行hash-join算法的分區階段的平均成本。

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

1.3 基于學習的布隆過濾器

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

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

1.4 基于學習的鍵值對存儲

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

圖2 從性能權衡到數據結構、鍵值存儲豐富的應用示意圖

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

1.5 基于學習的空間索引

傳統的空間索引，例如R-tree、kd-tree、G-tree，無法捕捉底層數據的分布，可以通過基于學習的技術進一步優化查找時間和空間開銷。例如，Wang等[29]提出了一種基于學習的ZM索引，該索引首先將多維地理空間點映射為具有Z排序的一維向量，然后構建神經網絡索引以擬合分布并預測查詢位置。

1.6 基于學習的高維數據索引

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

2 索引選擇技術

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

表2 索引選擇技術相關工作總結

2.1 在線方法

在線方法的有3個步驟：工作負載分析、索引方案選擇、索引方案實現，這3個步驟的循環進行，可以對工作負載的變化做自動調整。Lühring等[34]給出了一個基于“觀察-預測-反應”循環的軟索引自治管理方法，它可以在當前配置上自動根據環境實現索引結構，并在線自動調整框架本身的性能。

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

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

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

根據表2以及對上述典型在線方法實現的分析，優點是在線法可以根據負載變化及時調整索引，也能在一定程度上減輕DBA的負擔。然而，也有明顯的缺點，即沒有充分利用DBA的經驗，而且需要系統持續運行，會長時間占用系統資源。同時，連續調整也具有一定的盲目性。此類方法適應能力為中等。

2.2 離線方法

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

根據表2以及對上述典型離線方法實現的分析，優點是離線法能夠充分利用DBA的反饋。但是，無法處理工作負載的動態變化，并且加重了DBA的負擔。此類方法適應能力低。可以看到，離線方法與在線方法的優缺點相反。

2.3 半自動方法

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

根據表2以及對上述典型半自動方法實現的分析，優點是半自動法可以減輕DBA的負擔以及充分利用DBA的專業知識；缺點為沒有考慮工作方案對整體的影響。此類方法適應能力為中等。

2.4 基于學習的方法

給定一個工作負載，索引選擇的任務是決定創建索引的屬性使處理工作負載的好處最大。通常，由于空間約束和索引維護成本，會給出要創建的索引數量的上限，因此簡單地為所有列創建索引不是一個好的選項。當然，目標是在不需要管理員的情況下，以自動的方式提出適當的索引選擇。

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

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

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

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

然而，計算機系統的配置空間對于傳統和自動調整策略具有挑戰性。Welborn等[42]探討了如何使用特定任務的歸納偏置來增強基于學習的索引選擇，特別是通過將這些歸納偏置編碼為更好的動作結構。當問題根據排列學習重新表述時，就會出現索引選擇特定的動作表示，并且依靠最近的動作來學習關于排列的強化學習(reinforcement learning,RL)策略。通過這種方法，構建了一個索引代理，它能夠實現改進的索引并使用特定于任務的統計數據驗證其行為。與其他方法相比，該代理可以找到在相同延遲水平下最多減少40%的配置，并表示出更直觀的索引行為。

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

根據表2以及對上述典型基于學習的方法實現分析，基于學習的方法能夠適應工作負載的變化，并且推薦策略能夠動態變化。然而，基于DRL的索引選擇法通常需要結合其他算法(如遺傳算法)，并且強依賴于獎勵函數。

3 結論

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