[發明專利]一種內存-閃存混合存儲模式下的OLAP查詢優化方法

有效

• 申請號: 201410717830.6
• 申請日: 2014-12-01
• 公開（公告）號: CN104361113A
• 公開（公告）日: 2015-02-18
• 發明（設計）人: 張延松;張宇;王珊
• 申請（專利權）人: 中國人民大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F3/06
• 代理公司: 北京紀凱知識產權代理有限公司 11245
• 代理人: 徐寧;孫楠

1.一種內存-閃存混合存儲模式下的OLAP查詢優化方法，其包括以下步驟：

1)OLAP存儲采用flash-aware的存儲模型，即根據OLAP星形或雪花形模型中維表較小、謂詞操作較多的特點和事實表由外鍵和度量屬性組成的特點，在相對較小的DRAM和相對較大flash存儲之間按數據訪問的局部性進行劃分，在異構的兩級內存上進行存儲優化；

2)內存OLAP采用數組存儲，每個屬性列存儲于連續的數組單元中，表由相同長度的各屬性數組組成，維表使用數組下標作為主鍵，事實表外鍵為維表中相應記錄的數據下標，事實表記錄能夠根據外鍵值直接定位維表中對應的數組單元，將傳統的連接操作簡化為數組下標訪問，進行AIR算法的OLAP查詢處理；其中AIR為數組下標訪問；

3)將基于數組存儲和AIR算法的OLAP查詢處理分解為三個順序的數據訪問過程：維表訪問、事實表外鍵訪問和事實表度量屬性訪問，三個階段產生的中間數據結構包括：維表過濾分組向量、選擇向量和分組向量、分組多維數組；維表過濾分組向量、選擇向量和分組向量為各個查詢共用的數據結構，不同的查詢只需要更新向量的內容，分組多維數組根據查詢的不同而動態生成；

4)采用在基于關鍵字的位圖連接索引的基礎上在DRAM-flash兩級存儲中優化存儲K個關鍵字連接位圖，從中選擇n個高頻訪問關系字并將相應的位圖存儲于DRAM，其余的位圖存儲于flash，形成二級連接位圖索引結構。

2.如權利要求1所述的一種內存-閃存混合存儲模式下的OLAP查詢優化方法，其特征在于：所述步驟1)中，采用內存存儲引擎，維表駐留DRAM；事實表中的外鍵是多維分析中星形連接時訪問頻度較高的列，同樣駐留在DRAM中；事實表的度量屬性存儲于flash中，并提供度量列上按位置訪問API支持度量列的隨機訪問。

3.如權利要求1所述的一種內存-閃存混合存儲模式下的OLAP查詢優化方法，其特征在于：所述步驟3)中，維表過濾分組向量、選擇向量和分組向量、分組多維數組存儲于DRAM中；事實表度量屬性存儲于flash中。

4.如權利要求2所述的一種內存-閃存混合存儲模式下的OLAP查詢優化方法，其特征在于：所述步驟3)中，維表過濾分組向量、選擇向量和分組向量、分組多維數組存儲于DRAM中；事實表度量屬性存儲于flash中。

5.如權利要求1或2或3或4所述的一種內存-閃存混合存儲模式下的OLAP查詢優化方法，其特征在于：所述步驟2)中，所述AIR算法的OLAP查詢處理包括以下步驟：

①將OLAP查詢分解為維表上的分組過濾操作：將查詢中的選擇和分組操作按維表進行劃分，將查詢分解為在各個維表上的子查詢；

②生成維表過濾分組向量：每個維表根據各自的where子句對記錄進行過濾并投影出滿足選擇條件的分組屬性，滿足選擇條件的分組屬性進行字典表壓縮，字典表存儲于數組中，字典壓縮碼為字典數組下標，在過濾分組屬性中選擇條件為false的位置置為-1，否則置為分組壓縮編碼，并記錄在與維表等長的過濾分組向量中；

③事實表外鍵多趟掃描創建選擇和分組向量：按維表過濾分組向量選擇率由低到高的順序依次掃描事實表對應的外鍵列，每列掃描時按外鍵值映射到相應維表過濾分組向量指定的位置，向量值非負時將當前事實表記錄位置插入選擇向量；下一個外鍵列掃描時按照當前選擇向量中的記錄位置采用隨機訪問方式，并通過相應維表過濾分組向量更新選擇向量，刪除不滿足后續外鍵映射條件的事實表記錄位置；當各外鍵列掃描結束后，選擇向量記錄了事實表中滿足全部連接條件的記錄位置；當總選擇率較高時，在更新選擇向量的同時更新分組向量，用維表過濾分組向量中當前分組的下標增量地計算分組多維數組下標；當總選擇率很低時，首先生成選擇向量，最后按選擇向量的位置隨機訪問各外鍵列，一次性生成分組向量；

④通過選擇向量訪問flash存儲度量列指定度量值：根據選擇向量中的位置訪問flash存儲上的度量屬性值；根據選擇向量在flash上的隨機訪問采用多核并行執行；

⑤通過分組向量將度量值在分組多維數組中聚集：按照分組向量所記錄的分組下標，將從flash存儲上返回的度量屬性值“推”到分組向量中下標值指示的分組多維數組單元中進行聚集計算，完成全部的OLAP查詢處理；

⑥將分組多維數組的各維反向映射到分組字典表中獲得分組屬性值并輸出查詢結果。