基于段式右線性樹查詢優(yōu)化方法(數(shù)據(jù)庫)

時(shí)間：2022-12-28 04:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-28 04:30:01 來源：信息時(shí)代

    基于段式右線性樹查詢優(yōu)化方法 : 采用片段式右線性樹的模型表示查詢執(zhí)行計(jì)劃的一種優(yōu)化方法。
1.片段式右線性樹(SRD樹)
片段式右線性樹,簡稱為SRD樹,由一組右線性樹連接而成,每個(gè)右線性樹稱為一個(gè)片段,每個(gè)片段中的一個(gè)連接操作稱為一個(gè)階段。片段式右線性樹可遞歸地定義如下:
(1)右線性樹是一個(gè)片段式右線性樹。
(2)如果T是一個(gè)片段式右線性樹,則用一個(gè)片段式右線性樹替代T的任何一個(gè)葉結(jié)點(diǎn)所得到的樹仍然是片段式右線性樹。
在基于片段式右線性樹的查詢優(yōu)化方法中,優(yōu)化算法僅考慮由片段式右線性樹表示的查詢執(zhí)行計(jì)劃,查詢執(zhí)行計(jì)劃空間由片段式右線性樹查詢執(zhí)行計(jì)劃組成。片段式右線性樹查詢執(zhí)行計(jì)劃空間遠(yuǎn)大于右線性樹和左線性樹的查詢執(zhí)行計(jì)劃空間。因此,不能使用枚舉方法,而需要采用更新穎、高效的啟發(fā)式查詢優(yōu)化方法。
2.片段式右線性樹(SRD)的構(gòu)造過程
給定一個(gè)查詢Q,Q的基于SRD樹的查詢優(yōu)化問題是構(gòu)造Q的優(yōu)化SRD樹的問題。Q的優(yōu)化SRD樹的構(gòu)造過程如下:①確定SRD樹的片段數(shù)m;②確定每個(gè)片段中的關(guān)系數(shù)的上界; ③以k和m為輸入,調(diào)用啟發(fā)式算法為每個(gè)片段選擇一組連接關(guān)系,生成SRD樹。以上三步的實(shí)現(xiàn)算法如下:
(1)確定SRD樹的片段數(shù)和每個(gè)片段中的關(guān)系數(shù):在確定SRD樹的片段數(shù)時(shí),必須考慮所有關(guān)系的大小和可用存儲器空間的大小。在可用存儲器空間的限制下,選擇盡量小的片段數(shù)。如果片段數(shù)過多,由于建立Hash表、流水線處理、片段的結(jié)果關(guān)系寫回磁盤等方面的開銷,可能會引起查詢處理時(shí)間的延長,影響系統(tǒng)的性能。片段數(shù)計(jì)算的規(guī)則為:在保證每個(gè)片段中的所有關(guān)系的大小不超過所有處理結(jié)點(diǎn)的累計(jì)存儲器容量的前提下,選擇最小的片段數(shù),則一個(gè)SRD樹的片段數(shù)應(yīng)該是

其中,q是查詢中的關(guān)系數(shù),N是處理機(jī)數(shù),|R_i|是R_i的字節(jié)數(shù),M是每個(gè)處理機(jī)的存儲器容量(字節(jié)數(shù))。
(2)確定出SRD樹的片段數(shù)以后,可以很容易地估算出每個(gè)片段中關(guān)系數(shù)的上界:

(3) 為各片段選擇關(guān)系生成SRD樹: 為每個(gè)片段選擇一組連接關(guān)系是基于SRD樹的查詢優(yōu)化算法的最復(fù)雜而且最關(guān)鍵的步驟。通常,有兩種啟發(fā)式算法可供采用:
最小開銷算法(MW算法): 給定一組關(guān)系和整數(shù)k,MW算法的功能是確定一個(gè)由k個(gè)內(nèi)關(guān)系R₁,…,R_k和一個(gè)外關(guān)系S組成的右線性樹,形成SRD樹的一個(gè)片段,使得如下的目標(biāo)函數(shù)最小化:

對于i=1,…,k,W是|S|、|R_i|和|I_i|的線性組合。MW算法在選擇內(nèi)外關(guān)系時(shí)使用了貪心法,即從給定的關(guān)系集合中選擇關(guān)系R使得W中項(xiàng)(C₁+C₂₎|R|+(C₃+C₄₎|I|最小,其中,I是由于選擇R而產(chǎn)生的中間連接結(jié)果。MW算法首先從給定關(guān)系集合中選擇一個(gè)關(guān)系作為R₁,然后選擇另一個(gè)關(guān)系作為外關(guān)系S,次之再選擇一個(gè)關(guān)系作為R₂,如此下去,最后選擇一個(gè)關(guān)系作為R_k。確定R₁時(shí),還不能計(jì)算與R₁有關(guān)的中間結(jié)果I₁,所以只需選擇R₁使得(C₁+C₂₎|R₁|最小。由于(C₁+C₂₎是常數(shù),只需選擇R₁使得|R₁|最小。從選擇外關(guān)系S開始,就可以計(jì)算出與所選擇關(guān)系相關(guān)的中間連接結(jié)果。于是,從選擇外關(guān)系S開始,每當(dāng)選擇一個(gè)關(guān)系R,必須保證(C₁+C₂₎|R|+(C₃+C₄₎|I|最小。設(shè)RS是給定的關(guān)系集合,MW算法如下:①從RS選擇關(guān)系R作為R₁,使|R₁|最小,RS=RS-{R}; ②從RS選擇關(guān)系R′作為S,使(C₁+C₃₎|S|+(C₃+C₄₎|I₁|最小,RS=RS-{R′};③對于2≤i≤k-1,從RS選擇關(guān)系R′_i作為R_i,使(C₁+C₂₎|R_i|+(C₃+C₄₎|I_i|最小,RS=RS-{R′_i};④從RS選擇關(guān)系R′_k作為R_k,使(C₁+C₂₎|R_k|+C₅|I_k|最小,RS=RS-{R’_k}。
DB算法: MW方法總是為較早的片段分配較小的關(guān)系。這種策略可能引起兩個(gè)問題。一是越后邊的片段所含的關(guān)系越大,可能會使總的可用存儲空間容納不了整個(gè)片段內(nèi)的所有內(nèi)關(guān)系,導(dǎo)致增加更多片段,降低執(zhí)行效率; 二是由于較早生成的片段包含小關(guān)系,存儲空間得不到充分利用。DB算法可以避免這兩個(gè)問題。
DB使用了懲罰和獲利兩個(gè)概念。懲罰定義為P=WP+WB,獲利定義為B=(|S|+|R₁|+…+|R_k|)-|I_k|。DB算法的目的是為每個(gè)片段分配關(guān)系R₁,S,R₂,…,R_k,使得Y=P-wB最小,w是加權(quán)因子。設(shè)RS是給定的關(guān)系集合。展開Y式,可以得到如下的DB算法: ①從RS選擇關(guān)系R作為R1,使得|R₁|最小,RS=RS-{R};②從RS選擇關(guān)系R′作為S,使得|S|最小,RS=RS-{R′}:③對于2≤i≤k-1,從RS選擇關(guān)系R′_i作為R_i,使得(C₂-C₃₎|R_i|+(C₃-C₄₎|I_i|最小,RS=RS-{(R′_i};④從RS選擇關(guān)系R′_k作為R_k,使得(C₂-C₃₎|R_k|+C₅|I_k|最小,RS=RS-{R′_k}。
3. SRD樹的生成算法
算法輸入為:查詢中的關(guān)系集合RS,查詢中關(guān)系個(gè)數(shù)q,系統(tǒng)中處理機(jī)個(gè)數(shù)N和每個(gè)處理機(jī)可用的存儲器容量M。算法輸出為查詢的SRD樹執(zhí)行計(jì)劃。算法的主要執(zhí)行過程如下:
首先計(jì)算片段數(shù)

然后估算每個(gè)片段中關(guān)系數(shù)的上界

最后使用MW或DB算法由RS逐個(gè)構(gòu)造片段S_i。