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

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

2 SmartJoin模型

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

2.1 模型流程

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

圖1 SmartJOIN框架

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

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

2.2 嵌入表示方法SmartEncoder

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

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

圖2 查詢編碼

圖3 計(jì)劃編碼

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

表1 3a模板信息

表2 7a模板信息

表3 28c模板信息

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

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

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

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

圖7 計(jì)劃時(shí)間

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

圖8 執(zhí)行時(shí)間

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

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