兩段式并行查詢優(yōu)化方法(數(shù)據(jù)庫)

時間：2022-10-31 14:30:01 | 來源：信息時代

時間：2022-10-31 14:30:01 來源：信息時代

    兩段式并行查詢優(yōu)化方法 : 一種高效率的并行算法,該算法分兩階段執(zhí)行:第一階段使用傳統(tǒng)的查詢優(yōu)化方法產(chǎn)生高效率的順序查詢執(zhí)行計劃。第二階段則再將其并行化。第一階段產(chǎn)生的順序查詢執(zhí)行計劃,產(chǎn)生一個高效率的并行查詢執(zhí)行計劃。兩階段算法的主要問題是: 第一階段產(chǎn)生的順序查詢執(zhí)行計劃可能具有很高的固有順序性,但會使第二階段產(chǎn)生的并行查詢執(zhí)行計劃的并行性降低。
1.最小執(zhí)行時間方法
該方法是以最小化查詢執(zhí)行時間為目標的一種兩段式并行查詢優(yōu)化方法。以多連接查詢?yōu)槔?假定每個連接操作都由merge_sort連接算法實現(xiàn)。設(shè)R和S是兩個關(guān)系。使用merge_sort連接算法在單處理機系統(tǒng)中完成R和S的連接操作所需時間開銷定義為cost(R,S)=|R|+|S|+|R⋈S|, 其中,R⋈S表示R和S的連接,|R|、|S|和|R⋈S|分別表示關(guān)系R、S和R⋈S結(jié)果的大小。 兩個階段分述如下:
(1)順序查詢執(zhí)行計劃的產(chǎn)生算法: 有兩個高效率順序查詢執(zhí)行計劃的產(chǎn)生算法:
①貪心算法SG:設(shè)ψ是多連接查詢Q中所有關(guān)系的集合。SG算法的基本思想是: 首先從ψ中選擇兩個關(guān)系R和S,使得Cost(R,S)最小; 然后,令ψ={R⋈S}∪(ψ-{R,S}), 即用關(guān)系R⋈S替代R和S; 再從ψ中選擇R’≠R⋈S, 使得Cost(R⋈S,R′)最小; 這個過程循環(huán)反復(fù)進行直至ψ為空。
②啟發(fā)式算法SH:SG算法只能產(chǎn)生線性樹查詢執(zhí)行計劃。SH能夠產(chǎn)生更一般的濃密樹查詢執(zhí)行計劃。SH算法的思想來自于計算n個數(shù)的huffman算法。設(shè)ψ是多連接查詢Q中所有關(guān)系的集合。SH算法的基本思想是:首先從ψ中選擇兩個關(guān)系R和S, 使得cost(R,S)最小; 然后令ψ={R⋈S}∪(ψ-{R, S}), 即用關(guān)系R⋈S替代R和S; 再從ψ中選擇R′和S″,使得Cost(R′,S′)最小; 這個過程循環(huán)反復(fù),直至ψ為空。
(2)順序查詢執(zhí)行計劃的并行化: 順序查詢執(zhí)行計劃并行化的一種方法是為執(zhí)行計劃中每個連接操作分配多個處理機,既實現(xiàn)單個連接操作的并行執(zhí)行,也實現(xiàn)多個連接操作的并行執(zhí)行。有兩類為連接操作分配處理機的方法。
① 自底向上的分配方法:在一定的處理機數(shù)量范圍內(nèi),一個連接操作的執(zhí)行時間隨著執(zhí)行這個操作的處理機個數(shù)的增加而減少。當(dāng)執(zhí)行這個連接操作的處理機個數(shù)達到某個值后,由于該連接操作可開發(fā)的并行性的限制和通信開銷的迅速增長,繼續(xù)增加執(zhí)行該操作的處理機數(shù)將增加這個操作的執(zhí)行時間。這個值被稱為連接操作的最小時間點。在進行處理機分配時,必須充分考慮最小時間點的影響。以下是四種處理機分配策略:
順序執(zhí)行策略(SE): 逐個順序地執(zhí)行查詢執(zhí)行計劃中的每個連接操作,每個連接操作由所有處理機并行執(zhí)行。這種方法完全丟棄了多連接操作間的并行性。
固定分配方法(FS): 為查詢執(zhí)行計劃中的每個連接操作分配固定數(shù)量的處理機,發(fā)揮多連接操作間的并行性。
最小時間點方法(MT): 按照最小時間點P_m為每個連接操作分配處理機。由于數(shù)據(jù)相關(guān)性和處理機空閑的影響,這種方法僅能最小化單個連接操作的執(zhí)行時間,不一定能最優(yōu)化整個查詢的有效性。
時間與有效性折中方法(TE): 為查詢執(zhí)行計劃中每個連接操作分配x個處理機,其中,x∈(0,P_m]。
把任一個處理機分配策略與任一順序查詢執(zhí)行計劃生成算法結(jié)合,可得到完整的多連接查詢的啟發(fā)式優(yōu)化并行執(zhí)行算法。
② 自頂向下的處理機分配方法:該方法的核心是一個“同步執(zhí)行規(guī)則”。同步執(zhí)行規(guī)則定義為:處理機的分配要保證任一個連接操作的兩個操作關(guān)系必須在近似相等的時間點被同時產(chǎn)生。
設(shè)并行計算系統(tǒng)的處理機個數(shù)為P。由于順序查詢執(zhí)行計劃樹的根結(jié)點r對應(yīng)于最后執(zhí)行的連接操作,自頂向下的處理機分配方法首先把所有P個處理機全部分配給r。然后,把根結(jié)點r分得的P個處理機劃分為兩組L和R。L分配給r的左子結(jié)點,R分配給r的右子結(jié)點。L和R中的處理機數(shù)需要根據(jù)r的兩個子樹的工作量來確定,使得r的兩個子樹在近似相等的時間點產(chǎn)生r的兩個操作關(guān)系。上述過程自頂向下反復(fù)進行,直至查詢執(zhí)行計劃樹的所有內(nèi)結(jié)點(即所有連接操作)都被分配了處理機。算法TD與任何一個產(chǎn)生順序查詢執(zhí)行計劃的算法相結(jié)合即可得到一個完整的多連接查詢的優(yōu)化處理算法。