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

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

0 引 言

分析型數(shù)據(jù)庫管理系統(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ù)載中,查詢往往會涉及多個(gè)關(guān)系,即多表連接.數(shù)據(jù)庫查詢優(yōu)化器在處理多表連接查詢時(shí),會面對一個(gè)復(fù)雜的連接順序選擇 (Join Order Selection,JOS) 問題,也稱為連接順序優(yōu)化問題,即從連接順序搜索空間中選出性能最優(yōu)的連接順序.不同的連接順序在語義上等價(jià)(即能獲得相同的結(jié)果集),但是查詢效率有著顯著差異,在執(zhí)行時(shí)間上可能呈現(xiàn)幾個(gè)數(shù)量級的差異.因此,連接順序的選擇是一個(gè)十分關(guān)鍵的查詢優(yōu)化問題[1].由于連接操作的交換性和結(jié)合性,隨著連接表數(shù)量的增加,搜索空間的大小會呈指數(shù)級增長,如考慮左深樹、右深樹和濃密樹時(shí),N個(gè)表連接的搜索空間高達(dá),無法在多項(xiàng)式時(shí)間內(nèi)解決.Ibaraki 等[2]證明了連接順序選擇是一個(gè)NP-hard 問題.

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

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

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

1 相關(guān)工作

常見的評測基準(zhǔn),比如,Star Schema Benchmark[15]、TPC-H[16]、TPC-DS[17]主要用于數(shù)據(jù)庫查詢執(zhí)行的整體性能評測,其數(shù)據(jù)分布為均勻分布,而真實(shí)應(yīng)用場景中的數(shù)據(jù)往往為非均勻分布,有較大的數(shù)據(jù)傾斜度,并且其負(fù)載僅涉及鏈?zhǔn)健湫鸵约靶切偷暮唵芜B接形狀.因此,這些評測基準(zhǔn)無法對查詢優(yōu)化器的連接順序選擇進(jìn)行針對性評測.

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

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

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

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

2 連接形狀

連接圖是以表為結(jié)點(diǎn),連接關(guān)系為邊的無向圖,展示查詢中各表之間的連接關(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)是簡單的鏈?zhǔn)竭B接形狀,查詢中的表按順序連接,在實(shí)際應(yīng)用中很常見,同時(shí)也較容易優(yōu)化.圖2(b)星型連接常見于數(shù)據(jù)倉庫應(yīng)用中,此類查詢中的表分為一張事實(shí)表和多張維度表.事實(shí)表是數(shù)據(jù)倉庫中的中央表,存儲有事實(shí)記錄的表,如交易記錄、銷售明細(xì)、系統(tǒng)日志等;維度表用于保存維度的屬性值,即事實(shí)表中屬性的相關(guān)詳細(xì)信息,如日期維度表、產(chǎn)品維度表、用戶維度表等.星型可以看成將多張維度表連接到中央事實(shí)表.圖2(c)樹型可以看成是鏈?zhǔn)胶托切偷幕旌项愋?連接形式更加隨機(jī),會產(chǎn)生更大的連接順序搜索空間.圖2(d)環(huán)型中的所有表通過依賴關(guān)系連接形成一條環(huán)路,處理環(huán)路的復(fù)雜度高,給某些連接順序選擇策略帶來極大挑戰(zhàn).圖2(e)含環(huán)型的連接圖中至少存在一條環(huán)路,即可能存在多條環(huán)路,增大搜索空間以及延長優(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ù)雜,對其優(yōu)化的時(shí)間復(fù)雜度和空間復(fù)雜度就越高.同時(shí),由于不同連接形狀的特性,適合一種連接形狀的連接順序優(yōu)化算法可能不適合另一種連接形狀,健壯的優(yōu)化器需針對不同的連接形狀采用不同的優(yōu)化策略.

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

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

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

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

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

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

4 測試場景生成器

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

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

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

4.2 負(fù)載生成

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

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

4.2.1 連接圖生成

連接圖生成器生成連接圖G=(V,E) ,其中V是參與連接的表的集合,E是邊的集合,E中的每一條邊是連接兩張表的連接謂詞,表的連接關(guān)系由主外鍵參照關(guān)系決定.G的初始狀態(tài)為空集 (G=?),連接圖生成器依次對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水平對比 治療后觀察組HR水平明顯高于對照組，而MAP、SVV水平均明顯低于對照組，差異有統(tǒng)計(jì)學(xué)意義(均P<0.05)。見表2。

(1)eE;

(2)u∈V且v∈V.

適用于不同連接形狀的連接模板生成算法的基本思路是: 分別通過加點(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接生成過程中 (從加入第二張表起),需要同步更新度為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í),每次對連接圖進(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 評測基準(zhǔn)如TPC-H、TPC-DS、SSB、JOB 等,它們單個(gè)查詢的最大連接數(shù)為18,因此,N通常不是很大.

4.2.2 過濾謂詞生成

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

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

5 連接順序評估器

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

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是相對誤差.

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

5.2 評估指標(biāo)

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

(1) MRR

MRR 值常用于檢索系統(tǒng)中評估系統(tǒng)的性能,表示正確檢索結(jié)果在全體檢索結(jié)果中的排名.其公式為,其中Q代表查詢的個(gè)數(shù),ri是對于第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í)間.

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

(3) Q-error

Q-error 計(jì)算優(yōu)化器的預(yù)估基數(shù)與真實(shí)基數(shù)的誤差,用以評估基數(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)境和測試場景

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

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

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

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

表2 展示了OceanBase 和PostgreSQL 執(zhí)行4 種連接形狀的多表連接查詢時(shí)的MRR 結(jié)果.如表2 所示,對于鏈?zhǔn)?、樹型和環(huán)型的多表連接,PostgreSQL 的MRR 值均高于OceanBase,表明PostgreSQL 的連接順序排名整體優(yōu)于OceanBase,而兩者對星型的排名無明顯差異.先由MRR 值觀察到兩數(shù)據(jù)庫的整體連接順序排名情況,下文結(jié)合偏差分布對評估結(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 增長到6 時(shí),偏差整體呈現(xiàn)增長趨勢,這表明隨著參與連接的表數(shù)量的增大,OceanBase 選擇的連接順序與最優(yōu)連接順序之間的執(zhí)行時(shí)間偏差越來越大.優(yōu)化器從連接順序搜索空間中選擇出最優(yōu)連接順序的效果降低.圖4(b)展示了OceanBase 在處理星型連接時(shí)的平均偏差均低于10%,除了當(dāng)參與連接的表數(shù)量為9 時(shí),有一偏差的異常值為73%外,其余偏差的異常值均低于20%,該結(jié)果表明OceanBase 對星型連接的處理效果較好,且優(yōu)化性能穩(wěn)定.然而經(jīng)統(tǒng)計(jì),OceanBase 對星型連接的平均執(zhí)行時(shí)間為27 s,而PostgreSQL處理相同查詢的平均執(zhí)行時(shí)間只需1.5 s,因此,OceanBase 仍需提升對大數(shù)據(jù)量負(fù)載的優(yōu)化能力.將圖4(c)和圖4(a)對比可知,OceanBase 處理樹型連接的偏差均值全都高于鏈?zhǔn)?尤其當(dāng)表數(shù)量為8 和9 時(shí),樹型的偏差明顯比鏈?zhǔn)降钠畲?這說明隨著連接形狀復(fù)雜度的增大,優(yōu)化器的連接順序優(yōu)化效果降低.圖4(d)的結(jié)果展示了OceanBase 處理環(huán)型連接的偏差分布變化趨勢與處理鏈?zhǔn)竭B接的偏差分布變化趨勢相似,不同的是其處理鏈?zhǔn)竭B接時(shí),圖4(a)中異常值的偏差都低于80%,而處理環(huán)型時(shí)存在偏差高于100%的異常值,這說明存在多表連接負(fù)載的實(shí)際執(zhí)行時(shí)間比最優(yōu)執(zhí)行時(shí)間長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ù)雜連接會對優(yōu)化器帶來挑戰(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é)通過查看異常值查詢的執(zhí)行計(jì)劃,發(fā)現(xiàn)此類查詢的算子預(yù)估基數(shù)與真實(shí)基數(shù)相差較大.異常值查詢的單表過濾算子的基數(shù)預(yù)估Qe的平均值為2.9,連接算子的基數(shù)預(yù)估Qe的平均值為51.6.OceanBase 通過最值統(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è)會導(dǎo)致基數(shù)預(yù)估存在誤差.隨著謂詞之間的相互交叉增多以及連接層次的深入,基數(shù)預(yù)估的誤差會越來越大.錯(cuò)誤的基數(shù)估計(jì)使得優(yōu)化器代價(jià)模型在計(jì)算算子代價(jià)時(shí)會產(chǎn)生較大誤差,最終令優(yōu)化器選擇了性能較差的連接順序.由此可見,連接順序選擇效果受到錯(cuò)誤預(yù)估基數(shù)的影響較大.

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

圖5 枚舉空間大小對評估結(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í)行性能沒有明顯差異,這表明PostgreSQL 優(yōu)化器的連接順序選擇策略較健壯.但圖6(b)展示星型負(fù)載的偏差均值皆高于圖5(b),且存在更多的偏差異常值,這表明PostgreSQL 對星型連接的連接順序選擇策略有待改進(jìn).計(jì)算圖6 中偏差異常值對應(yīng)的執(zhí)行計(jì)劃的算子基數(shù)預(yù)估準(zhǔn)確度,得到單表過濾算子的Qe平均值為4.6,連接算子的Qe平均值為180.1,與OceanBase 不同的是,PostgreSQL 在大多數(shù)情況下低估了算子的基數(shù).PostgreSQL 通過直方圖、最頻值和distinct 值等統(tǒng)計(jì)信息進(jìn)行基數(shù)估計(jì).PostgreSQL 的基數(shù)預(yù)估基于3 條假設(shè): ①均勻性,所有值 (除了頻率最高的項(xiàng)) 都是均勻分布的;②獨(dú)立性,所有謂詞都是相互獨(dú)立的;③包含原則,連接鍵的值域有重合.基于以上假設(shè),PostgreSQL 對聯(lián)合謂詞和連接謂詞的基數(shù)預(yù)估同樣會存在較大誤差.由此可見,PostgreSQL 的連接順序選擇策略也會受糟糕基數(shù)預(yù)估的影響而產(chǎn)生巨大偏差.由于枚舉空間的影響,多表連接的評估池中包含更優(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 除對星型有穩(wěn)定的優(yōu)化效果外,在處理其余類型時(shí),隨著表數(shù)量的增大,優(yōu)化效果降低,并且受連接形狀復(fù)雜度的影響,其在處理樹型和環(huán)型連接時(shí)的優(yōu)化效果劣于鏈?zhǔn)?

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

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

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