Join Query Optimization with Deep Reinforcement Learning Algorithms

語言: CN / TW / HK
時間 2020-12-30 10:01:56
用了這個評估優化LiteOS映象利器，我徹底飄了…>>>

目錄

1.動機

 查詢優化已經進行幾十年的研究了，而連線順序選擇又是查詢優化中的一個非常重要的問題。連線順序選擇是一個NP-hard問題，隨著連線關係數量的線性增加，而連線順序呈現指數級增長。（1）傳統資料庫採用動態規劃的方法，再加上一些限定規則進行修剪搜尋空間，避免窮舉所有可能的連線順序，但是也會消耗許多資源，而且這些限定規則往往是基於專家經驗，需要手工設計和頻繁維護。同時也降低了在更大的搜尋空間找到更好的計劃的可能。（2）傳統資料庫採用的成本模型，基於傳統的基數估計，而基數估計中，屬性往往是採取獨立性假設，但是真實世界的資料庫，各個屬性並不是完全獨立，相反，還具有高度的相關性，所以，這樣會導致，成本模型估算不準確。最終導致次優的執行計劃。（3）傳統的資料庫優化器不會從過去執行過的糟糕計劃中學習教訓，吸取經驗，從而下次執行依然不能避免糟糕的計劃，雖然早在多年前Leo就提出了學習型優化器，不過這些方法並沒有廣泛採用。

2.貢獻

2.1總體概況

 最近，提出了將機器學習引入資料庫領域，取得了不錯的進展，可替代傳統的查詢優化器元件。於是，基於Rejoin、DQ提供的思想，本文提出了一種通用的連線順序優化器架構FOOP，可以結合不同的深度強化學習演算法進行直接對比。FOOP主要可以觀察查詢優化過程中所有關係和中間執行計劃。

2.2具體點

（1）FOOP將連線順序選擇問題表達為可觀察的強化學習過程，而且將FOOP獨立於資料庫系統，處於應用層，直接跟蹤所有關係和中間執行計劃。
（2）由FOOP框架，首次直接比較，各種DRL演算法在查詢優化中的效能。
（3）FOOP使用時間複雜度較低的優化演算法生成的查詢計劃與傳統優化器生成的查詢計劃，在成本模型中估計值相當。

3.背景

3.1查詢優化領域文獻

  1. 查詢優化仍未解決
    （1）Is query optimization a solved problem

  2. 傳統資料庫優化方法
    （2）System R
    （3）Vulcano
    （4）Leo


  3. 引入新的查詢基準
    （5）How good are query optimizers, really?

  4. 機器學習改進基數估計
    （6）Neural network-based approaches for predicting query response times.
    （7） Towards predicting query execution time for concurrent and dynamic database workloads.
    （8）Learning-based query performance modeling and prediction.
    （9）Predicting multiple metrics for queries: Better decisions enabled by machine learning.
    （10）Robust estimation of resource consumption for sql queries using statistical techniques.
    （11）Wisedb: a learning-based workload management advisor for cloud databases.





  5. 強化學習改進優化
    （12）Database meets deep learning: challenges and opportunities.
    （13）Towards a hands-free query optimizer through deep learning.（DQ擴充套件）
    （14）Learning state representations for query optimization with deep reinforcement learning.（狀態如何表示）
    （15）Skinnerdb: regret-bounded query evaluation via reinforcement learning.
    （16）Neo: A learned query optimizer.（Neo）——借鑑（Mastering the
    game of go with deep neural networks and tree search.）
    （17）DQN應用於查詢優化——借鑑（Playing atari with deep reinforcement learning. arXiv preprint）
    （18）Rejoin和DQ均依賴傳統成本模型。DQ加入微調機制。DQN和PG比Neo的DNN訓練時間更短。







3.2查詢優化為什麼是一個仍未解決的問題

  1. 查詢優化目標：將SQL轉換為高效的執行計劃
  2. 連線順序選擇是查詢優化重難點，連線順序選擇本質搜尋最佳排序，最佳意味著成本估算達到最低。
  3. 一般來說，n個關係進行排序，時間複雜度為O(n!)，
  4. 連線順序還需要考慮到物理運算子，那麼這個複雜度將會大大增加
  5. 對於n個關係，可以得到二叉查詢樹數量為(2*n-1)!/((n-1)!*n!)，例如：
    在這裡插入圖片描述
    在這裡插入圖片描述

  6. 以上僅僅是查詢二叉樹的形狀數量，每一顆二叉樹的結點還有不同的排列組合，這樣一來複雜性很大。更不用說，諸如選擇，投影之類的問題，再加上，複雜度極高。
  7. 一般來說，查詢優化的連線順序選擇通常使用n!評估，但是n!的複雜性也高，即也是一個NP難問題。因此需要設計優化演算法減小搜尋空間，動態規劃加上一系列限定規則可以做到，但是，不能保證未搜尋空間一定不存在最優計劃，換句話說有可能找到的是次優計劃，那麼仍需要進行研究新演算法，減少時間複雜度。
  8. 查詢優化器的架構主體由執行計劃器和成本估算模型組成。
  9. 計劃器是主體模組，功能是列出並檢查所有可能的查詢計劃，然後根據特定的成本模型選擇最佳方案。其中的問題是列出所有可能的查詢計劃，搜尋空間過大，時間複雜度太高，也是一個NP難問題。為了解決這個問題，通常是啟發式方法。例如動態規劃結合特定規則減少搜尋空間、若查詢過大，則再加上貪婪演算法、遺傳演算法。然後，再為了降低複雜度，只用左深查詢樹。
  10. 成本模型含義是指關於資料庫的不同假設和統計資料，進而評估查詢計劃的總體成本。成本模型主要包括CPU估計、I/O估計、基數估計。特別是，基數估計是在簡單情況下，例如對於基表，使用分位數統計、頻率分析、不同的計數規則進行預測。

3.3查詢優化中主要未解決問題

  1. 查詢計劃的限制性問題
     原因：窮舉耗時；解決：傳統優化器只使用左深樹；結果：降低時間複雜度至O(n!)；不足：減少了搜尋空間，降低找到最優方案的機會。深入：一般情況，左深接近最優，但對於複雜（大量連線關係）查詢的分析型資料庫，左深反而是次優。
  2. 查詢優化的基準問題
     原因：評估查詢優化器的基準的列值均勻分佈且獨立分佈，而真實世界資料庫列值相互關聯且非均勻分佈，因此，基於現有基準進行調整的查詢優化器不能推廣到真實世界，僅為部分優化；解決：採用源自真實世界的基準。
  3. 基數估計的錯誤問題
     原因：分位數統計無法檢測相關列值，無法比較列值，進而作出統計。因此，在非均勻分佈的列值會產生錯誤，進而導致成本模型估算錯誤。

3.4應用於查詢優化的強化學習概念的調整

  1. 強化學習定義：學習做什麼？環境——>行動，在這個過程中，將產生訊號（積極或者消極）；例子：嬰兒與周圍環境的互動，無人教導，產生因果資訊，某一個動作導致某一個結果。
  2. 數學角度：這個過程抽象為函式；目標：試圖得到最大化獎勵，但不直接給出採取哪一個動作。
  3. 基礎：貝爾曼最優原則、動態規劃、馬爾科夫決策過程
  4. 馬爾科夫擴充套件思想：agent與環境互動，採取一系列行動，期待最終得到最大化獎勵；關鍵點：未來狀態取決於當前狀態，與過去狀態和動作無關；內容：如圖1五元組；目標：策略S——>A（狀態到動作的函式），該函式可以使最終獎勵最大，工作原理如圖2。
    圖1
    圖2

3.5RL演算法——Q-learning

  1. Q-learning，來源：結合MC與DP，屬於TD演算法一種；內容：函式Q(s，a)指導在狀態s時採取最優動作；特點：離線策略演算法，簡化演算法分析、快速收斂，不過當前策略還是有作用，可以決定採取哪一個狀態-動作；傳統：Q表儲存資訊，不足之處是儲存過大，計算複雜；改進：非線性函式近似Q函式，特別是神經網路；借鑑思想：Atari；例子：DQN；關鍵點：輸入獨立性，但在互動過程，資料並不獨立；解決：引入經驗回放。
  2. 經驗回放，定義：收集觀察資料的緩衝區
  3. 目標網路，定義：解決Q值計算與更新引數的關聯較大，採用兩個相同Q網路，當前網路僅選擇動作，更新引數；目標網路僅計算Q值，不需要迭代更新，僅隔一段時間從當前網路複製引數即可；使得演算法收斂快。
    在這裡插入圖片描述
  4. DDQN+PR：DDQN再進一步通過解耦目標Q值動作選擇與Q值計算，避免低高估。PR通過改變樣本被選中的概率，提出優先順序，一般來說，樣本的TD誤差越大，優先順序高，越容易收斂。

3.6RL演算法——Policy Gradient Methods

隨後補充介紹~

4.FOOP架構

  1. 查詢優化建模為MDP；
    在這裡插入圖片描述
    在這裡插入圖片描述

  2. 查詢、資料庫資訊、狀態、動作——>特徵向量
    在這裡插入圖片描述
    其中；代表未連線，（）代表已經連線，[]代表某個狀態
    在這裡插入圖片描述
    其中（）代表動作，動作僅代表兩個關係連線，這是巧妙設計，減小動作空間，不至於一開始就設計三個或者以上關係的連線。如下圖例子：
    在這裡插入圖片描述
    在這裡插入圖片描述





其中灰色代表無效動作，亮黃代表已選擇動作，普黑代表候選動作。

  1. 獎勵難點：實際查詢時間難以獲取，且代價昂貴；解決：採取傳統資料庫自帶成本模型（借鑑How good are query optimizers, really?）；內容：負成本，且不計運算元計劃成本，只獲取最終成本。
    成本函式如下;在這裡插入圖片描述
    其中R代表基本關係，Q代表子查詢計劃，r和l分別代表右側和左側，hj和ij代表雜湊連線和索引巢狀迴圈連線，| |代表基數估計函式，其他為引數。該模型不考慮I/O，簡單，與PG相似。
    獎勵函式如下：
    在這裡插入圖片描述
    標準化如下：
    成本模型估算範圍(106,1018)~獎勵範圍(-10,10)，再進行獎勵範圍剪裁。首先獎勵為負，限定在(-10,0)，其次若成本模型估算高於1013，獎勵均為-10。如下圖：
    在這裡插入圖片描述






  2. 關鍵點：特徵化足夠準確，RL演算法足夠優

5.實驗

5.1配置

  1. 使用PG的基數估計器、執行器
  2. 獨立部署FOOP
  3. 基於TensorFlow和OpenAI_gym
  4. 查詢集JOB、資料集IMDB
  5. 訓練集80、測試集33

5.2演算法比較

  1. DQN
    借鑑DQ進行設定，引數列表如下：在這裡插入圖片描述
    關鍵點設定：預期獎勵依賴成本模型，獎勵只給予最終計劃，獎勵為負

  2. DDQN
    加入優先經驗回放，引數列表如下:
    在這裡插入圖片描述

  3. 實驗結果對比如下：
    在這裡插入圖片描述
    結論：降低高方差，避免昂貴計劃。

  4. PPO
    隨後介紹~

5.3增強RL演算法

  1. 訓練測試集劃分來增強
    原有：隨機劃分
    改進：滿足條件劃分（1）所有關係均存在於訓練集（2）所有連線條件均存在於訓練集（3）測試集儘可能包含不同連線條件

  2. 實驗對比結果如下：
    在這裡插入圖片描述
    其中方差減小，更加穩定，減少過擬合。

  3. 訓練多個策略來增強，原理：多個策略優化查詢計劃，再從多個已經優化的查詢計劃中進行選擇成本估算相對最低的最優計劃。
  4. 實驗對比結果如下：
    在這裡插入圖片描述

5.4與其他演算法對比實驗

  1. DQN系列與DP-left估算成本比較：
    在這裡插入圖片描述
    這裡成本模型由於是資料庫自帶，自然更好。

  2. PPO與DP-left估算成本比較：
    在這裡插入圖片描述
  3. 藍色點低於黃色異常分析：如圖，因為對於某些離群查詢，涉及到的關係，在訓練時很少訪問，而在測試時大量訪問，導致測試集不能很好包含足夠的訓練樣例，不能很好學習這些查詢。
    在這裡插入圖片描述
  4. 真實查詢時間比較：
    在這裡插入圖片描述
    其中DRL演算法的延遲優化與查詢關係為線性關係，且為O(n)。而DP-left為O(n!)。

6.結論

  1. FOOP僅優化連線順序選擇。
  2. FOOP易擴充套件為select-project-jion
  3. PPO優於DQN系列
  4. 整合（多策略）學習提高優化效能
  5. FOOP生成查詢計劃的成本與PG相似，但延遲明顯較低。

7.展望

  1. 問題：RL演算法樣本低效，需密集計算；解決：採取PG專家引導訓練，快速收斂
  2. 問題：成本模型中基數估計可能出錯；解決：微調，採用執行過的樣本的基數資料
  3. 問題：實現端到端；解決：進行擴充套件，例如對選擇、投影、聚合等操作進行優化設計
    本文是對《Join Query Optimization with Deep Reinforcement Learning Algorithms》進行闡述。
「」
「」