快1萬倍！伯克利提出用深度RL優化SQL查詢
公眾號/AI前線
策劃編輯 | Natalie
作者 | 伯克利 RiseLab
譯者 | 無明
編輯 | Vincent
AI 前線導讀：如何優化 SQL 連線是資料庫社群數十年來一直在研究的一個大問題。近日，伯克利 RiseLab 公佈了一項研究表明，深度強化學習可以被成功地應用在優化 SQL 連線上。對於大型的連線，這項技術的執行速度比傳統動態規劃快上 10 倍，比窮舉快上 10000 倍。這篇文章將介紹 SQL 連線問題以及這項強大的優化技術，更多詳細內容可以參看論文”Learning to Optimize Join Queries With Deep Reinforcement Learning“（連結在文末）。
更多優質內容請關注微信公眾號“AI 前線”（ID：ai-front）
資料庫社群已經針對 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 只是冰山一角，在資料庫社群存在激烈的爭論，圍繞著如何將更多的學習（或者說是資料適應性）納入到現有系統中。我們希望我們的工作是實現更智慧的查詢優化器的第一步。有關詳細資訊，請參閱我們的 Arxiv 論文。
Arxiv 論文連結：
https://arxiv.org/abs/1808.03196
英文原文：
ofollow,noindex" target="_blank">SQL Query Optimization Meets Deep Reinforcement Learning