[發明專利]列存儲數據庫中基于多維數組的分組聚集計算方法

有效

• 申請號: 201310263880.7
• 申請日: 2013-06-27
• 公開（公告）號: CN103294831A
• 公開（公告）日: 2013-09-11
• 發明（設計）人: 張延松;張宇;王珊
• 申請（專利權）人: 中國人民大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京汲智翼成知識產權代理事務所(普通合伙) 11381
• 代理人: 陳曦

技術領域

本發明涉及一種數據庫分組聚集計算方法，尤其涉及一種針對多核處理器和/或眾核協處理器平臺的技術特點，在列存儲數據庫中基于多維數組的分組聚集計算方法，屬于數據庫管理技術領域。

背景技術

OLAP（聯機分析處理）是數據庫系統最主要的一種應用，提高OLAP查詢處理的性能是數據庫領域的關鍵性研究問題之一。OLAP查詢處理中通常都會包含多表連接和分組聚集計算，提高這些操作的性能是提高OLAP響應速度的關鍵。當前，隨著數據量的迅速增長和分析型查詢處理需求的不斷提高，以及多核處理器和眾核協處理器平臺（例如通用GPU或英特爾至強融核^TM協處理器等）的并行計算需求，大數據分組聚集計算日益成為新的性能瓶頸。提高分組聚集操作的性能和效率成為一個重要的研究課題。

在現有的數據庫技術中，分組聚集計算主要采用兩種實現方案：一是對輸出記錄按分組屬性排序，然后在順序掃描記錄時將相同分組屬性值的記錄對應的聚集屬性值進行聚集處理（如sum對應累加操作）；二是采用哈希分組聚集處理，用分組屬性構造哈希分組聚集表，每個哈希入口（哈希桶）相當于一個聚集器（如sum對應的累加器），每一個輸出記錄通過分組屬性值的哈希探測找到其對應的哈希桶，并將聚集計算屬性值推到哈希桶中進行聚集計算。在基于排序的分組聚集計算方案中，排序操作的代價較大。在分組聚集的記錄集較大時，需要O（n*log₂n）的排序代價和O（n）的記錄掃描代價。在基于哈希表的分組聚集計算方案中，執行代價包括哈希探測的代價和聚集計算的代價。當分組屬性為高勢集時，即分組數量較大時，分組聚集哈希表需要較大的內存空間（哈希表需要相對原始數據較大的內存空間以使數據盡量分散，保證哈希探測的O（1）性能）。而當采用多核并行處理技術時，每個處理線程需要維護一個私有的哈希分組聚集表，而較大的哈希分組聚集表導致緩存缺失（cache?miss）增加，并行處理性能下降。對于復雜的分組聚集函數，如中位數、百分位、top?k、rank等函數涉及計算代價更高的處理過程，當聚集計算屬性增多時，分組聚集計算的代價會不斷增長。特別是在現有的分析查詢中，聚集計算的數量越來越多，逐漸成為計算代價較大的操作符。

另一方面，目前越來越多的分析型數據庫采用列存儲，但基于哈希表的分組聚集操作需要將查詢相關的列物化為行記錄后才能進行分組聚集計算。這種先物化策略不利用發揮列存儲一次一列的訪問效率，因此需要在列存儲數據庫中提供基于列存儲的分組聚集操作。對于多核處理器和眾核協處理器平臺而言，sum、count、average等聚集函數可以轉換為并行處理過程，由各線程獨立完成各自數據子集上的聚集計算，并通過全局聚集結果歸并得到最終的聚集結果。這種并行的分組聚集計算需要將哈希分組聚集表最小化以減少多核處理器共享緩存中的數據訪問沖突，因此需要比哈希表存儲效率更高的分組聚集數據結構。對于眾核處理器而言，向量結構比內存哈希表結構更加適合眾核處理器的高并行計算模式，因此需要將以內存哈希表為基礎的分組聚集處理技術向更加輕量化、向量化的分組聚集處理技術過渡，以更好地適應當前多核處理器和眾核協處理器平臺的需要，提高大數據分組聚集計算的性能。

發明內容

本發明所要解決的技術問題在于提供一種列存儲數據庫中基于多維數組的分組聚集計算方法。該方法降低了哈希表的存儲空間開銷和哈希探測的CPU代價，尤其適合多核處理器和眾核協處理器平臺使用。

為實現上述的發明目的，本發明采用下述的技術方案：

一種列存儲數據庫中基于多維數組的分組聚集計算方法，包括如下步驟：

在分組聚集計算過程中，將哈希表分解為多個同構的多維數組，每個多維數組對應一個聚集計算表達式，每個數組單元表示一個多維分組向量；

將查詢的星形連接過程輸出記錄的多個分組屬性映射為對應的多維數組各維上的下標，并轉換為一維數組下標；

為查詢生成連接向量，記錄每一個滿足連接條件記錄的ID和分組屬性對應的一維數組下標值；

在聚集計算過程中，各個聚集計算表達式根據連接向量獨立進行聚集計算，在掃描連接向量時根據記錄的ID直接訪問聚集計算表達式對應的度量屬性值，按照連接向量中分組屬性映射的一維數組下標將聚集屬性計算結果送至對應的多維數組單元中進行聚集計算。

其中較優地，對分組屬性進行編碼并映射為多維數組，輸出記錄根據分組編碼可以直接映射到多維數組指定的數組單元中。