[發明專利]一種數據庫的查詢重寫方法

在審

• 申請號: 202110644943.8
• 申請日: 2021-06-09
• 公開（公告）號: CN113515540A
• 公開（公告）日: 2021-10-19
• 發明（設計）人: 李國良;周煊赫
• 申請（專利權）人: 清華大學
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/22;G06N3/04;G06N3/08
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 羅文群

本發明屬于信息檢索技術領域，涉及一種數據庫的查詢重寫方法。本發明首先利用策略樹表示任意一個查詢語句的大量等價查詢和相應的重寫順序，其次，本發明基于蒙特卡洛樹搜索算法在策略樹上選擇高收益的重寫順序，實現查詢開銷和重寫頻率的平衡；為了更準確的估計重寫后查詢的整體收益，本發明利用深度注意力網絡學習當前查詢與重寫規則和訪問數據的關聯關系，并利用深度學習根據查詢特征和提取的關聯關系擬合當前查詢的整體收益。最后，針對具有大規模的策略樹的復雜查詢，本發明提出了一種并行節點選擇算法，在策略樹上利用一種最優算法選擇沒有祖先?后代關系且總收益最高的多個節點，并行擴展策略樹，從而大幅提高查詢重寫效率。

技術領域

本發明屬于信息檢索技術領域，涉及一種數據庫的查詢重寫方法，尤其涉及一種基于深度學習和蒙特卡洛樹搜索的查詢重寫方法。

背景技術

查詢重寫通過合理的選擇重寫操作，可以將慢查詢(如，存在冗余算子)的性能提高多個數量級。作為查詢優化中的一個基本問題，查詢重寫旨在將結構化查詢語言(StructuredQueryLanguage，SQL)轉換為等效查詢，但性能更高。具體而言，查詢重寫對查詢語句進行邏輯上的等價變換(如，刪除冗余算子，提升邏輯子查詢)，從而保證(1) 重寫的查詢等價于原始查詢；(2)重寫的查詢執行時間降低。

查詢重寫是一個多項式復雜程度的非確定性問題，現有方法通過將查詢與預定義的規則順序進行匹配(例如謂詞下推規則)來重寫SQL查詢。但是，這種方法的局限性在于，它們僅使用默認順序(例如，自頂而下重寫邏輯計劃)，沒有考慮和其他重寫順序相比的相對代價收益，進而導致局部最優，甚至表現劣化。一種簡單的策略，是對一些重寫順序進行采樣，并根據查詢開銷降低最多的順序進行重寫。但是，由于存在大量潛在的重寫順序，很難通過采樣保證較高的重寫質量。

因此，現有重寫方法仍然面臨若干挑戰。首先，重寫順序的搜索空間與可用規則的數量成指數關系，如何高效的表示不同的重寫順序以及相互關系。其次，給定較大的搜索空間，如何在有限預算內找到最佳順序。第三，選擇一個好的重寫順序，一個直觀的想法是估計重寫(或一系列多次重寫)的降低開銷，如果重寫所減少的開銷很小，則進行相應剪枝。因此，第三個挑戰是如何估算重寫后的開銷降低。

發明內容

本發明的目的是提出一種數據庫的查詢重寫方法，針對不同的查詢語句，基于深度學習和蒙特卡洛樹搜索，以較大幅度的降低數據庫慢查詢的執行開銷。

本發明提出的數據庫數據的查詢重寫方法，利用策略樹表示任意一個查詢語句的大量等價查詢和相應的重寫順序，基于蒙特卡洛樹搜索算法在策略樹上選擇高收益的重寫順序，實現查詢開銷和重寫頻率的平衡，利用深度注意力網絡學習當前查詢與重寫規則和訪問數據的關聯關系，并利用深度學習根據查詢特征和提取的關聯關系，擬合當前查詢的整體收益，利用重寫收益估計網絡，在策略樹上利用一種最優算法選擇沒有祖先-后代關系且總收益最高的多個節點，并行擴展策略樹，以大幅提高查詢重寫效率。

本發明提出的一種數據庫的查詢重寫方法，其優點是：

本發明的數據庫的查詢重寫方法，通過合理的選擇重寫的規則和應用順序，將一條慢查詢的執行效率提升多個數量級。本方法首先利用策略樹表示任意一個查詢語句(根節點) 的大量等價查詢(非根節點)和相應的重寫順序(從根節點到非根節點的路徑)；其次，本發明基于蒙特卡洛樹搜索算法在策略樹上選擇高收益的重寫順序，實現查詢開銷和重寫頻率的平衡；為了更準確的估計重寫后查詢的整體收益(當前查詢相對于最優的目的查詢的開銷降低程度)，本發明利用深度注意力網絡學習當前查詢與重寫規則和訪問數據的關聯關系，并利用深度學習根據查詢特征(如算子開銷)和提取的關聯關系擬合當前查詢的整體收益。最后，針對具有大規模的策略樹的復雜查詢，本發明提出了一種并行節點選擇算法，在策略樹上利用一種最優算法選擇沒有祖先-后代關系且總收益最高的多個節點，并行擴展策略樹，從而大幅提高查詢重寫效率。

附圖說明

圖1為本發明方法的流程框圖。