陽文燦 胡卉芪 段惠超 胡耀藝 錢衛(wèi)寧

摘要：索引在提高查詢性能方面可以起到至關(guān)重要的作用，數(shù)據(jù)庫管理員的一項重要工作是為數(shù)據(jù)庫選擇合適的索引.但隨著數(shù)據(jù)庫工作負(fù)載的不斷復(fù)雜、數(shù)據(jù)量的持續(xù)增加、庫中關(guān)系表的逐漸增多，人為地分析工作負(fù)載成本、選擇合適的索引并估算數(shù)據(jù)庫空間變化情況變得越發(fā)困難.本文設(shè)計了一款面向負(fù)載的自動化索引推薦工具——CedarAdvisor.它從日志中自動化收集負(fù)載，統(tǒng)計查詢頻率，在為單條查詢生成候選索引的基礎(chǔ)上，評估索引收益與代價，通過動態(tài)規(guī)劃算法生成整個負(fù)載的索引推薦.最后我們在分布式數(shù)據(jù)庫上驗證了工具的有效性.

關(guān)鍵詞：數(shù)據(jù)庫;工作負(fù)載;索引推薦

中圖分類號：TP392

文獻(xiàn)標(biāo)志碼：A

文章編號：1000-5641（2020）06-0052-11

0引言

隨著互聯(lián)網(wǎng)應(yīng)用的不斷發(fā)展與成熟，在云計算、大數(shù)據(jù)、人工智能等新技術(shù)的帶動下，數(shù)據(jù)的絕對量在以驚人的速度不斷膨脹.根據(jù)DELL公司一項預(yù)測顯示，2020年全球生產(chǎn)的數(shù)據(jù)量達(dá)到40ZB.在大數(shù)據(jù)領(lǐng)域，數(shù)據(jù)篩選是對海量數(shù)據(jù)進(jìn)行發(fā)掘與分析的基礎(chǔ)，而數(shù)據(jù)篩選面對的場景具有數(shù)據(jù)量龐大、數(shù)據(jù)多節(jié)點存儲、查詢業(yè)務(wù)繁多等特點.如何高效地對海量數(shù)據(jù)進(jìn)行查詢、分析、處理和更新，為政府、企業(yè)、組織提供決策支持，一直是學(xué)術(shù)界和工業(yè)界共同關(guān)注的一個研究方向.

如今，當(dāng)在數(shù)據(jù)庫中面對海量數(shù)據(jù)進(jìn)行查詢操作時，索引在提高查詢性能方面可以起到至關(guān)重要的作用.在查詢執(zhí)行過程中，通過查詢索引表的方式替代全表掃描，可以大幅縮短查詢時間.然而，索引在縮短數(shù)據(jù)項搜索時間的同時，也增加了額外開銷，主要體現(xiàn)在：（1）索引需要額外的存儲空間;

（2）使得更新操作復(fù)雜化，因為在對基表進(jìn)行更新操作時，需要對相應(yīng)的索引表進(jìn)行同步更新.

因此，在日常業(yè)務(wù)中，為了確保系統(tǒng)在面對工作負(fù)載時保持良好的性能，如何為工作負(fù)載選擇一組合適的索引是數(shù)據(jù)庫管理員面臨的一個重要問題，即索引選擇問題（Index Selection Problem，ISP）.但隨著數(shù)據(jù)量的大幅增加、工作負(fù)載的復(fù)雜性和動態(tài)性的不斷增加，數(shù)據(jù)庫管理人員面臨著更為困難的挑戰(zhàn).如何減輕數(shù)據(jù)庫管理員的工作難度、降低維護(hù)數(shù)據(jù)庫系統(tǒng)的人力成本，成為當(dāng)前數(shù)據(jù)庫研究領(lǐng)域的一個熱點問題.

本文以數(shù)據(jù)負(fù)載索引選擇問題為出發(fā)點，總結(jié)了部分商用數(shù)據(jù)庫的自動化索引推薦工具，提出了一種基于規(guī)則與基于代價相結(jié)合的負(fù)載自適應(yīng)索引推薦模型，并實現(xiàn)了一款索引推薦工具——CedarAdvisor，最后在分布式數(shù)據(jù)庫上驗證了工具的有效性.

本文的主要貢獻(xiàn)如下：

（1）實現(xiàn)了一個基于規(guī)則與基于代價相結(jié)合的負(fù)載自適應(yīng)索引推薦模型.

（2）實現(xiàn)了一個索引收益一代價評估模型.

（3）從候選索引空間中羅列所有索引組合配置復(fù)雜度非常大，本文采用動態(tài)規(guī)劃算法在有限時間內(nèi)得到最優(yōu)或者接近最優(yōu)的索引組合配置.

1背景和相關(guān)工作

人們從20世紀(jì)70年代就開始進(jìn)行索引選擇問題的研究.盡管研究時間很長，但有兩個基本原因使得該問題尚未完全解決，首先，索引選擇問題本質(zhì)上是一個排列組合問題，對一個大型企業(yè)的生產(chǎn)環(huán)境數(shù)據(jù)庫而言，有大量的表和列，難以在有限時間內(nèi)枚舉所有的索引組合情況.其次，難以通過用簡單的搜索算法為負(fù)載找到一個最優(yōu)的索引組合配置.數(shù)據(jù)庫管理人員很難在時間有限、空間有限的情況下，為負(fù)載建立合適的索引.越來越多的數(shù)據(jù)庫提供商力圖通過自動化工具減輕數(shù)據(jù)庫管理人員的工作負(fù)擔(dān)，幫助企業(yè)降低數(shù)據(jù)庫總運(yùn)營成本.各大供應(yīng)商對此進(jìn)行了相應(yīng)的研究并將研究成果應(yīng)用在了自身推出的產(chǎn)品中.

（1）AutoAdmin microsoft公司的AutoAdmin項目主要研究數(shù)據(jù)庫系統(tǒng)的自管理與自調(diào)優(yōu)技術(shù)，并將研究成果應(yīng)用到了SQL Server產(chǎn)品中，推出了針對SQL Server7.0的Index Tuning Wizard和針對SQL Sever 2005的Database Tuning Advisor.Database Tuning Advisor的執(zhí)行策略是，將整個負(fù)載作為輸入，逐條分析負(fù)載中的查詢.首先為單條查詢語句選出最優(yōu)或者接近最優(yōu)的索引，主要是通過分析負(fù)載語句中能夠減少執(zhí)行成本的結(jié)構(gòu)，作為此條查詢的候選索引空間，通過代價模型分析每個索引的收益，在不超過索引數(shù)量限制的基礎(chǔ)上，通過貪心算法從候選空間中選出可以減少此條查詢執(zhí)行時間的索引，直至查詢時間無法再減小.之后將所有單條查詢的推薦索引作為整個負(fù)載的候選索引空間.接著對集合中的索引進(jìn)行適當(dāng)?shù)暮喜?，主要是將作用查詢相同的索引合并為一個新的索引.最后，再次利用貪心算法從負(fù)載候選索引空間中選出整個負(fù)載的最優(yōu)索引集合.

（2）DB2 Designer Advisor

IBM公司的DB2 Designer Advisor是IBM為DB2數(shù)據(jù)庫研發(fā)的自調(diào)優(yōu)工具，可針對工作負(fù)載提供索引、物化視圖、數(shù)據(jù)分區(qū)等方面的建議.DB2 Advisor的索引選擇基于的思想是，假設(shè)將所有可能的索引都注入數(shù)據(jù)庫中作為虛擬索引（Virtual Index），通過DB2的查詢優(yōu)化器生成最佳的訪問計劃，如果計劃中用到了一個或多個虛擬索引，那么這些索引就是單條查詢的候選索引.但枚舉所有可能的索引會使得候選集合過于龐大，因此DB2 Advisor通過使用DB2的查詢優(yōu)化器中的“Smart column Enumeration for Index Scans”（SAEFIS）算法限制候選索引數(shù)量.SAEFIS算法主要通過分析語句中的謂詞條件、GROUP-BY、ORDER-BY條件，以生成可能在虛擬索引中用到的列集.DB2 Advisor通過“Brute Force and Ignorance”（BFI）算法枚舉所有可能的索引，并在DB2中虛擬地建立索引，即索引并不真正建立，但查詢優(yōu)化器可以搜索到.調(diào)用查詢優(yōu)化器為單條SQL生成最佳查詢計劃.在查詢計劃中找出虛擬索引作為負(fù)載整體候選索引.理論上可通過查詢優(yōu)化器的“Mass Query Optimization”（MQO）技術(shù)為負(fù)載推薦最優(yōu)索引組合，即調(diào)用一次查詢優(yōu)化器同時為多條SQL推薦索引，但由于MQO技術(shù)在商用數(shù)據(jù)庫中并不支持，因此DB2 Advisor采用0-1背包算法解決負(fù)載索引推薦.

2 CedarAdvisor整體架構(gòu)

CedarAdvisor索引推薦工具是基于小米SQL優(yōu)化和改寫工具開發(fā)的，面向整個負(fù)載的索引推薦工具.它從日志中自動化收集負(fù)載，統(tǒng)計查詢的頻率，在為單條查詢生成候選索引的基礎(chǔ)上，評估索引收益與代價.通過動態(tài)規(guī)劃算法生成整個負(fù)載的索引推薦，并在分布式數(shù)據(jù)庫Cedar上進(jìn)行了測試.圖1展現(xiàn)了該工具的主要執(zhí)行流程.

CedarAdvisor索引推薦工具主要分為如下幾個部分.

（1）負(fù)載收集：主要功能是從數(shù)據(jù)庫的日志中提取執(zhí)行的查詢SQL作為工作負(fù)載文件，并統(tǒng)計每條查詢的使用頻率.

（2）語法解析：采用語法解析庫將查詢解析為語法樹結(jié)構(gòu).

（3）候選索引：通過分析語法樹中謂詞條件、分組條件、排序條件選出候選列，通過數(shù)據(jù)庫統(tǒng)計信息獲取列信息、表信息，在估算選擇率的基礎(chǔ)上為單條查詢推薦出最佳索引.全部查詢的最佳索引構(gòu)成了整個負(fù)載的候選索引空間.

（4）數(shù)據(jù)庫基本信息獲?。和ㄟ^訪問數(shù)據(jù)庫，獲取表和列的元信息、統(tǒng)計信息，為代價模型提供支撐數(shù)據(jù).

（5）索引評估：估算每個索引帶來的收益和成本.

（6）負(fù)載索引：通過動態(tài)規(guī)劃算法，在有限的時間內(nèi)選出相對最優(yōu)的索引配置，完成負(fù)載索引推薦.

3具體實現(xiàn)

3.1負(fù)載收集

數(shù)據(jù)庫日志會記錄已經(jīng)執(zhí)行的查詢.例如，分布式數(shù)據(jù)庫Cedar將執(zhí)行過的查詢記錄在T-node（查詢節(jié)點）的日志中.負(fù)載收集的任務(wù)是從日志中讀取執(zhí)行過的查詢SQL，加入負(fù)載文件中，并統(tǒng)計每條查詢的使用頻率.

3.2候選索引生成

實踐中，大型企業(yè)的一個數(shù)據(jù)庫里通常含有幾百張表，采用枚舉的方法生成的候選索引空間將會非常龐大，因此必須采用一些方法限制候選索引的數(shù)量.根據(jù)Tapio Lahdenmaki等人提出的觀點，在一個查詢中，在謂詞條件、連接條件、ORDER-BY條件、GROUP-BY條件中涉及的列上建索引對提升查詢效率的幫助是最大的，因此可以通過分析查詢中的特定條件列，將候選索引的數(shù)量盡可能減少.

索引的選擇本身是一個在收益和代價之間做權(quán)衡的過程.索引的收益來自查詢性能的提升，索引代價來自額外的占用空間和對事務(wù)更新性能的影響.選擇較少的索引列可以減少索引的占用空間和索引維護(hù)代價，而選擇較多的索引列可以減小回表查詢的概率，獲得最大的查詢性能提升.我們將盡可能減少索引列的選擇方式稱為“最小化索引”，將盡可能多地增加索引列的選擇方式稱為“最大化索引”.本文采用的是最小化索引模式.

具體步驟如下：

（1）遍歷AST中WHERE條件中的等值條件列，加入等值列數(shù)組，稱之為EQValues數(shù)組;

（2）遍歷AST中WHERE條件中的范圍條件列，加入范圍列數(shù)組，稱之為RangeValues數(shù)組;

（3）根據(jù)采集的數(shù)據(jù)庫元信息和統(tǒng)計信息，補(bǔ)全EQValues和RangeValues中所有列的基本信息;

（4）將EQValues與RangeValues中的列，分別依據(jù)選擇率升序排列;

（5）定義一個HashMap，Key為表名，Value為列數(shù)組PKColumns，存放的列作為該索引表主鍵列.將EQValues與RangeValues中的列依據(jù)表名加入不同表的PKColumns中.在此需要注意的是，若PKColumns中存在原表第一主鍵列，則該表掃描路徑將不走索引而直接掃描原表的主鍵索引，因此該表不推薦索引，刪除此對Key-Value.

其具體流程如算法1所述.

3.3列基本信息

生成候選索引的時候，需要知道列的基本信息，從語法樹中獲取到候選列時，列所屬的表名可能存在3種情況：①表名為真實表名;②表名為別名;③不存在表名.針對前兩類情況，都可以直接在語法樹中找出真實表名.針對最后一類情況，直接從該SQL涉及的表中查找相同列名，若能找到則補(bǔ)充表名信息，若無法找到說明該列屬于子查詢結(jié)果集，在此層查詢的候選索引中去除該列，留給子查詢處理.

生成候選索引還需要估算列的選擇率（SelectionRate）.選擇率的估算參考了PostgreSQL數(shù)據(jù)庫的計算方法：

3.4索引收益-代價評估

為單條查詢生成最佳索引之后，需要計算每個索引的收益與成本.在此階段，收益是每個索引能為單條查詢執(zhí)行所減少的時間，而成本是每個索引所占用的空間大小.由于不可能將索引真正建立后再去統(tǒng)計查詢的執(zhí)行時間，需要一個代價模型去估算索引能帶來的時間減少.

（1）索引收益

在查詢執(zhí)行過程中，有一個訪問路徑?jīng)Q策階段.訪問路徑是獲取基本表數(shù)據(jù)的可能途徑，可分為直接從原表獲取或通過索引表獲取.若索引表包含的列無法包含上層算子的所有列，則需要通過索引中包含的原表主鍵訪問原表，這一過程稱為回表.本文討論的索引表不帶有冗余列，因此在計算索引收益之前，需要判斷使用該索引是否需要回表，若需要，則回表標(biāo)志位置為True.

前文已經(jīng)介紹了選擇率的計算方法，再結(jié)合基本表的行數(shù)信息，可以估算出掃描出來的結(jié)果集的大小，進(jìn)而使用這些數(shù)據(jù)來計算訪問路徑代價.訪問路徑代價主要包含：將磁盤讀取到內(nèi)存中的磁盤10代價、執(zhí)行過濾計算的CPU代價、索引回表代價，以及GROUP-BY和ORDER-BY條件的排序操作所產(chǎn)生的排序代價.

在代價估算過程中，無法獲取絕對真實的代價，但由于只需要做到不同訪問路徑之間的代價比較，因此以某個代價作為代價單位1，其他的代價都為相對于這個基準(zhǔn)代價的一個比值.

1）全表掃描代價

基本表的全表掃描代價為FullTableScanCost，主要包含CPU代價CpuRunCost和磁盤IO代價IOCost：

（2）索引代價

索引代價主要是估算索引所占用的空間大小，通過統(tǒng)計信息獲取原表行數(shù)Tuples（R），即索引表行數(shù)Tuples（Index）.對于varchar類型，本文采用保守計算方式，即字符串占滿所申請長度，通過索引表每一列數(shù)據(jù)類型估算每行數(shù)據(jù)大小TupleSize，最終索引表大小估算公式為

Size（Index）=Tuples（Index）×TupleSize.

3.5負(fù)載索引推薦

接下來將介紹為工作負(fù)載推薦索引的算法.通過經(jīng)典0-1背包算法去解決負(fù)載的索引選擇問題.每個索引都有收益與代價兩個屬性，存在放入與不放入背包兩種狀態(tài).索引的收益是指對利用它的查詢的估計執(zhí)行時間的改進(jìn)，并乘上每個查詢在工作負(fù)載中發(fā)生的頻率，索引的代價是指估算的索引表的大小，同時通過設(shè)定每張表的最大索引數(shù)量約束索引對事務(wù)更新造成的延時.

背包具有固定的最大尺寸，放人背包中的索引大小不能超過背包大小的限制.與此同時，由于當(dāng)原表發(fā)生更新操作時，索引表需要進(jìn)行同步更新，為了避免一張表索引數(shù)量過多對其更新事務(wù)造成延時，數(shù)據(jù)庫通常會對一張表的最大索引表數(shù)量進(jìn)行限制.例如，在Cedar中，一張表的最大索引數(shù)量默認(rèn)為10.算法的目標(biāo)是使得放人背包中的索引收益最大化.其具體流程如算法2所述.

4實驗評估

在分布式數(shù)據(jù)庫Cedar上，驗證CedarAdvisor所推薦索引的有效性.

4.1實驗環(huán)境

將Cedar部署在單集群環(huán)境中，集群中有1臺T-node（更新節(jié)點）、1臺Q-node（查詢節(jié)點）和1臺S-node（基線節(jié)點）.每臺機(jī)器的主要配置：Intel（R）Xeon（R）CPU E5-26200@2.00 GHz型號2核心CPU，128GB內(nèi)存和1TB機(jī)械硬盤.

4.2實驗方法與結(jié)果

采用TPC-DS基準(zhǔn)作為數(shù)據(jù)來源和負(fù)載來源，生成1GB的TPC-DS數(shù)據(jù)并導(dǎo)入庫中，從TPC-DS中選出部分可以滿足Cedar索引使用規(guī)則并且涉及大表查詢的查詢，與此同時，對SQL進(jìn)行一些改寫，以便更好地體現(xiàn)出索引的作用.在每條SQL中，為每個表都添加上選擇率較低的范圍過濾條件，改寫后的SQL名稱以原SQL名加上“-1”命名;在每條SQL中為每個表都添加等值過濾條件，改寫后的SQL名稱以原SQL名加上“-2”命名.選出18條查詢SQL構(gòu)成本次實驗的負(fù)載，負(fù)載中有重復(fù)的SQL，如表1所示，頻率為每條查詢SQL的執(zhí)行次數(shù)，整個負(fù)載共執(zhí)行30次查詢.

表2給出了CedarAdvisor針對此負(fù)載經(jīng)去重與整合后推薦的所有候選索引.并非所有的候選索引都會進(jìn)入最終被推薦的索引集合.需要結(jié)合索引空間限制、每個索引的收益與代價，選出整個負(fù)載的最優(yōu)索引.

首先測試針對單條查詢所推薦索引的有效性.使用CedarAdvisor分別給每條查詢推薦索引，經(jīng)數(shù)據(jù)預(yù)熱后比較每條查詢的使用索引與不使用索引執(zhí)行的時間長短.測試結(jié)果如圖2所示.

圖2給出了負(fù)載中各條查詢使用推薦索引的執(zhí)行時間.可以看出，當(dāng)非主鍵列上的過濾條件使用索引時，一定程度上加快了查詢速度.當(dāng)過濾條件為范圍條件時，可將全表掃描轉(zhuǎn)化為對索引表的范圍掃描，TPCDS原SQL的執(zhí)行速度得到了部分提升，“-1”系列SQL的執(zhí)行速度得到了明顯提升.當(dāng)過濾條件為等值條件時，可將全表掃描轉(zhuǎn)化為索引表的點查詢，較大提升了“-2”系列SQL的執(zhí)行速度.證明了單條SQL索引推薦策略的有效性.

接下的實驗是為了驗證在不同索引空間限制條件下，CedarAdvisor針對整個負(fù)載推薦的索引集合對負(fù)載執(zhí)行時間的影響，實驗結(jié)果如圖3所示.

在該實驗中，當(dāng)最大索引空間小于80MB時，增大索引空間可以容納更多的索引表，顯著提升了查詢執(zhí)行效率，縮短了負(fù)載的限制時間.但索引空間已經(jīng)大于80MB后，增加索引數(shù)量已經(jīng)無法再有效地增加負(fù)載執(zhí)行效率.3.5節(jié)中已經(jīng)介紹，負(fù)載的索引集合，是在單條SQL推薦索引的基礎(chǔ)上，再通過背包算法放入最優(yōu)索引集合.因此當(dāng)最大索引空間小于某個值前，通過增加索引可以有效提升查詢負(fù)載的執(zhí)行效率.但當(dāng)索引空間大于某個值后，單純通過增加索引已無法有效提升查詢負(fù)載的執(zhí)行效率，只會增加空間消耗與索引維護(hù)成本.該實驗證明了通過0-1背包算法選擇最優(yōu)索引集合的有效性.

5總結(jié)

本文以數(shù)據(jù)庫索引選擇問題為出發(fā)點，首先介紹了兩款商用數(shù)據(jù)庫的索引推薦工具的大致原理，進(jìn)而提出了面向負(fù)載的、以有限候選空間為基礎(chǔ)且用動態(tài)規(guī)劃算法為負(fù)載選擇索引的模型，在此模型的基礎(chǔ)上實現(xiàn)了CedarAdvisor索引推薦工具，并在分布式數(shù)據(jù)庫Cedar上驗證了該工具的有效性.SQL的結(jié)構(gòu)是非常豐富的，本文論述的索引推薦模型只討論了部分常見SQL結(jié)構(gòu)，對于SQL中的一些復(fù)雜結(jié)構(gòu)，如何為其選擇索引并評估收益值得進(jìn)一步研究與討論.