賴思超 吳小瑩 彭煜瑋 彭智勇,2

1（武漢大學計算機學院 武漢 430072）

2（武漢大學大數(shù)據(jù)研究院 武漢 430072）

（sichaolai@whu.edu.cn）

近年來，隨著企業(yè)的業(yè)務數(shù)據(jù)和業(yè)務場景越來越復雜多樣，一個固定的數(shù)據(jù)庫系統(tǒng)配置往往不能再滿足多變的業(yè)務需求，數(shù)據(jù)庫系統(tǒng)的調優(yōu)也變得越來越重要.這個調優(yōu)工作以往通常被交給企業(yè)的數(shù)據(jù)庫管理員（database administrator，DBA）處理.而據(jù)統(tǒng)計，DBA 的薪水支出占企業(yè)數(shù)據(jù)庫系統(tǒng)近1/2 的所有權總成本（total cost of ownership），且DBA 將近1/4 的工作時間用于數(shù)據(jù)庫的調優(yōu)[1]，因此高效的數(shù)據(jù)庫調優(yōu)對企業(yè)的業(yè)務系統(tǒng)性能和運營成本至關重要.其中，數(shù)據(jù)庫物理設計表達了從邏輯數(shù)據(jù)庫到物理數(shù)據(jù)庫的物化過程，涵蓋所有影響存儲介質上物理結構的設計問題，比如表的規(guī)范化、索引、物化視圖、無共享分區(qū)、多維集群等問題，是影響數(shù)據(jù)庫查詢性能的主要因素之一[2].作為數(shù)據(jù)庫物理設計中重要的物理結構，數(shù)據(jù)庫索引記錄了數(shù)據(jù)屬性（被稱為索引的搜索鍵，由一個或多個索引鍵（index key）組成）到數(shù)據(jù)記錄間的映射關系，能幫助數(shù)據(jù)庫快速找到所需的數(shù)據(jù)記錄.合理的數(shù)據(jù)庫索引配置能極大提升數(shù)據(jù)庫的查詢處理效率，是數(shù)據(jù)庫實現(xiàn)高效查詢處理的關鍵[3]，因此索引調優(yōu)是數(shù)據(jù)庫調優(yōu)的重要組成部分.

索引雖然可能提升工作負載的查詢效率，但作為一種物理結構，也會占用磁盤/內存存儲空間，且需適時進行維護，比如在處理數(shù)據(jù)操作語句導致數(shù)據(jù)庫數(shù)據(jù)發(fā)生更新時.過多的索引可能導致磁盤/內存資源的浪費和索引維護代價的提高，抵消其帶來的查詢效率提升效果.因此，索引調優(yōu)的核心內容是：如何選擇一個合適的索引集合，在其存儲空間占用和維護代價可控的情況下，最大化提升工作負載的查詢效率.在學術論文中，這個問題通常也被稱為索引選擇問題（index selection problem，?SP）[4].

?SP 是數(shù)據(jù)庫領域中一個歷久彌新的問題.在學術界，其研究歷史可追溯到操作系統(tǒng)文件的組織和索引機制[4-7].研究者們[8-9]發(fā)現(xiàn)索引可能給數(shù)據(jù)查詢帶來效率提升，也認識到?SP 的難度和挑戰(zhàn).在工業(yè)界實踐中，這個工作早期主要由DBA 參考數(shù)據(jù)庫的調優(yōu)手冊，并結合自身經(jīng)驗，手動完成調優(yōu).但在面對中大型規(guī)模的索引選擇問題時，這種方式變得不太現(xiàn)實，所以主流商業(yè)數(shù)據(jù)庫廠商開發(fā)了相關調優(yōu)工具來輔助DBA 進行調優(yōu)，比如微軟的SQL Server數(shù)據(jù)庫調優(yōu)顧問（database tuning advisor，DTA）[10]、?BM的DB2 設計顧問（DB2 design advisor，DB2Advis）[11-12]以及Oracle 的SQL 訪問顧問（SQL access advisor）[13]等.隨著機器學習技術的發(fā)展和數(shù)據(jù)庫應用場景的拓展，?SP 的相關研究也重新獲得越來越多研究者的關注，比如引入機器學習技術的索引選擇方案[14]、數(shù)據(jù)庫集群/云數(shù)據(jù)庫上的?SP[15-16]等.

根據(jù)索引鍵所包含的屬性數(shù)量是否為1，索引可被分為單列索引和多列索引.而根據(jù)索引的特性，索引也可被分為主索引（primary index）和二級索引（secondary index）（也成為輔助索引）.其中，主索引的索引鍵是唯一的，且數(shù)據(jù)記錄根據(jù)該搜索鍵值的順序進行組織，所以1 個關系表上最多只能有1 個主索引；二級索引記錄各索引鍵值及其對應數(shù)據(jù)記錄的位置，數(shù)據(jù)記錄順序與索引鍵值順序無關，所以1 個關系表上可以有多個二級索引.在一些探索性數(shù)據(jù)分析任務中，一些研究者提出了自適應索引（adaptive indexing）技術[17-19]，即根據(jù)查詢語句自動生成索引結構并進行自適應調整，避開選擇索引的問題，比如數(shù)據(jù)庫分裂（database cracking）[17]、索引自適應合并（adaptive merging）[18]技術.主索引通常在數(shù)據(jù)庫系統(tǒng)部署前的邏輯結構設計階段被確定；而自適應索引技術大多依賴快速的屬性列操作，比如屬性列數(shù)據(jù)的高效移動，故相關研究大多集中在列存數(shù)據(jù)庫背景下，不夠通用.因此本文將綜述范圍聚焦在通用的二級索引調優(yōu)技術上.文獻[2]的綜述范圍為數(shù)據(jù)庫物理設計技術；而文獻[20]則主要對到2010 年為止微軟的數(shù)據(jù)庫物理優(yōu)化工作進行總結；文獻[21]雖然研究的是索引選擇問題，但該文獻僅對部分傳統(tǒng)方法進行描述和實驗的對比分析，沒有對現(xiàn)有研究方法進行系統(tǒng)性總結；且不涉及應用機器學習技術的相關新進展.雖然現(xiàn)有?SP 的研究大多集中在磁盤數(shù)據(jù)庫領域，但其主要研究的仍是邏輯層面上選擇相關屬性組成索引并構建索引配置的問題.文獻[22]也指出內存數(shù)據(jù)庫和磁盤數(shù)據(jù)庫雖在索引結構設計方面存在不同，但在查詢優(yōu)化方面是類似的，而文獻[23]則是關于磁盤數(shù)據(jù)庫的索引選擇相關方法在內存數(shù)據(jù)庫下的應用，故我們認為相關理論方法也適用于內存數(shù)據(jù)庫，并在后文不再作區(qū)分.

?SP 通常被默認為離線（offline）?SP，即工作負載是靜態(tài)的.作為一個組合搜索/優(yōu)化問題，?SP 在理論上被證明是NP 難的[8]，也很難被近似[9].這意味著找不到一個多項式時間復雜度的精確算法對該問題進行求解，所以現(xiàn)有研究大多通過設計不同的近似算法進行求解.

通過對?SP 的特點和現(xiàn)有研究的調研和分析，本文首先對?SP 進行形式化定義，并將現(xiàn)有研究工作的解決方案歸結為一種基于搜索的求解范式（見第1 節(jié)），并隨后依次對該范式內三大部分（或者稱為步驟）的內容和方法分別進行總結、分析和討論（見第2～4 節(jié)）.隨著大數(shù)據(jù)時代的到來，企業(yè)的業(yè)務場景越來越多變，動態(tài)工作負載下的?SP（也被特稱為在線（online）索引選擇問題）所面臨的新挑戰(zhàn)變得越來越突出，本文基于在線反饋控制回路（online feedback control loop）[24]框架對動態(tài)負載下的索引選擇方案進行梳理，并進行討論和對比（見第5 節(jié)）.然后，結合不同時代對索引調優(yōu)的不同需求，對工業(yè)界的數(shù)據(jù)庫索引調優(yōu)工具的發(fā)展和現(xiàn)狀進行介紹（見第6 節(jié)）.最后，對?SP 在靜態(tài)和動態(tài)工作負載下的解決方案進行總結，并對未來的發(fā)展方向進行展望（見第7 節(jié)）.通過對現(xiàn)有研究的歸納、總結和分析，為研究者提供參考和研究思路.

1 索引選擇問題

1.1 問題定義

優(yōu)化器的查詢優(yōu)化目標在于為查詢語句生成合適的物理執(zhí)行計劃，包括確定每個邏輯操作符的物理實現(xiàn)方式（即物理操作符），比如關系表的訪問路徑（access path）、關系表連接操作的物理實現(xiàn)方式、關系表連接操作的順序等.現(xiàn)有數(shù)據(jù)庫管理系統(tǒng)（database management system，DBMS）優(yōu)化器大多采用基于代價的查詢優(yōu)化策略，即通過代價模型估計不同候選物理執(zhí)行計劃的代價，并輸出代價最小的物理執(zhí)行計劃.數(shù)據(jù)庫索引配置影響查詢語句的查詢優(yōu)化結果（即生成的查詢計劃）和查詢執(zhí)行代價.比如，如果查詢語句過濾謂詞的相關屬性上定義了索引，那么該查詢可利用索引掃描操作快速返回關系表上符合過濾謂詞的記錄，避免遍歷該關系表的所有記錄.

?SP 研究的是在特定的約束下，找到能給代表性工作負載（representative workload）帶來最大代價縮減的最優(yōu)索引配置的問題.其中，代表性工作負載可由DBA 設計和給定，比如基準測試工作負載，也可通過輔助工具生成，比如DB2 的查詢巡邏器（patroller）[12]、SQL Server 的跟蹤探查器（profiler）[25]和Oracle 的數(shù)據(jù)庫性能自動監(jiān)控器（automatic database performance monitoring，ADDM）[26].作為一個組合搜索類型的優(yōu)化問題，?SP 的搜索空間是離散的索引配置空間，目標是找到最優(yōu)的索引配置[27].

為了對這個問題進行形式化定義，首先引入一些基本概念.一個大小為d的數(shù)據(jù)庫實例D可以表示為關系表的集合 {T1,T2,…,Td}，一個包含m個屬性的關系表Ti可以表示為Ti={c1,c2,…,cm}，其中ci表示關系表中的一個屬性.數(shù)據(jù)庫工作負載通常指的是由一系列查詢語句組成的集合，一個大小為n的工作負載W可表示為W={q1,q2,…,qn}，其中qi表示工作負載中的一個查詢語句.索引配置指由索引組成的集合，一個大小為k的索引配置I可表示為I={i1,i2,…,ik}，其中ij表示索引集合中的一個索引.約束集指的是索引選擇過程中所需遵循的約束的集合，一個大小為j的約束集即可表示為B={b1,b2,…,bj}，其中bi表示約束條件集中的一個約束.最常見的約束條件包括索引存儲空間約束（索引配置中索引所占用物理存儲空間的限額）和調優(yōu)時間約束（調優(yōu)算法運行時間限額）.cost(W,I) 表示工作負載W在數(shù)據(jù)庫索引配置I下的代價，可通過實際執(zhí)行時間、外部代價模型估計、優(yōu)化器代價估計等方式獲取.綜合現(xiàn)有研究中的不同定義，本文對?SP 進行形式化定義.

定義1.給定一個數(shù)據(jù)庫D={T1,T2,…,Td}、一個代表性工作負載W={q1,q2,…,qn}以及一個約束條件集B={b1,b2,…,bj}，找到一個最優(yōu)索引配置I*，使能在滿足約束條件集B的情況下，最小化工作負載W的代價，即

其中最小化工作負載代價相當于最大化一個索引配置帶來的工作負載代價縮減（相對初始配置），該縮減值也可看成這個索引配置給工作負載帶來的收益，即bene fit(W,I)=cost(W,I)-cost(W,I0)，其中I0表示初始的索引配置，因此?SP 的優(yōu)化目標也可被等價表示為

1.2 研究內容與基于搜索的調優(yōu)范式

從該形式化定義出發(fā)，我們將?SP 的主要研究內容總結為3 點：1）從問題的輸入來說，數(shù)據(jù)庫的模式信息確定了索引的搜索鍵來源，代表性工作負載表達了用戶的查詢需求，需要找到一種有效的方法來生成包含能提高該工作負載預期處理效率的候選索引配置的搜索空間；2）從問題的目標來說，為了界定最優(yōu)的索引配置，需要找到一種合理的方法來評價索引配置的優(yōu)劣、對索引配置進行比較；3）從問題的核心來說，需要找到一種合理的策略能在索引配置搜索空間高效地找到最優(yōu)的索引配置.

這種按照一定策略在索引配置搜索空間中搜索最優(yōu)配置的方式是自然的，因此本文將現(xiàn)有解決方案都歸結為一種基于搜索的調優(yōu)范式，包含索引配置搜索空間的生成、索引配置的評價以及索引配置的枚舉3 個部分（步驟），如圖1 所示.

Fig.1 Search-based index selection framework圖1 基于搜索的索引選擇框架

首先在該范式中，搜索空間生成部分通過分析輸入的代表性工作負載內容，比如查詢語句的特征和當前數(shù)據(jù)庫狀態(tài)，生成候選索引及候選索引配置集合.候選索引配置組成的搜索空間的大小影響著調優(yōu)算法的代價，更大的搜索空間往往意味著更高的調優(yōu)算法代價上限.其次，為了評價候選索引配置的優(yōu)劣，需要對工作負載在各個候選索引配置下的執(zhí)行情況進行評估和判斷，更好的索引配置能給工作負載的執(zhí)行代價帶來更大縮減.圖1 中的評價模塊展示了3 種常見的索引配置評價方式，即基于外部代價模型、基于優(yōu)化器以及基于機器學習模型的方法.現(xiàn)有大部分研究都采用基于優(yōu)化器的評價方法，這種方式利用優(yōu)化器返回特定候選索引配置下的最優(yōu)查詢計劃和代價估計（具體細節(jié)和方法對比參見本文第3 節(jié)）.最后，枚舉和搜索策略確定搜索空間內的配置搜索路徑，一個好的枚舉策略能讓算法更快找到最優(yōu)索引配置.比如在圖2 中，最優(yōu)配置用實心圓表示，在同樣的搜索空間情況下，右下角的搜索路徑直到最后才找到最優(yōu)配置，而右上角的搜索路徑能提前找到最優(yōu)索引配置，不用訪問剩下（虛線所連接部分）的索引配置.

Fig.2 The search for the best index configuration圖2 最優(yōu)索引配置的搜索

圖1 中這3 個部分內部相對獨立，但外部聯(lián)系緊密.搜索空間中的候選索引配置是索引配置枚舉部分的輸入，而索引配置枚舉過程需要對索引配置進行評價以更快地找到最優(yōu)配置.不同的研究方案在這3 個部分的具體設計存在不同，但索引選擇方案的效果和這3 部分的整體設計相關.大多數(shù)研究，比如文獻[3,11]為了減小索引配置搜索空間會盡早對候選索引進行剪枝，提高索引選擇方案的效率.但這種方式可能會錯誤地把一些可能后期被證明有用的索引剔除，因此文獻[23]選擇盡量晚地對候選索引進行剪枝，即不在候選索引配置搜索空間生成過程中剪枝，而在其遞歸的枚舉搜索策略中動態(tài)剪枝，以保證索引調優(yōu)方案的效果.

同時，我們將現(xiàn)有索引選擇方案中的方法與技術也按照該調優(yōu)范式進行整理和總結，如圖3 所示（對應本文第2～4 節(jié)的內容）.

Fig.3 Classification of related ?SP methods圖3 索引選擇問題相關方法分類

1.3 存在的挑戰(zhàn)

本文將?SP 存在的挑戰(zhàn)歸納總結為3 點：

1）從問題性質來說，索引選擇問題這種組合優(yōu)化問題是NP 難的.數(shù)據(jù)庫關系表的每個屬性上都可以建立索引，且在不考慮主索引的情況下，不同索引可任意組合形成不同的索引配置，導致組合型（combinatorial）的索引配置搜索空間.文獻[9]通過假設存在一個能夠準確計算任意索引配置對每個工作負載查詢收益的函數(shù)（即能對任意索引配置進行優(yōu)劣評價），將?SP 簡化為一個純搜索問題，并將該簡化的?SP 規(guī)約為NP 難的稠密k子圖問題，從而證明?SP 肯定也是NP 難的.

2）對于當前數(shù)據(jù)庫和工作負載，如何準確快速地判斷一個索引配置的好壞是?SP 的一大挑戰(zhàn).文獻[9]假設的準確的收益計算函數(shù)通常是不存在的，且現(xiàn)有大部分索引調優(yōu)方案代價的最大來源[28]便是索引配置評價過程.雖然通過記錄工作負載在不同索引配置下的實際執(zhí)行時間能準確地通過數(shù)值來評價索引配置的優(yōu)劣，但實際執(zhí)行的代價太過昂貴.而使用優(yōu)化器對工作負載在不同索引配置下的代價進行估計的方式更為輕量，但存在估計不準的問題[29]，影響索引調優(yōu)方案的效果.因此，實際的索引選擇方案需要包含一個合理的索引配置評價機制，平衡索引配置評價的準確性和代價.

3）索引間相互影響（index interaction）讓最優(yōu)索引配置的搜索變得更復雜[9,30].如果一個查詢，比如SELECTdFROMTWHEREa=1，能通過多個不同的索引完成執(zhí)行，比如i1(a,b)和i2(a,c)，對于這個查詢來說，i1和i2可看成是一種競爭關系（特別是在考慮存儲空間限制和索引維護代價的情況下）；而如果一個查詢，比如SELECTdFROMTWHEREa=1 ANDb=2，可以利用不同索引間的相互影響加速查詢執(zhí)行，比如i3(a)和i4(b)，那對于這個查詢來說，i3和i4可 看成是一種合作關系.這些相互影響一方面讓同一索引配置內的索引收益分配變得困難[9]，另一方面也讓搜索過程變得更加復雜[30].

這些挑戰(zhàn)展示了?SP 的復雜性，同時也吸引著眾多研究者對這個問題的解決方案進行持續(xù)的研究和改進.

2 索引配置搜索空間的生成

2.1 可被索引屬性和可被接受索引

索引配置由索引組成，而索引被搜索鍵定義.索引的搜索鍵可從數(shù)據(jù)庫所有表的屬性中進行選擇，如果考慮多列索引，則可選擇任意表上的若干屬性進行排列組合，形成以多個屬性為搜索鍵的多列索引.這些可能索引的數(shù)量是龐大的.為了降低候選索引數(shù)量，可以利用工作負載信息對索引鍵的屬性搜索范圍進行限制.比如，如果一個屬性未出現(xiàn)在工作負載的查詢語句中，那么在索引的搜索鍵中包含這個屬性將不能給工作負載帶來收益，反而可能導致索引存儲和維護代價的增加，因此可以預先將這些屬性篩除.

現(xiàn)有研究工作常用2 個概念篩選屬性和索引：可被索引屬性（indexable columns）和可被接受索引（admissible indexes）[3,31-32].通常來說，可被索引屬性被定義為對構成索引有益的屬性，比如出現(xiàn)在查詢語句WHERE 子句中的屬性，有些文獻中也稱其為可行屬性（plausible columns）[31].而根據(jù)可被索引屬性生成的、對工作負載執(zhí)行有潛在收益的索引則被稱為可被接受索引.

為了抽取這些相關信息，現(xiàn)有研究中的工作負載分析方法主要分為基于查詢語句的方法和基于查詢計劃的方法.基于查詢語句的方法從查詢語句文本抽取可被索引屬性以生成可被接受索引.比如，抽取查詢語句文本中的SELECT，WHERE，ORDER BY，GROUP BY 子句出現(xiàn)的屬性[3,33-35]，或通過規(guī)則和算法來篩選可被索引屬性，像DB2Advis 的索引掃描智能屬性枚舉（smart column enumeration for index scans，SAFE?S）算法[11].這種方法只使用查詢的文本信息，簡單高效.基于查詢計劃的方法[31,36-37]則通過分析優(yōu)化器生成的查詢計劃來獲取可被索引屬性和可被接受索引.查詢語句經(jīng)過優(yōu)化器的分析和改寫，生成的查詢計劃反映了真實的數(shù)據(jù)查詢需求.比如，查詢計劃中JO?N，AGGREGATE，SORT 算子的相關屬性即可作為可被索引屬性，用于可被接受索引的生成.這種方式需要額外調用優(yōu)化器來生成查詢計劃，但能規(guī)避文本解析的局限性，比如優(yōu)化器的查詢重寫過程可幫助消除空的子查詢，排除干擾屬性.

2.2 候選索引集合

從可被索引屬性生成可被接受索引以作為候選索引的方式是可行的，但重點在于索引搜索鍵構建過程中的組合爆炸問題，即使通過可被索引屬性概念限制搜索鍵的屬性選擇范圍，可被接受索引的數(shù)量仍然很大，難以處理.很多早期研究工作只考慮單列索引[38-39]和/或單個關系表[8,38-41]，雖不能完全避免組合爆炸問題，但在這些假設下，實際可被索引屬性較少，可被接受索引數(shù)量也可控.然而這些假設是不切實際的：一個實際的數(shù)據(jù)庫中不可能只有一個關系表，且多列索引在實際場景中也是十分常見且有效的.

針對這個問題，很多研究利用啟發(fā)式規(guī)則或/和優(yōu)化器進一步對可被接受索引集合進行限制，降低候選索引數(shù)量.比如，AutoAdmin[3]從單個查詢出發(fā)，通過解析器（parser）抽取該查詢的可被索引屬性，生成可被接受索引.然后將這些可被接受索引作為該查詢的候選索引，利用優(yōu)化器和虛擬索引技術[25]（將在3.2 節(jié)進行更詳細的介紹）找到對這個查詢而言最好的索引配置（query-specific-best-index-configuration）.以同樣的步驟遍歷工作負載中所有查詢，將得到的這些單個查詢的最優(yōu)配置（即索引的集合）進行集合并集操作，形成當前工作負載的候選索引集合.此時，單個查詢最優(yōu)配置中的可被索引屬性來自單個查詢，而工作負載候選索引集合中的索引都來自這些最優(yōu)配置，所以該方法有效降低了候選索引數(shù)量.和Auto-Admin 通過解析器抽取可被索引屬性并生成可被接收索引的方式不同，DB2Advis[11]首先在DB2 優(yōu)化器中執(zhí)行SAFE?S 算法，生成每個查詢的有潛力索引（一種基于規(guī)則的索引生成算法，生成的有潛力索引集合是可被接受索引集合的子集）.然后通過虛擬索引技術將這些虛擬索引注入DB2 的模式信息模型，讓優(yōu)化器認為這些索引已被創(chuàng)建并可被用于查詢計劃的生成.最后在DB2 優(yōu)化器的RECOMMEND ?NDEXES模式下為工作負載的所有查詢生成查詢計劃，并只將計劃中被采用的虛擬索引加入候選索引集合，有效地減少了最終候選索引的數(shù)量.

然而這2 種方法在候選索引的初始生成階段只考慮面向單個查詢的最優(yōu)索引（配置），忽略了那些雖對任何一個查詢都不是最優(yōu)索引（配置）但可能對整個工作負載最優(yōu)的索引（配置），導致有益的候選索引的疏漏，特別是在有存儲空間限制或數(shù)據(jù)更新的情況下[20,42]，這種情況在別的物理設計問題中也可能存在，比如數(shù)據(jù)庫分區(qū)設計問題中[43].舉個例子，如果一個工作負載W包含2 個查詢q1,q2，此時有3 個可能索引i1,i2,i3.其中i1給q1,q2帶來的收益分別為60和20，i2給q1,q2帶來的收益分別為30 和70，i3給q1,q2帶來的收益分別為58 和66，如果此時所剩空間只允許創(chuàng)建1 個索引，那么對于工作負載W來說，上述2種方法可能都不會考慮索引i3，因為i3既不是q1又不是q2的最優(yōu)索引，但i3實際上卻是對工作負載W的最優(yōu)索引.針對這種情況，一些研究工作通過索引變換（index transformation）操作對候選索引集合進行調整[36,42,44]，緩解候選索引生成過程中疏漏有益索引的情況.其中的索引變換操作包括合并（merging）、分割（splitting）、約減（reduction）和提升（promotion）.具體來說，合并操作合并2 個候選索引生成1 個新索引，消除這2 個索引的共有屬性以降低存儲代價，并盡量保留原有索引的查詢加速能力，比如索引i1(a,b)和i2(a,c) 可以被合并為im1(a,b,c)或im2(a,c,b).分割操作則分離輸入索引的公有屬性和剩余屬性以形成新索引，比如索引i3(a,b,e)和i4(a,b,c,d)的分割操作輸出為is1(a,b)，is2(c,d)，is3(e).約減操作，有的文獻中也叫前綴（prefixing）操作[36]，通過取一個候選索引的搜索鍵前綴來形成新索引，比如索引i5(a,c,d)可通過約減操作形成索引ir1(a,c)和ir2(a).提升操作指的是把沒有聚集索引（clustered index）和主索引的關系表上的特定索引提升為聚集索引的操作.和主索引一樣，聚集索引所在關系表的數(shù)據(jù)會按照聚集索引搜索鍵值的順序進行組織，但是其搜索鍵不需要是唯一的.提升操作會改變關系表數(shù)據(jù)的存儲順序，進而改變該表上其他索引和該索引的關系，影響該表上的訪問路徑選擇和查詢計劃生成.這些變換操作考慮了索引在DBMS 實際查詢優(yōu)化和執(zhí)行過程的作用以及查詢間、索引間的關系，能從當前候選索引集合出發(fā)，生成更多對工作負載可能有益的候選索引.

2.3 候選索引配置搜索空間

得到候選索引集合S后，如果不考慮存儲空間限制，候選索引配置形成的搜索空間 C可以看成候選索引集合S的冪集（power set），即 C=P(S)=2S；如果考慮存儲空間限制，搜索空間中那些所需存儲空間大于給定限額的索引配置則需要被去除.根據(jù)這種思想，同時結合物理設計配置（比如索引配置和視圖配置）對合并和約減操作的閉包性質，Bruno 等人[44]提出一種形式化表示物理設計配置搜索空間的方法，也可直接被用于只考慮索引的情況.

?SP 的搜索空間規(guī)模往往影響著索引選擇方案的效果.比如在決策支持系統(tǒng)（decision support system，DSS）場景下，數(shù)據(jù)庫中關系表及其屬性的數(shù)量可能很多，導致候選索引數(shù)量也非常多，直接影響著候選索引配置的數(shù)量（即搜索空間的大小），進而影響索引配置評價過程的代價和索引選擇方案的總代價.同時，一個索引選擇方案在不同搜索空間規(guī)模下的表現(xiàn)也是該方案可伸縮性的重要指標.

我們認為，可以通過各種手段在保證質量的情況下盡量縮減搜索空間，比如通過可被索引屬性、可被接受索引這樣的概念或自定義規(guī)則來排除一些候選索引.還可以根據(jù)每個查詢在整個工作負載中的代價占比情況，比如在候選索引生成過程中只考慮工作負載中最昂貴的k個查詢[12]或一些工作負載壓縮方法（將在2.4 節(jié)進行詳細介紹），通過減少工作負載中的查詢數(shù)量來降低候選索引數(shù)量.此外，還可以選擇直接對搜索空間進行剪枝，比如利用存儲空間約束條件將所需存儲空間大于指定閾值的索引配置從搜索空間中刪除；或通過高效的枚舉算法降低搜索空間規(guī)模的影響，比如，AutoAdmin[3]中的迭代式枚舉算法通過啟發(fā)式規(guī)則來避免對整個搜索空間的遍歷，以實現(xiàn)對搜索空間的高效搜索.

2.4 工作負載的壓縮

索引選擇方案的復雜性隨工作負載大小的增長而呈二次方增長[45]，所以在工作負載驅動的問題中，可通過工作負載壓縮（也稱為摘要[32]）等預處理操作，減少工作負載中的查詢數(shù)量，提高搜索空間的生成效率，縮減搜索空間大小.

數(shù)據(jù)庫工作負載壓縮方案的常用評價指標[32,45-47]有3 個，即壓縮結果的覆蓋性、代表性和壓縮方案的效率.其中，覆蓋性保證壓縮后的工作負載可覆蓋原工作負載中大部分重要查詢，代表性保證壓縮后工作負載應盡量保留原工作負載的特征（比如查詢分布），這2 個指標要求壓縮過程要保證壓縮質量.而壓縮方案的效率則影響壓縮方案的可用性，保證壓縮帶來的收益顯著超過壓縮所需的代價（比如壓縮執(zhí)行所需的時間和資源等）.一個合理的壓縮方案需要根據(jù)任務的具體要求在這3 個指標上找到平衡.數(shù)據(jù)庫工作負載壓縮最直接的一種方法，即不考慮查詢順序，將工作負載表示為查詢和查詢頻率的對，減少索引選擇方案要處理的查詢對象.另外一種直接的方法則用查詢模板[15,48-51]對工作負載進行壓縮.這2 種直接的方法只使用查詢語句的文本信息，得到工作負載后可快速完成壓縮，壓縮結果的覆蓋性和代表性相對可控.也有研究利用查詢計劃的模板[52-53]來提高索引選擇方案的效率.雖然這種直接模板化的方式能加快搜索空間生成的速度，但不能減小索引配置的搜索空間，因為查詢所包含的可被索引屬性并沒有減少.同時，在索引配置評價過程中，查詢模板也不能代替查詢實例，因為查詢模板不能夠直接在DBMS 中執(zhí)行，且查詢模板的一個實例通常并不能代表該模板下的所有查詢實例.比如，當屬性數(shù)據(jù)不是均勻分布的時候（實際中的大部分情況），同一索引配置對同一查詢模板下不同查詢實例的收益是存在差異的，即一個索引配置對一個查詢實例的收益不能夠代表這個索引配置對該模板下所有查詢實例的收益情況.此外，實際場景中的查詢是多樣的，工作負載包含的查詢模板數(shù)量可能仍然很多[32]，導致壓縮效率沒有保障.

為了進一步提高工作負載壓縮方案的效率，Chaudhuri 等人[46]系統(tǒng)性地提出了一種數(shù)據(jù)庫工作負載壓縮的思路：其目標是找到一種工作負載壓縮算法，使解決方案在輸入變?yōu)閴嚎s后工作負載時仍能得到質量相近的結果（隱含了對壓縮結果的覆蓋性和代表性的要求），提高工作負載驅動任務（比如索引選擇問題）解決方案的效率.其中心思想是將工作負載的壓縮看成是一個查詢聚類問題，在解決方案質量損失最大允許范圍內，盡量降低壓縮后工作負載中的查詢數(shù)量.該方法需要事先對聚類過程中的距離函數(shù)進行定義，但有些場景下的距離函數(shù)并不容易被定義.針對這個情況，Chaudhuri 等人[54]又設計了一種適應大部分場景的通用工作負載分析語言WAL.WAL 在SQL 語法基礎上設計并集成了2 種新原語（primitives）：支配（dominance）和表示（representation），通過這種聲明式語言的形式可定制地、輕量化地篩除工作負載中的冗余查詢，支撐工作負載的摘要和壓縮任務.比如，支配原語可用來描述查詢語句謂詞集合間的子集關系，通過過濾工作負載中那些被支配的查詢語句，對工作負載進行壓縮.但這種通用壓縮方法[46,54-55]沒有考慮到索引選擇問題的特殊性，壓縮后可能還會保留很多發(fā)生頻率高但索引收益上限低的查詢.針對這個問題，Siddiqui 等人[32]提出了一種在索引選擇背景下的查詢表征方法，用來計算索引感知（indexing-aware）的查詢相似性，實現(xiàn)工作負載的壓縮，提高索引選擇方案的效率.

2.5 小 結

本節(jié)內容聚焦如何生成候選索引和候選索引配置.現(xiàn)有研究方法通常通過啟發(fā)式規(guī)則從工作負載查詢文本或從查詢計劃抽取相關的屬性和索引（比如可被索引屬性和可被接受索引），形成候選索引和候選索引集合.其中基于查詢語句的方法簡單高效，而基于查詢計劃的方法能生成更為準確的候選索引集合，但這種方式需要調用優(yōu)化器生成查詢計劃，代價相對更大.為了提高候選索引配置生成的效率，還有很多研究通過壓縮工作負載來減少需要處理的查詢數(shù)量，基于模板的方法能加快搜索空間生成的速度，但不能縮減索引配置的搜索空間，同時在查詢模板數(shù)量很多的實際場景下不能保證壓縮效率.基于聚類的方法和把壓縮操作抽象為SQL 原語的方法則能進一步提高工作負載的壓縮效率.我們認為，未來的查詢相似性度量和工作負載壓縮機制的設計應關注文獻[32]中的索引感知性質，使得到的查詢聚類結果更具有針對性，減少因工作負載壓縮引起的索引選擇方案效果的損失.

3 索引配置的評價

索引配置的評價是索引選擇方案的核心內容之一.其思路一般可分為2 種，其中最自然、使用最多的一種思路是用數(shù)值記錄索引配置對工作負載代價的影響程度.比如，用工作負載在特定配置下的代價來評價該配置，工作負載在一個索引配置下的代價越低，則代表該索引配置對當前工作負載越好.另一種思路則通過構建索引配置間的偏序關系來評價索引配置的優(yōu)劣.如果一個配置比其他配置都好，那么這個配置顯然也是最優(yōu)配置.在前一種思路中，最直接的方法就是將工作負載的實際執(zhí)行時間作為工作負載代價，但這種方式太過昂貴.特別是在處理聯(lián)機分析處理（online analysis process，OLAP）型工作負載情況下，一個長查詢的執(zhí)行可能耗費幾個小時，且索引選擇方案需要在多個不同的索引配置下對相同的工作負載進行代價估計.因此，大多數(shù)研究選擇用優(yōu)化器估計工作負載在特定配置下的代價.但優(yōu)化器的代價估計是不準確的，可能導致次優(yōu)的索引配置推薦，甚至數(shù)據(jù)庫性能的退化[29].如何設計一種高效且相對準確的代價估計方法是這種思路的關鍵.而在后一種思路中，由于不需要確定工作負載代價的具體數(shù)值，索引配置間準確偏序關系的構建成為該思路的重點，比如通過機器學習建立配置偏序關系的模型，能快速且準確地在當前工作負載情況下對索引配置進行比較，得到最優(yōu)索引配置.本節(jié)首先對大多數(shù)研究所采用的第1 種思路的代價估計方法進行歸納和總結，然后對使用機器學習進行索引配置比較的第2 種思路進行分析介紹，最后對索引的更新維護代價問題進行論述.

3.1 外部代價模型與優(yōu)化器估計

很多早期研究采用輕量的外部代價模型[38,41,56-57]估計特定索引配置下工作負載代價以評價索引配置，但這些代價模型通常會對工作負載和數(shù)據(jù)庫狀態(tài)做出諸多假設，比如數(shù)據(jù)庫中只有一個表；各屬性值的數(shù)據(jù)分布是獨立的，實用性不強.而且這種方式讓索引選擇過程和優(yōu)化器脫節(jié)[3,31]，即使外部代價模型更準確，得到的索引配置仍可能不會給查詢執(zhí)行帶來預期收益.因為在不改動優(yōu)化器的情況下，優(yōu)化器仍按照其內部代價模型生成計劃，所以可能并不會采用被推薦的索引.如果想要外部代價模型產(chǎn)生較好效果，在保證外部代價模型準確的基礎上，還需要侵入式地對DBMS 優(yōu)化器的查詢計劃生成模塊進行修改，確保優(yōu)化器能采用被推薦的相關索引.但這也意味著更高的工程實現(xiàn)難度和更低的可遷移性（portability）.針對這種情況，F(xiàn)inkelstein 等人[31]在研究數(shù)據(jù)庫物理設計問題時，提出直接使用優(yōu)化器內部代價模型來估計工作負載代價的思想和使用優(yōu)化器實現(xiàn)同步（insync），也讓索引選擇過程能契合目標數(shù)據(jù)庫優(yōu)化器特性.大部分后續(xù)相關研究[3,9,11,23,44,52,58-59]都采用優(yōu)化器對工作負載代價進行估計，大多數(shù)DBMS 也實現(xiàn)并暴露了相關接口，比如PostgreSQL，SQL Server，DB2 中的EXPLA?N 命令.

3.2 what-if 優(yōu)化與虛擬索引機制

雖然優(yōu)化器可對特定索引配置下的工作負載代價進行估計，但是一些索引配置調整操作的代價是昂貴的，比如索引創(chuàng)建操作，所以先實際調整當前索引配置到目標索引配置再進行代價估計的方式是低效的.現(xiàn)有研究通常采用what-if 優(yōu)化（what-if optimization）技術[25]對物理設計的調整進行模擬，讓優(yōu)化器支持在虛擬的物理設計配置下估計工作負載代價，避免對配置進行實際調整.在?SP 中即意味著對索引結構的模擬，其可行性依賴優(yōu)化器的查詢優(yōu)化機制：優(yōu)化器在生成查詢計劃過程中不需要使用索引的實際數(shù)據(jù)（在查詢執(zhí)行過程才需要使用索引的實際數(shù)據(jù)），只需要使用索引的源信息，比如索引鍵的信息、索引鍵所在表的信息、索引大小的信息、是否是聚集索引等.根據(jù)這種思想，Chaudhuri 等人[25]在SQL Server 7.0 的虛擬配置模擬模塊實現(xiàn)了虛擬索引機制.別的商業(yè)數(shù)據(jù)庫一般也實現(xiàn)了類似的虛擬索引機制，比如在DB2 的RECOMMEND ?NDEX 模式[11]、Oracle 的SQL 訪問路徑顧問模塊[13]中.它們實現(xiàn)的基本功能為虛擬索引的管理，比如創(chuàng)建、刪除及考慮虛擬索引的查詢計劃生成功能.

一個值得關注的重要問題是what-if 優(yōu)化過程的代價問題.雖然相比實際執(zhí)行，what-if 優(yōu)化技術確實能大幅度降低調優(yōu)代價，但what-if 優(yōu)化過程中對優(yōu)化器的調用，也被稱為what-if 調用，仍占據(jù)索引調優(yōu)方案大約90%的調優(yōu)時間[28].what-if 調用次數(shù)主要受需要進行what-if 優(yōu)化的候選索引配置數(shù)量的影響.關于如何減少what-if 調用的問題，F(xiàn)inkelstein 等人[31]提出了原子配置（atomic configurations）概念，限制每個表上最多只有1 個索引，且僅在對工作負載在原子配置下的代價估計時進行what-if 優(yōu)化，并利用原子配置下的代價信息推導非原子配置下的代價，減少配置評價過程中的what-if 調用.AutoAdmin[3]考慮到優(yōu)化器特點，對原子配置概念進行發(fā)展，提出單連接原子配置（single-join atomic configurations）概念，限制每個表上最多同時使用2 個索引的交集以及面對多表查詢時最多只考慮2 個表上的索引，進一步降低了需要進行what-if 優(yōu)化的配置數(shù)量.

除了通過原子配置概念對需要進行what-if 優(yōu)化的索引配置進行篩選，還可以利用索引選擇方案的巧妙設計減少what-if 調用.比如，DB2Advisor[11]的候選索引生成策略能在1 次對DB2 的優(yōu)化器調用中同時進行單個查詢的候選索引生成工作和該查詢的最優(yōu)索引配置選擇工作，使后續(xù)步驟不再需要調用優(yōu)化器對該查詢進行查詢優(yōu)化，降低what-if 調用次數(shù).因為對這個查詢來說，優(yōu)化器認為的最優(yōu)索引配置已被優(yōu)化器選中并用于查詢計劃的生成，或通過緩存what-if 調用結果[58,60]來避免對優(yōu)化器的冗余調用.

還有研究工作[12,61]通過減少工作負載中所需處理查詢數(shù)量來減少需要進行what-if 優(yōu)化的配置數(shù)量，比如工作負載壓縮，或利用索引配置間關系動態(tài)降低what-if 優(yōu)化所需考慮查詢的數(shù)量[23,44]，比如，如果1 個待評估索引配置和1 個已被評價索引配置只差1 個索引，那么只需重新估計和該索引相關的查詢在待評價索引配置下的代價，即可通過相關查詢在不同配置間的差值推導出工作負載在待評價索引配置下的代價.

3.3 基于機器學習的配置評價

隨著機器學習技術的發(fā)展，越來越多數(shù)據(jù)庫優(yōu)化問題的解決方案引入了機器學習技術[62].本節(jié)將分析討論使用機器學習評價索引配置的思路和方法.

3.3.1 基于機器學習的代價估計

基于優(yōu)化器的代價估計可能存在不準確的情況，影響索引選擇方案的效果[29].現(xiàn)有DBMS 的代價估計通常由優(yōu)化器在計劃生成階段完成，即通過表、（子）表達式的基數(shù)估計和代價模型計算查詢的代價.其錯誤可以分為基數(shù)估計引入的錯誤和代價模型引入的錯誤，且相比于代價模型，基數(shù)估計對代價估計的影響更大[63]，所以很多研究致力于研究準確估計各計劃節(jié)點基數(shù)的方法.基于摘要的傳統(tǒng)基數(shù)估計方法，比如直方圖法、采樣法可能經(jīng)常會出現(xiàn)不準確的情況，特別是在數(shù)據(jù)庫表或屬性列間存在著關聯(lián)關系時[64]，而機器學習強大的數(shù)據(jù)抽象能力能捕獲查詢和數(shù)據(jù)的特征，幫助更準確地估計基數(shù).

一種經(jīng)典的基于機器學習的基數(shù)估計方法是Kipf 等人[65]提出的MSCN 模型.該模型會抽取工作負載查詢中所涉及到的表信息、查詢的連接信息以及謂詞條件信息，并通過集合卷積（set convolution）操作整合這3 種特征信息以捕捉對基數(shù)估計存在影響的特征.整合后的特征向量被輸入到一個2 層的全連接神經(jīng)網(wǎng)絡，輸出即為估計的基數(shù)值.而Sun 等人[66]觀察到即使通過機器學習模型獲得了較準確的基數(shù)估計結果，但還是可能由于代價模型的錯誤而得到不準確的代價估計結果，所以提出了一個端到端的、能同時對基數(shù)和代價進行估計的學習模型.該模型通過收集查詢的物理計劃、計劃代價以及計劃基數(shù)，對影響查詢代價的4 個主要因素，即物理計劃操作信息、謂詞信息、源信息以及數(shù)據(jù)信息進行特征編碼.然后輸入到一個樹形模型進行多任務訓練，得到每個計劃節(jié)點的穩(wěn)定表征.最后輸入到一個2 層全連接神經(jīng)網(wǎng)絡對（子）查詢的基數(shù)和代價進行估計.

現(xiàn)在也有索引選擇方案使用基于機器學習的代價估計模型.比如，Zhou 等人[51]通過收集數(shù)據(jù)庫內核中能捕獲到的查詢的?/O 和CPU 代價作為特征，以查詢的歷史代價值為標簽，訓練一個深度回歸模型來預測查詢代價.Siddiqui 等人[67]以查詢模板為單位，收集該模板下所有實例的模板參數(shù)選擇率和索引配置信息，并進行向量化.然后訓練一個樹形機器學習模型對查詢在特定索引配置下的代價進行預測.Gao等人[68]通過結合查詢計劃信息和相關索引信息，訓練一個圖卷積神經(jīng)網(wǎng)絡來對查詢代價進行估計，并用于索引調優(yōu).在類似的視圖選擇問題上，Yuan 等人[69]提出一種結合計劃、關聯(lián)表信息的查詢表征方法，并設計了一種Wide-Deep 模型預測查詢在特定視圖配置下的代價.該模型的核心思想是用一個寬的線性模型來編碼數(shù)值型特征，用一個深的神經(jīng)網(wǎng)絡模型來編碼文本型特征.結合這些特征編碼作為模型的輸入進行訓練，得到可預測查詢代價的機器學習模型.

基于機器學習的代價估計在索引選擇方案中的應用仍不多.我們認為，可能的原因包含2 個方面：一方面，基數(shù)估計/代價估計的模型準確性和穩(wěn)定性問題使得相關研究仍屬于早期起步階段，相關研究雖然探索了用機器學習方法預測查詢代價，但仍沒有文獻對其中的代價估計模型進行詳細的對比分析；另一方面，和外部代價模型一樣，為了得到預期收益，仍避免不了對數(shù)據(jù)庫優(yōu)化器代碼進行侵入式修改.但我們認為，為了獲得更好的索引調優(yōu)結果，這仍是一個具有前景的方向.

3.3.2 基于機器學習的索引配置比較

?SP 的目標是找到最優(yōu)索引配置，實際上并不關心在每個候選索引配置下工作負載代價的具體數(shù)值，只關心能最小化工作負載代價的索引配置，所以通過索引配置的偏序關系來評價索引配置的思路也是可行的.據(jù)我們所知，該思路現(xiàn)有研究只有Ding 等人[29]的工作（本文稱為Ding?dxAdvis）.該工作指出優(yōu)化器估計不準導致索引調優(yōu)效果變差的問題，并用分類模型實現(xiàn)索引配置的比較和評價.具體來說，文獻[29]從生成的查詢計劃中抽取物理操作符（比如索引掃描、表掃描、哈希連接等）信息作為特征，并附加這些操作的執(zhí)行模式信息（以行還是批為執(zhí)行單位）和并行信息（是否是并行執(zhí)行），形成〈Physical Operator〉_〈Execution Mode〉_〈Parallelism〉形式的物理操作符標識鍵，比如Scan_Batch_Parallel，HashJoin_Row_Serial.這個標識鍵會被賦予特定數(shù)值，用來評估這個物理操作符的計劃完成量，比如當前操作在計劃中的預期代價或計劃結構信息加權的行數(shù)總和.通過整合查詢計劃中所有操作的特征即可形成一個計劃的向量表示.對于2 個不同的索引配置下產(chǎn)生的不同查詢計劃，將它們的向量表示進行差值整合作為分類器的輸入，分類器的輸出為從一個計劃變?yōu)榱硪粋€計劃后查詢性能變化類別的預測結果，比如性能是提升了還是退化了，亦或是不確定（不確定時使用優(yōu)化器估計進行比較），通過對比不同索引配置下所產(chǎn)生計劃的性能來對索引配置進行比較.最后在索引配置搜索過程中，只保留那些能帶來非退化性能的索引配置，并不斷更新已搜索到的最優(yōu)索引配置.

3.4 索引的更新維護代價

當工作負載中包含插入、刪除以及更新類型的語句時，數(shù)據(jù)庫相關表的數(shù)據(jù)會更新，此時定義在這些表上的索引也需要進行更新維護.在OLAP 場景下，業(yè)務數(shù)據(jù)變化頻率低，工作負載的執(zhí)行時間較長，所以經(jīng)常選擇忽略索引的維護代價.這也是大部分?SP的研究背景為數(shù)據(jù)倉庫和OLAP 場景的原因之一.而在聯(lián)機事務處理（online transaction processing，OLTP）場景下，工作負載需要頻繁且快速地對數(shù)據(jù)庫數(shù)據(jù)進行讀取、寫入和更新，如果一個索引被定義在需要頻繁更新的表上，那么這個索引可能需要經(jīng)常進行維護，產(chǎn)生大量維護代價，也不能再被忽略.所以需要設計策略以減少索引的維護代價，比如，通過存儲空間約束[52,70]或索引合并[42]等手段盡量減少索引配置中的索引數(shù)量，降低維護發(fā)生的概率.

對于索引更新維護代價的估計，現(xiàn)有研究大多先會對查詢語句進行分割，形成語句的SELECT 部分和UPDATE 部分[3,36,59,61]，并根據(jù)UPDATE 部分計算索引的更新維護代價.其中，SELECT 部分和普通的SELECT 語句類似，UPDATE 部分（也稱為更新殼，update shell[30,36,44]）則對SELECT 部分選中的記錄進行更新操作.前期的一些索引選擇方案[4,7,38]會對各類型語句的概率進行建模，并建立外部模型來計算更新維護代價[39]，但這些方法在數(shù)據(jù)庫、工作負載等方面做出諸多假設，比如只考慮1 個表[7,38].同時索引的更新代價還與查詢執(zhí)行機制[51]、索引配置中其他索引有關[30]，讓索引更新代價的準確估計變得更難.針對這個情況，Zhou 等人[51]以索引更新操作的?/O 代價、CPU 代價和數(shù)據(jù)查找代價作為輸入特征，以查詢處理代價作為輸出，訓練一個深度回歸模型來學習索引更新操作代價中?/O 代價和CPU 代價間的比例關系以及各輸入的代價特征和查詢處理代價之間的關系，對更新代價進行考慮.

3.5 小 結

本節(jié)聚焦如何高效準確地評價索引配置的優(yōu)劣.早期基于外部代價模型的方式雖然效率高，但為了模型可用性做出諸多假設，且和優(yōu)化器脫節(jié)，所以已很少在索引選擇方案被直接使用.現(xiàn)有主流方法采用優(yōu)化器和what-if 優(yōu)化機制來估計工作負載在特定索引配置下的代價，實現(xiàn)對不同的索引配置的比較.這種方式和優(yōu)化器同步，但不準確的優(yōu)化器代價估計可能導致索引選擇方案效果出現(xiàn)偏差，甚至造成數(shù)據(jù)庫系統(tǒng)性能的退化.同時，為了保證索引選擇方案的效率，還需要注意what-if 優(yōu)化的代價問題，可以通過原子配置概念、what-if 調用結果的緩存與復用或通過減少工作負載中所需處理查詢數(shù)量來減少需要what-if 優(yōu)化的配置數(shù)量（這些方法可結合使用）.而隨著機器學習技術的發(fā)展，越來越多的研究者開始研究用機器學習技術提升索引配置評價的準確性和效率，雖然該部分方法在代價估計的平均誤差低于傳統(tǒng)優(yōu)化器，但要達到可用，仍需關注機器學習模型的訓練（包括更新）代價和穩(wěn)定性問題，并對數(shù)據(jù)庫內核中優(yōu)化器部分代碼進行修改.

4 索引配置的枚舉與搜索

如2.3 節(jié)所述，雖然利用啟發(fā)式規(guī)則可以縮減索引配置搜索空間，但仍不能改變該搜索問題的NP 難屬性，且索引配置評價過程的代價也不可忽略，因此通過暴力枚舉、評估、比較所有候選索引配置來找到最優(yōu)配置的精確算法是不切實際的，需要設計一種精巧的枚舉或搜索算法，犧牲一定的精度和確定性，保證代價相對可控的情況下，更快地找到“最優(yōu)”配置.針對這個問題，本文將當前范式下的枚舉/搜索策略總結為4 種：自底向上（bottom-up）的枚舉策略、自頂向下（top-down）的枚舉策略、基于整數(shù)規(guī)劃（integer programming，?P）的隱枚舉策略和基于強化學習（reinforcement learning，RL）的搜索策略.

4.1 索引間的相互影響

雖然在不考慮主索引和存儲空間約束的情況下，一個索引配置可包含任意多個不同的索引，但是索引間不是完全獨立的，如果存在正向或負向相互影響的索引出現(xiàn)在同一索引配置中，會產(chǎn)生相互影響[30].這種相互影響與工作負載中查詢、索引搜索鍵及優(yōu)化器查詢優(yōu)化機制相關，影響索引調優(yōu)方案的效果.

現(xiàn)有工作負載驅動的索引選擇方案隱式地[3,11,23,36,39]或顯式地[9,30,71]在索引推薦過程中考慮索引間的相互影響.隱式的方法通常與枚舉/搜索策略的設計相關，而顯式的方法則直接對索引間的相互影響進行量化評估.比如，Schnaitter 等人[30]提出索引間交互度（degree of interaction）概念來衡量索引間的相互影響.具體來說，交互度衡量的是一個索引在另一個索引加入索引配置前后工作負載代價的變化幅度，交互度大則意味著索引之間關聯(lián)緊密.Bruno 等人[71]則提出有用度（usefulness）概念來衡量索引間的相互影響，并用于索引收益的計算.其核心思想在于比對索引搜索鍵間的包含、前綴等關系.比如，如果索引i1搜索鍵中不包含索引i2搜索鍵中任一屬性，那么索引i1完全不能實現(xiàn)索引i2在關系表訪問加速上的功能；而如果索引i2搜索鍵就是索引i1搜索鍵的前綴，索引i1則完全可以被用來替代索引i2來完成關系表訪問加速的功能，雖然替代后可能導致更高的索引訪問代價和索引更新代價.

4.2 自底向上的枚舉策略

自底向上的枚舉策略從空的或當前索引配置出發(fā)，逐漸向這個配置依照一定策略加入新索引、形成新配置，直到達到設定的終止條件，比如任意新索引的加入都會導致違反存儲空間約束條件停止.

AutoAdmin[3]提出一種自底向上的枚舉方法greedy(m,k).該算法首先暴力遍歷所有由m個索引組成的索引配置（m≤k），隱式地考慮存在重要相互影響的索引，讓那些有強正向相互影響的索引能提前被加入索引配置中.然后進入迭代的索引配置擴展階段：迭代每一步找一個能給工作負載代價帶來最大縮減的索引加入索引配置，直到配置中索引數(shù)量達到k時停止.DB2Advisor[11]則提出了一種基于背包問題的?SP 建模：將配置內的索引當成背包里的物品，索引的大小看成物品的重量，索引收益（索引的存在與否帶來的工作負載代價差異）看成物品的價格.這個問題是NP 難的，所以DB2Advisor 設計了一種啟發(fā)式規(guī)則來近似處理，即以每單位存儲收益對搜索空間內的索引進行排序，并依次選取剩余排序最高的索引加入索引配置，直到加入下一個索引會導致違反存儲空間約束時停止.但在這個過程中（特別是索引收益的計算過程），文獻[11]沒有充分考慮索引間的相互影響，導致索引選擇方案效果受到影響.Chaudhuri等人[9]針對這個情況提出了BEN_KNAP 方案，迭代地縮放各索引的收益值范圍，使索引配置內索引的收益值能盡量滿足線性關系（索引配置收益等于配置內所有索引收益之和），實現(xiàn)在考慮索引間相互影響的情況下計算各索引的收益，提升索引調優(yōu)效果.

Extend[23]則提出一種遞歸的索引配置構建策略.該方案不預先對候選索引進行剪枝，防止過早排除可能有用的索引.雖然該方案仍是自底向上擴充索引配置，但和AutoAdmin[3]，DB2Advisor[11]方案不同，該方案第1 步會選擇收益最大的單列索引加入空的初始索引配置，后面的每一步有2 種可能選擇：第1種是從剩下未被選中的單列索引中選擇收益最大的單列索引；第2 種則在從當前索引配置中所有單列索引上擴展一個屬性形成擴展索引，并選擇能帶來最大收益的那個擴展索引.最終選擇這2 種可能選擇中收益更大的那個.該方案在每一步對索引配置的擴展中考慮了索引配置中已有索引的情況，隱式地對索引間的相互影響進行了考慮.

4.3 自頂向下的枚舉策略

與自底向上的枚舉策略相反，自頂向下的枚舉策略首先從一個不考慮約束條件的初始配置出發(fā)，逐漸對索引配置進行變換，直到能滿足約束條件.初始配置的選擇影響后續(xù)配置枚舉的范圍，可能的選擇包括所有可能由索引組成的索引配置[39]、通過啟發(fā)式規(guī)則得到的候選索引組成的索引配置[36,72]等.

Whang[39]提出了一種自頂向下的枚舉策略DROP.該策略從一個包含所有可能索引的初始索引配置出發(fā)，每次挑選k個索引（初始的k設為1），使刪除那k個索引后可以給工作負載代價帶來最大縮減.當每k個索引的刪除不再能給工作負載代價帶來縮減時，給k的值加1（k=k+1），重復上述過程，直到達到終止條件（比如達到設定的最大k值）停止.Bruno 等人[36]則提出了一種Relaxation 枚舉策略.其初始配置為一個不考慮存儲空間約束的最優(yōu)配置，然后開始迭代：首先檢查初始/當前索引配置是否滿足存儲約束條件，并評估這個配置的工作負載代價；然后選擇一個能帶來最小松弛懲罰，即每存儲單位減少帶來的工作負載代價增加的索引變換操作對當前配置進行變換，得到存儲開銷更低但更低效的松弛（relaxed）配置，直到滿足存儲約束條件時停止.

關于自底向上和自頂向下的枚舉策略，結合文獻[21]進行分析：當存儲限額較低時，滿足條件的索引配置中索引數(shù)量通常較少，自底向上的枚舉策略能較快地找到最優(yōu)索引配置；而自頂向下的枚舉策略由于初始配置的大小和索引變換操作的多樣性，需要評價的候選配置數(shù)量相對更多，算法運行時間更長，但調優(yōu)效果一般更好.而如果存儲限額較高，自頂向下的枚舉策略可用更少的迭代次數(shù)和配置評價次數(shù)，更快地使松弛索引配置滿足存儲約束條件，提高效率.

4.4 基于整數(shù)規(guī)劃的隱枚舉策略

如4.2 節(jié)所述，索引選擇問題可以被建模為背包問題.而整數(shù)規(guī)劃也是解決背包問題的經(jīng)典方法之一.這類方法將索引（物品）是否存在于索引配置（背包）中的狀態(tài)建模為0-1 變量，然后通過這些變量表達?SP 的目標和約束條件，得到一個最優(yōu)化問題的數(shù)學模型.其解空間即對應索引配置的搜索空間，其求解過程則對應索引配置的枚舉/搜索，通過檢查一部分的變量組合來找到最優(yōu)解.

比如，Caprara 等人[73]將索引選擇問題看成廣義無容量限制設施定位問題（generalized uncapacitated facility location problem，GUFLP），用0-1 線性規(guī)劃建模，并提出一種基于分支定界法的精確解法和一些基于松弛和啟發(fā)式規(guī)則的近似解法.Papadomanolakis等人[59]則將GUFLP 的建模應用到商業(yè)數(shù)據(jù)庫的實際場景中，消除了GUFLP 中的1 個查詢只能使用1個索引的假設[31,74]，即不支持索引交集技術，并用線性優(yōu)化中的敏感性分析（sensitivity analysis）技術獲取參數(shù)區(qū)間（intervals），分析特定索引是否應該被加入索引配置，使該數(shù)學模型能被更高效地求解.CoPhy[52]方案觀察到?SP 解空間的良好結構，證明了?SP 在結合類似?NUM[58]和C-PQO[28]等快速代價估計技術后仍可被建模為0-1 整數(shù)規(guī)劃問題，提高了求解效率.

對于小規(guī)模的?SP，基于整數(shù)規(guī)劃的方法能夠很快地返回該背包建模的理論最優(yōu)解（即最優(yōu)索引配置）.但隨著問題規(guī)模的增大，整數(shù)規(guī)劃系統(tǒng)中變量的數(shù)目由于組合爆炸而指數(shù)級增加.雖然隨著整數(shù)規(guī)劃研究的持續(xù)發(fā)展，已存在很多優(yōu)化解答器（optimization solver）能對這種較大規(guī)模的整數(shù)規(guī)劃問題進行高效求解，比如Gurobi optimizer[75]，CPLEX optimizer[76]，但其最優(yōu)性保證建立在準確計算每個候選索引的大小和收益值的基礎上，面臨索引間相互影響帶來的挑戰(zhàn)[9].

4.5 基于強化學習的搜索策略

隨著強化學習特別是深度強化學習技術的興起，越來越多強化學習技術被用于數(shù)據(jù)庫優(yōu)化問題，比如DBMS 的參數(shù)調優(yōu)[77-78]、分區(qū)[79]、連接順序選擇[80-82]、視圖的物化選擇[83]、索引選擇[15,49-51,84-88]問題，給優(yōu)化策略提供從錯誤中學習的能力.Schaarschmidt 等人[89]也將數(shù)據(jù)庫優(yōu)化任務抽象為強化學習任務，并提出示教學習（learning from demonstration）和代價模型自展（cost model bootstrapping）2 種可能提升強化學習方案實用性的策略以及一種應對規(guī)模增長的增量學習（incremental learning）方法，為強化學習算法在數(shù)據(jù)庫優(yōu)化任務中的應用提供指導.

從4.2 節(jié)和4.3 節(jié)可以看出，自底向上和自頂向下的枚舉策略依賴啟發(fā)式規(guī)則的設計，但這些啟發(fā)式規(guī)則是固定的，在面對不同的數(shù)據(jù)庫和工作負載時常?？赡軐е洛e失最優(yōu)索引配置，且沒有從錯誤的選擇中進行學習的能力.這意味著這些策略未來遇到相同狀況還是會犯一樣的錯誤.而索引選擇方案這種逐步向索引配置加入合適索引的過程可以看成是一個序列決策問題，利用強化學習理論來進行建模和求解，即通過試錯法（trial-and-error）訓練索引調優(yōu)智能體，使智能體能根據(jù)數(shù)據(jù)庫狀態(tài)和工作負載情況，自動做出索引調優(yōu)決策，調整索引配置.

具體來說，為了將?SP 建模為序列決策問題（該過程也可被稱為強化學習建模），需要將?SP 上下文映射為強化學習任務的基本元素，即環(huán)境（包括獎勵、狀態(tài)）和智能體（包括動作、策略）.最直接的一種強化學習建模就是將?SP 建模為一個情節(jié)性強化學習（episodic reinforcement learning）[90]任 務，將DBMS 作為環(huán)境，將索引選擇策略作為智能體，智能體在每一個情節(jié)（episode）中完成一次完整的索引配置調優(yōu)：對于一個工作負載，智能體通過觀測DBMS，使用策略函數(shù)計算所需采取的動作，比如創(chuàng)建一個特定的索引，然后采取動作對現(xiàn)有（虛擬）索引配置進行變更；DBMS 通過評價新配置的好壞，比如工作負載代價的縮減給智能體一定數(shù)值的獎勵，新配置越好，獎勵值越大.智能體在不斷與環(huán)境的交互過程中更新其策略函數(shù)，以獲得更大的情節(jié)回報（episode return）.其中，可將約束條件用作情節(jié)的終止條件，比如索引數(shù)量限額，也可將約束因素，比如存儲空間約束中的索引存儲空間作為懲罰項，用于調整智能體動作的獎勵值.

比如，Sharma 等人[85]提出一種基于深度強化學習的單列索引推薦方案NoDBA.智能體動作為一個特定索引的創(chuàng)建，其狀態(tài)包含數(shù)據(jù)庫屬性列的選擇率信息和DBMS 現(xiàn)有索引配置信息.獎勵函數(shù)為索引創(chuàng)建后帶來的工作負載代價縮減，其使用交叉熵方法進行訓練.但NoDBA 建立在一些過度簡化的假設上，比如只考慮1 個關系表，且只能推薦單列索引，這使得該方案很難在實際場景中被應用.Licks 等人[91]提出一種基于強化學習的索引選擇方案Smart?X，雖然考慮了多表情況，但也只考慮單列索引的推薦.Lan等人[86]采用一種基于深度Q 網(wǎng)絡[92]（deep Q-network，DQN）的深度強化學習算法的索引推薦方案Lan?dx-Advis，且設計了啟發(fā)式規(guī)則來生成候選索引，縮減動作空間.但這種基于規(guī)則的候選索引生成方法可能誤刪一些實際有益的索引[23]，導致次優(yōu)的推薦結果.Lai 等人[87]把單列和多列索引的推薦融入強化學習建模，并探索了利用基于近端策略優(yōu)化（proximal policy optimization，PPO）的深度強化學習方法實現(xiàn)索引配置的推薦.Wu 等人[88]在考慮what-if 調用次數(shù)的情況下，使用基于蒙特卡羅樹搜索（Monte Carlo tree search，MCTS）的強化學習方法對索引選擇問題進行求解（本文稱該方案為MCTS_?T）.與經(jīng)典的強化學習方法不同，MCTS 是一種決策時規(guī)劃（decision time planning）方法，不會維護一個全局策略函數(shù)，只會維護已知狀態(tài)的局部策略函數(shù).在遇到新狀態(tài)時通過蒙特卡羅試驗得到該狀態(tài)下的動作，并反向更新已知狀態(tài)的策略函數(shù)[90].MCTS_?T 將索引配置自底向上枚舉的過程映射成搜索樹生成的過程，不斷通過動作策略生成新的索引配置，形成搜索樹，最后通過貪婪算法遍歷搜索樹找到最優(yōu)索引配置.

我們認為，基于強化學習的索引選擇方案在序列決策的每一步從當前索引配置出發(fā)，隱式地將索引間相互影響納入了考慮.同時這種逐步擴充索引配置的方式也可看成是一種自底向上的搜索策略.但和傳統(tǒng)自底向上的枚舉策略不同，在基于強化學習的索引選擇方案中，索引配置的每次擴充對應著智能體策略函數(shù)控制的一次動作，不需要重復地枚舉、評估和比較所有可能的擴充索引配置.智能體的策略函數(shù)相當于一個靈活可變的啟發(fā)式規(guī)則，在與DBMS 的交互過程中學習（包括從錯誤中學習），不斷改進.

4.6 方法對比

4.6.1 常用實驗設置與評價指標

除了真實的DBMS 數(shù)據(jù)和工作負載，現(xiàn)有索引選擇方案最常用的公共數(shù)據(jù)庫數(shù)據(jù)和工作負載來源為TPC-H[93]，TPC-DS[94]，JOB[63]，均為決策支持型測試基準，這些基準測試套件中都包含相應的數(shù)據(jù)庫數(shù)據(jù)填充程序和基于模板的查詢生成程序.

索引選擇方案的常用評價指標為推薦索引配置下的工作負載代價和調優(yōu)時間.比如代表性工作負載在特定索引配置下的執(zhí)行時間越低配置越好；或與初始配置下執(zhí)行時間相比的代價縮減（率）越高配置越好；調優(yōu)時間則越低越好.

4.6.2 代表性方法對比

本節(jié)對現(xiàn)有索引選擇問題的代表性方法進行整體的分析對比.DROP[39]作為早期的代表性方法，設計了外部代價模型評估工作負載代價.但DROP 對?SP 做出了一些簡化假設，比如，為了讓文獻[39]提出的代價模型可用，假設查詢語句只包含簡單的等值謂詞條件，且該方法沒有考慮工作負載的特征，將數(shù)據(jù)庫中所有可能的索引都作為候選索引，使得該方案的時間復雜度很高.

AutoAdmin[3]和DB2Advisor[11]均基于規(guī)則和優(yōu)化器生成搜索空間，但是它們對規(guī)則和優(yōu)化器的使用方法不同.AutoAdmin 通過啟發(fā)式規(guī)則迭代選擇每個查詢的最優(yōu)索引配置，然后合并這些查詢的最優(yōu)索引配置作為工作負載的候選索引集合，并以相同的啟發(fā)式規(guī)則選擇整個工作負載的最優(yōu)索引配置；而DB2Advisor 針對每個查詢調用1 次DB2 優(yōu)化器，同時完成候選索引的生成（SAEF?S 算法）和選擇（基于虛擬索引注入和優(yōu)化器計劃生成機制）.此外，AutoAdmin還利用原子配置概念和代價推導規(guī)則減少優(yōu)化器的what-if 調用，其greedy(m,k) 算法先確定一個由m個索引組成的最優(yōu)種子配置再根據(jù)當前配置逐步加入一個最佳新索引的做法也隱式地將索引間相互影響考慮在內.而DB2Advisor 在其枚舉階段沒有進行whatif 調用，導致枚舉過程中不能考慮到索引間的相互影響，只能通過設計一個額外的擾動階段，將枚舉得到的索引配置進行索引隨機替換，有限地考慮索引間的相互影響.

Ding?dxAdvis[29]和AutoAdmin[3]的主要差別在于前者在索引配置評價階段使用了基于分類的機器學習模型對索引配置進行比較.BEN_KNAP[9]針對索引選擇問題背包建模中索引收益計算通常沒有考慮索引間相互影響的問題（比如DB2Advisor[11]中），提出了一種顯式根據(jù)索引間相互影響對配置內的各索引的收益進行分配/推導的機制，提升索引選擇方案效果.該索引收益分配機制可以和各種搜索空間生成方法兼容，所以文獻[9]沒有限定搜索空間的生成方法（實驗部分使用的是AutoAdmin[3]的生成方法）.

Extend[23]遞歸式的索引配置構建方法不預先確定一個固定的索引配置搜索空間，而在每一步根據(jù)現(xiàn)有配置和規(guī)則確定一個動態(tài)的單步搜索空間.通過what-if 優(yōu)化和最大每單位存儲代價縮減確定索引配置的擴充動作，隱式地考慮現(xiàn)有索引和新索引間的相互影響，并在索引配置占用存儲達到限額后停止.

Relaxation[36]是當前經(jīng)典的自頂向下索引選擇方案.首先在不考慮存儲空間約束情況下，通過優(yōu)化器分析工作負載中每個查詢的索引請求，并通過規(guī)則生成該查詢的最優(yōu)索引配置.然后對這些最優(yōu)索引配置進行并集操作，形成工作負載的候選索引集合.最后通過啟發(fā)式規(guī)則選擇集合中一個索引配置進行松弛如刪除特定索引或2.2 節(jié)所提到的合并、約簡等那些能降低索引配置空間占用的索引變換操作，并迭代更新最優(yōu)配置為滿足存儲空間約束且代價最低的松弛配置，直到達到調優(yōu)時間限額后停止.文獻[36]的方法只對被變換索引的相關查詢進行代價的重新估計，并設計了一種根據(jù)現(xiàn)有配置查詢計劃及其代價推導松弛配置下代價上界的方法，減少了what-if調用次數(shù).

CoPhy[52]是現(xiàn)有基于整數(shù)規(guī)劃枚舉方案中最好的方案.其搜索空間是由變量及約束條件構成的解空間，只用簡單的規(guī)則進行剪枝，并交由整數(shù)規(guī)劃解答器進行可行解的高效枚舉.其配置評價過程使用?NUM[58]中的代價推導方法減少what-if 調用，并支持在該規(guī)劃系統(tǒng)中處理那些能改寫為線性不等式的軟性約束（soft constraint）.同時，文獻[52]的方案可以隨整數(shù)規(guī)劃解答器求解而自然結束，也可以在可行解質量足夠高的情況下提前結束求解，該決策可自動或引入DBA 判斷，減少求解時間，這得益于現(xiàn)有大多數(shù)解答器的性質：求解效率較高且能夠在任意時間點上判斷出當前探索到的可行解和最優(yōu)解之間的距離.

NoDBA[85]，Lan?dxAdvis[86]，MCTS_?T[88]是3 種 基于強化學習的代表性方案.NoDBA 作為一個早期的探索方案，只考慮單列索引，且其獎勵計算是基于工作負載實際執(zhí)行時間的縮減，每個情節(jié)中智能體步數(shù)與索引數(shù)量限額相等.考慮到效率問題，Lan?dxAdvis通過啟發(fā)式規(guī)則生成候選索引，限制動作空間.同時在訓練過程中使用what-if 優(yōu)化在當前動作所形成的索引配置下估計工作負載代價，并將相對于前一時刻的工作負載代價的縮減值作為智能體的獎勵來源.為了在探索和利用間平衡，在智能體策略函數(shù)中添加了 ε-greedy 因子（有 ε的隨機選擇動作的概率），終止條件為存儲空間約束或索引數(shù)量限額約束.MCTS_?T 采用和AutoAdmin 類似的方式生成候選索引（對應動作空間），并根據(jù)索引配置的單調性假設：一個工作負載在一個索引配置的子集配置下的代價不小于此工作負載在該索引配置下的代價，推導出一個索引配置下的工作負載代價為其所有子集配置所能達到的最小工作負載代價.其獎勵函數(shù)設計主要考慮相對于起始時刻的代價縮減率（代價縮減值與無索引情況下代價的比值），其智能體策略為了探索和利用的平衡，添加了簡化的 ε-greedy 因子，終止條件為索引數(shù)量限額.

表1 從搜索空間的生成策略、索引配置的評價手段、配置的形成策略、最終索引配置形成過程中的導向指標（即根據(jù)什么指標確定添加或刪除的索引）、索引調優(yōu)的終止條件、是否考慮索引間相互影響這6 個方面對這些代表性方法的特點進行了展示，文獻[21]也對部分傳統(tǒng)方法進行了實驗對比分析.

Table 1 Comparison of Representative Methods表1 代表性方法對比

5 動態(tài)工作負載下的索引選擇問題

5.1 在線索引選擇問題

在學術上，根據(jù)處理的工作負載情況是否可變，?SP 又可細分為離線?SP 和在線?SP.?SP 通常默認為離線?SP，處理的是不變的代表性工作負載.而實際生產(chǎn)環(huán)境中的工作負載可能是動態(tài)變化的，在線?SP處理的即是這種動態(tài)的工作負載，所以離線?SP 也可看成在線?SP 的特例，即在一個時間段內的在線?SP.現(xiàn)有離線索引選擇方案通常需要DBA 啟動集成索引推薦模塊的調優(yōu)工具，然后根據(jù)工具返回的提示信息和自身經(jīng)驗做出最終的調優(yōu)決策.但現(xiàn)代業(yè)務場景越來越復雜多變，這種完全離線的方案變得越來越局限.為了解決這個問題，在線?SP 研究如何在動態(tài)環(huán)境中有效地對數(shù)據(jù)庫索引配置進行調優(yōu)維護（比如索引的創(chuàng)建、刪除、更新等），保證數(shù)據(jù)庫系統(tǒng)的穩(wěn)定和高效.

綜合現(xiàn)有代表性在線索引選擇文獻[34,37,50-51,71,95]中的描述，本文對在線?SP 進行如下形式化定義：

定義2.給定一個數(shù)據(jù)庫D={T1,T2,…,Td}、一個查詢的序列 (q1,q2,…,qn) 以及約束條件集B={b1,b2,…,bj}，找到一個最優(yōu)的索引配置序列S*=(I1,I2,…,In)，使能在滿足約束條件集B的情況下最小化查詢序列的代價和索引配置轉變代價的總和，即S*=

其中cost(qi,Ii) 表示查詢qi在索引配置Ii下的代價，而transition(Ii-1,Ii) 表示索引配置從Ii-1變更為Ii的代價（比如創(chuàng)建/刪除索引的代價）.值得注意的是，有的研究工作[34,50-51]由于應用場景或假設不同，仍以工作負載序列而不是查詢序列為單位維護索引配置.同時，除了離線?SP 中常見的存儲空間約束和調優(yōu)時間約束外，還可能涉及由于動態(tài)工作負載帶來的新約束，比如索引配置變更的提升和代價間差值（也稱為索引配置變更收益）的閾值約束，即只有索引配置轉變的收益與代價間差值達到一定程度才會考慮變更索引配置.

5.2 在線ISP 的新挑戰(zhàn)

在線索引選擇處理的是動態(tài)工作負載，工作負載的偏移（workload shift）可能導致在原工作負載下推薦的索引配置在新工作負載發(fā)生收益衰減，甚至產(chǎn)生負收益.為了更好地處理動態(tài)工作負載，在線索引選擇方案可建模為一個在線反饋控制回路[24,37,96-97]，即監(jiān)控—調優(yōu)—調整的循環(huán)回路，如圖4 所示.通過監(jiān)控和觀測工作負載和數(shù)據(jù)庫系統(tǒng)指標，對現(xiàn)有數(shù)據(jù)庫系統(tǒng)和不同的候選索引配置進行評價和診斷，得到包含推薦配置的調優(yōu)建議，然后實際調整現(xiàn)有數(shù)據(jù)庫系統(tǒng)索引配置到推薦配置，完成一次控制反饋循環(huán).

Fig.4 Online index selection framework based on online feedback control loop圖4 基于在線反饋控制回路的在線索引選擇框架

大多離線索引選擇方案的輸出僅為調優(yōu)建議，對應在線反饋控制回路中的調優(yōu)部分，因此在線?SP不僅繼承了離線?SP 的既有挑戰(zhàn)，還面臨著新的挑戰(zhàn)：

1）需要高效的系統(tǒng)監(jiān)控.為了保證不會顯著影響數(shù)據(jù)庫系統(tǒng)的正常業(yè)務運行，系統(tǒng)監(jiān)控過程需要足夠高效，并能及時歸集相關數(shù)據(jù)，使能對系統(tǒng)進行及時的診斷調優(yōu)工作.比如，通過將相關監(jiān)控功能代碼嵌入數(shù)據(jù)庫內核（工程方面的挑戰(zhàn)）或根據(jù)調優(yōu)算法的需求，提高原始監(jiān)控數(shù)據(jù)預處理的能力，比如提高工作負載表征的準確性和效率.

2）需要高效的索引調優(yōu).由于工作負載的動態(tài)變化，在線索引選擇方案需要快速地生成和部署索引調優(yōu)建議，避免出現(xiàn)索引調優(yōu)建議部署完成后所面對的工作負載特征已經(jīng)發(fā)生變化的情況，造成實際調優(yōu)效果的下降.因此在實際設計在線索引調優(yōu)方案時，應充分考慮索引調優(yōu)主體算法的代價和索引配置變更的代價，比如新增對索引調優(yōu)算法代價和索引配置變更收益值等目標的考慮，更多的目標也提高了該多目標優(yōu)化問題的求解難度.

3）需要高效的索引配置變更.索引配置變更操作的調度計劃（即索引操作的序列）應該足夠高效，特別是考慮到索引間相互影響對索引操作代價影響的情況下.比如，如果待刪除索引i1搜索鍵是待創(chuàng)建索引i2的搜索鍵的前綴，此時可以利用索引i1降低索引i2的創(chuàng)建代價，即在變更部署計劃中先創(chuàng)建索引i2，再刪除索引i1.文獻[44]將該問題建模為調度（scheduling）問題，并證明了該問題是NP 難的.

值得注意的是，也有研究[35,98]提出半自動化的在線索引選擇方案，利用DBA 提供的調優(yōu)反饋讓調優(yōu)過程更人為可控[99].但我們認為，這種半自動的方案更適合在特定的探索性數(shù)據(jù)分析場景下使用.一方面，在企業(yè)數(shù)據(jù)管理和業(yè)務環(huán)境下，完全自動的方案能進一步降低企業(yè)的數(shù)據(jù)庫所有權成本，在算法和調優(yōu)機制將變得越來越智能的未來更有前景.另一方面，DBA 在復雜多變的數(shù)據(jù)庫應用場景下提供反饋信號的可靠性也是半自動化方案的一大瓶頸.

5.3 數(shù)據(jù)庫系統(tǒng)的監(jiān)控

現(xiàn)有研究對在線?SP 輸入的處理一般可分為2 種：一種是將輸入的查詢切分為一個一個等時間或等數(shù)量的窗口，一個窗口內查詢的集合即形成一個工作負載，如果不同窗口間工作負載的查詢分布發(fā)生偏移，則可能需要進行調整[34]；另一種則將輸入當成以查詢?yōu)閱挝坏牟樵兞鱗37,71]，實時地對索引配置進行調整.但不管使用哪種處理方式，都離不開對數(shù)據(jù)庫系統(tǒng)的監(jiān)控.

5.3.1 監(jiān)控與在線索引選擇

動態(tài)工作負載，比如查詢需求發(fā)生了改變，可能導致原來輸入/生成的代表性工作負載變得不再具有代表性，原來推薦的索引配置也可能變得不再高效.為了捕獲這種變化，數(shù)據(jù)庫系統(tǒng)需要持續(xù)監(jiān)控流入的查詢語句、索引利用情況以及系統(tǒng)性能等信息.

針對這個問題，很多數(shù)據(jù)庫廠商都在其數(shù)據(jù)庫產(chǎn)品中實現(xiàn)了這種監(jiān)控功能.比如，Oracle 的自動工作負載倉庫（automatic workload repository，AWR）模塊[13]能自動地從內存視圖中收集系統(tǒng)性能數(shù)據(jù)的快照，用來簡單識別工作負載中代價昂貴的查詢或傳入像ADDM[26]這樣的診斷模塊進行更復雜的調優(yōu)工作.微軟則將監(jiān)控機制集成在SQL Server 服務端內部，提出了一個持續(xù)監(jiān)控的通用框架SQLCM[100]，能以較低代價實現(xiàn)對數(shù)據(jù)庫系統(tǒng)的監(jiān)控.結合其事件—條件—動作（event-condition-action，ECA）規(guī)則引擎，可以給像索引選擇這樣的數(shù)據(jù)庫優(yōu)化任務提供支持.DB2 數(shù)據(jù)庫也實現(xiàn)了其查詢巡邏器組件，能對流入的工作負載進行監(jiān)控和管理[12].在學術界，Thiem 等人[101]提出了一種集成式性能監(jiān)控的思想，通過將性能監(jiān)控代碼集成到數(shù)據(jù)庫內核中，盡可能減小細粒度監(jiān)控給數(shù)據(jù)庫正常運行帶來的影響.

5.3.2 工作負載/查詢的表征

數(shù)據(jù)庫工作負載或查詢的表征反映了數(shù)據(jù)庫系統(tǒng)用戶的數(shù)據(jù)需求，對代表性工作負載（或查詢）或預期工作負載（或查詢）的正確認識是數(shù)據(jù)庫系統(tǒng)設計和優(yōu)化的關鍵之一.通過對DBMS 的監(jiān)控，可以抽取工作負載（查詢）相關的原始信息[13,100-101]，比如查詢文本、查詢相關數(shù)據(jù)表/列的統(tǒng)計信息、DBMS 在各時刻的實時性能信息等.但這些原始信息過于龐雜，如果能利用這些原始信息形成工作負載（查詢）的有效表征，則可更好地支持后續(xù)數(shù)據(jù)庫的診斷和調優(yōu)工作.離線?SP 處理的代表性工作負載是靜態(tài)的，且對調優(yōu)時間容忍度較高，所以工作負載通常被簡單表示為查詢語句的集合或查詢語句-頻率對的集合，但是這種粗粒度的表征方式忽略了查詢語句中的特征信息.合理的工作負載表征能幫助挖掘工作負載中的隱含知識，比如工作負載的查詢分布或工作負載、索引以及數(shù)據(jù)庫性能之間的關系，還能幫助進行工作負載摘要、查詢預測等預處理工作，提升索引選擇方案的效率和效果.

Calzarossa 等人[102]對批處理系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、分布式系統(tǒng)中的通用工作負載表征技術進行了綜述.對于數(shù)據(jù)庫工作負載，可以根據(jù)數(shù)據(jù)庫系統(tǒng)的追蹤（trace）記錄信息，利用聚類、統(tǒng)計分析等手段實現(xiàn)對工作負載的描述和分類.很多商業(yè)DBMS 會默認記錄這些信息，比如Oracle 和SQL Server 的系統(tǒng)性能快照[26,100]、DB2 的追蹤記錄[12].針對關系型數(shù)據(jù)庫系統(tǒng)，Yu 等人[103]提出了一個工作負載的分析和表征工具REDWAR，通過分析工作負載中查詢語句的結構、復雜性、查詢語句的實際執(zhí)行以及關系（視圖）構成情況，形成該工作負載的描述性統(tǒng)計信息并進行展示，幫助DBA 了解當前工作負載.Elnaffar 等人[104]則通過抽取工作負載特征來構建決策樹，判斷工作負載的類型是OLTP 型還是DSS 型，定性地對工作負載進行描述.這種定性的、描述性的方式能給數(shù)據(jù)庫系統(tǒng)設計和優(yōu)化任務提供參考信息，但不能提供精細的建議.

同時，不同任務場景下所需的工作負載表征方法是不同的.比如在系統(tǒng)資源/容量的規(guī)劃任務和數(shù)據(jù)庫參數(shù)調優(yōu)這些任務中，一種直接的解決思路就是通過歷史工作負載的性能表現(xiàn)信息對工作負載進行隱式（implicit）表征[1,105].比如，OtterTune[1]通過分析并選取數(shù)據(jù)庫部分內部運行時指標（internal runtime metric）來向量化工作負載.但在索引選擇問題中，索引的創(chuàng)建依賴數(shù)據(jù)庫模式，索引的采用與查詢語句內容、數(shù)據(jù)庫統(tǒng)計信息關系緊密.通過性能信息隱式表征工作負載的方式很難捕獲到這些關系，因此顯式地將查詢語句的文本特征（比如查詢所包含的關系、屬性等信息）或/和數(shù)據(jù)庫統(tǒng)計信息等特征與索引收益預期關聯(lián)的方式可能更適合索引選擇問題.

比如，在基于窗口的查詢處理方案中，Hammer等人[38]以當前窗口內的各類統(tǒng)計信息作為工作負載的表征，包括數(shù)據(jù)更新相關的統(tǒng)計信息（比如當前時間窗口內的數(shù)據(jù)記錄的增加、刪除和更新量）、屬性選擇率的統(tǒng)計信息（和索引的采用相關）以及查詢類型相關的統(tǒng)計信息.Schnaitter 等人[34]則將當前窗口內的查詢分布作為工作負載的表征.而對于基于查詢流的處理方案，Bruno 等人[37]提出用查詢邏輯計劃的訪問路徑請求信息表征工作負載.而QB5000[48]將工作負載中的查詢抽象為查詢模板，然后根據(jù)查詢模板的歷史到達率信息對模板所代表的查詢進行表征.Jain 等人[53]則提出用詞嵌入（word embedding）和基于長短期記憶（long short-term memory，LSTM）網(wǎng)絡的自編碼器技術實現(xiàn)查詢語句的向量化，并將該技術用于索引調優(yōu)[106].Paul 等人[107]通過設計和訓練2種不同的編碼器模型，從查詢計劃中分別捕獲查詢的結構與性能信息，綜合地對查詢語句進行向量化表征.

5.4 索引配置的診斷與調優(yōu)

通過監(jiān)控DBMS 獲取工作負載等索引調優(yōu)所需的信息后，在線索引選擇方案需要進一步地分析和判斷，解決是否需要對當前索引配置進行調整以及如何進行調整的問題.

5.4.1 反應式與主動式調優(yōu)

調優(yōu)階段的算法與離線索引選擇方案類似，輸出當前時刻的索引調優(yōu)建議，該過程需要耗費時間和計算資源.如果當前DMBS 和工作負載比較穩(wěn)定或新索引配置的預期提升不大，則應盡量避免調整配置.在線索引調優(yōu)有2 種處理方式：一種是反應式的（reactive），另一種則是主動式的（proactive）.反應式調優(yōu)分析歷史信息，檢測系統(tǒng)狀態(tài)變化，并根據(jù)這些信息輸出索引配置的調整建議；而主動式調優(yōu)則基于對未來狀態(tài)的預測結果進行調優(yōu)，比如根據(jù)預測得到的未來工作負載計算索引配置的調整策略.

對于反應式調優(yōu)方案，重要的是觸發(fā)條件的確定及對應的處理操作.觸發(fā)條件可以是特定長度的時間間隔或特定系統(tǒng)狀況的出現(xiàn)，比如工作負載出現(xiàn)了偏移、數(shù)據(jù)庫系統(tǒng)性能出現(xiàn)了明顯下降、系統(tǒng)指標超過了預設閾值等.比如，PDAlerter[37]即是一個輕量級的在線警告器，利用收集到的歷史查詢執(zhí)行信息估計對當前工作負載進行調優(yōu)的收益上下界，幫助判斷當前時刻是否需要進行調優(yōu).只有調優(yōu)收益可觀，該工具才會發(fā)出調優(yōu)提示.這種方式一定程度上可看成離線索引方案在在線?SP 上的直接擴展，更適合在工作負載較少發(fā)生偏移、偶爾需要調優(yōu)的場景下使用.OnlinePT[71]也是一種反應式調優(yōu)方案，在查詢優(yōu)化過程中收集候選索引，在查詢執(zhí)行過程中記錄和更新每個候選索引的累積收益情況，即文獻[71]中候選索引的累積收益被定義為過去一時間段內如果索引配置中存在該索引所帶來的累積代價縮減.如果觀測到一個候選索引的剩余收益（累積收益和索引創(chuàng)建代價之差）小于或等于0，則刪除這個索引；如果觀測到一個候選索引的創(chuàng)建滿足存儲空間約束，且能帶來最大剩余收益，則創(chuàng)建這個索引.文獻[71]方案利用索引歷史時間段的累積收益情況作為當前時刻的決策依據(jù)，這也意味著該方案只有在工作負載較少發(fā)生偏移或偏移幅度較小情況下能保證效果和可用性.此外，Elnaffar 等人[108]提出了一種工作負載偏移檢測機制，能判斷工作負載類型是否在DSS 和OLTP 間發(fā)生轉變.Holze 等人[109]則提出了一種更通用的工作負載變化檢測機制，將工作負載建模為n-gram 模型[110-111]，根據(jù)工作負載的困惑度（perplexity）變化情況來判斷工作負載是否發(fā)生了偏移.如果發(fā)生了偏移，則進行后續(xù)的索引調優(yōu)操作.半自動化的索引調優(yōu)方案WF?T[98]也屬于反應式的調優(yōu)方案，文獻[98]定義了索引配置的工作函數(shù)(work function)概念，并將其作為調優(yōu)目標.然后通過分析流入的查詢持續(xù)更新各索引配置的工作函數(shù)值，并基于這些信息生成調優(yōu)建議.

而對于主動式調優(yōu)方案，其重點在于對未來工作負載（表征）的預測.在得到未來工作負載的預測信息后，即可和不同的索引調優(yōu)策略結合進行調優(yōu).比如，Hammer 等人[38]以統(tǒng)計信息表征工作負載，并在每個時間段末尾基于歷史工作負載的統(tǒng)計信息用指數(shù)平滑法來預測下一時間段工作負載的統(tǒng)計信息，然后利用啟發(fā)式規(guī)則推薦索引.而COLT[34]通過歷史窗口的各索引收益情況預測那些索引在未來窗口的收益情況，且隨著工作負載中查詢的執(zhí)行不斷更新這些索引的收益估計.最后利用這些索引收益信息，采用背包問題解法進行索引推薦.QB5000[48]則用查詢的到達率信息對查詢進行表征，集成線性回歸、循環(huán)神經(jīng)網(wǎng)絡和核回歸模型，對未來工作負載中各查詢的到達率進行預測以用于索引推薦.

5.4.2 索引配置的調整代價

索引配置的調整是需要代價的.離線索引選擇方案的運行頻率較低，而且索引配置調整代價和工作負載的實際執(zhí)行代價相比較小，因此通常會忽略索引配置調整代價.但在線索引選擇方案需要更頻繁地對索引配置進行調整，不能再忽略索引配置調整代價.而且只有真實索引（非虛擬索引）才能給查詢執(zhí)行帶來實際收益，所以如果一個索引的創(chuàng)建比較耗時，或創(chuàng)建后查詢性能提升小于索引創(chuàng)建代價，則沒必要推薦這個索引.比如，在COLT[34]，OnlinePT[71]，WF?T[98]，SOFT[112]方案中，索引的收益計算過程便會扣除索引的創(chuàng)建代價.同時，索引調優(yōu)算法應避免短時間內頻繁創(chuàng)建和刪除同一個索引，因為這可能對數(shù)據(jù)庫系統(tǒng)帶來負擔.此外，考慮到方案的魯棒性，避免性能抖動，通常只有當調優(yōu)建議的預期性能提升與代價間的差值超過自定義閾值[37,98,113]時，該建議才會被采納.

5.4.3 調優(yōu)算法代價

在線索引調優(yōu)是持續(xù)進行的，所以對調優(yōu)方案的時效性和代價控制的要求更高.這些方案的代價來源主要分為3 個部分：監(jiān)控代價（見5.3 節(jié)）、調優(yōu)算法代價和索引配置調整的代價（見5.4.2 節(jié)）.本節(jié)將對如何降低調優(yōu)算法代價的問題進行討論.

無論是離線?SP 還是在線?SP，其調優(yōu)算法代價的主要來源都是what-if 優(yōu)化操作.離線索引選擇方案中用到的減少工作負載大?。ū热绻ぷ髫撦d壓縮）、原子配置概念等方法均可被用于在線索引選擇方案.而針對在線?SP 的動態(tài)特點和持續(xù)、重復的調優(yōu)需求，也有一些在線索引選擇方案設計了減少what-if優(yōu)化過程代價的新機制.比如，COLT[34]將候選索引集合分為3 部分：第1 部分被稱為物化索引集，包含所有已在數(shù)據(jù)庫系統(tǒng)中被物化的索引；第2 部分被稱為熱索引集，包含那些雖還未被物化但有潛力的索引；第3 部分被稱為普通索引集，包含所有不屬于物化索引集和熱索引集的索引.考慮到用what-if 優(yōu)化獲取所有候選索引收益的昂貴代價，COLT 設計了一種2 階段策略來維護更新索引的收益值，其中采用不同的方法對不同種類索引的收益進行更新.在第1 階段，COLT 利用外部代價模型生成粗粒度的索引收益統(tǒng)計信息，并根據(jù)這些信息對候選索引進行排序.一部分排名在前但還未被物化的候選索引會被加入熱索引集.在第2 階段，因為物化索引集和熱索引集中的索引最終被推薦的概率更大，為了更準確有效地進行調優(yōu)，COLT 會用更準確但更昂貴的what-if 優(yōu)化操作來收集和更新這2 個集合中候選索引的收益統(tǒng)計信息，避免對所有候選索引配置進行what-if 優(yōu)化.OnlinePT[71]則利用文獻[36-37]中查詢計劃的局部變換操作，在不進行what-if 調用情況下收集候選索引的收益相關信息，用于在線索引調優(yōu).

5.4.4 基于強化學習的在線索引選擇

在線?SP 處理的對象是窗口化的工作負載或查詢流，所以其強化學習建模與離線情況強化學習建模的主要區(qū)別在于狀態(tài)和獎勵函數(shù)的設計，而重點在于模型對動態(tài)工作負載的適應能力.為了讓智能體更好地適應動態(tài)環(huán)境、降低重新訓練的需要，狀態(tài)建模中應包含所有能幫助進行索引選擇的重要信息，使智能體在面對不同工作負載時，仍能輸出合理的調優(yōu)建議.比如利用基于學習的工作負載表征[49,51]讓智能體能捕捉查詢中影響索引選擇策略的特征，使智能體訓練后能更容易適應不同的工作負載/查詢.

比如，DBA bandits[49]將在線?SP 建模為多臂老虎機（multi-arm bandits，MAB）問題[90].其中每個手臂相當于一個索引配置，而每個手臂的評分用來評價該索引配置的好壞.面對每個查詢模板，該方法選取每個手臂包含的索引鍵前綴及其統(tǒng)計信息（比如是否是覆蓋索引、當前索引配置與數(shù)據(jù)庫的存儲空間比值、動作臂的歷史選取頻率）作為當前手臂的上下文（context）信息，并假設一個手臂的評分和其上下文信息存在線性關系，然后通過強化學習的訓練量化該線性關系.在實際決策過程中，智能體選擇當前狀態(tài)下評分最大的手臂所代表的索引配置用于推薦.文獻[49]從實驗上驗證了該方法對動態(tài)工作負載的適應能力，但要求未來查詢和現(xiàn)有查詢具有一定的相似性，不能完全不同.

而SW?RL[50]是一個基于PPO 的在線索引選擇方案.其智能體的狀態(tài)表示包含3 種信息，即源信息（比如存儲空間限制值這樣的約束描述信息）、當前狀態(tài)的索引配置信息以及工作負載信息（比如每個代表性查詢語句的頻率、每個代表性查詢語句在當前配置下的執(zhí)行時間估計等）.SW?RL 將代表性查詢語句的計劃以操作符為中心進行向量化，同時利用潛在語義索引（latent semantic indexing，LS?）技術[114]降低特征向量的維度，形成最終的工作負載表征.SW?RL可以幫助捕捉工作負載的語義信息，讓智能體更容易適應動態(tài)的工作負載環(huán)境.

針對非共享數(shù)據(jù)庫集群上的在線索引選擇問題，Sadri 等人[15]提出了一種基于DQN 的方案DRLinda，通過同時考慮查詢代價和集群負載均衡，讓智能體學習在面對一個查詢時如何選擇一個特定數(shù)據(jù)庫副本并建立特定的索引配置的策略.

此外，Basu 等人[84]提出了一種基于強化學習的數(shù)據(jù)庫調優(yōu)框架，并以索引調優(yōu)為例進行討論.該框架以查詢?yōu)榛締挝唬恍枰峁┐鷥r模型，同時對代價模型和索引選擇策略的值函數(shù)進行學習.但該方案假設查詢特征和代價估計、值函數(shù)之間都是線性關系，且沒有考慮索引間的相互影響，同時其采用的傳統(tǒng)強化學習算法也很難處理巨大的候選索引數(shù)量.

5.4.5 調優(yōu)算法對比

傳統(tǒng)在線索引選擇算法中，OnlinePT[71]和COLT[34]分別是反應式調優(yōu)方法和主動式調優(yōu)方法的代表.Schnaitter 等人[95]也針對在線?SP 提出了一個基準測試方法，用工作負載處理時間和索引配置變更時間之和以及工作負載處理的時鐘時間（wall-clock time）2 個指標來評價方案的優(yōu)劣，并對COLT 和OnlinePT的表現(xiàn)進行了對比.總的來說，OnlinePT 在工作負載變化快和變化幅度大的情況下效果比COLT 更穩(wěn)定和更好，因為在這種情況下COLT 這種主動式調優(yōu)方法對未來工作負載情況的預測可能出現(xiàn)偏差.基于強化學習的在線索引選擇方案[15,49-50,84]屬于反應式調優(yōu)，通過不斷試錯、學習和改進，學習面對各種查詢/工作負載的靈活策略.這些方法理論上是可行且有潛力的，但仍屬于探索性工作，也沒有和傳統(tǒng)在線索引選擇方案（比如COLT 和OnlinePT）相互之間進行實驗的對比分析.

5.5 索引配置的調整部署

索引配置的調整只有真實反映到數(shù)據(jù)庫系統(tǒng)中才能真正對查詢執(zhí)行造成影響，而合理的索引配置調整操作順序能提高調優(yōu)建議部署的效率.比如，如果索引配置的調整包含創(chuàng)建索引i1(a)和刪除索引i2(a,b) 這2 個操作，我們可能傾向于先創(chuàng)建索引i1，后刪除索引i2，因為索引i2中已包含按照屬性a排序的索引數(shù)據(jù)，因此可加速索引i1的創(chuàng)建.

雖然這個問題在離線?SP 中也存在，但由于離線情況下調優(yōu)頻率相對較低、影響不大，故離線索引選擇方案中很少考慮這個問題.而現(xiàn)有在線索引選擇方案還主要集中在解決獲取合理的索引配置調整建議問題上，因此這方面研究也較少.為了降低索引配置調整的代價，避免性能抖動，Luhring 等人[112]和Sattler 等人[33]在進行索引配置調整時都使用了一種延時索引（deferred index）機制，即先在數(shù)據(jù)庫注冊索引信息但不實際創(chuàng)建索引，實際創(chuàng)建操作會選擇在有查詢對該索引所在關系表進行全表掃描時進行，通過共享掃描過程，減少顯式創(chuàng)建索引的代價.

Agrawal 等人[115]首先意識到查詢順序對索引調優(yōu)的重要性，將工作負載看成一個查詢序列，并將索引的創(chuàng)建和刪除操作合理地插入工作負載查詢處理的序列中，最小化工作負載的執(zhí)行時間.該方法將索引推薦和索引配置的調整融合成一個過程，但假定工作負載是已知的，更適合離線索引選擇場景.Bruno等人[44]則首次提出物理設計調度（physical design scheduling）問題的概念和形式化定義，并以索引配置的調整為例進行討論，但沒有形成具體的方法.Kimura 等人[116]針對索引配置調整問題進行了系統(tǒng)的研究，對索引間相互影響進行分類和描述，并基于分類信息和基于約束規(guī)劃（constraint programming）的數(shù)學模型對這個問題進行形式化定義和求解.

5.6 小 結

面對動態(tài)的工作負載，?SP 也呈現(xiàn)出新的挑戰(zhàn).本節(jié)綜合現(xiàn)有代表性在線索引選擇文獻中的描述，對在線?SP 進行了形式化定義.然后基于在線反饋控制回路框架歸納和總結了相關的研究內容和方法.其中，數(shù)據(jù)庫系統(tǒng)的監(jiān)控模塊為調優(yōu)模塊提供輸入的查詢/工作負載或預處理后的監(jiān)控數(shù)據(jù)（比如通過手動設計或表示學習得到的特征）.調優(yōu)模塊解決是否需要對當前索引配置進行調整以及如何進行調整的問題.從形式上看，可以選擇反應式或主動式的調優(yōu)方式，反應式調優(yōu)的效果取決于歷史和未來的工作負載間、DBMS 狀態(tài)間的相似性，而主動式調優(yōu)的效果則取決于對未來的工作負載和DBMS 狀態(tài)的預測準確性.在工作負載變化快和變化幅度大的情況下，由于工作負載預測難度的提升，反應式調優(yōu)方案效果通常相對更好.而從細節(jié)上看，為了提高調優(yōu)模塊的效率效果，需要綜合考慮索引配置的調整代價和調優(yōu)算法的代價.合理的索引配置調整操作順序能提高索引配置的變更效率，該問題也是NP 難的，但現(xiàn)有研究較少.我們認為，未來對該問題進行系統(tǒng)性研究的潛力較大.

6 索引調優(yōu)工具的發(fā)展與現(xiàn)狀

6.1 索引調優(yōu)工具

在工業(yè)界，商業(yè)數(shù)據(jù)庫廠商為了提升產(chǎn)品競爭力，通常會在產(chǎn)品中集成相關調優(yōu)工具（GU? 或命令行工具）輔助DBA 進行調優(yōu).商業(yè)數(shù)據(jù)庫廠商很早就開始研究數(shù)據(jù)庫的物理設計調優(yōu)（包括索引調優(yōu)），并將研究成果以調優(yōu)工具的形式集成在其產(chǎn)品中.比如，微軟在1997 年便開始布局和推進該方向[3,25,117]，并在2001 年正式成立AutoAdmin 項目[118]，并延續(xù)至今，專注研究數(shù)據(jù)庫的管理和調優(yōu)，很多研究成果也被集成在SQL Server 數(shù)據(jù)庫調優(yōu)顧問中.同時期，?BM 也在DB2 上集成了db2advis 命令和可視化的DB2 設計顧問[119]，幫助DBA 進行索引調優(yōu)，并逐步形成對物化查詢表、多維聚簇表轉換等其他物理設計的調優(yōu)支持；而Oracle 則在其數(shù)據(jù)庫中實現(xiàn)了SQL 訪問路徑顧問，支持對索引、物化視圖、分區(qū)等物理設計的調優(yōu).

隨著開源數(shù)據(jù)庫的興起和流行，也有開發(fā)者和公司為開源數(shù)據(jù)庫實現(xiàn)索引調優(yōu)工具，擴展開源數(shù)據(jù)庫的功能，提升開源數(shù)據(jù)庫的可用性.比如，Percona工具箱中的pt-index-usage 命令[120]就可被用來分析MySQL 的索引使用情況，輸出不常用索引的刪除建議.開源插件dexter[121]，PoWA[122]和商業(yè)的pganalyze[123]，EDB Postgres[124]在PostgreSQL 上實現(xiàn)了索引推薦功能.還有第三方工具支持對多種數(shù)據(jù)庫的調優(yōu)，比如EverSQL[125]支持對Oracle，SQL Server，PostgreSQL，MySQL 等主流數(shù)據(jù)庫的索引調優(yōu).

雖然支持開源數(shù)據(jù)庫的索引調優(yōu)工具越來越多，但總的來說，商業(yè)數(shù)據(jù)庫的調優(yōu)工具起步更早，功能更加完善，且有相關論文[3,9-13,16,20,25-26,54,71,117-118]支撐.

6.2 自動化的調優(yōu)方案

隨著企業(yè)數(shù)據(jù)管理分析的場景日趨復雜多變，數(shù)據(jù)庫調優(yōu)工具也逐漸向更自動化、智能化、自治的（autonomous）方向發(fā)展.Oracle 在現(xiàn)有數(shù)據(jù)庫產(chǎn)品[126]中同時集成了主動式調優(yōu)和反應式調優(yōu)的能力，通過持續(xù)的系統(tǒng)監(jiān)控，自動捕捉和收集工作負載及相關執(zhí)行環(huán)境信息等源信息，支撐SQL 訪問顧問生成調優(yōu)建議及其預期收益的估計，極大降低了DBA 的調優(yōu)負擔.微軟最新的SQL Server 則集成了自動調優(yōu)（automatic tuning）[127]特性，通過分析查詢性能問題的潛在原因，自動推薦解決方案進行修復，比如自動進行索引調優(yōu)、自動糾正可能有問題的計劃等.且會持續(xù)對數(shù)據(jù)庫性能進行監(jiān)控，并對解決方案進行驗證，即如果性能出現(xiàn)下降，則自動恢復到最近的最佳狀態(tài).開源數(shù)據(jù)庫OpenGauss 在其DBMind 模式中也集成了一些機器學習驅動的數(shù)據(jù)庫技術，其中包括索引推薦功能[128].OtterTune 作為一個第三方工具，集成了很多機器學習算法，支持在其面板查看索引健康度的指標[129]，并提供索引調優(yōu)建議.

隨著云數(shù)據(jù)庫的發(fā)展，很多企業(yè)將部分數(shù)據(jù)庫調優(yōu)工作外包給云數(shù)據(jù)庫廠商.為了服務大量不同場景下的客戶，云數(shù)據(jù)庫廠商更需要自動化、智能化的索引調優(yōu)服務.比如，阿里云便為其云數(shù)據(jù)庫產(chǎn)品提供了數(shù)據(jù)庫自治服務[130].同時，傳統(tǒng)數(shù)據(jù)庫廠商也開始提供云數(shù)據(jù)庫產(chǎn)品，比如微軟的Azure SQL 數(shù)據(jù)庫[131]、Oracle 的自治數(shù)據(jù)庫Exadata[132]、?BM 的 云數(shù)據(jù)庫系列[133]也將其在傳統(tǒng)數(shù)據(jù)庫產(chǎn)品中成熟的索引調優(yōu)功能搬上云端，比如，Oracle 的自治數(shù)據(jù)庫便基于Oracle 數(shù)據(jù)庫及其Exadata 云數(shù)據(jù)庫提出，以應對各種場景不同復雜度和不同規(guī)模工作負載下的索引調優(yōu)任務.

7 總結與展望

7.1 總結

索引是數(shù)據(jù)庫系統(tǒng)重要的物理數(shù)據(jù)結構之一，索引調優(yōu)也是數(shù)據(jù)庫物理設計的重要組成部分.一個合適的索引配置能給數(shù)據(jù)庫性能帶來極大的提升，這也讓?SP 成為數(shù)據(jù)庫優(yōu)化的經(jīng)典問題之一.本文首先對離線?SP 進行定義，并把現(xiàn)有解決方案歸結為一個包含索引配置搜索空間生成、索引配置評價及索引配置的枚舉與搜索三大部分的調優(yōu)范式，然后對每部分的相關研究進行了歸納、總結和對比.

索引配置搜索空間的生成階段主要通過啟發(fā)式規(guī)則和優(yōu)化器來生成候選索引和索引配置，形成索引配置的搜索空間.作為輸入，索引配置搜索空間的大小極大影響著索引選擇方案的代價和效率.但是過于激進的空間剪枝策略反而可能錯誤地排除掉有益的索引，影響索引調優(yōu)方案的效果，所以啟發(fā)式規(guī)則的設計應該在效率和效果之間取得平衡.

為了評價索引配置，一種常用思路是通過工作負載在各索引配置下代價的數(shù)值來評價，相關研究大多通過優(yōu)化器的what-if 優(yōu)化技術進行估計.另一種思路則是通過構建索引配置間的偏序關系來比較各索引配置.比如，訓練一個機器學習分類器模型對索引間的偏序關系進行預測，然后在搜索過程中不斷尋找更好的索引配置.

在索引配置的枚舉與搜索策略中，自底向上的枚舉策略簡單直觀，效率相對較高，效果和具體的枚舉策略有關，在存儲空間限制較小時更適用.自頂向下的枚舉策略從不考慮存儲約束的初始配置，開始迭代地對索引配置進行松弛，通常在索引配置存儲限額較大時效果較好，但運行時間也更長.而基于整數(shù)規(guī)劃的隱枚舉策略側重在索引推薦的最優(yōu)性保證上，更難考慮到索引間的相互影響.且在面對大規(guī)模數(shù)據(jù)庫系統(tǒng)和工作負載時，這種策略可用性下降.基于強化學習的搜索策略通過訓練一個智能體，學習一個靈活的智能策略函數(shù)以生成索引調優(yōu)建議是一個有前景的方向.

面對動態(tài)工作負載下的?SP，我們依照在線反饋控制回路[24]框架，分別對數(shù)據(jù)庫系統(tǒng)的監(jiān)控、索引配置的診斷與調優(yōu)以及索引配置的部署調整3 方面的相關方法進行歸納和總結.面對動態(tài)工作負載，數(shù)據(jù)庫系統(tǒng)的監(jiān)控是整個在線反饋控制回路框架的入口，監(jiān)控過程收集到的各種數(shù)據(jù)被處理后發(fā)送給診斷與調優(yōu)模塊進行分析，形成調優(yōu)建議.該模塊中的調優(yōu)算法即對應離線索引選擇方案從工作負載輸入到調優(yōu)建議輸出的過程，反應式地或主動式地生成索引調優(yōu)建議.最后根據(jù)該建議規(guī)劃配置調整的計劃進行部署，形成在線反饋控制回路的閉環(huán).

7.2 展 望

在近幾年的數(shù)據(jù)庫領域頂級會議上，研究者們開始探索使用機器學習技術來增強或替換數(shù)據(jù)庫系統(tǒng)的優(yōu)化器，比如，Kraska 等人[134]提出一種學習型的數(shù)據(jù)庫系統(tǒng)框架SageDB，Marcus 等人[135]則提出了一個學習型優(yōu)化器Bao.在索引調優(yōu)問題上：1）越來越多的研究工作開始使用機器學習技術來改進索引選擇方案.比如，Ding?ndexAdvis[29]通過學習一個分類器來對索引配置進行比較和評價，替代AutoAdmin[3]中基于what-if 優(yōu)化的索引配置評價方式.2）索引調優(yōu)方案所考慮的要素也越來越精細和實際.比如，Siddiqui 等人[32]提出一種基于學習的新型工作負載壓縮算法?SUM 以提升索引選擇方案的效率.Siddiqui等人[67]還提出一個新型索引調優(yōu)原型系統(tǒng)D?ST?LL，設計了一個過濾冗余候選索引的過濾器和一個高效的學習型代價估計模型以提升索引選擇方案的效率和可伸縮性.而Wu 等人[88]針對what-if 優(yōu)化的代價問題提出一種能在what-if 調用次數(shù)預算內進行索引選擇的方案.3）越來越多變的應用場景也讓學術界更加關注更實際的在線?SP，特別是在索引選擇過程中對動態(tài)工作負載的處理.比如，Auto?ndex[51]針對索引配置的管理問題，提出利用蒙特卡洛樹搜索增量更新索引配置的方法，保證未來新工作負載的高效執(zhí)行效率.而SW?RL[50]通過抽取查詢或查詢計劃的特征并經(jīng)過潛在語義模型進行向量化，利用機器學習的泛化能力實現(xiàn)對動態(tài)工作負載的適應.

相比傳統(tǒng)索引選擇方案，現(xiàn)有基于機器學習的索引選擇方案仍不多，有較大的研究空間.我們認為，?SP 在6 個方向有較大的研究潛力，為研究者提供思路和參考：

1）集成基于學習的代價評估方法的索引選擇方案.現(xiàn)有研究中基于優(yōu)化器的代價估計方法是不準確的，可能導致調優(yōu)性能的退化[29].而當前面向?SP的基于學習的代價評估方法較少，具有較大研究潛力.其挑戰(zhàn)包括如何提高機器學習模型的訓練效率以及如何保證代價預測模型在不同情形下的穩(wěn)定性（面對不同工作負載和索引配置的組合時）和泛化能力（比如對動態(tài)工作負載的適應能力）等.

2）集成基于學習的索引配置比較方法的索引選擇方案.和利用工作負載代價值找到最優(yōu)索引配置的方式不同，基于學習的索引配置比較方法關注索引配置間的偏序關系，由于現(xiàn)有研究較少，具有較大的研究潛力.其挑戰(zhàn)在于對索引配置和工作負載的有效表征，使模型能準確地對索引配置進行比較.

3）基于強化學習的索引選擇方案.基于強化學習的方案能從數(shù)據(jù)和與DBMS 的交互過程中學習出靈活的索引配置搜索策略.基于強化學習的索引選擇方案越來越多，但仍存在很多挑戰(zhàn).比如如何合理地將索引選擇問題的挑戰(zhàn)內化到強化學習建模中，以及如何讓智能體適應動態(tài)的工作負載等.

4）索引調優(yōu)建議的最優(yōu)調整部署策略.該問題是NP 難的，現(xiàn)有相關研究較少，但卻影響索引調優(yōu)方案的效率（特別是在線場景下）.該問題可被看成是一個調度問題，且在數(shù)據(jù)庫索引間存在相互影響的上下文環(huán)境下變得更具挑戰(zhàn)性，值得進行更深入的研究.

5）考慮索引類型的索引調優(yōu).經(jīng)典的?SP 通常不考慮具體的索引類型，僅從邏輯上選擇特定的屬性列組成合適的索引并構建索引配置，通常也默認使用B+樹進行研究和實驗.但在實際調優(yōu)工具落地過程中，索引類型也是需要考慮的因素，比如，哈希索引在處理點查詢的時候通常是存在優(yōu)勢的.如果考慮索引類型，那么?SP 的候選索引配置空間將成倍增長，對索引選擇方案的伸縮性也提出了更高的要求.作為另一種選擇，新的學習型索引（learned index）用機器學習模型模擬索引從搜索鍵到實際記錄位置的映射，弱化了傳統(tǒng)索引結構的差別.但這些研究通常集中在內存數(shù)據(jù)庫領域，如果能夠將學習型索引技術遷移到磁盤數(shù)據(jù)庫中，那么將有利于消除索引調優(yōu)方案中對索引類型這個因素的考慮，同時也能提升學習型索引的應用面.這個方向已有少量研究[136-137]，仍具有較大潛力.

6）現(xiàn)有索引選擇研究主要集中在單機數(shù)據(jù)庫上，但分布式數(shù)據(jù)庫和云數(shù)據(jù)庫的迅猛發(fā)展為索引調優(yōu)引入了新的挑戰(zhàn).比如：在分布式數(shù)據(jù)庫中，如何選擇在哪個數(shù)據(jù)庫副本上建立怎樣的索引；在云數(shù)據(jù)庫中，如何利用云數(shù)據(jù)庫靈活的可擴展性和計費方式，經(jīng)濟地進行索引選擇，以及是否應該提高索引的存儲空間限額以提升數(shù)據(jù)庫的查詢處理性能等.

作者貢獻聲明：賴思超負責調研、論文撰寫和修改；吳小瑩指導論文寫作、審閱和修改；彭煜瑋、彭智勇提出論文指導意見.