查詢優(yōu)化器連接順序評(píng)估

陳 婷,項(xiàng)兆坤,徐金凱,張 蓉

（華東師范大學(xué) 數(shù)據(jù)科學(xué)與工程學(xué)院,上海 200062）

0 引 言

分析型數(shù)據(jù)庫(kù)管理系統(tǒng)主要用于完成聯(lián)機(jī)分析處理 (Online Analytical Processing,OLAP) 任務(wù),這類系統(tǒng)被廣泛應(yīng)用于數(shù)智供應(yīng)鏈與物流科技、金融分析、銷售業(yè)務(wù)分析等數(shù)據(jù)管理領(lǐng)域,為這些領(lǐng)域提供復(fù)雜的分析處理服務(wù).在OLAP 負(fù)載中,查詢往往會(huì)涉及多個(gè)關(guān)系,即多表連接.數(shù)據(jù)庫(kù)查詢優(yōu)化器在處理多表連接查詢時(shí),會(huì)面對(duì)一個(gè)復(fù)雜的連接順序選擇 (Join Order Selection,JOS) 問(wèn)題,也稱為連接順序優(yōu)化問(wèn)題,即從連接順序搜索空間中選出性能最優(yōu)的連接順序.不同的連接順序在語(yǔ)義上等價(jià)(即能獲得相同的結(jié)果集),但是查詢效率有著顯著差異,在執(zhí)行時(shí)間上可能呈現(xiàn)幾個(gè)數(shù)量級(jí)的差異.因此,連接順序的選擇是一個(gè)十分關(guān)鍵的查詢優(yōu)化問(wèn)題[1].由于連接操作的交換性和結(jié)合性,隨著連接表數(shù)量的增加,搜索空間的大小會(huì)呈指數(shù)級(jí)增長(zhǎng),如考慮左深樹、右深樹和濃密樹時(shí),N個(gè)表連接的搜索空間高達(dá),無(wú)法在多項(xiàng)式時(shí)間內(nèi)解決.Ibaraki 等[2]證明了連接順序選擇是一個(gè)NP-hard 問(wèn)題.

在研究連接順序優(yōu)化問(wèn)題時(shí),通常會(huì)以查詢中的表和連接關(guān)系作為結(jié)點(diǎn)和邊構(gòu)建連接圖,以圖的形式展現(xiàn)查詢中各表如何連接.在很大程度上,找到最優(yōu)連接順序的復(fù)雜度與連接圖的連接形狀有關(guān)[3].不同的連接形狀具有不同的優(yōu)化特性,對(duì)應(yīng)著不同的優(yōu)化策略及優(yōu)化難度,這為優(yōu)化器連接順序的選擇帶來(lái)很大的挑戰(zhàn).

如果計(jì)算得到最優(yōu)連接順序,那么優(yōu)化算法本身將會(huì)耗費(fèi)大量時(shí)間,反而會(huì)降低查詢效率.因此,如何在優(yōu)化時(shí)間與優(yōu)化效果之間進(jìn)行權(quán)衡是連接順序優(yōu)化算法需要考慮的核心問(wèn)題.傳統(tǒng)的連接順序優(yōu)化算法會(huì)對(duì)連接順序的搜索空間進(jìn)行剪枝,如基于動(dòng)態(tài)規(guī)劃的方法[4-5]和基于啟發(fā)式算法的方法[6-8].隨著機(jī)器學(xué)習(xí)的發(fā)展,目前深度學(xué)習(xí)[9]和強(qiáng)化學(xué)習(xí)[10-13]也被運(yùn)用于處理連接順序優(yōu)化問(wèn)題.因?yàn)?連接順序的選擇,在很大程度上決定了數(shù)據(jù)庫(kù)分析處理的性能,所以,連接順序選擇問(wèn)題備受相關(guān)領(lǐng)域研究者的關(guān)注.然而,面對(duì)眾多連接順序選擇策略,如何評(píng)估它們的優(yōu)劣還是一個(gè)難點(diǎn)問(wèn)題.評(píng)估連接順序選擇策略就是計(jì)算優(yōu)化器所選連接順序的執(zhí)行時(shí)間與最優(yōu)連接順序執(zhí)行時(shí)間的相對(duì)差距.文獻(xiàn)[14]對(duì)已有基于學(xué)習(xí)的基數(shù)預(yù)估算法進(jìn)行評(píng)估,分析現(xiàn)有基于學(xué)習(xí)的方法是否適用于基數(shù)預(yù)估問(wèn)題.現(xiàn)有工作沒(méi)有一整套通用的評(píng)估連接順序選擇策略的方法,無(wú)法有效評(píng)估各種連接順序選擇策略的優(yōu)劣.同時(shí),目前已有的評(píng)測(cè)基準(zhǔn)和評(píng)測(cè)工具的數(shù)據(jù)大多缺乏真實(shí)應(yīng)用數(shù)據(jù)特征 (如多樣的傾斜度),且負(fù)載中往往只涉及鏈?zhǔn)健⑿切?、樹型等?jiǎn)單連接形狀,不能覆蓋所有連接形狀,無(wú)法針對(duì)不同連接形狀進(jìn)行有效評(píng)測(cè).

為了有效評(píng)測(cè)優(yōu)化器在連接順序選擇上的優(yōu)化效果,本文設(shè)計(jì)了面向不同連接形狀的連接順序選擇策略評(píng)測(cè)工具.本文提出了基于主鍵的確定性數(shù)據(jù)生成方法、適用于不同連接形狀的連接模板生成算法、基于結(jié)果導(dǎo)向的參數(shù)實(shí)例化與過(guò)濾謂詞生成方法,實(shí)現(xiàn)對(duì)優(yōu)化器查詢處理性能的評(píng)估.

1 相關(guān)工作

常見的評(píng)測(cè)基準(zhǔn),比如,Star Schema Benchmark[15]、TPC-H[16]、TPC-DS[17]主要用于數(shù)據(jù)庫(kù)查詢執(zhí)行的整體性能評(píng)測(cè),其數(shù)據(jù)分布為均勻分布,而真實(shí)應(yīng)用場(chǎng)景中的數(shù)據(jù)往往為非均勻分布,有較大的數(shù)據(jù)傾斜度,并且其負(fù)載僅涉及鏈?zhǔn)?、樹型以及星型的?jiǎn)單連接形狀.因此,這些評(píng)測(cè)基準(zhǔn)無(wú)法對(duì)查詢優(yōu)化器的連接順序選擇進(jìn)行針對(duì)性評(píng)測(cè).

基于網(wǎng)絡(luò)電影數(shù)據(jù)集(Internet Movie Data Base,IMDB)的Join Order Benchmark (JOB)[18]可用于評(píng)測(cè)基數(shù)預(yù)估、連接順序選擇,但是其數(shù)據(jù)集不可擴(kuò)展,數(shù)據(jù)傾斜度固定.同時(shí),雖然它提供了相對(duì)復(fù)雜的連接,單個(gè)查詢最大連接數(shù)為16 (平均值為8),但連接形狀均為含環(huán)型,因此,無(wú)法針對(duì)某一特定連接形狀進(jìn)行專項(xiàng)評(píng)測(cè),且缺乏連接順序選擇的評(píng)測(cè)指標(biāo).JOB 共有33 個(gè)查詢模板,每個(gè)模板只有2～ 5 個(gè)查詢,若要評(píng)測(cè)深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的連接順序優(yōu)化方法,JOB 作為訓(xùn)練數(shù)據(jù)來(lái)說(shuō)不夠充足.許多工作[19-21]會(huì)使用JOB 的子集JOB-LIGHT 進(jìn)行基數(shù)預(yù)估的評(píng)測(cè),它基于簡(jiǎn)化的IMDB 數(shù)據(jù)集,僅包含70 個(gè)查詢,且均為連接數(shù)小于或等于5 的星型負(fù)載.針對(duì)基數(shù)預(yù)估的評(píng)測(cè)基準(zhǔn)有STATSCEB[22]和IMDB-CEB[23],分別采用真實(shí)的數(shù)據(jù)集STATS 和IMDB,人工構(gòu)建查詢負(fù)載.它們?nèi)狈﹄S機(jī)可控的連接數(shù)目和豐富的連接形狀.

目前有許多工作基于現(xiàn)有評(píng)測(cè)基準(zhǔn)的數(shù)據(jù)集與負(fù)載設(shè)計(jì)針對(duì)查詢優(yōu)化器的評(píng)測(cè)工具,它們大致分為兩類.第一類是面向查詢優(yōu)化器的某個(gè)特定部分的評(píng)測(cè).Gu 等[24]針對(duì)查詢優(yōu)化器的代價(jià)模型設(shè)計(jì)了評(píng)測(cè)工具TAQO,對(duì)優(yōu)化器候選執(zhí)行計(jì)劃列表的預(yù)估代價(jià)排名和真實(shí)代價(jià)排名進(jìn)行比較,得到優(yōu)化器所選執(zhí)行計(jì)劃的排名指標(biāo),以計(jì)算優(yōu)化器代價(jià)模型的準(zhǔn)確性.TAQO 只提出了評(píng)測(cè)方法與評(píng)測(cè)指標(biāo),沒(méi)有設(shè)計(jì)數(shù)據(jù)集與負(fù)載,在實(shí)驗(yàn)時(shí)使用TPC-H 作為測(cè)試負(fù)載.Qin 等[25]計(jì)算代價(jià)模型中磁盤代價(jià)估計(jì)的準(zhǔn)確性,實(shí)現(xiàn)細(xì)粒度的評(píng)測(cè)方法.

第二類是面向查詢優(yōu)化器整體的評(píng)測(cè).Li 等[26]提出了評(píng)測(cè)查詢優(yōu)化器的工具OptMark,他們利用TPC-DS 的數(shù)據(jù)與負(fù)載,設(shè)計(jì)了基于質(zhì)量與效率的評(píng)價(jià)指標(biāo),用以評(píng)測(cè)整體優(yōu)化器的端到端性能.OptMark 關(guān)注優(yōu)化器選擇的最終物理執(zhí)行計(jì)劃的有效性.對(duì)于一個(gè)查詢,在其可遍歷的執(zhí)行計(jì)劃搜索空間中,優(yōu)化器所選出的默認(rèn)執(zhí)行計(jì)劃比其他執(zhí)行計(jì)劃耗時(shí)短,則稱該查詢?yōu)橛行Р樵?有效性是指有效查詢?cè)谒胁樵冎兴嫉谋壤?由于不同物理執(zhí)行計(jì)劃可能擁有相同的連接順序,該有效性指標(biāo)不能直觀反映連接順序的優(yōu)劣.TiDB 參考OptMark 的有效性指標(biāo),使用TPC-H 和JOB 的數(shù)據(jù)集和負(fù)載,實(shí)現(xiàn)了Horoscope 工具,以評(píng)估TiDB 的查詢優(yōu)化器性能.

綜上所述,現(xiàn)有的評(píng)測(cè)基準(zhǔn)與評(píng)測(cè)工具有3 點(diǎn)不足: ①數(shù)據(jù)缺乏真實(shí)應(yīng)用數(shù)據(jù)特征,如多樣的傾斜度;② 負(fù)載缺乏隨機(jī)可控的連接數(shù)目和豐富的連接形狀;③缺乏有效的連接順序評(píng)測(cè)指標(biāo).因此,它們無(wú)法充分評(píng)測(cè)優(yōu)化器的連接順序選擇問(wèn)題,無(wú)法得到可靠的評(píng)測(cè)結(jié)果.

2 連接形狀

連接圖是以表為結(jié)點(diǎn),連接關(guān)系為邊的無(wú)向圖,展示查詢中各表之間的連接關(guān)系.示例1 中查詢包含4 張表(表A、表B、表C、表D)和4 個(gè)連接謂詞,該查詢的連接圖 (圖1),具有4 個(gè)頂點(diǎn)和4 條邊.

圖1 示例1 的連接圖Fig.1 Join graph of example 1

示例1SELECT COUNT(*) FROM A,B,C,D WHERE A.pk=B.fk1AND A.pk=C.fk1AND C.pk=B.fk2AND D.pk=B.fk3AND A.col1＞ 100 AND B.col2＜=2000 AND C.col1+C.col2＞ 300 AND D.col1=400;

連接圖根據(jù)連接形狀的不同,可以分為7 類 (圖2),分別為鏈?zhǔn)?、星型、樹型、環(huán)型、含環(huán)型、網(wǎng)格型和集團(tuán)型.

圖2(a)是簡(jiǎn)單的鏈?zhǔn)竭B接形狀,查詢中的表按順序連接,在實(shí)際應(yīng)用中很常見,同時(shí)也較容易優(yōu)化.圖2(b)星型連接常見于數(shù)據(jù)倉(cāng)庫(kù)應(yīng)用中,此類查詢中的表分為一張事實(shí)表和多張維度表.事實(shí)表是數(shù)據(jù)倉(cāng)庫(kù)中的中央表,存儲(chǔ)有事實(shí)記錄的表,如交易記錄、銷售明細(xì)、系統(tǒng)日志等;維度表用于保存維度的屬性值,即事實(shí)表中屬性的相關(guān)詳細(xì)信息,如日期維度表、產(chǎn)品維度表、用戶維度表等.星型可以看成將多張維度表連接到中央事實(shí)表.圖2(c)樹型可以看成是鏈?zhǔn)胶托切偷幕旌项愋?連接形式更加隨機(jī),會(huì)產(chǎn)生更大的連接順序搜索空間.圖2(d)環(huán)型中的所有表通過(guò)依賴關(guān)系連接形成一條環(huán)路,處理環(huán)路的復(fù)雜度高,給某些連接順序選擇策略帶來(lái)極大挑戰(zhàn).圖2(e)含環(huán)型的連接圖中至少存在一條環(huán)路,即可能存在多條環(huán)路,增大搜索空間以及延長(zhǎng)優(yōu)化時(shí)間.示例1 的連接形狀即含環(huán)型.圖2(f)網(wǎng)格型的連接圖呈現(xiàn)網(wǎng)格形狀,每張表至少與另外兩張表存在依賴關(guān)系.網(wǎng)格型由于存在大量的環(huán)而難以優(yōu)化.圖2(g)集團(tuán)型查詢中的任意兩張表之間都存在一個(gè)連接謂詞,是連接順序優(yōu)化的最壞情況.

圖2 連接圖的不同形狀Fig.2 Shapes of join graphs

連接形狀越復(fù)雜,對(duì)其優(yōu)化的時(shí)間復(fù)雜度和空間復(fù)雜度就越高.同時(shí),由于不同連接形狀的特性,適合一種連接形狀的連接順序優(yōu)化算法可能不適合另一種連接形狀,健壯的優(yōu)化器需針對(duì)不同的連接形狀采用不同的優(yōu)化策略.

3 評(píng)測(cè)系統(tǒng)整體架構(gòu)

評(píng)測(cè)系統(tǒng)整體架構(gòu)如圖3 所示,分為兩個(gè)部分: 測(cè)試場(chǎng)景生成器和連接順序評(píng)估器.測(cè)試場(chǎng)景生成器由模式生成、數(shù)據(jù)生成和負(fù)載生成3 個(gè)部分組成,連接順序評(píng)估器由查詢計(jì)劃解析、連接順序枚舉、連接順序評(píng)估3 個(gè)部分組成.

圖3 系統(tǒng)整體架構(gòu)Fig.3 System architecture

首先,系統(tǒng)讀入用戶定義的配置文件,配置文件的內(nèi)容包括: 數(shù)據(jù)庫(kù)配置、模式配置 (如生成表數(shù)量及規(guī)模、各表的屬性列數(shù)目、各表的屬性列數(shù)據(jù)分布、參與連接的表數(shù)量、查詢連接圖形狀等)、輸出文件保存路徑、其他自定義配置.測(cè)試場(chǎng)景生成器根據(jù)配置文件中的定義模式進(jìn)行模式生成,生成每張表的規(guī)模、每張表的屬性列數(shù)目及數(shù)據(jù)類型、屬性列的數(shù)據(jù)傾斜度、每張表的參照關(guān)系等.

然后,數(shù)據(jù)生成模塊采用基于主鍵的確定性數(shù)據(jù)生成機(jī)制生成各屬性數(shù)據(jù).負(fù)載生成模塊包括連接圖生成和過(guò)濾謂詞生成兩部分,該模塊先基于各表的參照關(guān)系采樣生成具有不同連接形式的負(fù)載模版,再通過(guò)結(jié)果導(dǎo)向的參數(shù)實(shí)例化方法生成過(guò)濾謂詞.

最后,測(cè)試場(chǎng)景生成器將所生成的數(shù)據(jù)和負(fù)載通過(guò)Java 數(shù)據(jù)庫(kù)連接 (Java Database Connectivity,JDBC) 接口導(dǎo)入數(shù)據(jù)庫(kù),將數(shù)據(jù)庫(kù)查詢優(yōu)化器所選擇的查詢計(jì)劃 (通過(guò)“EXPLAIN”關(guān)鍵字得到) 返回給連接順序評(píng)估器.由連接順序評(píng)估器對(duì)查詢計(jì)劃進(jìn)行解析以獲得優(yōu)化器選擇的連接順序,再將該連接順序與評(píng)估器采樣的連接順序共同放入評(píng)估池,對(duì)評(píng)估池中所有連接順序的性能進(jìn)行對(duì)比,最終輸出連接順序評(píng)估結(jié)果.

4 測(cè)試場(chǎng)景生成器

4.1 數(shù)據(jù)生成

本文采用基于主鍵的確定性數(shù)據(jù)生成方式[27-28]進(jìn)行數(shù)據(jù)生成.數(shù)據(jù)生成器為每個(gè)屬性列指定生成函數(shù),屬性列的值以主鍵為自變量通過(guò)生成函數(shù)映射得到.數(shù)據(jù)生成器規(guī)定生成函數(shù)必須為滿射函數(shù),若滿射函數(shù)F:X →Y,則Y中的所有元素在X中都能找到原像.假設(shè)某張表的主鍵x∈[0,n],其屬性列c的生成函數(shù)為F(x) ,則主鍵x對(duì)應(yīng)屬性列c的值為y=F(x) ,其中y∈{y|y=F(x),x ∈[0,n]}.需要注意的是,非數(shù)字類型的數(shù)據(jù)類型 (如Varchar) 需要進(jìn)行類型轉(zhuǎn)化.通過(guò)定義符合分布的生成函數(shù)即可保證屬性列數(shù)據(jù)的分布,如高斯分布和ZipFian 分布.

基于主鍵的數(shù)據(jù)映射 (生成) 實(shí)現(xiàn)了數(shù)據(jù)感知的參數(shù)實(shí)例化.在生成過(guò)濾謂詞時(shí),通過(guò)求解各屬性與主鍵的關(guān)聯(lián)關(guān)系的滿足性約束,即可感知可供采樣的數(shù)據(jù)范圍,故而保證查詢結(jié)果不為空,生成有效的查詢.

4.2 負(fù)載生成

為了實(shí)現(xiàn)對(duì)查詢優(yōu)化器連接順序選擇的質(zhì)量評(píng)測(cè),負(fù)載需要擁有不同的連接形狀、豐富的連接數(shù)量以及多樣的謂詞基數(shù).無(wú)論是現(xiàn)有的評(píng)測(cè)基準(zhǔn)負(fù)載,還是某現(xiàn)實(shí)應(yīng)用負(fù)載都不能包含所有負(fù)載特征,代表所有負(fù)載.本文的可配置負(fù)載生成能夠根據(jù)配置文件,生成滿足特定需求的負(fù)載,對(duì)負(fù)載的覆蓋面更廣,能更好地評(píng)估優(yōu)化器的優(yōu)化能力.

負(fù)載生成階段按照給定配置文件從模式中選取規(guī)定數(shù)量的表以及各表之間的主外鍵參照關(guān)系,進(jìn)行連接圖的生成,接著通過(guò)結(jié)果導(dǎo)向的參數(shù)實(shí)例化生成基數(shù)不同 (且不為零) 的過(guò)濾謂詞.

4.2.1 連接圖生成

連接圖生成器生成連接圖G=(V,E) ,其中V是參與連接的表的集合,E是邊的集合,E中的每一條邊是連接兩張表的連接謂詞,表的連接關(guān)系由主外鍵參照關(guān)系決定.G的初始狀態(tài)為空集 (G=?),連接圖生成器依次對(duì)G進(jìn)行加點(diǎn)操作 (定義1) 或加邊操作 (定義2),直至得到符合配置要求的連接圖.

定義1(加點(diǎn)操作) 向連接圖G=(V,E)中添加一個(gè)結(jié)點(diǎn)v,v要滿足以下條件:

(1)vV;

(2)存在連接謂詞使得v與集合中的某一結(jié)點(diǎn)u相連,即存在e=(u,v) ;

(3)若連接形狀為樹型,則u∈V;若連接形狀為鏈?zhǔn)交颦h(huán)型,則u∈V且u的度為1;若連接形狀為星型,則u∈V且u為中央事實(shí)表.

定義2(加邊操作) 向連接圖G=(V,E)中添加一條邊e=(u,v),u,v為兩個(gè)結(jié)點(diǎn),e滿足以下條件:

2.2 治療前后兩組MAP、HR、SVV水平對(duì)比 治療后觀察組HR水平明顯高于對(duì)照組，而MAP、SVV水平均明顯低于對(duì)照組，差異有統(tǒng)計(jì)學(xué)意義(均P<0.05)。見表2。

(1)eE;

(2)u∈V且v∈V.

適用于不同連接形狀的連接模板生成算法的基本思路是: 分別通過(guò)加點(diǎn)操作和加邊操作為連接圖添加新表和新的連接關(guān)系 (邊) 以生成高質(zhì)量的多表連接模板,使模板中的連接均為有效的主外鍵連接,且連接形狀與連接數(shù)目符合要求,如算法1 所示.

首先,初始化連接圖G和度為1 的結(jié)點(diǎn)集合D為空集 (行1—2).接著加入第一張表,若生成星型連接,則選擇規(guī)模最大的表作為中央事實(shí)表加入連接圖G;若生成其他類型,則從所有表中隨機(jī)選擇一張表加入連接圖G(行3—7).然后,根據(jù)目標(biāo)連接形狀不斷向G中添加結(jié)點(diǎn)和邊直至結(jié)點(diǎn)數(shù)量滿足規(guī)定表數(shù)量為止 (行9—23).第9 行|V|表示集合V中元素的個(gè)數(shù),即當(dāng)前G中的結(jié)點(diǎn)數(shù)量.樹型連接的生成,規(guī)定每次向連接圖G中添加一個(gè)結(jié)點(diǎn)v與一條邊e,即進(jìn)行一次加點(diǎn)操作和一次加邊操作(行10—12).鏈?zhǔn)竭B接同樣進(jìn)行一次加點(diǎn)操作和一次加邊操作,且邊e需要連接結(jié)點(diǎn)v和度為1 的結(jié)點(diǎn)u.在鏈?zhǔn)竭B接生成過(guò)程中 (從加入第二張表起),需要同步更新度為1 的結(jié)點(diǎn)集合D,確保始終存在兩個(gè)度為1 的結(jié)點(diǎn),即首尾結(jié)點(diǎn) (行15—19).環(huán)型與鏈?zhǔn)较啾?相同的是所有表都處于一條鏈上,不同的是環(huán)型的首尾兩張表間存在一條邊.最后,環(huán)型的生成需要進(jìn)行一次額外加邊操作 (行24—27).星型連接生成將模式中規(guī)模最大的表作為中央事實(shí)表,隨機(jī)選擇其余表作為維度表.在選擇維度表時(shí),每次對(duì)連接圖進(jìn)行一次加點(diǎn)操作和一次加邊操作,且要求新加入的結(jié)點(diǎn)v與事實(shí)表存在依賴關(guān)系,新加入的邊e需要連接維度表v和事實(shí)表 (行21).當(dāng)參與連接的表數(shù)量為N時(shí),則算法循環(huán)N次,每次向連接圖中加入一張表,時(shí)間復(fù)雜度為O(N) .觀察常用的OLAP 評(píng)測(cè)基準(zhǔn)如TPC-H、TPC-DS、SSB、JOB 等,它們單個(gè)查詢的最大連接數(shù)為18,因此,N通常不是很大.

4.2.2 過(guò)濾謂詞生成

基數(shù)預(yù)估的結(jié)果影響代價(jià)模型,從而決定連接順序的選擇.而基數(shù)預(yù)估分為對(duì)基表過(guò)濾算子的預(yù)估和對(duì)連接算子的預(yù)估,4.2.1 節(jié)已由連接圖確定參與連接的關(guān)系以及連接條件,本節(jié)將在連接圖的基礎(chǔ)上生成基于單個(gè)表的標(biāo)準(zhǔn)過(guò)濾謂詞.

參數(shù)實(shí)例化是過(guò)濾謂詞生成過(guò)程中不可或缺的部分,它控制算子的中間結(jié)果集大小,從而使得查詢優(yōu)化器選擇代價(jià)不同的查詢執(zhí)行計(jì)劃,直接影響查詢性能.本文采用基于結(jié)果導(dǎo)向的參數(shù)實(shí)例化算法[28],實(shí)現(xiàn)有效的查詢參數(shù)實(shí)例化.謂詞參數(shù)的取值范圍可由主鍵到屬性列的映射函數(shù)以及連接條件確定性得到,該算法根據(jù)取值范圍選擇合理的參數(shù),確保經(jīng)過(guò)參數(shù)實(shí)例化的過(guò)濾謂詞與連接謂詞有效,即無(wú)空值返回.

5 連接順序評(píng)估器

首先,連接順序評(píng)估器通過(guò)“EXPLAIN”關(guān)鍵字獲得查詢優(yōu)化器選擇的執(zhí)行計(jì)劃,從中提取出選定連接順序;其次,枚舉適當(dāng)數(shù)量的連接順序 (稱為枚舉空間),將優(yōu)化器選擇的連接順序與枚舉的連接順序共同放入同個(gè)評(píng)估池;再次,強(qiáng)制數(shù)據(jù)庫(kù)依次按照評(píng)估池中的連接順序執(zhí)行,得到各自的執(zhí)行時(shí)間;最后,利用兩個(gè)評(píng)估指標(biāo)對(duì)優(yōu)化器連接順序的選擇進(jìn)行評(píng)估.

5.1 枚舉空間

表1 連接順序的搜索空間Tab.1 Search space of join order

執(zhí)行搜索空間中所有連接順序是十分耗時(shí)的,本節(jié)采用式 (1),以一定誤差和置信水平下的最小樣本數(shù)量作為枚舉空間大小[29].

式(1)中:n是所需要枚舉空間大小;Z是置信水平的Z統(tǒng)計(jì)量,如95%置信水平的Z統(tǒng)計(jì)量為1.96;p是總體的估計(jì)差異性,該值一般未知,設(shè)定為0.5;e是相對(duì)誤差.

在實(shí)驗(yàn)中設(shè)定置信水平為95%,相對(duì)誤差為10%,即Z=1.96,e=0.1,根據(jù)式 (1) 得到枚舉空間大小約為97 個(gè) (向上取整).

5.2 評(píng)估指標(biāo)

為了評(píng)價(jià)查詢優(yōu)化器的連接順序優(yōu)劣,本節(jié)引入兩個(gè)評(píng)估指標(biāo): MRR (Mean Reciprocal Rank)和偏差.MRR 著重于查詢優(yōu)化器所選連接順序的排名,偏差對(duì)比查詢優(yōu)化器所選連接順序的執(zhí)行時(shí)間與枚舉空間中所有連接順序的執(zhí)行時(shí)間最小值,計(jì)算它們之間的相對(duì)偏離程度.同時(shí),為了分析基數(shù)預(yù)估對(duì)連接順序選擇的影響,本文使用Q-error 計(jì)算基數(shù)預(yù)估的誤差.

(1) MRR

MRR 值常用于檢索系統(tǒng)中評(píng)估系統(tǒng)的性能,表示正確檢索結(jié)果在全體檢索結(jié)果中的排名.其公式為,其中Q代表查詢的個(gè)數(shù),ri是對(duì)于第i個(gè)查詢,將查詢優(yōu)化器選擇的連接順序和枚舉的連接順序的執(zhí)行時(shí)間從小到大排序,查詢優(yōu)化器選擇的連接順序的執(zhí)行時(shí)間的排名.

若有3 個(gè)查詢,查詢優(yōu)化器選擇的連接順序排名分別為1、3、5,則可得

(2) 偏差

偏差計(jì)算優(yōu)化器所選連接順序的執(zhí)行時(shí)間與最優(yōu) (最短) 執(zhí)行時(shí)間之間的偏差.其公式為,其中D表示偏差,t表示優(yōu)化器所選連接順序的執(zhí)行時(shí)間,tb表示枚舉的連接順序搜索空間中最優(yōu) (最短) 的執(zhí)行時(shí)間.

通過(guò)MRR 值的排名情況可以判斷連接順序的優(yōu)劣,但有時(shí)雖然優(yōu)化器選擇的連接順序排名較低,其與最優(yōu)連接順序的執(zhí)行時(shí)間卻相差不大.因此,MRR 值低并不一定表明連接順序選擇效果差;MRR 值低且執(zhí)行時(shí)間偏差大則說(shuō)明連接順序選擇較差.本文通過(guò)結(jié)合MRR 與偏差,對(duì)連接順序選擇性能進(jìn)行有效評(píng)估.

(3) Q-error

Q-error 計(jì)算優(yōu)化器的預(yù)估基數(shù)與真實(shí)基數(shù)的誤差,用以評(píng)估基數(shù)預(yù)估的準(zhǔn)確性.其公式為,其中e表示優(yōu)化器預(yù)估的基數(shù),a表示真實(shí)的基數(shù),Qe=1 表示預(yù)估準(zhǔn)確.

6 實(shí)驗(yàn)分析

6.1 實(shí)驗(yàn)環(huán)境和測(cè)試場(chǎng)景

本文在OceanBase (v3.1.2)和PostgreSQL (v14)上進(jìn)行實(shí)驗(yàn),其中OceanBase 為單機(jī)版本.數(shù)據(jù)庫(kù)分別部署在兩臺(tái)8 核CPU、32 GB 內(nèi)存的機(jī)器上,本文的評(píng)測(cè)工具部署在一臺(tái)4 核CPU、16 GB 內(nèi)存的機(jī)器上.

為生成盡可能豐富多變的多表連接負(fù)載,測(cè)試場(chǎng)景生成器生成20 張不同的表,規(guī)模最小為千行(約245 kB)、最大為千萬(wàn)行 (約3.6 GB).每張表?yè)碛袛?shù)量不等的屬性列與外鍵約束.實(shí)驗(yàn)負(fù)載包含3～ 9張表的多表連接查詢,連接形狀包括鏈?zhǔn)?、星型、樹型和環(huán)型.

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

本節(jié)評(píng)估OceanBase 和PostgreSQL 在4 種連接形狀 (鏈?zhǔn)?、星型、樹型和環(huán)型) 下選定連接順序的性能.測(cè)試場(chǎng)景生成器為每種連接形狀隨機(jī)生成50 個(gè)查詢.連接順序評(píng)估器為每個(gè)查詢枚舉除優(yōu)化器選擇的連接順序之外的97 個(gè)不同的連接順序,共98 個(gè)連接順序構(gòu)成評(píng)估池,強(qiáng)制待測(cè)試數(shù)據(jù)庫(kù)以評(píng)估池中的規(guī)定連接順序運(yùn)行查詢,從而得到執(zhí)行時(shí)間.具體地,OceanBase 通過(guò)“HINT LEADING”關(guān)鍵字實(shí)現(xiàn)規(guī)定連接順序,PostgreSQL 通過(guò)“SET join_collapse_limit=1” 語(yǔ)句實(shí)現(xiàn)規(guī)定連接順序.OceanBase 和PostgreSQL 的評(píng)估池是相同的,即二者的評(píng)估池包含98 個(gè)相同的連接順序.為了消除執(zhí)行計(jì)劃緩存對(duì)實(shí)驗(yàn)的影響,實(shí)驗(yàn)設(shè)置關(guān)閉數(shù)據(jù)庫(kù)的執(zhí)行計(jì)劃緩存.注意實(shí)驗(yàn)設(shè)置3 張表參與連接時(shí)只產(chǎn)生鏈?zhǔn)胶铜h(huán)型.

表2 展示了OceanBase 和PostgreSQL 執(zhí)行4 種連接形狀的多表連接查詢時(shí)的MRR 結(jié)果.如表2 所示,對(duì)于鏈?zhǔn)?、樹型和環(huán)型的多表連接,PostgreSQL 的MRR 值均高于OceanBase,表明PostgreSQL 的連接順序排名整體優(yōu)于OceanBase,而兩者對(duì)星型的排名無(wú)明顯差異.先由MRR 值觀察到兩數(shù)據(jù)庫(kù)的整體連接順序排名情況,下文結(jié)合偏差分布對(duì)評(píng)估結(jié)果進(jìn)行分析.

表2 OceanBase 和PostgreSQL 執(zhí)行4 種連接形狀的多表連接查詢時(shí)的MRR 結(jié)果Tab.2 MRR results for OceanBase and PostgreSQL when processing multi-table-join queries with four join shapes

圖4—6 為箱型圖,展示了目標(biāo)數(shù)據(jù)的最小值、上四分位數(shù)、中位數(shù)、下四分位數(shù)與最大值,是常用的表示目標(biāo)數(shù)據(jù)分布的一種統(tǒng)計(jì)圖.圖4 展示了OceanBase 執(zhí)行4 種連接形狀的多表連接查詢時(shí)的偏差分布情況,橫坐標(biāo)表示參與連接的表數(shù)量,縱坐標(biāo)表示優(yōu)化器所選擇的連接順序的執(zhí)行時(shí)間與最優(yōu)執(zhí)行時(shí)間的偏差.圖4(a)展示了OceanBase 處理鏈?zhǔn)降亩啾磉B接的結(jié)果分布,當(dāng)參與連接表的數(shù)量為3 時(shí),偏差的中位數(shù)為1.3%,偏差的均值為8.9%,位于數(shù)據(jù)序列25% (下四分位) 至75% (上四分位) 位置的偏差的范圍為0～ 11.5%,3 個(gè)偏差分布中的異常值 (離群點(diǎn)) 分別為37.7%、39.1%和40.7%.IQR (Inter-Quartile Range) 為內(nèi)距,又稱為四分位差,1.5IQR 的上邊緣表示偏離上四分位數(shù)1.5 倍距離內(nèi)的最大極值點(diǎn),如圖4(a)中表數(shù)量為5 時(shí)的1.5IQR 上邊緣為49.7%;1.5IQR 的下邊緣表示偏離下四分位數(shù)1.5 倍距離的最小極值點(diǎn),如圖4(a)中表數(shù)量為5 時(shí)的1.5IQR 下邊緣為0.當(dāng)參與連接表的數(shù)量小于或等于5 時(shí),偏差大部分低于20%.當(dāng)參與連接的表數(shù)量從3 增長(zhǎng)到6 時(shí),偏差整體呈現(xiàn)增長(zhǎng)趨勢(shì),這表明隨著參與連接的表數(shù)量的增大,OceanBase 選擇的連接順序與最優(yōu)連接順序之間的執(zhí)行時(shí)間偏差越來(lái)越大.優(yōu)化器從連接順序搜索空間中選擇出最優(yōu)連接順序的效果降低.圖4(b)展示了OceanBase 在處理星型連接時(shí)的平均偏差均低于10%,除了當(dāng)參與連接的表數(shù)量為9 時(shí),有一偏差的異常值為73%外,其余偏差的異常值均低于20%,該結(jié)果表明OceanBase 對(duì)星型連接的處理效果較好,且優(yōu)化性能穩(wěn)定.然而經(jīng)統(tǒng)計(jì),OceanBase 對(duì)星型連接的平均執(zhí)行時(shí)間為27 s,而PostgreSQL處理相同查詢的平均執(zhí)行時(shí)間只需1.5 s,因此,OceanBase 仍需提升對(duì)大數(shù)據(jù)量負(fù)載的優(yōu)化能力.將圖4(c)和圖4(a)對(duì)比可知,OceanBase 處理樹型連接的偏差均值全都高于鏈?zhǔn)?尤其當(dāng)表數(shù)量為8 和9 時(shí),樹型的偏差明顯比鏈?zhǔn)降钠畲?這說(shuō)明隨著連接形狀復(fù)雜度的增大,優(yōu)化器的連接順序優(yōu)化效果降低.圖4(d)的結(jié)果展示了OceanBase 處理環(huán)型連接的偏差分布變化趨勢(shì)與處理鏈?zhǔn)竭B接的偏差分布變化趨勢(shì)相似,不同的是其處理鏈?zhǔn)竭B接時(shí),圖4(a)中異常值的偏差都低于80%,而處理環(huán)型時(shí)存在偏差高于100%的異常值,這說(shuō)明存在多表連接負(fù)載的實(shí)際執(zhí)行時(shí)間比最優(yōu)執(zhí)行時(shí)間長(zhǎng)2 倍以上.觀察圖4(d)上偏差的最大異常值,OceanBase 選擇的連接順序執(zhí)行時(shí)間為5 484 ms,最優(yōu)執(zhí)行時(shí)間為2 442 ms,兩者相差約3 s,這在實(shí)際應(yīng)用中難以接受.OceanBase 在處理鏈?zhǔn)脚c環(huán)型連接時(shí),在偏差的異常值上的差異表明存在環(huán)路復(fù)雜連接會(huì)對(duì)優(yōu)化器帶來(lái)挑戰(zhàn).

圖4 OceanBase 執(zhí)行4 種連接形狀的多表連接查詢時(shí)的偏差分布情況Fig.4 Distribution of deviation on OceanBase when processing multi-table-join queries with four join shapes

為了進(jìn)一步分析優(yōu)化器何時(shí)錯(cuò)誤選擇的連接順序,本節(jié)通過(guò)查看異常值查詢的執(zhí)行計(jì)劃,發(fā)現(xiàn)此類查詢的算子預(yù)估基數(shù)與真實(shí)基數(shù)相差較大.異常值查詢的單表過(guò)濾算子的基數(shù)預(yù)估Qe的平均值為2.9,連接算子的基數(shù)預(yù)估Qe的平均值為51.6.OceanBase 通過(guò)最值統(tǒng)計(jì)、distinct 值統(tǒng)計(jì)等統(tǒng)計(jì)信息進(jìn)行基數(shù)預(yù)估,3.2 版本以上增加直方圖統(tǒng)計(jì).在聯(lián)合謂詞和連接謂詞的基數(shù)預(yù)估時(shí),OceanBase 假設(shè)數(shù)據(jù)均勻分布和謂詞相互獨(dú)立,這些假設(shè)會(huì)導(dǎo)致基數(shù)預(yù)估存在誤差.隨著謂詞之間的相互交叉增多以及連接層次的深入,基數(shù)預(yù)估的誤差會(huì)越來(lái)越大.錯(cuò)誤的基數(shù)估計(jì)使得優(yōu)化器代價(jià)模型在計(jì)算算子代價(jià)時(shí)會(huì)產(chǎn)生較大誤差,最終令優(yōu)化器選擇了性能較差的連接順序.由此可見,連接順序選擇效果受到錯(cuò)誤預(yù)估基數(shù)的影響較大.

圖4(a)中當(dāng)表數(shù)量增加到7 時(shí),偏差整體呈現(xiàn)下降趨勢(shì).這是因?yàn)楸緦?shí)驗(yàn)設(shè)置置信水平為95%、相對(duì)誤差為10%的枚舉空間大小為97 個(gè),該枚舉空間與龐大的多表連接搜索空間對(duì)比相對(duì)較小.連接順序評(píng)估器很可能沒(méi)有隨機(jī)選到最優(yōu)的連接順序.圖5 以O(shè)ceanBase 為例展示了枚舉空間大小對(duì)評(píng)估結(jié)果的影響.當(dāng)式 (1) 中置信水平為95%、相對(duì)誤差為10%時(shí),枚舉空間大小為385 個(gè).圖5 對(duì)比了枚舉空間為97 個(gè)和385 個(gè)時(shí),OceanBase 執(zhí)行鏈?zhǔn)?、星型、樹型和環(huán)型負(fù)載時(shí)選擇的連接順序執(zhí)行時(shí)間與最優(yōu)執(zhí)行時(shí)間的偏差結(jié)果,實(shí)驗(yàn)設(shè)置參與連接的表數(shù)量為5.圖5 的橫坐標(biāo)分別為4 種類型的枚舉空間大小,縱坐標(biāo)為優(yōu)化器選擇的連接順序的執(zhí)行時(shí)間與最優(yōu)執(zhí)行時(shí)間的偏差.從圖5 中可以看出,當(dāng)枚舉空間增大時(shí),4 種形狀的偏差整體呈現(xiàn)增長(zhǎng)趨勢(shì),枚舉空間為385 個(gè)的中位線和均值比枚舉空間為97 個(gè)的中位線與均值分別平均增長(zhǎng)了26.7%和27.1%.結(jié)果表明,圖4(a)的下降趨勢(shì)與枚舉空間的大小有關(guān).盡管相對(duì)較小的枚舉空間會(huì)影響最終的評(píng)估結(jié)果,但本文的工具依舊能夠發(fā)現(xiàn)優(yōu)化器的不足,如圖4 所示,當(dāng)參與連接的表數(shù)量越多,偏差的異常值的數(shù)目越多,而偏差的異常值意味著優(yōu)化器對(duì)某些多表連接負(fù)載的優(yōu)化效果很差,使其執(zhí)行時(shí)間明顯長(zhǎng)于最優(yōu)時(shí)間 (偏差高于50%).

圖5 枚舉空間大小對(duì)評(píng)估結(jié)果的影響Fig.5 Influence of enumeration space on evaluation results

圖6 展示了PostgreSQL 執(zhí)行4 種連接形狀的多表連接查詢時(shí)的偏差分布情況,橫坐標(biāo)表示參與連接的表數(shù)量,縱坐標(biāo)表示優(yōu)化器選擇的連接順序的執(zhí)行時(shí)間與最優(yōu)執(zhí)行時(shí)間的偏差.圖6(a)—(d)4 種連接形狀平均偏差大部分都低于15%,且4 種連接形狀的執(zhí)行性能沒(méi)有明顯差異,這表明PostgreSQL 優(yōu)化器的連接順序選擇策略較健壯.但圖6(b)展示星型負(fù)載的偏差均值皆高于圖5(b),且存在更多的偏差異常值,這表明PostgreSQL 對(duì)星型連接的連接順序選擇策略有待改進(jìn).計(jì)算圖6 中偏差異常值對(duì)應(yīng)的執(zhí)行計(jì)劃的算子基數(shù)預(yù)估準(zhǔn)確度,得到單表過(guò)濾算子的Qe平均值為4.6,連接算子的Qe平均值為180.1,與OceanBase 不同的是,PostgreSQL 在大多數(shù)情況下低估了算子的基數(shù).PostgreSQL 通過(guò)直方圖、最頻值和distinct 值等統(tǒng)計(jì)信息進(jìn)行基數(shù)估計(jì).PostgreSQL 的基數(shù)預(yù)估基于3 條假設(shè): ①均勻性,所有值 (除了頻率最高的項(xiàng)) 都是均勻分布的;②獨(dú)立性,所有謂詞都是相互獨(dú)立的;③包含原則,連接鍵的值域有重合.基于以上假設(shè),PostgreSQL 對(duì)聯(lián)合謂詞和連接謂詞的基數(shù)預(yù)估同樣會(huì)存在較大誤差.由此可見,PostgreSQL 的連接順序選擇策略也會(huì)受糟糕基數(shù)預(yù)估的影響而產(chǎn)生巨大偏差.由于枚舉空間的影響,多表連接的評(píng)估池中包含更優(yōu)連接順序的概率較低,因此,圖6 中當(dāng)參與連接的表數(shù)量為8 和9 時(shí),鏈?zhǔn)?、樹型、環(huán)型的偏差較低,并且表2 中當(dāng)參與連接的表數(shù)量為8 和9 時(shí),PostgreSQL 運(yùn)行這3 類形狀的負(fù)載時(shí)MRR 值較高.

圖6 PostgreSQL 執(zhí)行4 種連接形狀的多表連接查詢時(shí)的偏差分布情況Fig.6 Distribution of deviation on PostgreSQL when processing multi-table-join queries with four join shapes

以上實(shí)驗(yàn)表明,PostgreSQL 在處理鏈?zhǔn)?、樹型、環(huán)型連接時(shí)的整體連接順序選擇效果優(yōu)于OceanBase,但在星型連接上的優(yōu)化效果不如OceanBase.PostgreSQL 在處理4 種連接形狀時(shí)性能較穩(wěn)定;OceanBase 除對(duì)星型有穩(wěn)定的優(yōu)化效果外,在處理其余類型時(shí),隨著表數(shù)量的增大,優(yōu)化效果降低,并且受連接形狀復(fù)雜度的影響,其在處理樹型和環(huán)型連接時(shí)的優(yōu)化效果劣于鏈?zhǔn)?

7 結(jié)論和未來(lái)工作

針對(duì)優(yōu)化器的連接順序選擇問(wèn)題,本文實(shí)現(xiàn)了一個(gè)通用的評(píng)估工具,有效評(píng)測(cè)優(yōu)化器在連接順序選擇上的優(yōu)化效果.本文使用基于主鍵的確定性數(shù)據(jù)生成方法生成測(cè)試場(chǎng)景數(shù)據(jù);使用適用于不同連接形狀的連接模板生成算法以及基于結(jié)果導(dǎo)向的參數(shù)實(shí)例化方法生成測(cè)試場(chǎng)景負(fù)載;使用連接順序評(píng)估器實(shí)現(xiàn)執(zhí)行計(jì)劃的解析與連接順序的枚舉,實(shí)現(xiàn)對(duì)優(yōu)化器連接順序優(yōu)劣的評(píng)估.經(jīng)過(guò)對(duì)OceanBase 和PostgreSQL 的評(píng)估,發(fā)現(xiàn)了兩者在連接順序選擇效果上的差異與各自的不足之處.

目前,本文評(píng)估工具只支持內(nèi)連接,不支持外連接;支持主鍵-外鍵連接、外鍵-外鍵連接,不支持非主外鍵連接.在未來(lái)工作中,將擴(kuò)展本文工具生成負(fù)載的連接模式,使其覆蓋更全面的負(fù)載類型.