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

時間：2022-12-28 02:30:01 | 來源：信息時代

時間：2022-12-28 02:30:01 來源：信息時代

    基于左線性樹查詢優(yōu)化方法 : 采用左線性樹模型表示查詢執(zhí)行計劃的一種優(yōu)化方法。
1.左線性樹查詢優(yōu)化算法
一個多連接查詢的查詢樹是一棵樹T=(V,E),其中,V是結(jié)點(diǎn)集合,每個內(nèi)結(jié)點(diǎn)表示一個連接操作,同時也對應(yīng)于該連接操作的結(jié)果關(guān)系;每個葉結(jié)點(diǎn)表示一個操作關(guān)系,同時也表示這個關(guān)系上的scan操作,scan操作是直接作用在關(guān)系上的投影和選擇操作的組合; E是邊集合,如V表示的連接操作的輸入關(guān)系是結(jié)點(diǎn)V₁和V₂所對應(yīng)的關(guān)系,則(V₁,V)、(V₂,V)∈E。在查詢樹T中,如果根到結(jié)點(diǎn)V的路徑長為k,則稱V為T的k級結(jié)點(diǎn),如果從根到葉結(jié)點(diǎn)的最長路徑的長度為n,則稱這個查詢樹為n+1級查詢樹。
給定一棵查詢樹T,可得到查詢樹的數(shù)據(jù)相關(guān)圖,用來描述查詢樹中各操作之間的固有數(shù)據(jù)依賴性,規(guī)定查詢樹的并行執(zhí)行方式。
n+1級左線性樹(left-deep-tree)是一個滿足下列條件的查詢樹:
(1)具有2n+1個結(jié)點(diǎn)。
(2)每個內(nèi)結(jié)點(diǎn)有且僅有兩個子結(jié)點(diǎn)。
(3)每個內(nèi)結(jié)點(diǎn)(n-1級內(nèi)結(jié)點(diǎn)除外)的左子結(jié)點(diǎn)是一連接操作,右子結(jié)點(diǎn)是一關(guān)系。
(4)n-1級內(nèi)結(jié)點(diǎn)的兩個子結(jié)點(diǎn)皆為關(guān)系。
以下簡稱左線性樹為LDT樹。
設(shè)Q是一個具有n個連接操作的多連接查詢。可以從Q構(gòu)造出n!個等價的左線性樹。如果使用m種算法實(shí)現(xiàn)一個連接操作,則對于每個左線性樹存在mⁿ種執(zhí)行Q的策略或計劃。于是,得到mⁿn!種按照左線性樹方式執(zhí)行Q的查詢執(zhí)行計劃。這些查詢執(zhí)行計劃構(gòu)成了基于左線性樹的查詢執(zhí)行計劃空間?；谧缶€性樹的查詢優(yōu)化方法就是要從這個查詢執(zhí)行計劃空間中選擇具有最小或較小時間復(fù)雜性的計劃,完成Q的執(zhí)行。
2.基于并行Hash連接算法的LDT樹優(yōu)化查詢實(shí)例
以下以并行Hash連接算法為例,說明LDT樹與優(yōu)化查詢執(zhí)行計劃的關(guān)系和LDT樹的復(fù)雜性模型。在Hash連接算法中,連接關(guān)系分為內(nèi)關(guān)系和外關(guān)系。內(nèi)關(guān)系用來建立Hash表。外關(guān)系用來搜索匹配由內(nèi)關(guān)系建立的Hash表。Hash連接算法可以視為兩個獨(dú)立操作的組合。一個操作用來建立Hash表,簡記作build。另一個操作用來搜索匹配Hash表,實(shí)現(xiàn)兩個關(guān)系的連接,簡記作probe。Hash連接算法可以分為兩個順序執(zhí)行階段:
(1) build階段: 使用build操作,掃描內(nèi)關(guān)系,建立Hash表。
(2) probe階段:使用probe操作,掃描外關(guān)系,搜索匹配Hash表,完成連接處理。
給定一個多連接查詢的一棵左線性樹,它的數(shù)據(jù)操作相關(guān)圖就確定了這個多連接查詢的唯一的一個具有最高數(shù)據(jù)操作間并行性的查詢執(zhí)行計劃。
3.存儲空間限制問題的解決方法
基于左線性樹查詢優(yōu)化方法存在存儲空間限制問題。在build階段,除了第一個Hash表以外,所有其他Hash表都是由中間結(jié)果關(guān)系建立的。這些中間結(jié)果關(guān)系的大小很難預(yù)測。即使能夠預(yù)測這些中間結(jié)果的大小,在多用戶環(huán)境下優(yōu)化處理程序也很難預(yù)知查詢執(zhí)行計劃執(zhí)行時可用存儲空間的大小。如果我們有足夠的存儲空間,問題很簡單,只需為Hash表分配充分大的空間。如果我們只有有限的存儲空間,Hash表大小的確定則成為影響并行查詢執(zhí)行計劃性能的大問題。常用的解決方法有兩種:
第一種方法由Graefe和Ward提出。這種方法的基本思想是在優(yōu)化處理階段產(chǎn)生多個查詢執(zhí)行計劃,在運(yùn)行階段由運(yùn)行系統(tǒng)根據(jù)當(dāng)時的存儲空間大小選擇合適的查詢執(zhí)行計劃執(zhí)行。
第二種方法是運(yùn)行系統(tǒng)根據(jù)可用存儲空間大小的改變,動態(tài)地調(diào)整連接操作的Hash表的大小。通常,可以在每個連接操作的Hash表中記錄連接操作中間結(jié)果的大小,并使用這個信息動態(tài)改變該操作的下一個連接操作Hash表的大小。