牛祥虞 游進(jìn)國 虞文波

摘 要：建立索引是提高數(shù)據(jù)庫性能的一個重要方法。目前隨著強(qiáng)化學(xué)習(xí)算法的發(fā)展，出現(xiàn)了一系列使用強(qiáng)化學(xué)習(xí)解決索引推薦問題（index selection problem，ISP）的方法。針對現(xiàn)有的深度強(qiáng)化學(xué)習(xí)索引推薦算法訓(xùn)練時間長、訓(xùn)練不夠穩(wěn)定的問題，提出了一個基于A2C的索引推薦算法PRELIA。該算法加入負(fù)載索引掃描行數(shù)特征矩陣，并對獎勵值進(jìn)行歸一化處理，旨在提高索引選擇的準(zhǔn)確性和效率，減少索引空間占用。在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表示，該算法可以在保證與比較算法相當(dāng)?shù)乃饕扑]質(zhì)量的同時，推薦出的索引占用更小的存儲空間，其訓(xùn)練時間比基線算法時間提高了4倍以上。

關(guān)鍵詞：數(shù)據(jù)庫； 索引推薦； 強(qiáng)化學(xué)習(xí)； 查詢優(yōu)化

中圖分類號：TP391?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號：1001-3695（2023）12-034-3742-05

doi：10.19734/j.issn.1001-3695.2023.03.0146

Database index recommendation based on multithread parallel reinforcement learning

Abstract：Indexing is an important method to improve database performance. At present， with the development of reinforcement learning algorithm， there are a series of methods to solve the index recommendation problem by reinforcement learning. Aiming at the problem that the existing deep reinforcement learning index recommendation algorithm has long training time and unstable training， this paper proposed an index recommendation algorithm based on A2C （advantage actorcritical）， called PRELIA （parallel compensation learning index advisor）. In order to improve the accuracy and efficiency of index selection and reduce the occupation of index space， the algorithm added the characteristic matrix of the number of rows scanned by load index and normalized the reward value. Experimental results on different data sets show that the proposed algorithm can guarantee the index recommendation quality equivalent to that of the compared algorithms， while the recommended index occupies less storage space， and the training time is more than 4 times longer than that of the baseline algorithms.

Key words：database; index recommendations; reinforcement learning; query optimization

0 引言

在云計算、大數(shù)據(jù)等技術(shù)的推動下，數(shù)據(jù)的存儲量呈爆發(fā)式增長。創(chuàng)建索引是目前對海量數(shù)據(jù)進(jìn)行高效查詢的主要方法之一。傳統(tǒng)的索引推薦方法大多采用啟發(fā)式規(guī)則進(jìn)行枚舉的貪心，然而在負(fù)載動態(tài)變化的生產(chǎn)環(huán)境數(shù)據(jù)庫中，枚舉算法無法在有限的時間內(nèi)計算出所有索引組合情況，并且基于貪心方法的索引推薦方法可能存在計算出次優(yōu)解的問題。很多數(shù)據(jù)庫供應(yīng)商提供了自己數(shù)據(jù)庫的索引推薦工具來幫助數(shù)據(jù)庫管理人員減輕工作負(fù)擔(dān)，但是需要數(shù)據(jù)庫管理員有豐富的使用經(jīng)驗(yàn)。

基于強(qiáng)化學(xué)習(xí)的索引推薦方法是隨著強(qiáng)化學(xué)習(xí)的技術(shù)發(fā)展起來的，與傳統(tǒng)索引推薦方法相比，它可以在數(shù)據(jù)庫負(fù)載動態(tài)變化的環(huán)境下進(jìn)行索引推薦，不需要借助數(shù)據(jù)庫管理員的經(jīng)驗(yàn)?；趶?qiáng)化學(xué)習(xí)的索引推薦過程的本質(zhì)是馬爾可夫過程，首先通過神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)不同索引前后對負(fù)載的代價影響，之后根據(jù)已經(jīng)創(chuàng)建的索引預(yù)測下一個應(yīng)該建立索引的概率，最終根據(jù)不同的負(fù)載推薦出合適的索引配置。

使用強(qiáng)化學(xué)習(xí)可以訓(xùn)練一個智能代理來進(jìn)行索引推薦，可以基于最終訓(xùn)練好的模型來進(jìn)行推薦，無須每次都重新運(yùn)行算法，但是訓(xùn)練過程往往需要花費(fèi)大量的時間。由于強(qiáng)化學(xué)習(xí)算法對獎勵函數(shù)（reward）的設(shè)計較為敏感，索引推薦過程中有的索引可能對負(fù)載提升效果不佳，有的可能對負(fù)載提升巨大，造成訓(xùn)練過程不穩(wěn)定，最終導(dǎo)致結(jié)果變差。這樣差異過大的獎勵值會影響強(qiáng)化學(xué)習(xí)的學(xué)習(xí)效果。

針對現(xiàn)有索引推薦模型訓(xùn)練時間長、訓(xùn)練過程不穩(wěn)定的問題，本文提出基于優(yōu)勢—演員—評論家算法（advantage actorcritic，A2C）的索引推薦模型PRELIA（parallel reinforcement learning index advisor）。PRELIA模型主要基于A2C算法解決索引選擇問題，這是因?yàn)锳2C算法可以同時訓(xùn)練演員網(wǎng)絡(luò)和評論家網(wǎng)絡(luò)，并且多線程運(yùn)行可以大大減少訓(xùn)練時間。此外，索引掃描行數(shù)是評價索引性能的一個重要指標(biāo)，PRELIA模型在狀態(tài)特征中加入了負(fù)載索引掃描行數(shù)特征矩陣。同時考慮到索引推薦過程中大量無效索引會導(dǎo)致模型計算出無效獎勵值，因此對強(qiáng)化學(xué)習(xí)中的獎勵值進(jìn)行了歸一化處理，以減少獎勵奇異值的影響。本文的主要貢獻(xiàn)如下：

a）提出索引推薦方法PRELIA。該方法主要基于A2C算法解決索引選擇問題，與之前基于強(qiáng)化學(xué)習(xí)的索引推薦模型相比，A2C算法可以多線程運(yùn)行，其訓(xùn)練時間更短。

b）在模型的狀態(tài)特征中加入了負(fù)載索引掃描行數(shù)特征矩陣，結(jié)果顯示，加入索引掃描行數(shù)特征矩陣可以減少推薦索引的索引空間占用。

c）對強(qiáng)化算法中的獎勵值進(jìn)行了歸一化，可以減少獎勵奇異值對強(qiáng)化學(xué)習(xí)的影響，提高算法穩(wěn)定性。

1 相關(guān)工作

1.1 傳統(tǒng)方法的數(shù)據(jù)庫索引推薦

早期的傳統(tǒng)方法大多使用貪心算法來進(jìn)行數(shù)據(jù)庫索引推薦，傳統(tǒng)索引推薦往往沒有考慮到索引的交互作用，既不考慮新建的索引會對已經(jīng)創(chuàng)建的索引產(chǎn)生影響，也不考慮工作負(fù)載的動態(tài)性。

Whang［1］在1985年提出的Drop算法使用啟發(fā)式規(guī)則，只能推薦單列索引，并且Drop方法的索引評估沒有基于查詢優(yōu)化器，而是基于數(shù)據(jù)的特征。Chaudhuri等人［2］為Microsoft SQL Server提出了AutoAdmin算法，AutoAdmin算法在每次的計算中可以推薦多列索引，枚舉每個索引候選對工作負(fù)載的影響，保證可以達(dá)到最優(yōu)解。之后，在AutoAdmin算法的基礎(chǔ)上又提出了DTA（database engine tuning advisor）算法，該算法首先確定每個查詢的索引候選項，然后根據(jù)原始的貪婪枚舉確定整個工作負(fù)載的索引配置。Valentin等人［3］提出了DB2Advisor算法用于IBM的BD2數(shù)據(jù)庫，該算法利用了whatif優(yōu)化器，考慮了索引交互的影響。Bruno等人［4］提出了Relaxation算法，該算法會對最優(yōu)的索引配置進(jìn)行轉(zhuǎn)換，來減少索引的存儲消耗。

基于傳統(tǒng)方法的數(shù)據(jù)庫索引推薦需要借助研究者對數(shù)據(jù)庫索引原理以及數(shù)據(jù)庫優(yōu)化器的專業(yè)知識，針對數(shù)據(jù)庫優(yōu)化器來設(shè)計合適的算法， 并且各種數(shù)據(jù)庫的優(yōu)化器有所差異，導(dǎo)致算法的普適性受限。

1.2 基于強(qiáng)化學(xué)習(xí)的數(shù)據(jù)庫索引推薦

近年來隨著深度強(qiáng)化學(xué)習(xí)［5］的發(fā)展，在許多問題上取得了非常成功的應(yīng)用，出現(xiàn)了一些基于強(qiáng)化學(xué)習(xí)的索引推薦方法。Sharma等人［6］展示了如何將深度強(qiáng)化學(xué)習(xí)方法應(yīng)用在索引選擇問題上。首先對SQL工作負(fù)載進(jìn)行語法解析，提取出索引候選項，然后利用深度強(qiáng)化學(xué)習(xí)算法DQN（deep Qnetwork）與數(shù)據(jù)庫環(huán)境進(jìn)行交互推薦出索引。Basu等人［7］提出了一種一般性的強(qiáng)化學(xué)習(xí)方法來解決數(shù)據(jù)庫調(diào)優(yōu)問題。Sadri等人［8］提出了基于深度強(qiáng)化學(xué)習(xí)的索引選擇方法，使用MDP（Markov decision process）學(xué)習(xí)數(shù)據(jù)庫負(fù)載的特征進(jìn)行索引推薦。Welborn等人［9］探討了如何使用特定任務(wù)的歸納偏置來增強(qiáng)基于學(xué)習(xí)的索引選擇，通過該方法構(gòu)建了一個索引代理，它能夠?qū)崿F(xiàn)改進(jìn)的索引并使用特定于任務(wù)的統(tǒng)計數(shù)據(jù)驗(yàn)證其行為。對于NoSQL 數(shù)據(jù)庫，Yan等人［10］提出了一種新的索引選擇方法DRLISA（deep reinforcement learning index selection approach），該方法選擇索引配置比手動選擇索引更合理，并且可以應(yīng)對 NoSQL 數(shù)據(jù)庫智能索引選擇問題。文獻(xiàn)［11］將啟發(fā)式規(guī)則和DQN算法結(jié)合，減少了強(qiáng)化學(xué)習(xí)的動作空間，證明了算法的有效性。

現(xiàn)有基于強(qiáng)化學(xué)習(xí)的索引推薦算法都存在著訓(xùn)練時間長的問題，且大多基于DQN算法。DQN算法前期需要將環(huán)境交互的數(shù)據(jù)樣本存儲到記憶單元，訓(xùn)練時隨機(jī)拿出一些數(shù)據(jù)來訓(xùn)練，訓(xùn)練初期的效果較差。因此本文提出基于A2C的數(shù)據(jù)庫索引推薦模型對以上局限性進(jìn)行改進(jìn)，A2C算法利用多線程的訓(xùn)練，可以減少訓(xùn)練時間，并且不需要存儲數(shù)據(jù)樣本，利用并行計算減少樣本的相關(guān)性，使訓(xùn)練過程更加穩(wěn)定。

2 基于多線程并行強(qiáng)化學(xué)習(xí)的數(shù)據(jù)庫索引推薦

由于A2C算法結(jié)合了價值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)，并采用多個并行的智能體與環(huán)境獨(dú)立交互計算，相比其他強(qiáng)化學(xué)習(xí)算法，具有較好的性能和穩(wěn)定性。本文提出了基于A2C強(qiáng)化學(xué)習(xí)的索引推薦模型PRELIA，本章主要介紹模型的總體架構(gòu)。

2.1 模型概述

2.1.1 形式化定義

將數(shù)據(jù)庫索引推薦過程形式化為馬爾可夫決策過程，將狀態(tài)、動作st、獎勵函數(shù)at、策略p（at+1|st）、智能體agent定義如下。

a）狀態(tài)。模型的狀態(tài)表示一個神經(jīng)網(wǎng)絡(luò)矩陣，主要包括索引的選擇度矩陣IS、索引的掃描行數(shù)特征矩陣IR以及索引的負(fù)載代價矩陣IC。狀態(tài)表示索引效果好壞的信息。

b）動作。動作矩陣的長度由候選索引的個數(shù)決定，1表示創(chuàng)建了此索引，0表示沒有創(chuàng)建此索引。

c）獎勵函數(shù)。獎勵函數(shù)用于評價索引提升的性能。在工作負(fù)載為W，索引配置為I時，第t次時間步的獎勵函數(shù)定義如下：

rt=costt（W，I）-costt（W，I）（1）

由于不同索引對SQL的提升效果差距可能很大，本文對獎勵值進(jìn)行了歸一化，將其限定在一定的范圍內(nèi)，以消除奇異值的影響。最終獎勵函數(shù)如下：

其中：cost（W，Iall）表示創(chuàng)建所有候選索引工作負(fù)載的代價;cost（W，）表示沒有創(chuàng)建任何候選索引工作負(fù)載的代價。

d）智能體。本文的智能體由演員網(wǎng)絡(luò)和價值網(wǎng)絡(luò)組成，兩個網(wǎng)絡(luò)的結(jié)構(gòu)相同，使用具有三層的完全連接的神經(jīng)網(wǎng)絡(luò)。優(yōu)勢演員—評論家算法結(jié)構(gòu)如圖1所示。

（a）演員網(wǎng)絡(luò)p（ar|st;θ）用來更新學(xué)習(xí)模型的策略，計算在狀態(tài)所采取的動作的概率分布。演員網(wǎng)絡(luò)可以針對給定的狀態(tài)產(chǎn)生最佳動作，即根據(jù)狀態(tài)神經(jīng)網(wǎng)絡(luò)矩陣產(chǎn)生最佳的索引配置。

（b）評論家網(wǎng)絡(luò)V（st，θv）用來評價狀態(tài)St執(zhí)行動作at的優(yōu)劣，評價索引配置的效果。算法的優(yōu)勢函數(shù)定義如下：

其中：rt+i表示即時獎賞，γ∈［0，1］為折扣因子，代表未來獎賞對于累計獎賞的重要程度。當(dāng)n=1時，其為1步回報優(yōu)勢函數(shù);當(dāng)n=k時，其為k步回報優(yōu)勢函數(shù)。該算法的演員網(wǎng)絡(luò)和評論家網(wǎng)絡(luò)的損失函數(shù)如下所示。

aloss=θlogπ（at|st;θ）A（st，at）（4）

其中：R表示智能體在當(dāng)前狀態(tài)下依據(jù)策略選擇動作所獲得的回報值;V（st;θv）表示該狀態(tài)下的值函數(shù);A（st;at）表示優(yōu)勢函數(shù)。

2.1.2 模型總體框架

由于 A2C 算法具有多線程處理能力，有利于處理大規(guī)模狀態(tài)空間的任務(wù)，本文將 A2C 強(qiáng)化學(xué)習(xí)算法應(yīng)用于索引推薦領(lǐng)域，設(shè)計了索引推薦模型PRELIA。

首先對負(fù)載進(jìn)行語法解析，解析出索引候選項，包括where、group by、order by后的字段。對索引候選項進(jìn)行編碼，強(qiáng)化學(xué)習(xí)的動作狀態(tài)，然后訪問數(shù)據(jù)庫獲取負(fù)載的特征信息、負(fù)載代價、索引掃描行數(shù)、索引存儲空間，同時根據(jù)索引候選項的信息計算出索引的選擇度，將這些信息作為強(qiáng)化學(xué)習(xí)算法的狀態(tài)信息。經(jīng)過以上處理后開始進(jìn)行模型的訓(xùn)練過程，直到模型最終收斂。

如圖2所示，本文的解決方案由五個模塊組成：

a）語法解析。將工作負(fù)載采用語法解析庫解析為語法樹結(jié)構(gòu)。

b）候選索引。分析語法樹中的where、group by、order by條件選出候選索引，構(gòu)成整個負(fù)載的候選索引空間。

c）獲取負(fù)載特征。通過訪問數(shù)據(jù)庫，獲取負(fù)載的特征信息，如掃描行數(shù)、選擇度等。

d）并行強(qiáng)化學(xué)習(xí)的索引推薦模型。將負(fù)載特征作為環(huán)境向量，候選索引作為動作向量，智能體與環(huán)境交互，對動作進(jìn)行評估，返回獎勵給智能體進(jìn)行下一輪次的決策。

e）索引評估。估算創(chuàng)建索引后負(fù)載的代價和索引的存儲空間大小。

2.2 算法流程

PRELIA模型的訓(xùn)練流程如算法1所示。首先對工作負(fù)載進(jìn)行語法解析（第1～11行），解析出索引候選項，然后訪問數(shù)據(jù)庫獲取負(fù)載的各種特征信息作為A2C算法的輸入，A2C算法推薦出索引（第12～33行），通過數(shù)據(jù)庫評估索引的效果，不斷進(jìn)行訓(xùn)練直到算法收斂。

算法1 PRELIA

輸入：工作負(fù)載W;學(xué)習(xí)率η;衰減因子γ。

輸出：最佳索引配置I。

1 ?//工作負(fù)載預(yù)處理

2 ?function PreProcessing（W）

3? ?I=［］ //候選索引

4? ?for each 查詢語句qt? do

5??? I←從查詢中提取索引候選

6? ?end for

7? ?IR←創(chuàng)建索引掃描行數(shù)矩陣

8? ?IS←創(chuàng)建索引選擇度矩陣

9? ?IC←創(chuàng)建索引負(fù)載代價矩陣

10? return IR，IS，IC

11 end function

12 //強(qiáng)化學(xué)習(xí)訓(xùn)練

13 function PRELIA（I，IR，IS，IC，N）

14? 初始化策略網(wǎng)絡(luò)actor

15? 初始化價值網(wǎng)絡(luò)critic

16? 初始化狀態(tài)s=IR∪IS∪IC

17? 創(chuàng)建N個環(huán)境Envs

18? while （true） do：

19?? 重置環(huán)境Env，索引配置C

20?? for each Env∈Envs do

21??? ?value←演員網(wǎng)絡(luò)計算value

22??? ?st+1←執(zhí)行動作a

23??? ?reward←計算獎勵

24??? ?存儲reward，value

25?? end for

26?? 計算優(yōu)勢函數(shù)（式（3））

27?? 計算actorloss，criticloss

28?? 累計演員網(wǎng)絡(luò)更新

29?? 累計評論家網(wǎng)絡(luò)更新

30?? 更新全局神經(jīng)網(wǎng)絡(luò)模型參數(shù)

31?? ?until episode>episodemax

32? end while

33 ?end function

3 實(shí)驗(yàn)結(jié)果與分析

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

a）實(shí)驗(yàn)數(shù)據(jù)。本文在兩個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，即標(biāo)準(zhǔn)數(shù)據(jù)庫基準(zhǔn)TCPH 和TCPDS數(shù)據(jù)集。TCPH數(shù)據(jù)集包括22條查詢模板，61個數(shù)據(jù)庫字段屬性。TPCDS包括99條查詢模板，429個數(shù)據(jù)庫字段屬性。實(shí)驗(yàn)使用PostgreSQL數(shù)據(jù)庫，針對兩個數(shù)據(jù)集分別生成了10 GB數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫中，每個查詢模板生成了一條查詢語句作為負(fù)載。本文使用了文獻(xiàn)［12］開發(fā)的傳統(tǒng)ISP算法的評估平臺，平臺包含了索引推薦的傳統(tǒng)算法Relaxation、Extend、DTA等。

b）實(shí)驗(yàn)環(huán)境。實(shí)驗(yàn)全部運(yùn)行在Ubuntu Linux上，機(jī)器的主要配置為：Intel CoreTM i710875H CPU@2.30 GHz（16 CPUs），4 GB內(nèi)存和200 GB機(jī)械硬盤。

c）超參數(shù)設(shè)置。本文基于A2C的深度強(qiáng)化學(xué)習(xí)算法，使用Adam梯度下降法進(jìn)行網(wǎng)絡(luò)參數(shù)更新，由于學(xué)習(xí)率過大會導(dǎo)致模型在參數(shù)更新時跳過最優(yōu)解，導(dǎo)致訓(xùn)練不穩(wěn)定，所以設(shè)置學(xué)習(xí)率η=0.001。同時設(shè)置學(xué)習(xí)率衰減，使模型在訓(xùn)練后期更加穩(wěn)定，更容易達(dá)到全局最優(yōu)點(diǎn)，設(shè)置為每2 000輪衰減為原來的92%。折扣因子γ=0.9，由于索引推薦的過程關(guān)注未來價值，γ設(shè)置為了較大值。實(shí)驗(yàn)用16 個線程并行訓(xùn)練，每回合結(jié)束更新一次網(wǎng)絡(luò)參數(shù)，總計訓(xùn)練了10 000輪，每100輪測試一次模型。

d）評價指標(biāo)。實(shí)驗(yàn)采用負(fù)載代價提升率（負(fù)載使用推薦索引配置相對負(fù)載無索引相比代價的提升率）和索引占用存儲空間大小作為評價模型的效果評價指標(biāo)，同時也比較了訓(xùn)練時間與訓(xùn)練過程的穩(wěn)定性。

負(fù)載代價提升率公式為

3.2 基線算法

本文在兩個數(shù)據(jù)集上將PRELIA與四種算法進(jìn)行對比。其中，DB2 Advisor、Relaxation、DTA為傳統(tǒng)索引推薦方法，IndexAdvisor、SWIRL為強(qiáng)化學(xué)習(xí)索引推薦方法。

a）DB2 Advisor［3］利用優(yōu)化器的假設(shè)功能實(shí)現(xiàn)索引推薦，但是由于該方法面向單個查詢進(jìn)行優(yōu)化，可能會丟失整體查詢較好的索引。

b）Relaxation［4］方法在候選集合上循環(huán)使用轉(zhuǎn)換規(guī)則以減少時間、空間占比。該方法首先利用查詢優(yōu)化器為獲取每個查詢可能的最佳索引;然后在得到的負(fù)載上的最佳索引候選集上不斷進(jìn)行relax過程，以降低存儲開銷的同時保持盡可能高的時間收益。

c）DTA［2］是AutoAdmin算法的完善版本。首先根據(jù)貪婪枚舉確定每個查詢的候選索引，再為整個負(fù)載確定索引配置。DTA作為改進(jìn)后的算法，在各個方面都有了很大提升，如加入了時間限制、算法可以隨時中斷。

d）IndexAdvisor［13］算法集成了啟發(fā)式規(guī)則和深度強(qiáng)化學(xué)習(xí)，支持對表的多索引訪問。采用深度Q網(wǎng)絡(luò)（DQN）并使用啟發(fā)式規(guī)則，大大減少了學(xué)習(xí)中動作空間和狀態(tài)空間的大小。

e）SWIRL［14］算法通過動作屏蔽的方法來屏蔽無效動作，并結(jié)合代價估計器進(jìn)行代價評估，使模型可以更有效地訓(xùn)練。

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 負(fù)載代價提升率與索引空間占用對比

對各算法進(jìn)行實(shí)驗(yàn)比較，分別在TPCH與TPCDS數(shù)據(jù)集上測試了各算法的索引推薦結(jié)果，評價指標(biāo)為負(fù)載代價提升百分比和索引存儲大小，結(jié)果如表1、2所示。

從表1可以看出，在TPCH數(shù)據(jù)集上，基于代價模型的DB2 Advisor算法的負(fù)載代價提升最小，索引存儲占用最大，這是因?yàn)镈B2 Advisor算法基于代價模型進(jìn)行優(yōu)化，沒有考慮索引的存儲大小。Relaxation 在TPCH數(shù)據(jù)集上的索引占用僅次于PRELIA模型，是因?yàn)镽elaxation算法的relax過程可以在減少索引代價的同時盡量減少索引空間占用。IndexAdvisor模型在索引代價提升上略低于PRELIA模型，由于PRELIA模型在環(huán)境狀態(tài)中考慮了索引掃描行數(shù)特征，在索引空間占用上優(yōu)于IndexAdvisor與SWIRL算法。

從表2可以看出，在TPCDS數(shù)據(jù)集上，IndexAdvisor模型的負(fù)載代價提升率最少，出現(xiàn)這種情況的原因是IndexAdvisor模型的環(huán)境狀態(tài)表示只包含查詢代價，不能很好地對數(shù)據(jù)庫環(huán)境進(jìn)行建模。 PRELIA在TPCDS數(shù)據(jù)集上也取得了較優(yōu)的負(fù)載代價提升率和索引空間大小。

綜上所述，由于PRELIA加入了索引掃描行數(shù)特征矩陣，PRELIA在保證索引推薦質(zhì)量的同時，索引的推薦空間更小。

3.3.2 訓(xùn)練穩(wěn)定性對比

圖3～7分別是IndexAdvisor、SWIRL、PRELIA在TPCH與TPCDS數(shù)據(jù)集訓(xùn)練獎勵值reward的變化曲線。圖中顯示了訓(xùn)練10 000輪的結(jié)果，其中每訓(xùn)練100輪就輸出一次獎勵值進(jìn)行測試。

圖3、5、7是不同算法在TPCH數(shù)據(jù)集上獎勵值隨訓(xùn)練輪次增加的變化過程。從圖中對比可以看出，PRELIA模型的波動次數(shù)最少，而IndexAdvisor模型在7 000輪左右獎勵值還呈上升趨勢，收斂速度慢于PRELIA算法。SWIRL在4 000輪之前發(fā)生了多次波動才達(dá)到獎勵最大值，PRELIA在3 000輪左右就已經(jīng)達(dá)到，說明SWIRL比PRELIA算法曲折，穩(wěn)定性不如PRELIA模型。IndexAdvisor與SWIRL在訓(xùn)練前期穩(wěn)定性低于PRELIA，是因?yàn)闆]有對獎勵進(jìn)行歸一化，受到了獎勵奇異值的影響，所以訓(xùn)練曲線波動較多。

圖4、6、8是不同算法在TPCDS數(shù)據(jù)集上獎勵值隨訓(xùn)練輪次增加的變化過程。從圖中對比可以看出，IndexAdvisor在TPCDS數(shù)據(jù)集上發(fā)生了5次較為劇烈的獎勵值下降，分別在1 000輪、2 000輪、4 000輪、5 000輪、6 000輪左右。SWIRL在TPCDS數(shù)據(jù)集上在2 000輪之前波動了6次，并且在訓(xùn)練9 000輪左右才達(dá)到了獎勵最大值。而PRELIA模型只在600輪左右有一次大的獎勵值下降，在7 000輪后的訓(xùn)練獎勵值已經(jīng)較為穩(wěn)定。對比可知，PRELIA比IndexAdvisor模型在TPCDS數(shù)據(jù)集上的訓(xùn)練過程更穩(wěn)定。

綜上所述，PRELIA基于A2C算法，同時訓(xùn)練演員網(wǎng)絡(luò)和評論家網(wǎng)絡(luò)，可以更準(zhǔn)確地估計獎勵值，同時對PRELIA的獎勵值進(jìn)行了歸一化處理，減少了獎勵奇異值對強(qiáng)化學(xué)習(xí)的影響，算法的穩(wěn)定性高于基線算法。

3.3.3 訓(xùn)練時間對比

表3顯示了IndexAdvisor、SWIRL與PRELIA在TPCH與TPCDS數(shù)據(jù)集上的訓(xùn)練時間對比。由于傳統(tǒng)算法DB2 Advisor、Relaxation、DTA不需要訓(xùn)練，所以本文只比較了基于強(qiáng)化學(xué)習(xí)算法IndexAdvisor與SWIRL的訓(xùn)練時間。

觀察表3可知，IndexAdvisor模型在TPCH與TPCDS的訓(xùn)練時間均高于PRELIA模型。兩個模型在TPCDS數(shù)據(jù)集上的訓(xùn)練時間均高于TPCH數(shù)據(jù)集，是因?yàn)門PCDS表結(jié)構(gòu)與負(fù)載復(fù)雜度都高于TPCH。其中，PRELIA模型的訓(xùn)練時間在TPCH數(shù)據(jù)集是IndexAdvisor模型的1/4左右，在TPCDS數(shù)據(jù)集上是IndexAdvisor模型的1/5左右，訓(xùn)練時間均短于IndexAdvisor算法。而SWIRL的訓(xùn)練時間比IndexAdvisor的訓(xùn)練時間略高，這是因?yàn)镾WIRL使用了動作屏蔽，增加了計算時間。由于PRELIA使用了A2C算法，可以多線程運(yùn)行，每個線程可以并行地與環(huán)境交互，這樣可以大大地減少訓(xùn)練時間。在實(shí)驗(yàn)中，PRELIA使用了16個線程并行訓(xùn)練模型，相比于單線程訓(xùn)練，可以減少數(shù)倍的訓(xùn)練時間。

3.3.4 推薦結(jié)果分析

PRELIA在TPCH數(shù)據(jù)集的索引推薦結(jié)果如表4所示。

TPCH數(shù)據(jù)集的數(shù)據(jù)來自銷售系統(tǒng)。其中，lineitem商品表和orders訂單表是數(shù)據(jù)集中的較為關(guān)鍵的表，也是數(shù)據(jù)量較大的表。從表4可以看出，PRELIA推薦的索引涵蓋SQL負(fù)載中一些常用的連接字段，例如lineitem表的l_orderkey和orders表的o_orderkey，這些索引有助于加速相關(guān)SQL的表連接操作。一些索引涉及到過濾操作，如orders表的o_orderdate可以提高按日期范圍過濾的查詢效率，lineitem表的l_extendedprice和lineitem表的l_tax等索引有助于提高對具體金額和稅率的聚合查詢性能。

PRELIA在TPCDS數(shù)據(jù)集的推薦結(jié)果如表5所示。

TPCDS數(shù)據(jù)集來自真實(shí)的銷售決策支持系統(tǒng)，在表5的推薦結(jié)果中，其中一些索引可加速多表連接查詢的效率，如catalog_sales表的cs_bill_customer_sk、cs_promo_sk、索引，customer表的c_address_sk、c_customer_sk索引。還有一些索引可以加速排序的效率，如catalog_sales表的cs_sold_date_sk。其中customer_demographics表的cd_marital_status索引，date_dim表的d_year索引可以加速分組操作的效率。

綜上所述，PRELIA的索引推薦結(jié)果可以有效地針對TPCH與TPCDS數(shù)據(jù)集。

3.3.5 消融實(shí)驗(yàn)

本文設(shè)計了以下幾個變體用來做消融實(shí)驗(yàn)。

a）PRELIA_nRows。此變體不考慮PRELIA的環(huán)境中加入索引掃描行數(shù)，即環(huán)境矩陣中不加入工作負(fù)載的掃描行數(shù)矩陣。

b）PRELIA_nNorm。此變體不對PRELIA的獎勵函數(shù)進(jìn)行歸一化處理，即獎勵函數(shù)使用式（1）。

從表6、7可以看出，PRELIA相比其他兩種變體在TPCH與TPCDS數(shù)據(jù)集上的評價指標(biāo)均是最優(yōu)的。PRELIA_nNorm沒有對獎勵函數(shù)進(jìn)行歸一化處理，由于獎勵值的差距較大，對模型最終推薦的結(jié)果影響比較大，導(dǎo)致負(fù)載代價提升較差；PRELIA_nRows沒有在狀態(tài)中加入對掃描行數(shù)的影響，最終負(fù)載代價提升與PRELIA差不多，但是在索引空間大小上占用了更多空間。由于最終數(shù)據(jù)庫使用索引不僅僅考慮負(fù)載代價，在負(fù)載代價相同的情況下，會優(yōu)先選擇掃描行數(shù)少的索引。

4 結(jié)束語

索引選擇是數(shù)據(jù)庫優(yōu)化的一個重要方面。本文提出了一個新的索引推薦模型PRELIA。該算法以A2C算法為基礎(chǔ)，利用算法的并發(fā)性，減少了強(qiáng)化學(xué)習(xí)算法的訓(xùn)練時間，在環(huán)境狀態(tài)中加入索引掃描行數(shù)矩陣，減少了推薦索引空間占用。同時，PRELIA對獎勵函數(shù)進(jìn)行了歸一化，算法有更好的穩(wěn)定性。在未來工作中，如何更好地在動態(tài)負(fù)載中保證索引的推薦效果將是下一步的研究重點(diǎn)。

參考文獻(xiàn)：

[1]Whang K Y. Index selection in relational databases［M］//Ghosh S P， Kambayashi Y， Tanaka K. Foundations of Data Organization.Boston， MA：Springer，1987：487-500.

［2]Chaudhuri S， Narasayya V R. An efficient， costdriven index selection tool for Microsoft SQL server［C］//Proc of the 23rd International Conference on Very Large Data Bases.San Francisco，CA：Morgan Kaufmann Publishers Inc.，1997：146-155.

［3]Valentin G， Zuliani M， Zilio D C， et al. DB2 Advisor： an optimizer smart enough to recommend its own indexes［C］//Proc of the 16th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2000：101-110.

［4]Bruno N， Chaudhuri S.Automatic physical database tuning：a relaxationbased approach［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2005：227-238.

［5]Mnih V， Kavukcuoglu K， Silver D， et al. Humanlevel control through deep reinforcement learning［J］.Nature，2015，518（7540）：529-533.

［6]Sharma A， Schuhknecht F M， Dittrich J. The case for automatic database administration using deep reinforcement learning［EB/OL］.（2018-01-17）.https：//arxiv.org/abs/1801.05643.

［7]Basu D， Lin Qian， Chen Weidong， et al. Costmodel oblivious database tuning with reinforcement learning［M］//Chen Qiming，Hameurlain A，Toumani F，et al.Database and Expert Systems Applications.Cham：Springer，2015：253-268.

［8]Sadri Z， Gruenwald L， Leal E. Online index selection using deep reinforcement learning for a cluster database［C］//Proc of the 36th International Conference on Data Engineering Workshops.Piscataway，NJ：IEEE Press，2020：158-161.

［9]Welborn J， Schaarschmidt M， Yoneki E. Learning index selection with structured action spaces［EB/OL］.（2019-09-16）.https：//arxiv.org/abs/1909.07440.

［10]Yan Yu， Yao Shun， Wang Hongzhi， et al. Index selection for NoSQL database with deep reinforcement learning［J］.Information Sciences，2021，561：20-30.

［11]Sharma V， Dyreson C， Flann N. MANTIS： multiple type and attribute index selection using deep reinforcement learning［C］//Proc of the 25th International Database Engineering & Applications Symposium.New York：ACM Press，2021：56-64.

［12]Kossmann J， Halfpap S， Jankrift M， et al. Magic mirror in my hand， which is the best in the land？An experimental evaluation of index selection algorithms［J］.Proceedings of the VLDB Endowment，2020，13（12）：2382-2395.

［13]Lan Hai， Bao Zhifeng， Peng Yuwei. An index advisor using deep reinforcement learning［C］//Proc of the 29th ACM International Conference on Information and Knowledge Management.New York：ACM Press，2020：2105-2108.

［14]Kossmann J， Kastius A， Schlosser R. SWIRL： selection of workloadaware indexes using reinforcement learning［C］//Proc of the 25th International Conference on Extending Database Technology.2022：155-168.

［15]孫彧，曹雷，陳希亮，等.多智能體深度強(qiáng)化學(xué)習(xí)研究綜述［J］.計算機(jī)工程與應(yīng)用，2020，56（5）：13-24.（Sun Yu， Cao Lei， Chen Xiliang， et al. Review of research on deep reinforcement learning of multiple agents［J］.Computer Engineering and Applications，2020，56（5）：13-24.）

［16]李國良，于戈，楊俊，等.數(shù)據(jù)庫系統(tǒng)新型技術(shù)專題前言［J］.軟件學(xué)報，2022，33（3）：771-773.（Li Guoliang， Yu Ge， Yang Jun， et al. Foreword on new technology of database system［J］.Journal of Software，2022，33（3）：771-773.）

［17]汪晨，曾凡玉，郭九霞.憶增強(qiáng)型深度強(qiáng)化學(xué)習(xí)研究綜述［J］.型微型計算機(jī)系統(tǒng)，2021，42（3）：454-461.（Wang Chen， Zeng Fanyu， Guo Jiuxia. Review of memoryenhancing deep reinforcement learning［J］.Journal of Chinese Computer Systems，2021，42（3）：454-461.）

［18]楊國平，喬少杰，屈露露.學(xué)習(xí)型數(shù)據(jù)庫索引推薦技術(shù)綜述［J］.重慶理工大學(xué)學(xué)報：自然科學(xué)，2022，36（6）：189-199.（Yang Guoping， Qiao Shaojie， Qu Lulu. Review of indexing recommendation technology for learning databases［J］.Journal of Chongqing University of Technology：Natural Science，2022，36（6）：189-199.）

［19]劉全，翟建偉，章宗長，等.深度強(qiáng)化學(xué)習(xí)綜述［J］.計算機(jī)學(xué)報，2018，41（1）：1-27.（Liu Quan， Zhai Jianwei， Zhang Zongchang， et al. Review of deep reinforcement learning［J］.Chinese Journal of Computers，2018，41（1）：1-27.）