基于多核環(huán)境的并行性雙向枚舉連接

陳永恒，左祥麟

（吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012）

多核處理器先將多個(gè)完全功能的核心集成在同一芯片內(nèi)，再將整個(gè)芯片作為統(tǒng)一的結(jié)構(gòu)對(duì)外提供服務(wù)［1－2］.多核處理器先通過集成多個(gè)單線程處理核心或集成多個(gè)同時(shí)多線程處理核心，使整個(gè)處理器可同時(shí)執(zhí)行的線程是單處理器的數(shù)倍，極大提升了處理器的并行性能［3－5］.

通過利用多核處理器框架，文獻(xiàn)［6］首次提出了并行查詢優(yōu)化PDPsva算法，該算法主要是將連接對(duì)的生成和查詢計(jì)劃的生成進(jìn)行分離，并為了避免查詢計(jì)劃生成過程中訪問連接對(duì)產(chǎn)生的沖突，依據(jù)連接對(duì)中關(guān)系的數(shù)量進(jìn)行分組，從而將所有連接對(duì)轉(zhuǎn)換成偏序?qū)?，最后根?jù)組間依賴和組內(nèi)并行的特點(diǎn)，實(shí)現(xiàn)部分查詢計(jì)劃自底向上的多線程并行構(gòu)建.因而PDPsva算法是以連接對(duì)中包含連接表的數(shù)目為驅(qū)動(dòng)產(chǎn)生最優(yōu)查詢計(jì)劃.而動(dòng)態(tài)規(guī)劃算法DPccp［7］和DPhyp［8］通過直接遍歷查詢圖生成連接對(duì)，進(jìn)一步優(yōu)化解決了PDPsva算法中枚舉算法帶來的無效連接對(duì)問題.本文提出一種DPbid算法，該算法通過結(jié)合上述兩種方法的優(yōu)點(diǎn)，實(shí)現(xiàn)了最優(yōu)查詢計(jì)劃的并行化生成.

1 DPbid算法

基于自底向上動(dòng)態(tài)規(guī)劃算法會(huì)產(chǎn)生大量不可連接的匹配連接對(duì)，而自頂向下枚舉算法的邏輯轉(zhuǎn)換是依據(jù)邏輯轉(zhuǎn)換規(guī)則隨機(jī)產(chǎn)生的，且每次都需使用查詢圖特性控制笛卡爾積的產(chǎn)生.針對(duì)兩種遍歷方式的優(yōu)缺點(diǎn)，本文提出一種DPbid算法.

1.1 算法框架

DPbid算法包括如下3步：

1）通過圖遍歷構(gòu)建公共表，該公共表對(duì)連接匹配的每個(gè)連接對(duì)進(jìn)行編碼，從而提高了由上至下遍歷時(shí)的邏輯轉(zhuǎn)換效率，避免了成本較大的笛卡爾積運(yùn)算；

2）采用自底向上動(dòng)態(tài)規(guī)劃算法并行求解包含少于或等于兩個(gè)表部分解的最優(yōu)計(jì)劃；

3）基于連接對(duì)及步驟2）中產(chǎn)生的部分最優(yōu)解，執(zhí)行自頂向下的動(dòng)態(tài)規(guī)劃算法.

DPbid算法流程如下：

DPbid算法通過生成單表的最優(yōu)查詢計(jì)劃初始化全局解Memo，將連接對(duì)的生成和查詢計(jì)劃的生成進(jìn)行分離，Partition算法利用圖遍歷生成連接對(duì)，并對(duì)其進(jìn)行編碼.使用Reorder對(duì)生成的連接對(duì)分組，從而將所有連接對(duì)轉(zhuǎn)換成偏序?qū)?最后根據(jù)組間依賴和組內(nèi)并行的特點(diǎn)，DownUpQEPs實(shí)現(xiàn)部分查詢計(jì)劃自底向上的多線程并行構(gòu)建.根據(jù)不同的訪問路徑和連接方法，DownUpQEPs遞歸的從Group中訪問每個(gè)連接對(duì).對(duì)于生成的部分解QEP1和QEP2，如果QEP2的成本小于QEP1的成本，則PrunePlans剪枝掉QEP1，并利用全局變量Memo保存生成的最優(yōu)查詢計(jì)劃.

1.2 Partition分割

在自底向上和由上至下枚舉過程中，連接對(duì)的生成非常重要.Partition算法能產(chǎn)生避免笛卡爾積運(yùn)算的連接對(duì).

Partition算法流程如下：

CmpSub算法流程如下：

MinOptimistic算法流程如下：

所有連接的子圖都可以通過Partition算法實(shí)現(xiàn).Partition算法先將每個(gè)節(jié)點(diǎn)入隊(duì)，對(duì)于隊(duì)列中每個(gè)節(jié)點(diǎn)｛v｝，通過調(diào)用MinOptimistic擴(kuò)展該節(jié)點(diǎn)，從而取得更大的連接子圖，然后通過調(diào)用CmpSub獲得子圖的互補(bǔ)子圖.MinOptimistic是自調(diào)用遞歸函數(shù)，主要通過調(diào)用鄰接函數(shù)擴(kuò)展節(jié)點(diǎn)，返回所有的連接子圖.若s是無向圖G的一個(gè)連接子圖，s′是N（s）的子集，則s∪s′是可連接的.MinOptimistic基于該理論為線索構(gòu)造所有的連接子圖.CmpSub針對(duì)每個(gè)調(diào)用MinOptimistic產(chǎn)生連接子圖及互補(bǔ)連接子圖.

圖1 查詢圖GFig.1 Query graph G

例如，對(duì)如圖1所示的查詢圖G，利用partition和reorder函數(shù)，可得到圖2中的一個(gè)表.圖2包含了所有通過調(diào)用partition得到的連接對(duì).這些連接對(duì)依據(jù)其包含連接表的多少進(jìn)行分組和編碼.

圖2 連接對(duì)結(jié)構(gòu)及編碼Fig.2 Join－pair structure and coding

1.3 自頂向下枚舉TopDownEnum

TopDownEnum算法先檢測(cè)全局變量Memo，對(duì)于分解出的物理表達(dá)式G，如果其成本小于上限且Memo中存在其最優(yōu)查詢計(jì)劃，則返回最優(yōu)查詢計(jì)劃；否則，如果Memo中不存在其最優(yōu)解，則調(diào)用Commutativity.Commutativity利用構(gòu)建的連接對(duì)組Group實(shí)現(xiàn)邏輯表達(dá)式的進(jìn)一步等價(jià)邏輯分解變換.TopDownEnum算法中的MatchSearch用于實(shí)現(xiàn)這種邏輯分解變換.例如，對(duì)于圖2中Group［4］的R0R1R2，可利用遍歷Group［3］中LVA∪RVA為｛0，1，2｝的所有連接對(duì) QS實(shí)現(xiàn)其邏輯變換.

TopDownEnum算法流程如下：

Commutativity算法流程如下：

2 性能分析

下面將DPbid算法與使用LBUsize表示的自底向上動(dòng)態(tài)規(guī)劃PDPsva算法［6］及使用LDPbid表示的自頂向下動(dòng)態(tài)規(guī)劃算法進(jìn)行比較.表1列出了用于實(shí)驗(yàn)測(cè)試的3種算法.查詢類型分別針對(duì)chain，cycle，star和clique查詢圖，圖3～圖6為不同算法的相對(duì)時(shí)間.由于不同的查詢規(guī)模其優(yōu)化時(shí)間也不同，所以不同算法的性能比較都是以LDPbid為基準(zhǔn)進(jìn)行的，LDPbid的優(yōu)化時(shí)間是常數(shù)5.實(shí)驗(yàn)運(yùn)行于Windows Vista系統(tǒng)，且具有兩個(gè)Intel Xeon Quad Core E540 1.6GHz CPUs，8Gb物理內(nèi)存，每個(gè)CPU具有4Mb L2緩存.

表1 運(yùn)行算法Table 1 Run algorithms

針對(duì)chain查詢，圖3比較了LDPbid，LCTD和LBUsize算法的相對(duì)性能.由圖3可見，LDPbid算法總是優(yōu)于LCTD算法和LBUsize算法.而隨著查詢規(guī)模的增大，LBUsize算法會(huì)產(chǎn)生大量的笛卡爾積連接對(duì)，因而LBUsize算法性能下降最快.圖4～圖6的運(yùn)行結(jié)果與此類似.由于LDPbid算法產(chǎn)生的枚舉連接對(duì)明顯少于LCDT算法和LBUsize算法，因而其空間復(fù)雜度也明顯降低.

圖3 Chain查詢時(shí)3種算法的相對(duì)性能Fig.3 Relative performance of 3 algorithms for chain query

圖4 Star查詢時(shí)3種算法的相對(duì)性能Fig.4 Relative performance of 3 algorithms for star query

綜上所述，本文提出了雙向連接枚舉并行算法，該算法結(jié)合了傳統(tǒng)自底向上和自頂向下動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)，利用圖遍歷得到的連接對(duì)公共表，采用雙向連接枚舉的并行算法，充分發(fā)揮多核環(huán)境的優(yōu)勢(shì)，優(yōu)化了傳統(tǒng)自頂向下的動(dòng)態(tài)規(guī)劃算法中的邏輯轉(zhuǎn)換性能.實(shí)驗(yàn)結(jié)果表明，該算法在時(shí)間和空間性能上都優(yōu)于傳統(tǒng)算法.

圖5 Cycle查詢時(shí)3種算法的相對(duì)性能Fig.5 Relative performance of 3 algorithms for cycle query

圖6 Clique查詢時(shí)3種算法的相對(duì)性能Fig.6 Relative performance of 3 algorithms for clique query

［1］Banikazemi M，Poff D，Abali B.Pam：A Novel Performance／Power Aware Meta－Scheduler for Multi－core Systems［C］／／Proccedings of the 2008ACM／IEEE Conference on Supercomputing.Piscaraway：IEEE Press，2008：24－36.

［2］Sutter H，Larus J.Software and the Concurrency Revolution ［J］.Queue：Multiprocessors Que，2005，3（7）：54－62.

［3］ZHOU Jing－ren，Cieslewicz J，Ross K A，et al.Improving Database Performance on Simultaneous Multithreading Processors［C］／／Proccedings of the 31st International Conference on Very Large Data Bases.New York：ACM Press，2005：49－60.

［4］Stenstr?m P.Ipdps Panel：Is the Multi－core Roadmap Going to Live up to Its Promises［C］／／IEEE International Conference on Parallel and Distributed Processing Symposium.Piscaraway：IEEE Press，2007：14－15.

［5］Ailamaki A，Dewitt D J，Hill M D，et al.DBMSs on a Modern Processor：Where Does Time Go ［C］／／Proccedings of the 25th International Conference on Very Large Data Bases.New York：ACM Press，1999：266－277.

［6］Han Wook－Shin，Lee J.Dependency－Aware Reordering for Parallelizing Query Optimization in Multi－core CPUs［C］／／Proccedings of the 2009ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2009：45－58.

［7］Guido M，Thomas N.Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products ［C］／／Proceedings of the 32nd International Conference on Very Large Data Bases.New York：ACM Press，2006：930－941.

［8］Moerkotte G，Neumann T.Dynamic Programming Strikes Back ［C］／／Proceedings of the 2008ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2008：539－552.