基于濃密樹查詢優(yōu)化方法(數(shù)據(jù)庫)

時間：2022-12-29 04:30:02 | 來源：信息時代

時間：2022-12-29 04:30:02 來源：信息時代

    基于濃密樹查詢優(yōu)化方法 : 采用濃密樹模型表示查詢執(zhí)行計劃的一種優(yōu)化方法。濃密樹查詢執(zhí)行計劃是一種更一般的查詢執(zhí)行計劃表示模型。
濃密樹是一個滿足下列條件的樹:
(1)葉結(jié)點表示關(guān)系。
(2)每個內(nèi)結(jié)點既表示一個數(shù)據(jù)操作,也表示操作的結(jié)果關(guān)系,其子結(jié)點所對應(yīng)的關(guān)系是該內(nèi)結(jié)點的操作關(guān)系。
作為一種更一般的查詢執(zhí)行計劃表示模型,濃密樹在線性樹查詢執(zhí)行計劃中,多個連接操作被逐個地完成,即第一個第二個關(guān)系首先連接成為一個關(guān)系,其結(jié)果再與第三個關(guān)系連接成為一個關(guān)系,如此下去,直至最后一個關(guān)系被連接。在濃密樹查詢執(zhí)行計劃中,可以有多個關(guān)系對同時進行連接操作。
設(shè)Q是一個多連接查詢。Q的所有濃密樹查詢執(zhí)行計劃構(gòu)成了Q的濃密樹查詢執(zhí)行計劃空間。如果Q包括n個連接操作,可以從Q構(gòu)造出[]×n!個濃密樹。如果使用m種算法實現(xiàn)一個連接操作,則對于每個濃密樹存在n^m種執(zhí)行Q的策略或計劃。于是,得到n^m[]×n!種按照濃密樹方式執(zhí)行Q的查詢執(zhí)行計劃。顯然,濃密樹查詢執(zhí)行計劃空間遠比其他幾種查詢執(zhí)行計劃空間大。如果考慮到處理器和存儲器的分配,濃密樹的查詢執(zhí)行計劃空間將會更大。
1.并行查詢優(yōu)化算法GP
GP算法是一種循環(huán)算法,每個循環(huán)產(chǎn)生濃密樹查詢執(zhí)行計劃的一個順序執(zhí)行段。GP算法也是一個貪心算法。在每次循環(huán)中,它都把盡可能多的連接操作放進一個順序執(zhí)行段,以獲得最大的局部并行性。GP算法的輸入是一個連接查詢圖G=(V,E),其中,V是結(jié)點集,每個結(jié)點對應(yīng)一個關(guān)系,E是邊集合,每條邊表示一個連接操作,用關(guān)系對(R₁,R₂₎表示。輸出為查詢執(zhí)行計劃S。算法的主要思想如下: 先令S為空集合。如果參與連接的關(guān)系數(shù)目大于3(即結(jié)點數(shù)V>3),則調(diào)用函數(shù)select_rel_pairs(G)來選擇一組并行執(zhí)行的連接操作 Ψ并將其并入S中。然后算法根據(jù)Ψ中的操作對圖G進行修改。對Ψ中每個連接操作(R₁,R₂₎,設(shè)R₁表示R₁與R₂的連接結(jié)果關(guān)系。算法從G中刪除結(jié)點R₂并從E中刪除滿足條件{(R₁, R₂₎}∪ {(r,R₁)|∃(r,R₂₎∈E}的邊。最后算法確定G中余下的3個關(guān)系的優(yōu)化連接序列并將其并入S中。
算法GP中的select-rel-pairs(G)函數(shù)為一個順序執(zhí)行段選擇盡可能多的可并行執(zhí)行的連接操作。它的輸入是一個連接查詢圖G,輸出是可并行執(zhí)行的一組連接操作。該函數(shù)循環(huán)調(diào)用minimum_cost(G,k,Ψ_k,C_k)函數(shù),若Ψ_k不包含G中所有連接關(guān)系對,則執(zhí)行minimum_cost(G,k+1,Ψ_k+1,C_k+1),直至(C_k+1>C_k)∨(Ψ_k+1包含所有G中的連接關(guān)系對)。上述循環(huán)從k=0開始,逐次遞增直至滿足循環(huán)結(jié)束條件。當(dāng)循環(huán)結(jié)束后,若(C_k+1>C_k)則返回Ψ_k,否則返回Ψ_k+1。
函數(shù)minimum_cost(G,i,Ψ_i,C_k)是select_rel_pairs函數(shù)的核心部分。它以連接查詢圖G和需要并行運行的連接操作數(shù)i為輸入,計算所有首先并行執(zhí)行i個連接操作的查詢執(zhí)行計劃的開銷,以連接關(guān)系對集合的形式確定具有最小開銷的查詢執(zhí)行計劃并返回到Ψ_i,其開銷返回到C_i,并為確定的查詢執(zhí)行計劃的每個連接操作確定實現(xiàn)算法。
為了減少minimum cost函數(shù)的開銷,進而減少優(yōu)化算法的開銷,將兩個啟發(fā)式規(guī)則,分別加入GP算法,得到啟發(fā)式貪心算法GPT。
2. GPT算法
GPT是啟發(fā)式貪心算法。一個濃密樹查詢執(zhí)行計劃的開銷是其所有順序執(zhí)行段的開銷的總和?？紤]到每個多連接查詢的所有可能的順序執(zhí)行段數(shù)和每個階段內(nèi)所有可能并行執(zhí)行的連接操作數(shù),濃密樹查詢執(zhí)行計劃空間是相當(dāng)大的,搜索具有最小開銷的濃密樹查詢執(zhí)行計劃的時間復(fù)雜性相當(dāng)大。為了減少查詢執(zhí)行計劃空間,算法GPT的啟發(fā)式規(guī)則規(guī)定只在滿足下列條件的濃密樹查詢執(zhí)行計劃中尋找優(yōu)化查詢執(zhí)行計劃: ①第一順序執(zhí)行段具有多個連接操作并行執(zhí)行; ②其余順序執(zhí)行段僅包含一個連接操作。
這樣,算法GPT搜索的查詢執(zhí)行計劃空間(簡稱GPT查詢執(zhí)行計劃空間)就小了很多。對于GPT查詢執(zhí)行計劃空間中的每個查詢執(zhí)行計劃P,如果P的第一順序執(zhí)行段有k個并行執(zhí)行的連接操作,其余的順序執(zhí)行段僅執(zhí)行一個連接操作,則其開銷定義為:totalk(P)=par_join_cost(P_k)+seq_join_cost((P-R(P_k))∪join_result(P_k))。其中,P_k是P的第一順序執(zhí)行段,R(P_k)是查詢執(zhí)行計劃P_k的關(guān)系集合,par_join_cost(P_k)是并行執(zhí)行P_k中k個連接操作所需的開銷,join_result(P_k)是P_k的結(jié)果關(guān)系,seq_join_cost(X)是逐個執(zhí)行X中所有連接操作(每個連接操作可以由多個處理機并行執(zhí)行)所需開銷。GPT算法與GP算法的不同僅在于minimum_cost(G,k,Ψ_k,C_k)的不同。給定k,GPT算法的minimum_cost函數(shù),首先枚舉所有“第一順序執(zhí)行段包括k個連接操作、其余順序執(zhí)行段皆包括一個連接操作”的濃密樹查詢執(zhí)行計劃,計算每個計劃的開銷Totalk;然后選擇具有最小Totalk的計劃送Ψ_k,其開銷送C_k。只需要用函數(shù)minimum_costT(G,k,Ψ_k,C_k)替代GP算法中的函數(shù)minimum_cost(G,k,Ψ_k,C_k)即可得到GPT。