基于列存儲的MapReduce 并行連接算法

張 濱，樂嘉錦

(1.東華大學(xué)計算機科學(xué)與技術(shù)學(xué)院，上海 201620;2.浙江財經(jīng)大學(xué)，杭州 310018)

1 概述

隨著計算機技術(shù)和互聯(lián)網(wǎng)的急速發(fā)展，特別是隨著Web2.0 的發(fā)展，互聯(lián)網(wǎng)上的數(shù)據(jù)量高速增長，現(xiàn)有技術(shù)對大數(shù)據(jù)的處理能力越來越無法勝任。伴隨著待處理數(shù)據(jù)越來越多，當前已經(jīng)不可能將大數(shù)據(jù)存儲在一臺或有限數(shù)目的服務(wù)器內(nèi)，而且無法由數(shù)目有限的計算機來處理大數(shù)據(jù)的困境。因此，如何實現(xiàn)資源和計算能力的分布式共享以及如何應(yīng)對當前數(shù)據(jù)量高速增長的勢頭，是目前數(shù)據(jù)管理、數(shù)據(jù)處理領(lǐng)域亟待解決的問題。

本文將大數(shù)據(jù)的特點描述為:大數(shù)據(jù)具有規(guī)模大、深度大、寬度大、處理時間短、硬件系統(tǒng)普通化、軟件系統(tǒng)開源化特點。在MapReduce［1］分布式環(huán)境下，原有傳統(tǒng)的關(guān)系運算，特別是數(shù)據(jù)的連接運算，在執(zhí)行過程中產(chǎn)生大量的中間結(jié)果，從而導(dǎo)致大量的系統(tǒng)開銷，執(zhí)行效率低下。這已經(jīng)成為影響大數(shù)據(jù)分析處理的瓶頸。

針對上述問題，本文提出一種基于列存儲的MapReduce 并行連接算法，該算法在列存儲系統(tǒng)中結(jié)合基于規(guī)則及基于代價的方式優(yōu)化查詢，給出一種MapReduce 平臺上基于過濾器的多表連接算法，它能夠同時對多個關(guān)系表進行連接，避免中間結(jié)果的產(chǎn)生，還能最大程度避免不必要的元組復(fù)制與數(shù)據(jù)傳輸。

2 相關(guān)工作

2.1 列存儲技術(shù)

列存儲［2］的概念可以追溯到20 世紀70 年代，早在1976 年，加拿大統(tǒng)計局開發(fā)實現(xiàn)了列存儲數(shù)據(jù)庫管理系統(tǒng)，并在80 年代廣泛應(yīng)用。這些系統(tǒng)對傳統(tǒng)DBMS 底層存儲進行修改，對關(guān)系表進行垂直分解，然而在查詢初始時將查詢涉及的列組裝成行，使用面向行的查詢執(zhí)行引擎進行查詢執(zhí)行，其效率提高有限。隨著企業(yè)對分析型查詢需求的快速增長，對列存儲的研究在近些年得到了快速提升。Monet DB［3］和C-Store［4］是其中有影響力的代表性成果。Monet DB 由荷蘭國家數(shù)學(xué)和計算機科學(xué)研究院(CWI)研 究 開 發(fā)。C-Store 由 美 國 MIT，Yale，Brandeis 大學(xué)、Brown 大學(xué)以及UMass Boston 大學(xué)等多所大學(xué)聯(lián)合研究開發(fā)，在存儲結(jié)構(gòu)、查詢優(yōu)化、壓縮等各方面進行技術(shù)創(chuàng)新。

2.2 面向大數(shù)據(jù)處理的MapReduce 模型

2004 年，Google 研究員Dean J 和Ghemawat S 通過對網(wǎng)頁數(shù)據(jù)存儲和并行分析處理研究后，提出了MapReduce 計算模型，此后在ACM 等多個期刊上轉(zhuǎn)載。MapReduce 計算模型為大數(shù)據(jù)分析處理問題的提供了一個新的有效解決方法和途徑。

2008 年 底，Apache 的 Hadoop［5］項 目 作 為MapReduce 開源實現(xiàn)，迅速得到廣泛關(guān)注和使用。Hadoop 的HDFS(Hadoop Distributed File System)是一種專門為MapReduce 設(shè)計的大數(shù)據(jù)分布式文件系統(tǒng)，處理大數(shù)據(jù)性能優(yōu)越。

2.3 MapReduce 與數(shù)據(jù)庫技術(shù)的結(jié)合

在并行數(shù)據(jù)庫與MapReduce 模型相結(jié)合的理論研究方面，國外以耶魯大學(xué)的研究團隊在近3 年SIGMOD，VLDB 上發(fā)表了多篇關(guān)于在數(shù)據(jù)庫領(lǐng)域的列存儲的論文，2009 年、2011 年發(fā)表在VLDB 上的HadoopDB［6］研究為代表，在Hadoop 基礎(chǔ)上提出了Hadapt［7］研究，它消除數(shù)據(jù)孤島，在云環(huán)境中使用現(xiàn)有的SQL 工具，組織分析大量的“多層結(jié)構(gòu)”數(shù)據(jù)。2011 年SIGMOD 上發(fā)表了新加坡國立大學(xué)和浙江大學(xué)研究的借助列存儲技術(shù)實現(xiàn)MapReduce 框架下可擴展連接處理論文［8］。設(shè)計了Llama 這個在MapReduce 框架下的數(shù)據(jù)管理原型系統(tǒng)，在底層使用一個創(chuàng)新的文件存儲格式:CFiles。2011 年VLDB上發(fā)表了威斯康星麥迪遜大學(xué)和IBM 研究員聯(lián)合研發(fā)的基于列存儲技術(shù)的MapReduce 框架論文［9］，利用列存儲技術(shù)對MapReduce 的改進，該論文闡述了列存儲格式兼容Hadoop 復(fù)制和調(diào)度約束機制，證明列存儲格式在實際工作負載條件下能加快MapReduce 任務(wù)處理速度;其次研究如何處理列存儲遇到的復(fù)雜的數(shù)據(jù)類型。

在國內(nèi)對于大數(shù)據(jù)分析應(yīng)用以及MapReduce 與數(shù)據(jù)庫技術(shù)相結(jié)合技術(shù)研究，相對起步較晚。文獻［10］指出面對大數(shù)據(jù)深度分析的挑戰(zhàn)，關(guān)系數(shù)據(jù)庫技術(shù)的擴展性遇到了前所未有的困難。MapReduce 技術(shù)具有簡潔的模型、良好的擴展性、容錯性和并行性，高性能。關(guān)系數(shù)據(jù)庫技術(shù)和MapReduce 技術(shù)相互競爭、相互學(xué)習(xí)和相互滲透，促進了數(shù)據(jù)分析新生態(tài)系統(tǒng)的浮現(xiàn)。文獻［11］提出了基于MapReduce 的關(guān)系型數(shù)據(jù)倉庫并行查詢方法，并設(shè)計了基于MapReduce的分布式關(guān)系數(shù)據(jù)庫:ChunkDB。

綜上所述，當前列存儲系統(tǒng)在MapReduce 的分布式環(huán)境下的并行連接方向的研究還較少，對聚集運算缺少深入分析，方法也很局限，本文提出基于列存儲的MapReduce 環(huán)境下數(shù)據(jù)查詢中的并行連接算法，該算法結(jié)合分片聚集和啟發(fā)式規(guī)則對連接進行優(yōu)化，提高數(shù)據(jù)處理效率。

3 基本定義與符號

列存儲在MapReduce 分布式環(huán)境實現(xiàn)示意圖如圖1 所示。

圖1 列存儲在MapReduce 分布式環(huán)境實現(xiàn)示意圖

在MapReduce 并行計算環(huán)境下，列存儲與行存儲不同，其查詢處理的操作對象，由原來的行或者行組，轉(zhuǎn)變?yōu)榉植际酱鎯υ诿總€節(jié)點上的列或水平劃分后的列組，因此，查詢執(zhí)行投影操作轉(zhuǎn)變?yōu)槊總€節(jié)點上的列的操作，效率很高。查詢中的每個操作都相對獨立，減少重復(fù)訪問同表帶來的I/O 浪費，這也為MapReduce 框架下查詢的并行執(zhí)行提供了必要條件。在行存儲中，下推的目標對象是表，而在列存儲中，下推的目標對象具體到某個列，每個列相當于一個由(rowid，value)組成的小表。在MapReduce 分布式環(huán)境下，小表又是分隔后存儲在集群每臺機器上。因此，在列存儲的MapReduce 計算環(huán)境里，目標對象是分片小表。傳統(tǒng)的集合運算包括并、交、差、廣義笛卡爾積4 種運算。在此基礎(chǔ)上，本文給出MapReduce 并行計算環(huán)境下，列存儲系統(tǒng)的專門關(guān)系代數(shù)。

定義1 在基于列存儲的MapReduce 并行環(huán)境下，設(shè)關(guān)系R 具有k 元屬性A1，A2，…，Ak而屬性Ai，i=1，2，…，k 分割后分布存儲在m 個節(jié)點上，那么屬性Ai 的分量就可以用Ai1，Ai2，…，Aim表示。即Ai的形式定義如下:

則關(guān)系R 的形式定義如下:

定義2(rowid) 為了重組列存儲的行數(shù)據(jù)，每一列都要附加偽列rowid，形如(rowid，value)。

定義3 分布存儲分量

設(shè)關(guān)系R 具有k 元屬性，有n 個元組。將每列分量Ai，i=1，2，…，k;存在m 個節(jié)點上，則除去最后一個分量的元組數(shù)為t=n%m，其他每個分量的元組數(shù)都為t=n/m，其數(shù)據(jù)記為aji，j=1，2，…，t;令bj為aij對應(yīng)的rowid 偽列，則這些切分后的數(shù)據(jù)分量的形式定義如下:

定義4 投影

由于是列存儲，沒有實際意義投影操作，只需把所有節(jié)點的列Ai1，Ai2，…，Aim并在一起就得到所需屬性。

定義5 選擇

屬性Ai關(guān)于公式F 的選擇操作的形式定義如下:

通過σi(R)可以得到滿足公式F 對屬性Ai的所有rowid。那么關(guān)系R 關(guān)于公式F 的選擇操作形式定義為:

定義6 自然連接

設(shè)有2 個關(guān)系R 和S，R 和S 的公共屬性是A1，A2，…，Ak，那么首先要把這些屬性的分量組合起來，計算R×S，那么自然連接操作的定義為:

4 面向大數(shù)據(jù)的分布式計算模型

本節(jié)針對大數(shù)據(jù)分析處理，在MapReduce 分布式環(huán)境下，設(shè)計了基于列的分布式文件存儲格式，數(shù)據(jù)的分布式加載以及利用協(xié)同定位方法對數(shù)據(jù)存儲進行優(yōu)化。

4.1 MCF 存儲格式

針對MapReduce 分布式計算環(huán)境，本文在底層設(shè)計了一個新的文件存儲格式MCF(MapReduce Column-store File)，即基于MapReduce 的分布式列存儲格式，其示意圖如圖2 所示。對于Facebook 設(shè)計的Hive［12］文件存儲格式RCFile［13］，它采用行存儲，每個關(guān)系模式按照行組，存儲在RCFile 中，而本文提出MCF 采用列存儲，避免提取關(guān)系表中的無關(guān)屬性，相對RCFile，其大數(shù)據(jù)查詢效率提高明顯。

在MCF 中，每一列都附加一個偽列rowid，每個塊包含固定數(shù)量的記錄，稱為M 值。因為屬性類型大小是可變的，每個邏輯塊的多少n 不同。塊存儲在緩沖區(qū)。緩沖區(qū)的大小通常為1 MB。當緩沖區(qū)大小超出閾值或緩沖區(qū)中的記錄數(shù)達到m 個，緩沖區(qū)刷新到HDFS 中。每塊的起始偏移量被記錄下來。使用MCPage 代表在文件系統(tǒng)的分區(qū)單位。在文獻［15］中指出HDFS(Hadoop 分布式文件系統(tǒng))中，每個輸入的數(shù)據(jù)文件將切成塊(HDFS Block)，MCPage 存儲在HDFS Block 中，從而MCPage 在不同的數(shù)據(jù)節(jié)點復(fù)制。在HDFS，默認MCPage 大小為64 MB。MCPage 包含多個數(shù)據(jù)塊，由記錄m 的值和每個記錄的大小確定。

MCF 在表掃描通過避免沒必要列值讀取來優(yōu)化讀取，它在分布式集群環(huán)境下優(yōu)于按行存儲結(jié)構(gòu)。同時，MCF 是基于列存儲的壓縮，因此，有很高的空間利用率。

4.2 數(shù)據(jù)分布式加載

本文提出按照MCF 文件格式，將數(shù)據(jù)通過分片方法構(gòu)造分布存儲分量A'ij，從而分別導(dǎo)入到每個MCPage 的數(shù)據(jù)塊中。

在HDFS 中默認splitSize 等于HDFS blockSize的默認值(64 MB)。而InputSplit 是MapReduce 對文件進行處理和運算的輸入單位，只是一個邏輯概念，每個InputSplit 并沒有對文件實際的切割，只是記錄了要處理的數(shù)據(jù)的位置和長度。

如果按照默認的順序數(shù)據(jù)加載方法，必然存在一行記錄被劃分到不同的Block，甚至不同的DataNode。根據(jù)定義3，通過分析FileInputFormat 里面的getSplits 方法，某一行記錄同樣也可能被劃分到不同的InputSplit。對輸入的文檔進行預(yù)處理，讀取前N 行做為一個splits，通過重寫FileSplit，定義一個split 的大小是1 KB 個字節(jié)，這樣就可以將輸入的文檔進行分片。最終實現(xiàn)A'ij的構(gòu)造。

4.3 協(xié)同定位優(yōu)化策略

本文提出數(shù)據(jù)存儲的協(xié)同定位策略，其示意圖如圖3 所示。對于那些數(shù)據(jù)量非常龐大的事實表，如lineorder 表，往往跨越許多的HDFS 塊，通常在每個節(jié)點上分割存儲，不做復(fù)制，而對于數(shù)據(jù)量相對較小的維表，如supplier，customer，part，date 表，協(xié)同定位優(yōu)化策略將其在每個節(jié)點都復(fù)制一份，使得可以分布連接和聚集運算直接在本機運算即可，因此，大大減少了節(jié)點之間網(wǎng)絡(luò)傳送次數(shù)和時間，提高了4.1 節(jié)分布聚集效率，查詢性能優(yōu)化明顯。

圖3 協(xié)同定位優(yōu)化策略示意圖

5 基于列存儲的MapReduce 并行連接算法

本節(jié)對與基于列存儲的MapReduce 并行連接算法從分片聚集和子連接的啟發(fā)式優(yōu)化2 個方面，闡述了算法的具體實現(xiàn)。

5.1 分片聚集方法

基于列存儲的MapReduce 并行連接算法，其示意圖如圖4 所示。為了充分調(diào)用集群所有機器的計算資源，實現(xiàn)數(shù)據(jù)的并行連接，在查詢計劃執(zhí)行的Map 階段，本文提出分片聚集方法。

圖4 并行連接查詢計劃示意圖

(1)抽取:按照定義6 并行連接操作，在集群中的多個機器上分別執(zhí)行完之后，得到子連接結(jié)果，傳給分片聚集階段。

(2)分片聚集:在這個階段，對每個子連接結(jié)果計算聚集。從而利用分片方法來減少數(shù)據(jù)量。提高并行計算能力。而且在多查詢?nèi)蝿?wù)時，分片聚集結(jié)果還可以重用。

(3)分布:對前階段的結(jié)果，按照查詢語句的分組條件，被重分配到各個分組中。這使所有具有相同的查詢字符串的結(jié)果分配到到同一個Map 任務(wù)。從而完成GROUP BY 字句要求的對查詢結(jié)果進行分組實現(xiàn)。

(4)全聚集:每個分區(qū)即每個Map 任務(wù)，通過合并計算具有相同的查詢字符串的查詢結(jié)果，從而得到最終聚集結(jié)果。例如:得到count (*)結(jié)果。

(5)過濾:通過過濾掉HAVING 字句中的組條件，例如:count(*)＞50，計數(shù)小于50 的將不會傳入Reduce 階段。

(6)排序:調(diào)用hadoop 的排序算法，本文使用TeraSort 算法，對剩余的結(jié)果按照ORDER BY 字句的要求分別并行排序。

(7)合并:每個Reducer 進行合并操作對所有分區(qū)排序的結(jié)果的合并在一起，輸出最終結(jié)果。

(8)輸出:最終的結(jié)果是輸出為MCF 文件。

5.2 子連接的啟發(fā)式優(yōu)化方法

在并行連接過程中，對于每個節(jié)點本地執(zhí)行的連接任務(wù)，本文利用前期研究成果［14］:啟發(fā)式優(yōu)先方法對關(guān)系運算進行優(yōu)化。

本文啟發(fā)式優(yōu)化的基本思想是:首先執(zhí)行最具限制性的選擇和連接操作。具體優(yōu)化策略為:盡可能早地執(zhí)行選擇操作;盡可能早地執(zhí)行投影操作;同列謂詞的下推能盡早減少所需處理的元組數(shù)目。而由于同表列的rowid 唯一且一致，優(yōu)先執(zhí)行同表列的連接能有效減少中間結(jié)果的規(guī)模，因此Map 階段產(chǎn)生的中間結(jié)果之和較小的計劃一般是最優(yōu)的。基于啟發(fā)式優(yōu)化的查詢計劃示意圖如圖5 所示。

圖5 基于啟發(fā)式優(yōu)化的查詢計劃示意圖

6 實驗驗證

本文實驗采用課題組開發(fā)的基于列存儲的MapReduce 大數(shù)據(jù)并行處理原型系統(tǒng) HCMS(Hadoop Column-store Management System)為算法測試平臺，采用國際通用的SSB 測試數(shù)據(jù)集，對算法進行測試，從而驗證其高效性和可擴展性。

6.1 實驗環(huán)境

本文系統(tǒng)驗證要求與原有單機環(huán)境不同，對計算機數(shù)量有更高要求。實驗系統(tǒng)運行在課題組實驗室選取的50 臺普通計算機組成測試集群，每個節(jié)點:4 核CPU，4 GB 主存，1 塊500 GB SATA 硬盤，每臺機器的操作系統(tǒng)都是Redhat Linux 6.1。網(wǎng)絡(luò)環(huán)境為1 GB 以太網(wǎng)交換機組成的局域網(wǎng)。本文實驗使用的軟件，如表1 所示。其中，DBMS3.0 為課題組前期列存儲數(shù)據(jù)庫研究成果。

表1 實驗軟件環(huán)境

實驗規(guī)劃每個Datanode 分配6 個map 任務(wù)和2 個reducer 任務(wù)。HDFS 數(shù)據(jù)塊大小設(shè)置為256 MB，MapReduce 查詢執(zhí)行器使用全局內(nèi)存大小設(shè)置為1 GB。

測試節(jié)點從10 個節(jié)點開始增加到50 個，記錄每個測試數(shù)據(jù)集合和測試查詢語句執(zhí)行時間和日志。每次測試完后，需要對集群HDFS 重新格式化。

6.2 測試數(shù)據(jù)集

實驗采用國際通用的星型模式基準SSB［15］中定義的測試數(shù)據(jù)集進行大數(shù)據(jù)處理的實驗驗證，生成的星型模式下的真實數(shù)據(jù)集和基于MapReduce 的大數(shù)據(jù)并行處理原型系統(tǒng)考慮的大數(shù)據(jù)測試目標相吻合。

實驗將用SSB 提供的數(shù)據(jù)產(chǎn)生器DBgen 生成了SSB 的數(shù)據(jù)集實例。每個實例數(shù)據(jù)集的大小是用增量因子控制的，記為SF，選用SF=1，數(shù)據(jù)集大小為1 GB，初始lineorder 表數(shù)據(jù)量為6 000 000 行，如表2 所示。實驗逐步增加SF，生成數(shù)據(jù)集從10 GB，100 GB 到1 TB。分別記錄每次測試結(jié)果。

表2 實驗測試數(shù)據(jù)

6.3 實驗結(jié)果與分析

實驗1 各個測試語句性能對比

選取SSB 的連接語句測試Q1.1，簡單聚集任務(wù)測試Q2.1 以及復(fù)雜聚集任務(wù)測試Q3.1 和Q4.1 作為基礎(chǔ)測試語句，在全部節(jié)點都啟用的條件下，通過對100 GB 數(shù)據(jù)分別測試10 次，計算平均值，其結(jié)果如圖6 所示。

圖6 各個測試語句性能對比圖

由于采用了分片聚集算法，在聚集任務(wù)Q3.1 和Q4.1，特別是復(fù)雜聚集任務(wù)，本文算法優(yōu)化明顯。

實驗2 數(shù)據(jù)量變化下性能對比

選取SSB 的Q2.2 作為基礎(chǔ)測試語句，在全部節(jié)點都啟用的條件下，通過對10 GB，100 GB 和1 TB數(shù)據(jù)分別測試10 次，計算平均值，其性能對比圖如圖7所示。測試系統(tǒng)，在大數(shù)據(jù)條件下的運行負載能力。從圖7 中可看出，當數(shù)據(jù)量增加時，DWMS 執(zhí)行時間增長明顯，而Hive 和HCMS 則較平緩，充分驗證了并行執(zhí)行的優(yōu)越性。當負載增大到1 TB 時，HCMS性能比Hive 提高26.2%，由此充分驗證了同時使用MCF 列存儲結(jié)構(gòu)和分片聚集能更大提升并行連接的有效性，使得查詢效率更高。

圖7 數(shù)據(jù)量變化下性能對比

實驗3 集群數(shù)量變化下性能對比

選取SSB 的Q2.2 作為基礎(chǔ)測試語句，選擇100 GB數(shù)據(jù)，通過對集群Datanode 節(jié)點數(shù)從10 個、20 個、30 個、40 個，增加到50 個，重新格式化后，分別測試10 次，計算平均值，其性能對比如圖8 所示。列存儲數(shù)據(jù)倉庫管理系統(tǒng)DWMS 不是并行分布式系統(tǒng)，本次測試實驗中未使用。

圖8 集群數(shù)量變化下性能對比

由圖8 可以看出，隨著運算節(jié)點數(shù)目的增加，HCMS 比Hive 執(zhí)行時間不斷減少，從10 個節(jié)點的相差15.8%，減少到50 個節(jié)點的26.3%。從而驗證了算法性能優(yōu)化明顯。另一方面也證實了算法的可擴展性。

7 結(jié)束語

基于列存儲的MapReduce 并行連接算法分析了MapReduce 并行環(huán)境列存儲連接與單機環(huán)境列存儲的區(qū)別，根據(jù)面向大數(shù)據(jù)的分布式計算模型“大而化小，分而治之”的設(shè)計思路，從而為大數(shù)據(jù)查詢分析處理提供了有效的解決方案。本文算法在面向大數(shù)據(jù)的分布式計算模型基礎(chǔ)上，利用協(xié)同定位實現(xiàn)存儲優(yōu)化。從分片聚集和子連接啟發(fā)式優(yōu)化2 個方面構(gòu)造了并行連接算法的具體實現(xiàn)。實驗結(jié)果證明，該算法有效地減少了MapReduce 過程的中間數(shù)據(jù)和不必要的I/O 開銷。此外，由于利用了模型的可擴展性特點，無論在執(zhí)行時間還是負載能力上，都有較好的性能表現(xiàn)，明顯提高了大數(shù)據(jù)運算的效率。下一步的工作重點將轉(zhuǎn)向列存儲的MapReduce 連接索引技術(shù)的研究，對適用于列存儲的MapReduce 各種索引進行分析，使MapReduce 大數(shù)據(jù)查詢性能得到進一步的優(yōu)化。

［1］Dean J，Ghemawat S.MapReduce:Simplified Data Processing on Large Clusters［C］//Proc.of OSDI'04.San Francisco:［s.n.］，2004:137-150.

［2］Abadi D J，Madden S R，Hachem N.Column-stores vs.Row-stores:How Different Are They Really?［C］//Proc.of ACM SIGMOD'08.Vancouver，Canada:ACM Press，2008:967-980.

［3］Stonebraker M，Abadi D J，Batkin A，et al.C-store:A Column-oriented DBMS ［C］//Proc.of VLDB Conference.Trondheim，Norway:［s.n.］，2005:553-564.

［4］Boncz P，Zukowski M，Nes N.MonetDB/X100:Hyperpipelining Query Execution［C］//Proc.of CIDR'05.Asilomar，USA:ACM Press，2005:251-264.

［5］Blanas S，Patel J M，Ercegovac V，et al.A Comparison of Join Algorithms for Log Processing in MapReduce［C］//Proc.of ACM SIGMOD International Conference on Management of Data.Indianapolis，USA:ACM Press，2010:975-986.

［6］Abouzeid A，Bajda-Pawlikowski K，Abadi D J，et al.HadoopDB:An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads［C］//Proc.of VLDB Conference.Lyon，F(xiàn)rance:［s.n.］，2009:922-933.

［7］Bajda-Pawlikowski K，Abadi D J，Silberschatz A，et al.Efficient Processing of Data Warehousing Queries［C］//Proc.of ACM SIGMOD International Conference on Management of Data.Athens，Greece:ACM Press，2011:1165-1176.

［8］Lin Yuting，Agrawal D，Chen Chun，et al.Llama:Leveraging Columnar Storage for Scalable Join Processing in the MapReduce Framework［C］//Proc.of ACM SIGMOD International Conference on Management of Data.Athens，Greece:ACM Press，2011:961-972.

［9］Floratou A，Patel J M，Shekita E J.Column-oriented Storage Techniques for MapReduce.The VLDB Journal，2011，4(7):419-429.

［10］覃雄派，王會舉，杜小勇，等.大數(shù)據(jù)分析——RDBMS與MapReduce 的競爭與共生［J］.軟件學(xué)報，2012，23(1):32-45.

［11］師金鋼，鮑玉斌，冷芳玲，等.基于MapReduce 的關(guān)系型數(shù)據(jù)倉庫并行查詢［J］.東北大學(xué)學(xué)報:自然科學(xué)版，2011，32(5):626-629.

［12］Thusoo A，Sarma J S，Jain N，et al.Hive——A Warehousing Solution over a Map-reduce Framework［C］//Proc.of VLDB Conference.Lyon，F(xiàn)rance:［s.n.］，2009:1626-1629.

［13］He Yongqiang，Lee R，Yin Huai，et al.RCFile:A Fast and Space-efficient Data Placement Structure in MapReducebased Warehouse Systems［C］//Proc.of International Conference on Data Engineering.Hannover，Germany:IEEE Press，2011:1199-1208.

［14］嚴秋玲，孫 莉，王 梅，等.列存儲數(shù)據(jù)倉庫中啟發(fā)式查詢優(yōu)化機制［J］.計算機學(xué)報，2011，10(34):2018-2026.

［15］O'Neil P，O' Neil B，Chen Xuedong.Star Schema Benchmark Revision3［EB/OL］.(2010-02-09).http://www.cs.umb.edu/～poneil.