毛思語,張利軍,張小芳,高錦濤,李戰(zhàn)懷

(西北工業(yè)大學(xué)計算機學(xué)院,西安710129)

面向分布“數(shù)據(jù)庫的相關(guān)子查詢優(yōu)化策略

毛思語,張利軍,張小芳,高錦濤,李戰(zhàn)懷

(西北工業(yè)大學(xué)計算機學(xué)院,西安710129)

子查詢是指查詢語句作為另一個語句的查詢條件出現(xiàn),相關(guān)子查詢是指子查詢的查詢條件依賴于父查詢.相關(guān)子查詢要對子查詢反復(fù)求值,需要多次訪問磁盤,尤其是在分布式的環(huán)境中還會產(chǎn)生大量的通信開銷,導(dǎo)致執(zhí)行效率低下.在對現(xiàn)有相關(guān)子查詢優(yōu)化策略分析研究的基礎(chǔ)上,綜合分布式的特點,將子查詢展開、無用子樹切除、聚集函數(shù)消除等策略應(yīng)用于分布式關(guān)系數(shù)據(jù)庫系統(tǒng)中,并在開源分布式關(guān)系數(shù)據(jù)庫OceanBase中應(yīng)用這些策略實現(xiàn)對謂詞EXISTS的相關(guān)子查詢的優(yōu)化.實驗表明這些策略能夠明顯改善相關(guān)子查詢的查詢性能.

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

0 引言

SQL語言是關(guān)系數(shù)據(jù)庫中一種高度非過程化語言[1],在SQL語言中,一個SELECTFROM-WHERE稱為一個查詢塊,將一個查詢塊嵌套在另一個查詢塊條件中的查詢稱為子查詢,子查詢根據(jù)是否和父查詢有依賴關(guān)系分為相關(guān)子查詢和非相關(guān)子查詢[2].非相關(guān)子查詢實現(xiàn)較為簡單,即先執(zhí)行子查詢,父查詢綁定子查詢的結(jié)果執(zhí)行,子查詢和父查詢都只執(zhí)行一遍;相關(guān)子查詢執(zhí)行較為復(fù)雜,先執(zhí)行父查詢,從父查詢的結(jié)果集中取出一個元組,重寫子查詢后執(zhí)行,簡單來說,父查詢中有多少個元組,將執(zhí)行多少次子查詢.這種相關(guān)子查詢執(zhí)行策略非常耗時,當(dāng)子查詢嵌套層數(shù)較多時,執(zhí)行次數(shù)將是指數(shù)級的增長,因此對相關(guān)子查詢的執(zhí)行進行優(yōu)化非常重要.

相關(guān)子查詢的優(yōu)化方向是減少子查詢的執(zhí)行次數(shù)或者是減少子查詢的執(zhí)行時間.現(xiàn)有對相關(guān)子查詢的優(yōu)化策略一般是去相關(guān)性,然后各個部分獨立執(zhí)行.本文在分析研究相關(guān)子查詢的優(yōu)化策略的基礎(chǔ)上,結(jié)合分布式的特點,并將相關(guān)子查詢的優(yōu)化策略應(yīng)用于分布式數(shù)據(jù)庫中,并以開源分布式關(guān)系型數(shù)據(jù)庫OCEANBASE為基礎(chǔ),實現(xiàn)了謂詞為EXISTS的相關(guān)子查詢,并采用子查詢展開、無用分支切除和聚集函數(shù)消除等優(yōu)化策略對相關(guān)子查詢進行優(yōu)化.

1 相關(guān)研究

一般來說,子查詢可以作為過濾條件出現(xiàn)在WHERE/HAVING/ON等地方,或者作為臨時表出現(xiàn)在FROM/SELECT等子句中[3].本文只討論作為過濾條件使用的子查詢,子查詢可以按照關(guān)鍵字和語義劃分為以下3類[2].

(1)IN關(guān)鍵字的集合成員查詢.

(2)ANY/SOME/ALL等集合比較查詢.

(3)以EXISTS為標(biāo)志的空判斷查詢.從語義上分析,EXISTS不返回任何數(shù)據(jù),只做邏輯空判斷,并且根據(jù)證明,所有其他子查詢都可以轉(zhuǎn)化為EXISTS子查詢[2,4].

由于以EXISTS為標(biāo)志的空判斷查詢從語義上是一種只取一次的查詢,不同于其他子查詢要掃描全表或者是部分表,從查詢語義上說,EXISTS子查詢是一種最優(yōu)子查詢,并且其他謂詞的子查詢都可以轉(zhuǎn)為EXISTS子查詢.在本文中只討論EXISTS相關(guān)子查詢,下文中提到的相關(guān)子查詢也指謂詞為EXISTS的相關(guān)子查詢.

相關(guān)子查詢由于執(zhí)行多次子查詢使效率較低,很多去相關(guān)性的方法提出以提高相關(guān)子查詢性能[5],常用以下3種方法優(yōu)化子查詢性能.

(1)子查詢展開為半連接,把子查詢展開為半連接,消除子查詢.

(2)子查詢展開為內(nèi)連接,把子查詢展開為內(nèi)連接,消除子查詢.

(3)子查詢中相關(guān)列上建索引,減少單次子查詢執(zhí)行時間,并不降低子查詢執(zhí)行次數(shù).

但是在相關(guān)子查詢不能展開的情況,使用原始方法執(zhí)行子查詢還是非常耗時,JUN RAO等人基于這種情況提出一種將子查詢中和父查詢相關(guān)條件去除后物化中間結(jié)果的方法,填充子查詢展開和傳統(tǒng)方法中的空缺,性能優(yōu)于傳統(tǒng)的NEST-LOOP方式[6].

1.1 子查詢展開為半連接

根據(jù)相關(guān)子查詢語義,一個相關(guān)子查詢類似于一個半連接.Bellamokan等人提出使用窗口函數(shù)和半連接的方式消除子查詢,目前Oracle、Postgre和MYSQL等查詢優(yōu)化器中采用這種策略對相關(guān)子查詢進行優(yōu)化[7-8].在執(zhí)行子查詢展開技術(shù)是把將子查詢轉(zhuǎn)換為半連接,嵌套層數(shù)減1.

Postgre將位于WHERE子句后的子查詢稱為子鏈接,其在生成執(zhí)行計劃之前有一個優(yōu)化層處理,在這一部分處理對相關(guān)子查詢的優(yōu)化[8].從上層依次調(diào)用函數(shù)展開子鏈接,同時把子鏈接轉(zhuǎn)換為半連接或者是反半連接完成優(yōu)化工作[9].

值得注意的是,并不是所有的子查詢都可以進行展開操作,在POSTGRE中如果子查詢中含有WITH子句、聚集函數(shù)、FROM或者WHERE子句為空的情況下并不支持展開操作的處理.能進行的展開操作即使把子鏈接FROM子句的表合并到父查詢FROM子句中.把子鏈接中的WHERE子句合并到父查詢的WHERE子句中.如例1所示,可將子查詢展開為內(nèi)連接,其中T1、T2...表示表,C1表示表中的列.

例1:SELECT*FROM T1 WHERE T1.C1＞1 AND EXISTS(SELECT*FROM T2 WHERE T2.C1=T1.C1);

優(yōu)化后:

SELECT*FROM T1 SEMMI JOIN T2 WHERE T1.C1＞1 AND T2.C1=T1.C1;

1.2 子查詢展開為內(nèi)連接

除了可以將相關(guān)子查詢轉(zhuǎn)為半連接,由WON KIM等人提出使用內(nèi)連接的方式拉平子查詢,減少子查詢嵌套層數(shù)[1].根據(jù):R∝a=bS=QR(R∞a=bS)=R∞a=b(Qb(S)),其中R和S分別代表關(guān)系,a和b分別代表關(guān)系的連接屬性[10].把子查詢轉(zhuǎn)換內(nèi)連接后要在輸出列上加上去重操作.

Won Kim將子查詢分成五類,其中相關(guān)子查詢根據(jù)是否含有聚集函數(shù)分為兩類[1].不含聚集函數(shù)的相關(guān)子查詢直接可以展開為內(nèi)連接,含有聚集函數(shù)的子查詢需要借用臨時表機制消除聚集函數(shù),轉(zhuǎn)化為不含聚集函數(shù)的相關(guān)子查詢后展開處理.

其消除子查詢的算法是將一個N層子查詢拉平為N-1層的算法:合并所有的FROM子句,WHERE子句的過濾條件用AND鏈接,如果子查詢的謂詞是IS IN則轉(zhuǎn)換成“=”,如果是其他的則謂詞不變,對于父查詢的SELECT子句不做任何變化[1].如例2所示,可將子查詢展開為內(nèi)連接.

例2:SELECT C3 FROM T1 WHERE T1.C1 IS IN(SELECT C1 FROM T2 WHERE T2.C2=T1.C3);

優(yōu)化后:

SELECT DISTINCT C3 FROM T1 INNER JOIN T2 WHERE T1.C1=T2.C1 AND T2.C1=T1.C3;

1.3 子查詢中相關(guān)列上建索引

相關(guān)子查詢除了可以減少內(nèi)查詢執(zhí)行的次數(shù),還可以優(yōu)化內(nèi)查詢的執(zhí)行,總體提升子查詢性能.Takamitsu Shioi等人從數(shù)據(jù)存儲角度出發(fā),提出針對使用行存儲的數(shù)據(jù)庫系統(tǒng),可通過在WHERE中的屬性列上建立索引的方式對子查詢進行優(yōu)化[11].MYSQL中對于EXISTS相關(guān)子查詢沒有進行優(yōu)化,而是采取索引的方式減少子查詢執(zhí)行時間.

在父查詢表很小的情況下,子查詢表很大的情況下,借用索引進行執(zhí)行,縮短每次執(zhí)行子查詢的時間,總體開銷較小.MYSQL本質(zhì)上沒有對EXISTS做優(yōu)化,但是通過借助索引減少子查詢的執(zhí)行時間,提升子查詢執(zhí)行性能.

2 面向分布式系統(tǒng)的相關(guān)子查詢優(yōu)化

2.1 面向分布式系統(tǒng)的相關(guān)子查詢優(yōu)化策略

數(shù)據(jù)庫查詢的優(yōu)化主要分為兩個方面:路徑優(yōu)化和掃描次數(shù)的優(yōu)化.查詢耗時主要是傳送磁盤塊次數(shù)和搜索磁盤塊次數(shù)[4].對于路徑方面的優(yōu)化可以減少傳送磁盤塊的次數(shù),對掃描次數(shù)的優(yōu)化可以減少搜索磁盤塊的次數(shù).對于分布式數(shù)據(jù)庫而言,通信是影響查詢響應(yīng)的主要因素,在處理查詢語句時要盡量避免過多的通信開銷,可以通過減少通信時間實現(xiàn)子查詢的優(yōu)化[12].

由子查詢執(zhí)行策略可以看出,相關(guān)子查詢的復(fù)雜度主要是因為子查詢和父查詢有依賴關(guān)系,對子查詢的掃描次數(shù)過多.最壞的情況是父查詢有多少個元組,則要進行多少次子查詢表掃描.所以,針對相關(guān)子查詢優(yōu)化的方向主要是減少子查詢表的掃描次數(shù)和借助索引減少子查詢表的掃描時間.

2.1.1 子查詢展開

把子查詢置于外層的父查詢中,作為連接關(guān)系與外層父查詢并列,其實質(zhì)是把某些子查詢重寫為等價的多表連接操作[5],這樣有關(guān)的訪問路徑、連接方法和連接順序可能被有效利用,使得查詢語句的層次盡可能地減少.因為EXISTS子查詢語義是半連接語義,所以可以根據(jù)公式把子查詢展開為內(nèi)連接執(zhí)行.如上述例2所示的轉(zhuǎn)化.將子查詢的FROM子句以內(nèi)連接的形式合并到父查詢中,將子查詢的WHERE子句以AND連接的形式合并到父查詢中,對父查詢的輸出列做去重操作.

但是這種優(yōu)化并不是全部適應(yīng),在子查詢中有WITH子句、FROM或者WHERE子句為空的情況下并不能進行子查詢展開[7].

2.1.2 無用子樹切除

根據(jù)EXISTS語義來說,只做空判斷,并不關(guān)心結(jié)果集具體是什么內(nèi)容,所以可以去除子查詢的SELECT子句去及SELECT子句上的所有操作.在可以去除子查詢的SELECT子句、對SELECT子句的排序去重或限制輸出等.減少了物理計劃執(zhí)行時路徑長度和無用操作.如例4所示,是無用分支切除后的語句.

例4:SELECT*FROM T1 WHERE EXISTS(SELECT DISTINCT C2 FROM T2 WHERE T1.C1=T2.C1 ORDER BY(C3));

優(yōu)化后:

SELECT*FROMT1WHEREEXISTS(SELECTC2FROMT2WHERE T1.C1=T2.C1);

2.1.3 聚集函數(shù)消除

結(jié)合聚集函數(shù)的語義,不管一張表里有沒有數(shù)據(jù),聚集函數(shù)都會輸出一行,例如SUM(X)會返回NULL,COUNT(*)會返回0[13],子查詢的最終結(jié)果集不可能為空,對于EXISTS過濾條件,其結(jié)果是永真的.因此輸出列中存在聚集函數(shù)的子查詢是無意義的,可以直接去除.如例5所示,可以直接去除子查詢.

例5:SELECT*FROM T1 WHERE EXISTS(SELECT MAX(C1)FROM T2 WHERE T2.C1=T1.C1);

優(yōu)化后:

SELECT*FROM T1;

2.1.4 借用索引

在不能進行子查詢展開的情況下,可以選擇建合適的索引,減少子查詢的執(zhí)行時間.并且由于EXISTS相關(guān)子查詢是空判斷,并不關(guān)心具體得到了多少個元組,應(yīng)該對子查詢加LIMIT 1限制.使子查詢在執(zhí)行時只得到一行可以滿足條件的元組后就會輸出,而不是一直阻塞直到得到所有元組.如例6所示,T2表的C1列是主鍵列,則填充后可以改變掃描方式.

例6:SELECT*FROM T1 WHERE EXISTS(SELECT*FROM T2 WHERE T2.C1 =T1.C2);

優(yōu)化后:

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

2.2 分布式數(shù)據(jù)庫OceanBase中相關(guān)子查詢優(yōu)化實現(xiàn)

2.2.1 分布式數(shù)據(jù)庫系統(tǒng)OceanBase

OceanBase是由阿里巴巴開發(fā)的分布式關(guān)系型數(shù)據(jù)庫.OceanBase有4種類型的服務(wù)器:主控服務(wù)器、基準(zhǔn)服務(wù)器、增量服務(wù)器和合并服務(wù)器.OceanBase將數(shù)據(jù)分為基準(zhǔn)數(shù)據(jù)和增量數(shù)據(jù)分別存放在基準(zhǔn)服務(wù)器和增量服務(wù)器中,增量服務(wù)器中的數(shù)據(jù)可以通過合并的方式生成新的基準(zhǔn)數(shù)據(jù).客戶端在進行查詢時,需要通過合并服務(wù)器把需求發(fā)送到兩個服務(wù)器中,根據(jù)主控服務(wù)器中的信息取到相關(guān)數(shù)據(jù),然后進行過濾合并后返回給客戶端.

OceanBase對某些查詢可以不用將數(shù)據(jù)取到合并數(shù)據(jù)庫上進行過濾,將過濾條件下壓到基準(zhǔn)數(shù)據(jù)庫上進行,減少傳輸?shù)脑M數(shù)和空間占用,在基準(zhǔn)數(shù)據(jù)庫上的過濾是一次掃描所有所需元組,然后輸出第一行滿足條件的元組.OceanBase元組的掃描方式有兩種:一種基于主鍵的GET方法,利用主鍵索引直接取到所需元組;另一種是逐行SCAN,掃描表中所有元組是否滿足過濾條件.

目前開源的OceanBase版本中并不支持子查詢,實驗只實現(xiàn)了應(yīng)用較多且性能較優(yōu)化的EXISTS相關(guān)子查詢.

2.2.2 EXISTS的執(zhí)行策略

對于相關(guān)子查詢的執(zhí)行策略,需要先執(zhí)行父查詢,把和子查詢相關(guān)的列傳給子查詢,經(jīng)過子查詢過濾,決定是否輸出這一個元組.圖1為OceanBase中的EXISTS相關(guān)子查詢執(zhí)行流程.

如圖1所示,在物理計劃執(zhí)行開始時,從父查詢?nèi)〕鲆粋€元組,填充子查詢,如果子查詢中有合適的元組,即子查詢的結(jié)果集不為空,則輸出父查詢的元組;否則,不輸出.

父查詢過濾規(guī)則:本階段,在父查詢物理操作符打開完成后,需要過濾除子查詢外其他元組,即假設(shè)子查詢結(jié)果恒為真的情況下過濾表中元組,去除不滿足其他條件的元組.這里主要有兩種情況:一種是＜子查詢＞OR＜其他過濾條件P＞,這種情況不執(zhí)行P,直接把元組輸出;另一種是＜子查詢＞AND＜其他過濾條件P＞,如果不滿足P過濾條件,則不用取出這行元組,被過濾掉.為了識別子查詢,需要在物理計劃構(gòu)建的時給每個過濾條件打上標(biāo)記.在執(zhí)行時直接假設(shè)這個條件為真.

子查詢執(zhí)行:執(zhí)行子查詢,采用管道方式進行,從父查詢?nèi)〕鲆粋€元組,需要在子查詢執(zhí)行前填充子查詢中和父查詢相關(guān)的列,填充完成后,打開子查詢物理操作符,執(zhí)行子查詢物理計劃.因為EXISTS條件的特殊性,只需執(zhí)行一次子查詢就可以知道是否滿足EXISTS條件.EXISTS是空判斷不是NULL判斷,即使執(zhí)行子查詢后輸出結(jié)果是NULL仍然滿足EXISTS條件.這里需要對于父查詢中出現(xiàn)＜子查詢＞OR＜其他過濾條件P＞的過濾條件重新進行判斷,對不滿足子查詢的元組進行判斷是否可以滿足P.

圖1 EXISTS相關(guān)子查詢執(zhí)行流程Fig.1Execution process of correlated subquery for predicate EXISTS

2.2.3 EXISTS的優(yōu)化策略

使用2.1節(jié)所述的優(yōu)化策略對EXISTS進行優(yōu)化,如算法1所示,其中參數(shù)Q表示待優(yōu)化查詢.

算法1:

Optimize Subquery()函數(shù)實現(xiàn)對查詢Q的優(yōu)化,對Q中的每個子查詢,首先判斷其有無無用分支,若有則直接切除無用分支,然后判斷子查詢中是否有聚集函數(shù),如果存在則直接去除子查詢,否則判斷子查詢是否可展開,若可展開同時子查詢中不再包含子查詢,則對子查詢進行展開處理,否則遞歸地調(diào)用Optimize Subquery()函數(shù)對該子查詢進行同樣的處理.最后若有索引,則使用索引對查詢進行處理.

3 實驗

3.1 實驗設(shè)計

實驗在服務(wù)器上部署OceanBase分布式數(shù)據(jù)庫系統(tǒng),其中服務(wù)器軟硬件配置如下:16G內(nèi)存,4核CPU,1T硬盤.Red Hat 6.2操作系統(tǒng).

基于前述對OceanBase分析,為了減少通信的時間和空間開銷,過濾條件最好可以下壓到基準(zhǔn)服務(wù)器中,過濾條件存在主鍵索引時速度比較快.根據(jù)優(yōu)化策略可以得知:展開減少通信開銷,主鍵索引減少子查詢執(zhí)行時間.由于無用子樹切除和聚集函數(shù)消除都是在特殊場景下的應(yīng)用,雖然會對性能產(chǎn)生一定影響,但是不算在優(yōu)化的范圍內(nèi),所以本次實驗并不包括這些因素對實驗的影響.設(shè)計實驗如下.

(1)展開有效性驗證,當(dāng)父查詢表很大,子查詢表很小,執(zhí)行會有很多次的通信時間開銷,使用子查詢展開技術(shù)應(yīng)該優(yōu)化性能更好一點.

(2)主鍵索引有效性驗證,當(dāng)父查詢表很小,子查詢表很大,執(zhí)行時間主要是子查詢表的查詢時間,通過主鍵索引可以更好的優(yōu)化性能.

(3)展開穩(wěn)定性驗證,當(dāng)父查詢和子查詢表都很大的情況下,分布式的通信開銷和子查詢的執(zhí)行時間開銷都很大的情況下,主鍵索引不會明顯的優(yōu)化性能,但是使用子查詢展開應(yīng)該可以有效的提升性能,并且不會有很大的波動.

實驗所用的表結(jié)構(gòu)如下:

STUDENT(SNO,SNAME,SSEX,SAGE,SDEPT);

COURSE(CNO,CNAME,CPNO,CCREDIT);

SC(SNO,CNO,GRADE).

其中加下劃線的列為主鍵列.

3.2 子查詢展開有效性驗證

該實驗測試在父查詢表很大,子查詢表很小的情況下,有無主鍵索引性能上的差異,另外在無主鍵索引的情況下,使用子查詢展開優(yōu)化對性能的影響.測試父查詢表為SC表,表中有100萬行元組,下面語句中使用到的SNO列為主鍵列.子查詢表為COURSE表,表中130行元組,其中CNO為主鍵列.

使用主鍵測試語句為:SELECT*FROM SC WHERE SNO＜X AND EXISTS(SELECT *FROM COURSE WHERE CNO=SC.CNO);其執(zhí)行結(jié)果和展開后的執(zhí)行結(jié)果見圖2.

圖2 主鍵索引的情況下優(yōu)化后的性能Fig.2Performance of using primary key index and pull up subquery

由圖2可以看出,在父查詢表很大,子查詢表很小的情況下,即使有主鍵索引的情況,對于分布式而言,通信開銷仍然是不可忽略的.將子查詢展開后性能提升的比較明顯.

不使用主鍵索引的語句為:SELECT*FROM SC WHERE SNO＜X AND EXISTS(SELECT*FROM COURSE WHERE CPNO=SC.CNO);其執(zhí)行結(jié)果和展開后的執(zhí)行結(jié)果見圖3.

圖3 無主鍵索引的情況下優(yōu)化后的性能Fig.3Performance of without primary key index and pull up subquery

從兩次實驗結(jié)果可以看出,是否使用了主鍵索引,性能上并沒有提升了很多.因為在子查詢表很小的情況下,主鍵索引優(yōu)化的空間很小.并且在這種情況下,通信時間開銷是不可回避的.所以這種情況下,使用子查詢展開技術(shù)是非常有效的優(yōu)化手段.

3.3 主鍵索引有效性驗證

該實驗測試在父查詢表很小,但是子查詢表很大的情況下,主鍵索引和子查詢展開對性能的影響.實驗環(huán)境同上.父查詢使用COURSE表,子查詢使用SC表.

使用主鍵測試語句為:SELECT*FROM COURSE WHERE CNO＜X AND EX-ISTS(SELECT*FROM SC WHERE CNO=COURSE.CNO);其執(zhí)行結(jié)果和展開后的執(zhí)行結(jié)果見圖4.

圖4 有主鍵索引的情況下優(yōu)化后的性能Fig.4Performance of using primary key index and pull up subquery

由圖4可以看出,有主鍵索引的情況下,主鍵的性能優(yōu)于子查詢展開.因為在父查詢表很小的情況下,在分布式系統(tǒng)中,通信開銷不是很大.但是由于子查詢的表很大,所以對子查詢的優(yōu)化就有很大的空間.并且展開子查詢后需要很大的空間開銷.

不使用主鍵索引的語句為:SELECT*FROM COURSE WHERE CNO＜X AND EXISTS(SELECT*FROM SC WHERE SGRADE=COURSE.CNO);其執(zhí)行結(jié)果和展開后的執(zhí)行結(jié)果見表5.

圖5 無主鍵索引的情況下優(yōu)化后的性能Fig.5Performance of without primary key index and pull up subquery

由圖5可知,子查詢展開技術(shù)和主鍵索引都對性能有很大的提升,但是從子查詢展開技術(shù)效果比較明顯.但是在有主鍵索引的情況下,不展開子查詢效果更好一點.在沒有主鍵索引的情況下,使用子查詢展開較好.

3.4 子查詢展開穩(wěn)定性驗證

該實驗測試在父查詢和子查詢表很大的情況下,主鍵索引和子查詢展開對性能的影響.測試環(huán)境同上.測試父查詢表為STUDENT表,表中存在100萬行元組,子查詢是SC表.

使用主鍵測試語句為:SELECT*FROM STUDENT WHERE SNO＜X AND EXISTS(SELECT*FROM SC WHERE SNO=STUDENT.SNO);其執(zhí)行結(jié)果和展開后的執(zhí)行結(jié)果見圖6.

由圖6可知,在有主鍵索引的情況下,如果父查詢的結(jié)果集比較小,主鍵索引的效果更好一點.這時候?qū)τ谡归_反而不是很好的選擇.但是當(dāng)子查詢的結(jié)果集增大時,分布式環(huán)境中的通信開銷隨之增大,耗時和子查詢的結(jié)果集成正比.但是可以看出,子查詢的結(jié)果集對展開的情況沒有太大的影響.

不使用主鍵索引的語句為:SELECT*FROM STUDENT WHERE SNO＜X AND EXISTS(SELECT*FROM SC WHERE SNO=STUDENT.SAGE);其執(zhí)行結(jié)果和展開后的執(zhí)行結(jié)果見圖7.

圖6 有主鍵索引的情況下優(yōu)化后的性能Fig.6Performance of using primary key index and pull up subquery

圖7 無主鍵索引的情況下優(yōu)化后的性能Fig.7Performance of without primary key index and pull up subquery

由圖7可知,主鍵索引的耗時和父查詢的元組數(shù)成正比,在數(shù)據(jù)集比較小的情況下,表現(xiàn)突出.但是父查詢的元組數(shù)對子查詢展開沒有太大的影響,所以這種情況下,比較適用于選擇子查詢展開避免過多的通信開銷.

4 總結(jié)

相關(guān)子查詢是關(guān)系數(shù)據(jù)庫的重要功能之一,按照傳統(tǒng)方式執(zhí)行的相關(guān)子查詢是一種非常耗時的操作,對于相關(guān)子查詢的優(yōu)化是有重要意義的.本文研究分析現(xiàn)有相關(guān)子查詢的優(yōu)化策略,并結(jié)合分布式數(shù)據(jù)庫的特點,將無用分支切除、子查詢展開,索引、聚集函數(shù)消除等相關(guān)子查詢優(yōu)化策略應(yīng)用于分布式數(shù)據(jù)庫中.在分布式環(huán)境中傳統(tǒng)執(zhí)行策略會產(chǎn)生大量的通信開銷,因此選擇子查詢展開技術(shù)減少通信時間開銷,使用索引降低通信空間開銷.實驗了基于OCEANBASE分布式數(shù)據(jù)庫的EXISTS相關(guān)子查詢,并在不同的應(yīng)用場景下比較了不同優(yōu)化策略對查詢性能的影響.

根據(jù)實驗結(jié)果可以得知,當(dāng)父查詢執(zhí)行其它過濾條件后的結(jié)果集較小,并且子查詢有索引的情況下,其性能優(yōu)于子查詢展開后的性能.當(dāng)父查詢結(jié)果集比較大,或者是沒有主鍵索引的情況下,使用子查詢展開技術(shù)對性能提升很大.使用索引的情況,執(zhí)行時間和父查詢的結(jié)果集大小成正比,但是子查詢展開技術(shù)相對來說比較穩(wěn)定,在大數(shù)據(jù)的情況下比較適用.

針對子查詢不滿足展開條件的情況,如何對其進行優(yōu)化,本文沒有提出切實的解決方法,這將在以后的工作中進一步深入研究.

［1］KIM W.On optimizing an SQL-like nested query[J].ACM Transactions on Database Systems(TODS),1982, 7(3):443-469.

［2］薩師煊,王珊.數(shù)據(jù)庫系統(tǒng)概論[M].北京:高等教育出版社,2000.

［3］李海翔.數(shù)據(jù)庫查詢優(yōu)化器的藝術(shù)[M].北京:機械工業(yè)出版社,2014.

［4］SILBERSCHATZ A,KORTH H F,SUDARSHAN S.Database System Concepts[M].New York:McGraw-Hill, 1997.

［5］CAO B.Optimization of complex nested queries in relational databases[C]//Proceedings of 22nd International Conference on Data Engineering Workshops.[S.l.]:IEEE,2006:X137.

［6］RAO J,ROSS K A.Reusing invariants:A new strategy for correlated queries[C]//SIGMOD,1998,27(2):37-48.

［7］BELLAMKONDAS,AHMED R,WITKOWSKI A,et al.Enhanced subquery optimizations in oracle[C]//Proceedings of the VLDB Endowment.Germany:DBLP,2009,2(2):1366-1377.

［8］彭智勇.PostgreSQL數(shù)據(jù)庫內(nèi)核分析[M].北京:機械工業(yè)出版社,2012.

［9］KHAN M,KHAN M N A.Exploring query optimization techniques in relational databases[J].International Journal of Database Theory&Application,2013,6(3):11-20.

［10］魏士偉,黃文明,康業(yè)娜,等.分布式數(shù)據(jù)庫中基于半連接的查詢優(yōu)化算法研究[J].計算機應(yīng)用,2007,27(B06):34-36.

［11］SHIOIT,HATANOK.Queryprocessingoptimizationusingdisk-basedrow-storeandcolumnstore[C]//Proceedings of the 17th International Conference on Information Integration and Web-based Applications&Services.New York:ACM,2015:69.

［12］CHEN G,WU Y,LIU J,et al.Optimization of sub-query processing in distributed data integration systems[J]. Journal of Network and Computer Applications,2011,34(4):1035-1042.

［13］GALINDO-LEGARIA C,JOSHI M.Orthogonal optimization of subqueries and aggregation[C]//ACM SIGMOD Record.New York:ACM,2001,30(2):571-581.

(責(zé)任編輯:張晶)

Optimization strategies of correlated subquery for distributed database

MAO Si-yu,ZHANG Li-jun,ZHANG Xiao-fang,GAO Jin-tao,LI Zhan-huai
(School of Computer,Northwestern Polytechnical University,Xi’an710129,China)

A query which occurs in another query as a filter is called subquery,and if the filtering condition of a subquery depends on its parent query,it is called correlated subquery.Generally,the execution cost of query with correlated subquery is high due to that subquery would be executed multiply,which leads to multiple disk access and extra communications in distributed system.Based on the investigation of the classical optimization strategies of correlated subquery,and according to the characteristics of distributed system,we adopt pulling up subquery,removing useless tree and eliminating aggregation function to optimize correlated subquery in distributed database system.And we implement these strategies in the distributed relational database OceanBase for the correlated subquery predicate EXIST.Experiment results show that these strategies can significantly improve the performance of a correlated subquery.

distributed database;correlated subquery;subquery optimization

TP392

A

10.3969/j.issn.1000-5641.2016.05.007

1000-5641(2016)05-0056-11

2016-05

中央高校基本科研業(yè)務(wù)費專項資金資助(3102015JSJ0004)

毛思語,女,碩士研究生,研究方向為數(shù)據(jù)庫.E-mail:maosiyu@mail.nwpu.edu.cn.

張利軍,男,講師,研究方向為數(shù)據(jù)庫理論,數(shù)據(jù)管理技術(shù). E-mail:zhanglijun@nwpu.edu.cn.