面向關(guān)系數(shù)據(jù)庫(kù)的智能索引調(diào)優(yōu)方法

面向關(guān)系數(shù)據(jù)庫(kù)的智能索引調(diào)優(yōu)方法

來(lái)源：《軟件學(xué)報(bào)》，作者邱 濤等

摘 要:數(shù)據(jù)庫(kù)索引是關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)快速查詢的有效方式之一.智能索引調(diào)優(yōu)技術(shù)可以有效地對(duì)數(shù)據(jù)庫(kù)實(shí)例進(jìn)行索引調(diào)節(jié),從而保持?jǐn)?shù)據(jù)庫(kù)高效的查詢性能.現(xiàn)有的方法大多利用了數(shù)據(jù)庫(kù)實(shí)例的查詢?nèi)罩?它們先從查詢?nèi)罩局械玫胶蜻x索引,再利用人工設(shè)計(jì)的模型選擇索引,從而調(diào)節(jié)索引.然而,從查詢?nèi)罩局挟a(chǎn)生出的候選索引可能并未實(shí)際存在于數(shù)據(jù)庫(kù)實(shí)例中,因此導(dǎo)致這些方法不能有效地估計(jì)這類索引對(duì)于查詢的優(yōu)化效果.首先,設(shè)計(jì)并實(shí)現(xiàn)了一種面向關(guān)系數(shù)據(jù)庫(kù)的智能索引調(diào)優(yōu)系統(tǒng);其次,提出了一種利用機(jī)器學(xué)習(xí)方法來(lái)構(gòu)造索引的量化模型,根據(jù)該模型,可以準(zhǔn)確地對(duì)索引的查詢優(yōu)化效果進(jìn)行估計(jì);接著設(shè)計(jì)了一種高效的最優(yōu)索引選擇算法,實(shí)現(xiàn)快速地從候選索引空間中選擇滿足給定大小約束的最優(yōu)的索引組合;最后,通過實(shí)驗(yàn)測(cè)試不同場(chǎng)景下智能索引調(diào)優(yōu)系統(tǒng)的調(diào)優(yōu)性能.實(shí)驗(yàn)結(jié)果表明,所提出的技術(shù)可以在不同的場(chǎng)景下有效地對(duì)索引進(jìn)行優(yōu)化,從而實(shí)現(xiàn)數(shù)據(jù)庫(kù)系統(tǒng)查詢性能的提升.

關(guān)鍵詞:索引調(diào)優(yōu);機(jī)器學(xué)習(xí);數(shù)據(jù)庫(kù)索引;優(yōu)化模型;關(guān)系數(shù)據(jù)庫(kù)

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

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

智能索引調(diào)優(yōu)技術(shù)可以解決人工設(shè)計(jì)索引存在的問題,該技術(shù)通過對(duì)應(yīng)用的查詢?nèi)罩具M(jìn)行分析,動(dòng)態(tài)地對(duì)數(shù)據(jù)庫(kù)實(shí)例的索引進(jìn)行調(diào)整,使其對(duì)與查詢?nèi)罩局芯哂邢嗨铺卣鞯牟樵兲峁└咝У牟樵冃阅?現(xiàn)有的調(diào)優(yōu)技術(shù)可以分為基于規(guī)則和基于代價(jià)模型的兩類.基于規(guī)則的調(diào)優(yōu)技術(shù)利用特定的規(guī)則(例如滿足出現(xiàn)頻率的字段組合[5]、滿足索引調(diào)用機(jī)制的字段組合)從查詢?nèi)罩局挟a(chǎn)生出推薦的索引集合,如果推薦索引未存在于數(shù)據(jù)庫(kù)實(shí)例中,則直接在實(shí)例中建立該索引.這類方法僅考慮了利用索引能帶來(lái)的查詢優(yōu)化效果,未考慮維護(hù)索引所需的代價(jià).尤其對(duì)于當(dāng)前常見的混合事務(wù)/分析處理(HTAP)的應(yīng)用,這類方法無(wú)法有效地調(diào)節(jié)索引.基于代價(jià)模型的調(diào)優(yōu)技術(shù)則進(jìn)一步考慮了維護(hù)索引所需的代價(jià),通過設(shè)計(jì)相應(yīng)的收益-代價(jià)模型,選擇查詢優(yōu)化收益大于維護(hù)代價(jià)的索引.然而,從查詢?nèi)罩局挟a(chǎn)生的推薦索引可能并未實(shí)際存在于數(shù)據(jù)庫(kù)實(shí)例中,現(xiàn)有的基于代價(jià)模型的方法不能準(zhǔn)確地估計(jì)這類索引的查詢優(yōu)化效果與維護(hù)代價(jià);同時(shí),該類方法未考慮數(shù)據(jù)庫(kù)實(shí)例中現(xiàn)有索引與數(shù)據(jù)分布對(duì)于查詢性能的影響,致使其無(wú)法有效的進(jìn)行索引調(diào)節(jié).

另一方面,機(jī)器學(xué)習(xí)已經(jīng)廣泛地應(yīng)用于各個(gè)領(lǐng)域.現(xiàn)有的技術(shù)已經(jīng)利用了機(jī)器學(xué)習(xí)的方法來(lái)實(shí)現(xiàn)數(shù)據(jù)庫(kù)的查詢優(yōu)化.例如,相比于傳統(tǒng)的利用人工設(shè)計(jì)的模型,通過機(jī)器學(xué)習(xí)的方法可以更加準(zhǔn)確地估計(jì)各種場(chǎng)景下的查詢執(zhí)行時(shí)間與資源消耗[6?9].本文針對(duì)上述基于模型的索引調(diào)優(yōu)技術(shù)所存在的問題,提出了利用了機(jī)器學(xué)習(xí)的方法來(lái)預(yù)測(cè)不同的索引對(duì)于用戶查詢的查詢優(yōu)化效果.

本文首先設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)面向關(guān)系數(shù)據(jù)庫(kù)的智能索引調(diào)優(yōu)系統(tǒng),該系統(tǒng)可以直接應(yīng)用于不同的關(guān)系數(shù)據(jù)庫(kù)的實(shí)例上;其次,提出了一種利用機(jī)器學(xué)習(xí)的方法來(lái)構(gòu)造對(duì)索引進(jìn)行有效性量化的模型,根據(jù)該模型,可以準(zhǔn)確地對(duì)索引的查詢優(yōu)化效果進(jìn)行估計(jì);接著設(shè)計(jì)了一種高效的最優(yōu)索引選擇算法,實(shí)現(xiàn)快速地從候選索引空間中選擇最優(yōu)的索引組合;最后,通過實(shí)驗(yàn)測(cè)試不同場(chǎng)景下智能索引調(diào)優(yōu)系統(tǒng)的調(diào)優(yōu)性能.實(shí)驗(yàn)結(jié)果表明:本文提出的技術(shù)可以在不同的場(chǎng)景下有效地對(duì)索引進(jìn)行優(yōu)化調(diào)節(jié),從而實(shí)現(xiàn)數(shù)據(jù)庫(kù)系統(tǒng)高效的查詢性能.

1 相關(guān)工作

1.1 索引構(gòu)建與優(yōu)化方法

目前,最典型的索引設(shè)計(jì)與調(diào)節(jié)方法是由設(shè)計(jì)人員以離線的方式完成的.設(shè)計(jì)人員分析相應(yīng)應(yīng)用的具體查詢業(yè)務(wù),對(duì)于業(yè)務(wù)中常用的讀查詢(select 查詢),對(duì)其查詢條件所包含的字段建立二級(jí)索引,從而提升數(shù)據(jù)庫(kù)系統(tǒng)的整體查詢性能[1,2,4].然而,通過離線方式一次性構(gòu)建的索引不能對(duì)所有的查詢都具有查詢優(yōu)化效果,尤其對(duì)于混合事務(wù)/分析處理(HTAP)的查詢需求.為了保證索引的有效性,設(shè)計(jì)人員需要長(zhǎng)期地根據(jù)查詢?nèi)罩緦?duì)數(shù)據(jù)庫(kù)索引進(jìn)行調(diào)優(yōu).顯然,由設(shè)計(jì)人員以離線的方式索引構(gòu)建與調(diào)整需要很高的代價(jià).

一些研究工作提出了自動(dòng)索引調(diào)優(yōu)的方法,該類方法避免了索引構(gòu)建與調(diào)整過程中人工的參與,并且能夠自動(dòng)地根據(jù)應(yīng)用查詢?nèi)罩緛?lái)調(diào)整數(shù)據(jù)庫(kù)索引.現(xiàn)有的自動(dòng)索引調(diào)優(yōu)技術(shù)可以分為基于規(guī)則[5]與基于代價(jià)模型這兩類技術(shù).MISA[5]利用的規(guī)則是構(gòu)建索引的字段組合需要在查詢?nèi)罩局袧M足一定的出現(xiàn)頻率,它利用頻繁項(xiàng)挖掘算法Apriori 找到查詢?nèi)罩局袧M足頻率閾值的字段組合,然后在采樣得到的數(shù)據(jù)庫(kù)實(shí)例上再利用數(shù)據(jù)庫(kù)優(yōu)化器來(lái)進(jìn)行篩選,并在最終選擇的字段組合上建立二級(jí)索引.SOAR 是小米公司開發(fā)的一個(gè)用于SQL 智能優(yōu)化與改寫的開源工具,同時(shí)也提供了索引調(diào)優(yōu)的功能.SOAR 在通過查詢?nèi)罩具M(jìn)行索引調(diào)優(yōu)時(shí),使用的規(guī)則是選擇滿足索引調(diào)用機(jī)制[10]的字段組合建立索引.基于規(guī)則的技術(shù)沒有考慮寫查詢(insert,update 與delete 查詢)引起的索引維護(hù)的代價(jià),對(duì)于不同應(yīng)用場(chǎng)景的索引調(diào)優(yōu)需求,該類方法無(wú)法進(jìn)行有效的索引調(diào)優(yōu).

基于代價(jià)模型的調(diào)優(yōu)技術(shù)通過設(shè)計(jì)相應(yīng)的收益-代價(jià)模型來(lái)選擇索引,根據(jù)查詢?nèi)罩局邪淖x/寫查詢,綜合考慮了索引帶來(lái)的查詢優(yōu)化效果與索引維護(hù)代價(jià)[11?14].該類方法的基本思路為:先通過查詢?nèi)罩井a(chǎn)生出候選索引(字段組合),然后利用設(shè)計(jì)的模型對(duì)索引進(jìn)行查詢優(yōu)化效果評(píng)估與維護(hù)代價(jià)評(píng)估.為了計(jì)算索引的查詢優(yōu)化效果,現(xiàn)有方法都是通過調(diào)用數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化器來(lái)實(shí)現(xiàn)的(對(duì)于給定的查詢,利用優(yōu)化器比較索引存在與不存在這兩種情況下該查詢的查詢代價(jià)).然而實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)中,僅有SQL Server 能通過What-If 分析工具來(lái)實(shí)現(xiàn)類似的查詢代價(jià)比較[11],極大地限制了方法的可用性.另一方面,現(xiàn)有方法都未考慮數(shù)據(jù)庫(kù)實(shí)例中現(xiàn)有索引與數(shù)據(jù)分布對(duì)于查詢性能的影響.

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

1.2 利用機(jī)器學(xué)習(xí)的數(shù)據(jù)庫(kù)查詢優(yōu)化方法

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

2 智能索引調(diào)優(yōu)系統(tǒng)框架

給定一個(gè)關(guān)系數(shù)據(jù)庫(kù)的實(shí)例,智能索引調(diào)優(yōu)系統(tǒng)利用該數(shù)據(jù)庫(kù)實(shí)例上的一段時(shí)間窗口內(nèi)的查詢?nèi)罩具M(jìn)行索引調(diào)優(yōu).調(diào)優(yōu)系統(tǒng)包含了3 個(gè)模塊,分別為查詢分析模塊、候選索引生成模塊與索引選擇模塊.圖1 所示為智能索引調(diào)優(yōu)系統(tǒng)的總體框架.

Fig.1 Framework of the intelligent index tuning system
圖1 智能索引調(diào)優(yōu)系統(tǒng)的總體框架

調(diào)優(yōu)系統(tǒng)最終生成的索引調(diào)節(jié)語(yǔ)句(創(chuàng)建索引/刪除索引)會(huì)作用于數(shù)據(jù)庫(kù)實(shí)例上.由于數(shù)據(jù)庫(kù)實(shí)例的主鍵索引具有唯一性,修改主鍵索引可能會(huì)導(dǎo)致數(shù)據(jù)記錄無(wú)法通過主鍵字段進(jìn)行唯一標(biāo)識(shí).因此,調(diào)優(yōu)系統(tǒng)僅針對(duì)數(shù)據(jù)庫(kù)的二級(jí)索引(輔助索引)進(jìn)行優(yōu)化.圖2 所示為調(diào)優(yōu)系統(tǒng)的各個(gè)模塊的詳細(xì)功能.

Fig.2 Functions ofdifferent modules in the intelligent index tuning system
圖2 智能索引調(diào)優(yōu)系統(tǒng)的各個(gè)模塊的詳細(xì)功能

(1)查詢分析模塊

按照查詢對(duì)文件的操作方式分為讀查詢與寫查詢,本文考慮的讀查詢指僅包含Select 操作的查詢,包含Insert/Delete/Update 操作的查詢則為寫查詢.查詢分析模塊對(duì)查詢?nèi)罩局械拿恳粭l查詢進(jìn)行解析,解析過程包含詞法分析與語(yǔ)法分析兩個(gè)步驟,調(diào)優(yōu)系統(tǒng)采用開源的詞法分析器Flex(GNU flex.free software foundation.https://www.gnu.org/software/flex/)與語(yǔ)法分析器Bison(GNU bison.free software foundation.https://www.gnu.org/software/bison/)來(lái)完成詞法分析與語(yǔ)法分析.在進(jìn)行詞法/語(yǔ)法分析的時(shí)候,系統(tǒng)同時(shí)能檢驗(yàn)解析的SQL 查詢是否符合查詢語(yǔ)言的詞法與語(yǔ)法規(guī)則.解析后的查詢可以表示為一個(gè)解析樹的形式,系統(tǒng)可以通過該結(jié)構(gòu)獲取到相應(yīng)查詢上的投影(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)候選索引生成模塊

對(duì)于查詢分析模塊產(chǎn)生的屬于同一個(gè)數(shù)據(jù)表上的字段集合,其任意字段的組合都可以作為候選索引.然而,并非對(duì)所有的字段組合建立索引都可以提升查詢的性能.例如,對(duì)于圖3 所示例子中獲得的字段集合,在字段組合(FNAME,LNAME)上建立索引不會(huì)對(duì)示例查詢產(chǎn)生查詢優(yōu)化效果(即,對(duì)于該示例查詢,查詢優(yōu)化器不會(huì)調(diào)用該索引).因此,為了獲得有效的字段組合,本系統(tǒng)利用文獻(xiàn)[10]提出的索引等級(jí)評(píng)價(jià)標(biāo)準(zhǔn)(即三星標(biāo)準(zhǔn)),對(duì)于查詢記錄中的每一條查詢,都產(chǎn)生滿足其任意星級(jí)標(biāo)準(zhǔn)的字段組合.其具體內(nèi)容如下.

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

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

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

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

Fig.4 An example of producing candidate indice
圖4 產(chǎn)生候選索引的示例

雖然不同的數(shù)據(jù)庫(kù)系統(tǒng)或者不同的數(shù)據(jù)庫(kù)系統(tǒng)版本在系統(tǒng)實(shí)現(xiàn)上會(huì)存在差異,但上述介紹的索引調(diào)用機(jī)制對(duì)于不同的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)是一致的.

智能索引調(diào)優(yōu)系統(tǒng)可以利用不同時(shí)段的查詢?nèi)罩具B續(xù)地對(duì)數(shù)據(jù)庫(kù)實(shí)例進(jìn)行索引優(yōu)化,因此,在進(jìn)行一次索引優(yōu)化之前,數(shù)據(jù)庫(kù)實(shí)例可能會(huì)包含已經(jīng)建立的二級(jí)索引,這種實(shí)際存在于數(shù)據(jù)庫(kù)實(shí)例中的索引稱之為真實(shí)索引.上述方法通過查詢?nèi)罩井a(chǎn)生的實(shí)際不存在與數(shù)據(jù)庫(kù)實(shí)例中的候選索引(非真實(shí)索引)稱為虛擬索引.如圖2 中候選索引生成模塊所示,調(diào)優(yōu)系統(tǒng)最終生成的候選索引中包含了兩類索引,即通過數(shù)據(jù)庫(kù)實(shí)例獲取到的真實(shí)索引與通過查詢?nèi)罩精@取到的虛擬索引.

(3)索引選擇模塊

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

3 索引查詢優(yōu)化效果建模

由于不同的索引對(duì)于數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化效果是不一樣的,甚至存在索引建立后會(huì)導(dǎo)致數(shù)據(jù)庫(kù)系統(tǒng)查詢性能降低的情況(由于索引存在維護(hù)代價(jià)).為了實(shí)現(xiàn)索引的調(diào)節(jié)優(yōu)化,需要對(duì)索引的查詢優(yōu)化效果進(jìn)行量化.對(duì)于一個(gè)候選索引I,I的實(shí)用值代表了該索引對(duì)于數(shù)據(jù)庫(kù)系統(tǒng)在某個(gè)時(shí)間段內(nèi)的查詢優(yōu)化作用,表示為I.utility.本節(jié)先介紹索引實(shí)用值的具體內(nèi)容,然后再介紹一種利用機(jī)器學(xué)習(xí)模型來(lái)估計(jì)索引實(shí)用值的方法.

3.1 索引實(shí)用值

給定查詢?nèi)罩?i>L,索引I對(duì)于L可獲得的實(shí)用值可通過公式(1)進(jìn)行計(jì)算:

其中,Profit(I,q)表示索引I對(duì)于一個(gè)查詢q所能取得的查詢優(yōu)化效果,I.build表示構(gòu)建索引I所需要的時(shí)間代價(jià).I.utility的計(jì)算考慮了I對(duì)于日志L中所有查詢的作用(本文假設(shè)數(shù)據(jù)庫(kù)系統(tǒng)未來(lái)處理的查詢與查詢?nèi)罩?i>L具有相同的特征,因此可利用L來(lái)計(jì)算索引的實(shí)用值.當(dāng)未來(lái)處理的查詢與查詢?nèi)罩?i>L的特征不一致時(shí),可通過查詢預(yù)測(cè)方法先得到預(yù)測(cè)后的查詢負(fù)載[19,20],再利用預(yù)測(cè)的查詢負(fù)載進(jìn)行索引調(diào)優(yōu)),并且還有構(gòu)建I本身的代價(jià).α與β為兩個(gè)取值范圍為[0,1]的因子,用于調(diào)節(jié)構(gòu)建I的代價(jià)對(duì)于索引實(shí)用性的影響.α/β越大,則說明系統(tǒng)越傾向于索引帶來(lái)優(yōu)化效果,而不是考慮構(gòu)建I所需的代價(jià).

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

實(shí)際上會(huì)存在多種形式的指標(biāo)來(lái)表示索引對(duì)于查詢的優(yōu)化效果Profit(I,q),本文采用了查詢q在索引I存在與不存在這兩種情況下的執(zhí)行時(shí)間差值來(lái)表示I的優(yōu)化效果,即Profit(I,q)=time(q|I)?time(q|

).然而,Profit(I,q)是無(wú)法直接計(jì)算得到的,因?yàn)樵谒饕{(diào)優(yōu)階段,是無(wú)法將虛擬索引在數(shù)據(jù)庫(kù)實(shí)例中建立為真實(shí)索引的.因此,為了解決該問題,文本利用了機(jī)器學(xué)習(xí)的方法來(lái)預(yù)測(cè)Profit(I,q).該方法的基本思路為:先離線地通過訓(xùn)練數(shù)據(jù)集訓(xùn)練出一個(gè)反映查詢q、索引I與查詢優(yōu)化效果Profit(I,q)映射關(guān)系的模型,再通過該模型來(lái)在線地對(duì)于給定I與q估計(jì)出對(duì)應(yīng)的Profit(I,q),從而避免上述的索引構(gòu)建問題.

3.2 利用機(jī)器學(xué)習(xí)預(yù)測(cè)索引優(yōu)化效果

與許多現(xiàn)有利用機(jī)器學(xué)習(xí)的方法一樣,本文的方法也分為兩個(gè)階段:訓(xùn)練階段和測(cè)試階段,如圖5 所示.

Fig.5 Phases of model training and testing
圖5 模型訓(xùn)練與測(cè)試階段

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

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

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

訓(xùn)練階段的最后一步為利用機(jī)器學(xué)習(xí)方法進(jìn)行模型訓(xùn)練.本文使用了具有代表性的3 種方法來(lái)訓(xùn)練模型.

·LR(linear regression)[23]:一種線性方法,數(shù)據(jù)使用線性預(yù)測(cè)函數(shù)來(lái)建模,并且未知的模型參數(shù)也是通過數(shù)據(jù)來(lái)估計(jì).LR 的優(yōu)點(diǎn)在于實(shí)現(xiàn)簡(jiǎn)單,建模速度快,并且可以有效地防止過擬合;但同時(shí),LR 對(duì)異常值較敏感,并且線性模型本身表達(dá)能力差;

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

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

本文在實(shí)驗(yàn)部分對(duì)上述方法進(jìn)行了比較,并對(duì)比了訓(xùn)練出來(lái)的3 種不同模型對(duì)索引優(yōu)化的影響(詳見第5.2節(jié)).在測(cè)試階段,索引調(diào)優(yōu)系統(tǒng)利用與訓(xùn)練階段同樣的方法,從候選索引I與查詢q中提取出特征向量,然后調(diào)用訓(xùn)練好的預(yù)測(cè)模型來(lái)預(yù)測(cè)I對(duì)于q的查詢優(yōu)化效果Profit(I,q),從而計(jì)算得到每個(gè)候選索引的實(shí)用值(公式(1)).

4 最優(yōu)索引組合選擇算法

4.1 最優(yōu)索引選擇問題

如上一節(jié)所述,對(duì)于候選索引集合C中的候選索引I,其實(shí)用值為I.utility、大小為I.size.為了實(shí)現(xiàn)優(yōu)化后的索引具有最優(yōu)的查詢優(yōu)化效果,調(diào)優(yōu)系統(tǒng)需要選擇一組索引總大小滿足用戶給定閾值B且總的實(shí)用值最大的索引集合S′(即

＜B).顯然,該問題可以轉(zhuǎn)化為經(jīng)典的0-1 背包問題[26].

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

對(duì)于經(jīng)典的0-1 背包問題,可以設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法在時(shí)間O(m?n)內(nèi)求得最優(yōu)解,其中,m為背包中物體的數(shù)目,n為背包的容量.對(duì)于本節(jié)所需要解決的問題,直接利用該動(dòng)態(tài)規(guī)劃算法求解則會(huì)存在如下問題.

·當(dāng)調(diào)優(yōu)系統(tǒng)所處理的數(shù)據(jù)庫(kù)實(shí)例較大時(shí),閾值B需設(shè)置較大的值.利用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)自底向上的求解子問題需要枚舉每一種空間限制大小下的局部解,因此會(huì)導(dǎo)致很大的時(shí)間開銷.例如,當(dāng)閾值B=1GB(空間大小粒度為1MB)、候選索引數(shù)目為1 000 時(shí),計(jì)算的子問題數(shù)目為1024×1000;

·動(dòng)態(tài)規(guī)劃算法計(jì)算的子問題中,大部分都與最終的最優(yōu)解無(wú)關(guān).

因此,本文設(shè)計(jì)了自頂向下計(jì)算子問題的遞歸算法,該算法僅遞歸地計(jì)算與最終最優(yōu)解有關(guān)的子問題,避免了動(dòng)態(tài)規(guī)劃算法導(dǎo)致的無(wú)關(guān)子問題的計(jì)算.同時(shí),考慮到動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)在于可以避免重復(fù)子問題的計(jì)算(子問題結(jié)果復(fù)用),為了避免自頂向下的遞歸算法帶來(lái)的重復(fù)子問題計(jì)算,本節(jié)提出了相應(yīng)的技術(shù)解決遞歸算法中存在的重復(fù)子問題計(jì)算問題.

4.2 具有子問題復(fù)用的遞歸算法

在遞歸算法中實(shí)現(xiàn)子問題復(fù)用的基本思路為:對(duì)遞歸過程中計(jì)算過的子問題,利用哈希表存儲(chǔ)其結(jié)果,在計(jì)算新的子問題時(shí),先通過哈希表判斷該子問題是否已經(jīng)求解過.如哈希表中存在中間結(jié)果,則直接復(fù)用.

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

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

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

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

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

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

5 實(shí) 驗(yàn)

5.1 實(shí)驗(yàn)設(shè)置

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

在默認(rèn)條件下,TPCCMySQL 與OLTPBench 會(huì)根據(jù)TPC-C 實(shí)例信息來(lái)生成查詢,并且生成查詢的查詢條件都可利用到對(duì)應(yīng)表上的主鍵索引(在默認(rèn)主鍵索引設(shè)置情況下,該工具產(chǎn)生的查詢利用主鍵索引已經(jīng)達(dá)到了最優(yōu)的查詢優(yōu)化效果).因此,為了測(cè)試索引調(diào)優(yōu)的效果,本文實(shí)驗(yàn)分別選擇3 種主鍵索引設(shè)置下的場(chǎng)景,從而使得測(cè)試工具生成的查詢可通過建立二級(jí)索引進(jìn)一步的提升查詢性能.表2 所示為TPC-C 數(shù)據(jù)庫(kù)實(shí)例上的3 種不同的主鍵索引設(shè)置.

Table 2 Different settings for primary keys in the DB instance
表2 數(shù)據(jù)庫(kù)實(shí)例中不同的主鍵索引設(shè)置

TPCCMySQL 工具產(chǎn)生的查詢?nèi)罩景? 763 條查詢記錄,其中,不同類別的查詢占比分別為:Select 61.67%,Delete 1.23%,Update 21.01%,Insert 16.09%(該比例由TPCCMySQL 使用的查詢事務(wù)比例所決定).此外,查詢?nèi)罩局?98.5%為單表查詢,1.5%為多表查詢.OLTPBench 工具則可通過變化事務(wù)的比例來(lái)產(chǎn)生不同查詢類別占比的查詢?nèi)罩?詳細(xì)信息見第5.2 節(jié)中的第3 個(gè)實(shí)驗(yàn)).本節(jié)所有實(shí)驗(yàn)均使用TPCCMySQL 作為性能測(cè)試工具,性能測(cè)試指標(biāo)為數(shù)據(jù)庫(kù)系統(tǒng)的吞吐量(TPS,每秒執(zhí)行的事務(wù)數(shù)).

用于測(cè)試的數(shù)據(jù)庫(kù)實(shí)例部署在一臺(tái)ThinkServer 服務(wù)器上(配置為Intel Xeon E3-1226 3.30GHz 處理器,16GB 內(nèi)存,500GB SSD),索引調(diào)優(yōu)系統(tǒng)部署在一臺(tái)Dell PC 上(配置為IntelCore i7-8700 3.2GHz 處理器,8GB 內(nèi)存,256GB SSD),調(diào)優(yōu)系統(tǒng)通過遠(yuǎn)程連接數(shù)據(jù)庫(kù)實(shí)例獲取到實(shí)例信息與索引的調(diào)節(jié).索引調(diào)優(yōu)系統(tǒng)通過C++語(yǔ)言編寫與實(shí)現(xiàn),估計(jì)模型通過PyTorch 框架來(lái)編寫,并將訓(xùn)練得到的模型存儲(chǔ)到本地,再由調(diào)優(yōu)程序進(jìn)行調(diào)用.

5.2 實(shí)驗(yàn)結(jié)果及分析

(1)不同索引調(diào)優(yōu)方法調(diào)優(yōu)性能對(duì)比

第1 個(gè)實(shí)驗(yàn)對(duì)比了不同的索引調(diào)優(yōu)方法的性能.對(duì)比的方法中,Baseline 為使用對(duì)應(yīng)的主鍵索引設(shè)置的方法.由于現(xiàn)有的索引調(diào)優(yōu)/推薦方法中,大部分都依賴查詢優(yōu)化器來(lái)實(shí)現(xiàn)索引作用的估計(jì),無(wú)法應(yīng)用在MySQL 數(shù)據(jù)庫(kù)系統(tǒng)上,因此,本文僅使用了開源的SQL 優(yōu)化器SOAR(SQL optimizer and rewriter.Xiao Mi.https://github.com/xiaomi/soar)作為對(duì)比方法,其無(wú)需依賴查詢優(yōu)化器完成索引調(diào)優(yōu),并且對(duì)比方法不考慮索引大小的約束限制.SmartIndex 為本文所提出方法(默認(rèn)情況下,SmartIndex 使用DNN 來(lái)訓(xùn)練索引查詢優(yōu)化效果的估計(jì)模型,不同預(yù)測(cè)模型的對(duì)比測(cè)試結(jié)果如下一個(gè)實(shí)驗(yàn)所示).

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

此外,圖6 所示實(shí)驗(yàn)還測(cè)試了不同索引大小閾值B對(duì)于索引調(diào)優(yōu)的影響.實(shí)驗(yàn)結(jié)果顯示:SmartIndex 在越大的索引大小閾值下,可以取得越好的查詢性能.例如,在圖6(a)中的PrimarySetting1 下,當(dāng)閾值B的值從100MB增加到500MB 時(shí),系統(tǒng)的吞吐量從4 820 增加到了5 993.這是因?yàn)殚撝?i>B越大的情況下,系統(tǒng)可以建立更多有效的索引,從而更多的查詢可以利用索引來(lái)提升查詢性能.

Fig.6 Comparison on the tuning performance of different index tuning methods
圖6 不同調(diào)優(yōu)方法的調(diào)優(yōu)性能對(duì)比

(2)索引優(yōu)化作用估計(jì)模型測(cè)試

第2 個(gè)實(shí)驗(yàn)測(cè)試了不同估計(jì)模型訓(xùn)練算法對(duì)于索引調(diào)優(yōu)效果的影響.本實(shí)驗(yàn)所對(duì)比的模型訓(xùn)練方法為L(zhǎng)R,GDBT 與DNN(如第3.2 節(jié)所述).對(duì)于LR 方法,實(shí)驗(yàn)使用了前向特征選擇(forward feature selection)[27]的方法來(lái)選擇特征屬性,從而使得LR 訓(xùn)練的模型達(dá)到了最高的準(zhǔn)確率.DNN 算法使用了2 層隱藏層,并且使用Adam 算法作為優(yōu)化器.為了進(jìn)行數(shù)據(jù)采集,實(shí)驗(yàn)利用TPCCMySQL 產(chǎn)生了2 000 條的查詢?nèi)罩炯?并且在TPC-C 數(shù)據(jù)庫(kù)實(shí)例上建立了80 個(gè)不同的索引.對(duì)于一個(gè)查詢q與索引I,為了測(cè)試得到Profit(q,I),實(shí)驗(yàn)分別在不包含任何索引的數(shù)據(jù)表與僅包含I的同一數(shù)據(jù)表上進(jìn)行了性能測(cè)試,然后求兩種情況下的執(zhí)行之間的差值.最終,實(shí)驗(yàn)采集得到160 000 條具有真實(shí)目標(biāo)值的數(shù)據(jù),并將數(shù)據(jù)按照7:3 的比例劃分成訓(xùn)練數(shù)據(jù)與測(cè)試數(shù)據(jù).

由于絕對(duì)誤差的度量方式存在個(gè)別數(shù)據(jù)誤差影響整體誤差的問題,為了度量預(yù)測(cè)模型的準(zhǔn)確性,本文使用了文獻(xiàn)[19]中定義的平均相對(duì)錯(cuò)誤率作為度量標(biāo)準(zhǔn),公式(3)所示為平均相對(duì)錯(cuò)誤率的計(jì)算方式:

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

Table 3 Comparison for the models trained by different learning algorithms
表3 不同算法訓(xùn)練得到的預(yù)測(cè)模型的性能比較

(3)不同類型查詢占比對(duì)調(diào)優(yōu)性能影響測(cè)試

由于寫查詢(增刪改)可能會(huì)導(dǎo)致索引的更新,因此不同的查詢類型對(duì)于索引的查詢優(yōu)化效果會(huì)存在影響.為了測(cè)試不同查詢集合對(duì)于參數(shù)調(diào)優(yōu)的影響,第3 個(gè)實(shí)驗(yàn)采用OLTPBench 工具來(lái)產(chǎn)生查詢?nèi)罩静⑶疫M(jìn)行性能測(cè)試(OLTPBench 可以通過調(diào)節(jié)事務(wù)比例來(lái)產(chǎn)生不同類別的查詢).表4 所示為OLTPBench 產(chǎn)生的3 組不同的查詢?nèi)罩?3 組查詢?nèi)罩局邪腟elect 查詢占比分別為85.12%,62.64%與49.80%,其分別代表了讀密集型查詢、混合類型查詢與寫密集型查詢.

Table 4 Three different query work load generated by OLTPBench
表4 OLTPBench 產(chǎn)生的3 組不同的查詢?nèi)罩?/p>

圖7 所示為利用SmartIndex 方法進(jìn)行索引調(diào)優(yōu)后(Baseline 為PrimarySetting1),通過OLTPBench 進(jìn)行性能測(cè)試得到的實(shí)驗(yàn)結(jié)果(性能測(cè)試的查詢類別比例與生成查詢?nèi)罩局械牟樵冾悇e比例一致).隨著寫查詢比例的增加,通過索引調(diào)優(yōu)后的數(shù)據(jù)庫(kù)系統(tǒng)的吞吐量是降低的.例如,SmartIndex(B=300MB)在query workload1 與query workload3 調(diào)優(yōu)后得到的系統(tǒng)吞吐量分別為1 585 與518.出現(xiàn)這種現(xiàn)象的原因是:更多的寫查詢會(huì)增加索引的更新維護(hù)代價(jià),從而降低了整體的吞吐量.此外,實(shí)驗(yàn)結(jié)果還顯示:在寫查詢比例增加后,增大索引閾值所能提升的查詢性能是降低的.這是因?yàn)樵趯懖樵儽壤叩臅r(shí)候,即使允許建立更多的索引,但由于索引更新維護(hù)代價(jià)的增加,SmartIndex 也無(wú)法選擇出新的具有查詢優(yōu)化效果的索引.

Fig.7 Impact of different query workloads for the effect of index tuning
圖7 不同類型的查詢集合對(duì)于調(diào)優(yōu)性能的影響

(4)索引選擇算法對(duì)比

本文最后一個(gè)實(shí)驗(yàn)測(cè)試了第4 節(jié)提出的索引選擇算法的效果.實(shí)驗(yàn)在1GB 的TPC-C 數(shù)據(jù)庫(kù)實(shí)例上利用TPCCMySQL 性能測(cè)試工具,測(cè)試對(duì)比了貪心算法Greedy(優(yōu)先選擇單位實(shí)用值高的索引,即I.utility/I.size)、動(dòng)態(tài)規(guī)劃算法DP 與本文提出的OptIDXSelect 算法,同時(shí)還對(duì)比了OptIDXSelect 算法在索引大小粒度gran設(shè)置為10MB 與100MB 下的效果.

圖8 與圖9 所示分別為不同索引選擇算法得到的索引調(diào)優(yōu)效果與推薦索引所需的時(shí)間.

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

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

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

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

6 總結(jié)與未來(lái)的工作

索引是數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)高效的查詢性能的方式之一,智能地對(duì)數(shù)據(jù)庫(kù)實(shí)例構(gòu)建并調(diào)節(jié)索引,不僅能夠保證高效的查詢性能,還能有效地提高硬件資源利用率與減少人力成本的投入.本文研究了面向關(guān)系數(shù)據(jù)庫(kù)的智能索引調(diào)優(yōu)方法.首先,本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)面向關(guān)系數(shù)據(jù)庫(kù)的智能索引調(diào)優(yōu)系統(tǒng);在索引調(diào)節(jié)時(shí),為了準(zhǔn)確地估計(jì)索引對(duì)于查詢的查詢優(yōu)化效果并選擇正確的索引,本文設(shè)計(jì)了一種使用機(jī)器學(xué)習(xí)方法來(lái)對(duì)索引的查詢優(yōu)化效果建模的方法;為了最大化索引的調(diào)優(yōu)效果,本文進(jìn)一步地設(shè)計(jì)了一種高效的最優(yōu)索引組合選擇算法,并提出了優(yōu)化技術(shù)來(lái)提升索引選擇的效率;最后設(shè)計(jì)了一系列的實(shí)驗(yàn)對(duì)索引調(diào)優(yōu)的各個(gè)環(huán)節(jié)進(jìn)行了測(cè)試.結(jié)果表明:本文設(shè)計(jì)的系統(tǒng)可以在不同的場(chǎng)景下有效地對(duì)索引進(jìn)行調(diào)優(yōu),從而提升數(shù)據(jù)庫(kù)系統(tǒng)的查詢性能.

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