用于多表連接優(yōu)化的深度強化學(xué)習(xí)嵌入表示

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

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

2 SmartJoin模型

在基于深度強化學(xué)習(xí)的多表連接優(yōu)化方法中，將當(dāng)前的子樹作為狀態(tài)，動作是連接兩個子樹的操作，對查詢語句的連接方案和選擇條件以及連接樹的信息進行編碼，得到關(guān)于查詢語句的嵌入表示信息，作為神經(jīng)網(wǎng)絡(luò)的輸入，可以由深度強化學(xué)習(xí)算法學(xué)習(xí)，每次操作將兩個關(guān)系進行連接，當(dāng)所有的關(guān)系被連接完成時，代表一個回合結(jié)束，模型會在多個回合中進行學(xué)習(xí)。

2.1 模型流程

多表連接優(yōu)化的目標(biāo)是找到一個每個狀態(tài)下采取動作所構(gòu)成的序列，使得累計代價最小。當(dāng)前狀態(tài)向量化以后作為輸入被送入狀態(tài)層，通過若干個隱藏層進行轉(zhuǎn)換，每層通過激活函數(shù)轉(zhuǎn)換其輸入數(shù)據(jù)，將輸出結(jié)果送至后續(xù)層，數(shù)據(jù)最終被傳遞到動作層。動作層的每個神經(jīng)元代表一個潛在的行動，它們的輸出被歸一化后形成一個概率分布，策略πθ(St,At) 通過從這個概率分布中取樣來選擇動作?；谏疃葟娀瘜W(xué)習(xí)的多表連接優(yōu)化方法SmartJOIN的整體框架如圖1所示。

圖1 SmartJOIN框架

本文使用基于策略梯度的強化學(xué)習(xí)方法——近端策略優(yōu)化算法[8]來進行連接順序決策，智能體根據(jù)一個參數(shù)化的策略πθ來選擇最佳操作，其中θ代表一個代表策略參數(shù)，在近端策略優(yōu)化算法中，用參數(shù)化神經(jīng)網(wǎng)絡(luò)表示策略πθ， 其中θ為網(wǎng)絡(luò)的權(quán)重，策略依據(jù)環(huán)境的反饋來調(diào)整θ， 從而優(yōu)化策略參數(shù)θ， 使得預(yù)期的獎勵Rπ(θ) 最優(yōu)。給定一個狀態(tài)和一個動作的集合At， 策略πθ會為At中的每個動作輸出一個概率(即連接兩個表的概率)，然后根據(jù)概率選擇動作，最終的連接順序結(jié)果發(fā)送到優(yōu)化器進行后續(xù)操作和執(zhí)行。

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

2.2 嵌入表示方法SmartEncoder

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

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

圖2 查詢編碼

圖3 計劃編碼

3 實驗與分析

3.1 數(shù)據(jù)集與實驗設(shè)置

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

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

3.2 實驗結(jié)果及分析

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

表1 3a模板信息

表2 7a模板信息

表3 28c模板信息

圖4 3a模板執(zhí)行時間

圖5 7a模板執(zhí)行時間

圖6 28c模板執(zhí)行時間

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

圖7 計劃時間

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

圖8 執(zhí)行時間

4 結(jié)束語

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