[發明專利]分組聚集排序TopK查詢處理方法及系統

有效

• 申請號: 201310484629.3
• 申請日: 2013-10-16
• 公開（公告）號: CN103544259B
• 公開（公告）日: 2017-01-18
• 發明（設計）人: 云曉春;徐小琳;王明華;高勝;李高超;常為領;王勇;王樹鵬;張永錚
• 申請（專利權）人: 國家計算機網絡與信息安全管理中心;中國科學院信息工程研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京輕創知識產權代理有限公司11212
• 代理人: 楊立

技術領域

本發明涉及網絡技術領域，尤其涉及一種分組聚集排序TopK查詢處理方法及系統。

背景技術

根據IDC?Internet?Data?Center，互聯網數據中心)，過去五年的研究發現，全球數據量大約每兩年翻一番。2010年，全球數據量跨入ZB時代,預計到2020年全球數據量將達到令人恐怖的35ZB。隨著網民參與互聯網產品和應用的程度越來越深，互聯網將更加智能，互聯網的數據量呈爆炸式增長，大數據時代已經來臨。如此龐大的數據量給數據存儲系統帶來了極大的挑戰。傳統的單機數據存儲系統已經不可行，分布式存儲系統成為未來數據存儲發展的必然趨勢。

復雜的海量數據中蘊含著各種有價值的信息，結構化查詢語言（SQL）作為一種對數據庫中的數據進行定義和操作的語法，經常用來表達用戶對海量數據的查詢需求。

在結構化查詢語言中，分組聚集排序TopK查詢是經常被用戶使用的查詢語法，其查詢語句格式類似“select?A,sum(B)from?t?group?by?A?order?by?sum(B)top1000;”，其用來表達在數據表t中，先按照字段A的值進行分組，將相應分組內的B值求和，并按照加和后的B字段值升序排列，取先1000條。

目前，針對分組聚集排序TopK查詢，傳統的分布式數據存儲系統的實現方式如下。

首先，在分布式數據節點內將數據按照字段A的值進行內存分組，如果內存占用較大，則利用外部文件系統保存分組信息；然后，將分組后的信息壓縮傳遞到集中計算節點進行聚合函數（sum(B)）合并計算，在數據合并過程中，如果內存不足以保存整個分組信息，則利用外部文件系統創建臨時文件進行處理；最后，采用外部歸并算法進行數據排序，并取排序結果的前1000條。以上實現方法可以保證數據處理的準確性，但是數據處理效率極低，很難滿足目前用戶對復雜查詢近實時性的要求。

另外，針對分組聚集排序TopK查詢問題，其它常用的實現方法如下。

（1）充分了解用戶的查詢需求，在數據加載時通過內存概要數據結構的維護，將指定字段的特定計算方式（如按字段A分組，組內字段B求和）提前計算好，保存到數據存儲系統中，當用戶查詢請求到來時，根據概要值簡單計算后及時給與查詢響應。

（2）分布式節點將原始數據壓縮后，傳遞到集中計算節點進行統一處理。結合Frequency等高頻項處理算法，在常數空間復雜度和較低時間復雜度情況下完成數據計算，給與響應。

以上方法都存在一些缺點。如查詢效率極低、不能解決任意邏輯的聚集排序查詢、分布式環境下不適用等等。

發明內容

本發明所要解決的技術問題是提供一種分組聚集排序TopK查詢處理方法及系統，提高查詢效率。

為解決上述技術問題，本發明提出了一種分組聚集排序TopK查詢處理方法，應用于分布式數據存儲系統，包括：

步驟一，接收分組聚集排序TopK查詢請求；

步驟二，各分布式數據節點根據所述查詢請求，進行本地數據分組聚集，并將自身的分組聚集數據異步傳輸到集中處理節點；

步驟三，所述集中處理節點采用哈希表結合二叉平衡樹的數據結構對各分布式數據節點的分組聚集數據進行數據合并，并采用近似高頻項統計算法進行統計，得到聚集排序后的高頻項列表；

步驟四，輸出所述高頻項列表。

進一步地，上述分組聚集排序TopK查詢處理方法還可具有以下特點，所述步驟二包括：

初始化第一數據項隊列，第一數據項隊列為分布式數據節點的數據項隊列，所述第一數據項隊列包括第一哈希表和第一雙向鏈表，第一哈希表用于保存分組內容，第一雙向鏈表用于保存第一哈希表中分組內容對應的保存地址，并設置第一計數值，所述第一計數值為所述第一哈希表表項個數；

將存在對應分組內容的新數據項item進行組內合并，合并結果保存在所述第一哈希表中，將不存在對應分組內容的新數據項item直接保存在所述第一哈希表中；

在所述第一哈希表的表項個數達到第一計數值時以及在全部新數據項處理完畢后，將第一哈希表的數據傳輸給集中處理節點。

進一步地，上述分組聚集排序TopK查詢處理方法還可具有以下特點，所述步驟三包括：