如何優化 SQL 連接是數據庫社區數十年來一直在研究的一個大問題。近日，伯克利 RiseLab 公布了一項研究表明，深度強化學習可以被成功地應用在優化 SQL 連接上。對于大型的連接，這項技術的運行速度比傳統動態規劃快上 10 倍，比窮舉快上 10000 倍。這篇文章將介紹 SQL 連接問題以及這項強大的優化技術。

數據庫社區已經針對 SQL 查詢優化問題進行了近 40 年的研究，可以追溯到 System R 的動態規劃方法。查詢優化的核心是連接排序問題。盡管這個問題由來已久，但仍然有很多研究項目嘗試更好地理解多連接查詢中的連接優化器的性能，或者解決在企業級“數據湖”中無處不在的大型連接查詢問題。

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

背景：連接排序為什么

強化學習是解決連接排序問題的好方法?要回答這個問題，先讓我們回顧一下傳統的動態規劃(DP)方法。

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

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

經典的“left-deep”DP 方法首先計算訪問三個基本關系的***成本，我們把結果放在一張表中： 

然后，它基于這些信息枚舉所有二元關系。例如，在計算{E,S}連接的***成本時，它會查找先前相關的計算結果：

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

這樣就得到了新的一行： 

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

這就是動態規劃方法。請注意，J 的第二個操作數(關系的右邊部分)始終是基本關系，而左邊可以是中間連接結果(因此叫作“left-deep”)。這個算法的空間復雜度和時間復雜度將隨著關系的數量增加呈指數級增長，這就是為什么它通常只被用于 10-15 個關系的連接查詢。

通過強化學習進行連接排序

我們的主要想法如下：不使用如上所示的動態規劃來解決連接排序問題，而是將問題表示為馬爾可夫決策過程(MDP)，并使用強化學習(RL)來解決它，這是一種用于解決 MDP 的一般性隨機優化器。

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

• 狀態，G：需要連接的剩余關系。
• 動作，c：剩余關系之外的有效連接。
• 下一個狀態，G’：這是舊的“剩余關系”的集合，移除了兩個關系，并添加了它們的結果連接。
• 獎勵，J：新連接的估算成本。

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

我們使用 Q-learning(一種流行的 RL 技術)來解決連接排序 MDP。我們定義了 Q 函數 Q(G,c)，它直觀地描述了每個連接的長期成本：我們在當前連接決策之后對所有后續連接采取***操作的累積成本。

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

請注意，如果我們可以訪問真正的 Q 函數，就可以進行貪婪的連接排序：

算法 1

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

根據貝爾曼的***性原則，我們的這個算法可證明是***的。這個算法令人著迷的地方在于它的計算復雜度為 O(n^3)，雖然仍然很高，但卻遠低于動態規劃的指數級運行時復雜度。  

圖 1：使用神經網絡逼近 Q 函數。輸出的意思是“如果我們在當前查詢圖 G 上進行連接 c，那么最小化長期連接計劃成本是多少?”

當然，實際上我們無法訪問真正的 Q 函數，需要對其進行近似。為此，我們使用神經網絡(NN)來學習 Q 函數，并稱其為深度 Q 網絡(DQN)。這項技術與用于學習 Atari 游戲專家級玩家能力的技術如出一轍。總而言之，我們的目標是訓練一個神經網絡，它接收 (G,c) 作為輸入，并輸出估算的 Q(G,c)，見圖 1。

深度強化學習優化器 DQ

現在介紹我們的深度強化學習優化器 DQ。

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

我們已經使用 J 表示連接的估算成本，但如果數據時從真實的數據庫執行收集而來，我們也可以使用實際的運行時。

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

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

雖然這個方案非常簡單，但我們發現它具有足夠的表現力。需要注意的是，我們的方案(和學習的網絡)假設的是一個固定的數據庫，因為它需要知道確切的屬性集和表集。

神經網絡訓練和規劃。默認情況下，DQ 使用簡單的兩層全連接網絡，并使用標準隨機梯度下降進行訓練。在完成訓練后，DQ 可以接受純文本的 SQL 查詢語句，將其解析為抽象語法樹，對樹進行特征化，并在每次候選連接獲得評分時調用神經網絡(也就是在算法 1 的步驟 2 中調用神經網絡 )。***，可以使用來自實際執行的反饋定期重新調整 DQ。

評 估

為了評估 DQ，我們使用了最近發布的 Join Order Benchmark(JOB)。這個數據庫由來自 IMDB 的 21 個表組成，并提供了 33 個查詢模板和 113 個查詢。查詢中的連接關系大小范圍為 5 到 15 個。當連接關系的數量不超過 10 個時，DQ 從窮舉中收集訓練數據。

比較。我們與幾個啟發式優化器(QuickPick 和 KBZ)以及經典動態規劃(left-deep、right-deep、zig-zag)進行比較。我們對每個優化器生成的計劃進行評分，并與***計劃(我們通過窮舉獲得)進行比較。

成本模型。隨著新硬件的創新(例如 NVRAM)和向無服務器 RDBMS 架構(例如 Amazon Aurora Serverless)的轉變，我們期望看到大量新的查詢成本模型可以捕獲不同的硬件特征。為了顯示基于學習的優化器可以適應不同的環境，我們設計了 3 個成本模型：

• Cost Model 1(Index Mostly)：模擬內存數據庫并鼓勵使用索引連接。
• Cost Model 2(Hybrid Hash)：僅考慮具有內存預算的散列連接和嵌套循環連接。
• Cost Model 3(Hash Reuse)：考慮重用已構建的散列表。

從 CM1 到 CM3，成本表現出更多的非線性，向靜態策略提出了挑戰。

我們進行了 4 輪交叉驗證，確保僅對未出現在訓練工作負載中的查詢進行 DQ 評估(對于每種情況，我們在 80 個查詢上訓練并測試其中的 33 個)。我們計算查詢的平均次優性，即“成本(算法計劃)/ 成本(***計劃)”，這個數字越低越好。例如，對 Const Model 1，DQ 平均距離***計劃 1.32 倍。結果如圖 3 所示。  

圖 3：不同成本模型的平均計劃次優性。

在所有成本模型中，DQ 在沒有指數結構的先驗知識的前提下可以與***解決方案一比高下。對于固定的動態規劃，情況并非如此：例如，left-deep 在 CM1 中產生了良好的計劃(鼓勵使用索引連接)，但在 CM2 和 CM3 中效果沒有那么好。同樣，right-deep 計劃在 CM1 中沒有競爭力，但如果使用 CM2 或 CM3，right-deep 計劃突然變得不那么糟糕。需要注意的是，基于學習的優化器比手動設計的算法更強大，可以適應工作負載、數據或成本模型的變化。

此外，DQ 以比傳統動態規劃快得多的速度產生了良好的計劃(圖 4)。 

圖 4：所有 113 個 JOB 查詢的優化器延遲，按查詢中的關系數量進行分組。誤差棒表示平均值附近的±標準偏差。共進行了 5 次試驗。

在大型連接機制中，DQ 實現了極大的加速：對于***的連接，DQ 的速度是窮舉的 10000 倍，比 zig-zag 快 1000 倍，比 left-deep 和 right-deep 枚舉快 10 倍。性能增益主要來自神經網絡提供的豐富的批處理機會——對于單個迭代中所有的候選連接，DQ 針對整個批處理調用一次 NN。我們相信，對于這樣一個學習優化器來說，這是一個意義深遠的性能改進：對于更大的查詢或運行在專用加速器(例如 GPU、TPU)上時，它將表現出更大的優勢。

概 要

我們認為深度強化學習非常適合用來解決連接排序問題。深度強化學習使用數據驅動方法來調整針對特定數據集和工作負載的查詢計劃，并觀察連接成本，而不是使用固定的啟發式。為了選擇查詢計劃，DQ 使用了能夠在訓練時編對態規劃表的壓縮版本進行編碼的神經網絡。

DQ 只是冰山一角，在數據庫社區存在激烈的爭論，圍繞著如何將更多的學習(或者說是數據適應性)納入到現有系統中。我們希望我們的工作是實現更智能的查詢優化器的***步。