徐 晶 劉夢(mèng)赤，2

1(武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室 湖北 武漢 430072)2(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072)

?

基于信息網(wǎng)模型的分布并行多連接查詢優(yōu)化

徐 晶1劉夢(mèng)赤1，2

1(武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室 湖北 武漢 430072)2(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072)

在分布式集群系統(tǒng)中，數(shù)據(jù)根據(jù)劃分算法存儲(chǔ)在集群的各個(gè)節(jié)點(diǎn)，這為涉及大量連接操作的復(fù)雜查詢帶來了昂貴的網(wǎng)絡(luò)開銷。針對(duì)該問題，基于信息網(wǎng)模型INM(Information Network Mode)，提出最小通信量查詢劃分算法和多目標(biāo)查詢優(yōu)化算法。其中查詢劃分算法將復(fù)雜查詢劃分成多個(gè)PWOC(parallelizable without communication)子查詢，所有子查詢可近似無通信地并行執(zhí)行。多目標(biāo)優(yōu)化算法將子查詢作為查詢計(jì)劃的基本操作，并將并行性和通信代價(jià)同時(shí)作為驅(qū)動(dòng)目標(biāo)，以傳統(tǒng)多目標(biāo)加權(quán)算法結(jié)合貪心策略作為評(píng)估依據(jù)生成查詢計(jì)劃樹。最后，系統(tǒng)基于TPC-H基準(zhǔn)生成測(cè)試數(shù)據(jù)，將原始算法與優(yōu)化算法進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果表明優(yōu)化算法可以極大提高復(fù)雜查詢的效率。

查詢優(yōu)化 分布并行處理 多連接 信息網(wǎng)模型(INM)

0 引 言

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

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

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

綜上所述，分布并行環(huán)境下查詢優(yōu)化需要同時(shí)考慮并行性和網(wǎng)絡(luò)通信對(duì)查詢的影響。基于這樣的考慮，本系統(tǒng)創(chuàng)新性地提出了最小通信量查詢劃分算法與多目標(biāo)查詢優(yōu)化算法。其中查詢劃分算法將復(fù)雜查詢劃分成多個(gè)PWOC子查詢，所有子查詢可近似無通信地并行執(zhí)行。多目標(biāo)優(yōu)化算法將子查詢作為查詢計(jì)劃的基本操作，并將并行性和通信代價(jià)同時(shí)作為驅(qū)動(dòng)目標(biāo)，以傳統(tǒng)多目標(biāo)加權(quán)算法結(jié)合貪心策略作為評(píng)估依據(jù)生成查詢計(jì)劃樹。最終系統(tǒng)基于TPC-H基準(zhǔn)生成測(cè)試數(shù)據(jù)，將原始算法與優(yōu)化算法進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果表明優(yōu)化算法可以極大提高復(fù)雜查詢的效率。

1 背景介紹

本系統(tǒng)提出的查詢優(yōu)化算法主要針對(duì)分布并行信息網(wǎng)模型DPINM(Distributed Parallel Information Networking Model)下的數(shù)據(jù)庫管理系統(tǒng)的查詢部分進(jìn)行優(yōu)化。DPINM是信息網(wǎng)模型(INM)的分布并行版本，下面分別對(duì)INM模型以及DPINM系統(tǒng)中查詢執(zhí)行流程進(jìn)行詳細(xì)說明。

1.1 INM

信息網(wǎng)模型不同于關(guān)系模型，它是一種基于角色、對(duì)象模型的新型數(shù)據(jù)庫模型，可以表示現(xiàn)實(shí)世界復(fù)雜的語義關(guān)聯(lián)。在信息網(wǎng)模型中，現(xiàn)實(shí)世界中的實(shí)體對(duì)應(yīng)于數(shù)據(jù)庫中的對(duì)象，多個(gè)對(duì)象之間通過關(guān)聯(lián)建立聯(lián)系?；趯?duì)象和關(guān)聯(lián)，所有實(shí)體都可以用信息網(wǎng)簡(jiǎn)單表示。如圖1所示，用INM表示TPC-H中供應(yīng)商(supplier)、零件(part)、訂單(orders)等對(duì)象類之間的關(guān)聯(lián)。其中訂單與細(xì)項(xiàng)通過item關(guān)聯(lián)建立聯(lián)系，同理與客戶通過customer關(guān)聯(lián)建立聯(lián)系。

圖1 信息網(wǎng)數(shù)據(jù)模型

信息網(wǎng)模型的查詢語言是INM Query Language (IQL)。IQL結(jié)合了XQuery、OQL、Cyper等語言的特點(diǎn)，可以支持路徑查詢、結(jié)果構(gòu)造、圖查詢等概念。第3節(jié)給出了5個(gè)IQL例子，IQL查詢分為查詢表達(dá)式和結(jié)果構(gòu)造表達(dá)式兩部分。查詢表達(dá)式根據(jù)當(dāng)前的查詢路徑，從一個(gè)對(duì)象或一類對(duì)象出發(fā)沿著關(guān)聯(lián)或?qū)傩圆檎夷繕?biāo)對(duì)象，并用變量保存查找的結(jié)果，整個(gè)結(jié)果最終以查詢樹的形式呈現(xiàn)。結(jié)果表達(dá)式對(duì)上一步得到的查詢樹重新整合，構(gòu)造用戶希望的結(jié)果集合。

1.2 查詢系統(tǒng)架構(gòu)

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

圖2 Quadrant-III模型

圖3 DPINM系統(tǒng)查詢執(zhí)行框架

1) 控制節(jié)點(diǎn)

左側(cè)的控制節(jié)點(diǎn)作為系統(tǒng)的入口，實(shí)現(xiàn)對(duì)外交互以及任務(wù)控制的功能。它負(fù)責(zé)接收用戶的操作指令，例如查詢語句，并對(duì)指令進(jìn)行詞法語法解析。然后根據(jù)本地的統(tǒng)計(jì)信息調(diào)用查詢優(yōu)化算法自動(dòng)生成任務(wù)計(jì)劃并控制計(jì)劃的執(zhí)行，整合結(jié)果并返回用戶指令的執(zhí)行情況。

2) 通信通道

控制器與各個(gè)節(jié)點(diǎn)之間通過信息傳遞接口MPI(Message Passing Interface)完成通信。

3) 處理節(jié)點(diǎn)

右側(cè)的處理子節(jié)點(diǎn)等待控制器的事務(wù)請(qǐng)求，并結(jié)合本地?cái)?shù)據(jù)、模式信息、索引信息在當(dāng)前節(jié)點(diǎn)執(zhí)行請(qǐng)求任務(wù)，并返回中間結(jié)果給控制器。處理節(jié)點(diǎn)之間可以相互通信，當(dāng)某節(jié)點(diǎn)上查找的數(shù)據(jù)不存在時(shí)，可以向其他節(jié)點(diǎn)發(fā)出請(qǐng)求實(shí)時(shí)獲取。

2 DPINM查詢處理與優(yōu)化

本節(jié)介紹最小通信量查詢劃分算法(MTQS)和多目標(biāo)查詢優(yōu)化算法(MOQO)的具體實(shí)現(xiàn)。其中MTQS算法將查詢劃分成多個(gè)近似無通信可并行的子查詢集，MOQO算法將子查詢作為查詢計(jì)劃的基本操作，利用多目標(biāo)加權(quán)和貪心策略生成包含子查詢執(zhí)行順序的查詢計(jì)劃樹。

2.1 統(tǒng)計(jì)信息

DPINM查詢優(yōu)化算法需要借助數(shù)據(jù)的統(tǒng)計(jì)信息作為算法評(píng)估的基礎(chǔ)。本系統(tǒng)結(jié)合INM數(shù)據(jù)模型和IQL查詢的特點(diǎn)，設(shè)計(jì)了三種統(tǒng)計(jì)信息索引表，分別為模式統(tǒng)計(jì)表、對(duì)象統(tǒng)計(jì)表和關(guān)聯(lián)統(tǒng)計(jì)表。模式、對(duì)象和關(guān)聯(lián)是INM模型中實(shí)體的重要信息，也是IQL中最常出現(xiàn)的關(guān)聯(lián)有效信息。模式的概念與面向?qū)ο笾械念愊嗨?，?duì)象是類的一個(gè)具體實(shí)體，通過關(guān)聯(lián)將對(duì)象與對(duì)象聯(lián)系起來。IQL查詢處理是從某個(gè)源對(duì)象或某個(gè)模式出發(fā)沿著指定路徑查找目標(biāo)對(duì)象的過程。例如查詢“大學(xué)中教授發(fā)表的論文”，此時(shí)需要從大學(xué)這個(gè)模式出發(fā)找到所有大學(xué)的對(duì)象，然后分別從每個(gè)大學(xué)對(duì)象出發(fā)，沿著“教學(xué)人員”//“教授”這個(gè)角色關(guān)聯(lián)路徑跳入“教授”目標(biāo)對(duì)象再繼續(xù)往下查找。因此查詢處理過程中將涉及到多個(gè)對(duì)象之間的連接。DPINM以對(duì)象為單位劃分?jǐn)?shù)據(jù)，IQL中通過關(guān)聯(lián)建立聯(lián)系的源對(duì)象與目標(biāo)對(duì)象會(huì)存在未存放在同一處理節(jié)點(diǎn)的情況。此時(shí)如果有大量的目標(biāo)對(duì)象未與源對(duì)象存放在一個(gè)處理節(jié)點(diǎn)，需要通過通信獲取的次數(shù)與數(shù)據(jù)傳輸量將劇增。因此統(tǒng)計(jì)信息以從IQL語句中獲取的有效信息(包括對(duì)象名、模式名、關(guān)系名)為索引，統(tǒng)計(jì)在這些已知條件下的源對(duì)象個(gè)數(shù)、目標(biāo)對(duì)象個(gè)數(shù)，以及目標(biāo)對(duì)象與源對(duì)象的數(shù)據(jù)分布情況。

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

統(tǒng)計(jì)信息從集群的所有子節(jié)點(diǎn)處獲取，存放在控制節(jié)點(diǎn)上。系統(tǒng)定時(shí)檢查數(shù)據(jù)更新日志，并對(duì)統(tǒng)計(jì)信息進(jìn)行維護(hù)。

表1 模式統(tǒng)計(jì)索引表

表2 對(duì)象統(tǒng)計(jì)索引表

表3 關(guān)聯(lián)統(tǒng)計(jì)索引表

2.2 查詢劃分算法

復(fù)雜多連接查詢涉及多個(gè)對(duì)象，對(duì)該查詢的處理方式通常是將查詢劃分成多個(gè)子查詢?cè)偬幚?。最小通信量劃分算法的目的是將查詢劃分成多個(gè)近似PWOC的子查詢，避免子查詢執(zhí)行過程中大量節(jié)點(diǎn)間通信的情況產(chǎn)生。

算法1給出了最小通信量劃分算法的描述，算法輸入分別是Qin和S，輸出是劃分后的子查詢集Qout。其中S是2.1節(jié)獲取的統(tǒng)計(jì)數(shù)據(jù)，Qin是按照查詢包含的對(duì)象類將查詢劃分成多個(gè)獨(dú)立的子查詢集，第3節(jié)中Q5根據(jù)查詢包含的7個(gè)對(duì)象類劃分之后的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算法評(píng)估因子

算法對(duì)Qin中的每個(gè)子查詢循環(huán)預(yù)處理，首先根據(jù)查詢有效信息和S統(tǒng)計(jì)信息獲取評(píng)估查詢通信量的三個(gè)影響因子，分別是源對(duì)象數(shù)Lo、目標(biāo)對(duì)象數(shù)LT、目標(biāo)對(duì)象的缺對(duì)象數(shù)LM(未與源對(duì)象存放在同一節(jié)點(diǎn)的目標(biāo)對(duì)象個(gè)數(shù))。系統(tǒng)選取這三者作為影響因子，是因?yàn)檫@三個(gè)因子都影響查詢執(zhí)行過程的效率。當(dāng)源對(duì)象數(shù)Lo較大時(shí)，針對(duì)每個(gè)源對(duì)象需要完成一次路徑匹配過程，此時(shí)的查詢執(zhí)行復(fù)雜度較大。同理，當(dāng)目標(biāo)對(duì)象數(shù)LT較大時(shí)，查詢需要循環(huán)匹配目標(biāo)對(duì)象，處理執(zhí)行時(shí)間長(zhǎng)。前兩個(gè)因子主要從數(shù)據(jù)本身影響查詢效率的角度考慮，目標(biāo)對(duì)象的缺對(duì)象數(shù)LM從網(wǎng)絡(luò)通信傳輸?shù)慕嵌瓤紤]對(duì)查詢效率的影響。當(dāng)缺對(duì)象數(shù)較大時(shí)需要多次與其他節(jié)點(diǎn)建立連接，獲取目標(biāo)對(duì)象的具體信息，伴隨著較大的網(wǎng)絡(luò)傳輸開銷，同時(shí)也降低查詢效率。在確定查詢劃分成子查詢的切分點(diǎn)時(shí)，需要考慮上述三個(gè)因子對(duì)查詢效率的影響。當(dāng)這些因子得到的綜合評(píng)估值超過閾值時(shí)，該查詢的復(fù)雜度較高，此時(shí)不應(yīng)該連接后面的子查詢，增加跳對(duì)象次數(shù)與路徑處理長(zhǎng)度。通過將查詢分成多個(gè)子查詢并行處理，分散查詢處理的難度可以適當(dāng)?shù)靥岣卟樵冃省?/p>

w1+w2+w3=1

(1)

通過最小通信量劃分算法處理之后，輸入查詢集Qin轉(zhuǎn)換成輸出查詢集Qout，表4給出Qin中每個(gè)子查詢的三個(gè)影響因子以及根據(jù)因子計(jì)算的Vnet值。其中W1、W2、W3,threshold的值分別為0.25、0.25、0.5、0.3。在該例中W3權(quán)值較大，因此劃分處理時(shí)更多考慮跳對(duì)象網(wǎng)絡(luò)通信對(duì)查詢效率的影響。經(jīng)過算法處理之后得到的輸出劃分結(jié)果為{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}。

從結(jié)果可以看出表4的q5、q6、q7合并為一個(gè)子查詢，由于q5的目標(biāo)對(duì)象已經(jīng)確定為nation4，并且目標(biāo)對(duì)象與源對(duì)象在同一節(jié)點(diǎn)，此時(shí)q5處理比較簡(jiǎn)單適合直接連接q6繼續(xù)更加復(fù)雜的處理。

2.3 多目標(biāo)查詢優(yōu)化算法

通過MTQS得到的子查詢集合可以直接在系統(tǒng)中完全并行執(zhí)行。但是所有子查詢只與控制節(jié)點(diǎn)通信，缺少相鄰子查詢間中間結(jié)果的篩選，網(wǎng)絡(luò)傳輸中會(huì)存在不必要數(shù)據(jù)的傳輸。例如查詢重點(diǎn)大學(xué)下的女教授，由于源對(duì)象“重點(diǎn)大學(xué)”到目標(biāo)對(duì)象“教授”在同一節(jié)點(diǎn)的比例較小，因此MTQS算法會(huì)將其分成兩個(gè)子查詢，分別查重點(diǎn)大學(xué)下的教授和性別為女的教授。重點(diǎn)大學(xué)下的教授很多，女教授的對(duì)象數(shù)較少，如果先查性別為女的教授，再將結(jié)果賦值給前一個(gè)子查詢，那么可以減少大量不滿足條件的傳輸結(jié)果。因此當(dāng)IQL涉及的對(duì)象數(shù)較多、對(duì)象較大時(shí)，不必要數(shù)據(jù)傳輸總量大，控制節(jié)點(diǎn)需要重組的數(shù)據(jù)集也較大，同樣也會(huì)降低查詢效率。基于上述考慮，本系統(tǒng)在查詢劃分算法的基礎(chǔ)之上創(chuàng)新性地提出了多目標(biāo)查詢優(yōu)化算法。該算法考慮子查詢執(zhí)行的先后順序，利用多目標(biāo)加權(quán)算法將并行性和通信開銷同時(shí)作為優(yōu)化目標(biāo)以生成更優(yōu)的查詢計(jì)劃。下面將從代價(jià)估計(jì)和搜索算法兩個(gè)方面對(duì)算法進(jìn)行描述。

1) 代價(jià)估計(jì)

集中式查詢優(yōu)化算法將查詢中間結(jié)果作為衡量代價(jià)的唯一指標(biāo)，生成的查詢計(jì)劃往往采用左深樹作為數(shù)據(jù)結(jié)構(gòu)(如圖4(a)所示)?；诜植际江h(huán)境，并行成為趨勢(shì)?，F(xiàn)有的并行框架如Map-Reduce，充分利用框架并行性，忽視了中間結(jié)果帶來的搜索空間縮小的優(yōu)勢(shì)，造成網(wǎng)絡(luò)通信量的增大。因此，本系統(tǒng)結(jié)合查詢并行與順序執(zhí)行各自的優(yōu)勢(shì)，將并行性和通信開銷同時(shí)作為代價(jià)估計(jì)的目標(biāo)，最終以濃密樹(如圖4(b)所示)的結(jié)構(gòu)生成查詢計(jì)劃。

圖4 兩種查詢計(jì)劃樹

對(duì)一個(gè)連接R=q1∩q2，表示q1子查詢與q2子查詢的連接操作，其通信代價(jià)評(píng)估值cost(∩1)為:

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

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

(2)

其中qi表示當(dāng)前查詢對(duì)象的基數(shù)，sizeof(qi)表示qi查詢每個(gè)對(duì)象的大小，q1∩q2代表兩個(gè)查詢連接后得到中間對(duì)象個(gè)數(shù)，sizeof(q1∩q2)表示中間對(duì)象的大小。

當(dāng)有n個(gè)子查詢連接時(shí)，一個(gè)查詢計(jì)劃的通信代價(jià)評(píng)估值COST為連接的代價(jià)估計(jì)總和，如下所示:

(3)

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

CONCURRENCY=concurrency(Rn)

(4)

2) 搜索算法

f1(x)=mincost(Ri)

(5)

f2(x)=minconcurrency(Ri)

(6)

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

(7)

多目標(biāo)優(yōu)化算法的兩個(gè)目標(biāo)分別是中間結(jié)果最小(利用查詢執(zhí)行的先后順序縮小搜索空間)、并行度最大(查詢樹高度越小)。這兩個(gè)目標(biāo)間存在矛盾，不能同時(shí)獲得目標(biāo)的最優(yōu)解，只能選擇兩個(gè)目標(biāo)的平衡點(diǎn)作為最后的解。如式(5)-式(7)所示，系統(tǒng)采用傳統(tǒng)多目標(biāo)加權(quán)優(yōu)化算法[17]得到最終的優(yōu)化公式F(x)，并以F(x)建模生成多目標(biāo)貪心算法。F(x)將作為貪心算法每一步的評(píng)估標(biāo)準(zhǔn)找到當(dāng)前最佳的計(jì)劃子樹。多目標(biāo)貪心算法描述如算法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)

每一步貪心算法都會(huì)選擇當(dāng)前評(píng)估值最優(yōu)的連接加入到最終的查詢計(jì)劃樹中，此時(shí)的執(zhí)行過程如下：對(duì)每個(gè)選擇的連接∩i，檢查∩i包含的子查詢是否已經(jīng)存在于查詢計(jì)劃樹TMOO中。如果存在則找到子查詢的父節(jié)點(diǎn)，將父節(jié)點(diǎn)作為當(dāng)前連接的子節(jié)點(diǎn)之一。如果不存在這樣的節(jié)點(diǎn)，則根據(jù)子查詢生成新的子節(jié)點(diǎn)。當(dāng)連接左右節(jié)點(diǎn)都確定之后，生成新的父節(jié)點(diǎn)，將父節(jié)點(diǎn)的值置為連接之后中間結(jié)果的值。

下面以一個(gè)例子對(duì)算法進(jìn)行詳細(xì)說明，Q5經(jīng)過MTQS處理之后得到的5個(gè)查詢組成的子查詢集。這5個(gè)子查詢構(gòu)成4個(gè)相鄰的連接，對(duì)每個(gè)連接根據(jù)表5給出的數(shù)據(jù)分析并行度和通信代價(jià)，依次選擇評(píng)估值最小的連接加入計(jì)劃樹，同時(shí)用中間結(jié)果修正對(duì)連接的影響，循環(huán)執(zhí)行直到所有的連接都加入樹中為止。最后得到依次加入的順序?yàn)椤?、∩3、∩1、∩2，圖5給出了查詢計(jì)劃樹的生成過程。

表5 MOQO連接統(tǒng)計(jì)信息

圖5 查詢計(jì)劃樹生成過程

MOQO算法的創(chuàng)新之處在于同時(shí)考慮并行性和通信開銷對(duì)查詢計(jì)劃的影響，并且提出了使用多目標(biāo)加權(quán)算法來對(duì)兩個(gè)目標(biāo)值進(jìn)行評(píng)估，旨在生成既能在一定程度上并行，同時(shí)又能結(jié)合中間結(jié)果縮小搜索空間的查詢計(jì)劃。

3 測(cè)試與分析

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

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

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

表6 IQL測(cè)試用例

表7 改進(jìn)前后網(wǎng)絡(luò)傳輸量 MB

圖6 8 GB數(shù)據(jù)集算法改進(jìn)前后效率對(duì)比

圖7 40 GB數(shù)據(jù)集算法改進(jìn)前后效率對(duì)比

4 結(jié) 語

本文介紹了分布并行信息網(wǎng)數(shù)據(jù)管理系統(tǒng)的架構(gòu)，并針對(duì)分布式環(huán)境下復(fù)雜多連接查詢存在大量通信開銷的問題，提出了最小通信量查詢劃分算法和多目標(biāo)查詢優(yōu)化算法。最小通信量查詢劃分算法旨在將復(fù)雜查詢劃分成多個(gè)可以并行執(zhí)行的子查詢，算法通過統(tǒng)計(jì)信息的評(píng)估，劃分后的每個(gè)子查詢近似于PWOC子查詢，在通信量大的情況下不從其他處理節(jié)點(diǎn)通信獲取數(shù)據(jù)。多目標(biāo)查詢優(yōu)化算法在劃分算法的基礎(chǔ)之上，提出了以并行度和通信代價(jià)同時(shí)作為目標(biāo)驅(qū)動(dòng)，利用傳統(tǒng)多目標(biāo)加權(quán)算法建模的查詢優(yōu)化算法，算法的每一步都利用貪心算法選取當(dāng)前通信代價(jià)與并行度最佳的連接操作加入到最終的查詢計(jì)劃樹。通過兩種算法的結(jié)合處理，最終系統(tǒng)可以生成并行度高、通信代價(jià)小的查詢計(jì)劃。最后，本文基于TPC-H基準(zhǔn)生成測(cè)試數(shù)據(jù)，將查詢?cè)妓惴ㄅc優(yōu)化算法的效率進(jìn)行了對(duì)比，證明優(yōu)化算法能顯著提高復(fù)雜查詢的效率，平均提升幅度為44%。

然而由于系統(tǒng)采用的是傳統(tǒng)多目標(biāo)加權(quán)算法，得到的目標(biāo)評(píng)估值存在主觀因素影響，不一定是Pareto最優(yōu)解，得到的查詢計(jì)劃是近似最優(yōu)解。采用貪心算法對(duì)濃密樹的搜索空間為不完全覆蓋。因此在下一步工作中，將考慮采用多目標(biāo)遺傳算法或多目標(biāo)粒子群算法作為多目標(biāo)模型，并且結(jié)合動(dòng)態(tài)規(guī)劃覆蓋所有搜索空間進(jìn)一步優(yōu)化查詢的性能。

[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] 胡捷, 劉夢(mèng)赤. 信息網(wǎng)模型INM研究[M]. 科學(xué)出版社, 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] 曹陽, 方強(qiáng), 王國(guó)仁, 等. 基于遺傳算法的多連接表達(dá)式并行查詢優(yōu)化[J]. 軟件學(xué)報(bào), 2002, 13(2):250-257.

[15] 林桂亞. 基于粒子群算法的數(shù)據(jù)庫查詢優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用研究, 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] 徐秉堃. 解多目標(biāo)優(yōu)化問題的改進(jìn)加權(quán)求和算法[D].西安電子科技大學(xué), 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。國(guó)家自然科學(xué)基金項(xiàng)目(61672389，61202100)；軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目(SKLSE2012-09-20)。徐晶，碩士生，主研領(lǐng)域：新型數(shù)據(jù)庫理論，分布式查詢優(yōu)化處理。劉夢(mèng)赤，教授。

TP3

A

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