高瑞瑋，葉 青，徐小玲，劉 雯，韓 楠，楊國(guó)平，徐康鐳

(1.成都信息工程大學(xué) 軟件工程學(xué)院，四川 成都 610225；2.四川省金科成地理信息技術(shù)有限公司，四川 成都 610095；3.成都安聯(lián)云防保安服務(wù)有限公司，四川 成都 610095；4.四川省大數(shù)據(jù)中心，四川 成都 610096)

0 引言

隨著云計(jì)算技術(shù)[1]被廣泛應(yīng)用于各行各業(yè)，云數(shù)據(jù)庫(kù)也得到了蓬勃發(fā)展。云數(shù)據(jù)庫(kù)的查詢優(yōu)化是大型系統(tǒng)實(shí)現(xiàn)良好查詢性能的關(guān)鍵[2]。查詢優(yōu)化的目標(biāo)是為給定查詢找到一組具有最低延遲的執(zhí)行計(jì)劃。對(duì)于復(fù)雜的多表連接查詢，將產(chǎn)生數(shù)千萬(wàn)個(gè)不同連接順序的候選執(zhí)行計(jì)劃。如何在數(shù)千萬(wàn)個(gè)候選執(zhí)行計(jì)劃中確定一組最佳連接順序的執(zhí)行計(jì)劃是查詢優(yōu)化中極具挑戰(zhàn)性的問(wèn)題[3]。此外，不同連接順序能夠顯著影響執(zhí)行計(jì)劃的代價(jià)和延遲。例如，一個(gè)糟糕的連接順序的執(zhí)行計(jì)劃需要花費(fèi)數(shù)小時(shí)甚至數(shù)天的查詢時(shí)間，而一個(gè)較好的連接順序的執(zhí)行計(jì)劃僅花費(fèi)ms級(jí)別的查詢時(shí)間。因此，連接順序選擇被視為查詢優(yōu)化的重難點(diǎn)[4]。

云數(shù)據(jù)庫(kù)的查詢優(yōu)化方法為啟發(fā)式算法[5]，往往基于專家經(jīng)驗(yàn)，但是仍然存在局限性[6]。例如，動(dòng)態(tài)規(guī)劃算法需要巨大的搜索空間，花費(fèi)較長(zhǎng)的優(yōu)化時(shí)間。QuickPick-1000[7]的優(yōu)化時(shí)間較短，但是容易生成糟糕的連接順序執(zhí)行計(jì)劃，使得查詢性能下降，并且傳統(tǒng)的查詢優(yōu)化方法無(wú)法從歷史查詢中學(xué)習(xí)經(jīng)驗(yàn)。例如，對(duì)于相同的多表連接查詢會(huì)重復(fù)生成糟糕的執(zhí)行計(jì)劃，進(jìn)而產(chǎn)生較高的延遲[8]。

最近，利用人工智能技術(shù)解決查詢優(yōu)化取得了成功。例如，Marcus等[9]首次提出了基于強(qiáng)化學(xué)習(xí)的優(yōu)化器Rejoin。隨后Krishnan等[10]提出了利用Deep Q-network(DQN)[11]算法解決連接順序選擇?，F(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器雖然能夠克服傳統(tǒng)的查詢優(yōu)化方法的局限性，但是仍然存在著一些缺陷：

① Rejoin和DQ等現(xiàn)有優(yōu)化器的編碼方法不包括物理運(yùn)算符和執(zhí)行計(jì)劃的結(jié)構(gòu)特征，進(jìn)而無(wú)法準(zhǔn)確地表示執(zhí)行計(jì)劃。物理運(yùn)算符是指執(zhí)行計(jì)劃中單表的掃描方式和多表之間的連接方式。

② Rejoin和DQ等現(xiàn)有優(yōu)化器并沒(méi)有設(shè)計(jì)狀態(tài)表示模型，無(wú)法捕捉執(zhí)行計(jì)劃的結(jié)構(gòu)特征，進(jìn)而無(wú)法為后續(xù)強(qiáng)化學(xué)習(xí)算法提供準(zhǔn)確的狀態(tài)表示。

③ Rejoin和DQ等現(xiàn)有優(yōu)化器使用數(shù)據(jù)庫(kù)代價(jià)估計(jì)器為執(zhí)行計(jì)劃估計(jì)代價(jià)，并將代價(jià)作為獎(jiǎng)勵(lì)目標(biāo)。對(duì)于復(fù)雜的多表連接查詢，并不能準(zhǔn)確估計(jì)中間結(jié)果集的代價(jià)，容易出現(xiàn)錯(cuò)誤的代價(jià)估計(jì)[12]，進(jìn)而生成次優(yōu)的執(zhí)行計(jì)劃。

④ Neo[13]和AlphaJoin[14]等現(xiàn)有優(yōu)化器使用價(jià)值網(wǎng)絡(luò)為執(zhí)行計(jì)劃預(yù)測(cè)延遲，并將延遲作為優(yōu)化目標(biāo)。雖然能夠避免錯(cuò)誤的代價(jià)估計(jì)導(dǎo)致生成次優(yōu)的執(zhí)行計(jì)劃，但是Neo和AlphaJoin的價(jià)值網(wǎng)絡(luò)的預(yù)測(cè)準(zhǔn)確性較低，并且需要高質(zhì)量的歷史查詢樣本進(jìn)行訓(xùn)練[15]。

⑤ Neo等現(xiàn)有優(yōu)化器使用簡(jiǎn)單的搜索策略指導(dǎo)連接順序選擇，并沒(méi)有嘗試在更大的搜索空間中進(jìn)行探索，可能會(huì)降低找到最優(yōu)執(zhí)行計(jì)劃的概率，容易陷入局部最優(yōu)解。

⑥ Rejoin和DQ等現(xiàn)有優(yōu)化器的強(qiáng)化學(xué)習(xí)算法的探索性較差，容易受到超參數(shù)的影響，并且訓(xùn)練速度較慢、收斂不穩(wěn)定[16-18]。

針對(duì)上述問(wèn)題，提出了一種新型基于異步Soft Actor-Critic的連接查詢優(yōu)化器(Asynchronous Soft Actor-Critic for Join Query，ASA-Join)。ASA-Join集成了一種新的編碼方法，將物理運(yùn)算符和執(zhí)行計(jì)劃的結(jié)構(gòu)特征進(jìn)行編碼，能夠準(zhǔn)確地表示執(zhí)行計(jì)劃。ASA-Join設(shè)計(jì)了狀態(tài)表示模型，利用BiGRU[19]模型來(lái)捕捉執(zhí)行計(jì)劃的結(jié)構(gòu)特征，進(jìn)而能夠?yàn)楫惒絊oft Actor-Critic提供準(zhǔn)確的狀態(tài)表示。ASA-Join設(shè)計(jì)了新的獎(jiǎng)勵(lì)機(jī)制，利用多任務(wù)學(xué)習(xí)方法[20]將執(zhí)行計(jì)劃的延遲和代價(jià)均作為優(yōu)化目標(biāo)，進(jìn)而使得執(zhí)行計(jì)劃能夠反映真實(shí)的查詢時(shí)間。ASA-Join利用多線程通信機(jī)制設(shè)計(jì)了異步Soft Actor-Critic算法。異步Soft Actor-Critic算法指導(dǎo)連接順序選擇，利用最大熵機(jī)制能夠增加動(dòng)作選擇的隨機(jī)性，進(jìn)而提高智能體的探索能力，盡可能從全局上搜索最優(yōu)執(zhí)行計(jì)劃。異步Soft Actor-Critic算法不依賴于精確的超參數(shù)調(diào)整，并且多線程通信機(jī)制能夠?qū)崿F(xiàn)異步更新，進(jìn)而加快訓(xùn)練速度并提高收斂穩(wěn)定性。在真實(shí)數(shù)據(jù)集Join Order Benchmark (JOB)[21]和TPC-H上對(duì)ASA-Join的性能進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明，ASA-Join的代價(jià)和延遲均低于現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化方法。

1 ASA-Join的整體架構(gòu)

ASA-Join的整體架構(gòu)如圖1所示。

圖1 ASA-Join的整體架構(gòu)Fig.1 The overall framework of ASA-Join

ASA-Join主要由3個(gè)關(guān)鍵部分構(gòu)成：編碼方法、狀態(tài)表示模型以及異步Soft Actor-Critic算法。

① 編碼方法主要由查詢語(yǔ)句編碼Query-Encoding和執(zhí)行計(jì)劃編碼Plan-Encoding組成。Query-Encoding主要對(duì)查詢語(yǔ)句的連接謂詞和選擇謂詞進(jìn)行編碼，Plan-Encoding主要對(duì)執(zhí)行計(jì)劃的結(jié)構(gòu)特征和物理運(yùn)算符進(jìn)行編碼，進(jìn)而生成執(zhí)行計(jì)劃向量樹(shù)。

② 狀態(tài)表示模型主要對(duì)執(zhí)行計(jì)劃向量樹(shù)進(jìn)行序列化處理，生成執(zhí)行計(jì)劃向量集，并將執(zhí)行計(jì)劃向量集作為BiGRU模型的輸入，進(jìn)而B(niǎo)iGRU模型能夠捕捉執(zhí)行計(jì)劃的結(jié)構(gòu)特征，為異步Soft Actor-Critic提供準(zhǔn)確的狀態(tài)表示。

③ 異步Soft Actor-Critic算法包含1個(gè)Actor網(wǎng)絡(luò)、2個(gè)Value-Critic和2個(gè)Q-Critic。Actor網(wǎng)絡(luò)將當(dāng)前執(zhí)行計(jì)劃狀態(tài)作為輸入，進(jìn)而從動(dòng)作空間中選擇將要執(zhí)行的動(dòng)作，例如選擇2個(gè)表進(jìn)行連接，并指定掃描方式(Sequence-Scan，Index-Scan)以及連接方式(Hash-Join，Nest-Loop-Join，Merge-Join)。Value-Critic網(wǎng)絡(luò)主要對(duì)當(dāng)前執(zhí)行計(jì)劃狀態(tài)進(jìn)行評(píng)估，輸出狀態(tài)價(jià)值。Q-Critic網(wǎng)絡(luò)主要對(duì)當(dāng)前執(zhí)行計(jì)劃狀態(tài)下將要執(zhí)行的動(dòng)作進(jìn)行評(píng)估，輸出動(dòng)作價(jià)值。每當(dāng)ASA-Join執(zhí)行Actor網(wǎng)絡(luò)選擇的動(dòng)作后，將更新執(zhí)行計(jì)劃編碼，進(jìn)而更新執(zhí)行計(jì)劃狀態(tài)，使得Actor網(wǎng)絡(luò)從動(dòng)作空間中再次選擇將要執(zhí)行的動(dòng)作，直到達(dá)到終止?fàn)顟B(tài)(所有表均被連接，生成完整執(zhí)行計(jì)劃)。

進(jìn)一步地，完整執(zhí)行計(jì)劃將被發(fā)送給云數(shù)據(jù)庫(kù)，云數(shù)據(jù)庫(kù)的代價(jià)估計(jì)器和執(zhí)行器分別為完整執(zhí)行計(jì)劃給出代價(jià)和延遲，并利用多任務(wù)學(xué)習(xí)方法將執(zhí)行計(jì)劃的代價(jià)和延遲均作為獎(jiǎng)勵(lì)目標(biāo)。需要注意的是，收集執(zhí)行計(jì)劃的代價(jià)不需要運(yùn)行執(zhí)行計(jì)劃，因此將執(zhí)行計(jì)劃的代價(jià)作為第1階段的獎(jiǎng)勵(lì)目標(biāo)，使得ASA-Join能夠快速理解以代價(jià)作為獎(jiǎng)勵(lì)目標(biāo)的云數(shù)據(jù)庫(kù)優(yōu)化方式。執(zhí)行計(jì)劃的延遲是云數(shù)據(jù)庫(kù)運(yùn)行執(zhí)行計(jì)劃的時(shí)間，難以短時(shí)間內(nèi)獲取，因此將執(zhí)行計(jì)劃的延遲作為第2階段的獎(jiǎng)勵(lì)目標(biāo)。在第1階段訓(xùn)練后，ASA-Join能夠生成較優(yōu)的執(zhí)行計(jì)劃，再使用執(zhí)行計(jì)劃的延遲作為獎(jiǎng)勵(lì)目標(biāo)進(jìn)行微調(diào)，使得ASA-Join最終生成的執(zhí)行計(jì)劃能夠反映真實(shí)的執(zhí)行時(shí)間，并避免錯(cuò)誤的代價(jià)估計(jì)導(dǎo)致生成次優(yōu)的執(zhí)行計(jì)劃。

此外，在ASA-Join的訓(xùn)練過(guò)程中，利用多線程通信機(jī)制來(lái)異步更新Soft Actor-Critic的參數(shù)。在每個(gè)線程中均包含具有相同結(jié)構(gòu)和相同參數(shù)的Soft Actor-Critic。選擇任意一個(gè)線程中的Soft Actor-Critic作為全局模型，其余線程中的Soft Actor-Critic作為計(jì)算模型。計(jì)算模型主要與云數(shù)據(jù)庫(kù)進(jìn)行交互，獲取數(shù)據(jù)樣本(狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)等信息)來(lái)計(jì)算Soft Actor-Critic中各個(gè)網(wǎng)絡(luò)的參數(shù)梯度，但并不用于更新計(jì)算模型，而是用于更新全局模型的參數(shù)。

2 ASA-Join的編碼方法

2.1 Query-Encoding

Query-Encoding的示例如圖2所示。

圖2 Query-Encoding的示例Fig.2 Example of Query-Encoding

主要對(duì)查詢語(yǔ)句的連接謂詞和選擇謂詞進(jìn)行編碼。連接謂詞首先使用維度為N的鄰接矩陣M進(jìn)行編碼，其中N為云數(shù)據(jù)庫(kù)中表的數(shù)量。鄰接矩陣的元素Mi,j取值為0或者1，1代表第i個(gè)表與第j個(gè)表具有連接關(guān)系，0代表第i個(gè)表與第j個(gè)表無(wú)連接關(guān)系，i和j均為整數(shù)，且0

vi*(N-1)+j=Mi,j

(1)

式中，vi*(N-1)+j為連接謂詞向量v的第i*(N-1)+j個(gè)位置上的值。選擇謂詞使用獨(dú)熱向量進(jìn)行編碼，生成選擇謂詞向量u，獨(dú)熱向量的維度為云數(shù)據(jù)庫(kù)中列的數(shù)量。為了便于說(shuō)明Query-Encoding，給出了一個(gè)查詢語(yǔ)句例子，如圖2所示。查詢語(yǔ)句的連接謂詞為E.a=F.a，E.b=G.b，E.c=H.c，則鄰接矩陣中對(duì)應(yīng)位置元素的值為1，連接謂詞向量v為(0111 1000 1000 1000)。查詢語(yǔ)句的F.a列和H.c列涉及選擇謂詞，則選擇謂詞向量u中對(duì)應(yīng)位置的值為1，其余位置的值為0。

2.2 Plan-Encoding

Plan-Encoding將執(zhí)行計(jì)劃的物理運(yùn)算符和結(jié)構(gòu)特征進(jìn)行編碼。執(zhí)行計(jì)劃的物理運(yùn)算符包括掃描方式和連接方式。掃描方式使用獨(dú)熱向量進(jìn)行編碼，例如(10)表示執(zhí)行計(jì)劃中某個(gè)表使用Sequence-Scan，(01)表示執(zhí)行計(jì)劃中某個(gè)表使用Index-Scan。連接方式使用獨(dú)熱向量進(jìn)行編碼，例如(100)表示執(zhí)行計(jì)劃中某2個(gè)表使用Hash-Join生成中間結(jié)果集，(010)表示執(zhí)行計(jì)劃中某2個(gè)表使用Nest-Loop-Join生成中間結(jié)果集，(001)表示執(zhí)行計(jì)劃中某2個(gè)表使用Merge-Join生成中間結(jié)果集。

執(zhí)行計(jì)劃的結(jié)構(gòu)特征包括執(zhí)行計(jì)劃的節(jié)點(diǎn)類型、節(jié)點(diǎn)連接順序。執(zhí)行計(jì)劃的節(jié)點(diǎn)類型包括左表、右表和中間結(jié)果集。執(zhí)行計(jì)劃的節(jié)點(diǎn)類型使用獨(dú)熱向量進(jìn)行編碼，例如(10)表示執(zhí)行計(jì)劃的節(jié)點(diǎn)類型為左表，(01)表示執(zhí)行計(jì)劃的節(jié)點(diǎn)類型為右表，(11)表示執(zhí)行計(jì)劃的節(jié)點(diǎn)類型為中間結(jié)果集。執(zhí)行計(jì)劃的節(jié)點(diǎn)連接順序使用2位整數(shù)進(jìn)行編碼，例如(01)表示第1次選擇該節(jié)點(diǎn)進(jìn)行連接或者第1次生成該節(jié)點(diǎn)，(02)表示第2次選擇該節(jié)點(diǎn)進(jìn)行連接或者第2次生成該節(jié)點(diǎn)。

進(jìn)一步，Plan-Encoding將執(zhí)行計(jì)劃編碼為執(zhí)行計(jì)劃向量樹(shù)，執(zhí)行計(jì)劃向量樹(shù)中每一個(gè)節(jié)點(diǎn)向量均由該節(jié)點(diǎn)的物理運(yùn)算符編碼、節(jié)點(diǎn)類型編碼和節(jié)點(diǎn)連接順序編碼組成。需要注意的是，執(zhí)行計(jì)劃分為部分執(zhí)行計(jì)劃和完整執(zhí)行計(jì)劃，因此執(zhí)行計(jì)劃向量樹(shù)中的節(jié)點(diǎn)數(shù)量將動(dòng)態(tài)增長(zhǎng)。為了便于說(shuō)明Plan-Encoding，基于圖2的查詢語(yǔ)句給出了部分執(zhí)行計(jì)劃向量樹(shù)。Plan-Encoding示例如圖3所示，假設(shè)第1次選擇E表和F表使用Hash-Join生成中間結(jié)果集(EF)，并指定E表作為左表、E表掃描方式為Sequence-Scan，F(xiàn)表作為右表、F表掃描方式為Sequence-Scan。第2次選擇表E和表G進(jìn)行連接，也就是將中間結(jié)果集(EF)和表G使用Nest-Loop-Join生成中間結(jié)果集((EF)G)，并指定G表作為右表、G表掃描方式為Index-Scan。

圖3 Plan-Encoding示例Fig.3 Example of Plan-Encoding

3 ASA-Join的狀態(tài)表示模型

準(zhǔn)確的狀態(tài)表示能夠提升強(qiáng)化學(xué)習(xí)算法的性能。因此，ASA-Join設(shè)計(jì)了狀態(tài)表示模型對(duì)連接謂詞向量、選擇謂詞向量和執(zhí)行計(jì)劃向量樹(shù)進(jìn)行處理。對(duì)于連接謂詞向量和選擇謂詞向量，狀態(tài)表示模型使用全連接層進(jìn)行處理，生成靜態(tài)信息向量q，能夠克服連接謂詞向量和選擇謂詞向量的稀疏性。對(duì)于執(zhí)行計(jì)劃向量樹(shù)，狀態(tài)表示模型首先使用后序遍歷算法進(jìn)行序列化處理，生成執(zhí)行計(jì)劃向量集。為了便于說(shuō)明狀態(tài)表示模型使用后序遍歷算法對(duì)執(zhí)行計(jì)劃向量樹(shù)進(jìn)行序列化處理的過(guò)程，基于圖3中的部分執(zhí)行計(jì)劃向量樹(shù)給出了一個(gè)例子。如圖4所示，依次訪問(wèn)部分執(zhí)行計(jì)劃向量樹(shù)各個(gè)節(jié)點(diǎn)向量，并按訪問(wèn)順序?qū)⒐?jié)點(diǎn)向量存入執(zhí)行計(jì)劃向量集。

圖4 基于后序遍歷算法處理執(zhí)行計(jì)劃向量樹(shù)Fig.4 Processing execution plan vector tree based on post-order traversal algorithm

狀態(tài)表示模型使用BiGRU模型對(duì)執(zhí)行計(jì)劃向量集進(jìn)行處理，能夠捕捉執(zhí)行計(jì)劃的結(jié)構(gòu)特征，并生成動(dòng)態(tài)信息向量p。不同結(jié)構(gòu)特征的執(zhí)行計(jì)劃向量樹(shù)可以轉(zhuǎn)換為執(zhí)行計(jì)劃向量集。換言之，捕捉執(zhí)行計(jì)劃的結(jié)構(gòu)特征可以轉(zhuǎn)換為捕捉有序節(jié)點(diǎn)的上下文信息。BiGRU適合處理序列數(shù)據(jù)，即使是相當(dāng)長(zhǎng)的序列數(shù)據(jù) (如在自然語(yǔ)言處理中)。因此，對(duì)于執(zhí)行計(jì)劃向量樹(shù)，BiGRU能夠自動(dòng)學(xué)習(xí)執(zhí)行計(jì)劃的結(jié)構(gòu)特征，進(jìn)而給出執(zhí)行計(jì)劃的準(zhǔn)確表示。對(duì)于執(zhí)行計(jì)劃向量集，BiGRU依次處理執(zhí)行計(jì)劃向量集中每個(gè)節(jié)點(diǎn)向量，進(jìn)而捕捉執(zhí)行計(jì)劃中節(jié)點(diǎn)之間的上下文信息。當(dāng) BiGRU 處理當(dāng)前節(jié)點(diǎn)向量時(shí)，BiGRU 可以同時(shí)記住前一個(gè)節(jié)點(diǎn)以及后一個(gè)節(jié)點(diǎn)的關(guān)鍵信息，例如結(jié)構(gòu)特征。即使 BiGRU 處理最后一個(gè)節(jié)點(diǎn)向量，仍然可以記住第1個(gè)節(jié)點(diǎn)向量包含的結(jié)構(gòu)信息，進(jìn)而捕捉整個(gè)執(zhí)行計(jì)劃向量樹(shù)的結(jié)構(gòu)特征。狀態(tài)表示模型將靜態(tài)信息向量q和動(dòng)態(tài)信息向量p進(jìn)行級(jí)聯(lián)，最終生成執(zhí)行計(jì)劃狀態(tài)向量s。基于圖4中的例子，狀態(tài)表示模型的工作原理如圖5所示。

圖5 狀態(tài)表示模型的工作機(jī)制Fig.5 Working mechanism of the state representation model

4 ASA-Join的異步Soft Actor-Critic

現(xiàn)有強(qiáng)化學(xué)習(xí)算法通常存在3類問(wèn)題：

① 探索能力、健壯性較差；

② 依賴于精確的超參數(shù)設(shè)置；

③ 訓(xùn)練速度較慢、收斂不穩(wěn)定。

為了ASA-Join更好地指導(dǎo)連接順序選擇，提出了異步Soft Actor-Critic算法。異步Soft Actor-Critic算法利用最大熵機(jī)制能夠增加策略的隨機(jī)性，并鼓勵(lì)智能體選擇從未嘗試的動(dòng)作，進(jìn)而更全面地評(píng)估各個(gè)動(dòng)作的價(jià)值。最大熵機(jī)制能夠增加智能體的探索能力并提高算法的健壯性。此外，利用多線程通信機(jī)制實(shí)現(xiàn)異步更新，能夠加快訓(xùn)練速度，并且使用基于當(dāng)前策略的數(shù)據(jù)樣本計(jì)算參數(shù)梯度，能夠提高訓(xùn)練效果和收斂穩(wěn)定性。異步Soft Actor-Critic算法步驟如算法1所示。

算法1：異步Soft Actor-Critic算法

輸入：Actor網(wǎng)絡(luò)的初始參數(shù)WA，Value-Critic網(wǎng)絡(luò)的初始參數(shù)WV，Q-Critic網(wǎng)絡(luò)的初始參數(shù)WQ

1. CreateThreads();

2. Allocation();

3. SelectGlobalModel();

6. SetT=0,T最大值為Tmax;

7. Sett=1,t的最大間隔值為tmax;

8. WHILE (T

11. Resettstart=t;

12.st=GetState();

13.FOReach episodeDO

14. 計(jì)算模型中Actor網(wǎng)絡(luò)根據(jù)st選擇動(dòng)作at;

15.st+1=ChangeState(st,at);

16. IF (st表示完整執(zhí)行計(jì)劃狀態(tài)){

17.r(st,at)=costorlatency;

18. }

19.ELSE{

21. }

25.t=t+1,T=T+1;

26.IF(t-tstart=tmax){

29.ENDFOR

異步Soft Actor-Critic算法主要包含如下操作：

⑤ 算法第25～28行分別更新線程計(jì)數(shù)器和全局計(jì)數(shù)器的計(jì)數(shù)值t,T。如果間隔計(jì)數(shù)值等于tmax, 將計(jì)算模型中的參數(shù)梯度傳遞到全局模型中來(lái)更新全局模型的參數(shù)。

5 ASA-Join的實(shí)驗(yàn)評(píng)估

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

實(shí)驗(yàn)數(shù)據(jù)集為JOB和TPC-H數(shù)據(jù)集。JOB數(shù)據(jù)集是基于電影數(shù)據(jù)集IMDB的查詢語(yǔ)句集合，包括33個(gè)查詢模板和113個(gè)復(fù)雜的多表連接查詢語(yǔ)句，其中多表連接查詢語(yǔ)句平均包含9個(gè)連接謂詞，最多包含17個(gè)連接謂詞。所有的查詢語(yǔ)句真實(shí)地反映了電影愛(ài)好者的問(wèn)題。電影數(shù)據(jù)集IMDB包含3.6 GB非均勻分布數(shù)據(jù)和21個(gè)表，其中表cast_info和movie_info分別包含3 000萬(wàn)行記錄和1 500萬(wàn)行記錄。TPC-H數(shù)據(jù)集是基于供貨業(yè)務(wù)數(shù)據(jù)集的查詢語(yǔ)句集合，包括22個(gè)查詢語(yǔ)句。供貨業(yè)務(wù)數(shù)據(jù)集由DBGen工具模擬生成，包含4.0 GB數(shù)據(jù)和8個(gè)表。

實(shí)驗(yàn)硬件環(huán)境為具有12核24線程的CPU、NVIDIA 3090GTX顯卡、64 GB內(nèi)存和2 TB硬盤的戴爾服務(wù)器。實(shí)驗(yàn)軟件環(huán)境為OpenAI-gym強(qiáng)化學(xué)習(xí)交互環(huán)境庫(kù)、RLlib強(qiáng)化學(xué)習(xí)算法庫(kù)、Tensorflow2.0。

實(shí)驗(yàn)所用云數(shù)據(jù)庫(kù)為華為云數(shù)據(jù)庫(kù)Relational Database Service(RDS) for PostgreSQL、阿里云數(shù)據(jù)庫(kù)RDS for PostgreSQL和云數(shù)據(jù)庫(kù)GuassDB[22]。RDS for PostgreSQL，RDS for PostgreSQL和GuassDB的代價(jià)估計(jì)器和執(zhí)行器為執(zhí)行計(jì)劃提供代價(jià)和延遲。

5.2 實(shí)驗(yàn)評(píng)估指標(biāo)

為了便于直觀地比較ASA-Join與現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器的性能差異，使用相對(duì)代價(jià) (Relative Cost，RC)和相對(duì)延遲 (Relative Latency，RL)作為評(píng)估指標(biāo)。RC計(jì)算如下：

(2)

式中，cost(qi)表示ASA-Join或現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器為第i條查詢語(yǔ)句生成相應(yīng)執(zhí)行計(jì)劃的代價(jià)；n為JOB數(shù)據(jù)集或TPC-H數(shù)據(jù)集中查詢語(yǔ)句的數(shù)量；costdp(qi)表示動(dòng)態(tài)規(guī)劃方法為第i條查詢語(yǔ)句生成相應(yīng)執(zhí)行計(jì)劃的代價(jià)。RL計(jì)算如下：

(3)

式中，latency(qi)表示ASA-Join或現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器為第i條查詢語(yǔ)句生成相應(yīng)執(zhí)行計(jì)劃的延遲；latencydp(qi)表示動(dòng)態(tài)規(guī)劃方法為第i條查詢語(yǔ)句生成相應(yīng)執(zhí)行計(jì)劃的延遲。

5.3 ASA-Join的相對(duì)代價(jià)評(píng)估

基于不同云數(shù)據(jù)庫(kù)的JOB數(shù)據(jù)集的代價(jià)評(píng)估如圖6所示。

圖6 基于不同云數(shù)據(jù)庫(kù)的JOB數(shù)據(jù)集的代價(jià)評(píng)估Fig.6 Cost evaluation of JOB datasets based on different cloud databases

基于RDS for PostgreSQL構(gòu)建ASA-Join和現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器如圖6(a)所示。在JOB數(shù)據(jù)集上，ASA-Join的相對(duì)代價(jià)低于現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器如Rejoin，DQ，Neo和AlphaJoin，這表明ASA-Join能夠生成以代價(jià)為優(yōu)化目標(biāo)的最優(yōu)執(zhí)行計(jì)劃。主要原因在于，相比Rejoin和DQ，ASA-Join能夠捕捉執(zhí)行計(jì)劃的結(jié)構(gòu)特征并提供執(zhí)行計(jì)劃的準(zhǔn)確表示，進(jìn)而可以提高后續(xù)異步Soft Actor-Critic算法的性能；相比Neo和AlphaJoin，ASA-Join的異步Soft Actor-Critic算法能夠增加策略的隨機(jī)性以及提高智能體的探索能力，避免陷入局部最優(yōu)解，盡可能生成最優(yōu)執(zhí)行計(jì)劃?，F(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器的相對(duì)代價(jià)均低于傳統(tǒng)優(yōu)化方法QP(QuickPick-1000)，這表明利用強(qiáng)化學(xué)習(xí)能夠更好地指導(dǎo)連接順序選擇，進(jìn)而生成更低代價(jià)的執(zhí)行計(jì)劃。如圖6(a)和(b)所示，分別基于RDS for PostgreSQL，GuassDB構(gòu)建ASA-Join和現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器。在JOB數(shù)據(jù)集上，ASA-Join的相對(duì)代價(jià)低于現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器。其中，AlphaJoin的相對(duì)代價(jià)最接近ASA-Join，傳統(tǒng)優(yōu)化QP的相對(duì)代價(jià)最大。

基于不同云數(shù)據(jù)庫(kù)的TPC-H數(shù)據(jù)集的代價(jià)評(píng)估如圖7所示， 在不同云數(shù)據(jù)庫(kù)的TPC-H數(shù)據(jù)集上，ASA-Join均能夠生成更好的執(zhí)行計(jì)劃(以代價(jià)為優(yōu)化目標(biāo))，這表明ASA-Join能夠適應(yīng)不同的云數(shù)據(jù)庫(kù)，并不依賴于特定云數(shù)據(jù)庫(kù)，具有較高的通用性。在代價(jià)評(píng)估方面，ASA-Join始終優(yōu)于現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器和傳統(tǒng)的優(yōu)化方法。

圖7 基于不同云數(shù)據(jù)庫(kù)的TPC-H數(shù)據(jù)集的代價(jià)評(píng)估Fig.7 Cost evaluation of TPC-H datasets based on different cloud databases

5.4 ASA-Join的相對(duì)延遲評(píng)估

基于不同云數(shù)據(jù)庫(kù)的JOB數(shù)據(jù)集的延遲評(píng)估如圖8所示。

圖8 基于不同云數(shù)據(jù)庫(kù)的JOB數(shù)據(jù)集的延遲評(píng)估Fig.8 Latency evaluation of JOB datasets based on different cloud databases

可以看出，在不同云數(shù)據(jù)庫(kù)的JOB數(shù)據(jù)集上，ASA-Join的相對(duì)延遲均最低，并且ASA-Join的相對(duì)延遲分別為0.60(基于RDS for PostgreSQL)，0.61(基于GuassDB)和0.63(基于RDS for PostgreSQL)。在延遲評(píng)估方面，ASA-Join優(yōu)于現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器和傳統(tǒng)的優(yōu)化方法。主要原因在于，ASA-Join的獎(jiǎng)勵(lì)機(jī)制基于多任務(wù)學(xué)習(xí)思想，將延遲和代價(jià)均作為優(yōu)化目標(biāo)。換言之，ASA-Join既可以學(xué)習(xí)以代價(jià)作為獎(jiǎng)勵(lì)的策略，也可以學(xué)習(xí)以延遲為獎(jiǎng)勵(lì)的策略，能夠克服錯(cuò)誤的代價(jià)估計(jì)和基數(shù)估計(jì)，使得生成的執(zhí)行計(jì)劃反映真實(shí)查詢時(shí)間。此外，ASA-Join的異步Soft Actor-Critic算法能夠加快訓(xùn)練速度、提高收斂穩(wěn)定性，進(jìn)而提高ASA-Join的訓(xùn)練效果。在RDS for PostgreSQL上，ASA-Join的相對(duì)延遲分別比Rejoin(相對(duì)延遲為1.20)低50.0%，比DQ(相對(duì)延遲為1.15)低47.8%，比Neo(相對(duì)延遲為0.80)低25.0%，比AlphaJoin(相對(duì)延遲為0.72)低16.7%。在GuassDB上，ASA-Join的相對(duì)延遲分別比Rejoin(相對(duì)延遲為1.12)低45.5%，比DQ(相對(duì)延遲為1.17)低48.7%，比Neo(相對(duì)延遲為0.78)低21.8%，比AlphaJoin(相對(duì)延遲為0.70)低12.9%。在RDS for PostgreSQL上，ASA-Join的相對(duì)延遲分別比Rejoin(相對(duì)延遲為1.18)低46.6%，比DQ(相對(duì)延遲為1.19)低47.1%，比Neo(相對(duì)延遲為0.82)低23.2%，比AlphaJoin(相對(duì)延遲為0.74)低14.9%。在JOB數(shù)據(jù)集上，ASA-Join的相對(duì)延遲與其他優(yōu)化方法的差距較大，主要原因是JOB數(shù)據(jù)集中的查詢語(yǔ)句均為復(fù)雜的多表連接查詢，平均包含9個(gè)以上的連接謂詞，使得候選執(zhí)行計(jì)劃的結(jié)構(gòu)復(fù)雜多變。ASA-Join的編碼方法能夠準(zhǔn)確表示執(zhí)行計(jì)劃，并且利用BiGRU模型能夠捕捉執(zhí)行計(jì)劃的結(jié)構(gòu)特征，為異步Soft Actor-Critic提供準(zhǔn)確的狀態(tài)表示，進(jìn)而使異步Soft Actor-Critic能夠更好地指導(dǎo)多表連接順序選擇，ASA-Join生成更好的執(zhí)行計(jì)劃(以延遲為優(yōu)化目標(biāo))。

基于不同云數(shù)據(jù)庫(kù)的TPC-H數(shù)據(jù)集的延遲評(píng)估如圖9所示?？梢钥闯觯诓煌茢?shù)據(jù)庫(kù)的TPC-H數(shù)據(jù)集上，ASA-Join的相對(duì)延遲也低于現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器和傳統(tǒng)的優(yōu)化方法。在TPC-H數(shù)據(jù)集上，ASA-Join的相對(duì)延遲與其他優(yōu)化方法的差距并不是很大，主要原因是TPC-H數(shù)據(jù)集中查詢語(yǔ)句包含的連接謂詞的數(shù)量較少，現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器均能夠較好地指導(dǎo)連接順序選擇，而ASA-Join更擅長(zhǎng)處理復(fù)雜的多表連接查詢。

圖9 基于不同云數(shù)據(jù)庫(kù)的TPC-H數(shù)據(jù)集的延遲評(píng)估Fig.9 Latency evaluation of TPC-H datasets based on different cloud databases

6 結(jié)束語(yǔ)

本文針對(duì)云數(shù)據(jù)庫(kù)的啟發(fā)式查詢優(yōu)化方法和現(xiàn)有基于強(qiáng)化學(xué)習(xí)的優(yōu)化器存在的缺陷，提出了新型基于異步Soft Actor-Critic的連接查詢優(yōu)化器。首先，ASA-Join集成了新的編碼方法，包括Query-Encoding和Plan-Encoding，能夠準(zhǔn)確表示執(zhí)行計(jì)劃。其次，ASA-Join設(shè)計(jì)了狀態(tài)表示模型來(lái)捕捉執(zhí)行計(jì)劃的結(jié)構(gòu)特征，進(jìn)而提供準(zhǔn)確的狀態(tài)表示，使得異步Soft Actor-Critic能更好地指導(dǎo)連接順序選擇。再者，ASA-Join利用多線程通信機(jī)制設(shè)計(jì)了異步Soft Actor-Critic算法。異步Soft Actor-Critic利用最大熵機(jī)制增加智能體的探索能力，使得智能體能夠探索更多從未嘗試的動(dòng)作，并且多線程通信機(jī)制能夠?qū)崿F(xiàn)異步更新，進(jìn)而加快訓(xùn)練速度以及提高收斂穩(wěn)定性。此外，ASA-Join將執(zhí)行計(jì)劃的代價(jià)和延遲均作為獎(jiǎng)勵(lì)目標(biāo)，使得生成的執(zhí)行計(jì)劃能夠反映真實(shí)的查詢時(shí)間。

未來(lái)的工作將著重探究云數(shù)據(jù)庫(kù)模式的頻繁改變對(duì)基于強(qiáng)化學(xué)習(xí)的優(yōu)化器的影響，并基于ASA-Join進(jìn)一步研究新的優(yōu)化器如何適應(yīng)工作負(fù)載的變化。