啟發(fā)式優(yōu)化(數(shù)據(jù)庫)
時間：2022-11-06 14:30:01 | 來源：信息時代
時間：2022-11-06 14:30:01 來源：信息時代
啟發(fā)式優(yōu)化 : 啟發(fā)式優(yōu)化是指查詢優(yōu)化器利用啟發(fā)式規(guī)則來選取查詢計劃,這種方法可以有效縮減查詢計劃的搜索空間,提高查詢優(yōu)化的效率。
基于代價的查詢優(yōu)化的一個缺點是,尋找優(yōu)化的查詢方案的搜索空間過于龐大,使得優(yōu)化本身的代價過高。查詢計劃樹中所有操作符的可能組合形式構(gòu)成了查詢計劃樹的空間,隨著操作符數(shù)目的增長,這個空間擴張的速度非?？臁Ｒ砸粋€四表連接的查詢?yōu)槔?其可能的樹形狀有5種,如圖1所示。對于每一種樹形狀,四個關系又可以有4!即24種排列次序,于是,四表連接的查詢樹共有5×24即120種形式。
圖1 四表連接的五種連接樹形狀
n個關系的連接操作,其樹形狀的數(shù)目T(n)可以如下遞歸計算出來:
T(1)=1,
例如T(1)=1,T(2)=1,T(3)=2,T(4)=5,T(5)=14,T(6)=42,等等。對于n個關系,每種樹形可以有n!種方法來分配關系。因此當允許所有樹型時,查詢計劃樹的可能數(shù)目為T(n)×n!。對于每個操作符結(jié)點,又可能有m種算法可供選擇,因此可以得到n
m×T(n)×n! 種查詢執(zhí)行計劃。為每一種查詢執(zhí)行計劃計算其代價,并從中選出最小代價的計劃,當n比較大時,其代價將是非常大的。
啟發(fā)式優(yōu)化就是查詢優(yōu)化器利用啟發(fā)式規(guī)則來減少優(yōu)化本身的代價,即查詢優(yōu)化過程中,運用啟發(fā)式規(guī)則選取若干較優(yōu)的候選方案,只計算這些候選方案的執(zhí)行代價,而不必比較全部可能的方案,從而縮減了查詢優(yōu)化的搜索空間,減少了生成備選方案的開銷和估算代價的工作量,較快地選出最終的優(yōu)化方案。當然這樣做的前提是可能丟失最佳執(zhí)行計劃,因為這些啟發(fā)式規(guī)則只是在通常情況下的經(jīng)驗規(guī)則,但并不能適用于所有情況。
啟發(fā)式優(yōu)化的策略可以分為兩大類,第一類是限制查詢計劃樹形狀的規(guī)則,第二類是選取操作算法的啟發(fā)式規(guī)則。
限制查詢計劃樹形狀的規(guī)則,就是將查詢計劃樹限制為某一類固定形狀,例如對于連接樹,DBMS通常只考慮左深連接樹,即圖1(a)形狀的樹。這樣,對于n個關系,如果只有一種左深連接樹的形狀,當每個操作符m種算法時,搜索空間由n
m×T(n)×n! 種可能的查詢執(zhí)行計劃降低為n
mn! 種可能的計劃。
選取操作算法常用的啟發(fā)式規(guī)則包括:
(1)對于邏輯計劃中的σ
A=c(R),如果R在屬性A上有索引,則執(zhí)行一個索引掃描以獲得R中A屬性值等于c的元組。
(2)對于邏輯計劃中的σ
A=cand…(R),如果R在屬性A上有索引,則先執(zhí)行一個索引掃描以獲得R中A值等于c的元組,然后再對其作進一步篩選(用物理操作符Filter表示)。
(3)如果參與連接的一個關系在連接屬性上有索引,則采用索引連接,且該關系作內(nèi)表。
(4)如果參與連接的一個關系是按連接屬性排好序的,則采用排序-合并連接比用散列連接好,但不一定比索引連接好。
(5)計算三個或更多的關系的并或交時,先對最小關系進行組合。
顯然,使用了限制查詢計劃樹形狀的規(guī)則和選取操作算法的啟發(fā)式規(guī)則后,查詢優(yōu)化器的代價可以明顯降低。這就是啟發(fā)式優(yōu)化的價值所在。
在線咨詢