錢文淵，荊一楠，王曉陽，吳振環(huán)

（1.復(fù)旦大學(xué) 計算機科學(xué)技術(shù)學(xué)院，上海 200433；2.司法部 信息中心，北京 100020）

0 概述

查詢優(yōu)化是許多關(guān)系型數(shù)據(jù)庫管理系統(tǒng)以及其他數(shù)據(jù)庫（如圖數(shù)據(jù)庫）領(lǐng)域的一個重要課題［1-3］。查詢是用戶對數(shù)據(jù)庫信息發(fā)起的請求，可以是簡單快速的查詢，也可以是復(fù)雜耗時的查詢。查詢結(jié)果是通過訪問相關(guān)數(shù)據(jù)庫數(shù)據(jù)并對其進行操作從而產(chǎn)生的用戶所需要的信息。由于數(shù)據(jù)庫結(jié)構(gòu)復(fù)雜，對于復(fù)雜的查詢，其執(zhí)行時間可能根據(jù)處理查詢方式的不同而存在較大的差異，從幾分之一秒到幾小時不等。查詢優(yōu)化是一個自動化的過程，其目的是找到通過最少時間來處理給定查詢的方式。不同的查詢處理策略對應(yīng)不同的執(zhí)行時間，為提高查詢效率，進行查詢優(yōu)化具有一定的現(xiàn)實意義［4-6］。

在眾多數(shù)據(jù)庫查詢操作中，連接（JOIN）操作最為費時，其往往涉及多個表之間大量的數(shù)據(jù)讀取，因此，許多查詢優(yōu)化是針對JOIN 展開的［7-8］?；鶖?shù)估計是對數(shù)據(jù)表統(tǒng)計信息進行估計，并將其用于后續(xù)優(yōu)化步驟。對原始數(shù)據(jù)進行基數(shù)估計在大多情況下比較費時，而在樣本數(shù)據(jù)上做基數(shù)估計，對查詢涉及的數(shù)據(jù)本身進行抽樣，使得原本在大規(guī)模數(shù)據(jù)上進行的基數(shù)估計計算變?yōu)樵谳^小但足夠精確的樣本數(shù)據(jù)上進行基數(shù)估計，并通過樣本數(shù)據(jù)上的基數(shù)估計結(jié)果近似估計出原數(shù)據(jù)集上的基數(shù)，從而大幅減少計算時間。

近年來，許多在單表上的抽樣算法相繼被提出［9-11］，同時，學(xué)者們也對一些評估抽樣結(jié)果優(yōu)劣的方法與標(biāo)準(zhǔn)進行了研究［9，12］，這些工作大都聚焦在單表數(shù)據(jù)分布或是與其他表的主外鍵關(guān)系上，針對每一個單表進行最佳抽樣率計算［13-14］。但是，假設(shè)數(shù)據(jù)庫含有多個數(shù)據(jù)表，且對于眾多數(shù)據(jù)表的樣本臨時數(shù)據(jù)表存在存儲限制，即不能對每個數(shù)據(jù)表做過多抽樣，樣本總?cè)萘坑蓄A(yù)算上限，那么如何分配每個數(shù)據(jù)表的抽樣大小就成為一個需要解決的問題。此時，需要找到一個合理的樣本分配方案，使得在此樣本數(shù)據(jù)上做基數(shù)估計的準(zhǔn)確率能夠在一定標(biāo)準(zhǔn)下以及一定誤差范圍內(nèi)盡可能達到最高。

將多個表的抽樣率整體看作一個待分配比例的組合，尋找一個最佳抽樣率的分配就成了一個連續(xù)空間搜索問題，此時擅長連續(xù)空間搜索的貝葉斯優(yōu)化算法可以發(fā)揮優(yōu)勢。本文將貝葉斯優(yōu)化算法應(yīng)用到數(shù)據(jù)庫抽樣中，提出一種面向多表JOIN 查詢優(yōu)化的基數(shù)估計方法。在多表關(guān)系型數(shù)據(jù)庫對樣本臨時表有整體存儲限制時，利用貝葉斯優(yōu)化算法可以快速搜索出不同表之間抽樣樣本大小的分配比例，且抽樣結(jié)果可以達到最優(yōu)，從而實現(xiàn)查詢優(yōu)化的目的。具體地，如果有一組查詢負載涉及多個表之間的JOIN 操作，需要將這組查詢涉及的所有表進行一定比例的抽樣，但抽樣樣本的總體大小受到限制。此時，將每個表的抽樣比例看作一個參數(shù)，則整個數(shù)據(jù)庫中所有表的抽樣比例形成一個參數(shù)組合，所有不超過樣本總大小限制的參數(shù)組合總體構(gòu)成參數(shù)空間。在一個參數(shù)組合對應(yīng)的抽樣方案下，參考文獻［12］進行二層抽樣做基數(shù)估計，得到一個多表整體基數(shù)估計準(zhǔn)確率。利用貝葉斯優(yōu)化［15］快速地在參數(shù)空間搜索對應(yīng)基數(shù)估計準(zhǔn)確率最高的參數(shù)組合，即在抽樣樣本總大小受限的條件下，利用貝葉斯優(yōu)化算法快速確定對應(yīng)基數(shù)估計準(zhǔn)確率最高的多表抽樣比例分配方案。

1 問題定義

1.1 多表JOIN 查詢優(yōu)化

在關(guān)系型數(shù)據(jù)庫中，最耗時的一類查詢往往涉及許多JOIN 操作。不同表之間不同類型（如BroadcastHashJoin、SortMergeJoin）、不同順序的JOIN 往往數(shù)據(jù)量大不相同，操作代價也存在很大差異。因此，合理地執(zhí)行計劃（如合理的JOIN 類型、合理的JOIN 順序）能夠大幅優(yōu)化查詢過程，提高查詢效率。在查詢計劃優(yōu)化器中有一類基于代價的優(yōu)化器，其根據(jù)數(shù)據(jù)庫中數(shù)據(jù)表上數(shù)據(jù)統(tǒng)計和代價模型的代價進行估計，計算不同執(zhí)行計劃對應(yīng)的代價，從而選擇最小代價的計劃來執(zhí)行。因此，數(shù)據(jù)統(tǒng)計結(jié)果的精確度會影響基于代價的優(yōu)化器對執(zhí)行計劃的選擇，從而影響查詢優(yōu)化結(jié)果。多表JOIN 查詢優(yōu)化表示當(dāng)查詢語句中的JOIN 操作涉及3 張以上的數(shù)據(jù)表時，數(shù)據(jù)庫管理系統(tǒng)或數(shù)據(jù)庫優(yōu)化工具根據(jù)數(shù)據(jù)統(tǒng)計信息對JOIN 順序、JOIN 方式進行合理規(guī)劃，從而達到縮減查詢開銷的目標(biāo)。

1.2 基數(shù)估計

本文主要關(guān)注基于代價的優(yōu)化器中的數(shù)據(jù)統(tǒng)計部分，這一部分通常稱作基數(shù)估計，其通過數(shù)據(jù)統(tǒng)計和對數(shù)據(jù)分布、列的相關(guān)性以及連接關(guān)系的一些假設(shè)，來得到一些中間操作的元組條目數(shù)，這些數(shù)字會用于代價模型以決定查詢計劃。理論上講，只要基數(shù)估計準(zhǔn)確、后續(xù)代價模型估計準(zhǔn)確，優(yōu)化器就能在有限時間內(nèi)獲得全局最優(yōu)的查詢執(zhí)行計劃。

在數(shù)據(jù)庫查詢場景下，基數(shù)估計指的是對一個操作符產(chǎn)生的結(jié)果元組條目數(shù)進行估計，這個估計的條目數(shù)會用于代價模型預(yù)測這一個操作符的操作代價開銷，根據(jù)操作代價開銷的不同，對查詢作出不同的物理執(zhí)行計劃，從而達到查詢優(yōu)化的目的。文獻［15］指出，在現(xiàn)有的代價模型下，微小的基數(shù)估計誤差可能會帶來最多30% 的代價預(yù)測誤差。文獻［16］對多表JOIN 復(fù)雜查詢下傳統(tǒng)查詢優(yōu)化器的物理執(zhí)行計劃進行研究，其得到了與文獻［15］類似的結(jié)論。因此，基數(shù)估計結(jié)果的準(zhǔn)確率會嚴重影響查詢優(yōu)化的效果。

在數(shù)據(jù)庫查詢中，最費時的一類查詢往往涉及多個JOIN 操作，因此，本文主要關(guān)注這一類涉及多表JOIN 的查詢優(yōu)化中所需進行的基數(shù)估計。多表JOIN 涉及多張表之間多個列上的基數(shù)估計。在實際的數(shù)據(jù)庫優(yōu)化中，基數(shù)估計包括復(fù)雜的計算，本文將對基數(shù)估計的計算過程進行簡化。基數(shù)估計的關(guān)鍵步驟是計算結(jié)果表中元組的分類計數(shù)，本文將基數(shù)估計過程轉(zhuǎn)化為一個GROUP BY+COUNT 的查詢，以一組特殊設(shè)計的查詢語句來近似替代單表基數(shù)估計進行計算。

定義1（多表基數(shù)估計近似查詢）對于一個給定的涉及JOIN 的查詢（如RJOINP），記這個JOIN 結(jié)果為J，令S為J的一個列組合（如{R.a1}，{R.a1，P.b2}等），S在一種特殊情況下為空，即S=?，則對于如下查詢結(jié)果的估計即為對涉及JOIN 查詢的多表基數(shù)估計：

SELECTS，COUNT（*）

FROMJ

GROUP BYS

對查詢結(jié)果的估計，包括了結(jié)果條目數(shù)的估計以及每一條結(jié)果中對COUNT（*）結(jié)果的估計。需要注意的是，單表基數(shù)估計近似查詢是JOIN 查詢基數(shù)估計近似查詢的一個特例。因此，本文討論涉及JOIN 查詢的多表基數(shù)估計近似查詢。

1.3 基于抽樣的多表JOIN 查詢基數(shù)估計

圖1 所示為基于抽樣并面向多表JOIN 查詢的基數(shù)估計問題定義。上文定義的面向多表JOIN 查詢的基數(shù)估計由于要計算連接后的結(jié)果表元組條目數(shù)，因此當(dāng)原始數(shù)據(jù)表規(guī)模很大時計算量巨大。為解決該問題，常用的一個策略是對原始數(shù)據(jù)表進行一定比例的抽樣，在抽樣數(shù)據(jù)表上進行基數(shù)估計近似查詢，然后根據(jù)抽樣比例再估算原始數(shù)據(jù)表上做多表JOIN 查詢的基數(shù)估計結(jié)果。對于多表JOIN 查詢，各表上不同的抽樣比例會導(dǎo)致JOIN 查詢在抽樣表上做出的基數(shù)估計結(jié)果準(zhǔn)確率不同。因此，對于一組確定的多表JOIN 查詢，本文目標(biāo)是確定一組使得基數(shù)估計準(zhǔn)確率最高的抽樣方案。

圖1 基于抽樣的多表JOIN 查詢基數(shù)估計問題Fig.1 Cardinality estimation problem of multitable JOIN query based on sampling

當(dāng)限定一個數(shù)據(jù)庫中可以額外存儲臨時表的空間，即限制數(shù)據(jù)表可產(chǎn)生的抽樣樣本表的樣本空間時，則必須將有限的樣本空間分配給數(shù)據(jù)庫中的每一張需要抽樣的數(shù)據(jù)表，使得每張數(shù)據(jù)表以一定的抽樣率進行樣本抽樣且樣本總和不超過限制的空間大小。在這個空間有限制的總體樣本上，本文針對給定的查詢負載做基數(shù)估計。本文目標(biāo)是在給定樣本空間限制的條件下，找到一種樣本抽樣在不同數(shù)據(jù)表上的分配方案，使得查詢負載在樣本上做出的基數(shù)估計準(zhǔn)確率最高，即數(shù)據(jù)庫中所有數(shù)據(jù)表的樣本基數(shù)估計結(jié)果準(zhǔn)確率的平均值最大。

2 貝葉斯優(yōu)化與二層抽樣

2.1 貝葉斯優(yōu)化

貝葉斯優(yōu)化的目標(biāo)是一個計算代價昂貴的黑盒函數(shù)f［17-19］，f的具體函數(shù)形式不得而知，但對于一個特定的自變量輸入值x，其對應(yīng)的函數(shù)值f(x)是可以獲取的。雖然f(x)的值可以獲取，但是計算時間會很長，因此，要求得函數(shù)f在定義域X上的最大值或最小值，就不能進行窮盡枚舉［17］。貝葉斯優(yōu)化可以在有限步的嘗試內(nèi)，近似搜索到函數(shù)f的最大值或最小值，從而大幅縮短函數(shù)優(yōu)化時間［20］。

貝葉斯優(yōu)化算法是一個迭代執(zhí)行的過程，x它在每一步迭代時選取一個函數(shù)的合法輸入值x∈X并評估y=f（x）。在算法的初始階段，需要隨機選取幾個輸入值x。在迭代過程中，假設(shè)函數(shù)的一個輸入和輸出的鍵值對序列已經(jīng)在之前的t?1 輪迭代中被選中并評估過，記已評測過的采樣點集合為Dt-1=。貝葉斯優(yōu)化在迭代時使用一個采集函數(shù)（acq）來挑選xt，從而近似估計xbest并交由高斯過程（GP）［18，21］去擬合待優(yōu)化的函數(shù)，那么xt和相應(yīng)的輸出（即模型性能）yt=f(xt)將被加到已評測過的采樣點集合Dt=Dt-1∪{(xt，yt)}中。在實踐中，這個過程不會停止，直到模型性能收斂，或者迭代過程已經(jīng)執(zhí)行了一個預(yù)設(shè)好且數(shù)值較大的最大迭代輪數(shù)T。

2.2 二層抽樣

二層抽樣是文獻［12］在總結(jié)目前用于查詢優(yōu)化中數(shù)據(jù)表JOIN 結(jié)果基數(shù)估計的抽樣方法后，提出的一種用以估計兩表間查詢JOIN 結(jié)果大小的抽樣方法。該文分析了簡單獨立伯努利抽樣（即隨機抽樣）、關(guān)聯(lián)抽樣、端偏抽樣（End-biased sampling）的特點與弊端，在此基礎(chǔ)上提出了二層抽樣方法。

假設(shè)需要JOIN 的2 個表分別為A和B，且在列A.a和B.a上做條件JOIN，v為A.a或B.a上的某一 屬性值，在A.a中的頻數(shù)為av，在B.a中的頻數(shù)為bv。KA和KB為2 個人工設(shè)定的系數(shù)，則令p(v)=，二層抽樣的步驟如下：

1）第一層抽樣。確定JOIN 的屬性列，并利用一個哈希函數(shù)h將屬性列上的屬性值v映射到h(v)∈［0，1］的區(qū)間。若h(v)≤p(v)，則屬性v對應(yīng)的表中元組將在第一層抽樣中被全部抽??；反之，則不抽取。

2）第二層抽樣。對于第一層抽樣中抽取的屬性值，以概率q進行均勻抽樣，同時保證每一類屬性值對應(yīng)的元組中至少有一條被保留。

二層抽樣方法考慮了原始數(shù)據(jù)的分布與連接關(guān)系，避免了需要JOIN 的兩表間數(shù)據(jù)屬性值匹配不均而帶來的基數(shù)估計誤差。二層抽樣方法易于操作，僅需遍歷一遍數(shù)據(jù)即可完成，且可以根據(jù)人工參數(shù)進行調(diào)整，使得在不同抽樣樣本量條件下樣本盡可能地保留連接屬性值。

3 算法實現(xiàn)

本文通過形式化的定義，將多表JOIN 查詢基數(shù)估計問題轉(zhuǎn)化為等價SQL 語句的近似查詢問題?；谶@一轉(zhuǎn)化，本文提出一種面向多表JOIN 查詢基數(shù)估計的最佳數(shù)據(jù)抽樣方案搜索算法。

3.1 數(shù)據(jù)抽樣與基數(shù)估計

假設(shè)有一組（若干條）JOIN 查詢，需要對這若干條JOIN 查詢都做出基數(shù)估計，本文將對若干條JOIN查詢做出的基數(shù)估計問題稱為基數(shù)估計查詢負載（下文簡稱為負載）。在實際應(yīng)用中，數(shù)據(jù)庫中的數(shù)據(jù)表條目數(shù)通常達百萬條之多，若是負載中的查詢覆蓋到數(shù)據(jù)庫中所有的數(shù)據(jù)表，那么在原數(shù)據(jù)上做JOIN 查詢會是一個數(shù)據(jù)量巨大的工作。為解決該問題，可以對原數(shù)據(jù)表進行合理地抽樣，然后將負載在抽樣后的樣本上執(zhí)行查詢，依據(jù)結(jié)果做基數(shù)估計，并用樣本上的基數(shù)估計來近似原數(shù)據(jù)表上的基數(shù)估計。由于執(zhí)行的數(shù)據(jù)表經(jīng)過了抽樣，因此在抽樣樣本上原始負載的近似基數(shù)估計結(jié)果也有誤差。在不同的抽樣率下，基數(shù)估計結(jié)果也必然不同。因此，需要定義對于確定的負載在抽樣樣本上做基數(shù)統(tǒng)計的結(jié)果準(zhǔn)確率，具體方法是將樣本上做出的基數(shù)估計查詢結(jié)果與實際原始數(shù)據(jù)上做出的基數(shù)估計查詢結(jié)果進行比較并得出誤差。

假設(shè)Creal是基數(shù)估計查詢在真實數(shù)據(jù)集（未抽樣前的原始數(shù)據(jù)集）上得出的結(jié)果表，Csample是基數(shù)估計查詢在將語句中的數(shù)據(jù)表替換為樣本數(shù)據(jù)表后在樣本數(shù)據(jù)表上得出的結(jié)果表。有如下結(jié)論：

命題1對于?s∈S，如果(s，r)出現(xiàn)在Csample中，則?r′，使得(s，r′)出現(xiàn)在Creal中，且r′唯一；反之，不一定成立。

證明不妨設(shè)某一基數(shù)估計查詢涉及2 張表R和P的JOIN：

J=RJOINjoinconditionP

那么JOIN 結(jié)果J可以用關(guān)系代數(shù)改寫成如下形式：

對R和P分別進行抽樣，得到樣本數(shù)據(jù)表R′和P'，那么Csample是在抽樣樣本結(jié)果表J′上做查詢的結(jié)果：

因為R′和P′分別是數(shù)據(jù)表R和P的抽樣結(jié)果，所以有：

因為J和J′分別是對R×P和R′×P′在同一條件下的選擇結(jié)果，所以根據(jù)式（1）、式（2）有：

則對于?s在J′中，有如下結(jié)論：

由于基數(shù)估計查詢結(jié)果是GROUP BY 后的COUNT（*）結(jié)果，因此s和r在結(jié)果集中一一對應(yīng)，即：

在式（6）中，r和r′是唯一的。由式（5）、式（6）得到：

?s∈S，如果(s，r)∈Csample?

?唯一的r′，使得(s，r′)∈Creal

上述是2 張表做JOIN 時的情形，同理，可以推廣到任意數(shù)量的表JOIN 時的情形，即當(dāng)一個JOIN操作是由R1，R2，…，Rk的JOIN 而成時，令，…，為抽樣后的樣本數(shù)據(jù)表，那么式（1）、式（2）可改寫為如下形式：

同理，Jmulti和之間的包含關(guān)系也如上可證，結(jié)論成立。

證畢。

由命題1 可知：?(s，r0)，使得(s，r0)∈Creal，而對?r∈N+，均有(s，r)?Csample。由于下文需要定義基數(shù)估計查詢結(jié)果準(zhǔn)確率，因此本文將Csample進行如下擴增以得到：對于使得(s，r0)∈Creal，而對?r∈N+，均有(s，r)?Csample，對這樣的s，將(s，0)加入Csample中，最終獲得，即：

定義2（以樣本進行基數(shù)估計的準(zhǔn)確率）給定一個JOIN 基數(shù)估計查詢，設(shè)原始基數(shù)估計查詢在原數(shù)據(jù)表上的結(jié)果為Creal，將原數(shù)據(jù)表的每張表按抽樣率p抽樣后，在樣本數(shù)據(jù)表上做基數(shù)估計查詢的結(jié)果為Csample，將Csample按式（7）做擴增，得到。記Creal的條目數(shù)為|Creal|，則使用樣本的基數(shù)估計準(zhǔn)確率ρ定義為：

3.2 數(shù)據(jù)抽樣的空間限制

2.1 節(jié)所提抽樣方法都是在單表下討論的，在真實場景中，查詢往往包括JOIN 操作，這就涉及一個查詢語句需要在2 張甚至多張數(shù)據(jù)表上進行查詢計算，因此，需要對涉及的2 張甚至多張表都進行抽樣，而這些表上的抽樣肯定相關(guān)聯(lián)，能夠用以準(zhǔn)確進行基數(shù)估計的樣本結(jié)果不會是相互獨立的。因此，對于某一個特定的查詢問句，需要對其涉及的所有表都進行一次聯(lián)合抽樣，以實現(xiàn)最準(zhǔn)確的基數(shù)估計。

定義3（數(shù)據(jù)表的最佳抽樣率）設(shè)數(shù)據(jù)庫中擁有n張數(shù)據(jù)表，記為R1，R2，…，Ri，…，Rn。設(shè)擁有若干條（m條）查詢，記為Q1，Q2，…，Qj，…，Qm。假設(shè)在處理查詢Qj的過程中需要對表Ri進行抽樣率為pij的隨機抽樣，能夠達到最準(zhǔn)確的基數(shù)估計（即樣本基數(shù)估計結(jié)果準(zhǔn)確率ρ的值最大，注意，這里可能查詢Qj并不涉及表Ri，在這種情況下pij=0），那么針對由m條查詢構(gòu)成的查詢集合，表Ri的最佳抽樣率為：

通過定義3 可以得知，假設(shè)在隨機抽樣策略下要達到最準(zhǔn)確的基數(shù)估計，則整個數(shù)據(jù)庫所有數(shù)據(jù)表的抽樣樣本存儲大小之和為Hbest，如果數(shù)據(jù)庫本身已經(jīng)存儲了大量數(shù)據(jù)，所剩存儲空間不多，已經(jīng)不足以存放Hbest大小的抽樣樣本，就出現(xiàn)了問題。由于整體可產(chǎn)生的抽樣樣本所占存儲空間受到限制，那么針對特定的查詢集合，勢必?zé)o法使得每張表的樣本都進行最準(zhǔn)確的基數(shù)估計，即本文所討論的情況是在H≤Hbudget

定義4（數(shù)據(jù)庫的整體樣本基數(shù)估計結(jié)果準(zhǔn)確率）設(shè)數(shù)據(jù)庫中有n張表R1，R2，…，Rn，每張表的抽樣率為pi，并且在給定的抽樣率條件下，針對給定的查詢負載，其樣本基數(shù)估計結(jié)果準(zhǔn)確率分別為ρ1，ρ2，…，ρn，則數(shù)據(jù)庫的樣本基數(shù)估計準(zhǔn)確率ρdb定義為：

由定義4 可知，當(dāng)給定一組抽樣率p1，p2，…，pn且滿足H=≤Hbudget（Hbudget事先給定）時，可以得到給定查詢負載下整體基數(shù)估計結(jié)果準(zhǔn)確率ρdb，誤差率為1-ρdb。

3.3 貝葉斯優(yōu)化與空間有限數(shù)據(jù)抽樣

由定義3 可知，當(dāng)查詢負載和抽樣樣本給定時，數(shù)據(jù)表的樣本基數(shù)估計結(jié)果準(zhǔn)確率容易計算。因此，如果將一組在限定空間大小之內(nèi)的數(shù)據(jù)表樣本抽樣分配方案作為自變量，將此時對于給定的查詢負載在樣本上的整體基數(shù)估計準(zhǔn)確率作為應(yīng)變量，在這2 個變量間建立映射關(guān)系，那么上述尋找最佳樣本抽樣分配方案的問題，就可轉(zhuǎn)化為函數(shù)最優(yōu)化搜索問題，則可以引入貝葉斯優(yōu)化算法進行解決。本文在給定樣本總空間大小條件下，將數(shù)據(jù)庫中所有數(shù)據(jù)表合法的抽樣樣本組合（即樣本總和不超過給定大小的上限）組成整個自變量搜索空間，空間中每一個自變量對應(yīng)一種合法樣本組合（設(shè)數(shù)據(jù)庫中有n張表），然后通過貝葉斯優(yōu)化算法在搜索空間中搜索，以給定查詢負載下數(shù)據(jù)庫樣本基數(shù)估計結(jié)果準(zhǔn)確率ρdb作為目標(biāo)函數(shù)值，從而優(yōu)化這一映射關(guān)系函數(shù)，最終搜索出最高的數(shù)據(jù)庫樣本基數(shù)估計結(jié)果準(zhǔn)確率，以及使得數(shù)據(jù)庫樣本基數(shù)估計結(jié)果準(zhǔn)確率最高的樣本組合，就可求出每張表對應(yīng)的抽樣率。為計算方便，本文將搜索空間適當(dāng)修改，將合法的樣本組合一一對應(yīng)成合法的抽樣率組合，即貝葉斯優(yōu)化算法需要搜索的搜索空間變?yōu)橛伤泻戏ǖ某闃勇式M合X=(p1，p2，…，pn)（設(shè)數(shù)據(jù)庫中有n張表）構(gòu)成的空間。具體算法描述如算法1所示。

在上述貝葉斯優(yōu)化搜索的每一步，當(dāng)假設(shè)了每張數(shù)據(jù)表的抽樣率之后，采用二層抽樣方法來抽取樣本以用于最終的基數(shù)估計。在每一輪迭代中，在貝葉斯優(yōu)化算法推薦的抽樣比例下做二層抽樣以估算基數(shù)估計結(jié)果，并按式（8）計算基數(shù)估計準(zhǔn)確率，將其與歷史最優(yōu)記錄進行比較，若該抽樣比例方案下基數(shù)估計準(zhǔn)確率有所提高，則更新歷史最優(yōu)記錄。整體算法流程如圖2 所示。

圖2 面向多表JOIN 查詢優(yōu)化的基數(shù)估計方法流程Fig.2 Procedure of cardinality estimation method for multitable JOIN query optimization

3.4 時間復(fù)雜度分析

原始貝葉斯優(yōu)化算法在一次迭代中用高斯過程搜索黑盒函數(shù)最值點的時間復(fù)雜度為Ο(n2)，其中，n為觀測點數(shù)目［22-23］。而在一次迭代中，本文優(yōu)化算法除了利用高斯過程計算一組推薦抽樣率方案之外，還需要根據(jù)計算出的抽樣率方案對查詢負載中的m條多表JOIN 查詢計算基數(shù)估計準(zhǔn)確率，因此，一次迭代的總時間開銷為Ο(n2+m)。根據(jù)貝葉斯優(yōu)化算法的特點，算法在進行第n輪迭代時的觀測點數(shù)目為n，因此，本文算法前n輪的總時間復(fù)雜度為Ο(n3+nm)。

4 實驗評估

4.1 實驗設(shè)置

在本次實驗中，采用TPC-H生成了1 GB的數(shù)據(jù)集，并選取22 個官方查詢模板查詢語句中的12 個查詢模板語句（這12 個模板均含有多表JOIN 查詢，符合本文討論的范疇），構(gòu)建查詢負載并進行優(yōu)化。其中，問句均涉及2 張及2 張以上的表的JOIN，并且查詢返回時以某一列或某幾列做分組（GROUP BY）后的計數(shù)（COUNT）作為結(jié)果呈現(xiàn)。所有12 個查詢問句共涉及數(shù)據(jù)庫中的8 張數(shù)據(jù)表，以這種類型的查詢問句來模擬數(shù)據(jù)庫的查詢優(yōu)化器在分析用戶真實查詢問句后得出問句涉及具體哪些數(shù)據(jù)表（對應(yīng)實驗中查詢問句的JOIN 部分），以及獲取到下一步執(zhí)行計劃優(yōu)化所需基數(shù)估計的列（對應(yīng)實驗中查詢問句的GROUP BY 部分）。因此，實驗中的查詢負載事實上是模擬了真實場景中查詢優(yōu)化器分析需要做何種基數(shù)估計的這一步驟。

4.2 誤差率對比實驗

本文設(shè)定允許產(chǎn)生的樣本總大小為原始數(shù)據(jù)大小的0.01%～5%不等，利用貝葉斯優(yōu)化算法搜索20 步，記錄搜索到的8 張表上的最佳抽樣率組合以及對應(yīng)的數(shù)據(jù)庫抽樣基數(shù)估計誤差率的最小值。對于選定的抽樣率，以隨機抽樣或二層抽樣的方法重復(fù)10 次實驗并取最佳結(jié)果，同樣地，利用隨機搜索算法搜索20 步，記錄8 張表上的最佳抽樣率組合以及對應(yīng)的數(shù)據(jù)庫抽樣基數(shù)估計誤差率的最小值。實驗結(jié)果如圖3 所示。

圖3 各算法在不同抽樣比例下的基數(shù)估計誤差率Fig.3 Cardinality estimation error rate of each algorithm under different sampling proportion

分析圖3 可知，對于各表在抽樣大小受限條件下的最優(yōu)抽樣率分配方案，采用二層抽樣方法總是優(yōu)于隨機抽樣方法，而在相同的抽樣樣本比例限定下（如0.1%），采用貝葉斯優(yōu)化算法確定的最優(yōu)樣本分配方案在有限步驟內(nèi)（或有限時間內(nèi)）總是要比隨機搜索確定的最優(yōu)樣本分配方案對應(yīng)基數(shù)估計的誤差率要小。在抽樣率比例上限為0.01%和5%條件下，采用貝葉斯優(yōu)化算法得到的基數(shù)估計誤差率比隨機搜索算法得到的基數(shù)估計誤差率分別降低60.2%和54.8%。

4.3 搜索效率對比實驗

本文設(shè)計實驗來證明貝葉斯優(yōu)化算法在解決面向多表JOIN 查詢優(yōu)化基數(shù)估計問題上的高效性。通過TPC-H 產(chǎn)生1 GB 原始數(shù)據(jù)，并設(shè)置允許產(chǎn)生的各表樣本總大小分別為原始數(shù)據(jù)的0.01%、0.05%、0.1%、0.5%和1%，分別使用隨機搜索和貝葉斯優(yōu)化算法來確定各表的最優(yōu)抽樣率比例分配方案，抽樣方法均采用二層抽樣，記錄歷史最低基數(shù)估計誤差率，直到歷史最低基數(shù)估計誤差率在10 步迭代內(nèi)降低不超過1%，則可認為搜索到的最優(yōu)抽樣率比例分配收斂，記錄隨機搜索和貝葉斯優(yōu)化算法的收斂時間，每一種抽樣比例下進行20 次實驗取平均值，結(jié)果如圖4 所示。

圖4 不同抽樣比例下搜索到最優(yōu)抽樣分配方案的收斂時間Fig.4 Convergence time of searching the optimal sampling allocation scheme under different sampling proportion

分析圖4 可知，在不同的抽樣數(shù)據(jù)規(guī)模下，利用貝葉斯優(yōu)化算法搜索最優(yōu)抽樣分配方案時，收斂時間少于隨機搜索算法。因此，貝葉斯優(yōu)化算法在解決面向多表JOIN 查詢優(yōu)化的基數(shù)估計問題時具有高效性。

5 結(jié)束語

本文提出一種面向多表JOIN 查詢優(yōu)化的基數(shù)估計方法。對于一組給定的查詢負載，需要在查詢優(yōu)化前對其進行基數(shù)估計，而對于龐大的原始數(shù)據(jù)，又需要在基數(shù)估計前進行樣本總大小有限的多表聯(lián)合抽樣。本文利用貝葉斯優(yōu)化算法快速搜索多張數(shù)據(jù)表之間可能的抽樣樣本比例分配組合，采用二層抽樣方法在有限時間內(nèi)確定多表聯(lián)合抽樣率分配方案，使得給定查詢負載平均基數(shù)估計結(jié)果誤差率最小，從而實現(xiàn)精準(zhǔn)且快速的基數(shù)估計。實驗結(jié)果表明，該方法能有效提升涉及多表JOIN 復(fù)雜查詢的基數(shù)估計計算效率，且誤差率相比隨機搜索算法大幅降低，實現(xiàn)了查詢優(yōu)化的效果。下一步考慮將元學(xué)習(xí)、強化學(xué)習(xí)等算法應(yīng)用于查詢優(yōu)化與基數(shù)估計任務(wù)中，結(jié)合傳統(tǒng)基于數(shù)據(jù)統(tǒng)計的計算方法與基于強化學(xué)習(xí)的模型，以提高數(shù)據(jù)查詢效率并提升數(shù)據(jù)庫優(yōu)化的整體水平。