基于代價的查詢優(yōu)化(數(shù)據(jù)庫)

時間：2022-12-27 22:30:01 | 來源：信息時代

時間：2022-12-27 22:30:01 來源：信息時代

    基于代價的查詢優(yōu)化 : 物理查詢優(yōu)化的一種重要方法。對關(guān)系查詢進行物理查詢優(yōu)化的主要任務(wù),是為邏輯查詢計劃選擇高效合理的操作算法或存取路徑,求得優(yōu)化的查詢計劃,達到查詢優(yōu)化的目標。物理優(yōu)化手段包括基于代價、基于規(guī)則、基于語義以及同時基于代價和規(guī)則的幾種策略。其中基于代價的查詢優(yōu)化是根據(jù)數(shù)據(jù)字典中記載的各種統(tǒng)計信息,估算各種執(zhí)行策略的代價,并從中選擇一個系統(tǒng)認為是“較好”的執(zhí)行策略。
鑒于數(shù)據(jù)庫應(yīng)用是I/O密集型操作,I/O開銷遠遠大于CPU開銷,因此,估算執(zhí)行策略的代價時可以用所執(zhí)行的磁盤I/O數(shù)近似,而忽略CPU時間。同時,由于我們僅僅需要比較兩個不同策略的相對代價,因此,可以簡單地用一個操作需要輸入和輸出的關(guān)系大小來近似操作本身的代價。
基本關(guān)系的大小可以直接從統(tǒng)計信息中獲得,中間關(guān)系的大小需要根據(jù)統(tǒng)計信息進行估算,每個操作符都有常用的估算公式。
估算中間結(jié)果需要的統(tǒng)計信息包括:
T(R): 關(guān)系R的元組數(shù)Card(R)。
S(R):關(guān)系R每條元組的字節(jié)數(shù)Length(R.A)。
B(R):關(guān)系R占用的數(shù)據(jù)塊數(shù)Page(R)。
V(R,A):關(guān)系R中屬性A的不同取值個數(shù)Dom(R.A)。
Omax(R.A): 屬性A在其值域范圍內(nèi)的最大值。
Omin(R.A): 屬性A在其值域范圍內(nèi)的最小值。
這些統(tǒng)計信息一般被保存在數(shù)據(jù)字典、數(shù)據(jù)結(jié)構(gòu)、相應(yīng)屬性的B樹索引或統(tǒng)計直方圖之中,由DBMS獲取和維護。其中統(tǒng)計直方圖可以比較方便地表達一個關(guān)系表的屬性分布情況。最常見的統(tǒng)計直方圖包括等高直方圖和等寬直方圖。
假設(shè)屬性A的值域被劃分為如下n個區(qū)間:(A₀,A₁,…,A_n-1)＝([a₀,a₁),[a₁,a₂₎,…,[a_n-1,a_n]),a₀和a_n為最大值和最小值,每個區(qū)間中的元組數(shù)被記為T(Range(R.A_i))＝T([a_i,a_i+1)),i=0,1,…,n-1。每個區(qū)間中屬性A的基數(shù)被記為T(Odom(R.A_i))。等寬直方圖的定義為:T(Odom(R.A_i))＝T(Odom(R.A_j))0≤i,j≤n-1,i≠j。即一個屬性的等寬直方圖是把該屬性的取值范圍分成相等大小的若干個區(qū)間,分別統(tǒng)計取值落在各個區(qū)間的元組數(shù)的多少,如圖1所示。
等高直方圖的定義為:T(Range(R.A_i))＝T(Range(R.A_j)),0≤i,j≤n-1,i≠j。即一個屬性的等高直方圖是調(diào)整區(qū)間的分界,使得落入每個區(qū)間的元組數(shù)相等,如圖2所示。由于等高直方圖可以比較好地解決數(shù)據(jù)偏斜(Data Skew)問題,因此在大多數(shù)系統(tǒng)中都采用這種直方圖。

圖1 等寬直方圖

圖2 等高直方圖

依據(jù)這些統(tǒng)計信息估算中間結(jié)果大小的方法如下:
(1)投影操作符: 令U=π_a,b(R)。如果投影操作符不去除投影中的重復(fù)結(jié)果,其大小是可計算的,即有T(U)=T(R),S(U)為屬性A和屬性B的長度之和。如果去除投影中的重復(fù)結(jié)果,則T(U)為V(R,a)*V(R,b)。
(2)選擇操作符: 選擇操作的結(jié)果大小估計公式為:T(δ_p(R))=Selectivity_p(R)*T(R)。其中,Selectivity_p(R)是謂詞p在R上的選擇率。
(3)笛卡兒積操作符:R₁和R₂的笛卡兒積可以按如下公式估算:T(R₁×R₂₎＝T(R₁)×T(R₂₎;S(R₁×R₂₎＝S(R₁₎+S(R₂₎。
(4)非等值連接操作符:對于,可以用笛卡兒積加選擇操作符來估算,即T(U)=T(σ_R1.a>R2.b(R₁×R₂₎₎。
(5) 自然連接操作符和等值連接操作符: 自然連接結(jié)果大小的估算基于兩個關(guān)于值集的簡化假設(shè): 針對連接屬性的值集包含假設(shè)和針對非連接屬性的值集保持假設(shè)。
對于R(X,Y)⋈S(Y,Z), 值集包含假設(shè)是指, 如果V(R,Y)≤V(S,Y),則R中連接屬性Y的每個取值都將出現(xiàn)在S的連接屬性Y值中;如果V(R,Y)≥V(S,Y),則S中連接屬性Y的每個取值都將出現(xiàn)在R的連接屬性Y值中。值集保持假設(shè)是指,非連接屬性X和Z的每個取值都會出現(xiàn)在連接結(jié)果集中,即V(R⋈S,X)=V(R,X),V(R⋈S,Y)=V(R,Y)。
基于這兩個假設(shè),R和S的連接結(jié)果集大小可以用下面公式估算:
令U=R(X,Y)⋈S(Y,Z), 則:

該估算公式可以類推到多屬性自然連接上。假設(shè)R與S有任意多個公共屬性y₁,y₂,…,y_n,則:

該估算公式也可以類推到多表連接上。令U=R₁⋈R₂⋈…⋈R_n,T(U)的估算規(guī)則是, 從每個關(guān)系中元組數(shù)的積出發(fā),然后對于至少出現(xiàn)兩次的屬性A,除以除了V(R_i,A)中最小值之外的所有值。
等值連接結(jié)果的估算與自然連接類似,區(qū)別僅僅在于S的估算上,R和S等值連接結(jié)果的元組大小等于R和S的元組大小之和。
(6) 并操作符: 對于U=R∪S,T(U)的上限是R和S兩個關(guān)系的元組數(shù)之和,下限是R和S中最大元組數(shù),因此,T(U)通常用平均值來估算,即:

T(U)=((T(R)+T(S)+max(T(R),T(S)))/2;
S(U)=S(R)=S(S)。

(7)交操作符: 對于U=R∩S,T(U)的上限是R和S兩個關(guān)系中最小元組數(shù),下限是0,因此T(U)通常用平均值來估算,即:

T(U)=(0+min(T(R)),T(S)))/2=min(T(R),T(S))/2;
S(U)=S(R)=S(S)。

(8)差操作符: 對于U=R-S:

T(U)=(T(R)+(T(R)-T(S)))/2=T(R)-T(S)/2;
S(U)=S(R)=S(S)。

有了單個操作符的操作結(jié)果大小估算公式后,就可以估算不同操作算法的代價和內(nèi)存需求了。代價估算方法就是根據(jù)計算相應(yīng)操作算法從磁盤上讀入關(guān)系的大小加上寫出到磁盤上的關(guān)系大小,這些關(guān)系可能是基本表,也可能是上述操作符的輸出結(jié)果。例如,對于投影和選擇操作,它們只需要掃描一次關(guān)系,因此其代價為B(R),最小內(nèi)存需求為1塊。嵌套循環(huán)連接算法的代價為B(R)B(S)/M,最小內(nèi)存需求M為2塊。一趟散列連接的代價為B(R)+B(S),最小內(nèi)存需求為min(B(R),B(S))+1。兩趟散列連接算法的代價為3*(B(R)+B(S)),最小內(nèi)存需求為

不同操作算法的代價估算和內(nèi)存需求估算是基于代價優(yōu)化方法選取優(yōu)化物理計劃的依據(jù),選取優(yōu)化物理計劃的具體方法包括窮舉法、啟發(fā)式方法、分支界定計劃枚舉方法、爬山法、動態(tài)規(guī)劃方法、Selinger風(fēng)格優(yōu)化等方法。其中除窮舉法遍歷了全部搜索空間,其他方法都可以看作是運用啟發(fā)式規(guī)則縮減了搜索空間。
窮舉法是對所有可能的選擇(連接的次序、操作符的物理實現(xiàn)等)加以組合,對每個可能的物理計劃估算代價,選擇具有最小代價的一個計劃。其優(yōu)點是針對給定的邏輯查詢計劃,可以為之找到最優(yōu)的物理計劃,缺點是代價過于高昂。
啟發(fā)式方法的基本思想是: 用啟發(fā)式規(guī)則裁剪一部分可能不太好的物理計劃。其優(yōu)點是物理優(yōu)化的搜索空間顯著減小,缺點是可能丟失最優(yōu)計劃。
分支界定計劃枚舉方法的基本思想是: 首先通過啟發(fā)式規(guī)則為整個邏輯查詢計劃找到一個好的物理計劃,令其代價為C; 然后當考慮子計劃的其他計劃時,除去那些代價大于C的計劃;如果代價C較小,則終止搜索并獲得目前為止最優(yōu)的計劃。以該計劃作為最終執(zhí)行計劃,以避免搜索更好的計劃所花費的代價大于所獲得的收益。
爬山法的基本思想是: 依據(jù)啟發(fā)式規(guī)則選定一個的查詢計劃,以此作為開始,通過對計劃作小的修改,找到具有較低代價的“鄰近”計劃,當小的修改已經(jīng)找不到更好的計劃時,搜索結(jié)束。
動態(tài)規(guī)劃方法的基本思想是: 采用自底向上的方式進行搜索,對于每個子表達式,僅保留當前最小代價的計劃。
Selinger風(fēng)格優(yōu)化是動態(tài)規(guī)劃方法的改進。它不僅記錄了每個子表達式的最小代價的計劃,而且也記錄了那些雖然具有較高代價,但按此計劃執(zhí)行,所生成中間結(jié)果集的元組順序?qū)Ρ磉_式樹中較高層操作符很有用的計劃。