基于多核環境的并行性雙向枚舉連接

陳永恒，左祥麟

（吉林大學 計算機科學與技術學院，長春130012）

多核處理器先將多個完全功能的核心集成在同一芯片內，再將整個芯片作為統一的結構對外提供服務［1－2］.多核處理器先通過集成多個單線程處理核心或集成多個同時多線程處理核心，使整個處理器可同時執行的線程是單處理器的數倍，極大提升了處理器的并行性能［3－5］.

通過利用多核處理器框架，文獻［6］首次提出了并行查詢優化PDPsva算法，該算法主要是將連接對的生成和查詢計劃的生成進行分離，并為了避免查詢計劃生成過程中訪問連接對產生的沖突，依據連接對中關系的數量進行分組，從而將所有連接對轉換成偏序對，最后根據組間依賴和組內并行的特點，實現部分查詢計劃自底向上的多線程并行構建.因而PDPsva算法是以連接對中包含連接表的數目為驅動產生最優查詢計劃.而動態規劃算法DPccp［7］和DPhyp［8］通過直接遍歷查詢圖生成連接對，進一步優化解決了PDPsva算法中枚舉算法帶來的無效連接對問題.本文提出一種DPbid算法，該算法通過結合上述兩種方法的優點，實現了最優查詢計劃的并行化生成.

1 DPbid算法

基于自底向上動態規劃算法會產生大量不可連接的匹配連接對，而自頂向下枚舉算法的邏輯轉換是依據邏輯轉換規則隨機產生的，且每次都需使用查詢圖特性控制笛卡爾積的產生.針對兩種遍歷方式的優缺點，本文提出一種DPbid算法.

1.1 算法框架

DPbid算法包括如下3步：

1）通過圖遍歷構建公共表，該公共表對連接匹配的每個連接對進行編碼，從而提高了由上至下遍歷時的邏輯轉換效率，避免了成本較大的笛卡爾積運算；

2）采用自底向上動態規劃算法并行求解包含少于或等于兩個表部分解的最優計劃；

3）基于連接對及步驟2）中產生的部分最優解，執行自頂向下的動態規劃算法.

DPbid算法流程如下：

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

1.2 Partition分割

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

Partition算法流程如下：

CmpSub算法流程如下：

MinOptimistic算法流程如下：

所有連接的子圖都可以通過Partition算法實現.Partition算法先將每個節點入隊，對于隊列中每個節點｛v｝，通過調用MinOptimistic擴展該節點，從而取得更大的連接子圖，然后通過調用CmpSub獲得子圖的互補子圖.MinOptimistic是自調用遞歸函數，主要通過調用鄰接函數擴展節點，返回所有的連接子圖.若s是無向圖G的一個連接子圖，s′是N（s）的子集，則s∪s′是可連接的.MinOptimistic基于該理論為線索構造所有的連接子圖.CmpSub針對每個調用MinOptimistic產生連接子圖及互補連接子圖.

圖1 查詢圖GFig.1 Query graph G

例如，對如圖1所示的查詢圖G，利用partition和reorder函數，可得到圖2中的一個表.圖2包含了所有通過調用partition得到的連接對.這些連接對依據其包含連接表的多少進行分組和編碼.

圖2 連接對結構及編碼Fig.2 Join－pair structure and coding

1.3 自頂向下枚舉TopDownEnum

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

TopDownEnum算法流程如下：

Commutativity算法流程如下：

2 性能分析

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

表1 運行算法Table 1 Run algorithms

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

圖3 Chain查詢時3種算法的相對性能Fig.3 Relative performance of 3 algorithms for chain query

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

綜上所述，本文提出了雙向連接枚舉并行算法，該算法結合了傳統自底向上和自頂向下動態規劃算法的優點，利用圖遍歷得到的連接對公共表，采用雙向連接枚舉的并行算法，充分發揮多核環境的優勢，優化了傳統自頂向下的動態規劃算法中的邏輯轉換性能.實驗結果表明，該算法在時間和空間性能上都優于傳統算法.

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

圖6 Clique查詢時3種算法的相對性能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.