瞿 中,吳哲一

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

1 引 言

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

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

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

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

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

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

2 模型算法與理論

2.1 強(qiáng)化學(xué)習(xí)

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

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

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

(S,A,R,P)

(1)

其中,S表示環(huán)境的狀態(tài)信息,st∈S表示智能體在t時(shí)刻的環(huán)境狀態(tài);A為智能體可執(zhí)行的動(dòng)作,at∈A表示智能體在t時(shí)刻執(zhí)行的動(dòng)作;R是獎(jiǎng)勵(lì)函數(shù),rt∈R表示智能體在t時(shí)刻獲得的獎(jiǎng)勵(lì)值;P為狀態(tài)轉(zhuǎn)移概率分布函數(shù),表示智能體執(zhí)行動(dòng)作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)無(wú)關(guān).在強(qiáng)化學(xué)習(xí)中,智能體以獲得最大累積獎(jiǎng)勵(lì)為目標(biāo),t時(shí)刻的累積獎(jiǎng)勵(lì)可表示為:

(3)

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

2.2 DQN算法

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

(4)

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

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

(5)

(6)

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

(7)

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

(8)

通過(guò)以上步驟有效緩解了DQN中存在的Q值過(guò)估計(jì)問(wèn)題.

3 索引選擇問(wèn)題描述

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

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

(9)

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

(10)

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

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

4.1 候選索引的生成

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

(11)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(12)

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

4.3 改進(jìn)的ε-greedy探索策略

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

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

(13)

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

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

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

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

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

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

圖3 基于DDQNPER的索引選擇方法學(xué)習(xí)過(guò)程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.隨機(jī)初始化評(píng)估網(wǎng)絡(luò)參數(shù)θ和目標(biāo)網(wǎng)絡(luò)參θ′

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

3.生成工作負(fù)載,通過(guò)索引評(píng)價(jià)規(guī)則生成候選索引;

4.For episode=1 toVdo:

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

6. For episode=1 toTdo:

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

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

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

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

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

15. End For

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

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

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

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

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

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

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

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

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

5.1 實(shí)驗(yàn)環(huán)境

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

5.2 工作負(fù)載的生成

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

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

表2 查詢語(yǔ)句示例表Table 2 Query statement sample table

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

5.3 實(shí)驗(yàn)評(píng)估與結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié) 語(yǔ)

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

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