基于多線程通信機制的云數據庫查詢優化方法

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

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

0 引言

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

云數據庫的查詢優化方法為啟發式算法[5]，往往基于專家經驗，但是仍然存在局限性[6]。例如，動態規劃算法需要巨大的搜索空間，花費較長的優化時間。QuickPick-1000[7]的優化時間較短，但是容易生成糟糕的連接順序執行計劃，使得查詢性能下降，并且傳統的查詢優化方法無法從歷史查詢中學習經驗。例如，對于相同的多表連接查詢會重復生成糟糕的執行計劃，進而產生較高的延遲[8]。

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

① Rejoin和DQ等現有優化器的編碼方法不包括物理運算符和執行計劃的結構特征，進而無法準確地表示執行計劃。物理運算符是指執行計劃中單表的掃描方式和多表之間的連接方式。

② Rejoin和DQ等現有優化器并沒有設計狀態表示模型，無法捕捉執行計劃的結構特征，進而無法為后續強化學習算法提供準確的狀態表示。

③ Rejoin和DQ等現有優化器使用數據庫代價估計器為執行計劃估計代價，并將代價作為獎勵目標。對于復雜的多表連接查詢，并不能準確估計中間結果集的代價，容易出現錯誤的代價估計[12]，進而生成次優的執行計劃。

④ Neo[13]和AlphaJoin[14]等現有優化器使用價值網絡為執行計劃預測延遲，并將延遲作為優化目標。雖然能夠避免錯誤的代價估計導致生成次優的執行計劃，但是Neo和AlphaJoin的價值網絡的預測準確性較低，并且需要高質量的歷史查詢樣本進行訓練[15]。

⑤ Neo等現有優化器使用簡單的搜索策略指導連接順序選擇，并沒有嘗試在更大的搜索空間中進行探索，可能會降低找到最優執行計劃的概率，容易陷入局部最優解。

⑥ Rejoin和DQ等現有優化器的強化學習算法的探索性較差，容易受到超參數的影響，并且訓練速度較慢、收斂不穩定[16-18]。

針對上述問題，提出了一種新型基于異步Soft Actor-Critic的連接查詢優化器(Asynchronous Soft Actor-Critic for Join Query，ASA-Join)。ASA-Join集成了一種新的編碼方法，將物理運算符和執行計劃的結構特征進行編碼，能夠準確地表示執行計劃。ASA-Join設計了狀態表示模型，利用BiGRU[19]模型來捕捉執行計劃的結構特征，進而能夠為異步Soft Actor-Critic提供準確的狀態表示。ASA-Join設計了新的獎勵機制，利用多任務學習方法[20]將執行計劃的延遲和代價均作為優化目標，進而使得執行計劃能夠反映真實的查詢時間。ASA-Join利用多線程通信機制設計了異步Soft Actor-Critic算法。異步Soft Actor-Critic算法指導連接順序選擇，利用最大熵機制能夠增加動作選擇的隨機性，進而提高智能體的探索能力，盡可能從全局上搜索最優執行計劃。異步Soft Actor-Critic算法不依賴于精確的超參數調整，并且多線程通信機制能夠實現異步更新，進而加快訓練速度并提高收斂穩定性。在真實數據集Join Order Benchmark (JOB)[21]和TPC-H上對ASA-Join的性能進行評估。實驗結果表明，ASA-Join的代價和延遲均低于現有基于強化學習的優化方法。

1 ASA-Join的整體架構

ASA-Join的整體架構如圖1所示。

圖1 ASA-Join的整體架構Fig.1 The overall framework of ASA-Join

ASA-Join主要由3個關鍵部分構成：編碼方法、狀態表示模型以及異步Soft Actor-Critic算法。

① 編碼方法主要由查詢語句編碼Query-Encoding和執行計劃編碼Plan-Encoding組成。Query-Encoding主要對查詢語句的連接謂詞和選擇謂詞進行編碼，Plan-Encoding主要對執行計劃的結構特征和物理運算符進行編碼，進而生成執行計劃向量樹。

② 狀態表示模型主要對執行計劃向量樹進行序列化處理，生成執行計劃向量集，并將執行計劃向量集作為BiGRU模型的輸入，進而BiGRU模型能夠捕捉執行計劃的結構特征，為異步Soft Actor-Critic提供準確的狀態表示。

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

進一步地，完整執行計劃將被發送給云數據庫，云數據庫的代價估計器和執行器分別為完整執行計劃給出代價和延遲，并利用多任務學習方法將執行計劃的代價和延遲均作為獎勵目標。需要注意的是，收集執行計劃的代價不需要運行執行計劃，因此將執行計劃的代價作為第1階段的獎勵目標，使得ASA-Join能夠快速理解以代價作為獎勵目標的云數據庫優化方式。執行計劃的延遲是云數據庫運行執行計劃的時間，難以短時間內獲取，因此將執行計劃的延遲作為第2階段的獎勵目標。在第1階段訓練后，ASA-Join能夠生成較優的執行計劃，再使用執行計劃的延遲作為獎勵目標進行微調，使得ASA-Join最終生成的執行計劃能夠反映真實的執行時間，并避免錯誤的代價估計導致生成次優的執行計劃。

此外，在ASA-Join的訓練過程中，利用多線程通信機制來異步更新Soft Actor-Critic的參數。在每個線程中均包含具有相同結構和相同參數的Soft Actor-Critic。選擇任意一個線程中的Soft Actor-Critic作為全局模型，其余線程中的Soft Actor-Critic作為計算模型。計算模型主要與云數據庫進行交互，獲取數據樣本(狀態、動作和獎勵等信息)來計算Soft Actor-Critic中各個網絡的參數梯度，但并不用于更新計算模型，而是用于更新全局模型的參數。

2 ASA-Join的編碼方法

2.1 Query-Encoding

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

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

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

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

(1)

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

2.2 Plan-Encoding

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

執行計劃的結構特征包括執行計劃的節點類型、節點連接順序。執行計劃的節點類型包括左表、右表和中間結果集。執行計劃的節點類型使用獨熱向量進行編碼，例如(10)表示執行計劃的節點類型為左表，(01)表示執行計劃的節點類型為右表，(11)表示執行計劃的節點類型為中間結果集。執行計劃的節點連接順序使用2位整數進行編碼，例如(01)表示第1次選擇該節點進行連接或者第1次生成該節點，(02)表示第2次選擇該節點進行連接或者第2次生成該節點。

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

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

3 ASA-Join的狀態表示模型

準確的狀態表示能夠提升強化學習算法的性能。因此，ASA-Join設計了狀態表示模型對連接謂詞向量、選擇謂詞向量和執行計劃向量樹進行處理。對于連接謂詞向量和選擇謂詞向量，狀態表示模型使用全連接層進行處理，生成靜態信息向量q，能夠克服連接謂詞向量和選擇謂詞向量的稀疏性。對于執行計劃向量樹，狀態表示模型首先使用后序遍歷算法進行序列化處理，生成執行計劃向量集。為了便于說明狀態表示模型使用后序遍歷算法對執行計劃向量樹進行序列化處理的過程，基于圖3中的部分執行計劃向量樹給出了一個例子。如圖4所示，依次訪問部分執行計劃向量樹各個節點向量，并按訪問順序將節點向量存入執行計劃向量集。

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

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

圖5 狀態表示模型的工作機制Fig.5 Working mechanism of the state representation model

4 ASA-Join的異步Soft Actor-Critic

現有強化學習算法通常存在3類問題：

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

② 依賴于精確的超參數設置；

③ 訓練速度較慢、收斂不穩定。

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

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

輸入：Actor網絡的初始參數WA，Value-Critic網絡的初始參數WV，Q-Critic網絡的初始參數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. 計算模型中Actor網絡根據st選擇動作at;

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

16. IF (st表示完整執行計劃狀態){

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行分別更新線程計數器和全局計數器的計數值t,T。如果間隔計數值等于tmax, 將計算模型中的參數梯度傳遞到全局模型中來更新全局模型的參數。

5 ASA-Join的實驗評估

5.1 實驗設置

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

實驗硬件環境為具有12核24線程的CPU、NVIDIA 3090GTX顯卡、64 GB內存和2 TB硬盤的戴爾服務器。實驗軟件環境為OpenAI-gym強化學習交互環境庫、RLlib強化學習算法庫、Tensorflow2.0。

實驗所用云數據庫為華為云數據庫Relational Database Service(RDS) for PostgreSQL、阿里云數據庫RDS for PostgreSQL和云數據庫GuassDB[22]。RDS for PostgreSQL，RDS for PostgreSQL和GuassDB的代價估計器和執行器為執行計劃提供代價和延遲。

5.2 實驗評估指標

為了便于直觀地比較ASA-Join與現有基于強化學習的優化器的性能差異，使用相對代價 (Relative Cost，RC)和相對延遲 (Relative Latency，RL)作為評估指標。RC計算如下：

(2)

式中，cost(qi)表示ASA-Join或現有基于強化學習的優化器為第i條查詢語句生成相應執行計劃的代價；n為JOB數據集或TPC-H數據集中查詢語句的數量；costdp(qi)表示動態規劃方法為第i條查詢語句生成相應執行計劃的代價。RL計算如下：

(3)

式中，latency(qi)表示ASA-Join或現有基于強化學習的優化器為第i條查詢語句生成相應執行計劃的延遲；latencydp(qi)表示動態規劃方法為第i條查詢語句生成相應執行計劃的延遲。

5.3 ASA-Join的相對代價評估

基于不同云數據庫的JOB數據集的代價評估如圖6所示。

圖6 基于不同云數據庫的JOB數據集的代價評估Fig.6 Cost evaluation of JOB datasets based on different cloud databases

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

基于不同云數據庫的TPC-H數據集的代價評估如圖7所示， 在不同云數據庫的TPC-H數據集上，ASA-Join均能夠生成更好的執行計劃(以代價為優化目標)，這表明ASA-Join能夠適應不同的云數據庫，并不依賴于特定云數據庫，具有較高的通用性。在代價評估方面，ASA-Join始終優于現有基于強化學習的優化器和傳統的優化方法。

圖7 基于不同云數據庫的TPC-H數據集的代價評估Fig.7 Cost evaluation of TPC-H datasets based on different cloud databases

5.4 ASA-Join的相對延遲評估

基于不同云數據庫的JOB數據集的延遲評估如圖8所示。

圖8 基于不同云數據庫的JOB數據集的延遲評估Fig.8 Latency evaluation of JOB datasets based on different cloud databases

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

基于不同云數據庫的TPC-H數據集的延遲評估如圖9所示。可以看出，在不同云數據庫的TPC-H數據集上，ASA-Join的相對延遲也低于現有基于強化學習的優化器和傳統的優化方法。在TPC-H數據集上，ASA-Join的相對延遲與其他優化方法的差距并不是很大，主要原因是TPC-H數據集中查詢語句包含的連接謂詞的數量較少，現有基于強化學習的優化器均能夠較好地指導連接順序選擇，而ASA-Join更擅長處理復雜的多表連接查詢。

圖9 基于不同云數據庫的TPC-H數據集的延遲評估Fig.9 Latency evaluation of TPC-H datasets based on different cloud databases

6 結束語

本文針對云數據庫的啟發式查詢優化方法和現有基于強化學習的優化器存在的缺陷，提出了新型基于異步Soft Actor-Critic的連接查詢優化器。首先，ASA-Join集成了新的編碼方法，包括Query-Encoding和Plan-Encoding，能夠準確表示執行計劃。其次，ASA-Join設計了狀態表示模型來捕捉執行計劃的結構特征，進而提供準確的狀態表示，使得異步Soft Actor-Critic能更好地指導連接順序選擇。再者，ASA-Join利用多線程通信機制設計了異步Soft Actor-Critic算法。異步Soft Actor-Critic利用最大熵機制增加智能體的探索能力，使得智能體能夠探索更多從未嘗試的動作，并且多線程通信機制能夠實現異步更新，進而加快訓練速度以及提高收斂穩定性。此外，ASA-Join將執行計劃的代價和延遲均作為獎勵目標，使得生成的執行計劃能夠反映真實的查詢時間。

未來的工作將著重探究云數據庫模式的頻繁改變對基于強化學習的優化器的影響，并基于ASA-Join進一步研究新的優化器如何適應工作負載的變化。