一種基于深度強化學(xué)習(xí)的索引選擇方法

瞿 中,吳哲一

(重慶郵電大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,重慶 400065)

1 引 言

數(shù)據(jù)庫系統(tǒng)已經(jīng)在行業(yè)中成熟而穩(wěn)定地運行,而大數(shù)據(jù)時代為數(shù)據(jù)庫系統(tǒng)提出了更高的要求.隨著數(shù)據(jù)量的增大,也要求數(shù)據(jù)庫系統(tǒng)能夠具備更快的查詢速度、更高的系統(tǒng)吞吐量.數(shù)據(jù)的類型模式不斷增多,使得工作負載具有快速而又多樣化的特點,要求數(shù)據(jù)庫系統(tǒng)能夠具備快速、準(zhǔn)確地響應(yīng)查詢負載動態(tài)變化的能力[1].隨著數(shù)據(jù)規(guī)模的不斷增大,數(shù)據(jù)庫性能的調(diào)優(yōu)對研究人員、企業(yè)和數(shù)據(jù)庫管理員(Database Administrator,DBA)也變得越來越重要.數(shù)據(jù)庫性能調(diào)優(yōu)的一個重要的方面是選擇合適的索引.索引選擇問題(Index Selection Problem,ISP)是數(shù)據(jù)庫性能調(diào)優(yōu)中的重要問題之一.在系統(tǒng)中設(shè)置適當(dāng)?shù)乃饕梢约涌鞌?shù)據(jù)的訪問過程,使用不合適的索引不僅浪費資源,而且還會對系統(tǒng)造成不必要的磁盤開銷與索引維護代價[2].

強化學(xué)習(xí)[3](Reinforcement Learning,RL)是機器學(xué)習(xí)的一個分支,是與人類學(xué)習(xí)最接近的一種形式,可以通過探索和利用未知環(huán)境來學(xué)習(xí)經(jīng)驗.環(huán)境(Environment)傳遞給智能體(Agent)環(huán)境狀態(tài)信息,智能體執(zhí)行相應(yīng)的動作(Action),環(huán)境反饋給智能體一定的獎勵(Reward);智能體的目的是最大化累計的獎勵,通過反復(fù)的交互,智能體可以做出最優(yōu)的動作.深度學(xué)習(xí)[4](Deep Learning,DL)的優(yōu)勢在于感知能力,可以讓智能體提取到外界環(huán)境狀態(tài)的有效特征.DeepMind將深度學(xué)習(xí)的感知能力和強化學(xué)習(xí)的決策能力相結(jié)合,提出了深度強化學(xué)習(xí)[5](Deep Reinforcement Learning,DRL),并創(chuàng)造出AlphaGo.

傳統(tǒng)索引選擇方法如AutoAdmin[6]、DB2Advis[7]使用不同的啟發(fā)式規(guī)則生成候選索引,來減少配置搜索空間,在通過貪心算法找到最優(yōu)的索引選擇.但索引之間是可以相互影響的,即一個索引的優(yōu)化效果會因為另一個索引的的存在而受到影響[8].因此,要找到最佳的索引組合就必須考慮索引間的交互,不能僅僅考慮單個索引的優(yōu)化效果,因為每個索引可能會影響所有其他索引,所以從一大堆候選索引中找到最佳索引非常具有挑戰(zhàn)性,索引交互極大地增加了索引選擇的復(fù)雜性.傳統(tǒng)的索引選擇方法先生成候選索引,再利用動態(tài)規(guī)劃等算法從候選索引中選擇在限制條件最優(yōu)的索引組合,但都沒有考慮到不同索引間的影響.近年來,將機器學(xué)習(xí)應(yīng)用于索引選擇問題成為了熱門的研究方向.Sharma等人提出的NoDBA[9]系統(tǒng)提供了一個用強化學(xué)習(xí)進行索引選擇的思路,將工作負載和候選索引表示為強化學(xué)習(xí)中的環(huán)境,將在某列上創(chuàng)建索引表示為動作,其證明了將強化學(xué)習(xí)應(yīng)用于索引選擇是可行的.文獻[10,11]提出了基于深度強化學(xué)習(xí)的索引推薦方案,但大多數(shù)也只能選擇單列索引,就會錯過類似于覆蓋索引這樣可以大幅度提升查詢性能的多列索引,并且上述方法沒有考慮到索引交互的影響.文獻[12]考慮到索引交互的影響,其將已創(chuàng)建索引之間的交互建模為神經(jīng)元之間的交互,但沒有將不同索引配置下的數(shù)據(jù)庫查詢性能進行比較,不能充分考慮到索引交互對索引選擇帶來的影響.

針對上述問題,本文將索引選擇過程建模為馬爾可夫決策模型,首先通過對數(shù)據(jù)庫的工作負載進行分析生成候選索引,然后利用深度強化學(xué)習(xí)算法訓(xùn)練智能體進行索引選擇.相對于目前的索引選擇方法,本文提出的方法具有以下優(yōu)點:

1)將索引選擇問題定義為一個馬爾可夫決策過程,提出一個基于深度強化學(xué)習(xí)的索引選擇方法,并通過制定索引評價規(guī)則生成候選索引,實現(xiàn)了單列索引和多列索引的同時選擇.

2)通過定義深度強化學(xué)習(xí)過程中數(shù)據(jù)庫環(huán)境的狀態(tài)表示、智能體的動作和獎勵函數(shù),充分考慮了索引之間可能的交互,能夠選擇最優(yōu)索引組合.

2 模型算法與理論

2.1 強化學(xué)習(xí)

強化學(xué)習(xí)的目標(biāo)是最大化智能體的累積獎勵,使用強化學(xué)習(xí)的智能體可以通過與環(huán)境的反復(fù)交互,學(xué)會選擇近似最優(yōu)的行為以實現(xiàn)其目標(biāo),最終學(xué)習(xí)得到一個環(huán)境狀態(tài)到動作的映射關(guān)系.其原理如圖1所示.

圖1 強化學(xué)習(xí)原理Fig.1 Principle of reinforcement learning

強化學(xué)習(xí)過程屬于馬爾科夫決策過程(Markov Decision Process,MDP).通常,將MDP定義為一個四元組:

(S,A,R,P)

(1)

其中,S表示環(huán)境的狀態(tài)信息,st∈S表示智能體在t時刻的環(huán)境狀態(tài);A為智能體可執(zhí)行的動作,at∈A表示智能體在t時刻執(zhí)行的動作;R是獎勵函數(shù),rt∈R表示智能體在t時刻獲得的獎勵值;P為狀態(tài)轉(zhuǎn)移概率分布函數(shù),表示智能體執(zhí)行動作at,從狀態(tài)轉(zhuǎn)移到下一狀態(tài)st+1的概率.

P(st+1,rt+1|s1,a1,r1,…,st,at,rt)=P(st+1,rt+1|st,at)

(2)

公式(2)表明,狀態(tài)st+1僅與當(dāng)前狀態(tài)st相關(guān),與之前狀態(tài)無關(guān).在強化學(xué)習(xí)中,智能體以獲得最大累積獎勵為目標(biāo),t時刻的累積獎勵可表示為:

(3)

其中,γ∈[0,1]是折扣系數(shù),代表智能體對未來獎勵的重視程度.

2.2 DQN算法

強化學(xué)習(xí)根據(jù)是否需要價值函數(shù)分為基于價值(Value-based)的和基于策略(Policy-based)的,Q-Learning是基于價值中的代表性算法.狀態(tài)-動作函數(shù)Q(s,a)指在某一時刻的s狀態(tài)下,采取動作a能夠獲得獎勵的期望,該算法將所有狀態(tài)s與動作a關(guān)聯(lián)起來組成一張Q表,來存儲狀態(tài)動作對(s,a)的Q值,通過在每個狀態(tài)下選擇具有最高Q值的動作來形成策略,Q值的更新如式(4)所示:

(4)

Q-Learning算法通過表格來存儲Q值,當(dāng)狀態(tài)-動作空間很大時,表格的維度也會增大,導(dǎo)致在表格中的搜索效率降低.深度強化學(xué)習(xí)是強化學(xué)習(xí)與深度學(xué)習(xí)相結(jié)合的全新算法,能夠有效地對任務(wù)中的高維狀態(tài)與數(shù)據(jù)特征進行提取,可以有效地解決Q表的維度過大的問題.

Mnih等提出了深度Q網(wǎng)絡(luò)[5](Deep Q Network,DQN).DQN采用神經(jīng)網(wǎng)絡(luò)來代替Q表,解決了Q-Learning算法的Q表的維度過大的問題.DQN中有兩個結(jié)構(gòu)相同但參數(shù)不同的神經(jīng)網(wǎng)絡(luò),分別為評估網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò),為了提高了算法的穩(wěn)定性,首先讓評估網(wǎng)絡(luò)在執(zhí)行動作后都會進行參數(shù)更新,目標(biāo)網(wǎng)絡(luò)隔一段時間將評估網(wǎng)絡(luò)參數(shù)硬拷貝過來,實現(xiàn)目標(biāo)網(wǎng)絡(luò)的更新,其次使用經(jīng)驗回放機制打亂了樣本之間的相關(guān)性.目標(biāo)值網(wǎng)絡(luò)Q值的計算公式如公式(5)所示:

(5)

(6)

為緩解DQN中動作值函數(shù)容易產(chǎn)生Q值過估計的問題,Van等提出了雙重深度Q網(wǎng)絡(luò)模型[13](Double Deep Q Network,DDQN).DDQN的網(wǎng)絡(luò)結(jié)構(gòu)與DQN類似,主要是將動作選取和值評估解耦,首先根據(jù)公式(7)利用當(dāng)前Q網(wǎng)絡(luò)選擇Q值最大的動作.

(7)

再通過公式(8)選出的動作在目標(biāo)Q網(wǎng)絡(luò)中計算目標(biāo)Q值.

(8)

通過以上步驟有效緩解了DQN中存在的Q值過估計問題.

3 索引選擇問題描述

索引選擇問題是在特定限制條件下,如存儲限制,索引數(shù)量限制,調(diào)優(yōu)時間限制等,為給定工作負載找到一組索引組合,能最大限度提升數(shù)據(jù)庫系統(tǒng)的查詢性能.

數(shù)據(jù)庫D中包含n張表{T1,T2,…,Tn},其中Ti為數(shù)據(jù)庫中的表.工作負載W(大小為m)是一組工作負載W={Q1,Q2,…,Qm},Qi是第i條查詢語句.索引配置I為一組索引{i1,i2,…,ik},可能包含來自不同表的單列索引或多列索引.C為當(dāng)前的限制,如索引的內(nèi)存限制或數(shù)量限制.Cost(Qi,I)表示在索引配置I下查詢語句Qi的查詢成本.因此,工作負載W在索引設(shè)置I下的查詢成本如公式(9)所示:

(9)

本文對索引選擇問題的優(yōu)化目標(biāo)是,在一個包含n張表的數(shù)據(jù)庫D上,針對一組工作負載W,在限制條件為C的情況下生成一組候選索引Ic,并從候選索引Ic選擇一組索引I*并使得公式(10)成立:

(10)

4 基于深度強化學(xué)習(xí)的索引選擇方法

本節(jié)主要闡述將深度強化學(xué)習(xí)應(yīng)用于索引選擇算法的相關(guān)定義,包括通過索引評價規(guī)則生成候選索引和分別對深度強化學(xué)習(xí)算法所需的數(shù)據(jù)庫環(huán)境狀態(tài)、索引選擇智能體的動作、獎勵等信息進行定義.

4.1 候選索引的生成

如果在有一張含有n列的表建立一個維度為i(1≤i≤n)的索引,索引的第1列有n種選擇,第2列有n-1種選擇,以此類推這張表可能索引數(shù)量如公式(11)所示:

(11)

如果一張表有10列,就有10種不同的可能性單列索引,有90種2個屬性的索引,若索引包含5個屬性,則可能的索引有30240種[14].如果要實現(xiàn)多列索引的選擇,通過窮舉所有可能的索引作為候選索引是不現(xiàn)實的.因此,本文通過使用索引評價規(guī)則對工作負載進行分析,進而生成高質(zhì)量地候選索引,限制候選索引的數(shù)量.本文提出的索引選擇方法只對二級索引進行操作,所以創(chuàng)建的索引都是B+樹結(jié)構(gòu).

本文根據(jù)文獻[15]提出的觀點,在一條查詢語句中,對在謂詞條件、連接條件、GROUP-BY條件、ORDER-BY條件關(guān)聯(lián)的屬性創(chuàng)建索引能最大程度提升查詢效率.因此文中設(shè)計5條索引評價規(guī)則,能最大程度提供高質(zhì)量的候選索引.規(guī)則如下:

規(guī)則1.將查詢語句中WHERE后面所有出現(xiàn)的屬性設(shè)為單列索引.

規(guī)則2.將WHERE后面的等值查詢和范圍查詢關(guān)聯(lián)的屬性作為多列索引,且索引中的順序和查詢語句中的排列順序一致.

規(guī)則3.若出現(xiàn)ORDER-BY和GROUP-BY,多列索引需要包含對應(yīng)關(guān)聯(lián)的屬性,且保持順序一致.

規(guī)則4.若有具體要查詢的屬性,多列索引需包含全部要查詢的屬性,即為覆蓋索引.

規(guī)則5.若出現(xiàn)多表連接查詢,將連接查詢處的每個表的連接屬性分別設(shè)為單列索引.

規(guī)則1將在查詢語句中所有WHERE后面出現(xiàn)的屬性都設(shè)置為單列索引,雖然這些單列索引有可能不會給對查詢語句帶來優(yōu)化,但是單列索引數(shù)量的有限,并不會帶來維度爆炸的問題,同時能給索引選擇智能體更多動作選項.因為本文創(chuàng)建的B+樹索引是一種有序的數(shù)據(jù)機構(gòu),所以對于一個查詢語句,一個索引只要按照前綴順序包含該查詢語句的WHERE條件中屬性,該索引就可以對此查詢語句進行優(yōu)化,由此引出規(guī)則2.當(dāng)查詢語句包含ORDER-BY和GROUP-BY等排序操作時,通過規(guī)則3可以在創(chuàng)建索引時就進行排序,這樣在進行查詢時就無需多余的排序操作.

當(dāng)查詢語句為SELECT×FROM … WHERE…時,首先要通過二級索引查詢到符合WHERE后條件記錄的主鍵ID,再根據(jù)主鍵ID通過聚集索引訪問數(shù)據(jù)表找到對應(yīng)的記錄,這個過程叫做回表查詢.但如果有具體要查詢的屬性,就可以通過規(guī)則4創(chuàng)建覆蓋索引,這樣就避免再次訪問表的操作.

連接查詢的執(zhí)行相對比較復(fù)雜,在執(zhí)行連接查詢時在主要由嵌套循環(huán)連接、哈希連接和合并掃描連接這3種方式對表進行連接,不同的連接方式對索引的設(shè)置有著不同的要求.在使用嵌套循環(huán)連接時,表的訪問順序會對索引的設(shè)置有著重大的影響,主要取決于那一張表是驅(qū)動表.而哈希連接和合并掃描連接都是先通過連接字段進行掃描,保存在一個臨時表中,再通過掃描其他的表滿足本地謂詞條件的記錄和臨時表中對應(yīng)記錄進行匹配,所以在連接屬性上創(chuàng)建索引都有可能對查詢語句進行優(yōu)化.因此,本文提出規(guī)則5,將每個表的連接屬性設(shè)為單列索引.

4.2 基于DDQNPER的索引選擇智能體

優(yōu)先級經(jīng)驗重放[16]被證明是對傳統(tǒng)經(jīng)驗重放的一種非常有效的改進,因為優(yōu)先級經(jīng)驗重放不是均勻抽樣,而是對樣本進行加權(quán),使得產(chǎn)生高誤差的樣本在訓(xùn)練中更容易被抽取,有助于降低總體偏差.DDQN算法有效緩解了DQN中存在的Q值過估計問題.本文將它們的優(yōu)勢結(jié)合,提出基于DDQNPER的索引選擇方法.

本文中基于DDQNPER的索引選擇方法中的Q-Learning算法基本要素可表示為:

1)環(huán)境(environment):基于PostgreSQL數(shù)據(jù)庫的TPC-H實例.

2)智能體(agent):智能體是索引選擇調(diào)優(yōu),它接收來自環(huán)境的狀態(tài)和獎勵,并在每一步更新策略以選擇合適的索引.

3)動作(action):在索引選擇過程中,動作at可表示為在步驟t時,在候選索引I中選擇一個索引i,其中i∈I.

4)狀態(tài)(state):狀態(tài)st由一個向量表示,初始化都為0,每個位置表示當(dāng)前候選索引的選擇與否,當(dāng)選擇某個索引時,將其對應(yīng)位置設(shè)置為1,表示已經(jīng)選擇,狀態(tài)空間維度等于動作空間維度,也就是候選索引的數(shù)量.

5)策略(policy):策略是從狀態(tài)映射到動作的函數(shù),策略π從s0開始,在每個時間步下選擇一個索引,進入下一個狀態(tài)st+1,這個過程重復(fù)進行,直到達到索引數(shù)量限制.執(zhí)行完策略的結(jié)果是選擇過的索引集合.

6)獎勵(reward):在強化學(xué)習(xí)中,獎勵是智能體不斷完善自己,使自己能夠自主實現(xiàn)目標(biāo)的直接經(jīng)驗來源.智能體在進行索引選擇時,每次選擇新索引indexnew創(chuàng)建之后,所有索引整體的優(yōu)化效果會出現(xiàn)變化,這可能是創(chuàng)建indexnew帶來的優(yōu)化效果或者indexnew與indexesold中某些索引交互產(chǎn)生的,因此,本文將這兩種情形都考慮在內(nèi).因此本文在設(shè)計獎勵函數(shù)時將索引交互對索引選擇的影響考慮在內(nèi),將當(dāng)前索引配置下Cost(W,It)與初始化下索引配置下Cost(W,I0)以及上一次索引選擇配置下Cost(W,It-1)進行比較,其獎勵函數(shù)如公式(12)所示:

(12)

α和β為兩個取值范圍為[0,1]的因子,用于調(diào)節(jié)索引交互對于獎勵的影響,α/β越大,說明智能體越重視當(dāng)前索引配置相對于上一次索引配置的帶來查詢性能的變化,也就是索引交互可能帶來的影響,而不是考慮當(dāng)前索引配置相對于初始狀態(tài)下查詢性能的變化.

4.3 改進的ε-greedy探索策略

動作的選取在強化學(xué)習(xí)中十分重要,ε-greedy策略是經(jīng)常被使用的選擇策略.在傳統(tǒng)強化學(xué)習(xí)算法中,探索因子ε的值是固定的,如果ε的值太小會導(dǎo)致智能體在訓(xùn)練前期無法對環(huán)境進行充分探索,導(dǎo)致智能體陷入局部最優(yōu).若其太大,會導(dǎo)致訓(xùn)練后期智能體雖然已經(jīng)對環(huán)境進行了充分探索,但仍然以較大概率隨機選取動作,而非通過當(dāng)前策略選擇最優(yōu)動作,出現(xiàn)過度探索而利用不足,這樣和尋找最優(yōu)策略的原則不相符合.

在索引選擇問題場景下,DRL的狀態(tài)空間和動作空間都是非常大的,如果在智能體訓(xùn)練前期不進行充分的探索,很難學(xué)習(xí)到最優(yōu)的策略,但是如果在訓(xùn)練后期智能體還在過度探索,則可能導(dǎo)致神經(jīng)網(wǎng)絡(luò)很難收斂,所以根據(jù)索引選擇問題的實際情況,本文基于ε-greedy策略提出一種改進的動態(tài)探索策略,ε值的變化如公式(13)所示:

(13)

其中x為訓(xùn)練步數(shù),μ為偏移量.圖2展示了不同偏移量下對應(yīng)ε值的變化.

圖2 ε 值變化曲線Fig.2 Variation curve of ε value

如圖2所示,隨著μ值的增大會ε值變化的曲線向右偏移,所以智能體訓(xùn)練中前期的探索的機會越多,隨著訓(xùn)練過程的深入,ε值始終會收斂到一個較小的水平,保證了智能體更大概率地利用當(dāng)前最優(yōu)策略.

4.4 索引選擇智能體的訓(xùn)練

索引選擇算法的核心在于訓(xùn)練神經(jīng)網(wǎng)絡(luò),為了使DDQNPER網(wǎng)絡(luò)模型適用于索引選擇場景,需要創(chuàng)建真實的數(shù)據(jù)庫實例場景,并根據(jù)隨機生成的工作負載對智能體進行訓(xùn)練,通過迭代求解不斷更新網(wǎng)絡(luò)參數(shù),使得神經(jīng)網(wǎng)絡(luò)的訓(xùn)練收斂,最終得到完成訓(xùn)練的智能體.

基于DDQNPER的索引選擇方法分為候選索引的生成和訓(xùn)練兩個階段,訓(xùn)練過程如圖3所示.

圖3 基于DDQNPER的索引選擇方法學(xué)習(xí)過程Fig.3 Learning process of ISP based on DDQNPER

算法1.基于DDQNPER的索引選擇算法

輸入：訓(xùn)練回合數(shù)V,每回合訓(xùn)練步數(shù)T,目標(biāo)網(wǎng)絡(luò)更新頻率C,折扣率λ,ε中的偏移量μ;

輸出：訓(xùn)練完成的索引選擇智能體

1.隨機初始化評估網(wǎng)絡(luò)參數(shù)θ和目標(biāo)網(wǎng)絡(luò)參θ′

2.初始化經(jīng)驗單元,容量為N

3.生成工作負載,通過索引評價規(guī)則生成候選索引;

4.For episode=1 toVdo:

5. 初始化數(shù)據(jù)庫系統(tǒng);

6. For episode=1 toTdo:

7. 在狀態(tài)st下,通過公式(13)計ε,利用概率ε隨機選取動作;

9. 執(zhí)行動作at,測試數(shù)據(jù)庫系統(tǒng)查詢性能,并以此計算rt,狀態(tài)轉(zhuǎn)換為st+1;

10.將(st,at,st+1,rt)組成訓(xùn)練樣本存入經(jīng)驗回放單元;

11. 從經(jīng)驗回放單元隨機抽取訓(xùn)練樣本,并對抽取的樣本進行排序;

14. 每訓(xùn)練C輪后,用評估網(wǎng)絡(luò)的參數(shù)更新目標(biāo)網(wǎng)絡(luò)的參數(shù),即θ′=θ;

15. End For

16.End For 參數(shù)θ,θ′收斂

本文利用算法1訓(xùn)練智能體.訓(xùn)練開始前,對數(shù)據(jù)庫系統(tǒng)和深度強化學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)參數(shù)進行初始化,然后隨機生成工作負載,并根據(jù)本文提出的索引評價規(guī)則生成候選索引.每執(zhí)行完一次訓(xùn)練回合,對數(shù)據(jù)庫系統(tǒng)進行初始化,刪除所有本回合創(chuàng)建的索引.

智能體在選擇動作前,首先通過公式(13)先計算ε值,再根據(jù)ε決定隨機選擇還是選取Q值最高的動作執(zhí)行,執(zhí)行完動作后獲得獎勵,同時轉(zhuǎn)換到下一個環(huán)境狀態(tài).由于需要訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型,所以將訓(xùn)練數(shù)據(jù)以(st,at,st+1,rt)的形式存儲到經(jīng)驗回放單元.經(jīng)歷C次迭代訓(xùn)練后,從經(jīng)驗回放單元抽取批量訓(xùn)練數(shù)據(jù)對評估網(wǎng)絡(luò)進行訓(xùn)練更新.根據(jù)目標(biāo)網(wǎng)絡(luò)更新頻率,用評估網(wǎng)絡(luò)的參數(shù)替換目標(biāo)網(wǎng)絡(luò)的參數(shù);執(zhí)行完所有的訓(xùn)練回合后,得到訓(xùn)練完成的索引選擇智能體.

算法1的時間復(fù)雜度為O(V×(Ti+Ta+Tnn)),其中V為訓(xùn)練回合數(shù),Ti是本次訓(xùn)練回合開始前數(shù)據(jù)庫狀態(tài)初始化的時間,Ta是在數(shù)據(jù)庫系統(tǒng)中創(chuàng)建索引的時間,Tnn是神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練更新的時間.

本文中神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練相關(guān)參數(shù)設(shè)置如表1所示.

表1 超參數(shù)列表Table 1 Hyperparameter list

索引選擇智能體的網(wǎng)絡(luò)模型由3個全連接層組成,(輸入為數(shù)據(jù)庫系統(tǒng)當(dāng)前候選索引的配置,所以網(wǎng)絡(luò)模型的狀態(tài)維度和動作維度也與候選索引數(shù)量相同,輸出為每個候選索引的Q值.智能體的網(wǎng)絡(luò)模型結(jié)構(gòu)如圖4所示.

圖4 模型結(jié)構(gòu)Fig.4 Model architecture

5 實 驗

5.1 實驗環(huán)境

本文在PostgreSQL數(shù)據(jù)庫系統(tǒng)上進行了實驗測試,并使用PostgreSQL的HypoPG(1)http://github.com/hypopg擴展來創(chuàng)建虛擬索引,避免實際的查詢執(zhí)行和索引創(chuàng)建的開銷.本次實驗在Intel Xeon 3160 CPU,NVIDIA GeForce RTX 2080 GPU,RAM:16GB的服務(wù)器上進行,操作系統(tǒng)為Ubuntu 20.04.本次實驗所有的代碼都使用Python和PyTorch實現(xiàn),公式(12)中的參數(shù)α與β的值都為0.5.

5.2 工作負載的生成

TPC(2)http://www.tpc.org是業(yè)界廣泛使用的一套數(shù)據(jù)庫基準(zhǔn)測試,其中TPC-H用于評測數(shù)據(jù)庫的分析查詢能力,主要用于對數(shù)據(jù)庫系統(tǒng)進行基準(zhǔn)測試.但是,TPC-H不是索引選擇方法的基準(zhǔn)測試.TPC-H測試的工作負載非常復(fù)雜,不僅包含大量函數(shù)操作,還存在許多子查詢以及分組查詢,并不符合實際場景下的數(shù)據(jù)庫操作,所以本文采用自定義生成的工作負載.

為了驗證本文提出的基于DDQNPER改進的索引選擇方法(簡稱為DDQN-MC)的有效性,本文使用了兩種類型的工作負載來驗證.工作負載A中的查詢語句對所有表進行SELECT T_A.C_B或者SELECT COUNT(*)查詢,在WHERE后通過謂詞[AND,OR,JOIN]連接最多3個隨機創(chuàng)建的查詢條件,WHERE子句查詢條件為等值查詢(例如L_TAX=0.02)或者范圍查詢(例如L_SHIPDATE<′1994-01-01′),查詢語句最后可能包含聚合[GROUP-BY,ORDER-BY],T_A和C_B的值隨機地從數(shù)據(jù)庫中選擇真實存在的值.工作負載A由5組不同類型的查詢語句組成,每組各生成4條查詢語句,類型示例如表2所示.分別生成訓(xùn)練工作負載和測試工作負載各20條查詢語句.工作負載的多樣性有助于驗證索引選擇方法的有效性.

表2 查詢語句示例表Table 2 Query statement sample table

工作負載B中的每條查詢語句都是對LINEITEM表進行SELECT COUNT(*)查詢,在WHERE后通過AND連接最多7個隨機創(chuàng)建的查詢條件,WHERE子句查詢條件為等值查詢或者范圍查詢.分別生成訓(xùn)練工作負載和測試工作負載各10條查詢語句.

5.3 實驗評估與結(jié)果分析

本次實驗通過TPC-H生成大小為1GB的數(shù)據(jù)庫實例,索引數(shù)量限制為3,使用工作負載B.將基于動態(tài)探索策略的DDQN-MC和傳統(tǒng)DDQN算法進行分別執(zhí)行100次迭代訓(xùn)練,對兩種算法每一步的平均獎勵值進行比較.平均獎勵值的數(shù)據(jù)如圖5所示.

圖5 DDQN算法和DDQN-MC算法平均獎賞值對比圖Fig.5 Comparison of the average rewards values between DDQN and DDQN-MC in simple environment

NoDBA同樣是一個基于DRL的索引選擇智能體,其將當(dāng)前索引配置和工作負載作為DRL中的環(huán)境,可執(zhí)行的動作為在某列上創(chuàng)建索引,所以其無法推薦多列索引.為了能與DDQN-MC進行比較,本次實驗的使用工作負載B,且基于DDQN的索引選擇方法和DDQN-MC都沒有使用本文提出的索引評價規(guī)則生成候選索引,候選索引都為工作負載B中出現(xiàn)過的屬性,皆為單列索引.

由圖6和圖7的實驗結(jié)果可以得知,在創(chuàng)建相同數(shù)量索引的情況下,DDQN-MC選擇的索引組合相對于NoDBA和DDQN能更多地提升數(shù)據(jù)庫系統(tǒng)的查詢性能.NoDBA在設(shè)計獎勵函數(shù)沒有將索引交互考慮在內(nèi),只比較當(dāng)前索引配置相對于初始狀態(tài)下數(shù)據(jù)庫系統(tǒng)查詢性能的變化,所以出現(xiàn)隨著索引數(shù)量的增加查詢性能提升率增加緩慢甚至退化的情況.而基于DDQN的索引選擇方法和DDQN-MC都可以隨著索引數(shù)量的增加使得查詢性能提升率有所提升.

圖6 數(shù)據(jù)庫實例大小為1G時不同方法查詢性能提升率對比Fig.6 Comparison of performance improvement rate of different methods when the database instance size is 1GB

圖7 數(shù)據(jù)庫實例大小為10G時不同方法查詢性能提升率對比Fig.7 Comparison of performance improvement rate of different methods when the database instance size is 10 GB

由圖7可以看出,在數(shù)據(jù)庫實例大小為10G時,基于DDQN的索引選擇方法和DDQN-MC的性能都有所下降.隨著數(shù)據(jù)規(guī)模的增加,在硬件的不同狀態(tài)下,相同工作負載的執(zhí)行時間變化較大,而工作負載的執(zhí)行時間對智能體的訓(xùn)練迭代有著關(guān)鍵的作用,所以導(dǎo)致智能體無法學(xué)習(xí)到最優(yōu)的策略,但仍可以看出DDQN-MC的性能要明顯優(yōu)于基于DDQN的索引選擇方法和NoDBA.

為了驗證本文提出的提出索引評價規(guī)則和DDQN-MC的有效性,本文將其與能同樣推薦多列索引的AutoAdmin、POWA(The PostgresSQL Workload Analyzer)以及基于索引評價規(guī)則和DDQN的索引選擇方法分別在大小為1G和10G的數(shù)據(jù)庫實例上進行對比實驗,執(zhí)行工作負載A.

AutoAdmin是Microsoft公司研究的數(shù)據(jù)庫系統(tǒng)自動化管理和調(diào)優(yōu)的技術(shù),并將其應(yīng)用于Microsoft SQL Server,其能根據(jù)工作負載同時選擇單列索引和多列索引,為了能與DDQN-MC進行比較,本文使用Jan[17]等針對PostgreSQL重新實現(xiàn)的AutoAdmin方法.

POWA是一個分析PostgresSQL工作負載的工具.POWA對數(shù)據(jù)庫中各種數(shù)據(jù)進行統(tǒng)計,其組件pg_qualstats能夠根據(jù)工作負載提出建議索引.

通過圖8和圖9實驗結(jié)果可以發(fā)現(xiàn),DDQN-MC在每個階段選擇索引的優(yōu)化效果都要強于其他3種方法,隨著索引數(shù)量的增加,工作負載的執(zhí)行時間也逐漸減少.DDQN在數(shù)據(jù)庫實例大小為1G的所有階段和數(shù)據(jù)庫大小為10G時絕大部分階段選擇索引的優(yōu)化效果也是優(yōu)于AutoAdmin和POWA.

圖8 數(shù)據(jù)庫實例大小為1G時不同方法查詢時間對比Fig.8 Comparison of query time between different methods when the database instance size is 1GB

圖9 數(shù)據(jù)庫實例大小為10G時不同方法查詢時間對比Fig.9 Comparison of query time between different methods when the database instance size is 10 GB

通過在不同場景下進行對比,DDQN-MC都能選擇出更優(yōu)的索引組合,有效地提升了數(shù)據(jù)庫的查詢性能.

6 結(jié) 語

本文提出一種基于深度強化學(xué)習(xí)的索引選擇方法.相比于傳統(tǒng)的索引選擇方法,本文提出的方法能更好地考慮索引交互的影響.與典型的基于深度強化學(xué)習(xí)的索引選擇方法相比,其不僅考慮索引交互的影響,還能夠選擇單列索引和多列索引,且相對于這兩種方法,其能夠選擇出更優(yōu)的索引組合.

但是本文提出的方法存在一定的局限性,例如未考慮索引創(chuàng)建帶來的時空開銷以及索引的刪除等方面.在未來的工作中,可以用全面的指標(biāo)來評價索引選擇方法,把智能體和數(shù)據(jù)庫環(huán)境的交互以及獎勵的設(shè)計作為重點,同時將更多深度強化學(xué)習(xí)算法應(yīng)用于索引選擇也是未來的發(fā)展方向之一.