張晨煜, 劉文潔, 龐天澤, 岳艷濤

(1.西北工業(yè)大學 計算機學院, 陜西 西安 710129; 2.交通銀行, 上海 200120)

隨著互聯(lián)網(wǎng)的發(fā)展和數(shù)據(jù)量的不斷激增，分布式數(shù)據(jù)庫已經(jīng)逐漸取代單機數(shù)據(jù)庫，成為金融、互聯(lián)網(wǎng)等行業(yè)應用的主流存儲系統(tǒng)。

在當前的數(shù)據(jù)庫使用中，讀操作占了數(shù)據(jù)庫操作的大多數(shù)，反映到SQL語句中即查詢語句被經(jīng)常使用。將一個由SELECT-FROM-WHERE組成的結構稱為查詢塊，對于一個查詢塊作為另一個查詢塊的查詢條件嵌套在其中的語句，稱為子查詢[1]。目前對于子查詢的執(zhí)行，如果是不依賴于父查詢的非相關子查詢，實現(xiàn)比較簡單，只需先對子查詢進行處理，將結果與父查詢綁定后執(zhí)行父查詢，由內(nèi)向外每個查詢只需要執(zhí)行一次。但對于依賴于父查詢的相關子查詢，需要先對父查詢計算，對于父查詢結果中的每一個元組，都需要將其重寫到子查詢中進行一次子查詢的計算。這種執(zhí)行策略使得相關子查詢的執(zhí)行會隨著父查詢元組數(shù)的增多而增長，對于嵌套層次更多的復雜相關子查詢，時間開銷將會是指數(shù)級增加。同時，在分布式數(shù)據(jù)庫環(huán)境中，這種執(zhí)行策略還會增加數(shù)據(jù)通信的時間開銷。

子查詢?yōu)镾QL查詢提供了更為豐富的表達能力，在數(shù)據(jù)庫使用當中，大多數(shù)查詢語句都含有子查詢，比如在TPC-H基準測試中就含有近乎一半的子查詢語句。因此，對于相關子查詢進行性能優(yōu)化，對于分布式數(shù)據(jù)庫的高效執(zhí)行有著重要的作用。

現(xiàn)有的查詢優(yōu)化主要是基于2個方面進行，即基于規(guī)則的查詢優(yōu)化和基于代價的查詢優(yōu)化。基于規(guī)則的研究一般是通過重寫查詢計劃，去除查詢的嵌套性來降低復雜度和子查詢的執(zhí)行次數(shù)來提高性能，基于代價的研究則是根據(jù)統(tǒng)計信息來進行查詢計劃的代價計算，選擇代價最小的查詢方案。

CBase 是西北工業(yè)大學聯(lián)合交通銀行、華東師范大學研發(fā)的分布式關系數(shù)據(jù)庫，基于阿里巴巴的OceanBase0.4.2，目前已經(jīng)在交通銀行上線應用[2-4]。CBase目前僅僅支持部分相關子查詢，且性能不佳。本文在對現(xiàn)有的查詢優(yōu)化策略進行分析研究的基礎上，結合分布式數(shù)據(jù)庫的特點，以查詢重寫為主，設計了相關子查詢的優(yōu)化策略，在CBase上實現(xiàn)了對于謂詞IN和EXISTS相關子查詢的上拉、無用分支切除和聚集函數(shù)消除的優(yōu)化。

1 相關研究

1.1 基于規(guī)則的研究

對于子查詢，按照關鍵字的不同，可以劃分為3類：①IN為標志的集合成員查詢；②ANY/SOME/ALL關鍵詞引導的比較查詢；③以EXISTS為關鍵詞的空判斷查詢。

對于這三類子查詢，均可以等價為EXISTS語義的查詢。在MySQL的研究中，將以IN為關鍵詞的子查詢，轉(zhuǎn)換成了同義的EXISTS語句。該轉(zhuǎn)換策略主要思路是將IN查詢相關的列轉(zhuǎn)換為EXISTS子句的等值過濾條件，遵循如下轉(zhuǎn)換規(guī)則：

對于原有的IN查詢：

SELECT C1 FROM T1 WHERE C2 IN (SELECT A1 FROM T2 WHERE T1.C3=T2.C3);

可以將其轉(zhuǎn)換成等價的EXISTS語義的語句：

SELECT C1 FROM T1 WHERE EXISTS(SELECT 1 FROM T2 WHERE T1.C3=T2.C2 AND T1.C2 = T2.A1);

不同于其他子查詢需要掃描全表，EXISTS子查詢只需要取一次查詢結果進行空判斷。相較于其他的子查詢，EXISTS子查詢是一種最優(yōu)的子查詢，因此在MySQL中，對于IN子查詢的優(yōu)化，采取了和EXISTS謂詞相似的策略：

1) 查詢展開，將子查詢上拉；

2) 消除冗余子樹；

3) 在相關列上構建索引。

而在Oracle的研究當中，Oracle對子查詢的優(yōu)化處理也采用了反嵌套的思想，主要包括了2種類型的反嵌套，一種是生成派生表，另一種是合并子查詢。接下來，將詳細地討論以上幾種優(yōu)化策略的思想。

1.1.1 子查詢上拉

一個相關的IN/EXISTS子查詢在語義上等價于一個半連接查詢語句，將父查詢塊與子查詢塊的表格在父查詢中做半連接操作，以子查詢塊中與父查詢塊相關的過濾條件作為連接條件，如果是IN子查詢則IN引導的列也將作為連接條件。根據(jù)這一理論，Bellamkonda等[5]提出了將相關子查詢上拉展開為同語義的半連接查詢的優(yōu)化策略，通過對子查詢的執(zhí)行計劃進行上拉，可以將子查詢的嵌套層數(shù)減少一層，減少了相關子查詢執(zhí)行時需要多次運算子查詢的時間，提高了查詢性能。

但是這種優(yōu)化策略對于待處理的子查詢語句有著一定的限制，對于子查詢中含有聚集函數(shù)、with子句、子查詢的FROM項為空或EXISTS子查詢的WHERE項為空時，將無法采用這種優(yōu)化策略。

將子查詢上拉為內(nèi)連接相較于轉(zhuǎn)換為半連接的策略，只解決了聚焦函數(shù)造成的優(yōu)化限制，對于其余限制條件仍不能解決。

以上2種優(yōu)化的主要思想基本上是一致的，都是對于待優(yōu)化的相關子查詢的查詢計劃中的父子查詢塊的FROM項進行連接，作為父查詢的FROM，再將子查詢塊WHERE中的過濾條件中與父表相關的屬性作為連接屬性上拉，并用AND連接，其余的子查詢過濾條件則依次填充進父查詢塊的WHERE中，對于IN相關子查詢，需要將IN相關的屬性改為“=”關系填充進連接條件，額外的，如果要轉(zhuǎn)換為內(nèi)連接查詢，可能會有重復的結果出現(xiàn)，需要進行投影運算去重。在效果上，2種方法也是基本一致的，都是將子查詢的嵌套層數(shù)減去了內(nèi)部的一層，減少了子查詢塊多次執(zhí)行的時間開銷。

1.1.2 冗余子樹切除

對于相關子查詢來說，由于IN相關子查詢可以通過轉(zhuǎn)換變?yōu)檎Z義等價的EXISTS相關子查詢，因此，對于子查詢中的一些限制子句的處理，可以按照EXISTS的語義進行考慮。EXISTS的語義對于子查詢的結果只判斷是否為空，并不關心結果中的順序等具體內(nèi)容，所以子查詢中的排序、去重等都是對于查詢結果毫無貢獻的無用操作，去除掉這些子句可以減少查詢計劃的內(nèi)容，切除子樹的規(guī)則如下：

例：原句為：

SELECT C1 FROM T1 WHERE C2 IN (SELECT DISTINCT(A1) FROM T2 WHERE T1.C3=T2.C3 ORDER BY (A2) GROUP BY(A3));

優(yōu)化后為：

SELECT C1 FROM T1 WHERE C2 IN (SELECT A1 FROM T2 WHERE T1.C3=T2.C3);

對于子句中的DINSTINCT、GROUP BY、ORDER BY謂詞都可以切除以減少查詢計劃的路徑長度，縮短時間開銷。

1.1.3 相關列構建索引

對于相關子查詢的優(yōu)化，除了可以通過規(guī)則優(yōu)化減少子查詢的執(zhí)行次數(shù)外，Shioi等[7]提出了通過在WHERE項的屬性上建立索引的方式來提升子查詢執(zhí)行的性能。這種優(yōu)化策略，在子表數(shù)據(jù)量很大的情況下，可以大大縮短對子表訪問所造成的時間開銷，縮短查詢時間。

1.1.4 子查詢合并

子查詢合并技術[5]指的是對于一個查詢語句中，由AND或者OR謂詞連接的多個子查詢，可以在一定條件下將其合并為一個子查詢，從而減少對表的訪問次數(shù)。

如果一個子查詢的結果集包含了另一個查詢塊的結果集，將其稱為容器查詢塊，另一個稱為包含查詢塊。對于同類型的2個子查詢，如果滿足包含關系，那么保留容器查詢塊，刪去包含查詢塊。

當子查詢塊之間不滿足包含與被包含的關系時，可以將具有等價語義的語義合并，并將其余下等非的條件合取或析取，使之成為一個子查詢。

如果2個子查詢塊存在包含與被包含的關系，但是2個查詢塊類型不同。假定EXISTS是容器子查詢塊，需要在合并后引入一個HAVING子句，將滿足NOT EXISTS條件的查詢結果返回值設為0，模擬其篩選過程。

1.1.5 聚集函數(shù)消除

對于聚集函數(shù)的處理策略是比較復雜的，在這里只討論了一些簡單的處理策略。在EXISTS中對于聚集函數(shù)的一些處理是簡單的。由于EXISTS子查詢的返回結果只是是否為空，而對于聚集函數(shù)的運算來說，無論是否有滿足過濾條件的行，都會返回一個運算結果，即使是沒有滿足子查詢過濾條件的元組，也會返回一個0或者NULL的結果，而非空結果，這就說明聚集函數(shù)在EXISTS的子句中是返回一個恒為TRUE的值的，即子查詢恒成立，所以可以將含有聚集函數(shù)的子查詢刪去，減少子查詢的執(zhí)行。

例：

SELECT * FROM T1 WHERE T1.C2=1 AND EXISTS(SELECT COUNT (*) FROM T2 WHERE T1.C1=T2.C1);

優(yōu)化后的結果為：

SELECT * FROM T1 WHERE T1.C2=1;

這種優(yōu)化策略刪去了對結果毫無影響的含有聚集函數(shù)的子查詢，消去了子查詢執(zhí)行的時間，在面對可優(yōu)化的情況下，性能比較顯著，但是可優(yōu)化的類型比較局限。

1.2 基于代價的研究

基于代價的優(yōu)化需要引入統(tǒng)計信息、直方圖等的功能[8-10]?；诖鷥r的優(yōu)化需要統(tǒng)計信息提供的關于表的相關信息，預先的估算查詢可用的若干計劃的可能開銷，從中選擇出代價最小的執(zhí)行方案執(zhí)行。

由于本文暫時只考慮了基于規(guī)則的優(yōu)化設計，所以在此對于目前基于代價的研究只進行簡單的討論。

在商業(yè)數(shù)據(jù)庫DBMS-X[11]中提出了一種名為位向量過濾器的優(yōu)化措施。這種優(yōu)化主要用于哈希連接，在哈希連接各個表的連接操作符處創(chuàng)建位向量過濾器，并將其下推到計劃中可能與該操作符涉及到的表相關的表或者其他位向量過濾器上。位向量過濾器的應用并非對已經(jīng)過代價計算選擇出的最優(yōu)計劃直接添加維向量過濾器，而是在代價計算中直接考慮了維向量過濾器的影響。因為相關的實驗已表明，在考慮了維向量過濾器后生成的查詢計劃的代價，遠小于對最優(yōu)計劃添加維向量過濾器后的代價，這也就說明，對于位向量過濾器的考慮，需要在基于代價的優(yōu)化過程中進行，而位向量過濾器的引入，也可能破壞了最優(yōu)子計劃的原則，破壞了現(xiàn)有的動態(tài)規(guī)劃框架，因為考慮位向量過濾器的最小代價計劃，在刪去位向量過濾器后，代價可能是高于不考慮位向量過濾器的情況下生成的執(zhí)行計劃的。

在Postgre SQL[12]中，提出了一種子查詢計劃重用的方法，來提高動態(tài)規(guī)劃得出最優(yōu)執(zhí)行計劃的代價。其主要思想是優(yōu)化了得出最優(yōu)執(zhí)行計劃的計算開銷和空間開銷。這種策略允許了子查詢在搜索空間中共享相似子查詢的查詢計劃。這種優(yōu)化策略的主要思想在于將每個查詢抽象成一個與之對應的圖，并且生成他的子圖覆蓋集，對于后來的查詢，在子圖覆蓋集中發(fā)現(xiàn)與之同構的子圖，共享對應的查詢計劃。而生成子圖覆蓋集是一個內(nèi)存密集的運算，在該研究中，對于覆蓋集的生成也進行了優(yōu)化，減少了內(nèi)存開銷。

1.3 分布式系統(tǒng)中的優(yōu)化

分布式數(shù)據(jù)庫系統(tǒng)與集中式數(shù)據(jù)庫系統(tǒng)之間查詢代價的差異，主要體現(xiàn)在查詢代價的構成上。傳統(tǒng)的集中式數(shù)據(jù)庫，查詢代價由CPU執(zhí)行時間與I/O構成。而分布式數(shù)據(jù)庫由于各個節(jié)點分布在網(wǎng)絡當中，除了基礎的CPU時間和I/O外，還有各個節(jié)點之間的網(wǎng)絡通信耗時。所以分布式數(shù)據(jù)庫在優(yōu)化策略的設計上，除了結合自身分布式特點的策略外，還借鑒了傳統(tǒng)的數(shù)據(jù)庫。

分布式數(shù)據(jù)庫的查詢優(yōu)化主要考慮2個方面：減少查詢耗時和通過分布式特點并行處理查詢。

查詢耗時的優(yōu)化主要是通過對查詢路徑的優(yōu)化減少磁盤塊的傳遞次數(shù)和對掃描次數(shù)進行優(yōu)化減少對磁盤塊的掃描次數(shù)[13]。這一目標的優(yōu)化方案通常借鑒了傳統(tǒng)數(shù)據(jù)庫的方法，對邏輯計劃和物理計劃進行優(yōu)化。

而并行處理則是結合了分布式的特點，提出了一種以操作符為中心的數(shù)據(jù)流模型[14]，將生成的查詢計劃按照操作符進行拆分，每個操作符都對應一個引擎，分發(fā)到各個服務器進行計算，最后將結果合并。通過較低的計算代價和數(shù)據(jù)冗余存儲換取高昂的網(wǎng)絡開銷，把一個查詢分到數(shù)據(jù)節(jié)點上進行并發(fā)查詢，最后在主節(jié)點融合數(shù)據(jù)結果，使得總體響應時間很短。同時，考慮到查詢批處理[10]的情況，對于每個引擎設置了一個可以接受的延遲時間，將若干查詢中對于同一個服務器的數(shù)據(jù)請求整合起來進行訪問，減少了多次訪問數(shù)據(jù)造成的網(wǎng)絡開銷。

2 算法實現(xiàn)

對于分布式數(shù)據(jù)庫優(yōu)化的2個目標，本文主要關注于第一個目標，減少查詢時間消耗，參考傳統(tǒng)數(shù)據(jù)庫對于查詢優(yōu)化的一些思想，進行基于規(guī)則的優(yōu)化。

本文的思想是通過聚集函數(shù)消除和切除子查詢中的無用子樹，優(yōu)化查詢路徑，減少磁盤塊的傳遞次數(shù)，減少各服務站點之間的網(wǎng)絡開銷。通過將相關子查詢上拉為連接查詢，減少對子查詢表的掃描次數(shù)和反復將子表數(shù)據(jù)傳輸?shù)木W(wǎng)絡開銷。

2.1 實現(xiàn)背景介紹

本文的研究環(huán)境基于分布式數(shù)據(jù)庫CBASE，其架構中分為4類服務器，分別是：RootServer、ChunkServer、MergeServer和UpdateServer 。數(shù)據(jù)包括基準數(shù)據(jù)和增量數(shù)據(jù)，基準數(shù)據(jù)存儲在ChunkServer中，增量數(shù)據(jù)存儲在UpdateServer 中，對于查詢的處理，將從MergeServer收到查詢請求后，根據(jù)RootServer上的信息，訪問相關的ChunkServer和UpdateServer 的數(shù)據(jù)，在MergeServer上合并后返回給用戶。對于查詢表的訪問，除了含有主鍵的查詢會采用GET方法直接訪問表中的對應元組外，其他的過濾條件都將采用SCAN的方式逐行掃描查詢表中的元組。這就導致了被訪問的表的元組數(shù)越多，時間開銷越大。在面對嵌套查詢的時候，多次訪問子表將會造成極大的時間開銷。

在目前的CBASE環(huán)境中，只支持了EXISTS的子查詢功能和IN的非相關子查詢功能，本文參考MySQL中的轉(zhuǎn)換規(guī)則實現(xiàn)IN相關子查詢并對IN和EXISTS相關子查詢進行優(yōu)化。

2.2 現(xiàn)有IN子查詢執(zhí)行策略

本文將詳細討論并實現(xiàn)IN相關子查詢的方法，并介紹在未優(yōu)化的情況下IN相關子查詢與EXISTS相關子查詢的執(zhí)行方法。

對于IN相關子查詢，考慮可以通過轉(zhuǎn)換現(xiàn)有的執(zhí)行計劃，使其成為等價的EXISTS相關子查詢，轉(zhuǎn)換的普遍規(guī)則如下：

原查詢：

SELECT expr FROM TABLE-1 WHERE outexpr1,outexpr2,…,outexprn IN(SELECT innerexpr1,innnerexpr2,…,innerexprn FROM TABLE-2 WHERE where-expr);

轉(zhuǎn)換后查詢：

SELECT expr FROM TABLE-1 WHERE EXISTS (SELECT 1 FROM TABLE-2 WHERE where-expr AND outexpr1=innerexpr1 AND outexpr2=innerexpr2…AND outexprn=innerexprn);

由于EXISTS子查詢的返回結果只是空與非空，對具體內(nèi)容并不關心，所以子查詢的目標并不需要指定，為1即可， 保留原有的子查詢的過濾條件，將原有查詢中IN相關的屬性一一對應改為“=”作為子查詢的新過濾條件。

這是最為普遍的轉(zhuǎn)換方法，額外的，需要討論被轉(zhuǎn)換的查詢中，IN相關的屬性允許為NULL值的情況。

當innerexpr可能為NULL值時，在添加過濾條件outexpr = innerexpr時，要析取一個判斷innerexpr IS NULL，將析取后的結果作為過濾條件添加進子查詢的WHERE中。假設innerexpr1可能為NULL，

例：

SELECT expr FROM TABLE-1 WHERE EXISTS(SELECT 1 FROM TABLE-2 WHERE where-expr AND(outexpr1=innerexpr1 OR innerexpr1 IS NULL) AND outexpr2=innerexpr2…AND outexprn= innerexprn);

在完成上述轉(zhuǎn)換后，在物理計劃的執(zhí)行上對于相關子查詢是類似的，物理計劃會首先執(zhí)行主查詢塊的查詢，取出主查詢中的每一個元組，對于多個過濾條件的，如果是用OR連接的過濾條件，則只需判斷其余過濾條件，如果其余過濾條件為假，再將該元組傳遞給子查詢執(zhí)行，如果為真，則可以不用執(zhí)行子查詢。對于由AND連接的過濾條件，需要判斷是否滿足其他過濾條件，只有滿足其他條件的元組信息會被傳遞給子查詢執(zhí)行。

對于傳遞給子查詢的元組信息，物理計劃會將子查詢中主查詢相關的屬性改寫成元組中具體的值，然后根據(jù)重寫后的物理計劃進行執(zhí)行計算子查詢的結果，如果子查詢執(zhí)行后存在滿足條件的結果，將返回給主查詢一個TRUE值，否則返回FALSE值。對于可以使子查詢結果為TRUE的元組，會將該元組的信息輸出，然后取出下一行元組，如此進行直到將主查詢中的所有元組掃描完成。

目前的執(zhí)行流程如圖1所示。

從流程圖中可以直觀的看出，現(xiàn)有的執(zhí)行策略對于每一個子查詢都有著嵌套的2個循環(huán)過程，對于外層父查詢的每一個元組都需要經(jīng)過一次完整的子查詢執(zhí)行流程，這在外層查詢的元組增加時大量的增加時間開銷，同時，如果存在多層嵌套的子查詢，那么時間開銷更是會指數(shù)級增加，反復對子查詢的執(zhí)行，也將會導致數(shù)據(jù)頻繁的進行通信，在分布式的環(huán)境下也會產(chǎn)生大量的通信時間開銷，接下來，將討論對子查詢優(yōu)化的具體策略與實現(xiàn)方法。

圖1 現(xiàn)有子查詢執(zhí)行流程圖

2.3 優(yōu)化策略

對分布式數(shù)據(jù)庫不同的語句環(huán)境，本文選擇了3種優(yōu)化方案：子查詢?nèi)哂嘧訕湎⒕奂瘮?shù)消除和子查詢上拉方案，針對不同的情況進行優(yōu)化。

2.3.1 子查詢?nèi)哂嘧訕淝谐?/p>

對于IN和EXISTS的相關子查詢來說，IN子查詢等價于在原有子查詢的過濾條件中添加了一個IN內(nèi)外表達式的等值過濾，在執(zhí)行時只是判斷是否對于過濾條件有非空結果產(chǎn)生，因此，子查詢的結果集是否排序、是否按某一屬性進行分組、選擇對象是否有唯一性限制并不會對查詢的結果產(chǎn)生影響。然而，這些子句會在物理計劃的生成與執(zhí)行時產(chǎn)生多余的執(zhí)行路徑與操作符，進而導致執(zhí)行時間開銷增加，所以對于子查詢中的去重限制，無其他子句的group by子句和order by子句進行切除，減少子查詢的操作。切除示例：

SELECT C1 FROM T1 WHERE C2 IN(SELECT DISTINCT(A1) FROM T2 WHERE T1.C3=T2.C3 ORDER BY (A2) GROUP BY(A3));

優(yōu)化后為：

SELECT C1 FROM T1 WHERE C2 IN (SELECT A1 FROM T2 WHERE T1.C3=T2.C3);

2.3.2 聚集函數(shù)消除

對于涉及到聚集函數(shù)的大部分情況來說，要消除聚焦函數(shù)是比較復雜的，本文只實現(xiàn)了對于EXISTS相關子查詢的聚集函數(shù)消除。聚集函數(shù)的計算結果對于即使是表中不存在滿足過濾條件的元組，也會返回一個有著具體值的結果，比如count()會返回0值，sum()會返回NULL值，然而無論返回什么樣的值，結果總是非空的，對于EXISTS的子查詢來說，恒為非空的子查詢將總會允許主查詢的元組被輸出，所以帶有聚集函數(shù)的子查詢并沒有對整個查詢產(chǎn)生影響，因此可以在構造計劃時，刪去含有聚集函數(shù)的子查詢。

例：SELECT*FROM T1 WHERE T1.C2=1 AND EXISTS(SELECT COUNT(*)FROM T2 WHERE T1.C1=T2.C1);

優(yōu)化后：

SELECT*FROM T1 WHERE T1.C2=1;

2.3.3 子查詢上拉

由于在語義上，IN相關子查詢和EXISTS相關子查詢是等價的，又都等價于半連接語義，所以可以考慮將子查詢中的表與條件展開上拉到主查詢中，這樣可以使得嵌套的子查詢變成了一層的連接查詢，減少了查詢執(zhí)行的次數(shù)。

由于目前的CBASE中暫不支持半連接語義的查詢，由1.1.1節(jié)的公式可知，2個關系R與S在某一屬性上的半連接，等價于對R與S在該屬性上進行內(nèi)連接后對關系R的屬性進行投影。所以在這里采用內(nèi)連接的策略，將IN相關子查詢的內(nèi)容，上拉合并到主查詢中。

將IN子查詢的表作為連接表合并進主查詢的FROM中，用INNER JOIN連接，將子查詢中與主查詢相關的過濾條件作為連接條件，其余過濾條件上拉合并至主查詢的過濾條件中。對于IN相關的內(nèi)外表達式，依次構造成等值過濾條件，添加進連接條件中，對于主查詢的目標，需要進行額外的去重操作。

但是這種優(yōu)化策略僅支持簡單的相關子查詢，要求子查詢中不含有聚集函數(shù)，不含有with子句，且子查詢的FROM和WHERE內(nèi)容不能為空，否則無法構造連接查詢。具體如下：

例：

SELECT C1 FROM T1 WHERE C2 IN (SELECT A1 FROM T2 WHERE T1.C3=T2.C3 AND T2.A2=3);

優(yōu)化后：

SELECT DISTINCT (C1) FROM T1 INNER JOIN T2 ON T1.C2=T2.A1 AND T1.C3=T2.C3 WHERE T2.A2=3;

子查詢上拉為連接查詢的優(yōu)化方法雖然對于待優(yōu)化的語句類型有著較為嚴格的限制，局限于簡單的子查詢語句，但是在日常的使用中，簡單的子查詢語句占了很大的比例，而且相關子查詢在面對查詢數(shù)據(jù)的增加時，耗時也會隨之劇增，因此，即使子查詢上拉只針對于簡單子查詢，也有著很大的應用環(huán)境。

2.4 優(yōu)化算法設計

對于優(yōu)化的進行，需要在解析語法樹的過程中進行一些準備工作，將查詢語句中的IN/EXISTS查詢塊的外部表達式和子查詢的查詢對象存儲起來預備進行上拉優(yōu)化。優(yōu)化的預處理工作與優(yōu)化器的調(diào)用流程如圖2所示。

圖2 優(yōu)化預處理及優(yōu)化器流程圖

本文將綜合2.3節(jié)中講述的幾種策略進行優(yōu)化，對于每一個進入優(yōu)化器的查詢，將依次處理每一個子查詢塊，先對輸入的子查詢可切除冗余子樹進行切除，之后，對含有聚集函數(shù)的EXISTS子查詢進行消除。經(jīng)過前2步處理后的子查詢，如果存在滿足可優(yōu)化的簡單子查詢，進行上拉展開,子查詢中還含有子查詢，則遞歸地調(diào)用優(yōu)化器，從最底層的子查詢依次向上優(yōu)化展開，減少查詢層數(shù)。偽代碼如下：

Optimize(query){

For each subquery-i{

If(subquery_i存在冗余子樹){

切除冗余子樹；

}

If(subquery-i存在聚集函數(shù)且是EXISTS){

消除subquery-i;

}else(subquery-i是簡單相關子查詢){

If(是葉子子查詢){

subquery-i FROM項上拉；

subquery-i WHERE與父查詢相關項上拉為連接條件；

subquery-iWHERE剩余項上拉；

subquery-i in相關項重構為等值語句上拉為連接條件；

}else{

Optimize(subquery-i);

}

}

}

}

3 實驗設計與結果

3.1 實驗環(huán)境

實驗選擇在Linux服務器上部署的CBASE分布式數(shù)據(jù)庫上進行，Linux服務器環(huán)境參數(shù)如表1所示。

表1 測試機器配置

性能測試采用了TPC-H基準的3張表：nation、supplier和customer并生成測試數(shù)據(jù)。指定TPC-H生成總量為1G的隨機數(shù)據(jù)，其中，nation表數(shù)據(jù)量為25行，supplier表數(shù)據(jù)量為1萬行，customer表數(shù)據(jù)為10萬行以上。以nation 表作為外表，其他2張表作為構成子查詢的內(nèi)表，分別用來進行不同數(shù)據(jù)量的測試。實驗目的是驗證目前選擇的3種策略，在單獨作用的情況下，是否能減少查詢的執(zhí)行時間。針對3種情況設計了不同的SQL語句來進行驗證優(yōu)化前后的性能。對于聚集函數(shù)消除，由于這種優(yōu)化方案針對的情況與其他2種方案并不重合，所以僅設計單獨的情況來驗證性能。對于冗余子樹切除和子查詢上拉，除了分別驗證各自的性能外，還設計了2種情況的SQL語句，測試綜合性能。在實驗結果展示中，將分別表示出對不同類型語句優(yōu)化前后的時間開銷，以及對冗余子樹切除后仍能進行上拉優(yōu)化的語句再次優(yōu)化的效果，稱之為二次優(yōu)化。

為了使性能測試的結果更接近實際用途，測試表的數(shù)據(jù)量外表25行數(shù)據(jù)，內(nèi)表10 000數(shù)據(jù)和外表25行數(shù)據(jù)，內(nèi)表100 000數(shù)據(jù)測試集。

3.2 實驗結果

1) 25×10 000數(shù)據(jù)

外表的內(nèi)容為：

nation(N-NATIONKEY,N-NAME,N-REGIONKEY,N-COMMENT);

內(nèi)表的內(nèi)容為：

supplier(S-SUPPKEY,S-NAME,S-ADDRESS,S-NATIONKEY,-PHONE,S-ACCTBAL,S-COMMENT);

設計的測試語句為：

針對distinct子句切除：

select*from nation where exists (select distinct(s-name) from supplier where supplier.s-nationkey=nation.n-nationkey );

針對group by子句切除：

select*from nation where n-nationkey in(select s-nationkey from supplier where nation.n-regionkey=1 group by (s-suppkey));

針對order by切除：

select*from nation where n-nationkey in(select s-nationkey from supplier where nation.n-regionkey=1 order by (s-suppkey));

聚集函數(shù)消除：

select*from nation where exists(select count(*) from supplier where supplier.s-nationkey=nation.n-nationkey );

上拉優(yōu)化：

select*from nation where n-nationkey in (select s-nationkey from supplier where nation.n-regionkey=1);

對于這幾種優(yōu)化的實際執(zhí)行結果如圖3所示。

圖3 25×1萬數(shù)據(jù)優(yōu)化性能顯示

可以從實驗的結果中直觀地看出，聚集函數(shù)由于直接切除了整個子查詢，在無其他子查詢時，相當于對主查詢的表進行一個簡單的掃描，所以優(yōu)化性能非常顯著，但是這種優(yōu)化方案的應用環(huán)境非常受限，適用不廣。冗余子樹的切除雖然對于性能有一定的提升，但是可以看出提升并不顯著。切除dinstinct路徑的優(yōu)化有19%，切除groupby和orderby的性能提升比較接近，都是5%左右?？梢钥闯觯谌哂嘧訕淝谐g相比，distinct切除后的性能優(yōu)化更為明顯，這說明在進行distinct運算時需要耗費較多的計算時間，所以其優(yōu)化性能相比其他的運算略微明顯。而由于設計的實驗語句，均為相關子查詢，即使通過冗余子樹切除減少了不必要的查詢路徑，優(yōu)化后的語句仍是一個相關子查詢語句，冗余子樹進行計算的CPU開銷和獲取相關數(shù)據(jù)的磁盤開銷，相比于相關子查詢對子表進行反復掃描的磁盤I/O和網(wǎng)絡開銷，占了總耗時中很少的一部分，所以在冗余子樹切除后，實驗語句的耗時仍然是較長的。子查詢展開轉(zhuǎn)換成連接的優(yōu)化方案，可以看出，無論是單獨的子查詢上拉的情況，還是先進行冗余子樹切除后再進行上拉的環(huán)境，都有著不錯的性能，這是由于相關子查詢對于外表中每一個符合條件的元組，都要進行一次子表掃描，這樣的耗時是非常巨大的，將子查詢上拉后，只需要進行一次掃描做連接運算，這大大減少了對磁盤的掃描和網(wǎng)絡通信。

2) 25×100 000數(shù)據(jù)：

外表內(nèi)容：

nation(N-NATIONKEY,N-NAME,N-REGIONKEY,N-COMMENT);

內(nèi)表內(nèi)容：

customer(C-CUSTKEY,C-NAME,C-ADDRESS,C-NATIONKEY,C-PHONE,C-ACCTBAL,C-MKTSEGMENT,C-COMMENT);

針對distinct切除：

select*from nation where exists (select distinct(c_custkey) from customer where customer.c_nationkey=nation.n-nationkey);

針對group by切除：

select*from nation where n-nationkey in (select c-nationkey from customer where nation.n_regionkey=1 group by (c-name));

針對order by切除：

select*from nation where n-nationkey in (select c-nationkey from customer where nation.n-regionkey=1 order by (c-name));

聚集函數(shù)消除：

select*from nation where exists (select count(*) from customer where customer.c-nationkey=nation.n-nationkey and nation.n-regionkey=1);

子查詢上拉：

select*from nation where n-nationkey in (select c-nationkey from customer where nation.n-regionkey=1);

實驗結果如下所示：

圖4 25×10萬數(shù)據(jù)優(yōu)化性能顯示

同樣的，在數(shù)據(jù)量增多的情況下可以發(fā)現(xiàn)同樣的結論，此外，也可以看出，對于冗余子樹切除的優(yōu)化，隨著數(shù)據(jù)量的增多，其性能的提升略微有所下降，這是由于數(shù)據(jù)量的增多使得每次掃描子表的開銷隨之增加，這就導致了相關子查詢多次掃描子表內(nèi)容產(chǎn)生的開銷占據(jù)了更大的比重，因此子查詢上拉的優(yōu)化策略隨著數(shù)據(jù)量的增多顯得性能更為顯著。

可以發(fā)現(xiàn)，單獨的冗余子樹切除對于查詢性能的提升只有不到20%，而且在子查詢存在有需要上拉優(yōu)化的情況下，查詢內(nèi)外表的數(shù)據(jù)量越多，子查詢在切除子樹后越復雜，冗余子樹切除對查詢性能的優(yōu)化效果越不明顯。聚集函數(shù)消除僅針對特定情況下的查詢有作用，但是對于可進行優(yōu)化的查詢效果提升非常顯著，優(yōu)化后的性能只與主查詢的復雜程度相關。上拉優(yōu)化是進行子查詢優(yōu)化的主要方案，目前大部分常用的查詢語句都屬于上拉優(yōu)化可優(yōu)化的范圍，也可以從實驗中看出，上拉優(yōu)化對于相關子查詢的時間開銷優(yōu)化作用顯著，可以達到90%以上。本文優(yōu)化方案在當前的CBASE環(huán)境下，面對特殊的情況和大部分普遍情況都是可以進行效果顯著的優(yōu)化的。

4 結 論

本文研究了目前現(xiàn)有的數(shù)據(jù)庫優(yōu)化策略，結合分布式數(shù)據(jù)庫CBASE的特點，選擇了子查詢上拉為內(nèi)連接，聚集函數(shù)消除，冗余子樹切除的方案，針對目前CBASE中IN相關子查詢執(zhí)行性能差、時間開銷大的問題，提出了優(yōu)化方案。本文的優(yōu)化方案從理論上可以減少IN相關子查詢執(zhí)行時不必要的物理計劃操作，減少了查詢的嵌套層次，轉(zhuǎn)為層數(shù)較少的連接查詢。

實驗結果表明：3種方案在面對特殊的聚集函數(shù)消除的情況時效果最為顯著；在面對普遍常見的簡單子查詢時，上拉優(yōu)化也可以有著顯著的優(yōu)化效果；冗余子樹切除的優(yōu)化策略在被優(yōu)化子查詢數(shù)據(jù)量大的情況時效果愈發(fā)平庸。

本文的研究中只針對了IN相關子查詢中的簡單子查詢和EXISTS查詢中的聚集函數(shù)的優(yōu)化，且只實現(xiàn)了基于規(guī)則的優(yōu)化。對于其他更為復雜的查詢語句以及基于代價選擇的優(yōu)化，本文暫時還沒有提出解決方案，在后續(xù)的工作中，將繼續(xù)深入研究視圖消除，子查詢合并等優(yōu)化方案 ，并對基于代價選擇的優(yōu)化提出解決方法，此外，將采用MPP架構，將查詢計劃按照操作符進行拆分，進行并行處理的優(yōu)化。