基于分布式數據庫的相關子查詢優化

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

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

隨著互聯網的發展和數據量的不斷激增，分布式數據庫已經逐漸取代單機數據庫，成為金融、互聯網等行業應用的主流存儲系統。

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

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

現有的查詢優化主要是基于2個方面進行，即基于規則的查詢優化和基于代價的查詢優化。基于規則的研究一般是通過重寫查詢計劃，去除查詢的嵌套性來降低復雜度和子查詢的執行次數來提高性能，基于代價的研究則是根據統計信息來進行查詢計劃的代價計算，選擇代價最小的查詢方案。

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

1 相關研究

1.1 基于規則的研究

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

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

對于原有的IN查詢：

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

可以將其轉換成等價的EXISTS語義的語句：

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

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

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

2) 消除冗余子樹；

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

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

1.1.1 子查詢上拉

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

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

將子查詢上拉為內連接相較于轉換為半連接的策略，只解決了聚焦函數造成的優化限制，對于其余限制條件仍不能解決。

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

1.1.2 冗余子樹切除

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

例：原句為：

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

優化后為：

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

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

1.1.3 相關列構建索引

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

1.1.4 子查詢合并

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

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

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

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

1.1.5 聚集函數消除

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

例：

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

優化后的結果為：

SELECT * FROM T1 WHERE T1.C2=1;

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

1.2 基于代價的研究

基于代價的優化需要引入統計信息、直方圖等的功能[8-10]。基于代價的優化需要統計信息提供的關于表的相關信息，預先的估算查詢可用的若干計劃的可能開銷，從中選擇出代價最小的執行方案執行。

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

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

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

1.3 分布式系統中的優化

分布式數據庫系統與集中式數據庫系統之間查詢代價的差異，主要體現在查詢代價的構成上。傳統的集中式數據庫，查詢代價由CPU執行時間與I/O構成。而分布式數據庫由于各個節點分布在網絡當中，除了基礎的CPU時間和I/O外，還有各個節點之間的網絡通信耗時。所以分布式數據庫在優化策略的設計上，除了結合自身分布式特點的策略外，還借鑒了傳統的數據庫。

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

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

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

2 算法實現

對于分布式數據庫優化的2個目標，本文主要關注于第一個目標，減少查詢時間消耗，參考傳統數據庫對于查詢優化的一些思想，進行基于規則的優化。

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

2.1 實現背景介紹

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

在目前的CBASE環境中，只支持了EXISTS的子查詢功能和IN的非相關子查詢功能，本文參考MySQL中的轉換規則實現IN相關子查詢并對IN和EXISTS相關子查詢進行優化。

2.2 現有IN子查詢執行策略

本文將詳細討論并實現IN相關子查詢的方法，并介紹在未優化的情況下IN相關子查詢與EXISTS相關子查詢的執行方法。

對于IN相關子查詢，考慮可以通過轉換現有的執行計劃，使其成為等價的EXISTS相關子查詢，轉換的普遍規則如下：

原查詢：

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

轉換后查詢：

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子查詢的返回結果只是空與非空，對具體內容并不關心，所以子查詢的目標并不需要指定，為1即可， 保留原有的子查詢的過濾條件，將原有查詢中IN相關的屬性一一對應改為“=”作為子查詢的新過濾條件。

這是最為普遍的轉換方法，額外的，需要討論被轉換的查詢中，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);

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

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

目前的執行流程如圖1所示。

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

圖1 現有子查詢執行流程圖

2.3 優化策略

對分布式數據庫不同的語句環境，本文選擇了3種優化方案：子查詢冗余子樹消除、聚集函數消除和子查詢上拉方案，針對不同的情況進行優化。

2.3.1 子查詢冗余子樹切除

對于IN和EXISTS的相關子查詢來說，IN子查詢等價于在原有子查詢的過濾條件中添加了一個IN內外表達式的等值過濾，在執行時只是判斷是否對于過濾條件有非空結果產生，因此，子查詢的結果集是否排序、是否按某一屬性進行分組、選擇對象是否有唯一性限制并不會對查詢的結果產生影響。然而，這些子句會在物理計劃的生成與執行時產生多余的執行路徑與操作符，進而導致執行時間開銷增加，所以對于子查詢中的去重限制，無其他子句的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));

優化后為：

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

2.3.2 聚集函數消除

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

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

優化后：

SELECT*FROM T1 WHERE T1.C2=1;

2.3.3 子查詢上拉

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

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

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

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

例：

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

優化后：

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

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

2.4 優化算法設計

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

圖2 優化預處理及優化器流程圖

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

Optimize(query){

For each subquery-i{

If(subquery_i存在冗余子樹){

切除冗余子樹；

}

If(subquery-i存在聚集函數且是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 實驗環境

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

表1 測試機器配置

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

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

3.2 實驗結果

1) 25×10 000數據

外表的內容為：

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

內表的內容為：

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));

聚集函數消除：

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

上拉優化：

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

對于這幾種優化的實際執行結果如圖3所示。

圖3 25×1萬數據優化性能顯示

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

2) 25×100 000數據：

外表內容：

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

內表內容：

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));

聚集函數消除：

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萬數據優化性能顯示

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

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

4 結 論

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

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

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