面向關系數據庫的智能索引調優方法

來源：《軟件學報》，作者邱 濤等

摘 要:數據庫索引是關系數據庫系統實現快速查詢的有效方式之一.智能索引調優技術可以有效地對數據庫實例進行索引調節,從而保持數據庫高效的查詢性能.現有的方法大多利用了數據庫實例的查詢日志,它們先從查詢日志中得到候選索引,再利用人工設計的模型選擇索引,從而調節索引.然而,從查詢日志中產生出的候選索引可能并未實際存在于數據庫實例中,因此導致這些方法不能有效地估計這類索引對于查詢的優化效果.首先,設計并實現了一種面向關系數據庫的智能索引調優系統;其次,提出了一種利用機器學習方法來構造索引的量化模型,根據該模型,可以準確地對索引的查詢優化效果進行估計;接著設計了一種高效的最優索引選擇算法,實現快速地從候選索引空間中選擇滿足給定大小約束的最優的索引組合;最后,通過實驗測試不同場景下智能索引調優系統的調優性能.實驗結果表明,所提出的技術可以在不同的場景下有效地對索引進行優化,從而實現數據庫系統查詢性能的提升.

關鍵詞:索引調優;機器學習;數據庫索引;優化模型;關系數據庫

數據庫索引是數據庫系統中一種排序的數據結構,以協助快速查詢、更新數據庫表中的數據[1,2].合理地設計數據庫索引,可以有效提升數據庫系統的檢索速度.構建數據庫索引雖可以提升數據庫管理系統的查詢性能,但同時也存在額外的磁盤開銷與索引維護代價[3,4](例如更新查詢引起的索引更新).因此,設計索引時需充分考慮應用的具體需求與數據分布特點,針對具體的實例添加相應的索引結構,從而提升數據庫系統的查詢性能.

當前,主流的索引設計方式是人工進行設計,由數據庫管理員(DBA)或程序開發人員完成數據庫實例的索引設計[2].這種設計方法存在如下兩方面的限制:(1)設計人員需要了解具體的應用需求(查詢特征與分布等),并且熟悉所使用的數據庫管理系統的查詢優化策略與索引調用機制;(2)當應用的查詢特征與分布發生變化時,既有的索引結構無法及時調整,以保證數據庫系統高效的查詢性能.由于人工設計索引存在的這些限制,使得實際應用中會存在大量的索引設計不合理的情況,極大地影響了數據庫系統的查詢性能,同時也增加了服務器硬件資源的開銷.

智能索引調優技術可以解決人工設計索引存在的問題,該技術通過對應用的查詢日志進行分析,動態地對數據庫實例的索引進行調整,使其對與查詢日志中具有相似特征的查詢提供高效的查詢性能.現有的調優技術可以分為基于規則和基于代價模型的兩類.基于規則的調優技術利用特定的規則(例如滿足出現頻率的字段組合[5]、滿足索引調用機制的字段組合)從查詢日志中產生出推薦的索引集合,如果推薦索引未存在于數據庫實例中,則直接在實例中建立該索引.這類方法僅考慮了利用索引能帶來的查詢優化效果,未考慮維護索引所需的代價.尤其對于當前常見的混合事務/分析處理(HTAP)的應用,這類方法無法有效地調節索引.基于代價模型的調優技術則進一步考慮了維護索引所需的代價,通過設計相應的收益-代價模型,選擇查詢優化收益大于維護代價的索引.然而,從查詢日志中產生的推薦索引可能并未實際存在于數據庫實例中,現有的基于代價模型的方法不能準確地估計這類索引的查詢優化效果與維護代價;同時,該類方法未考慮數據庫實例中現有索引與數據分布對于查詢性能的影響,致使其無法有效的進行索引調節.

另一方面,機器學習已經廣泛地應用于各個領域.現有的技術已經利用了機器學習的方法來實現數據庫的查詢優化.例如,相比于傳統的利用人工設計的模型,通過機器學習的方法可以更加準確地估計各種場景下的查詢執行時間與資源消耗[6?9].本文針對上述基于模型的索引調優技術所存在的問題,提出了利用了機器學習的方法來預測不同的索引對于用戶查詢的查詢優化效果.

本文首先設計并實現了一個面向關系數據庫的智能索引調優系統,該系統可以直接應用于不同的關系數據庫的實例上;其次,提出了一種利用機器學習的方法來構造對索引進行有效性量化的模型,根據該模型,可以準確地對索引的查詢優化效果進行估計;接著設計了一種高效的最優索引選擇算法,實現快速地從候選索引空間中選擇最優的索引組合;最后,通過實驗測試不同場景下智能索引調優系統的調優性能.實驗結果表明:本文提出的技術可以在不同的場景下有效地對索引進行優化調節,從而實現數據庫系統高效的查詢性能.

1 相關工作

1.1 索引構建與優化方法

目前,最典型的索引設計與調節方法是由設計人員以離線的方式完成的.設計人員分析相應應用的具體查詢業務,對于業務中常用的讀查詢(select 查詢),對其查詢條件所包含的字段建立二級索引,從而提升數據庫系統的整體查詢性能[1,2,4].然而,通過離線方式一次性構建的索引不能對所有的查詢都具有查詢優化效果,尤其對于混合事務/分析處理(HTAP)的查詢需求.為了保證索引的有效性,設計人員需要長期地根據查詢日志對數據庫索引進行調優.顯然,由設計人員以離線的方式索引構建與調整需要很高的代價.

一些研究工作提出了自動索引調優的方法,該類方法避免了索引構建與調整過程中人工的參與,并且能夠自動地根據應用查詢日志來調整數據庫索引.現有的自動索引調優技術可以分為基于規則[5]與基于代價模型這兩類技術.MISA[5]利用的規則是構建索引的字段組合需要在查詢日志中滿足一定的出現頻率,它利用頻繁項挖掘算法Apriori 找到查詢日志中滿足頻率閾值的字段組合,然后在采樣得到的數據庫實例上再利用數據庫優化器來進行篩選,并在最終選擇的字段組合上建立二級索引.SOAR 是小米公司開發的一個用于SQL 智能優化與改寫的開源工具,同時也提供了索引調優的功能.SOAR 在通過查詢日志進行索引調優時,使用的規則是選擇滿足索引調用機制[10]的字段組合建立索引.基于規則的技術沒有考慮寫查詢(insert,update 與delete 查詢)引起的索引維護的代價,對于不同應用場景的索引調優需求,該類方法無法進行有效的索引調優.

基于代價模型的調優技術通過設計相應的收益-代價模型來選擇索引,根據查詢日志中包含的讀/寫查詢,綜合考慮了索引帶來的查詢優化效果與索引維護代價[11?14].該類方法的基本思路為:先通過查詢日志產生出候選索引(字段組合),然后利用設計的模型對索引進行查詢優化效果評估與維護代價評估.為了計算索引的查詢優化效果,現有方法都是通過調用數據庫系統的查詢優化器來實現的(對于給定的查詢,利用優化器比較索引存在與不存在這兩種情況下該查詢的查詢代價).然而實際的數據庫系統中,僅有SQL Server 能通過What-If 分析工具來實現類似的查詢代價比較[11],極大地限制了方法的可用性.另一方面,現有方法都未考慮數據庫實例中現有索引與數據分布對于查詢性能的影響.

此外,還有一些工作研究了減小索引優化時添加索引對于數據庫系統性能的影響[15?18].該類技術利用了增量索引構建的方法,其優先對某些數據表中的記錄構建(partially-built)索引,并設計相應的利用partially-built 索引的數據檢索算法,使得DBMS 可以利用部分建立好的索引來優化查詢性能.這類方法與數據庫系統的耦合度高,需要在特定的數據庫系統上修改內核模塊,并且大部分方法都是基于NoSQL 數據庫的技術,無法直接應用在關系數據庫上.

1.2 利用機器學習的數據庫查詢優化方法

現有一些工作利用機器學習的方法來估計數據庫查詢的代價(查詢時間).文獻[6]采用統計學習的方法來估計XML 查詢的查詢代價,其利用查詢的操作符級別的特征,并使用一種基于變換回歸(transform regression)的機器學習模型.文獻[7]采用統計學習的技術來預測當存在多查詢并發執行時,一組查詢集合的完成查詢所需的時間.文獻[8]所提出的方法則用于估計單個查詢的查詢時間,該方法考慮了查詢的查詢模板中的特征與查詢中操作符上的特征,并利用一種混合模型來同時使用這兩類特征.文獻[9]不僅可以預測查詢的完成時間,還可以用于預估查詢對于硬件資源的消耗(如I/O 次數).該方法使用了與文獻[8]類似的特征,并使用了一種基于回歸樹(regression tree)與尺度函數(scaling function)的混合模型.

2 智能索引調優系統框架

給定一個關系數據庫的實例,智能索引調優系統利用該數據庫實例上的一段時間窗口內的查詢日志進行索引調優.調優系統包含了3 個模塊,分別為查詢分析模塊、候選索引生成模塊與索引選擇模塊.圖1 所示為智能索引調優系統的總體框架.

Fig.1 Framework of the intelligent index tuning system
圖1 智能索引調優系統的總體框架

調優系統最終生成的索引調節語句(創建索引/刪除索引)會作用于數據庫實例上.由于數據庫實例的主鍵索引具有唯一性,修改主鍵索引可能會導致數據記錄無法通過主鍵字段進行唯一標識.因此,調優系統僅針對數據庫的二級索引(輔助索引)進行優化.圖2 所示為調優系統的各個模塊的詳細功能.

Fig.2 Functions ofdifferent modules in the intelligent index tuning system
圖2 智能索引調優系統的各個模塊的詳細功能

(1)查詢分析模塊

按照查詢對文件的操作方式分為讀查詢與寫查詢,本文考慮的讀查詢指僅包含Select 操作的查詢,包含Insert/Delete/Update 操作的查詢則為寫查詢.查詢分析模塊對查詢日志中的每一條查詢進行解析,解析過程包含詞法分析與語法分析兩個步驟,調優系統采用開源的詞法分析器Flex(GNU flex.free software foundation.https://www.gnu.org/software/flex/)與語法分析器Bison(GNU bison.free software foundation.https://www.gnu.org/software/bison/)來完成詞法分析與語法分析.在進行詞法/語法分析的時候,系統同時能檢驗解析的SQL 查詢是否符合查詢語言的詞法與語法規則.解析后的查詢可以表示為一個解析樹的形式,系統可以通過該結構獲取到相應查詢上的投影(select)、選擇(where)與排序(order by)操作使用到的字段組合.圖3 的示例為利用解析樹獲取查詢中字段組合((CNO,FNAME),(LNAME,CNO),FNAME).

Fig.3 An example of computing field collections from the parsing tree of a SQL query
圖3 利用解析樹獲取查詢中包含字段組合的示例

(2)候選索引生成模塊

對于查詢分析模塊產生的屬于同一個數據表上的字段集合,其任意字段的組合都可以作為候選索引.然而,并非對所有的字段組合建立索引都可以提升查詢的性能.例如,對于圖3 所示例子中獲得的字段集合,在字段組合(FNAME,LNAME)上建立索引不會對示例查詢產生查詢優化效果(即,對于該示例查詢,查詢優化器不會調用該索引).因此,為了獲得有效的字段組合,本系統利用文獻[10]提出的索引等級評價標準(即三星標準),對于查詢記錄中的每一條查詢,都產生滿足其任意星級標準的字段組合.其具體內容如下.

·第1 星索引:索引將相關的記錄放到一起,即Where 后面的等值謂詞關聯的列為組合索引的前綴;

·第2 星索引:索引中的數據順序和查找中的排列順序一致,即Order by 中字段需被包含在組合索引中,且順序一致;

·第3 星索引:索引中的列包含了查詢中需要的全部列(覆蓋索引).

例如,圖4 所示的示例中,IND_3 滿足第1 星索引,IND_4 滿足了第1 星與第3 星索引,IND_5 則滿足了第2星與第3 星索引.另一方面,對于一個查詢,只要該查詢的Where 條件中包含了一個索引的前綴字段(即前綴調用原則[10]),那么該查詢就可以利用該索引進行查詢優化.因此,一個查詢的Where 條件中包含字段的所有子集都被考慮為候選索引.圖4 所示的例子中,IND_1 與IND_2 均為由Where 條件中字段的子集產生的候選索引.

Fig.4 An example of producing candidate indice
圖4 產生候選索引的示例

雖然不同的數據庫系統或者不同的數據庫系統版本在系統實現上會存在差異,但上述介紹的索引調用機制對于不同的關系數據庫系統是一致的.

智能索引調優系統可以利用不同時段的查詢日志連續地對數據庫實例進行索引優化,因此,在進行一次索引優化之前,數據庫實例可能會包含已經建立的二級索引,這種實際存在于數據庫實例中的索引稱之為真實索引.上述方法通過查詢日志產生的實際不存在與數據庫實例中的候選索引(非真實索引)稱為虛擬索引.如圖2 中候選索引生成模塊所示,調優系統最終生成的候選索引中包含了兩類索引,即通過數據庫實例獲取到的真實索引與通過查詢日志獲取到的虛擬索引.

(3)索引選擇模塊

索引選擇模塊的功能為從候選索引中選擇一組索引總大小不超過用戶給定空間閾值B的索引集合.該模塊包含了兩個步驟:第1 步,通過定義索引實用值對索引的作用進行量化,并設計相應的模型來估計候選索引的實用值(詳見第3 節);第2 步,從候選索引集合中選擇一組滿足空間閾值B的具有最大實用值的索引集合,使得優化后的索引集合的查詢優化效果最大化(詳見第4 節).

3 索引查詢優化效果建模

由于不同的索引對于數據庫系統的查詢優化效果是不一樣的,甚至存在索引建立后會導致數據庫系統查詢性能降低的情況(由于索引存在維護代價).為了實現索引的調節優化,需要對索引的查詢優化效果進行量化.對于一個候選索引I,I的實用值代表了該索引對于數據庫系統在某個時間段內的查詢優化作用,表示為I.utility.本節先介紹索引實用值的具體內容,然后再介紹一種利用機器學習模型來估計索引實用值的方法.

3.1 索引實用值

給定查詢日志L,索引I對于L可獲得的實用值可通過公式(1)進行計算:

其中,Profit(I,q)表示索引I對于一個查詢q所能取得的查詢優化效果,I.build表示構建索引I所需要的時間代價.I.utility的計算考慮了I對于日志L中所有查詢的作用(本文假設數據庫系統未來處理的查詢與查詢日志L具有相同的特征,因此可利用L來計算索引的實用值.當未來處理的查詢與查詢日志L的特征不一致時,可通過查詢預測方法先得到預測后的查詢負載[19,20],再利用預測的查詢負載進行索引調優),并且還有構建I本身的代價.α與β為兩個取值范圍為[0,1]的因子,用于調節構建I的代價對于索引實用性的影響.α/β越大,則說明系統越傾向于索引帶來優化效果,而不是考慮構建I所需的代價.

候選索引中的真實索引由于已經存在于數據庫實例中,其I.build則為0.對于虛擬索引,I.build則是通過索引大小來進行估計的,即I.build=I.size?unit_cost,其中,I.size表示索引I的大小(真實索引大小可通過數據庫實例直接獲取到;對于虛擬索引,可以通過現有的估計模型進行計算(space needed for keys[21]),unit_cost為通過測試得到構建單位大小(1MB)索引所需的時間.

實際上會存在多種形式的指標來表示索引對于查詢的優化效果Profit(I,q),本文采用了查詢q在索引I存在與不存在這兩種情況下的執行時間差值來表示I的優化效果,即Profit(I,q)=time(q|I)?time(q|

).然而,Profit(I,q)是無法直接計算得到的,因為在索引調優階段,是無法將虛擬索引在數據庫實例中建立為真實索引的.因此,為了解決該問題,文本利用了機器學習的方法來預測Profit(I,q).該方法的基本思路為:先離線地通過訓練數據集訓練出一個反映查詢q、索引I與查詢優化效果Profit(I,q)映射關系的模型,再通過該模型來在線地對于給定I與q估計出對應的Profit(I,q),從而避免上述的索引構建問題.

3.2 利用機器學習預測索引優化效果

與許多現有利用機器學習的方法一樣,本文的方法也分為兩個階段:訓練階段和測試階段,如圖5 所示.

Fig.5 Phases of model training and testing
圖5 模型訓練與測試階段

訓練階段的目的為建立一個模型M來準確地反映出查詢q與索引I的特征值與目標值Profit(I,q)間的映射關系,即M(x1,x2,…,xk)→Profit(I,q).訓練階段首先需要進行數據采集,對于訓練數據(查詢集合與索引集合)中的每一組(I,q),測試在沒有任何索引情況下q的查詢時間與僅存在索引I情況下的查詢時間,該兩種情況下的查詢時間差值則為目標值Profit(I,q).由于不同的查詢與索引對于Profit(I,q)都是存在影響的,所以用于模型訓練的特征屬性需要同時從查詢q與索引I中進行抽取,本文所使用的特征屬性見表1.

Table 1 Feature attributes selected from the query and index
表1 查詢與索引中選取的特征屬性

表1 中所示的特征屬性都為查詢編譯階段可獲取到的屬性值,特征屬性可分為3 類,分別從查詢q與I中獲取到的屬性與通過q與I同時獲取到的屬性.其中,Q_type,Q_rows_num,Q_operator_num,I_rows_num,I_fields_num均為調優系統在查詢解析階段可獲取得到的屬性值,Q_est_rows與Q_est_cost為通過數據庫系統查詢優化器可獲得的屬性值(例如MySQL 下的EXPLAIN 命令).相比之下,Q_fields_code與I_fields_code的獲取則更為復雜,由于q與I所使用的字段信息都為字符串,為了得到可用作訓練數據的數值型屬性值,本文將數據庫實例中的表中所有字段按照某一順序進行排列,然后再將q與I中使用的字段按照該順序進行One-hot 編碼[22],則得到Q_fields_code與I_fields_code.最后,由于在查詢解析階段可以比較判斷:i)q是否滿足I的前綴調用原則;ii)q中更新的字段是否包含了I中的字段,因此可以獲得IO_invoking與IO_updating這兩個屬性值.

訓練階段的最后一步為利用機器學習方法進行模型訓練.本文使用了具有代表性的3 種方法來訓練模型.

·LR(linear regression)[23]:一種線性方法,數據使用線性預測函數來建模,并且未知的模型參數也是通過數據來估計.LR 的優點在于實現簡單,建模速度快,并且可以有效地防止過擬合;但同時,LR 對異常值較敏感,并且線性模型本身表達能力差;

·GBDT(gradient boosting decision tree)[24]:一種由多棵決策樹組成的用于回歸分析的算法,在許多應用場景下,其具有很高的預測精度.GBDT 的優點在于可處理各種類型的數據(包括連續值與離散值),并且具有良好的非線性擬合能力,以及對超參數的魯棒性;

·DNN(deep neural network)[25]:深度神經網絡為當前最流行的方法,其本質是通過前面多層的隱藏網絡學習抽象特征,在最后輸出層使用上述抽象得到的特征完成最終的學習任務.這種方式得到的特征可以較好地降低問題的非線性程度,從而具有非常強的擬合能力.

本文在實驗部分對上述方法進行了比較,并對比了訓練出來的3 種不同模型對索引優化的影響(詳見第5.2節).在測試階段,索引調優系統利用與訓練階段同樣的方法,從候選索引I與查詢q中提取出特征向量,然后調用訓練好的預測模型來預測I對于q的查詢優化效果Profit(I,q),從而計算得到每個候選索引的實用值(公式(1)).

4 最優索引組合選擇算法

4.1 最優索引選擇問題

如上一節所述,對于候選索引集合C中的候選索引I,其實用值為I.utility、大小為I.size.為了實現優化后的索引具有最優的查詢優化效果,調優系統需要選擇一組索引總大小滿足用戶給定閾值B且總的實用值最大的索引集合S′(即

＜B).顯然,該問題可以轉化為經典的0-1 背包問題[26].

設X為一組索引集合,y為存儲空間限制,U(X,y)表示在y的限制范圍內選取X中索引可獲得的最大的實用值.與0-1 背包問題類似,U(X,y)可以通過如下遞歸方式進行計算,其中,top(X)為集合X中的第1 個索引:

對于經典的0-1 背包問題,可以設計動態規劃算法在時間O(m?n)內求得最優解,其中,m為背包中物體的數目,n為背包的容量.對于本節所需要解決的問題,直接利用該動態規劃算法求解則會存在如下問題.

·當調優系統所處理的數據庫實例較大時,閾值B需設置較大的值.利用動態規劃算法實現自底向上的求解子問題需要枚舉每一種空間限制大小下的局部解,因此會導致很大的時間開銷.例如,當閾值B=1GB(空間大小粒度為1MB)、候選索引數目為1 000 時,計算的子問題數目為1024×1000;

·動態規劃算法計算的子問題中,大部分都與最終的最優解無關.

因此,本文設計了自頂向下計算子問題的遞歸算法,該算法僅遞歸地計算與最終最優解有關的子問題,避免了動態規劃算法導致的無關子問題的計算.同時,考慮到動態規劃算法的優點在于可以避免重復子問題的計算(子問題結果復用),為了避免自頂向下的遞歸算法帶來的重復子問題計算,本節提出了相應的技術解決遞歸算法中存在的重復子問題計算問題.

4.2 具有子問題復用的遞歸算法

在遞歸算法中實現子問題復用的基本思路為:對遞歸過程中計算過的子問題,利用哈希表存儲其結果,在計算新的子問題時,先通過哈希表判斷該子問題是否已經求解過.如哈希表中存在中間結果,則直接復用.

遞歸算法見算法1,其設計思路與遞歸公式(2)是一致的.算法的輸入為一組候選索引集合X與相應的大小閾值y,輸出為X中在滿足y閾值下的最大的實用值與相應的索引集合.算法1 首先判斷當前遞歸處理的候選索引集合是否為空:如果為空,則表明輸入的候選索引集合都已經處理完畢.

在X不為空時,算法會先對當前的X與y的組合求哈希值h(該值用于標識當前子問題),然后判斷哈希表H(全局變量)中是否存在h對應的結果:如果存在,說明當前子問題已經計算過,則直接返回哈希表中存儲的結果(算法1 中第2 行～第4 行);如果H中不存在當前子問題的結果,則進一步遞歸地計算兩類子問題,即X中舍棄了一個索引I與選擇了索引I的情況(第7 行與第9 行).最后,比較這兩類子問題所能取得的實用值大小,并且在哈希表H中記錄相應的結果作為當前子問題的結果(第11 行～第14 行).

由于算法1 利用哈希表避免了重復子問題的計算,其通過遞歸調用執行函數的次數最多為X?y次.此外,由于每次遞歸函數體中的執行操作復雜度為O(1),因此算法1 的時間復雜度為O(X?y).

算法1.最優索引選擇算法(OptIDXSelect).

利用上述算法,將候選索引集合C與用戶給定閾值B作為最初參數傳入算法1,即可計算得到具有最大實用值的最優索引集合S′.然而通過實際的實驗測試可以發現:對于相似的子問題(即X相同且y相近),其得到的子問題的解(索引組合)絕大多數的時候都是一樣的.例如,y1=991MB,y2=992MB,對于相同的候選索引集合X,{X,y1}與{X,y2}為兩個不同的在遞歸時需計算的子問題,但{X,y1}與{X,y2}所求出的最優索引集合是一樣的.之所以出現該現象,是因為少量的空間大小限制的變化對于求最優索引組合是沒有影響的.

基于上述觀察,本文進一步的提出了利用增大索引大小粒度來提升算法子問題復用能力的方法.設索引大小粒度為gran(默認為1MB),在算法1 中計算(X,y)的哈希值時(第2 行),將y除以gran來提升子問題復用的能力,即ComputeHash(X,y/gran).通過該方法,相似的子問題(即X相同且y/gran相同)的計算結果也可以進行復用.例如,在gran取10MB 時,{X,991MB}與{X,992MB}這兩個子問題得到的哈希值是一樣的,{X,991MB}下的最優索引組合計算完后,{X,992MB}可以直接利用{X,991MB}的計算結果.該方法雖然在小概率情況下會導致所求的索引組合不是具有最大實用值的索引集合,但其可以提升索引調優系統的時間性能,尤其在候選索引多且索引空間閾值B較大時.在第5 節,本文將通過實驗進一步對該方法的效果進行闡述.

5 實 驗

5.1 實驗設置

本文在MySQL 8.0 數據庫系統上進行了實驗測試,性能測試工具采用業界廣泛使用的TPCCMySQL 與OLTPBench.測試的數據庫實例為大小分別為1GB 與200MB 的兩個TPC-C 數據庫實例(TPC-C 數據庫實例采用的數據模型來自一個大型商品批發公司,其包含了9 個數據表用以支持5 類不同的交易事務).為了得到查詢日志,首先將MySQL 數據庫的日志記錄功能臨時打開,然后分別利用TPCCMySQL 與OLTPBench 在測試實例上進行了性能測試,這樣分別得到TPCCMySQL 與OLTPBench 產生的查詢日志.性能測試階段同樣使用了TPCCMySQL 與OLTPBench,測試參數設置均為c:4r:60l:600(即用戶數為4,預熱時長60s,測試時長600s).在實驗中,公式(1)中的參數α與β的取值分別為0.6 與0.4,表示調優系統在添加新的索引結構時,會同時考慮添加索引的帶來的查詢優化效果與索引構建的代價,但更側重于添加索引的優化效果.

在默認條件下,TPCCMySQL 與OLTPBench 會根據TPC-C 實例信息來生成查詢,并且生成查詢的查詢條件都可利用到對應表上的主鍵索引(在默認主鍵索引設置情況下,該工具產生的查詢利用主鍵索引已經達到了最優的查詢優化效果).因此,為了測試索引調優的效果,本文實驗分別選擇3 種主鍵索引設置下的場景,從而使得測試工具生成的查詢可通過建立二級索引進一步的提升查詢性能.表2 所示為TPC-C 數據庫實例上的3 種不同的主鍵索引設置.

Table 2 Different settings for primary keys in the DB instance
表2 數據庫實例中不同的主鍵索引設置

TPCCMySQL 工具產生的查詢日志包含了7 763 條查詢記錄,其中,不同類別的查詢占比分別為:Select 61.67%,Delete 1.23%,Update 21.01%,Insert 16.09%(該比例由TPCCMySQL 使用的查詢事務比例所決定).此外,查詢日志中,98.5%為單表查詢,1.5%為多表查詢.OLTPBench 工具則可通過變化事務的比例來產生不同查詢類別占比的查詢日志(詳細信息見第5.2 節中的第3 個實驗).本節所有實驗均使用TPCCMySQL 作為性能測試工具,性能測試指標為數據庫系統的吞吐量(TPS,每秒執行的事務數).

用于測試的數據庫實例部署在一臺ThinkServer 服務器上(配置為Intel Xeon E3-1226 3.30GHz 處理器,16GB 內存,500GB SSD),索引調優系統部署在一臺Dell PC 上(配置為IntelCore i7-8700 3.2GHz 處理器,8GB 內存,256GB SSD),調優系統通過遠程連接數據庫實例獲取到實例信息與索引的調節.索引調優系統通過C++語言編寫與實現,估計模型通過PyTorch 框架來編寫,并將訓練得到的模型存儲到本地,再由調優程序進行調用.

5.2 實驗結果及分析

(1)不同索引調優方法調優性能對比

第1 個實驗對比了不同的索引調優方法的性能.對比的方法中,Baseline 為使用對應的主鍵索引設置的方法.由于現有的索引調優/推薦方法中,大部分都依賴查詢優化器來實現索引作用的估計,無法應用在MySQL 數據庫系統上,因此,本文僅使用了開源的SQL 優化器SOAR(SQL optimizer and rewriter.Xiao Mi.https://github.com/xiaomi/soar)作為對比方法,其無需依賴查詢優化器完成索引調優,并且對比方法不考慮索引大小的約束限制.SmartIndex 為本文所提出方法(默認情況下,SmartIndex 使用DNN 來訓練索引查詢優化效果的估計模型,不同預測模型的對比測試結果如下一個實驗所示).

圖6(a)所示為數據庫實例大小為1GB 時,不同方法的對比結果.SmartIndex 分別測試了索引空間閾值設置為100MB,300MB 與500MB 時的調優效果.通過實驗結果可以發現:相較于Baseline 方法,SOAR 與SmartIndex方法在索引調節后都取得了更好的查詢性能,并且 SmartIndex 的索引調優效果要優于 SOAR.例如,在PrimarySetting1 下,系統在利用SOAR 方法調優后的吞吐量提升到了1 200.相較之下,經過SmartIndex(索引大小閾值B設置為500MB)調優后,吞吐量則提升到了5 993.在大小為200MB 的數據庫實例上也得到了相似的實驗結果,如圖6(b)所示.例如,在PrimarySetting3 下,經過SmartIndex(閾值B=500MB)調優后,數據庫系統的吞吐量從190 提升到了12 778.由于圖6(b)中的實驗所用數據庫實例要小于圖6(a)實驗中的實例,因此圖6(b)中實驗所獲得的吞吐量要明顯高于圖 6(a)中的實驗結果.另一方面,通過比較 PrimarySetting1,PrimarySetting2 與PrimarySetting3 下的實驗結果可以發現,SmartIndex 在不同的主鍵索引設置下都具有很好的調優效果.

此外,圖6 所示實驗還測試了不同索引大小閾值B對于索引調優的影響.實驗結果顯示:SmartIndex 在越大的索引大小閾值下,可以取得越好的查詢性能.例如,在圖6(a)中的PrimarySetting1 下,當閾值B的值從100MB增加到500MB 時,系統的吞吐量從4 820 增加到了5 993.這是因為閾值B越大的情況下,系統可以建立更多有效的索引,從而更多的查詢可以利用索引來提升查詢性能.

Fig.6 Comparison on the tuning performance of different index tuning methods
圖6 不同調優方法的調優性能對比

(2)索引優化作用估計模型測試

第2 個實驗測試了不同估計模型訓練算法對于索引調優效果的影響.本實驗所對比的模型訓練方法為LR,GDBT 與DNN(如第3.2 節所述).對于LR 方法,實驗使用了前向特征選擇(forward feature selection)[27]的方法來選擇特征屬性,從而使得LR 訓練的模型達到了最高的準確率.DNN 算法使用了2 層隱藏層,并且使用Adam 算法作為優化器.為了進行數據采集,實驗利用TPCCMySQL 產生了2 000 條的查詢日志集合,并且在TPC-C 數據庫實例上建立了80 個不同的索引.對于一個查詢q與索引I,為了測試得到Profit(q,I),實驗分別在不包含任何索引的數據表與僅包含I的同一數據表上進行了性能測試,然后求兩種情況下的執行之間的差值.最終,實驗采集得到160 000 條具有真實目標值的數據,并將數據按照7:3 的比例劃分成訓練數據與測試數據.

由于絕對誤差的度量方式存在個別數據誤差影響整體誤差的問題,為了度量預測模型的準確性,本文使用了文獻[19]中定義的平均相對錯誤率作為度量標準,公式(3)所示為平均相對錯誤率的計算方式:

首先,實驗在測試數據上利用3 種方法訓練出來的模型進行了預測測試,實驗結果見表3 中第1 行數據所示.DNN 的模型獲得了最低的相對錯誤率,僅為32.6%;LR 的模型的錯誤率最高,達到了53.1%.實驗進一步比較了不同模型用于索引調優時的效果,測試所用數據庫實例大小為1GB,SmartIndex 設置的索引大小閾值B為300MB.實驗結果顯示:由于DNN 的模型具有最高的預測準確率,因此使用該模型進行索引調優后獲得了最大的吞吐量.此外,雖然LR 與GDBT 模型的錯誤率要明顯高于DNN 的錯誤率,但利用該模型取得的TPS差距卻要小一些.例如,在PrimarySetting1 下,利用LR 與DNN 的方法取得TPS最大差距也僅有24.5%.出現該現象的原因是:不同的查詢與索引利用同一預測模型后得到的目標值都會存在一定誤差,但不同索引估計得到的實用值間的相對關系卻是正確的.因此,利用本文所提出的索引選擇方法(見第4 節)仍能選擇出有效的索引組合.

Table 3 Comparison for the models trained by different learning algorithms
表3 不同算法訓練得到的預測模型的性能比較

(3)不同類型查詢占比對調優性能影響測試

由于寫查詢(增刪改)可能會導致索引的更新,因此不同的查詢類型對于索引的查詢優化效果會存在影響.為了測試不同查詢集合對于參數調優的影響,第3 個實驗采用OLTPBench 工具來產生查詢日志并且進行性能測試(OLTPBench 可以通過調節事務比例來產生不同類別的查詢).表4 所示為OLTPBench 產生的3 組不同的查詢日志,3 組查詢日志中包含的Select 查詢占比分別為85.12%,62.64%與49.80%,其分別代表了讀密集型查詢、混合類型查詢與寫密集型查詢.

Table 4 Three different query work load generated by OLTPBench
表4 OLTPBench 產生的3 組不同的查詢日志

圖7 所示為利用SmartIndex 方法進行索引調優后(Baseline 為PrimarySetting1),通過OLTPBench 進行性能測試得到的實驗結果(性能測試的查詢類別比例與生成查詢日志中的查詢類別比例一致).隨著寫查詢比例的增加,通過索引調優后的數據庫系統的吞吐量是降低的.例如,SmartIndex(B=300MB)在query workload1 與query workload3 調優后得到的系統吞吐量分別為1 585 與518.出現這種現象的原因是:更多的寫查詢會增加索引的更新維護代價,從而降低了整體的吞吐量.此外,實驗結果還顯示:在寫查詢比例增加后,增大索引閾值所能提升的查詢性能是降低的.這是因為在寫查詢比例高的時候,即使允許建立更多的索引,但由于索引更新維護代價的增加,SmartIndex 也無法選擇出新的具有查詢優化效果的索引.

Fig.7 Impact of different query workloads for the effect of index tuning
圖7 不同類型的查詢集合對于調優性能的影響

(4)索引選擇算法對比

本文最后一個實驗測試了第4 節提出的索引選擇算法的效果.實驗在1GB 的TPC-C 數據庫實例上利用TPCCMySQL 性能測試工具,測試對比了貪心算法Greedy(優先選擇單位實用值高的索引,即I.utility/I.size)、動態規劃算法DP 與本文提出的OptIDXSelect 算法,同時還對比了OptIDXSelect 算法在索引大小粒度gran設置為10MB 與100MB 下的效果.

圖8 與圖9 所示分別為不同索引選擇算法得到的索引調優效果與推薦索引所需的時間.

Fig.8 Comparison on the effect of index tuning for different index selection algorithms
圖8 不同索引選擇算法的索引選擇效果對比

Fig.9 Comparison on the time of computing optimized indices for different index selection algorithms
圖9 不同索引選擇算法完成索引推薦的時間對比

通過圖8 實驗結果可以發現,DP 與OptIDXSelect 所選擇索引的優化效果要優于Greedy 方法所選擇的索引.例如,在PrimarySetting1 下,Greedy,DP 與OptIDXSelect 選擇的索引得到的吞吐量分別為4 113,5 377 與5 377.同時需注意到:DP 與OptIDXSelect 方法由于都是選擇一組具有最大實用值的索引,因此它們得到的吞吐量是一致的.OptIDXSelect 算法在設置索引大小粒度gran后,所選擇的索引獲得的吞吐量有所下降.這是因為設置gran的目的是加快索引的選擇,但同時不能保證選擇的索引取得最大的實用值.

圖9 進一步反映了各種方法在選擇索引上的時間效率.顯然,由于Greedy 使用了貪心策略,其選擇索引花費的時間是最少的.比較DP 與OptIDXSelect 這兩個可以取得最優解的方法,OptIDXSelect 的時間效率要明顯優于DP.OptIDXSelect(gran=10MB)相比于OptIDXSelect 獲得的吞吐量相差很小,但是其選擇索引的效率卻要遠高于 OptIDXSelect 方法.例如,在 PrimarySetting1 下,Greedy,DP,OptIDXSelect,OptIDXSelect(gran=10MB)還有OptIDXSelect (gran=100MB)用于選擇索引花費的時間分別為221ms,43792ms,3388ms,774ms 與367ms.雖然當前實驗測試不同算法差距最大的也僅為43571ms,但在需要連續的通過查詢日志進行索引調優,并且日志中包含大量查詢的時候,選擇高效的算法來完成索引選擇仍非常重要.

6 總結與未來的工作

索引是數據庫系統實現高效的查詢性能的方式之一,智能地對數據庫實例構建并調節索引,不僅能夠保證高效的查詢性能,還能有效地提高硬件資源利用率與減少人力成本的投入.本文研究了面向關系數據庫的智能索引調優方法.首先,本文設計并實現了一個面向關系數據庫的智能索引調優系統;在索引調節時,為了準確地估計索引對于查詢的查詢優化效果并選擇正確的索引,本文設計了一種使用機器學習方法來對索引的查詢優化效果建模的方法;為了最大化索引的調優效果,本文進一步地設計了一種高效的最優索引組合選擇算法,并提出了優化技術來提升索引選擇的效率;最后設計了一系列的實驗對索引調優的各個環節進行了測試.結果表明:本文設計的系統可以在不同的場景下有效地對索引進行調優,從而提升數據庫系統的查詢性能.

利用智能技術優化數據庫索引具有很大的研究空間,未來的工作中將從以下3 個方面展開:首先,探索利用混合模型來提高索引查詢優化效果的估計準確性;其次,由于同一查詢可能利用上不同的索引來提升查詢效率,通過考慮不同索引間的相互影響,進一步提升索引選擇的質量;最后,進一步對比研究回歸任務與分類任務對于索引優化效果估計的影響.