基于信息網模型的分布并行多連接查詢優化

徐 晶 劉夢赤，2

1(武漢大學軟件工程國家重點實驗室 湖北 武漢 430072)2(武漢大學計算機學院 湖北 武漢 430072)

?

基于信息網模型的分布并行多連接查詢優化

徐 晶1劉夢赤1，2

1(武漢大學軟件工程國家重點實驗室 湖北 武漢 430072)2(武漢大學計算機學院 湖北 武漢 430072)

在分布式集群系統中，數據根據劃分算法存儲在集群的各個節點，這為涉及大量連接操作的復雜查詢帶來了昂貴的網絡開銷。針對該問題，基于信息網模型INM(Information Network Mode)，提出最小通信量查詢劃分算法和多目標查詢優化算法。其中查詢劃分算法將復雜查詢劃分成多個PWOC(parallelizable without communication)子查詢，所有子查詢可近似無通信地并行執行。多目標優化算法將子查詢作為查詢計劃的基本操作，并將并行性和通信代價同時作為驅動目標，以傳統多目標加權算法結合貪心策略作為評估依據生成查詢計劃樹。最后，系統基于TPC-H基準生成測試數據，將原始算法與優化算法進行了對比實驗，結果表明優化算法可以極大提高復雜查詢的效率。

查詢優化 分布并行處理 多連接 信息網模型(INM)

0 引 言

隨著移動和互聯網技術的發展，尤其是社交網絡、移動物聯網的迅速發展，數據時刻以爆炸式的速度增長。大數據時代，數據呈現出數量大、種類多等特點。傳統的集中式存儲方式由于可靠性低、擴展性差等缺點不再適用于海量數據存儲。過去十年，為解決大數據存儲管理，Google相繼提出了全新的分布式計算理論MapReduce、GFS和BigTable[1-3]，隨后相應的開源分布式并行計算系統Hadoop、Spark應運而生。分布并行技術逐漸發展成熟，成為解決大數據管理的首選。與此同時，為處理大量半結構化、非結構化數據，NoSQL(Not Only SQL)數據庫迅速發展，涌現了大批如MongoDb、HBase、Neo4J這樣的NoSQL數據庫。信息網(INM)[4-5]模型是一種語義關聯模型，它基于對象模型和角色模型，支持無模式數據插入，可以自然地表示現實世界中的實體對象?；谶@樣的背景，本文在信息網模型的基礎上，研究并實現了基于無共享資源架構的分布式信息網數據庫管理系統，并針對分布式環境下的復雜多連接查詢處理設計了相應的優化算法。

在分布式信息網系統中，數據以對象為單位存儲在集群的各個節點上。查詢的數據往往分布在多個節點，因此查詢處理需要從多個節點獲取數據并整合，這個過程伴隨著昂貴的網絡通信開銷，涉及到大量連接操作的復雜查詢尤為突出。針對分布式環境下網絡通信的查詢優化問題，Bernstein等在早期提出了SDD-1算法[6]，該算法通過半連接操作降低網絡傳輸數據量。Wu等曾提出利用分布式環境的并行性生成查詢計劃，其執行結果與Hive系統按照順序執行的結果相比取得了較好的優化效果[7]。近幾年語義網發展迅速，Partout[8]、TriAD[9]、H2RDF+[10]、DREAM[11]等分布式RDF引擎先后被提出。這些引擎多基于MapReduce編程框架，充分利用框架函數Map()、Reduce()的并行性，通過將數據劃分算法與相應的查詢優化計劃相結合的方式完成高效的分布式SPARQL查詢。綜上所述，在分布式環境下利用執行計劃的并行性可以提高查詢效率。

然而，僅僅簡單地將查詢計劃并行并不能使查詢的效率達到最佳。由于缺少中間結果的篩選，網絡傳輸中存在大量冗余數據。大量的數據處理對控制節點的能力提出了挑戰，極易使控制節點成為限制查詢效率的瓶頸。此時，可以借助集中式存儲環境下復雜查詢多連接優化策略，利用中間結果對搜索空間的篩選作用，生成代價最小的執行計劃。在集中式存儲環境下，多連接查詢優化是極為經典的問題，經證明該問題是一個NP難(NP-hard)問題。Selinger等認為采用動態規劃算法可以獲取最優解[12]。然而當連接數量極大時，算法本身的執行效率較低。為了提高算法效率，目前啟發式算法、隨機搜索算法以及具有隨機高效等特點的模擬退火算法[13]、遺傳算法[14]、粒子群算法[15]先后被應用到了多連接查詢優化領域。

綜上所述，分布并行環境下查詢優化需要同時考慮并行性和網絡通信對查詢的影響?；谶@樣的考慮，本系統創新性地提出了最小通信量查詢劃分算法與多目標查詢優化算法。其中查詢劃分算法將復雜查詢劃分成多個PWOC子查詢，所有子查詢可近似無通信地并行執行。多目標優化算法將子查詢作為查詢計劃的基本操作，并將并行性和通信代價同時作為驅動目標，以傳統多目標加權算法結合貪心策略作為評估依據生成查詢計劃樹。最終系統基于TPC-H基準生成測試數據，將原始算法與優化算法進行了對比實驗，結果表明優化算法可以極大提高復雜查詢的效率。

1 背景介紹

本系統提出的查詢優化算法主要針對分布并行信息網模型DPINM(Distributed Parallel Information Networking Model)下的數據庫管理系統的查詢部分進行優化。DPINM是信息網模型(INM)的分布并行版本，下面分別對INM模型以及DPINM系統中查詢執行流程進行詳細說明。

1.1 INM

信息網模型不同于關系模型，它是一種基于角色、對象模型的新型數據庫模型，可以表示現實世界復雜的語義關聯。在信息網模型中，現實世界中的實體對應于數據庫中的對象，多個對象之間通過關聯建立聯系?；趯ο蠛完P聯，所有實體都可以用信息網簡單表示。如圖1所示，用INM表示TPC-H中供應商(supplier)、零件(part)、訂單(orders)等對象類之間的關聯。其中訂單與細項通過item關聯建立聯系，同理與客戶通過customer關聯建立聯系。

圖1 信息網數據模型

信息網模型的查詢語言是INM Query Language (IQL)。IQL結合了XQuery、OQL、Cyper等語言的特點，可以支持路徑查詢、結果構造、圖查詢等概念。第3節給出了5個IQL例子，IQL查詢分為查詢表達式和結果構造表達式兩部分。查詢表達式根據當前的查詢路徑，從一個對象或一類對象出發沿著關聯或屬性查找目標對象，并用變量保存查找的結果，整個結果最終以查詢樹的形式呈現。結果表達式對上一步得到的查詢樹重新整合，構造用戶希望的結果集合。

1.2 查詢系統架構

DPINM整體采用主/從式體系結構，集群中各個節點之間相互獨立。根據數據和查詢的劃分情況，Hammoud等提出過四種分布式RDF查詢系統模型[16]。本系統采用如圖2所示的Quadrant-III模型，該模型的特點是數據分散存儲于集群的各個節點，查詢語句也分成多個子查詢執行。整個系統的查詢處理架構如圖3所示，主要由控制器、通信通道和處理節點三部分構成。

圖2 Quadrant-III模型

圖3 DPINM系統查詢執行框架

1) 控制節點

左側的控制節點作為系統的入口，實現對外交互以及任務控制的功能。它負責接收用戶的操作指令，例如查詢語句，并對指令進行詞法語法解析。然后根據本地的統計信息調用查詢優化算法自動生成任務計劃并控制計劃的執行，整合結果并返回用戶指令的執行情況。

2) 通信通道

控制器與各個節點之間通過信息傳遞接口MPI(Message Passing Interface)完成通信。

3) 處理節點

右側的處理子節點等待控制器的事務請求，并結合本地數據、模式信息、索引信息在當前節點執行請求任務，并返回中間結果給控制器。處理節點之間可以相互通信，當某節點上查找的數據不存在時，可以向其他節點發出請求實時獲取。

2 DPINM查詢處理與優化

本節介紹最小通信量查詢劃分算法(MTQS)和多目標查詢優化算法(MOQO)的具體實現。其中MTQS算法將查詢劃分成多個近似無通信可并行的子查詢集，MOQO算法將子查詢作為查詢計劃的基本操作，利用多目標加權和貪心策略生成包含子查詢執行順序的查詢計劃樹。

2.1 統計信息

DPINM查詢優化算法需要借助數據的統計信息作為算法評估的基礎。本系統結合INM數據模型和IQL查詢的特點，設計了三種統計信息索引表，分別為模式統計表、對象統計表和關聯統計表。模式、對象和關聯是INM模型中實體的重要信息，也是IQL中最常出現的關聯有效信息。模式的概念與面向對象中的類相似，對象是類的一個具體實體，通過關聯將對象與對象聯系起來。IQL查詢處理是從某個源對象或某個模式出發沿著指定路徑查找目標對象的過程。例如查詢“大學中教授發表的論文”，此時需要從大學這個模式出發找到所有大學的對象，然后分別從每個大學對象出發，沿著“教學人員”//“教授”這個角色關聯路徑跳入“教授”目標對象再繼續往下查找。因此查詢處理過程中將涉及到多個對象之間的連接。DPINM以對象為單位劃分數據，IQL中通過關聯建立聯系的源對象與目標對象會存在未存放在同一處理節點的情況。此時如果有大量的目標對象未與源對象存放在一個處理節點，需要通過通信獲取的次數與數據傳輸量將劇增。因此統計信息以從IQL語句中獲取的有效信息(包括對象名、模式名、關系名)為索引，統計在這些已知條件下的源對象個數、目標對象個數，以及目標對象與源對象的數據分布情況。

其中模式統計表如表1所示，里面存放基于TPC-H數據下以模式為索引包含的對象個數、關聯名、目標對象個數以及缺對象率(該模式下通過關聯名建立聯系的目標對象與源對象未存放在同一節點的比率)。表2所示對象統計表從對象出發，統計當前對象的大小、關聯名、目標對象個數和缺對象率(從源對象出發該關聯下目標對象與源對象未存放在一個節點的比率)。最后表3給出了關聯統計表的內容，包括關聯名、關聯的源對象個數、目標對象個數及其缺對象率。統計表中統計對象個數與目標對象個數的目的是預估IQL處理過程中的處理復雜度與可能通信的次數。對象個數越多，需要匹配的次數就越多，需要跳對象獲取目標對象的概率增加，處理復雜度就越大。最后在計算缺對象數時是通過將目標對象數與缺對象率相乘得到的，缺對象數將在MTQS算法中作為評估因子。

統計信息從集群的所有子節點處獲取，存放在控制節點上。系統定時檢查數據更新日志，并對統計信息進行維護。

表1 模式統計索引表

表2 對象統計索引表

表3 關聯統計索引表

2.2 查詢劃分算法

復雜多連接查詢涉及多個對象，對該查詢的處理方式通常是將查詢劃分成多個子查詢再處理。最小通信量劃分算法的目的是將查詢劃分成多個近似PWOC的子查詢，避免子查詢執行過程中大量節點間通信的情況產生。

算法1給出了最小通信量劃分算法的描述，算法輸入分別是Qin和S，輸出是劃分后的子查詢集Qout。其中S是2.1節獲取的統計數據，Qin是按照查詢包含的對象類將查詢劃分成多個獨立的子查詢集，第3節中Q5根據查詢包含的7個對象類劃分之后的Qin為表4中的IQL Statement。

算法 1 MTQS

input:Qin,S

output:Qout

1.SearchStatistics(S);

2. foreachq∈Qindo

3.computeFactor(q,S,LO,LT,LM);

8.if(Vnet>threshold)

9. splitStatus.push_back(1);

10.else

11. splitStatus.push_back(0);

12. RecombineQuery(splitStatus,Qout);

13.returnQout;

表4 MTQS算法評估因子

算法對Qin中的每個子查詢循環預處理，首先根據查詢有效信息和S統計信息獲取評估查詢通信量的三個影響因子，分別是源對象數Lo、目標對象數LT、目標對象的缺對象數LM(未與源對象存放在同一節點的目標對象個數)。系統選取這三者作為影響因子，是因為這三個因子都影響查詢執行過程的效率。當源對象數Lo較大時，針對每個源對象需要完成一次路徑匹配過程，此時的查詢執行復雜度較大。同理，當目標對象數LT較大時，查詢需要循環匹配目標對象，處理執行時間長。前兩個因子主要從數據本身影響查詢效率的角度考慮，目標對象的缺對象數LM從網絡通信傳輸的角度考慮對查詢效率的影響。當缺對象數較大時需要多次與其他節點建立連接，獲取目標對象的具體信息，伴隨著較大的網絡傳輸開銷，同時也降低查詢效率。在確定查詢劃分成子查詢的切分點時，需要考慮上述三個因子對查詢效率的影響。當這些因子得到的綜合評估值超過閾值時，該查詢的復雜度較高，此時不應該連接后面的子查詢，增加跳對象次數與路徑處理長度。通過將查詢分成多個子查詢并行處理，分散查詢處理的難度可以適當地提高查詢效率。

w1+w2+w3=1

(1)

通過最小通信量劃分算法處理之后，輸入查詢集Qin轉換成輸出查詢集Qout，表4給出Qin中每個子查詢的三個影響因子以及根據因子計算的Vnet值。其中W1、W2、W3,threshold的值分別為0.25、0.25、0.5、0.3。在該例中W3權值較大，因此劃分處理時更多考慮跳對象網絡通信對查詢效率的影響。經過算法處理之后得到的輸出劃分結果為{q1: part ＄x/partsupp:＄y}、{q2: supplier＄y/lineitem:＄z}、{q3:lineitem ＄z/l_order:＄l}、{q4:order＄l/o_cust:＄m}、{q5: customer ＄m/c_nation:nation4/n_region:＄s/r_name:＄e}。

從結果可以看出表4的q5、q6、q7合并為一個子查詢，由于q5的目標對象已經確定為nation4，并且目標對象與源對象在同一節點，此時q5處理比較簡單適合直接連接q6繼續更加復雜的處理。

2.3 多目標查詢優化算法

通過MTQS得到的子查詢集合可以直接在系統中完全并行執行。但是所有子查詢只與控制節點通信，缺少相鄰子查詢間中間結果的篩選，網絡傳輸中會存在不必要數據的傳輸。例如查詢重點大學下的女教授，由于源對象“重點大學”到目標對象“教授”在同一節點的比例較小，因此MTQS算法會將其分成兩個子查詢，分別查重點大學下的教授和性別為女的教授。重點大學下的教授很多，女教授的對象數較少，如果先查性別為女的教授，再將結果賦值給前一個子查詢，那么可以減少大量不滿足條件的傳輸結果。因此當IQL涉及的對象數較多、對象較大時，不必要數據傳輸總量大，控制節點需要重組的數據集也較大，同樣也會降低查詢效率?；谏鲜隹紤]，本系統在查詢劃分算法的基礎之上創新性地提出了多目標查詢優化算法。該算法考慮子查詢執行的先后順序，利用多目標加權算法將并行性和通信開銷同時作為優化目標以生成更優的查詢計劃。下面將從代價估計和搜索算法兩個方面對算法進行描述。

1) 代價估計

集中式查詢優化算法將查詢中間結果作為衡量代價的唯一指標，生成的查詢計劃往往采用左深樹作為數據結構(如圖4(a)所示)。基于分布式環境，并行成為趨勢?，F有的并行框架如Map-Reduce，充分利用框架并行性，忽視了中間結果帶來的搜索空間縮小的優勢，造成網絡通信量的增大。因此，本系統結合查詢并行與順序執行各自的優勢，將并行性和通信開銷同時作為代價估計的目標，最終以濃密樹(如圖4(b)所示)的結構生成查詢計劃。

圖4 兩種查詢計劃樹

對一個連接R=q1∩q2，表示q1子查詢與q2子查詢的連接操作，其通信代價評估值cost(∩1)為:

cost(∩1)=q1×sizeof(q1)+q2×sizeof(q2)+

‖q1∩q2‖×sizeof(‖q1∩q2‖)

(2)

其中qi表示當前查詢對象的基數，sizeof(qi)表示qi查詢每個對象的大小，q1∩q2代表兩個查詢連接后得到中間對象個數，sizeof(q1∩q2)表示中間對象的大小。

當有n個子查詢連接時，一個查詢計劃的通信代價評估值COST為連接的代價估計總和，如下所示:

(3)

最終的查詢計劃將以濃密樹的形式構造。在濃密樹中從葉子節點向上反向處理，處于同一層的子查詢可以并行，但需要判斷與其連接的是中間結果還是相鄰子查詢。如果是中間結果需要等待中間結果返回后再執行，否則可以完全并行。查詢樹越深則并行度越低，因此查詢計劃并行性的評估值concurrency(R)為加入R=q1∩q2后，查詢計劃樹的高度。最終的并行性評估值CONCURRENCY如式(4)所示，為最終生成的查詢計劃樹的高度。

CONCURRENCY=concurrency(Rn)

(4)

2) 搜索算法

f1(x)=mincost(Ri)

(5)

f2(x)=minconcurrency(Ri)

(6)

F(x)=min{ρf1(x)+(1-ρ)f2(x)}

(7)

多目標優化算法的兩個目標分別是中間結果最小(利用查詢執行的先后順序縮小搜索空間)、并行度最大(查詢樹高度越小)。這兩個目標間存在矛盾，不能同時獲得目標的最優解，只能選擇兩個目標的平衡點作為最后的解。如式(5)-式(7)所示，系統采用傳統多目標加權優化算法[17]得到最終的優化公式F(x)，并以F(x)建模生成多目標貪心算法。F(x)將作為貪心算法每一步的評估標準找到當前最佳的計劃子樹。多目標貪心算法描述如算法2所示。

算法2 MOQO

input: sets of q1∩q2∩…∩qn+1,S

output: the tree of query plan TMOO

1. ∩set←{ ∩1,∩2…∩n}

2. while(∩set! = null)

3. int count=0;

4. foreach ∩iin ∩set do

5. ++ count;

6. cost(∩i)=‖qi‖×sizeof(qi)+‖qj‖×sizeof(qj)+

7. ‖qi∩qj‖×sizeof(qi∩qj);

8. concurrency(∩i)=height(TMOO,∩i);

9. endfor

10. sort the ∩cost and ∩concurrency

11. get the min ∩ievaluate:

13. ∩set←∩set-{∩i}

14. Put ∩ito TMOO

15. revise middle result

16. endwile

17. return TMOO

(8)

∩1:{q1∩q2} ∩2:{q2∩q3}…

∩n-1:{qn-1∩qn}

(9)

每一步貪心算法都會選擇當前評估值最優的連接加入到最終的查詢計劃樹中，此時的執行過程如下：對每個選擇的連接∩i，檢查∩i包含的子查詢是否已經存在于查詢計劃樹TMOO中。如果存在則找到子查詢的父節點，將父節點作為當前連接的子節點之一。如果不存在這樣的節點，則根據子查詢生成新的子節點。當連接左右節點都確定之后，生成新的父節點，將父節點的值置為連接之后中間結果的值。

下面以一個例子對算法進行詳細說明，Q5經過MTQS處理之后得到的5個查詢組成的子查詢集。這5個子查詢構成4個相鄰的連接，對每個連接根據表5給出的數據分析并行度和通信代價，依次選擇評估值最小的連接加入計劃樹，同時用中間結果修正對連接的影響，循環執行直到所有的連接都加入樹中為止。最后得到依次加入的順序為∩4、∩3、∩1、∩2，圖5給出了查詢計劃樹的生成過程。

表5 MOQO連接統計信息

圖5 查詢計劃樹生成過程

MOQO算法的創新之處在于同時考慮并行性和通信開銷對查詢計劃的影響，并且提出了使用多目標加權算法來對兩個目標值進行評估，旨在生成既能在一定程度上并行，同時又能結合中間結果縮小搜索空間的查詢計劃。

3 測試與分析

本系統將優化算法分別與改進前的原始算法、并行算法進行了對比。原始算法不對查詢進行預處理，直接將查詢分發到處理節點執行。處理過程中發生數據不存在當前節點的情況時，通過網絡通信從其他節點獲取之后繼續執行。并行算法僅執行論文中的MTQS算法，將查詢分成多個子查詢，所有子查詢完全并行，不考慮執行的先后順序。實驗平臺基于7臺配置相同的計算機組成的集群，每臺機器采用GenuineIntel x86_64，132 GB內存，Red Hat Enterprise Linux 6.4的系統配置，其中一臺為控制節點，剩余6臺為處理節點。系統的測試數據采用TPC-H基準自動生成，系統分別在8 GB(3 764 362個對象)和40 GB(19 951 872個對象)的數據集上進行測試。

表6給出了用于測試的查詢用例Q1-Q5，用例分別對應不同連接的查詢。系統分別從網絡傳輸數據量和查詢執行時間兩個方面對算法性能進行了衡量。表7給出了Q1-Q5在原始算法、并行算法和優化算法下網絡傳輸數據量的實驗數據。其中并行算法將所有子查詢完全并行，不考慮中間結果對查詢的優化作用。從表7可以看出，除Q1外，優化算法的網絡傳輸數據量介于原始算法與并行算法之間。Q1中連接數為1，查詢不需要從其他對象獲取數據，因此沒有中間結果，所有算法的網絡傳輸數據量相同。優化算法是對原始算法與并行算法的一種折中策略，采用的查詢計劃樹是一棵濃密樹，通過部分借助中間結果的優化作用，可以盡量減少網絡傳輸數據量，從表中可以看出優化算法相比于并行算法，除Q1外查詢網絡傳輸量從整體上減少了22.6%。雖然優化算法的網絡傳輸量比原始算法的傳輸量大，但是優化算法具有并行性，通過并行可以提高查詢效率。

圖6、圖7分別給出了原始算法、并行算法、優化算法在8 GB數據集和40 GB數據集下，查詢Q1-Q5的執行時間(單位為毫秒)。從圖中可以看出，優化算法與原始算法相比顯著提升了復雜查詢的執行效率。在8 GB數據集下，整體上提升了38.6%的查詢效率。隨著數據集的增大，優化算法的優勢更加明顯。在40 GB數據集下，整體提升查詢效率的幅度為49.4%。優化算法與并行算法相比較在連接數較少時執行時間幾乎一致。但隨著連接數的增加，此時查詢的執行順序帶來的縮小搜索空間的優勢開始顯示出來。

表6 IQL測試用例

表7 改進前后網絡傳輸量 MB

圖6 8 GB數據集算法改進前后效率對比

圖7 40 GB數據集算法改進前后效率對比

4 結 語

本文介紹了分布并行信息網數據管理系統的架構，并針對分布式環境下復雜多連接查詢存在大量通信開銷的問題，提出了最小通信量查詢劃分算法和多目標查詢優化算法。最小通信量查詢劃分算法旨在將復雜查詢劃分成多個可以并行執行的子查詢，算法通過統計信息的評估，劃分后的每個子查詢近似于PWOC子查詢，在通信量大的情況下不從其他處理節點通信獲取數據。多目標查詢優化算法在劃分算法的基礎之上，提出了以并行度和通信代價同時作為目標驅動，利用傳統多目標加權算法建模的查詢優化算法，算法的每一步都利用貪心算法選取當前通信代價與并行度最佳的連接操作加入到最終的查詢計劃樹。通過兩種算法的結合處理，最終系統可以生成并行度高、通信代價小的查詢計劃。最后，本文基于TPC-H基準生成測試數據，將查詢原始算法與優化算法的效率進行了對比，證明優化算法能顯著提高復雜查詢的效率，平均提升幅度為44%。

然而由于系統采用的是傳統多目標加權算法，得到的目標評估值存在主觀因素影響，不一定是Pareto最優解，得到的查詢計劃是近似最優解。采用貪心算法對濃密樹的搜索空間為不完全覆蓋。因此在下一步工作中，將考慮采用多目標遺傳算法或多目標粒子群算法作為多目標模型，并且結合動態規劃覆蓋所有搜索空間進一步優化查詢的性能。

[1] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1):107-113.

[2] Ghemawat S, Gobioff H, Leung S T. The Google file system[C]//ACM Symposium on Operating Systems Principles 2003, SOSP 2003, Bolton Landing, Ny, Usa, October. DBLP, 2003:29-43.

[3] Chang F, Dean J, Ghemawat S, et al. Bigtable:A Distributed Storage System for Structured Data[J]. Acm Transactions on Computer Systems, 2008, 26(2):1-26.

[4] Liu M, Hu J. Information Networking Model[M]//Conceptual Modeling-ER 2009. Springer Berlin Heidelberg, 2009:131-144.

[5] 胡捷, 劉夢赤. 信息網模型INM研究[M]. 科學出版社, 2011.

[6] Bernstein P A, Goodman N, Wong E, et al. Query processing in a system for distributed databases (SDD-1)[J]. ACM Transactions on Database Systems (TODS), 1981, 6(4): 602-625.

[7] Wu S, Li F, Mehrotra S, et al. Query optimization for massively parallel data processing[C]//Proceedings of the 2nd ACM Symposium on Cloud Computing. ACM, 2011: 12.

[8] Galarraga L, Hose K, Schenkel R. Partout: A distributed engine for efficient rdf processing[C]//Proceedings of the companion publication of the 23rd international conference on World wide web companion. International World Wide Web Conferences Steering Committee, 2014: 267-268.

[9] Gurajada S, Seufert S, Miliaraki I, et al. TriAD: a distributed shared-nothing RDF engine based on asynchronous message passing[C]//Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, 2014: 289-300.

[10] Papailiou N, Konstantinou I, Tsoumakos D, et al. H 2 RDF+: High-performance distributed joins over large-scale RDF graphs[C]//Big Data, 2013 IEEE International Conference on. IEEE, 2013: 255-263.

[11] Hammoud M, Rabbou D A, Nouri R, et al. DREAM: Distributed RDF engine with adaptive query planner and minimal communication[J]. Proceedings of the VLDB Endowment, 2015, 8(6):654-665.

[12] Selinger P G, Astrahan M M, Chamberlin D D, et al. Access path selection in a relational database management system[C]//Proceedings of the 1979 ACM SIGMOD international conference on Management of data. ACM, 1979:23-34.

[13] Ioannidis Y E, Wong E. Query optimization by simulated annealing[C]// Association for Computing Machinery Special Interest Group on Management of Data Conference. ACM, 1987:9-22.

[14] 曹陽, 方強, 王國仁, 等. 基于遺傳算法的多連接表達式并行查詢優化[J]. 軟件學報, 2002, 13(2):250-257.

[15] 林桂亞. 基于粒子群算法的數據庫查詢優化[J]. 計算機應用研究, 2012, 29(3): 974-975.

[16] Hammoud M, Rabbou D A, Nouri R, et al. DREAM: Distributed RDF engine with adaptive query planner and minimal communication[J]. Proceedings of the VLDB Endowment, 2015, 8(6): 654-665.

[17] 徐秉堃. 解多目標優化問題的改進加權求和算法[D].西安電子科技大學, 2010.

DISTRIBUTED PARALLEL MULTI-JOIN QUERY OPTIMIZATION IN INFORMATION NETWORK MODEL

Xu Jing1Liu Mengchi1,2

1(StateKeyLaboratoryofSoftwareEngineering,WuhanUniversity,Wuhan430072,Hubei,China)2(SchoolofComputerScience,WuhanUniversity,Wuhan430072,Hubei,China)

In the distributed cluster system, data is partitioned in different nodes according to data partition algorithm, which causes expensive network communication expense for the complex multi-join query. To solve the problem, the Minimum Traffic Query Split Algorithm(MTQS) and the Multi-Objective Query Optimization Algorithm (MOQO) based on the Information Network Model are proposed. Among these two algorithms, MTQS is aimed at splitting query into several parallelizable without communication (PWOC) sub-queries, which guarantees every sub-query parallels approximately without communication. MOQO takes sub-query as the basic operation, which puts the parallelism and communication cost as goal driven and builds the query plan tree combining the traditional Multi-Objective weighted algorithm with the greedy algorithm as the assessing accordance. In the end, the system generates test data by TPC-H benchmark and conducts a comparative experiment between the previous and optimal algorithm, the result proves that the optimal algorithm improves the efficiency of complex query significantly.

Query optimization Distributed parallel processing Multi-join Information Network Model(INM)

2016-08-19。國家自然科學基金項目(61672389，61202100)；軟件工程國家重點實驗室開放基金項目(SKLSE2012-09-20)。徐晶，碩士生，主研領域：新型數據庫理論，分布式查詢優化處理。劉夢赤，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.07.014