如何優(yōu)化 SQL 連接是數(shù)據(jù)庫(kù)社區(qū)數(shù)十年來(lái)一直在研究的一個(gè)大問(wèn)題。近日，伯克利 RiseLab 公布了一項(xiàng)研究表明，深度強(qiáng)化學(xué)習(xí)可以被成功地應(yīng)用在優(yōu)化 SQL 連接上。對(duì)于大型的連接，這項(xiàng)技術(shù)的運(yùn)行速度比傳統(tǒng)動(dòng)態(tài)規(guī)劃快上 10 倍，比窮舉快上 10000 倍。這篇文章將介紹 SQL 連接問(wèn)題以及這項(xiàng)強(qiáng)大的優(yōu)化技術(shù)。

數(shù)據(jù)庫(kù)社區(qū)已經(jīng)針對(duì) SQL 查詢優(yōu)化問(wèn)題進(jìn)行了近 40 年的研究，可以追溯到 System R 的動(dòng)態(tài)規(guī)劃方法。查詢優(yōu)化的核心是連接排序問(wèn)題。盡管這個(gè)問(wèn)題由來(lái)已久，但仍然有很多研究項(xiàng)目嘗試更好地理解多連接查詢中的連接優(yōu)化器的性能，或者解決在企業(yè)級(jí)“數(shù)據(jù)湖”中無(wú)處不在的大型連接查詢問(wèn)題。

在我們的論文中，我們表明了如何通過(guò)深度強(qiáng)化學(xué)習(xí)技術(shù)來(lái)攻克這個(gè)已經(jīng)存在了數(shù)十年的挑戰(zhàn)。我們將連接排序問(wèn)題表示為馬爾可夫決策過(guò)程(MDP)，然后構(gòu)建了一個(gè)使用深度 Q 網(wǎng)絡(luò)(DQN)的優(yōu)化器，用來(lái)有效地對(duì)連接進(jìn)行排序。我們基于 Join Order Benchmark(最近提出的工作負(fù)載，專門用于壓力測(cè)試連接優(yōu)化)對(duì)我們的方法進(jìn)行了評(píng)估。我們只使用了適量的訓(xùn)練數(shù)據(jù)，基于強(qiáng)化學(xué)習(xí)的深度優(yōu)化器的執(zhí)行計(jì)劃成本比所有我們能想到的成本模型***解決方案改進(jìn)了 2 倍，比下一個(gè)***的啟發(fā)式改進(jìn)最多可達(dá) 3 倍——所有這些都在計(jì)劃的延遲范圍，比動(dòng)態(tài)規(guī)劃快 10 倍，比窮舉快 10000 倍。

背景：連接排序?yàn)槭裁?/h3>

強(qiáng)化學(xué)習(xí)是解決連接排序問(wèn)題的好方法?要回答這個(gè)問(wèn)題，先讓我們回顧一下傳統(tǒng)的動(dòng)態(tài)規(guī)劃(DP)方法。

假設(shè)一個(gè)數(shù)據(jù)庫(kù)包含三張表：Employees、Salaries 和 Taxes。下面這個(gè)查詢用于找出“所有 Manager 1 員工的總稅額”： 

 

 

這個(gè)查詢包含了三個(gè)關(guān)系連接。在下面的示例中，我們使用 J(R) 表示訪問(wèn)基本關(guān)系 R 的成本，使用 J(T1,T2) 表示連接 T1 和 T2 的成本。為簡(jiǎn)單起見，我們假設(shè)了一個(gè)訪問(wèn)方法，一個(gè)連接方法和一個(gè)對(duì)稱連接成本(即 J(T1,T2)=J(T2,T1))。

經(jīng)典的“left-deep”DP 方法首先計(jì)算訪問(wèn)三個(gè)基本關(guān)系的***成本，我們把結(jié)果放在一張表中： 

 

 

然后，它基于這些信息枚舉所有二元關(guān)系。例如，在計(jì)算{E,S}連接的***成本時(shí)，它會(huì)查找先前相關(guān)的計(jì)算結(jié)果：

Best({E, S}) = Best({E}) + Best({S}) + J({E}, S)

這樣就得到了新的一行： 

 

 

這個(gè)算法遍歷其他二元關(guān)系集，最終找到連接所有三張表的***成本。這需要在二元關(guān)系和基本關(guān)系的所有可能“left-deep”組合中取最小值： 

 

 

 

這就是動(dòng)態(tài)規(guī)劃方法。請(qǐng)注意，J 的第二個(gè)操作數(shù)(關(guān)系的右邊部分)始終是基本關(guān)系，而左邊可以是中間連接結(jié)果(因此叫作“left-deep”)。這個(gè)算法的空間復(fù)雜度和時(shí)間復(fù)雜度將隨著關(guān)系的數(shù)量增加呈指數(shù)級(jí)增長(zhǎng)，這就是為什么它通常只被用于 10-15 個(gè)關(guān)系的連接查詢。

通過(guò)強(qiáng)化學(xué)習(xí)進(jìn)行連接排序

我們的主要想法如下：不使用如上所示的動(dòng)態(tài)規(guī)劃來(lái)解決連接排序問(wèn)題，而是將問(wèn)題表示為馬爾可夫決策過(guò)程(MDP)，并使用強(qiáng)化學(xué)習(xí)(RL)來(lái)解決它，這是一種用于解決 MDP 的一般性隨機(jī)優(yōu)化器。

首先，我們將連接排序表示為 MDP：

• 狀態(tài)，G：需要連接的剩余關(guān)系。
• 動(dòng)作，c：剩余關(guān)系之外的有效連接。
• 下一個(gè)狀態(tài)，G’：這是舊的“剩余關(guān)系”的集合，移除了兩個(gè)關(guān)系，并添加了它們的結(jié)果連接。
• 獎(jiǎng)勵(lì)，J：新連接的估算成本。

可以簡(jiǎn)單地表示成 (G, c, G’, J) 。

我們使用 Q-learning(一種流行的 RL 技術(shù))來(lái)解決連接排序 MDP。我們定義了 Q 函數(shù) Q(G,c)，它直觀地描述了每個(gè)連接的長(zhǎng)期成本：我們?cè)诋?dāng)前連接決策之后對(duì)所有后續(xù)連接采取***操作的累積成本。

Q(G, c) = J(c) + \min_{c’} Q(G’, c’)

請(qǐng)注意，如果我們可以訪問(wèn)真正的 Q 函數(shù)，就可以進(jìn)行貪婪的連接排序：

算法 1

• 從初始查詢圖開始;
• 找到 Q(G,c) ***的連接;
• 更新查詢圖并重復(fù)。

根據(jù)貝爾曼的***性原則，我們的這個(gè)算法可證明是***的。這個(gè)算法令人著迷的地方在于它的計(jì)算復(fù)雜度為 O(n^3)，雖然仍然很高，但卻遠(yuǎn)低于動(dòng)態(tài)規(guī)劃的指數(shù)級(jí)運(yùn)行時(shí)復(fù)雜度。  

圖 1：使用神經(jīng)網(wǎng)絡(luò)逼近 Q 函數(shù)。輸出的意思是“如果我們?cè)诋?dāng)前查詢圖 G 上進(jìn)行連接 c，那么最小化長(zhǎng)期連接計(jì)劃成本是多少?”

當(dāng)然，實(shí)際上我們無(wú)法訪問(wèn)真正的 Q 函數(shù)，需要對(duì)其進(jìn)行近似。為此，我們使用神經(jīng)網(wǎng)絡(luò)(NN)來(lái)學(xué)習(xí) Q 函數(shù)，并稱其為深度 Q 網(wǎng)絡(luò)(DQN)。這項(xiàng)技術(shù)與用于學(xué)習(xí) Atari 游戲?qū)＜壹?jí)玩家能力的技術(shù)如出一轍。總而言之，我們的目標(biāo)是訓(xùn)練一個(gè)神經(jīng)網(wǎng)絡(luò)，它接收 (G,c) 作為輸入，并輸出估算的 Q(G,c)，見圖 1。

深度強(qiáng)化學(xué)習(xí)優(yōu)化器 DQ

現(xiàn)在介紹我們的深度強(qiáng)化學(xué)習(xí)優(yōu)化器 DQ。

數(shù)據(jù)采集。要學(xué)習(xí) Q 函數(shù)，我們首先需要觀察過(guò)去的執(zhí)行數(shù)據(jù)。DQ 可以接受來(lái)自任何底層優(yōu)化器的一系列 (G,c,G’,J)。例如，我們可以運(yùn)行經(jīng)典的 left-deep 動(dòng)態(tài)規(guī)劃(如背景部分所示)，并從 DP 表中計(jì)算出一系列“連接軌跡”。完整軌跡中的元組看起來(lái)像是 (G,c,G’,J)=({E,S,T}, join(S,T), {E,ST}，110)，它代表從初始查詢圖(狀態(tài))開始并將 S 和 T 連接在一起(動(dòng)作)的步驟。

我們已經(jīng)使用 J 表示連接的估算成本，但如果數(shù)據(jù)時(shí)從真實(shí)的數(shù)據(jù)庫(kù)執(zhí)行收集而來(lái)，我們也可以使用實(shí)際的運(yùn)行時(shí)。

狀態(tài)和動(dòng)作的特征化。由于使用神經(jīng)網(wǎng)絡(luò)來(lái)表示 Q(G,c)，我們需要將狀態(tài) G 和動(dòng)作 c 作為固定長(zhǎng)度的特征向量饋送到網(wǎng)絡(luò)中。DQ 的特征化方案非常簡(jiǎn)單：我們使用 1-hot 向量來(lái)編碼(1)查詢圖中存在的所有屬性的集合，包括模式中的所有屬性，(2)連接左側(cè)的參與屬性， (3)連接右側(cè)的屬性。如圖 2 所示。  

圖 2：查詢及其相應(yīng)的特征化。我們假設(shè)一個(gè)包含 Employees、Positions 和 Salaries 三張表的數(shù)據(jù)庫(kù)。圖中顯示了部分連接和完全連接。(G,c) 的最終特征向量是 A_G(查詢圖的屬性)、A_L(左側(cè)的屬性)和 A_R(右側(cè)的屬性)的串聯(lián)。

雖然這個(gè)方案非常簡(jiǎn)單，但我們發(fā)現(xiàn)它具有足夠的表現(xiàn)力。需要注意的是，我們的方案(和學(xué)習(xí)的網(wǎng)絡(luò))假設(shè)的是一個(gè)固定的數(shù)據(jù)庫(kù)，因?yàn)樗枰来_切的屬性集和表集。

神經(jīng)網(wǎng)絡(luò)訓(xùn)練和規(guī)劃。默認(rèn)情況下，DQ 使用簡(jiǎn)單的兩層全連接網(wǎng)絡(luò)，并使用標(biāo)準(zhǔn)隨機(jī)梯度下降進(jìn)行訓(xùn)練。在完成訓(xùn)練后，DQ 可以接受純文本的 SQL 查詢語(yǔ)句，將其解析為抽象語(yǔ)法樹，對(duì)樹進(jìn)行特征化，并在每次候選連接獲得評(píng)分時(shí)調(diào)用神經(jīng)網(wǎng)絡(luò)(也就是在算法 1 的步驟 2 中調(diào)用神經(jīng)網(wǎng)絡(luò) )。***，可以使用來(lái)自實(shí)際執(zhí)行的反饋定期重新調(diào)整 DQ。

評(píng) 估

為了評(píng)估 DQ，我們使用了最近發(fā)布的 Join Order Benchmark(JOB)。這個(gè)數(shù)據(jù)庫(kù)由來(lái)自 IMDB 的 21 個(gè)表組成，并提供了 33 個(gè)查詢模板和 113 個(gè)查詢。查詢中的連接關(guān)系大小范圍為 5 到 15 個(gè)。當(dāng)連接關(guān)系的數(shù)量不超過(guò) 10 個(gè)時(shí)，DQ 從窮舉中收集訓(xùn)練數(shù)據(jù)。

比較。我們與幾個(gè)啟發(fā)式優(yōu)化器(QuickPick 和 KBZ)以及經(jīng)典動(dòng)態(tài)規(guī)劃(left-deep、right-deep、zig-zag)進(jìn)行比較。我們對(duì)每個(gè)優(yōu)化器生成的計(jì)劃進(jìn)行評(píng)分，并與***計(jì)劃(我們通過(guò)窮舉獲得)進(jìn)行比較。

成本模型。隨著新硬件的創(chuàng)新(例如 NVRAM)和向無(wú)服務(wù)器 RDBMS 架構(gòu)(例如 Amazon Aurora Serverless)的轉(zhuǎn)變，我們期望看到大量新的查詢成本模型可以捕獲不同的硬件特征。為了顯示基于學(xué)習(xí)的優(yōu)化器可以適應(yīng)不同的環(huán)境，我們?cè)O(shè)計(jì)了 3 個(gè)成本模型：

• Cost Model 1(Index Mostly)：模擬內(nèi)存數(shù)據(jù)庫(kù)并鼓勵(lì)使用索引連接。
• Cost Model 2(Hybrid Hash)：僅考慮具有內(nèi)存預(yù)算的散列連接和嵌套循環(huán)連接。
• Cost Model 3(Hash Reuse)：考慮重用已構(gòu)建的散列表。

從 CM1 到 CM3，成本表現(xiàn)出更多的非線性，向靜態(tài)策略提出了挑戰(zhàn)。

我們進(jìn)行了 4 輪交叉驗(yàn)證，確保僅對(duì)未出現(xiàn)在訓(xùn)練工作負(fù)載中的查詢進(jìn)行 DQ 評(píng)估(對(duì)于每種情況，我們?cè)?80 個(gè)查詢上訓(xùn)練并測(cè)試其中的 33 個(gè))。我們計(jì)算查詢的平均次優(yōu)性，即“成本(算法計(jì)劃)/ 成本(***計(jì)劃)”，這個(gè)數(shù)字越低越好。例如，對(duì) Const Model 1，DQ 平均距離***計(jì)劃 1.32 倍。結(jié)果如圖 3 所示。  

圖 3：不同成本模型的平均計(jì)劃次優(yōu)性。

在所有成本模型中，DQ 在沒(méi)有指數(shù)結(jié)構(gòu)的先驗(yàn)知識(shí)的前提下可以與***解決方案一比高下。對(duì)于固定的動(dòng)態(tài)規(guī)劃，情況并非如此：例如，left-deep 在 CM1 中產(chǎn)生了良好的計(jì)劃(鼓勵(lì)使用索引連接)，但在 CM2 和 CM3 中效果沒(méi)有那么好。同樣，right-deep 計(jì)劃在 CM1 中沒(méi)有競(jìng)爭(zhēng)力，但如果使用 CM2 或 CM3，right-deep 計(jì)劃突然變得不那么糟糕。需要注意的是，基于學(xué)習(xí)的優(yōu)化器比手動(dòng)設(shè)計(jì)的算法更強(qiáng)大，可以適應(yīng)工作負(fù)載、數(shù)據(jù)或成本模型的變化。

此外，DQ 以比傳統(tǒng)動(dòng)態(tài)規(guī)劃快得多的速度產(chǎn)生了良好的計(jì)劃(圖 4)。 

圖 4：所有 113 個(gè) JOB 查詢的優(yōu)化器延遲，按查詢中的關(guān)系數(shù)量進(jìn)行分組。誤差棒表示平均值附近的±標(biāo)準(zhǔn)偏差。共進(jìn)行了 5 次試驗(yàn)。

在大型連接機(jī)制中，DQ 實(shí)現(xiàn)了極大的加速：對(duì)于***的連接，DQ 的速度是窮舉的 10000 倍，比 zig-zag 快 1000 倍，比 left-deep 和 right-deep 枚舉快 10 倍。性能增益主要來(lái)自神經(jīng)網(wǎng)絡(luò)提供的豐富的批處理機(jī)會(huì)——對(duì)于單個(gè)迭代中所有的候選連接，DQ 針對(duì)整個(gè)批處理調(diào)用一次 NN。我們相信，對(duì)于這樣一個(gè)學(xué)習(xí)優(yōu)化器來(lái)說(shuō)，這是一個(gè)意義深遠(yuǎn)的性能改進(jìn)：對(duì)于更大的查詢或運(yùn)行在專用加速器(例如 GPU、TPU)上時(shí)，它將表現(xiàn)出更大的優(yōu)勢(shì)。

概 要

我們認(rèn)為深度強(qiáng)化學(xué)習(xí)非常適合用來(lái)解決連接排序問(wèn)題。深度強(qiáng)化學(xué)習(xí)使用數(shù)據(jù)驅(qū)動(dòng)方法來(lái)調(diào)整針對(duì)特定數(shù)據(jù)集和工作負(fù)載的查詢計(jì)劃，并觀察連接成本，而不是使用固定的啟發(fā)式。為了選擇查詢計(jì)劃，DQ 使用了能夠在訓(xùn)練時(shí)編對(duì)態(tài)規(guī)劃表的壓縮版本進(jìn)行編碼的神經(jīng)網(wǎng)絡(luò)。

DQ 只是冰山一角，在數(shù)據(jù)庫(kù)社區(qū)存在激烈的爭(zhēng)論，圍繞著如何將更多的學(xué)習(xí)(或者說(shuō)是數(shù)據(jù)適應(yīng)性)納入到現(xiàn)有系統(tǒng)中。我們希望我們的工作是實(shí)現(xiàn)更智能的查詢優(yōu)化器的***步。