高錦濤, 李戰(zhàn)懷, 劉文潔

(西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安 710072)

基數(shù)估計(jì)是查詢優(yōu)化的重要組成部分，其效率以及準(zhǔn)確性關(guān)系到優(yōu)化器能否快速、準(zhǔn)確生成最優(yōu)執(zhí)行計(jì)劃。文獻(xiàn)[1]中指出基數(shù)估計(jì)的錯(cuò)誤率隨著連接表的數(shù)量呈指數(shù)型增長(zhǎng)，原因是中間結(jié)果的基數(shù)估計(jì)需要通過(guò)基本表的基數(shù)估計(jì)進(jìn)行再推導(dǎo)得到。如果有多個(gè)連接，則存在多個(gè)迭代的中間結(jié)果，因此錯(cuò)誤率被逐漸擴(kuò)大。如果基本表的基數(shù)估計(jì)錯(cuò)誤率較大，則嚴(yán)重影響查詢優(yōu)化的效果。

隨著大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)庫(kù)處理的數(shù)據(jù)量激增，在這種數(shù)據(jù)環(huán)境下，傳統(tǒng)基于原表離線收集模式會(huì)大大降低數(shù)據(jù)的收集效率并增大基數(shù)更新延遲。而基于原表樣本的收集模式雖然能夠緩解大數(shù)據(jù)收集效率問(wèn)題，但為保證準(zhǔn)確度，需要較大的樣本空間。一些策略[2-3]為避免從基本表推導(dǎo)得到基數(shù)，通過(guò)先前執(zhí)行的一些查詢的反饋信息或者通過(guò)執(zhí)行當(dāng)前查詢的一些重要的子查詢得到的結(jié)果作為基數(shù)值。這些策略雖然能夠在查詢運(yùn)行時(shí)獲得所需參數(shù)，但需要額外的查詢執(zhí)行代價(jià)，對(duì)于查詢數(shù)據(jù)量很大的情況，代價(jià)較高。

本文提出一種高效準(zhǔn)確的基于查詢結(jié)果的基數(shù)估計(jì)策略，特點(diǎn)是維護(hù)一張基數(shù)表，基數(shù)表中的項(xiàng)(簡(jiǎn)稱基數(shù)項(xiàng))的內(nèi)容為基本表或者中間結(jié)果在特定謂詞下運(yùn)行時(shí)得到的實(shí)際的執(zhí)行結(jié)果的基數(shù)，保證基數(shù)的準(zhǔn)確度。添加基數(shù)項(xiàng)熱度、過(guò)期信息等內(nèi)容，增加基數(shù)項(xiàng)的可操作性。通過(guò)動(dòng)態(tài)感知緩存資源，將基數(shù)項(xiàng)合理分配到緩存中，降低統(tǒng)計(jì)信息延遲。

1 相關(guān)工作

關(guān)于基數(shù)估計(jì)的研究主要集中在不同架構(gòu)下的基數(shù)估計(jì)策略以及不同查詢階段的基數(shù)估計(jì)策略。不同架構(gòu)指集中式和分布式架構(gòu)，不同查詢階段指查詢編譯期和執(zhí)行期?；鶖?shù)估計(jì)分為統(tǒng)計(jì)信息收集、維護(hù)和使用3個(gè)階段，下面就這3個(gè)階段在上述2個(gè)研究方面上的不同實(shí)施策略進(jìn)行闡述。

1.1 不同架構(gòu)下基數(shù)估計(jì)策略

1.1.1 集中式架構(gòu)

·收集階段為處理大數(shù)據(jù)，集中式架構(gòu)收集策略一般采用樣本收集[4-7]。如postgresql[4]，可根據(jù)樣本率調(diào)整收集數(shù)據(jù)量。Oracle[5]提供多種收集接口，如DBMS_STATS，允許用戶規(guī)定統(tǒng)計(jì)收集的并行度、樣本方法以及收集粒度。Teradata[6]規(guī)定初始樣本率為2%，如果檢測(cè)到收集的結(jié)果發(fā)生傾斜，則自動(dòng)將樣本率調(diào)整到50%。文獻(xiàn)[8]給出了保證統(tǒng)計(jì)信息準(zhǔn)確度的收集量。

·維護(hù)階段對(duì)于收集完畢的統(tǒng)計(jì)信息，如果原始數(shù)據(jù)改變較大，則需要對(duì)統(tǒng)計(jì)信息進(jìn)行維護(hù)，保證其準(zhǔn)確性。通常做法為設(shè)置一個(gè)單獨(dú)線程，如postgresql的collector線程，用來(lái)捕捉更新量，如果判斷更新量超過(guò)某個(gè)閾值，則觸發(fā)維護(hù)機(jī)制。

·使用階段優(yōu)化器基于統(tǒng)計(jì)信息評(píng)估計(jì)劃優(yōu)劣。優(yōu)化器從存儲(chǔ)統(tǒng)計(jì)信息的位置獲取統(tǒng)計(jì)信息，如postgresql，Oracle等，將統(tǒng)計(jì)信息存儲(chǔ)于系統(tǒng)表，使用時(shí)，直接從系統(tǒng)表獲取統(tǒng)計(jì)信息。

1.1.2 分布式架構(gòu)

·收集階段分布式架構(gòu)下統(tǒng)計(jì)信息收集手段包括：依賴中心控制節(jié)點(diǎn)收集和分布式節(jié)點(diǎn)收集。Orca[9]中統(tǒng)計(jì)任務(wù)發(fā)生在主節(jié)點(diǎn)的memo結(jié)構(gòu)中，收集單位是memo[10]中的組，數(shù)據(jù)來(lái)自底層分布式架構(gòu)。微軟的PDW QO[11]，對(duì)每一個(gè)分布式節(jié)點(diǎn)執(zhí)行SQL語(yǔ)句進(jìn)行本地統(tǒng)計(jì)信息收集，并將收集后的統(tǒng)計(jì)信息存儲(chǔ)在本地。文獻(xiàn)[12]提出的解中心化統(tǒng)計(jì)方式，將數(shù)據(jù)路由到工作節(jié)點(diǎn)，由工作節(jié)點(diǎn)實(shí)時(shí)收集統(tǒng)計(jì)信息。文獻(xiàn)[13]中統(tǒng)計(jì)信息的收集源來(lái)自內(nèi)存，雖然收集速度快，但收集的量有限。

·維護(hù)階段分布式架構(gòu)下，統(tǒng)計(jì)信息維護(hù)手段與集中式類似，由更改數(shù)據(jù)量是否超過(guò)閾值觸發(fā)收集任務(wù)。

·使用階段分布式架構(gòu)下，統(tǒng)計(jì)信息的使用方式主要通過(guò)局部統(tǒng)計(jì)信息推導(dǎo)出全局統(tǒng)計(jì)信息[9-11]。PDW QO[11]將存儲(chǔ)在shellbase中的局部統(tǒng)計(jì)信息合并成全局統(tǒng)計(jì)信息。類似的，Orca[9]在生成父親組的統(tǒng)計(jì)信息時(shí)，會(huì)給孩子組發(fā)送請(qǐng)求，由孩子組將各自的統(tǒng)計(jì)信息傳遞給父親組，由父親組合并成全局統(tǒng)計(jì)信息。文獻(xiàn)[14-15]則利用不同的分布式節(jié)點(diǎn)交換統(tǒng)計(jì)信息。

1.2 不同查詢階段基數(shù)估計(jì)策略

基數(shù)為推導(dǎo)信息，來(lái)源于基本統(tǒng)計(jì)信息[16]。統(tǒng)計(jì)信息一般以直方圖進(jìn)行表示，對(duì)于直方圖的詳細(xì)闡述可以參考文獻(xiàn)[17]。統(tǒng)計(jì)信息服務(wù)于優(yōu)化器，目前常見(jiàn)的優(yōu)化器工作階段分為查詢的編譯期以及執(zhí)行期，由于這2個(gè)階段主要涉及統(tǒng)計(jì)信息的使用，因此這里只討論統(tǒng)計(jì)信息的使用階段。

1.2.1 編譯期

·使用階段查詢編譯器涉及到的統(tǒng)計(jì)信息為靜態(tài)統(tǒng)計(jì)信息，獲得手段為on-line模式[4-7](統(tǒng)計(jì)信息收集和使用在同一時(shí)刻)或者off-line模式[9-11](統(tǒng)計(jì)信息收集和使用分離)。這2種模式下獲得的統(tǒng)計(jì)信息是靜態(tài)的，不會(huì)根據(jù)執(zhí)行時(shí)值的變化動(dòng)態(tài)調(diào)整統(tǒng)計(jì)信息，維持準(zhǔn)確性。

1.2.2 執(zhí)行期

·使用階段由于基數(shù)估計(jì)涉及的參數(shù)在執(zhí)行期可能發(fā)生較大改變，因此基于靜態(tài)基數(shù)估計(jì)的優(yōu)化器通常得不到準(zhǔn)確的基數(shù)。為使基數(shù)估計(jì)能夠根據(jù)執(zhí)行期實(shí)際運(yùn)行結(jié)果進(jìn)行動(dòng)態(tài)調(diào)整，一些自適應(yīng)策略[2-3]被提出。文獻(xiàn)[2]中提出一種ASE(adaptive selectivity estimator，自適應(yīng)選擇度估計(jì))策略，不需要進(jìn)行離線的統(tǒng)計(jì)信息收集或者建立樣本，而是根據(jù)子查詢的反饋結(jié)果進(jìn)行基數(shù)估計(jì)，具體策略為以一系列查詢?yōu)榛鶞?zhǔn)，根據(jù)前置查詢的執(zhí)行結(jié)果自我調(diào)整后續(xù)查詢的統(tǒng)計(jì)信息，進(jìn)而提高基數(shù)估計(jì)的準(zhǔn)確度。

1.3 討 論

上述各種策略對(duì)于統(tǒng)計(jì)信息的使用是即時(shí)的，沒(méi)有利用執(zhí)行期查詢執(zhí)行結(jié)果提高收集統(tǒng)計(jì)信息效率以及準(zhǔn)確度，并將其進(jìn)行緩存，利于后續(xù)使用。雖然文獻(xiàn)[2]能夠在執(zhí)行期收集，但面對(duì)大數(shù)據(jù)量，收集效率較低，影響查詢性能。文獻(xiàn)[3]提出的LEO(learning optimizer,自學(xué)習(xí)優(yōu)化器)涉及的基數(shù)估計(jì)策略和我們提出的思想最為接近，監(jiān)控并學(xué)習(xí)查詢執(zhí)行過(guò)程中的基數(shù)估計(jì)結(jié)果，用來(lái)提供后續(xù)基數(shù)估計(jì)的準(zhǔn)確度，但沒(méi)有進(jìn)行資源感知以及查詢結(jié)果的緩存。

2 相關(guān)定義

為便于理解論文提出的基于查詢結(jié)果的基數(shù)估計(jì)方法，給出如下相關(guān)定義。

定義1基數(shù)項(xiàng)(CardItem)，存儲(chǔ)基于查詢結(jié)果的統(tǒng)計(jì)信息的最小單位，類似關(guān)系中一個(gè)元組，形式化表示為:Ci=(type,name,predicate,cardinality,expire,hot),鍵為:(name,predicate)，下文將Ci簡(jiǎn)寫為(t,n,p,c,e,h)。參數(shù)解釋如表1。

定義2基數(shù)表(CardTable)，用來(lái)存儲(chǔ)各個(gè)基數(shù)項(xiàng)，形式化定義為Ct={Ci}。Ct可以以關(guān)系的形式進(jìn)行存儲(chǔ)，方便建立索引，加快Ci的獲取速度。

表1 Ci參數(shù)介紹

3 基于查詢結(jié)果的基數(shù)估計(jì)策略

3.1 架 構(gòu)

如圖1所示,傳統(tǒng)查詢處理過(guò)程:輸入查詢,解析器將查詢轉(zhuǎn)換為邏輯樹,根據(jù)邏輯樹進(jìn)行查詢優(yōu)化,生成計(jì)劃,執(zhí)行計(jì)劃并得到最終結(jié)果。

圖1 基于CEQR的查詢架構(gòu)圖

查詢優(yōu)化過(guò)程中,利用統(tǒng)計(jì)信息推導(dǎo)出基本表和中間結(jié)果的基數(shù)進(jìn)行基于代價(jià)的查詢優(yōu)化。引入CEQR策略后,首先根據(jù)邏輯樹執(zhí)行基數(shù)鍵提取模塊(3.2小節(jié)),得到基本表與其關(guān)聯(lián)謂詞的對(duì)應(yīng)關(guān)系,形成三元組(t,n,p),其中(n,p)為基數(shù)鍵,然后根據(jù)基數(shù)鍵利用資源感知模塊(3.3小節(jié))查找對(duì)應(yīng)的基數(shù)項(xiàng)(Ci)將Ci反饋給查詢優(yōu)化模塊?；鶖?shù)表維護(hù)(3.4小節(jié))的內(nèi)容來(lái)自更新操作產(chǎn)生的更改數(shù)據(jù)以及計(jì)劃執(zhí)行的結(jié)果。

3.2 基數(shù)鍵提取

為方便分析,采用經(jīng)典SPJ(select project join,選擇,映射,連接)格式[18]作為對(duì)象。這里只針對(duì)基表(B)進(jìn)行提取,中間結(jié)果部分在計(jì)劃執(zhí)行階段通過(guò)基表推導(dǎo)或者從Ct中獲取。提取過(guò)程如圖2所示,{n1,n2,..,nm}為連接的基表,{p1,p2,…,pk}為選擇謂詞。以基表為單位,將屬于這個(gè)基表的選擇謂詞映射到這個(gè)基表,然后形成一個(gè)三元組(t,n,p)。(t,n,p)為Ci的一部分,p為選擇謂詞構(gòu)成的集合。如果p中某些子集能夠合并,即這些子集中的元素涉及相同列的謂詞,則將其合并成一個(gè)謂詞。

圖2 基數(shù)鍵提取

示例見(jiàn)圖3,圖3中,c1,c2表示表的列名。如p1(n1.c1<100)和p3(n1.c1>0)同時(shí)隸屬于n1表的c1列,因此將這2個(gè)謂詞合并,形成新的謂詞:c1(0,100)。

圖3 基數(shù)鍵提取示例

3.3 資源感知策略

隨著硬件技術(shù)的發(fā)展,緩存資源越來(lái)越豐富,為

充分利用富余緩存資源,提高Ci獲取速度,將熱Ci映射到合適的緩存區(qū)。這里將Ci分為熱Ci(Hot CI,簡(jiǎn)稱Hot-Ci)、冷Ci(Cold CI,簡(jiǎn)稱Col-Ci)和溫CI(Middle CI,簡(jiǎn)稱Mid-Ci)。Hot-Ci常駐緩存,Col-Ci常駐磁盤,冷熱數(shù)據(jù)通過(guò)Ci訪問(wèn)頻度進(jìn)行標(biāo)識(shí)。Mid-Ci指新生成的Ci,需要將它的鍵與緩存中Ci項(xiàng)的鍵進(jìn)行比較確定其冷熱程度。資源感知過(guò)程如圖4,其中{k1,k2,…}表示Ct表中各個(gè)Ci的鍵值,對(duì)應(yīng)定義(1)中的(n,p)。緩存中以Ci格式定義緩存項(xiàng)。如果存在相等的緩存項(xiàng),則進(jìn)行合并(合并方式見(jiàn)3.4節(jié))。如果沒(méi)有匹配,則標(biāo)記為Col-Ci存儲(chǔ)到Ct中。這里規(guī)定初始映射到緩存項(xiàng)的Ci為舊Ci(o),新生成的Ci標(biāo)記為新Ci(n)。

圖4 資源感知過(guò)程

為合理安排Ci,提出如下資源管理方法。每一個(gè)Ci大小基本固定,設(shè)置為r,并規(guī)定緩存資源(Si)中Ci所占百分比為pi,則某一個(gè)緩存資源Si所能存儲(chǔ)的Ci的個(gè)數(shù)如(1)所示。

(1)

利用(2)中的哈希函數(shù)根據(jù)Ci的鍵將其映射到合適的Si中,并保證按鍵排序,其中N表示Si的個(gè)數(shù)。如果某一個(gè)Si中保存的Ci個(gè)數(shù)違反公式(1),則利用線性探測(cè)再散列的方式找到其合適的存放位置A。

(2)

3.4 基數(shù)表維護(hù)

基數(shù)表(Ct)與基本表數(shù)據(jù)大小無(wú)關(guān),但與基本表數(shù)據(jù)的內(nèi)容和查詢句式相關(guān),即原始基本表數(shù)據(jù)改變或者查詢句式改變,都有可能導(dǎo)致Ct的改變,即影響Ci的準(zhǔn)確度,需要對(duì)Ct進(jìn)行維護(hù)。維護(hù)內(nèi)容分為兩方面:更改維護(hù)(3.4.1節(jié))和查詢維護(hù)(3.4.2節(jié))。

3.4.1 更改維護(hù)

數(shù)據(jù)庫(kù)中insert/update/delete 3種操作會(huì)改變基本表的數(shù)據(jù),間接影響Ct,為統(tǒng)一維護(hù)接口,將insert/update/delete 3種操作涉及的數(shù)據(jù)轉(zhuǎn)換為(t,n,p,c)格式,(n,p)對(duì)應(yīng)Ct中的鍵。其中c只針對(duì)insert操作。轉(zhuǎn)換過(guò)程如下。

·insert轉(zhuǎn)換:將insert中涉及到的插入值轉(zhuǎn)換為謂詞形式,即統(tǒng)計(jì)各個(gè)插入列對(duì)應(yīng)的值的最大值、最小值以及行數(shù)(c),得出(t,n,p,c)四元組,其中p由插入的值中最小值和最大值形成的區(qū)間得到。

·update轉(zhuǎn)換:將update中涉及到的更新謂詞映射到需要更新的表中,形成(t,n,p)。

·delete轉(zhuǎn)換:將delete中涉及到的刪除謂詞映射到需要?jiǎng)h除的表中,形成(t,n,p)。

由于(t,n,p,c)對(duì)應(yīng)的Ci可能已經(jīng)存在,因此需要根據(jù)情況對(duì)Ci舊值和新值進(jìn)行基于鍵的合并、刪除、更新等操作。維護(hù)的情況共分為4種:舊鍵包含新鍵、新鍵包含舊鍵、新鍵與舊鍵相交、新鍵與舊鍵不相交。具體維護(hù)操作列表如圖5,其參數(shù)介紹如表2。

具體維護(hù)策略為:如果n-n和o-n不相等,則將n-n對(duì)應(yīng)的Ci直接插入到Ct中。如果相等,則根據(jù)新舊謂詞的關(guān)系(圖5中的第一列)分類進(jìn)行維護(hù)。具體以圖5中第三行為例進(jìn)行說(shuō)明。對(duì)于Ci的其他項(xiàng)e和h,分別設(shè)為默認(rèn)值false和1。

·insert操作:首先利用me操作將新舊謂詞合并成新的謂詞m-p,然后運(yùn)行add操作將新舊基數(shù)相加得到新的基數(shù)m-c。雖然舊Ci的基數(shù)發(fā)生改變,但仍然存在概率被使用,為增加命中率,這里并不舍棄這個(gè)Ci,而是利用upd操作以σ倍的m-c更新為新的基數(shù),最后將新形成的Ci(n-n,m-p,m-c),利用ins操作插入到Ct中。

·delete操作:首先生成m-c,然后更新舊Ci的基數(shù)。

·update操作:直接將新形成的Ci插入到Ct中,原因是update操作對(duì)于重疊的謂詞部分的更新并沒(méi)有改變這個(gè)范圍內(nèi)的行數(shù)。

圖5 基數(shù)表維護(hù)操作列表

3.4.2 查詢維護(hù)

維護(hù)過(guò)程如圖6所示,其中t1,t2表示基本表,J1表示中間結(jié)果,即表連接后的結(jié)果。為具體說(shuō)明維護(hù)過(guò)程,以流行的流水線執(zhí)行方式[19]為例,以左深樹表示執(zhí)行計(jì)劃。構(gòu)建操作包括:fetch(p),counter( ),join(n1,n2,p),update(n,p,c)。

fetch(p),作用是獲取一行滿足特定謂詞的數(shù)據(jù),應(yīng)用在基本表(B)的取數(shù)據(jù)操作和流水線某一個(gè)步驟(連接)的取數(shù)據(jù)操作。counter( ),作用是統(tǒng)計(jì)基表或中間結(jié)果實(shí)際輸出行數(shù)。join(n1,n2,p),作用是根據(jù)連接條件連接兩部分?jǐn)?shù)據(jù),n1和n2可能是基本表,也可能是中間結(jié)果。update(t,n,p,c),將3.2節(jié)形成的(t,n,p)以及獲得的基數(shù)c通過(guò)鍵(n,p)對(duì)Ct進(jìn)行更新,更新過(guò)程詳見(jiàn)3.4.1節(jié)。維護(hù)過(guò)程如下。

·在計(jì)劃執(zhí)行過(guò)程中,從根節(jié)點(diǎn)開始遍歷整顆物理計(jì)劃樹,并根據(jù)每一個(gè)節(jié)點(diǎn)的執(zhí)行結(jié)果獲得基數(shù)。

·對(duì)于中間結(jié)果(J1),采取如下步驟獲取基數(shù):join->fetch->counter->update。

·對(duì)于基本表(t),采取如下步驟獲取基數(shù):fetch->counter->update。

·基數(shù)獲取完畢后,通過(guò)資源感知模塊(3.3節(jié))將對(duì)應(yīng)的基數(shù)保存到緩存或者Ct中。

圖6 查詢維護(hù)過(guò)程

4 算 法

本章給出基于查詢結(jié)果的基數(shù)估計(jì)策略(CEQR)算法偽代碼描述。

CEQR算法

輸入:Q,Ct,S

輸出:{Ci}

1.A-tree=parse(Q)

2.B-keys=extract-keys(A-tree)

3.cards=get-cached-cards(B-keys,S)

4.IF NULL==cards

5. cards=get-basic-cards(B-keys,S)

6.P-tree=gene-physical-plan(cards)

7.{Ci}=collect-Ci(P-tree.root)

8.maintain-Ct({Ci},Ct,S)

CEQR算法對(duì)查詢(Q)進(jìn)行解析(parse),生成邏輯樹(A-tree)(行1),利用基數(shù)鍵提取功能從邏輯樹中提取基數(shù)項(xiàng)鍵值(B-keys,對(duì)應(yīng)(n,p))(行2)。利用鍵值到緩存(S)中查找對(duì)應(yīng)的基數(shù)(行3),如果基數(shù)不存在,則需要到基數(shù)表中查找基數(shù)(行4～5)。將得到的基數(shù)應(yīng)用到查詢優(yōu)化中物理計(jì)劃(P-tree)產(chǎn)生部分(行6)。在計(jì)劃執(zhí)行過(guò)程中調(diào)用collect-Ci函數(shù)從物理計(jì)劃樹中根節(jié)點(diǎn)(root)遞歸收集所有基表以及中間結(jié)果的基數(shù)(行7)。收集完畢后,調(diào)用maintain-Ct函數(shù)對(duì)基數(shù)表進(jìn)行維護(hù)(行8)。

函數(shù)collect-Ci

輸入:root

輸出:{Ci}

1. IF root !=NULL

2. cards=execute(root)

3. IF root.type==B

4. {Ci}.push(B,cards)

5. IF root.type==M

6. {Ci}.push(M,cards)

7. collect-Ci(root.left-child)

8. collect-Ct(root.right-child)

函數(shù)collect-Ci用于根據(jù)執(zhí)行結(jié)果收集基數(shù)。過(guò)程為:如果物理計(jì)劃樹根節(jié)點(diǎn)存在,則對(duì)于計(jì)劃樹中的每一個(gè)節(jié)點(diǎn),根據(jù)執(zhí)行的結(jié)果統(tǒng)計(jì)返回的行數(shù)(行1～2)。如果當(dāng)前節(jié)點(diǎn)類型為基本表,則將基本表對(duì)應(yīng)的基數(shù)存放到{Ci}中;如果為中間結(jié)果,則將中間結(jié)果對(duì)應(yīng)的基數(shù)存放到{Ci}中(行3～6)。遞歸遍歷左子樹和右子樹(行7～8)。

函數(shù)maintain-Ct

輸入:{Ci},Ct,S

輸出:Ct

1. FOR eachCiin {Ci}

2. addr=Hash(Ci)

3. old-Ci=fetch(S,addr)

4. IF old-Ci!=NULL

5. new-Ci=merge(Ci,old-Ci)

6. update(S,new-Ci)

7. store(new-Ci,Ct)

8. ELSE

9. store(Ci,Ct)

函數(shù)maintain-Ct作用為針對(duì)產(chǎn)生的基數(shù)項(xiàng)進(jìn)行基數(shù)表的維護(hù),過(guò)程為:對(duì)于每一個(gè)產(chǎn)生的基數(shù)項(xiàng),計(jì)算其緩存地址,根據(jù)緩存地址獲取緩存中已經(jīng)存在的基數(shù)項(xiàng)(行1～3)。如果存在,則將其和輸入的緩存項(xiàng)合并成新的Ci,更新本地緩存項(xiàng),并存儲(chǔ)到Ct中(行4～7)。如果不存在,則判斷為冷Ci,直接存儲(chǔ)到Ct中(行8～9)。

5 算法分析

傳統(tǒng)基數(shù)估計(jì)步驟分為:統(tǒng)計(jì)信息收集(C)、統(tǒng)計(jì)信息獲取(G)以及基數(shù)估計(jì)(E)。CEQR策略下,將基數(shù)估計(jì)分成基數(shù)鍵提取(De)、緩存查找(Fe)、Ci生成(Ge)、資源感知(Se)、基數(shù)獲取(Eg)五部分。根據(jù)功能,有映射:(Ge,Se)->C,(De,Fe,Se)->G,Eg->E。下面就CEQR算法代價(jià)進(jìn)行評(píng)估。

傳統(tǒng)基數(shù)估計(jì)策略(TRA)估計(jì)時(shí)間代價(jià)見(jiàn)(3)式。其中T表示不同階段的時(shí)間代價(jià),t表示一次網(wǎng)絡(luò)通信代價(jià),N表示統(tǒng)計(jì)信息收集時(shí)需要進(jìn)行的網(wǎng)絡(luò)通信次數(shù),與數(shù)據(jù)量成正比,M表示某個(gè)表數(shù)據(jù)分布的節(jié)點(diǎn)個(gè)數(shù)。

TTRA=TC+TG+TE

(3)

公式(3)中,無(wú)論是集中式(centralized)還是分布式(distributed),基數(shù)估計(jì)(E)都是在查詢節(jié)點(diǎn)內(nèi)存中操作,涉及數(shù)據(jù)量小,因此其時(shí)間代價(jià)可忽略(ignored)。統(tǒng)計(jì)信息獲取(G)時(shí),集中式下可忽略,而分布式環(huán)境下,由于一個(gè)表的統(tǒng)計(jì)信息分布存儲(chǔ),因此在查詢節(jié)點(diǎn)獲得統(tǒng)計(jì)信息時(shí)需要將局部統(tǒng)計(jì)信息進(jìn)行整合,消耗網(wǎng)絡(luò)代價(jià)。統(tǒng)計(jì)信息收集與數(shù)據(jù)量相關(guān),在數(shù)據(jù)量較大時(shí),需要消耗大量CPU代價(jià)(#CPU)和IO代價(jià)(#IO)。γ取值為{0,1},當(dāng)收集統(tǒng)計(jì)信息時(shí),需要形成全局和局部?jī)煞N統(tǒng)計(jì)信息,則取值為1,代表消耗網(wǎng)絡(luò)代價(jià),如文獻(xiàn)[20];當(dāng)只形成局部統(tǒng)計(jì)信息,則取值為0,代表不需要消耗網(wǎng)絡(luò)代價(jià),如文獻(xiàn)[21]。CEQR算法的時(shí)間代價(jià)如(4)式。

(4)

由于De和Eg都是在內(nèi)存中進(jìn)行,并且處理數(shù)據(jù)量很小,因此效率與E相當(dāng)。Fe根據(jù)鍵到緩存獲得Ci,如果命中(hit),則代價(jià)忽略,如果不命中(non-hit),需要消耗一次網(wǎng)絡(luò)代價(jià)到Ct中獲取Ci。即使分布式環(huán)境下,也不需要進(jìn)行統(tǒng)計(jì)信息的合并,因此多數(shù)情況下不需要消耗網(wǎng)絡(luò)代價(jià)。資源感知(Sw)策略作用是將熱數(shù)據(jù)映射到合適的緩存資源中,分布式環(huán)境下需要消耗網(wǎng)絡(luò)資源,與分布式節(jié)點(diǎn)數(shù)(K)相關(guān)。

綜上所述,傳統(tǒng)基數(shù)估計(jì)策略與原數(shù)據(jù)量相關(guān),即使采用樣本策略,為保證準(zhǔn)確度,也需要在較大樣本空間下進(jìn)行。CEQR算法與原數(shù)據(jù)量無(wú)關(guān),隨著查詢數(shù)量的增多,算法的準(zhǔn)確度和效率大幅提升。通過(guò)(5)式的推導(dǎo),得出TCEQR<=TTRA,等號(hào)成立的情況為在執(zhí)行Fe時(shí)緩存不命中,隨著查詢數(shù)量的增多,這種情況將大大減少。

basedon:TDe?TE,TGe?TE,

TEg?TE,TFe≤TG,

TSe≤TG

infer:TCEQR≤TTRA

(5)

6 適應(yīng)性

CEQR策略的效果會(huì)隨著查詢語(yǔ)句數(shù)量的增大而增強(qiáng),并且隨著硬件的發(fā)展,緩存資源逐漸豐富,能夠充分滿足CEQR策略的資源感知需求,大大降低統(tǒng)計(jì)信息的獲取以及維護(hù)代價(jià)。因此CEQR策略能夠滿足OLAP、OLTP以及OLAP&OLTP系統(tǒng)中進(jìn)行大數(shù)據(jù)量基數(shù)估計(jì)需求。

7 誤差分析

定義3基數(shù)估計(jì)誤差,即利用統(tǒng)計(jì)信息推導(dǎo)出的基數(shù)值和運(yùn)行時(shí)實(shí)際基數(shù)值之間的差值。這里定義3種誤差:初始誤差(ΔI),表示計(jì)算基本表基數(shù)值產(chǎn)生的誤差;連接誤差(ΔJ),表示根據(jù)基本表推導(dǎo)出連接結(jié)果基數(shù)值產(chǎn)生的誤差;更新誤差(ΔU),表示原數(shù)據(jù)更新導(dǎo)致依賴的基數(shù)值過(guò)期產(chǎn)生的誤差。這3種誤差的定義以及關(guān)系如(6)式所示。VE和VA分別表示基數(shù)估計(jì)值和實(shí)際基數(shù)值。

ΔI|J|U=|VE-VA|

(6)

如果基數(shù)一經(jīng)產(chǎn)生不會(huì)改變,則更新誤差不存在,如OLAP系統(tǒng)。對(duì)于OLTP和OLAP&OLTP混合的系統(tǒng),根據(jù)文獻(xiàn)[1],ΔU加強(qiáng)(power)ΔI,而ΔI加強(qiáng)ΔJ,ΔJ則加強(qiáng)優(yōu)化偏差。傳統(tǒng)基數(shù)估計(jì)策略3種誤差都存在,并且由于數(shù)據(jù)關(guān)聯(lián)性以及樣本建立策略的不合理,導(dǎo)致ΔI值較大,嚴(yán)重影響優(yōu)化器的優(yōu)化效果?；贑EQR的基數(shù)估計(jì)策略保存基本表和中間結(jié)果的準(zhǔn)確基數(shù)值,因此大大降低了ΔI和ΔJ值。通過(guò)資源感知策略結(jié)合細(xì)粒度Ci,大大降低ΔU值。

8 實(shí) 驗(yàn)

8.1 實(shí)驗(yàn)環(huán)境

我們將CEQR策略實(shí)施在淘寶開源數(shù)據(jù)庫(kù)——Oceanbase(源碼見(jiàn)文獻(xiàn)[22]，架構(gòu)見(jiàn)文獻(xiàn)[23])中。利用Oceanbase的單節(jié)點(diǎn)模式和集群模式搭建集中式測(cè)試環(huán)境和分布式測(cè)試環(huán)境。配置如下。

單節(jié)點(diǎn)模式 主頻為1400MHz的AMD Opteron(TM)處理器和16G內(nèi)存，物理CPU個(gè)數(shù)為2，物理核數(shù)8個(gè)，邏輯核數(shù)16個(gè)；操作系統(tǒng)為Red Hat 6.2。

集群模式 配置7個(gè)計(jì)算節(jié)點(diǎn)，其中1個(gè)主節(jié)點(diǎn)，6個(gè)副節(jié)點(diǎn)，主節(jié)點(diǎn)配置32G內(nèi)存，其他和單節(jié)點(diǎn)模式配置相同，副節(jié)點(diǎn)配置全部和單節(jié)點(diǎn)模式配置相同。

8.2 實(shí)驗(yàn)數(shù)據(jù)

利用tpc-h工具[24]生成8組TPC-H相關(guān)數(shù)據(jù)集(每組包含8張表)，數(shù)據(jù)量為(0.5,1,5,10,15,20,25,30)，單位為Gigabytes。

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

測(cè)試CEQR在單節(jié)點(diǎn)模式和集群模式下的效率。

8.3.1 單節(jié)點(diǎn)模式

在Oceanbase中實(shí)現(xiàn)postgresql的統(tǒng)計(jì)信息估計(jì)策略(簡(jiǎn)稱PG)。目的為測(cè)試2種策略的統(tǒng)計(jì)信息收集效率，預(yù)期為CEQR收集效率高于PG。設(shè)置postgresql的樣本率為30%。使用TPC-H相關(guān)查詢Q4生成CEQR相關(guān)基數(shù)項(xiàng)。測(cè)試數(shù)據(jù)選取TPC-H中的ORDERS表，并保證CEQR和PG收集的數(shù)據(jù)量相同。測(cè)試結(jié)果如圖7。PG中基數(shù)由統(tǒng)計(jì)信息推導(dǎo)得到，涉及到表行數(shù)，每列的不同值個(gè)數(shù)等統(tǒng)計(jì)信息的收集，需要進(jìn)行各種聚集運(yùn)算以及消耗數(shù)據(jù)掃描代價(jià)。而CEQR中基數(shù)來(lái)自SQL語(yǔ)句執(zhí)行過(guò)程中表的實(shí)際基數(shù)，只需消耗基數(shù)計(jì)算的代價(jià)。因此CEQR收集效率優(yōu)于PG。圖7符合預(yù)期測(cè)試結(jié)果。

圖7 單節(jié)點(diǎn)模式下CEQR和PG效率對(duì)比

8.3.2 集群模式

在Oceanbase中實(shí)現(xiàn)PDW QO中統(tǒng)計(jì)信息收集策略(簡(jiǎn)稱PC)。PC利用SQL語(yǔ)句進(jìn)行局部并行收集，雖然在一定程度上提高了收集效率，但由于存在傾斜問(wèn)題以及合并全局統(tǒng)計(jì)信息存在的網(wǎng)絡(luò)通信代價(jià)，因此預(yù)期數(shù)據(jù)量較大時(shí)，CEQR收集效率優(yōu)于PC。測(cè)試結(jié)果如圖8。

圖8 集群模式下CEQR和PDW QO效率對(duì)比

圖8中，當(dāng)數(shù)據(jù)量較小時(shí)，由于子表分散比較均勻并且數(shù)量較少，因此PC的收集效率較高，與CEQR基本相同。當(dāng)數(shù)據(jù)量較大時(shí)，由于負(fù)載不均衡以及網(wǎng)絡(luò)通信的增加，使PC效率低于CEQR。圖8符合預(yù)期測(cè)試結(jié)果。

9 結(jié) 論

基數(shù)估計(jì)在數(shù)據(jù)庫(kù)查詢優(yōu)化中占有重要地位，其效率以及準(zhǔn)確度關(guān)系最優(yōu)計(jì)劃的選擇。傳統(tǒng)基數(shù)估計(jì)策略中的統(tǒng)計(jì)信息或來(lái)自原數(shù)據(jù)或來(lái)自建立樣本，是一種推導(dǎo)、估計(jì)的過(guò)程，不能真實(shí)反映運(yùn)行時(shí)基本表以及中間結(jié)果實(shí)際基數(shù)，嚴(yán)重影響優(yōu)化效果。論文提出一種基于查詢結(jié)果的基數(shù)估計(jì)策略，能夠在查詢執(zhí)行過(guò)程中保存準(zhǔn)確的運(yùn)行時(shí)基數(shù)，并利用資源感知策略，提供快速的統(tǒng)計(jì)信息獲取以及維護(hù)，在查詢量足夠的情況下，能夠大大提高基數(shù)估計(jì)的效率和準(zhǔn)確度。