[發明專利]基于數組存儲和向量處理的OLAP查詢處理方法

有效

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

技術領域

本發明涉及一種OLAP(聯機分析處理)查詢處理方法，尤其涉及一種基于數組存儲和向量處理的OLAP查詢處理方法，屬于數據庫管理技術領域。

背景技術

數據庫技術可以分為事務型查詢處理(on-line transaction processing，OLTP)和分析型查詢處理(on-line analytical processing，OLAP)兩種主要類型，其中，分析型查詢處理技術以采用多維存儲模型(星形模型或雪花形模型)的數據倉庫和多維分析處理OLAP為代表。

數據倉庫中存儲有海量數據，具有復雜的模式(數量眾多的維表和復雜的多維數據結構)，分析型查詢具有復雜的多表連接操作和較多的分組聚集操作，其數據存儲訪問效率和查詢處理性能是制約數據倉庫應用的關鍵問題。

當前，數據倉庫和分析型數據庫普遍采用列存儲技術以提高大數據的存儲訪問效率：列存儲一方面在表屬性較多但查詢訪問屬性較少的分析型查詢中能夠根據查詢命令只訪問查詢指定的屬性，從而提高查詢時的數據訪問I/O效率或內存帶寬效率；另一方面列存儲將相同類型的數據連續存儲，更加適合采用數據壓縮技術，提高壓縮效率。與行存儲數據庫采用的一次一條記錄的迭代查詢處理技術不同，列存儲采用一次一列的查詢處理技術，邏輯記錄的處理過程被投影到多個列上，需要通過每個列處理后所產生的物化的中間列數據(記錄的列處理輸出記錄的OID或值，如荷蘭CWI的開源內存數據庫MonetDB所采用的BAT存儲和查詢處理技術)，記錄查詢相關屬性每個列處理階段的中間結果。這種列式查詢處理技術會產生大量中間結果，增加查詢處理時的空間代價和CPU執行代價，多個屬性列上的謂詞操作也會產生額外的中間OID列間的連接操作代價，這些額外的物化和列間連接操作代價減弱甚至抵消了列存儲所帶來的存儲訪問性能收益，而且列式處理在分組聚集操作中難以使用效率較高的哈希分組聚集技術。

當前主流的列存儲分析型數據庫，如MonetDB/X100、VectorWise、Greenplum、Vertica等通常采用向量處理技術(即一次將查詢相關多個列按相同的向量長度加載到內存處理)，將列存儲轉換為動態行存儲結構，在列存儲模型上實現基于流水線(pipelining)的行式處理，消除中間結果的物化和處理代價，并且更好地與傳統的行存儲查詢處理引擎保持兼容，但這種行式流水線查詢處理技術在代碼執行效率(流水線處理一條記錄時需要流水線上完整的處理代碼)和數據傳輸效率(完整的記錄在流水線操作符間的流動)方面相對于列存儲(每列只執行相同的列處理代碼，不傳輸無關的數據)有較大的不足。因此，列存儲上的列式處理所面臨的關鍵問題是如何最小化列處理時的中間數據物化代價和最小化列間連接操作代價。

除此之外，現有的OLAP查詢處理主要涉及謂詞處理、分組和聚集計算三個過程：在謂詞處理過程中，列存儲一次一列的處理技術具有較高的性能，但當謂詞屬性較多時，多個謂詞屬性處理的中間結果需要連接操作以合并謂詞操作結果；而分組和聚集計算操作通常合二為一，將分組和聚集屬性物化為輸出記錄后統一進行分組聚集處理(排序分組聚集或哈希分組聚集)。對于聚集計算的度量屬性來說，列式處理具有更好的I/O或帶寬效率，對于不同類型的聚集函數也能獨立地支持。如聚集函數中既包含簡單的SUM、COUNT等聚集函數，也包含MEDIAN中位數等復雜的聚集函數時，統一的哈希分組聚集計算增加了其復雜性。

發明內容

本發明所要解決的技術問題在于提供一種基于數組存儲和向量處理的OLAP查詢處理方法。該方法一方面通過數組列存儲進一步優化列存儲OLAP的性能，另一方面將傳統的OLAP查詢處理技術向量化，使其更好地適合未來眾核協處理器平臺的計算特點，提高OLAP性能。

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

一種基于數組存儲和向量處理的OLAP查詢處理方法，根據數據倉庫模式中的參照完整性約束關系在數據倉庫設計底層完成數據的數組存儲，數組存儲采用數組下標作為隱式或顯式的主鍵，所述參照完整性約束關系定義的主-外鍵參照關系轉換為外鍵所在的表與主鍵所在的表之間的數組下標參照關系，使維表與事實表通過主-外鍵的參照關系直接映射為數組下標地址，使表間連接操作被虛擬物化表內部的數組地址訪問替代，將OLAP查詢簡化為謂詞處理、分組處理和聚集處理三個階段，以向量為輔助數據結構，通過列式處理完成查詢處理；其中，

在謂詞處理階段使用共享的選擇向量多趟處理多個謂詞在事實表上的選擇結果；