[發明專利]一種基于超圖和動態規劃的大數據實時查詢優化方法

有效

• 申請號: 201310716665.8
• 申請日: 2013-12-16
• 公開（公告）號: CN103793467B
• 公開（公告）日: 2017-01-25
• 發明（設計）人: 陳嶺;周強;吳勇;閻孝文
• 申請（專利權）人: 浙江鴻程計算機系統有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及大數據實時查詢技術領域，尤其涉及一種基于超圖和動態計劃的大數據實時查詢優化方法。?

背景技術

大數據實時查詢是重要的大數據技術，現有的大數據查詢系統有Google?Dremel、Cloudera?Impala、Berkeley?Shark、Apache?Drill等。大數據實時查詢一般采用分布式計算架構，由于弱化了對事務等功能的支持，所以相對于關系型數據庫集群具有更高的可擴展性。同時由于大數據實時查詢能很好的滿足實時查詢的用戶需求，因此其在互聯網、智慧城市等領域有廣闊的應用空間。?

查詢優化是數據庫管理系統的重要組成部分，查詢優化方法一般由代價模型和優化方法兩部分組成。一般的代價模型需要考慮I/O、數據傳輸代價及具體連接算法運行特性等因素，但實際的查詢優化中為了簡化模型的構建通常只是考慮單個因素，現有的代價模型如對Hive查詢性能進行優化工作時采用的基于連接結果和最小化的代價模型，其能夠很好的應用于Hive數據倉庫并一定程度的優化其查詢效率。但是其只考慮連接中間結果讀寫產生的I/O代價這一因素，因此存在很大的系統局限性，這樣便很難保證產生高效的執行計劃，從而影響查詢的實時響應能力。?

現有的優化方法可以分為兩類：一類是獲得最優查詢計劃的方法；如基于記憶的優化方法及基于動態計劃的優化方法。基于記憶的優化方法，其工作原理是以一種自頂向下的方式生成計劃，如自頂向下分區搜索方法，該方法的核心是利用最小割集以一種自頂向下的形式生成連通子圖，由于在枚舉過程中結合了一些搜索策略如分支限界進行剪枝，故其算法的執行效率有很大程度的提升。但是其只能處理簡單的二值連接謂詞及內連接，而不能處理外連接以及反連接。基于動態計劃的優化方法，由于能夠有效的處理復雜的連接謂詞，所以能解決自頂向下優化方法存在的問題，但是一般動態計劃方法存在搜索空間會隨著關系數的增加而指數增長的問題。?

另一類是獲得次優查詢計劃的方法，如基于遺傳算法的優化方法。基于遺傳算法的方法，其工作原理是從一組隨機產生的種群開始搜索，種群中的每個個體都是問題的一個解，其根據適應值的大小選擇部分后代同時淘汰部分后代，算法不斷迭代直到收斂，該方法雖然較高效，但找到的解一般是次優解，同時存在過早收斂等問題。?

發明內容

本發明為克服上述的不足之處，目的在于提供一種基于超圖和動態計劃的大數據實時查詢優化方法，通過采用基于最佳代價的連接順序優化方法來提升查詢效率，在大數據環境下滿足用戶的實時查詢需求。?

本發明是通過以下技術方案達到上述目的：?

1、一種基于超圖和動態計劃的大數據實時查詢優化方法，包括最佳代價模型構建過程和執行計劃空間搜索過程，最佳代價模型構建兩過程包括以下步驟：?

1)分析元數據服務器中表數據，構建生成細粒度的列級統計信息直方圖，并將其存儲在元數據服務器中；?

2)利用統計信息，構建相應最佳的代價模型供生成計劃時使用。?

執行計劃空間搜索過程包括以下步驟：?

1)解析數據庫查詢語句，將結果保存于查詢超圖G＝(V，E)數據結構中，查詢超圖G＝(V，E)滿足兩個條件：第一，V是一個非空的頂點集，即所有參與連接的關系的集合；第二，E是一組超邊集合，即代表關系間連接操作的集合，其中超邊是一個無序對(u，v)，u和v是屬于頂點集V的非空子集，并且

2)為單個關系初始化設置執行計劃，將其保存在相應動態計劃表中，其它元素值全部置為

3)定義好計算枚舉策略：每個連通子圖及連通補集對只被生成一次；?

4)通過計算領域以枚舉連通子圖；?

5)為每個連通子圖找到合適的連通補集；?

6)為每對連通子圖和連通補集構成的執行計劃計算其代價，依照代價模型更新其相應執行計劃；?

7)重復執行步驟4)——步驟7)，直到整個左線性樹構成的執行計劃空間搜索完畢，生成執行計劃樹。?

本發明的有益效果在于：?

1)針對執行計劃搜索空間過大的問題，構建滿足左線性樹的搜索策略，大大降低了搜索的空間，提升了基于超圖和動態計劃算法運行的效率；?

2)構建滿足大數據環境的最佳代價模型，綜合考慮了大數據環境下傳輸代價及哈希連接算法運行特性等因素，確保了優化方法生成的計劃是最佳的。?

附圖說明

圖1：基于超圖和動態計劃的大數據實時查詢優化方法查詢優化總體流程圖；?

圖2：連通子圖枚舉流程圖；?

圖3：執行計劃生成流程圖。?