連接操作的優(yōu)化(數(shù)據(jù)庫)

時(shí)間：2022-10-30 08:30:01 | 來源：信息時(shí)代

時(shí)間：2022-10-30 08:30:01 來源：信息時(shí)代

    連接操作的優(yōu)化 : 對(duì)兩表或多表的各種連接操作符進(jìn)行優(yōu)化,選擇較優(yōu)的查詢計(jì)劃。
連接操作是從兩個(gè)關(guān)系的笛卡兒積中選取屬性間滿足一定條件的元組。在SQL查詢中,表現(xiàn)為FROM子句涉及多個(gè)表。連接操作包括等值連接、自然連接、非等值連接、自身連接、外連接、復(fù)合條件連接等。笛卡兒積也可以看作是一種特殊的連接操作,即無條件的連接操作。連接操作通常是數(shù)據(jù)庫查詢中開銷最大、最費(fèi)時(shí)的操作,因而也是查詢優(yōu)化的重點(diǎn)操作符。
連接操作的優(yōu)化主要包括確定多表連接操作的連接順序(包括內(nèi)表外表選擇)和每個(gè)連接操作符的操作算法。
連接順序的常用表達(dá)方式是連接樹。通用的連接樹形式是濃密樹(bushy tree)。濃密樹是一個(gè)滿足下列條件的樹:
(1)葉結(jié)點(diǎn)表示關(guān)系。
(2)每個(gè)內(nèi)結(jié)點(diǎn)既表示一個(gè)數(shù)據(jù)操作,也表示操作的結(jié)果關(guān)系,其子結(jié)點(diǎn)所對(duì)應(yīng)的關(guān)系是該內(nèi)結(jié)點(diǎn)的操作關(guān)系
濃密樹可以表達(dá)任意數(shù)目關(guān)系之間的任意連接順序。圖1就是一個(gè)五表連接的濃密樹示例,它表達(dá)的連接順序是:R₁與R₂連接,R₄與R₅連接,R₃與R₄、R₅的連接結(jié)果連接,R₁、R₂的連接結(jié)果與R₃、R₄、 R₅的連接結(jié)果連接。 即(R₁⋈R₂₎⋈(R₃⋈(R₄⋈R₅₎₎。

圖1 濃密樹示例

這些連接操作中, 分別由R₁、R₄、R₃、R₁⋈R₂做外關(guān)系。當(dāng)這五個(gè)表采用其他連接操作順序時(shí),會(huì)形成不同的濃密樹形式。
選擇連接順序的常用優(yōu)化方法包括動(dòng)態(tài)規(guī)劃算法和貪心算法。
動(dòng)態(tài)規(guī)劃算法的基本思想是,采用自底向上搜索,對(duì)于一組相同關(guān)系的連接操作,僅保留其中最小代價(jià)的計(jì)劃。連接操作的代價(jià)可以簡(jiǎn)單地以中間關(guān)系的大小表示(這時(shí)優(yōu)化算法就是選擇連接順序),也可以是所選用的連接算法的代價(jià)(這時(shí)算法就是選擇連接順序以及連接算法)。例如,對(duì)于一個(gè)四表連接查詢R⋈S⋈T⋈U,如果我們只允許左深連接樹,利用動(dòng)態(tài)規(guī)劃方法優(yōu)化連接操作的過程是:
(1)考慮單個(gè)關(guān)系,列出它的大小。不妨假設(shè)B(R)<B(S)<B(T)<B(U),則Cost(scan R)<Cost(scan S)<Cost(scan T)<Cost(scan U)。
(2)考慮兩個(gè)關(guān)系的連接,列出兩個(gè)關(guān)系的所有可能的連接組合,共種,即12種,它們是R⋈S, S⋈R, R⋈T, T⋈R, R⋈U, U⋈R, S⋈T,T⋈S, S⋈U, U⋈S, T⋈U, U⋈T。每一個(gè)關(guān)系對(duì),只保留以較小代價(jià)的關(guān)系作左變?cè)倪B接對(duì),例如,對(duì)于R⋈S與S⋈R,因?yàn)镃ost(scan R)<Cost(scan S),于是保留R⋈S。 這樣一共保留6個(gè)連接對(duì)(R⋈S,R⋈T, R⋈U, S⋈T, S⋈U,T⋈U), 分別計(jì)算其連接代價(jià)。 不妨假設(shè)Cost(T⋈U)<Cost(S⋈T)<Cost(R⋈S)<Cost(R⋈U)<Cost(R⋈T)<Cost(S⋈U)。
(3)考慮三個(gè)關(guān)系的連接,列出三個(gè)關(guān)系的所有可能的連接組合,共種, 即24種。對(duì)于每一個(gè)三關(guān)系組,由于只允許左深連接樹,因此它一定是兩個(gè)關(guān)系連接后再和第三個(gè)關(guān)系連接。我們只保留以最小代價(jià)的連接關(guān)系對(duì)作左變?cè)挠?jì)劃,計(jì)算其連接代價(jià)及結(jié)果關(guān)系的大小。例如,對(duì)于R、S、T的連接, 由第(2)步知道,Cost(S⋈T)<Cost(R⋈S)<Cost(R⋈T), 因此, 只保留以S⋈T作為左變?cè)倪B接計(jì)劃, 即(S⋈T)⋈R。這樣一共保留了4個(gè)連接子計(jì)劃。
(4)考慮四個(gè)關(guān)系的連接,由于只允許左深連接樹,因此,它一定是三個(gè)關(guān)系連接后再和第四個(gè)關(guān)系連接,我們?nèi)匀恢豢紤]以最小代價(jià)的連接計(jì)劃作左變?cè)?利用第(3)步的結(jié)果,最后計(jì)算保留下來的連接計(jì)劃的代價(jià)(共4種),從中選出最小代價(jià)的計(jì)劃就是最終的連接順序。
雖然動(dòng)態(tài)規(guī)劃算法對(duì)于一組相同關(guān)系的連接操作,僅保留了其中最小代價(jià)的計(jì)劃,以此縮減了優(yōu)化連接操作的搜索空間,但當(dāng)參與連接的關(guān)系數(shù)目較大時(shí)(比如超過了5～6個(gè)),其效率依然會(huì)較低。一個(gè)更高效的優(yōu)化連接操作的算法是貪心算法,它在優(yōu)化過程中采用連接順序試探來縮減搜索空間。貪心算法一次為連接的順序作一個(gè)決定,一旦做出決定便不再重新考慮。
貪心算法以連接代價(jià)估算值最小的關(guān)系對(duì)開始,這對(duì)關(guān)系的連接成為當(dāng)前樹。然后遞歸地在所有還沒有加入當(dāng)前樹的關(guān)系中,尋找與當(dāng)前樹進(jìn)行連接時(shí)代價(jià)最小的關(guān)系及相應(yīng)連接算法。以舊的當(dāng)前樹作為左變?cè)?被選中的關(guān)系作為右變?cè)獊硇纬尚碌漠?dāng)前樹。
除此之外,連接操作優(yōu)化時(shí),查詢優(yōu)化器還經(jīng)常用啟發(fā)式規(guī)則來選擇連接順序和連接算法,以進(jìn)一步提高優(yōu)化效率。常用的啟發(fā)式規(guī)則有:
(1)如果參與連接的一個(gè)關(guān)系在連接屬性上有索引,則采用索引連接,且該關(guān)系作為內(nèi)表。
(2)如果參與連接的一個(gè)關(guān)系是按連接屬性排好序的,則采用排序-合并連接比用散列連接好,但不一定比索引連接好。
(3)計(jì)算三個(gè)或更多的關(guān)系的并或交時(shí),先對(duì)最小關(guān)系進(jìn)行組合。