數(shù)據(jù)庫索引調(diào)優(yōu)技術(shù)綜述

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

1（武漢大學(xué)計(jì)算機(jī)學(xué)院 武漢 430072）

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

（sichaolai@whu.edu.cn）

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

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

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

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

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

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

1 索引選擇問題

1.1 問題定義

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

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

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

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

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

1.2 研究?jī)?nèi)容與基于搜索的調(diào)優(yōu)范式

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

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

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

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

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

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

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

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

1.3 存在的挑戰(zhàn)

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

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

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

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

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

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

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

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

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

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

2.2 候選索引集合

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

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

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

2.3 候選索引配置搜索空間

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

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

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

2.4 工作負(fù)載的壓縮

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

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

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

2.5 小 結(jié)

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

3 索引配置的評(píng)價(jià)

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

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

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

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

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

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

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

還有研究工作[12,61]通過減少工作負(fù)載中所需處理查詢數(shù)量來減少需要進(jìn)行what-if 優(yōu)化的配置數(shù)量，比如工作負(fù)載壓縮，或利用索引配置間關(guān)系動(dòng)態(tài)降低what-if 優(yōu)化所需考慮查詢的數(shù)量[23,44]，比如，如果1 個(gè)待評(píng)估索引配置和1 個(gè)已被評(píng)價(jià)索引配置只差1 個(gè)索引，那么只需重新估計(jì)和該索引相關(guān)的查詢?cè)诖u(píng)價(jià)索引配置下的代價(jià)，即可通過相關(guān)查詢?cè)诓煌渲瞄g的差值推導(dǎo)出工作負(fù)載在待評(píng)價(jià)索引配置下的代價(jià).

3.3 基于機(jī)器學(xué)習(xí)的配置評(píng)價(jià)

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

3.3.1 基于機(jī)器學(xué)習(xí)的代價(jià)估計(jì)

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

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

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

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

3.3.2 基于機(jī)器學(xué)習(xí)的索引配置比較

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

3.4 索引的更新維護(hù)代價(jià)

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

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

3.5 小 結(jié)

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

4 索引配置的枚舉與搜索

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

4.1 索引間的相互影響

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

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

4.2 自底向上的枚舉策略

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

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

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

4.3 自頂向下的枚舉策略

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

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

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

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

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

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

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

4.5 基于強(qiáng)化學(xué)習(xí)的搜索策略

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

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

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

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

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

4.6 方法對(duì)比

4.6.1 常用實(shí)驗(yàn)設(shè)置與評(píng)價(jià)指標(biāo)

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

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

4.6.2 代表性方法對(duì)比

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

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

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

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

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

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

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

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

Table 1 Comparison of Representative Methods表1 代表性方法對(duì)比

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

5.1 在線索引選擇問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3.2 工作負(fù)載/查詢的表征

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

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

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

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

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

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

5.4.1 反應(yīng)式與主動(dòng)式調(diào)優(yōu)

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

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

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

5.4.2 索引配置的調(diào)整代價(jià)

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

5.4.3 調(diào)優(yōu)算法代價(jià)

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

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

5.4.4 基于強(qiáng)化學(xué)習(xí)的在線索引選擇

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

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

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

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

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

5.4.5 調(diào)優(yōu)算法對(duì)比

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

5.5 索引配置的調(diào)整部署

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

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

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

5.6 小 結(jié)

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

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

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

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

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

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

6.2 自動(dòng)化的調(diào)優(yōu)方案

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

隨著云數(shù)據(jù)庫的發(fā)展，很多企業(yè)將部分?jǐn)?shù)據(jù)庫調(diào)優(yōu)工作外包給云數(shù)據(jù)庫廠商.為了服務(wù)大量不同場(chǎng)景下的客戶，云數(shù)據(jù)庫廠商更需要自動(dòng)化、智能化的索引調(diào)優(yōu)服務(wù).比如，阿里云便為其云數(shù)據(jù)庫產(chǎn)品提供了數(shù)據(jù)庫自治服務(wù)[130].同時(shí)，傳統(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)品中成熟的索引調(diào)優(yōu)功能搬上云端，比如，Oracle 的自治數(shù)據(jù)庫便基于Oracle 數(shù)據(jù)庫及其Exadata 云數(shù)據(jù)庫提出，以應(yīng)對(duì)各種場(chǎng)景不同復(fù)雜度和不同規(guī)模工作負(fù)載下的索引調(diào)優(yōu)任務(wù).

7 總結(jié)與展望

7.1 總結(jié)

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

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

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

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

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

7.2 展 望

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

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

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

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

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

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

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

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

作者貢獻(xiàn)聲明：賴思超負(fù)責(zé)調(diào)研、論文撰寫和修改；吳小瑩指導(dǎo)論文寫作、審閱和修改；彭煜瑋、彭智勇提出論文指導(dǎo)意見.