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

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

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

    基于右線性樹查詢優(yōu)化方法 : 采用右線性樹的模型來表示查詢執(zhí)行計(jì)劃的一種優(yōu)化方法。
1.基于右線性樹(RDT)的優(yōu)化查詢
n+1級(jí)右線性樹(right-deep tree)是一個(gè)滿足下列條件的查詢樹:
(1)具有2n+1個(gè)結(jié)點(diǎn)。
(2)每個(gè)內(nèi)結(jié)點(diǎn)有且僅有兩個(gè)子結(jié)點(diǎn)。
(3)每個(gè)內(nèi)結(jié)點(diǎn)(n-1級(jí)內(nèi)結(jié)點(diǎn)除外)的右子結(jié)點(diǎn)是一個(gè)連接操作,左子結(jié)點(diǎn)是一個(gè)關(guān)系。
(4) n-1級(jí)內(nèi)結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)皆為關(guān)系。簡(jiǎn)稱右線性樹為RDT樹。
設(shè)Q是一個(gè)具有n個(gè)連接操作的多連接查詢?？梢詮腝構(gòu)造出n!個(gè)等價(jià)的右線性樹。如果可以使用m種算法實(shí)現(xiàn)一個(gè)連接操作,則對(duì)于每個(gè)右線性樹存在mⁿ種執(zhí)行Q的策略或計(jì)劃。于是,得到mⁿn!種按照右線性樹方式執(zhí)行Q的查詢執(zhí)行計(jì)劃。這些查詢執(zhí)行計(jì)劃構(gòu)成了Q的基于右線性樹的查詢執(zhí)行計(jì)劃空間?；谟揖€性樹的查詢優(yōu)化方法就是要從這個(gè)查詢執(zhí)行計(jì)劃空間中選擇具有最小或較小時(shí)間復(fù)雜性的計(jì)劃,完成Q的執(zhí)行。
給定一個(gè)多連接查詢的一棵右線性樹,它的數(shù)據(jù)操作相關(guān)圖確定了多連接查詢的唯一一個(gè)具有最高并行性的執(zhí)行計(jì)劃(簡(jiǎn)稱查詢執(zhí)行計(jì)劃)。
2.右線性樹查詢執(zhí)行計(jì)劃的復(fù)雜性模型。
通常,右線性樹查詢采用復(fù)雜性模型實(shí)現(xiàn),該模型是選擇優(yōu)化右線性樹查詢執(zhí)行計(jì)劃的關(guān)鍵。RDT樹復(fù)雜性模型包括兩部分。第一部分是build、probe和scan操作的復(fù)雜性(與左線性樹相同);第二部分是整個(gè)查詢執(zhí)行計(jì)劃的復(fù)雜性(由build、probe和scan操作的復(fù)雜性計(jì)算而得到,其中包括工作量和并行執(zhí)行時(shí)間)。后者是整個(gè)右線性樹查詢執(zhí)行計(jì)劃的復(fù)雜性的測(cè)度。設(shè)給定一個(gè)多連接查詢Q,則以下為基于右線性樹的查詢優(yōu)化算法的主要實(shí)現(xiàn)步驟:
(1)使用枚舉方法搜索Q的RDT樹空間,選擇具有最小響應(yīng)時(shí)間的優(yōu)化RDT樹。
(2)從選定的優(yōu)化RDT樹產(chǎn)生數(shù)據(jù)操作相關(guān)圖。
(3) 由數(shù)據(jù)操作相關(guān)圖產(chǎn)生具有最高數(shù)據(jù)操作間并行性的RDT樹查詢執(zhí)行計(jì)劃。
(4)按照優(yōu)化RDT樹各結(jié)點(diǎn)的工作量的比例為每個(gè)結(jié)點(diǎn)分配處理機(jī)。
(5)調(diào)度處理機(jī)執(zhí)行查詢執(zhí)行計(jì)劃。
3.存儲(chǔ)空間限制問題的解決方法
基于右線性樹查詢優(yōu)化算法也存在主存儲(chǔ)器空間的限制問題。其解決方法有:
(1)靜態(tài)右線性樹調(diào)度方法: 這種方法把右線性樹分成多個(gè)不相交的可執(zhí)行片段,使得每個(gè)片段的存儲(chǔ)要求不超過可用的存儲(chǔ)空間。使用右線性樹和數(shù)據(jù)操作相關(guān)圖方法為每個(gè)片段確定具有最高數(shù)據(jù)操作間并行性的執(zhí)行計(jì)劃。然后順序地執(zhí)行各個(gè)片段。這種方法需要把每個(gè)片段的執(zhí)行結(jié)果暫存到磁盤上,作為下一個(gè)片段執(zhí)行的一個(gè)輸入關(guān)系。
(2)HYBRID調(diào)度方法:該方法的基本思想是在build階段,每個(gè)連接關(guān)系被分成兩部分,一部分進(jìn)入內(nèi)存,建立Hash表,另一部分以后處理;在probe階段,每個(gè)連接操作的結(jié)果也被分成兩部分,一部分直接用來進(jìn)行下一個(gè)連接操作的probe處理,另一部分以后處理。
(3) 自底向上的動(dòng)態(tài)調(diào)度方法: 與LDT樹解決方法類似。