基于分布式數(shù)據(jù)庫(kù)的相關(guān)子查詢優(yōu)化

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

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

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

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

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

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

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

1 相關(guān)研究

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

對(duì)于子查詢，按照關(guān)鍵字的不同，可以劃分為3類(lèi)：①I(mǎi)N為標(biāo)志的集合成員查詢；②ANY/SOME/ALL關(guān)鍵詞引導(dǎo)的比較查詢；③以EXISTS為關(guān)鍵詞的空判斷查詢。

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

對(duì)于原有的IN查詢：

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

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

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

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

1) 查詢展開(kāi)，將子查詢上拉；

2) 消除冗余子樹(shù)；

3) 在相關(guān)列上構(gòu)建索引。

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

1.1.1 子查詢上拉

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

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

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

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

1.1.2 冗余子樹(shù)切除

對(duì)于相關(guān)子查詢來(lái)說(shuō)，由于IN相關(guān)子查詢可以通過(guò)轉(zhuǎn)換變?yōu)檎Z(yǔ)義等價(jià)的EXISTS相關(guān)子查詢，因此，對(duì)于子查詢中的一些限制子句的處理，可以按照EXISTS的語(yǔ)義進(jìn)行考慮。EXISTS的語(yǔ)義對(duì)于子查詢的結(jié)果只判斷是否為空，并不關(guān)心結(jié)果中的順序等具體內(nèi)容，所以子查詢中的排序、去重等都是對(duì)于查詢結(jié)果毫無(wú)貢獻(xiàn)的無(wú)用操作，去除掉這些子句可以減少查詢計(jì)劃的內(nèi)容，切除子樹(shù)的規(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);

對(duì)于子句中的DINSTINCT、GROUP BY、ORDER BY謂詞都可以切除以減少查詢計(jì)劃的路徑長(zhǎng)度，縮短時(shí)間開(kāi)銷(xiāo)。

1.1.3 相關(guān)列構(gòu)建索引

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

1.1.4 子查詢合并

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

如果一個(gè)子查詢的結(jié)果集包含了另一個(gè)查詢塊的結(jié)果集，將其稱(chēng)為容器查詢塊，另一個(gè)稱(chēng)為包含查詢塊。對(duì)于同類(lèi)型的2個(gè)子查詢，如果滿足包含關(guān)系，那么保留容器查詢塊，刪去包含查詢塊。

當(dāng)子查詢塊之間不滿足包含與被包含的關(guān)系時(shí)，可以將具有等價(jià)語(yǔ)義的語(yǔ)義合并，并將其余下等非的條件合取或析取，使之成為一個(gè)子查詢。

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

1.1.5 聚集函數(shù)消除

對(duì)于聚集函數(shù)的處理策略是比較復(fù)雜的，在這里只討論了一些簡(jiǎn)單的處理策略。在EXISTS中對(duì)于聚集函數(shù)的一些處理是簡(jiǎn)單的。由于EXISTS子查詢的返回結(jié)果只是是否為空，而對(duì)于聚集函數(shù)的運(yùn)算來(lái)說(shuō)，無(wú)論是否有滿足過(guò)濾條件的行，都會(huì)返回一個(gè)運(yùn)算結(jié)果，即使是沒(méi)有滿足子查詢過(guò)濾條件的元組，也會(huì)返回一個(gè)0或者NULL的結(jié)果，而非空結(jié)果，這就說(shuō)明聚集函數(shù)在EXISTS的子句中是返回一個(gè)恒為T(mén)RUE的值的，即子查詢恒成立，所以可以將含有聚集函數(shù)的子查詢刪去，減少子查詢的執(zhí)行。

例：

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

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

SELECT * FROM T1 WHERE T1.C2=1;

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

1.2 基于代價(jià)的研究

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

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

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

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

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

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

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

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

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

2 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

對(duì)于IN相關(guān)子查詢，考慮可以通過(guò)轉(zhuǎn)換現(xiàn)有的執(zhí)行計(jì)劃，使其成為等價(jià)的EXISTS相關(guān)子查詢，轉(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子查詢的返回結(jié)果只是空與非空，對(duì)具體內(nèi)容并不關(guān)心，所以子查詢的目標(biāo)并不需要指定，為1即可， 保留原有的子查詢的過(guò)濾條件，將原有查詢中IN相關(guān)的屬性一一對(duì)應(yīng)改為“=”作為子查詢的新過(guò)濾條件。

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

當(dāng)innerexpr可能為NULL值時(shí)，在添加過(guò)濾條件outexpr = innerexpr時(shí)，要析取一個(gè)判斷innerexpr IS NULL，將析取后的結(jié)果作為過(guò)濾條件添加進(jìn)子查詢的WHERE中。假設(shè)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)換后，在物理計(jì)劃的執(zhí)行上對(duì)于相關(guān)子查詢是類(lèi)似的，物理計(jì)劃會(huì)首先執(zhí)行主查詢塊的查詢，取出主查詢中的每一個(gè)元組，對(duì)于多個(gè)過(guò)濾條件的，如果是用OR連接的過(guò)濾條件，則只需判斷其余過(guò)濾條件，如果其余過(guò)濾條件為假，再將該元組傳遞給子查詢執(zhí)行，如果為真，則可以不用執(zhí)行子查詢。對(duì)于由AND連接的過(guò)濾條件，需要判斷是否滿足其他過(guò)濾條件，只有滿足其他條件的元組信息會(huì)被傳遞給子查詢執(zhí)行。

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

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

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

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

2.3 優(yōu)化策略

對(duì)分布式數(shù)據(jù)庫(kù)不同的語(yǔ)句環(huán)境，本文選擇了3種優(yōu)化方案：子查詢?nèi)哂嘧訕?shù)消除、聚集函數(shù)消除和子查詢上拉方案，針對(duì)不同的情況進(jìn)行優(yōu)化。

2.3.1 子查詢?nèi)哂嘧訕?shù)切除

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

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ù)消除

對(duì)于涉及到聚集函數(shù)的大部分情況來(lái)說(shuō)，要消除聚焦函數(shù)是比較復(fù)雜的，本文只實(shí)現(xiàn)了對(duì)于EXISTS相關(guān)子查詢的聚集函數(shù)消除。聚集函數(shù)的計(jì)算結(jié)果對(duì)于即使是表中不存在滿足過(guò)濾條件的元組，也會(huì)返回一個(gè)有著具體值的結(jié)果，比如count()會(huì)返回0值，sum()會(huì)返回NULL值，然而無(wú)論返回什么樣的值，結(jié)果總是非空的，對(duì)于EXISTS的子查詢來(lái)說(shuō)，恒為非空的子查詢將總會(huì)允許主查詢的元組被輸出，所以帶有聚集函數(shù)的子查詢并沒(méi)有對(duì)整個(gè)查詢產(chǎn)生影響，因此可以在構(gòu)造計(jì)劃時(shí)，刪去含有聚集函數(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 子查詢上拉

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

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

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

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

例：

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)化方法雖然對(duì)于待優(yōu)化的語(yǔ)句類(lèi)型有著較為嚴(yán)格的限制，局限于簡(jiǎn)單的子查詢語(yǔ)句，但是在日常的使用中，簡(jiǎn)單的子查詢語(yǔ)句占了很大的比例，而且相關(guān)子查詢?cè)诿鎸?duì)查詢數(shù)據(jù)的增加時(shí)，耗時(shí)也會(huì)隨之劇增，因此，即使子查詢上拉只針對(duì)于簡(jiǎn)單子查詢，也有著很大的應(yīng)用環(huán)境。

2.4 優(yōu)化算法設(shè)計(jì)

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

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

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

Optimize(query){

For each subquery-i{

If(subquery_i存在冗余子樹(shù)){

切除冗余子樹(shù)；

}

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

消除subquery-i;

}else(subquery-i是簡(jiǎn)單相關(guān)子查詢){

If(是葉子子查詢){

subquery-i FROM項(xiàng)上拉；

subquery-i WHERE與父查詢相關(guān)項(xiàng)上拉為連接條件；

subquery-iWHERE剩余項(xiàng)上拉；

subquery-i in相關(guān)項(xiàng)重構(gòu)為等值語(yǔ)句上拉為連接條件；

}else{

Optimize(subquery-i);

}

}

}

}

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

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

表1 測(cè)試機(jī)器配置

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

設(shè)計(jì)的測(cè)試語(yǔ)句為：

針對(duì)distinct子句切除：

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

針對(duì)group by子句切除：

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

針對(duì)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);

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

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

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

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

針對(duì)distinct切除：

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

針對(duì)group by切除：

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

針對(duì)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);

實(shí)驗(yàn)結(jié)果如下所示：

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

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

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

4 結(jié) 論

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

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

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