面向多表連接查詢優(yōu)化的基數(shù)估計(jì)方法

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

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

0 概述

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

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

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

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

1 問題定義

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

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

1.2 基數(shù)估計(jì)

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

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

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

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

SELECTS，COUNT（*）

FROMJ

GROUP BYS

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

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

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

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

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

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

2.1 貝葉斯優(yōu)化

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

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

2.2 二層抽樣

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

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

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

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

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

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

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

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

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

假設(shè)Creal是基數(shù)估計(jì)查詢?cè)谡鎸?shí)數(shù)據(jù)集（未抽樣前的原始數(shù)據(jù)集）上得出的結(jié)果表，Csample是基數(shù)估計(jì)查詢?cè)趯⒄Z句中的數(shù)據(jù)表替換為樣本數(shù)據(jù)表后在樣本數(shù)據(jù)表上得出的結(jié)果表。有如下結(jié)論：

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

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

J=RJOINjoinconditionP

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

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

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

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

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

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

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

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

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

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

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

證畢。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)設(shè)置

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

4.2 誤差率對(duì)比實(shí)驗(yàn)

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

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

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

4.3 搜索效率對(duì)比實(shí)驗(yàn)

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

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

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

5 結(jié)束語

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