基于代價估計的Hive多維索引分割策略選擇算法

劉　越　李錦濤　虎嵩林

1(中國科學(xué)院計算技術(shù)研究所　北京　100190)2(中國科學(xué)院大學(xué)　北京　100049)3(中國科學(xué)院信息工程研究所　北京　100093)(liuyue01@ict.ac.cn)

基于代價估計的Hive多維索引分割策略選擇算法

劉越1,2李錦濤1虎嵩林3

1(中國科學(xué)院計算技術(shù)研究所北京100190)2(中國科學(xué)院大學(xué)北京100049)3(中國科學(xué)院信息工程研究所北京100093)(liuyue01@ict.ac.cn)

摘要在能源互聯(lián)網(wǎng)、智慧城市等新興領(lǐng)域，智能終端采集的龐大數(shù)據(jù)往往需要多維分析，傳統(tǒng)企業(yè)尋求借助互聯(lián)網(wǎng)技術(shù)(如Hadoop和Hive)應(yīng)對大數(shù)據(jù)問題.但是Hive當(dāng)前的多維索引能力較弱，無法滿足傳統(tǒng)企業(yè)的需求.針對這一問題，提出了一種基于分布式網(wǎng)格文件的多維索引技術(shù)——DGFIndex，來提升Hive的多維查詢處理能力.但是在創(chuàng)建DGFIndex時，需要用戶指定各個索引維度的分割粒度，而分割粒度的大小與查詢性能息息相關(guān).在用戶對數(shù)據(jù)與查詢特征不熟悉時，很難選擇較優(yōu)的分割策略.為了解決這一問題，通過建立新的MapReduce代價模型，并使用兩階段模擬退火算法為DGFIndex搜索較優(yōu)的分割策略，從而提升查詢性能，減少查詢集合的總耗時.實驗結(jié)果表明:DGFIndex可以提升Hive多維查詢性能50%～114%，對于固定的查詢集合，與人工選定分割策略比較，基于代價估計的分割策略選擇算法可以為DGFIndex快速選定較優(yōu)的分割策略，并可以使整個查詢集合的處理時間比人工方法最多減少30%.

關(guān)鍵詞Hive；MapReduce；多維索引；代價模型；模擬退火

隨著能源互聯(lián)網(wǎng)、智慧城市等領(lǐng)域技術(shù)的發(fā)展，傳統(tǒng)企業(yè)，如電力、通信、金融、制造等行業(yè)，需要處理的數(shù)據(jù)呈現(xiàn)爆炸式增長，以往依靠傳統(tǒng)商業(yè)關(guān)系型數(shù)據(jù)庫的解決方案遇到了瓶頸，其寫入吞吐、橫向擴展性與大數(shù)據(jù)分析能力都無法滿足日益增長的數(shù)據(jù)存儲與分析需求.因此，傳統(tǒng)企業(yè)都在尋找應(yīng)對大數(shù)據(jù)挑戰(zhàn)的替代方案.而互聯(lián)網(wǎng)領(lǐng)域已經(jīng)出現(xiàn)了大量的大數(shù)據(jù)處理系統(tǒng)，如Hadoop,Spark[1],Storm等，但是由于互聯(lián)網(wǎng)應(yīng)用與傳統(tǒng)企業(yè)應(yīng)用各具特點，因此在將互聯(lián)網(wǎng)技術(shù)應(yīng)用于傳統(tǒng)企業(yè)時會遇到諸多挑戰(zhàn)[2-4].例如，傳統(tǒng)企業(yè)往往需要對龐大的采集類數(shù)據(jù)進(jìn)行快速的在線分析與離線批量計算，在這些計算邏輯中包含大量的多維查詢[3]，但是現(xiàn)有互聯(lián)網(wǎng)領(lǐng)域的數(shù)據(jù)處理系統(tǒng)索引能力有限，無法滿足需求.

具備靈活可擴展性、高可用性、良好容錯性與低成本等優(yōu)點的Hadoop已成為海量數(shù)據(jù)存儲與分析的首選方案之一.而Hadoop之上的數(shù)據(jù)倉庫工具Hive[5]為用戶提供了類SQL查詢語言HiveQL，這使傳統(tǒng)企業(yè)的數(shù)據(jù)分析人員可以平滑地過渡到基于Hadoop的數(shù)據(jù)平臺上.但是傳統(tǒng)企業(yè)的數(shù)據(jù)分析邏輯包含大量的多維查詢與統(tǒng)計值分析，而Hive只支持有限的索引技術(shù)，如Compact Index等，這些索引數(shù)據(jù)過濾粒度較大，會造成過多的冗余數(shù)據(jù)讀取，查詢性能較低.為此，我們提出了一種基于分布式網(wǎng)格文件的多維索引技術(shù)——DGFIndex(distributed grid file index)[3].DGFIndex使用網(wǎng)格文件將數(shù)據(jù)空間分為很多小單元，通過小單元坐標(biāo)與對應(yīng)數(shù)據(jù)片位置的映射關(guān)系達(dá)到細(xì)粒度索引的目的.

在創(chuàng)建DGFIndex時，用戶需要指定每個索引維度的最小值與分割區(qū)間，但是在不熟悉數(shù)據(jù)與查詢特征時，選擇較優(yōu)的分割策略比較困難.如果索引維度分區(qū)粒度過小，雖然索引可以更精確地定位查詢相關(guān)數(shù)據(jù)，即減少冗余數(shù)據(jù)讀取，但是數(shù)據(jù)讀取性能較低;如果索引維度分區(qū)粒度過大，雖然數(shù)據(jù)讀取性能較高[6]，但是會造成讀取過多的冗余數(shù)據(jù)，并且數(shù)據(jù)解析與數(shù)據(jù)過濾的CPU開銷也會增大.因此，自動地為DGFIndex選擇較優(yōu)的分割策略對查詢性能的提升至關(guān)重要，但是不同查詢間的最優(yōu)分割策略會相互影響與制約.在傳統(tǒng)企業(yè)中，多數(shù)數(shù)據(jù)分析邏輯都以存儲過程形式存在，即查詢集合在一定時間內(nèi)是靜態(tài)的，所以本文要解決的問題是：對于固定的查詢集合，如何為DGFIndex選擇最優(yōu)的分割策略，從而使查詢集合耗時最短.為了解決該問題，本文首先建立了一種新的MapReduce代價模型來評估不同分割策略對查詢開銷的影響，然后基于該代價模型提出了一種基于模擬退火的兩階段搜索算法加速分割策略的搜索過程，最終為查詢集合選擇較優(yōu)的DGFIndex分割策略，減小查詢集合的總耗時.本文的主要貢獻(xiàn)將是：

1) 根據(jù)采集類數(shù)據(jù)的特征與查詢特點，提出了一種面向Hive的分布式網(wǎng)格文件索引——DGFIndex.該索引可以減少查詢?nèi)哂鄶?shù)據(jù)讀取量，提升查詢性能.

2) 針對基于索引查詢的MapReduce處理過程的特征，提出了一種新的MapReduce代價模型，并基于此提出了一種基于模擬退火的兩階段分割策略搜索算法.

3) 在實驗中，本文使用不同的查詢集合大小、數(shù)據(jù)集大小評測分割策略搜索算法的有效性，實驗顯示該算法可以快速地找到較優(yōu)的分割策略，從而減少查詢集合的總耗時.

1相關(guān)工作

Fig. 1　DGFIndex structure.圖1　DGFIndex結(jié)構(gòu)

在Hadoop索引研究領(lǐng)域，現(xiàn)有的研究工作主要分為2類:1)應(yīng)用于傳統(tǒng)數(shù)據(jù)分析的索引研究，如Jiang等人[7]提出了一種HDFS上的基于排序文件的一維區(qū)間索引，該索引為每個固定大小的頁建立一個索引項，索引表記錄該頁的最小值、最大值以及偏移量，而頁的大小由用戶指定.Dittrich等人[8]提出了Trojan Index和Trojan Join Index，前者為每個數(shù)據(jù)片保存最小值、最大值和記錄數(shù)，該數(shù)據(jù)片的大小由用戶指定，后者通過將欲連接的數(shù)據(jù)集按照連接維度共同分區(qū)存儲到一起來加速多表連接操作.Eltabakh等人[9]提出了Eagle-eyed elephant系統(tǒng)，該系統(tǒng)提供了多種索引機制來加速數(shù)據(jù)讀取，包括為每個數(shù)據(jù)片內(nèi)的數(shù)值和日期類型建立區(qū)間索引、為字符串類型建立倒排索引等，該數(shù)據(jù)片的大小為HDFS塊大小.Richter等人[10]提出了HAIL，該系統(tǒng)提供了一種靜態(tài)索引與一種自適應(yīng)索引，該索引為每個數(shù)據(jù)塊副本建立不同的索引結(jié)構(gòu)，在該研究工作中索引數(shù)據(jù)片的大小是固定的.2)應(yīng)用于空間數(shù)據(jù)處理的索引研究，如Aji等人[11]提出的Hadoop GIS，該系統(tǒng)提出了一種2層的索引結(jié)構(gòu)，全局索引保存維度值與對應(yīng)數(shù)據(jù)片的映射關(guān)系，在每個節(jié)點為每個數(shù)據(jù)片根據(jù)查詢類型按需建立局部索引.此外，Eldawy等人提出了Spatial Hadoop[12]，該系統(tǒng)也提供了一種2層索引結(jié)構(gòu)，首先使用Grid File,R-Tree或R+-Tree將數(shù)據(jù)劃分為大小相同的塊，然后為每個塊建立局部索引，全局索引保存在主節(jié)點的內(nèi)存中以加速索引的訪問.從上面的描述可以看出現(xiàn)有的Hadoop索引相關(guān)的研究工作，索引粒度或者由用戶指定或者設(shè)定為固定經(jīng)驗值，并沒有考慮查詢集合的影響.

在Hadoop代價模型領(lǐng)域，Herodotou[13]為Hadoop的MapReduce任務(wù)執(zhí)行流程的各個階段提出了詳細(xì)的代價模型，該模型應(yīng)用于Hadoop最優(yōu)化參數(shù)選擇[14].Wang等人[4]提出了一種面向Hive的代價模型，用于多表連接最優(yōu)順序選擇.Lin等人[15]為MapReduce提出了一種向量形式的代價模型，并基于該代價模型估算任務(wù)耗時.Wang等人[16]針對偏斜數(shù)據(jù)的GroupBy查詢和Join查詢提出了估價模型.Song等人[17]針對MapReduce中二元連接查詢提出了IO代價模型.但是以上工作沒有考慮基于索引的情況，即其Map階段的數(shù)據(jù)讀取直接使用本地順序讀取或網(wǎng)絡(luò)讀取性能指標(biāo)進(jìn)行代價估計，但是我們發(fā)現(xiàn)數(shù)據(jù)讀取性能不僅與數(shù)據(jù)片大小有關(guān)，還與讀取的查詢相關(guān)數(shù)據(jù)量有關(guān).此外，每個Mapper讀取的數(shù)據(jù)量不再等于HDFS塊大小，而是經(jīng)過索引定位后的數(shù)據(jù)量.并且，如果查詢處理需要多遍Map階段時，已有的工作往往使用一遍Map階段的耗時與遍數(shù)的乘積作為估計，但是如果存在索引的話，各個Mapper讀取的數(shù)據(jù)量是不同的，讀取數(shù)據(jù)量少的Mapper可以快速執(zhí)行完，后面未執(zhí)行的Mapper可以利用空閑出的資源馬上執(zhí)行.總之，現(xiàn)有MapReduce代價模型無法直接應(yīng)用于基于索引的MapReduce處理代價估計中.

2DGFIndex

2.1DGFIndex結(jié)構(gòu)

圖1展示了一個建立在索引維度x和y上的2維DGFIndex.DGFIndex使用網(wǎng)格文件將數(shù)據(jù)空間分為很多小單元，這些小單元稱為GFU(grid file unit).這樣，表中的記錄會按照索引維度的值落在對應(yīng)的GFU中，而所有落在同一個GFU中的記錄會被連續(xù)地存儲在數(shù)據(jù)文件中，稱為數(shù)據(jù)片.每個GFU在索引表中以KeyValue的形式存儲，GFUKey為GFU在數(shù)據(jù)空間中的左下角坐標(biāo)，GFUValue由2部分組成：header和location.header為用戶定義的預(yù)計算用戶自定義函數(shù)(user-defined function, UDF)，例如可以預(yù)計算每個GFU中數(shù)值列的sum，這樣可以極大地加速聚集值查詢;location記錄該GFU對應(yīng)數(shù)據(jù)片所在的文件名、開始偏移量和結(jié)束偏移量.例如，圖1中GFU對應(yīng)的GFUKey=10_17，如果在創(chuàng)建索引時預(yù)計算維度z的sum，則header為落在該GFU中所有記錄的sum(z)值，location為存儲所有落在該GFU中記錄的數(shù)據(jù)片的位置信息.在本例中，文件名為f，開始偏移為4，結(jié)束偏移為20.數(shù)據(jù)片的粒度由用戶在創(chuàng)建索引時給出的分割策略確定，分割策略包括每個索引維度的最小值和分割區(qū)間.如圖1，在創(chuàng)建該索引時，指定索引維度x的最小值為1，分割區(qū)間大小為3；而索引維度y的最小值為11，分割區(qū)間大小為2.此外，為了加快索引表的讀取，DGFIndex的索引表以KeyValue的形式保存在HBase中，這樣可以以基于鍵值的方式快速讀取索引信息.

DGFIndex可以良好地支持行式存儲與列式存儲.例如，對于TextFile存儲格式，DGFIndex記錄每個數(shù)據(jù)片在文件中的開始偏移量和結(jié)束偏移量；對于RCFile存儲格式，每個數(shù)據(jù)片保存為其中的一個行組(row group)，DGFIndex只需記錄每個Row Group的開始偏移量.可以看出，在DGFIndex中數(shù)據(jù)片為最小讀取單位.

Fig. 2　An example of DGFIndex construction.圖2　DGFIndex創(chuàng)建過程例子

2.2DGFIndex創(chuàng)建索引過程

DGFIndex的創(chuàng)建過程為一個MapReduce任務(wù)，Map階段的計算邏輯如算法1所示，Reduce階段的計算邏輯如算法2所示.

算法1. 創(chuàng)建DGFIndex的Map函數(shù).

輸入：鍵為記錄在該數(shù)據(jù)塊中的偏移量，值為記錄record;

①idxDValues=getIdxDimValues(record);

②GFUKey=computeGFUKey(idxDValues);

③Emit(GFUKey,record).

在創(chuàng)建索引的Map階段，對于每條記錄，首先讀取其索引維度的值(行①);然后根據(jù)索引維度的值與分割策略計算其所屬的GFU，從而得到該條記錄的GFUKey(行②);最后將GFUKey與該記錄作為鍵值對發(fā)往Reduce函數(shù)(行③).

算法2. 創(chuàng)建DGFIndex的Reduce函數(shù).

輸入：鍵為GFUKey，值為具有相同GFUKey的record列表ListRecordrecordsList;

輸出：存儲在HBase中的索引表與重組之后的數(shù)據(jù)文件.

①startOffset=當(dāng)前輸出文件的偏移量;

②endOffset=-1;

③sliceSize=0;

④filename=當(dāng)前輸出文件的名字;

⑤header=null;

⑥ forrecordinrecordsListdo

⑦h(yuǎn)eader=precompute(record,header);

⑧sliceSize+=sizeof(record);

⑨ end for

⑩endOffset=startOffset+sliceSize;

在創(chuàng)建索引的Reduce階段，Reducer接收到具有相同GFUKey的記錄列表，即屬于同一個數(shù)據(jù)片的所有記錄，最終目的是將每個數(shù)據(jù)片按序輸出，并記錄GFUKey與數(shù)據(jù)片在文件中位置的對應(yīng)關(guān)系.同時，還需按照用戶指定的UDF預(yù)計算每個GFU中記錄對應(yīng)的值.具體地，1)初始化數(shù)據(jù)片開始偏移、結(jié)束偏移、數(shù)據(jù)片大小、輸出文件名與保存預(yù)計算值的header(行①～⑤);2)對于具有相同GFUKey的每條記錄(行⑥)，首先預(yù)計算其UDF值并累加到header中(行⑦)，然后將當(dāng)前記錄的大小累加到sliceSize中(行⑧～⑨)，待處理完整個記錄列表，計算其結(jié)束偏移量(行⑩);3)計算GFUValue，并將GFUKeyGFUValue對寫入HBase(行).至此，索引創(chuàng)建結(jié)束.

如圖2所示，假設(shè)現(xiàn)有一個數(shù)據(jù)文件，使用圖1中的分割策略創(chuàng)建DGFIndex，同時預(yù)計算sum(z)，可以看到，DGFIndex索引創(chuàng)建的過程實際為數(shù)據(jù)重組織的過程，目的為將位于同一GFU中的記錄存儲到一起.如9,14,0.8與8,13,0.2位于同一個GFU，經(jīng)過數(shù)據(jù)重組織后存儲到數(shù)據(jù)文件的連續(xù)位置.同時，創(chuàng)建了包含GFUKey與GFUValue的索引項.

2.3基于DGFIndex的查詢處理過程

基于DGFIndex的數(shù)據(jù)查詢過程分為3步：1)索引表讀取;2)HDFS數(shù)據(jù)塊過濾;3)數(shù)據(jù)塊內(nèi)部的數(shù)據(jù)片過濾.下面分別詳細(xì)描述各步驟.

算法3. 索引表讀取.

輸入：SQL查詢qi；

輸出：查詢相關(guān)的數(shù)據(jù)片位置集合SLOCqi;

查詢子結(jié)果SubRes，如果查詢可以使用預(yù)計算的UDF時，在這一步可以通過讀取索引表得到部分查詢結(jié)果.

①idxPred=extract(qi);

②isUDFQuery=check(qi);

③ {innerKeySet,boundaryKeySet}=DGFIndex.search(idxPred);

④queryKeySet=boundaryKeySet;

⑤ ifisUDFQuerythen

⑥SubRes=KVStore.getHeader(innerKeySet);

⑦writeToTmpFile(SubRes);

⑧ else

⑨queryKeySet=queryKeySet∪InnerKeySet

⑩ end if

算法4. HDFS數(shù)據(jù)塊過濾.

輸入：輸入文件列表fileList、保存SLOCqi的臨時文件的路徑;

輸出：經(jīng)過索引過濾后的查詢qi相關(guān)的HDFS數(shù)據(jù)塊集合chosenBlocksqi.

①chosenBlocksqi=?;

②SLOCqi=readFromTmpFile();

③allBlocks=getSplits(fileList);

④ forblockinallBlocksdo

⑤ ifblock∩SLOCqi≠? then

⑥chosenBlocksqi=chosenBlocksqi∪block;

⑦ end if

⑧ end for

⑨ forblockinchosenBlocksqido

⑩slicesInBlock=getRelatedSlices

(SLOCqi);

步驟2. HDFS數(shù)據(jù)塊過濾的步驟如算法4所示，算法4發(fā)生在InputFormat.getSplits函數(shù)中.首先初始化過濾后選定的數(shù)據(jù)塊集合chosenBlocksqi為空(行①)，并讀取算法1輸出的臨時文件，得到查詢相關(guān)數(shù)據(jù)片的位置信息(行②).然后根據(jù)輸入文件列表得到所有需要處理的數(shù)據(jù)塊(行③)，對于每個數(shù)據(jù)塊，判斷其是否包含查詢相關(guān)的數(shù)據(jù)片，如果包含則放入chosenBlocksqi，否則拋棄(行④～⑧).隨后，為chosenBlocksqi中每個選中的數(shù)據(jù)塊建立一個KeyValue對，Key為該數(shù)據(jù)塊的ID，Value為該數(shù)據(jù)塊內(nèi)所有需要讀取的數(shù)據(jù)片的偏移量，所有的KeyValue對保存在HBase一張臨時表中(行⑨).最后，返回查詢相關(guān)的數(shù)據(jù)塊

步驟3. 數(shù)據(jù)塊內(nèi)部的數(shù)據(jù)片過濾發(fā)生在RecordReader.next函數(shù)中，該函數(shù)讀取步驟2中HBase中的臨時表，得到在該塊中所有需要讀取的數(shù)據(jù)片的偏移量，然后在讀取數(shù)據(jù)時跳過不需要讀取的數(shù)據(jù)片.如果某個數(shù)據(jù)片跨塊存儲，此時，假設(shè)其大部分存儲在塊A中，則讓處理塊A的Mapper處理該數(shù)據(jù)片，以最小化遠(yuǎn)程數(shù)據(jù)讀取.當(dāng)查詢?yōu)榫奂挡樵儯瑒t待Hive得到邊界GFU結(jié)果后，需要與算法3中內(nèi)部GFU的子結(jié)果合并得到最終結(jié)果.

如圖3所示，假設(shè)有一個SQL查詢，形式如圖3所示.1)先根據(jù)查詢謂詞，定位DGFIndex中的邊界GFU與內(nèi)部GFU，因為該查詢?yōu)榫奂挡樵?，對于?nèi)部區(qū)域直接查詢HBase中header得到子結(jié)果，保存于臨時文件中.對于邊界區(qū)域，得到相關(guān)數(shù)據(jù)片在文件中的位置信息.2)根據(jù)數(shù)據(jù)片在文件中的位置信息過濾與查詢無關(guān)的數(shù)據(jù)塊，然后為每個候選數(shù)據(jù)塊保存需要讀取的數(shù)據(jù)片的偏移.3)在Mapper處理每個數(shù)據(jù)塊時，跳過查詢無關(guān)的數(shù)據(jù)片.最終得到的子結(jié)果與第1步中的子結(jié)果合并，得到最終結(jié)果.

SELECTsum(z)

FROMtable

WHEREx>5 ANDx<12 ANDy≥12 ANDy<16

Fig. 3　An example of DGFIndex-based query.圖3　DGFIndex索引查詢例子

2.4DGFIndex分割策略選擇問題

由2.2～2.3節(jié)可以看出，分割策略的選擇與查詢性能息息相關(guān)：如果選擇細(xì)粒度的分割策略，查詢邊界區(qū)域會較小，即讀取的冗余數(shù)據(jù)量較小，而且解析數(shù)據(jù)、過濾數(shù)據(jù)的CPU開銷也較小.但是文獻(xiàn)[6]指出，數(shù)據(jù)讀取性能與數(shù)據(jù)片的大小成正比，即此情況下數(shù)據(jù)讀取性能較低；相反，如果選擇粗粒度的分割策略，雖然此時的數(shù)據(jù)讀取性能較高， 但是由于查詢邊界區(qū)域會較大，造成讀取過多冗余數(shù)據(jù)，而且，這也會造成解析數(shù)據(jù)、過濾數(shù)據(jù)的CPU開銷較大.圖4展示了不同數(shù)據(jù)片大小對查詢性能的影響(該實驗的數(shù)據(jù)集使用存儲格式為RCFile的TPC-H lineitem表，大小為187 GB;查詢使用TPC-H中的Q6，實驗環(huán)境與第4節(jié)中的描述一致，HDFS數(shù)據(jù)塊大小設(shè)置為256 MB).可以看出，對該查詢而言，32 MB為較優(yōu)的數(shù)據(jù)片大小，過小或過大的數(shù)據(jù)片都無法得到最優(yōu)的查詢性能.但是，由于不同的查詢具有不同的查詢謂詞，即不同查詢的最優(yōu)數(shù)據(jù)片大小可能不同，這就造成查詢間最優(yōu)分割策略相互影響與制約.因此，如何為DGFIndex選擇最優(yōu)的索引分割策略以最大化地提升查詢集合性能成為一項重要且具有挑戰(zhàn)性的任務(wù).

Fig. 4　Influence of different slice size on query performance.圖4　不同數(shù)據(jù)片大小對查詢性能造成的影響

3基于代價估計的分割策略選擇算法

3.1問題描述

為了方便描述問題定義與代價模型，首先預(yù)定義一些形式化符號，如表1所示.avgFieldSizek和avgRecordSize的值可以通過運行涉及某個列的查詢，然后根據(jù)MapReduce Counter的值得到.

(1)

q∈Q:{q1,q2,…,qn},

(2)

(3)

(4)

(5)

3.2代價模型

由問題描述可知，解決DGFIndex分割策略選擇問題的關(guān)鍵為建立合理的代價模型以反映不同分割策略對查詢的影響.MapReduce代價模型已經(jīng)被眾多學(xué)者廣泛研究[4,13-17]，但是現(xiàn)有工作中的代價模型無法直接應(yīng)用于本工作，原因如下：

1) 以往的代價模型在建模Map階段數(shù)據(jù)讀取代價時，直接使用HDFS塊大小與固定數(shù)據(jù)讀取吞吐的商，沒有考慮不同數(shù)據(jù)片大小對讀取性能的影響與索引對數(shù)據(jù)的過濾作用.

2) 當(dāng)查詢使用的Mapper數(shù)大于集群容量時，以往的代價模型直接使用Map階段運行的遍數(shù)與單遍代價的乘積作為Map階段的代價估計.而在基于索引的查詢處理時，由于每個Mapper讀取數(shù)據(jù)量各不相同，數(shù)據(jù)量較小的Mapper可以快速執(zhí)行完，第2遍的Mapper可以馬上使用空閑的Mapper資源進(jìn)行執(zhí)行，以往的代價模型無法準(zhǔn)確描述該特性.

因此需要建立新的基于索引進(jìn)行數(shù)據(jù)處理的MapReduce代價模型.圖5展示了Hive中操作符在Map階段的數(shù)據(jù)處理流程及各操作符的作用.不同分割策略只會影響RecordReader與FilterOperator的性能：對于RecordReader，分割粒度越大其讀取的數(shù)據(jù)量越大；對于FilterOperator，分割粒度越大其數(shù)據(jù)解析與數(shù)據(jù)過濾的CPU開銷越大.而FilterOperator后輸出的為符合查詢謂詞條件的記錄，不同的分割策略并不會影響該值.所以，只需要構(gòu)建Map階段數(shù)據(jù)讀取與數(shù)據(jù)處理的代價模型，即可反映不同分割策略對查詢集合性能的影響.

Fig. 5　Data process in Map phase.圖5　Map階段數(shù)據(jù)處理流程

查詢qi在分割策略SPj下，使用DGFIndex處理的代價估計建模為式(7),MapRead(SPj,qi)表示Map階段數(shù)據(jù)讀取的代價，MapCPU(SPj,qi)表示Map階段數(shù)據(jù)解析與數(shù)據(jù)過濾的CPU代價.

CostModel(SPj,qi)=

(7)

Map階段數(shù)據(jù)讀取的代價估計如式(8)所示，為查詢相關(guān)的數(shù)據(jù)總量與數(shù)據(jù)讀取吞吐的商，查詢相關(guān)數(shù)據(jù)總量定義為式(9)，數(shù)據(jù)片大小定義為式(10).對每個查詢而言，不同的分割策略SPj導(dǎo)致了不同的查詢相關(guān)的GFUKey集合與不同的數(shù)據(jù)片大小，從而導(dǎo)致不同的查詢相關(guān)數(shù)據(jù)量.由于基于索引進(jìn)行查詢處理時，每個Mapper處理的數(shù)據(jù)量不同，因此處理數(shù)據(jù)量少的Mapper可以快速完成，這樣未啟動的Mapper可以繼續(xù)使用空閑出來的資源進(jìn)行處理.并且，由于每次Mapper處理的次序與調(diào)度算法和集群中各節(jié)點的負(fù)載相關(guān)，因此很難事先得到Mapper處理的次序.所以，這里使用讀取查詢相關(guān)全部數(shù)據(jù)的總耗時進(jìn)行估計，這一點與以往的MapReduce代價模型不同.對于列式存儲，如RCFile,只需要讀取查詢相關(guān)的列，所以讀取的數(shù)據(jù)總量與查詢相關(guān)列的總大小成正比.

MapRead(SPj,qi)=

(8)

(9)

(10)

式(8)中數(shù)據(jù)讀取吞吐的建模過程如下：由圖6，7可以看出(該實驗使用與圖4中實驗相同的數(shù)據(jù)集、集群環(huán)境與參數(shù)設(shè)置)，數(shù)據(jù)讀取吞吐與數(shù)據(jù)片大小成正比，與查詢相關(guān)數(shù)據(jù)量成反比.原因為當(dāng)數(shù)據(jù)片增大時，隨機讀操作減少，數(shù)據(jù)的順序讀取性能提升；當(dāng)查詢相關(guān)數(shù)據(jù)量增大時，單節(jié)點啟動的多個Mapper對磁盤IO產(chǎn)生競爭，造成讀取吞吐降低，這種情況尤其會出現(xiàn)在磁盤讀取為瓶頸時，例如同一臺物理機上的多虛擬機實例.

Fig. 6　Influence of query selectivity and slice size on data reading performance.圖6　數(shù)據(jù)讀取吞吐與查詢選擇度和數(shù)據(jù)片大小的關(guān)系

Fig. 7　Query related data size.圖7　各查詢相關(guān)數(shù)據(jù)量

本文使用Profiling技術(shù)與多項式擬合方法建立數(shù)據(jù)讀取吞吐與數(shù)據(jù)片大小和查詢相關(guān)數(shù)據(jù)量之間的函數(shù)關(guān)系.具體地，首先隨機生成不同查詢選擇度的查詢集合，然后通過指定不同的分割策略為數(shù)據(jù)表建立不同數(shù)據(jù)片大小的DGFIndex，通過運行查詢集合得到讀取數(shù)據(jù)量大小與讀取耗時(通過在RecordReader中添加Counter得到)，從而得到對應(yīng)的數(shù)據(jù)讀取吞吐量，最后進(jìn)行多項式函數(shù)擬合.

此外，本文在建模數(shù)據(jù)讀取吞吐時，如果有數(shù)據(jù)片為跨塊讀取，并沒有考慮網(wǎng)絡(luò)遠(yuǎn)程讀取，原因有2點：1)因為使用了存儲大部分?jǐn)?shù)據(jù)片的Mapper處理該數(shù)據(jù)片的優(yōu)化技術(shù)，遠(yuǎn)程讀取數(shù)據(jù)量較小，通過實驗發(fā)現(xiàn)在使用8～128 MB數(shù)據(jù)片大小時，遠(yuǎn)程讀取數(shù)據(jù)量約占總讀取數(shù)據(jù)量的0～6%，因此對代價估計的影響有限.2)因為對于列式存儲格式而言，如RCFile，數(shù)據(jù)片為其中的一個Row Group，而Row Group為最小讀取單元，所以較難統(tǒng)計讀取部分Row Group的時間.

Map階段的數(shù)據(jù)解析與數(shù)據(jù)過濾的CPU代價估計如式(11)所示，即讀取的記錄數(shù)與每條記錄消耗的CPU代價的乘積.經(jīng)過實驗發(fā)現(xiàn)，每條記錄消耗的CPU代價為常量，不受其他變量的影響，在本文使用的實驗環(huán)境中，該常量值約為3167 nsrecord.

MapCPU(SPj,qi)=

(11)

由3.2節(jié)的代價模型可以看出，首先，分割策略在2方面決定了Hive處理查詢時讀取的數(shù)據(jù)量：1)查詢相關(guān)的數(shù)據(jù)片的數(shù)量，即給定索引維度的分割區(qū)間大小與查詢謂詞，就可以得到該查詢相關(guān)的數(shù)據(jù)片數(shù)量；2)數(shù)據(jù)片大小，一旦各索引維度分割區(qū)間確定，就確定了數(shù)據(jù)片大小.其次，分割策略決定了數(shù)據(jù)讀取吞吐，給定數(shù)據(jù)片大小與查詢相關(guān)數(shù)據(jù)量，就可以根據(jù)擬合的函數(shù)得到數(shù)據(jù)讀取吞吐.最后，分割策略還決定了Map階段數(shù)據(jù)解析與過濾的CPU開銷，因為其確定了讀取數(shù)據(jù)量，也就確定了記錄數(shù).

由此可知，一旦給定分割策略SPj，就可以對查詢集合Q中的每個qi進(jìn)行代價估計，從而衡量分割策略的優(yōu)劣.但是，由于候選分割策略的搜索空間大小正比于多個維度可選方案的乘積，并且對于每種分割策略，都要計算整個查詢集合的代價估計，因此遍歷搜索最優(yōu)的分割策略將會花費較長的時間.為了加快搜索過程，本文提出了一種基于模擬退火的兩階段搜索算法來尋找較優(yōu)的分割策略.

3.3基于模擬退火的兩階段分割策略搜索算法

由于分割策略選擇過程為多個索引維度分割區(qū)間選擇組合問題，為了避免搜索陷入局部最優(yōu)解，本文選擇模擬退火算法進(jìn)行搜索.基于模擬退火的分割策略搜索算法分為2個階段：粗粒度近似搜索與細(xì)粒度精確搜索.第1階段找到近似最優(yōu)解，第2階段減小搜索步長，在近似最優(yōu)解周圍搜索精確“最優(yōu)解”.這里的最優(yōu)解并非實際的最優(yōu)分割策略，因為這取決于代價模型的準(zhǔn)確性，而代價模型本身為估算值.

算法過程如算法5所示:

算法5. 基于模擬退火的兩階段搜索算法.

輸入：查詢集合Q;

輸出：較優(yōu)的分割策略.

①minIntrls=currentItrls=getInitial-

Interval();

②minCost=currentCost=getCost

(currentIntrls);

③ whiletemp>1 do

④newIntrls=getNeighbor(currentIntrls,temp);

⑤newCost=getCost(newIntrls);

⑥ ifnewCost

⑦acceptRatio=1;

⑧ else

⑩ end if

算法6. 得到當(dāng)前分割策略的鄰居算法.

輸入：當(dāng)前的分割策略currentIntrls、當(dāng)前的溫度temp;

輸出：當(dāng)前分割策略的鄰居.

①newIntrls=clone(currentIntrls)

② iftemp>10 then

③ratio=1;

④ else

⑤ratio=0.1;

⑥ end if

⑦ forkthintrlinnewIntrls(kfrom 1 to

idxNum) do

⑧random=random();

⑨ ifrandom>0.5 then

從算法6過程可以看出，迭代次數(shù)由初始溫度temp與冷卻速率coolingRate決定：temp越小，coolingRate越大，迭代次數(shù)越少，收斂速度越快，但是可能得不到最優(yōu)解;反之，則可能增加算法搜索時間.在下面的實驗中，設(shè)置temp=200，coolingRate=0.01.

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

4.1實驗環(huán)境與測試集

1) 硬件環(huán)境.本次實驗使用由32個虛擬機節(jié)點組成的集群環(huán)境，每個虛擬機節(jié)點具有12核CPU、26 GB內(nèi)存、600 GB磁盤.其中一個節(jié)點作為MapReduce計算框架的主節(jié)點JobTracker，一個節(jié)點作為HDFS的主節(jié)點NameNode，一個節(jié)點作為HBase的主節(jié)點HMaster.其他節(jié)點作為從節(jié)點，運行DataNode,TaskTracker.Hive與NameNode運行在同一節(jié)點.

2) 軟件環(huán)境.每個節(jié)點使用CentOS 7.0,JDK 1.7.0_65 64bit.使用Hadoop-1.2.1,HBase-0.94.23(用于存儲DGFIndex的索引表).DGFIndex實現(xiàn)在Hive-0.14.0中.HDFS塊大小設(shè)置為256 MB，Hadoop,Hive與HBase的其他配置參數(shù)都使用默認(rèn)值.

3) 測試集.本實驗使用TPC-H測試集中的lineitem表與Q6，使用被廣泛使用的RCFile與ORC作為文件存儲格式，不同數(shù)據(jù)集大小如表2所示.本實驗為lineitem表在l_discount,l_quantity和l_shipdate上建立三維索引，各維度的基數(shù)如表3所示.查詢集合由隨機生成的Q6構(gòu)成，集合中的查詢具有不用的選擇度，本實驗使用2個查詢集合：30個隨機查詢構(gòu)成的集合QSet30與50個隨機查詢構(gòu)成的集合QSet50.選擇該測試集的原因有3點：1)TPC-H被廣泛地用于數(shù)據(jù)倉庫類系統(tǒng)的評測工作，因此使用該測試集的結(jié)果具有可比性；2)由于在Hive中，索引只作用于過濾單表讀取時查詢無關(guān)的數(shù)據(jù)，所以選擇單表數(shù)據(jù)集足以評測索引的數(shù)據(jù)過濾性能，并且lineitem表是該測試集中最大的表；3)Q6是TPC-H中典型的多維查詢，可以充分測試DGFIndex的多維數(shù)據(jù)索引能力.此外，在本實驗中，在運行每個查詢前都會清空操作系統(tǒng)的緩存并重啟Hadoop，以保證索引定位的數(shù)據(jù)從磁盤讀取，從而避免緩存對結(jié)果造成的影響.并且，查詢集合中每個查詢都會運行3次，在結(jié)果中使用3次結(jié)果的平均值，以減弱集群不穩(wěn)定對結(jié)果造成的影響.

Table 2　Data Size

Table 3　Cardinality of Index Dimensions

Fig. 8　Query cost time of Data-Medium.圖8　Data-Medium上的查詢耗時

4.2DGFIndex的性能

本實驗中，在RCFile上創(chuàng)建Hive原生索引Compact Index與DGFIndex，此外，本實驗還與ORC[6]中的索引進(jìn)行對比.ORC是Hive目前最新的列式存儲格式，內(nèi)嵌了索引功能.Compact Index與ORC中索引的數(shù)據(jù)過濾效果與索引維度數(shù)值在文件中的分布有關(guān)，對于均勻數(shù)據(jù)集TPC-H來說，兩者的性能較差.為了提升兩者的索引性能，事先使用并行Order By對兩者的數(shù)據(jù)表在索引維度上進(jìn)行全排序預(yù)處理.圖8,9展示了在不同數(shù)據(jù)集大小與不同查詢選擇度下的各種索引的查詢性能.

Fig. 9　Query cost time of Data-Large.圖9　Data-Large上的查詢耗時

從實驗結(jié)果可以看出，相對不使用任何索引的RCFile，Compact Index可以提升2～7倍查詢性能，DGFIndex可以提升4.7～15倍查詢性能,并且，DGFIndex比Compact Index的查詢性能提升了50%～114%.原因有2點：1)Compact Index只能在HDFS數(shù)據(jù)塊級別過濾查詢無關(guān)數(shù)據(jù)，這會造成讀取過多的冗余數(shù)據(jù)；而DGFIndex可以在細(xì)粒度的數(shù)據(jù)片級別過濾查詢無關(guān)的數(shù)據(jù)，從而大幅降低冗余數(shù)據(jù)的讀取，提升查詢性能.2)Compact Index讀取索引的方式為啟用額外的MapReduce任務(wù)全表掃描的方式，索引讀取效率較低；而DGFIndex使用基于鍵值的方式，只需讀取查詢相關(guān)的鍵，讀取效率較高.此外，相比于不使用索引的ORC，其內(nèi)的索引提升1.6～2.6倍查詢性能.DGFIndex比ORC中的索引查詢性能提升了8%～28%，而對于點查詢來說，分別提升了1.2倍和2.2倍.可以看出，DGFIndex在低選擇度時的優(yōu)勢更明顯，原因為：經(jīng)過索引定位后，DGFIndex使用了比ORC更少的Mapper.

4.3分割策略選擇算法的有效性

Fig. 10　Cost time of QSet30.圖10　QSet30在不同數(shù)據(jù)片大小下的查詢耗時

本實驗使用RCFile作為底層存儲格式.圖10,11展示了不同數(shù)據(jù)量下基于代價估計的分割策略選擇算法得到的分割策略的查詢集合耗時與人工指定不同數(shù)據(jù)片大小的分割策略的查詢集合耗時對比結(jié)果，其中后綴為opt的為本文提出算法選擇的分割策略對應(yīng)的數(shù)據(jù)片大小.Data-Small下人工指定的分割策略(對應(yīng)索引維度l_quantity,l_discount,l_shipdate)分別為[2,0.01,60]，[4,0.01,60]，[4,0.01,120]，[4,0.02,115]與[8,0.02,115].Data-Medium下人工指定的分割策略分別為[2,0.01,29]，[2,0.01,58]，[4,0.01,59]，[8,0.01,58]與[12,0.01,73].Data-Large下人工指定的分割策略為[1,0.01,24]，[2,0.01,24]，[2,0.01,47]，[4,0.01,52]與[4,0.01,97].由本文算法得到的較優(yōu)分割策略如表4所示.

Fig. 11　Cost time of QSet50.圖11　QSet50在不同數(shù)據(jù)片大小下的查詢耗時

DataSetData-SmallData-MediumData-LargeQSet30[6,0.01,115][5,0.01,78][2,0,01,78]QSet50[9,0.01,83][9,0.01,49][3,0.01,49]

由結(jié)果可以看出，人工指定分割策略方法在選擇不同分割策略時性能各有差異，并且索引粒度太大或太小都無法得到較優(yōu)的性能，因此在用戶不熟悉數(shù)據(jù)與查詢特征時較難選擇較優(yōu)的分割策略.相反，基于代價估計的分割策略選擇算法可以根據(jù)查詢集合自動地得到較優(yōu)的分割策略，從結(jié)果可以看出與人工指定方法相比，最多可以減少查詢集合耗時30%.

4.4基于代價估計的分割策略選擇算法收斂速度

圖12展示了基于遍歷算法、模擬退火與人工選擇分割策略選擇算法的耗時，這里假設(shè)人工選擇的耗時為1 s.

Fig. 12　Cost time of splitting policy search algorithm.圖12　分割策略選擇算法耗時

從圖12可以看出,基于模擬退火的算法比遍歷算法快12～24倍，在短時間內(nèi)搜索到較優(yōu)的索引分割策略.此外，基于遍歷算法的分割策略選擇算法的耗時與多個索引維度基數(shù)的乘積成正比，因為其需要遍歷每一種可能的分割策略的可行性.而在本實驗中，索引維度的基數(shù)都較小，如果應(yīng)用中遇到更大基數(shù)的索引維度，如浮點類型維度，則遍歷算法的耗時是不可接受的.如果根據(jù)數(shù)據(jù)與查詢特征人為選取分割策略，雖然可以快速選定，但是較難選擇較優(yōu)的分割策略.

5結(jié)束語

本文針對采集類數(shù)據(jù)與查詢特征，提出了一種面向Hive的多維索引技術(shù)—DGFIndex，該索引以細(xì)粒度過濾查詢無關(guān)的數(shù)據(jù)大幅減少冗余數(shù)據(jù)讀取，其查詢性能比Hive原生索引Compact Index提升50%～114%，比ORC中的索引提升8%～28%，并極大地提高了點查詢的性能.

但是在創(chuàng)建DGFIndex時，需要人為指定各索引維度分割區(qū)間大小，在對查詢與數(shù)據(jù)特征不熟悉情況下，用戶很難選擇最優(yōu)的索引分割策略.針對該問題，本文首先提出了一種新的MapReduce代價模型，基于該模型提出了一種基于模擬退火的兩階段分割策略搜索算法，實驗證明該算法可以在較短的時間內(nèi)得到較優(yōu)的分割策略.

本文提出的代價模型沒有考慮數(shù)據(jù)分布維度，在數(shù)據(jù)分布不均勻時，對DGFIndex而言，各數(shù)據(jù)片的大小會出現(xiàn)不同.在這種情況下，使用查詢相關(guān)GFUKey的數(shù)量估算查詢相關(guān)數(shù)據(jù)量會不精確，需要得到數(shù)據(jù)片在文件中的布局來估算該值.但是由于需要記錄更多的信息，因此代價估計計算的速度會減慢，分割策略的搜索速度也會大大減慢.在未來的工作中，我們將會在代價模型中引入數(shù)據(jù)分布維度，并優(yōu)化在該種情況下分割策略搜索的速度.

參考文獻(xiàn)

[1]Zaharia M, Chowdhury M, Franklin M, et al. Spark: Cluster computing with working sets[C] //Proc of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 2010). Berkeley, CA: USENIX Association, 2010: 10

[2]Hu Songlin, Liu Wantao, Rabl T, et al. DualTable: A hybrid storage model for update optimization in Hive[C] //Proc of the 31st IEEE Int Conf on Data Engineering (ICDE 2015). Piscataway, NJ: IEEE, 2015: 1340-1351

[3]Liu Yue, Hu Songlin, Rabl T, et al. DGFIndex for smart grid: Enhancing Hive with a cost-effective multidimensional range index[C] //Proc of the 40th Int Conf on Very Large Data Bases (VLDB 2014). New York: ACM, 2014: 1496-1507

[4]Wang Yue, Xu Yingzhong, Liu Yue, et al. QMapper for smart grid: Migrating SQL-based application to Hive[C] //Proc of the ACM SIGMOD Int Conf on Management of Data (SIGMOD 2015). New York: ACM, 2015: 647-658

[5]Thusoo A, Sarma J S, Jain N, et al. Hive: A warehousing solution over a map-reduce framework[C] //Proc of the 35th Int Conf on Very Large Data Bases (VLDB 2009). New York: ACM, 2009: 1626-1629

[6]Huai Yin, Ma Siyuan, Lee Rubao, et al. Understanding insights into the basic structure and essential issues of table placement methods in clusters[C] //Proc of the 40th Int Conf on Very Large Data Bases (VLDB 2014). New York: ACM, 2014: 1750-1761

[7]Jiang Dawei, Ooi B C, Shi Lei, et al. The performance of MapReduce: An in-depth study[C] //Proc of the 36th Int Conf on Very Large Data Bases (VLDB 2010). New York: ACM, 2010: 472-483

[8]Dittrich J, Quiane-Ruiz J A, Jindal A, et al. Hadoop++: Making a yellow elephant run like a cheetah (without it even noticing)[C] //Proc of the 36th Int Conf on Very Large Data Bases (VLDB 2010). New York: ACM, 2010: 515-529

[9]Eltabakh M, Ozcan F, Sismanis Y, et al. Eagle-eyed elephant: Split-oriented indexing in Hadoop[C] //Proc of the 16th Int Conf on Extending Database Technology (EDBT/ICDT 2013). New York: ACM, 2013: 89-100

[10]Richter S, Quiane-Ruiz J A, Schuh S, et al. Towards zero-overhead static and adaptive indexing in Hadoop[J]. The VLDB Jounal, 2014, 23(3): 469-494

[11]Aji A, Wang Fusheng, Vo H, et al. Hadoop GIS: A high performance spatial data warehousing system over MapReduce[C] //Proc of the 39th Int Conf on Very Large

Data Bases (VLDB 2013). New York: ACM, 2013: 1009-1020

[12]Eldawy A, Mokbel M. A demonstration of spatial Hadoop: An efficient MapReduce framework for spatial data[C] //Proc of the 39th Int Conf on Very Large Data Bases (VLDB 2013). New York: ACM, 2013: 1230-1233

[13]Herodotou H. Hadoop performance models[R]. Pittsburgh, PA: arXiv preprint, 2011

[14]Herodotou H, Badu S. Profiling, what-if analysis, and cost-based optimization of MapReduce programs[C] //Proc of the 37th Int Conf on Very Large Data Bases (VLDB 2011). New York: ACM, 2011: 1111-1122

[15]Lin Xuelian, Meng Zide, Xu Chuan, et al. A practical performance model for Hadoop MapReduce[C] //Proc of 2012 IEEE Int Conf on Cluster Computing (Cluster 2012). Piscataway, NJ: IEEE, 2012: 231-239

[16]Wang Youwei, Wang Weiping, Meng Dan. Query optimization by statistical approach for Hive data warehouse[J]. Journal of Computer Research and Development, 2015, 52(6): 1452-1462 (in Chinese)(王有為, 王偉平, 孟丹. 基于統(tǒng)計方法的Hive數(shù)據(jù)倉庫查詢優(yōu)化實現(xiàn)[J]. 計算機研究與發(fā)展, 2015, 52(6): 1452-1462)

[17]Song Jie, Li Tiantian, Zhu Zhiliang, et al. Research on I/O cost of MapReduce join[J]. Journal of Software, 2015, 26(6): 1438-1456 (in Chinese)(宋杰, 李甜甜, 朱志良, 等. MapReduce連接查詢的I/O代價研究[J]. 軟件學(xué)報, 2015, 26(6): 1438-1456)

Liu Yue, born in 1988. PhD candidate. Student member of China Computer Federation. His research interests include distributed system and database system.

Li Jintao, born in 1962. Professor and PhD supervisor. His research interests include multimedia technology, virtual reality technology, and pervasive computing technology.

Hu Songlin, born in 1973. Professor and PhD supervisor. Senior member of China Computer Federation. His research interests include service computing, distributed system and middleware.

A Cost-Based Splitting Policy Search Algorithm for Hive Multi-Dimensional Index

Liu Yue1,2, Li Jintao1, and Hu Songlin3

1(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)3(InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093)

AbstractIn the domain of energy Internet, smart city, etc, the massive smart devices collect large amount of data every day, and traditional enterprises need to perform lots of multi-dimensional analysis on these data to support decision-making. Recently, these enterprises try to solve the big data problem with technologies from Internet companies, for example, Hadoop and Hive etc. However, Hive has limited multi-dimensional index ability, and cannot satisfy the requirements of high-performance analysis in traditional enterprises. In this paper, we propose a distributed grid file based multi-dimensional index—DGFIndex to improve the multi-dimensional query performance of Hive. However, DGFIndex needs user to specify the splitting policy when creating index, which is not trivial for user when they are not familiar with data and query pattern. To solve it, we propose a novel MapReduce cost model to measure the DGFIndex-based query performance on specific splitting policy, a two-phase simulated annealing algorithm to search for the suitable splitting policy for DGFIndex, and finally decrease the total cost time of query set. The experimental results show that, DGFIndex improves 50%～114% query performance than original Compact Index in Hive. For static query set, compared with manual-specifying partition policy, our algorithm can choose suitable interval size for each index dimension, and decrease the cost time of query set at most 30%.

Key wordsHive; MapReduce; multi-dimensional index; cost model; simulated annealing

收稿日期：2015-12-21；修回日期：2016-02-02

基金項目：國家自然科學(xué)基金項目(61070027)

通信作者：虎嵩林(husonglin@iie.ac.cn)

中圖法分類號TP311.132

This work was supported by the National Natural Science Foundation of China (61070027).