用于多表連接優化的深度強化學習嵌入表示

王江晴，王雪言，孫 翀+，帖 軍，尹 帆

(1.中南民族大學 計算機科學學院，湖北 武漢 430074；2.中南民族大學 湖北省制造企業智能管理工程技術研究中心，湖北 武漢 430074；3.中南民族大學農業區塊鏈與智能管理湖北省工程研究中心，湖北 武漢 430074)

0 引 言

多表連接優化是查詢優化的重要研究問題之一[1]，其任務是在各種可能的候選序列找到一種最佳的連接順序，使得執行計劃的代價最小[2]。不同的連接順序會生成不同大小的中間結果[3]，因此對應消耗的資源也不同(CPU和I/O的消耗)。傳統方法使用動態規劃算法和貪心策略來解決多表連接優化問題，這些方法不能從之前的經驗中學習，會重復選擇不好的執行計劃，導致查詢的效率低下。目前，數據庫領域出現強化學習相關技術的應用[4-6]，將多表連接優化建模為強化學習問題[7]，使用數據庫中的參與查詢的關系表示狀態，關系之間的連接視為動作，最終的執行耗時作為獎勵，模型的總目標是生成一個低延遲的執行計劃。而查詢語句的嵌入表示方法是影響使用強化學習生成連接順序結果的關鍵，因此找到一種能捕獲更多關于連接信息的嵌入表示方法至關重要。

針對上述問題，本文提出一種嵌入表示方法Smart-Encoder，能捕獲到查詢語句的選擇謂詞和連接謂詞信息、連接樹的左右關系及樹的高度信息，并使用基于策略的強化學習算法[8]來解決多表連接優化的問題，將模型集成到PostgreSQL查詢優化器中并同時從代價和延遲中學習，稱本文的模型為SmartJOIN。在數據集(join order benchmark，JOB)上的實驗結果表明，本文提出的嵌入表示方法SmartEncoder進行連接優化不僅可以減少生成執行計劃的時間，還可以提高生成的查詢計劃的質量，從而提高數據庫系統的查詢性能。

1 相關工作

多表連接優化作為查詢優化中一個非常重要的問題，隨著關系數量的線性增長，要枚舉的連接序列會呈現出指數級增長[9]，多表連接優化是NP-Hard的問題。現實應用中通常利用啟發式方法來解決，當代價模型是線性的，關系的連接和連接產生的代價成線性關系，這種方式是可接受的，然而實際情況中連接的代價具有非線性特征[10]。例如，連接的中間結果超過可用內存可能會觸發分區。在這種情況下，啟發式的方法可能會呈現出次優的效果，就難以起到良好的作用。采用基于學習的方法而不是啟發式方法來進行連接順序選擇優化，可以從過去的經驗中學習，充分利用之前的連接策略進行多表連接優化[11]。

近年來，基于學習的多表連接優化方法被提出，利用深度強化學習的技術來解決連接優化的問題。Ryan等[12]提出基于策略的深度強化學習算法的連接優化器ReJoin，將連接優化問題抽象成強化學習問題，ReJoin將選擇信息和連接信息向量化，將連接樹的高度信息向量化為每個表所處連接樹的深度的平方分之一來表示，輸入當前狀態的向量化信息，輸出對應狀態的連接動作的概率分布，然后選擇相應的連接動作，但是這種向量化方法無法區分連接的左右關系，導致不同的連接順序在編碼后產生相同的向量。Krishnan等提出基于Deep Q-Learning算法[13]的優化器DQ，將多表連接優化問題建模為馬爾可夫決策過程，每個狀態都是一個查詢圖，兩個關系之間的連接視為動作，對已經連接到一起的關系和待連接的關系進行編碼，并將多表連接的物理操作符用獨熱向量表示。用兩層深度神經網絡近似Q函數，輸入連接的狀態，輸出連接動作的Q值，選擇Q值最小的連接動作，但是DQ使用簡單的獨熱向量進行連接的狀態表示，導致不能獲得查詢樹的層次結構信息，且不同的連接順序的連接樹編碼后產生同樣的向量化信息。

對查詢語句編碼得到的不同嵌入表示方法會影響基于學習的多表連接優化方法的準確性[14]，針對上述連接優化方法中編碼方式存在的問題，本文提出一種改進的關于查詢語句的嵌入表示方法SmartEncoder，能包含更多關于連接的信息，對查詢語句的連接條件和選擇信息進行編碼，并采用改進的連接樹結構，能區分連接的左右關系并得到連接樹的層次結構，使得編碼和相應的連接順序之間有一致的一對一匹配關系，從而實現編碼可計算。本文提出的嵌入表示方法能夠得到更多關于查詢語句的信息，使用深度強化學習來優化多表連接順序選擇，提高了網絡的學習能力，進而提高查詢的性能。

2 SmartJoin模型

在基于深度強化學習的多表連接優化方法中，將當前的子樹作為狀態，動作是連接兩個子樹的操作，對查詢語句的連接方案和選擇條件以及連接樹的信息進行編碼，得到關于查詢語句的嵌入表示信息，作為神經網絡的輸入，可以由深度強化學習算法學習，每次操作將兩個關系進行連接，當所有的關系被連接完成時，代表一個回合結束，模型會在多個回合中進行學習。

2.1 模型流程

多表連接優化的目標是找到一個每個狀態下采取動作所構成的序列，使得累計代價最小。當前狀態向量化以后作為輸入被送入狀態層，通過若干個隱藏層進行轉換，每層通過激活函數轉換其輸入數據，將輸出結果送至后續層，數據最終被傳遞到動作層。動作層的每個神經元代表一個潛在的行動，它們的輸出被歸一化后形成一個概率分布，策略πθ(St,At) 通過從這個概率分布中取樣來選擇動作。基于深度強化學習的多表連接優化方法SmartJOIN的整體框架如圖1所示。

圖1 SmartJOIN框架

本文使用基于策略梯度的強化學習方法——近端策略優化算法[8]來進行連接順序決策，智能體根據一個參數化的策略πθ來選擇最佳操作，其中θ代表一個代表策略參數，在近端策略優化算法中，用參數化神經網絡表示策略πθ， 其中θ為網絡的權重，策略依據環境的反饋來調整θ， 從而優化策略參數θ， 使得預期的獎勵Rπ(θ) 最優。給定一個狀態和一個動作的集合At， 策略πθ會為At中的每個動作輸出一個概率(即連接兩個表的概率)，然后根據概率選擇動作，最終的連接順序結果發送到優化器進行后續操作和執行。

由于基數估計的不準確性會導致代價模型的估計不準確[15]，但獲取每條查詢語句的執行延遲是十分困難的。因此，在本文的方法中首先使用代價模型的估計作為獎勵來學習，這個階段完成后，模型可以生成一個以代價為指標的連接計劃。然后切換到基于真實延遲的數據中進行訓練，對模型進行微調。從而實現從代價和延遲中進行學習。

2.2 嵌入表示方法SmartEncoder

將查詢語句進行編碼后得到嵌入表示信息，即對模型有用的向量，向量包含的特征應該足夠豐富，可以獲得更多關于查詢的相關信息，這就需要得到此條查詢語句所請求的內容，連接左側的關系、連接右側的關系和過濾條件以及關于連接樹的信息。

查詢編碼：對查詢信息進行編碼，即對查詢語句中關系和屬性進行編碼。與之前的工作類似[16]，它包含了查詢語句中連接操作和選擇條件的信息兩部分，一部分連接操作用鄰接矩陣表示，矩陣中的“1”對應兩個表之間存在連接關系，矩陣的大小為數據庫中表的個數。如圖2(a)(連接謂詞)示例中，第一行第二列對應位置“1”表示A和B兩表之間存在連接操作；第二行第四列對應的位置為“0”，表示B和D兩表之間沒有進行連接。由于這個矩陣是對稱的，因此本文取上三角部分進行編碼；另一部分選擇操作用一維向量表示，用來標識查詢語句中用于過濾元組的屬性，向量的大小是數據庫表中所有的屬性個數。例如，在圖2(b)(選擇謂詞)中，數據庫中所有屬性的集合為 (A.id，A.a1，A.a2，…，B.id，B.a1，B.a2，…)， 其中屬性B.a2作為查詢語句的選擇謂詞，在對應向量的位置記為“1”。進一步擴展，對于查詢中的每個選擇條件，可以利用傳統數據庫管理系統中表的統計信息獲得它的選擇性。例如，如果選擇條件B.a2<50被估計為有30%的概率，故將列謂詞向量中其對應位置上的槽值改為0.3，用來表示查詢語句中這個過濾條件得到的基數信息。

圖2 查詢編碼

圖3 計劃編碼

3 實驗與分析

3.1 數據集與實驗設置

實驗數據集采用JOB，它從真實數據集IMDB派生出來，IMDB由21個表組成，有3.6 G大小，最大的表有3600萬行，包含了關于電影、演員和導演等信息。在JOB中一共包含33個模板和113個查詢，每個模板包含2到6個不同的變體，連接關系的數量從4到17個，每個查詢平均有8個連接。在實驗中對90個查詢進行訓練，訓練集覆蓋數據庫的所有關系和連接條件，對23個查詢進行測試，每個測試包含盡可能多的連接關系。

本實驗在GPU服務器環境配備NVIDIA Tesla K80和Ubuntu 20上，使用Python3.6和深度學習開源框架Tensorflow實現。將PostgreSQL配置為執行SmartEncoder嵌入表示的多表連接順序選擇優化方案，且使用PostgreSQL作為查詢執行引擎。為了得到在2.2節查詢編碼中的選擇謂詞返回的元組數量，在本文中使用根據PostgreSQL得到的基數估計量。本文中使用近端策略優化算法，并使用兩個帶有128個ReLUs單元的隱藏層。

3.2 實驗結果及分析

為了評估本文嵌入表示方法SmartEncoder在多表連接優化中的有效性，本文對比PostgreSQL和ReJOIN的連接順序生成執行計劃的效率。表1～表3分別展示了關系數量為4、8、14的3a模板、7a模板、28c模板(包含自連接)中參與連接的最大表、最小表的大小以及參與連接表的平均的大小和元組數量。如圖4～圖6分別展示了在關系數量為4、8、14的查詢模板中PostgreSQL和ReJOIN以及SmartEncoder生成執行計劃對應的時間。如圖4所示，執行模板3a的查詢語句，在參與連接的關系數目較少時，連接產生的中間結果也較小，此時SmartEncoder還沒有表現出明顯的優勢。如圖5中所示執行7a模板中的查詢語句，可以看出隨著關系數量的增加，這時會導致連接得到的中間結果增大，SmartEncoder的優勢逐漸顯現，計劃時間在一定程度上低于其它兩種方法的計劃時間。如圖6中所示執行28c模板的查詢時在關系數量的增多的同時SmartEncoder的計劃時間相較于其它兩種方法有了明顯的改善。從上述對比中可以看出，隨著關系數量的增加，尤其是參與連接關系數量較多時，使用SmartEncoder進行連接優化相對于其它兩種連接順序選擇優化方法的有效性。

表1 3a模板信息

表2 7a模板信息

表3 28c模板信息

圖4 3a模板執行時間

圖5 7a模板執行時間

圖6 28c模板執行時間

計劃時間：SmartEncoder對比了PostgreSQL和ReJOIN制定執行計劃的時間，根據要參與連接的關系數分組，如圖7所示，隨著查詢中關系數量的增加，PostgreSQL制定執行計劃的時間快速增長，ReJOIN和SmartEncoder都是基于學習的方法，計劃時間并沒有隨著關系數量增加而呈指數級增長。在剛開始SmartEncoder沒有表現出明顯的優勢，但同樣隨著關系數量的增加，SmartEnco-der制定執行計劃的時間逐漸有了改善。例如，在關系數量為9時，SmartEncoder的執行時間較PostgreSQL相比降低了29%，比ReJOIN降低了23%。在關系數量為12時，SmartEncoder較PostgreSQL的執行時間相比降低了22%，較ReJOIN降低了12%。

圖7 計劃時間

執行時間：如圖8的示例中對比了不同關系數量下PostgreSQL、ReJOIN和SmartEncoder的執行時間，可以看出，SmartEncoder的執行時間明顯低于PostgreSQL，較ReJOIN相比也有顯著的優勢。例如，在關系數量為9時，SmartEncoder的執行查詢語句所需要的時間較PostgreSQL相比降低了35%，較ReJOIN相比降低了20%。這得益于在本文中采用了能夠區別關于連接左右關系以及連接樹的層次結構的嵌入表示信息，且不會限制查詢樹的形態，能夠捕獲到更多關于查詢語句中關系的連接信息，也使得連接過程中有合適的中間結果，進而提高了查詢的性能。

圖8 執行時間

4 結束語

針對現有多表連接優化問題中查詢語句的嵌入表示方法對連接關系信息的關注程序不同，提出改進的嵌入表示方法SmartEncoder，能得到查詢語句的選擇謂詞和連接謂詞信息、能夠區分連接的左右關系和連接的高度信息，從而使得查詢編碼與查詢樹有一致的匹配，實現編碼可計算，能包含更多關于查詢語句的信息并將深度強化學習應用于多表連接優化問題。在模型訓練過程中，使用代價模型產生的代價進行訓練，再使用執行查詢語句的真實延遲調整。在PostgreSQL上的實驗結果表明了SmartEncoder在多表連接順序選擇優化方法的有效性。