第5章 關(guān)系查詢處理與優(yōu)化

1、編著編著嚴(yán)冬梅嚴(yán)冬梅 陳立君陳立君 張鎧張鎧 饒俊饒俊宋麗紅宋麗紅 李玉芝李玉芝 但志廣但志廣n本章主要介紹關(guān)系型數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化技術(shù)。本章主要介紹關(guān)系型數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化技術(shù)。查詢優(yōu)化技術(shù)在關(guān)系型數(shù)據(jù)庫中有著非常重要的查詢優(yōu)化技術(shù)在關(guān)系型數(shù)據(jù)庫中有著非常重要的作用，本章將使讀者初步了解作用，本章將使讀者初步了解RDBMSRDBMS查詢的基本查詢的基本處理過程，查詢優(yōu)化的基本概念和基本方法，并處理過程，查詢優(yōu)化的基本概念和基本方法，并給出了一些在實(shí)際應(yīng)用中的查詢優(yōu)化方法。給出了一些在實(shí)際應(yīng)用中的查詢優(yōu)化方法。5 5.1 .1 查詢優(yōu)化概述查詢優(yōu)化概述5 5.2 .2 查詢處理過程查詢處理

2、過程5 5. .3 3 查詢優(yōu)化方法查詢優(yōu)化方法5 5. .4 4 實(shí)際應(yīng)用中的查詢優(yōu)化實(shí)際應(yīng)用中的查詢優(yōu)化5 5. .5 5 本章小結(jié)本章小結(jié)5 5. .6 6 習(xí)題習(xí)題n查詢優(yōu)化對(duì)關(guān)系型系統(tǒng)來說既是挑戰(zhàn)又是機(jī)遇。所謂查詢優(yōu)化對(duì)關(guān)系型系統(tǒng)來說既是挑戰(zhàn)又是機(jī)遇。所謂挑戰(zhàn)是指關(guān)系系統(tǒng)為了達(dá)到用戶可接受的性能必須進(jìn)挑戰(zhàn)是指關(guān)系系統(tǒng)為了達(dá)到用戶可接受的性能必須進(jìn)行查詢優(yōu)化。由于關(guān)系表達(dá)式的語義級(jí)別很高，使得行查詢優(yōu)化。由于關(guān)系表達(dá)式的語義級(jí)別很高，使得關(guān)系系統(tǒng)能夠從關(guān)系表達(dá)式中分析查詢語義，提供了關(guān)系系統(tǒng)能夠從關(guān)系表達(dá)式中分析查詢語義，提供了查詢優(yōu)化的可行性。這為關(guān)系系統(tǒng)在性能上接近甚至查詢優(yōu)化的可

3、行性。這為關(guān)系系統(tǒng)在性能上接近甚至超過非關(guān)系系統(tǒng)提供了機(jī)遇。超過非關(guān)系系統(tǒng)提供了機(jī)遇。n本節(jié)主要討論查詢優(yōu)化問題的背景、查詢優(yōu)化的必要本節(jié)主要討論查詢優(yōu)化問題的背景、查詢優(yōu)化的必要性和在關(guān)系數(shù)據(jù)庫中進(jìn)行查詢的可行性。性和在關(guān)系數(shù)據(jù)庫中進(jìn)行查詢的可行性。n5 5.1.1 .1.1 查詢中遇到的問題查詢中遇到的問題n5 5.1.2 .1.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性n5 5.1.3 .1.3 查詢優(yōu)化的可行性查詢優(yōu)化的可行性n數(shù)據(jù)查詢是數(shù)據(jù)庫系統(tǒng)中的最基本、最常用和最數(shù)據(jù)查詢是數(shù)據(jù)庫系統(tǒng)中的最基本、最常用和最復(fù)雜的數(shù)據(jù)操作。復(fù)雜的數(shù)據(jù)操作。n查詢處理的代價(jià)通常取決于查詢過程對(duì)磁盤的訪查詢處

4、理的代價(jià)通常取決于查詢過程對(duì)磁盤的訪問，磁盤訪問速度相對(duì)于內(nèi)存速度要慢很多。問，磁盤訪問速度相對(duì)于內(nèi)存速度要慢很多。n如何從查詢的多個(gè)實(shí)現(xiàn)策略中進(jìn)行合理的選擇，如何從查詢的多個(gè)實(shí)現(xiàn)策略中進(jìn)行合理的選擇，這種選擇過程就是查詢處理過程的優(yōu)化，簡稱查這種選擇過程就是查詢處理過程的優(yōu)化，簡稱查詢優(yōu)化。詢優(yōu)化。n查詢優(yōu)化作為數(shù)據(jù)庫中的關(guān)鍵技術(shù)，對(duì)數(shù)據(jù)庫的查詢優(yōu)化作為數(shù)據(jù)庫中的關(guān)鍵技術(shù)，對(duì)數(shù)據(jù)庫的性能需求和實(shí)際應(yīng)用有著重要的意義。性能需求和實(shí)際應(yīng)用有著重要的意義。n查詢是數(shù)據(jù)庫的最主要功能，查詢優(yōu)化的基本途查詢是數(shù)據(jù)庫的最主要功能，查詢優(yōu)化的基本途徑可以分為用戶手動(dòng)處理和機(jī)器自動(dòng)處理兩種。徑可以分為用戶手

5、動(dòng)處理和機(jī)器自動(dòng)處理兩種。n關(guān)系型數(shù)據(jù)庫系統(tǒng)中，查詢優(yōu)化也是必須面對(duì)的關(guān)系型數(shù)據(jù)庫系統(tǒng)中，查詢優(yōu)化也是必須面對(duì)的挑戰(zhàn)。關(guān)系數(shù)據(jù)理論基于集合論，集合及其相關(guān)挑戰(zhàn)。關(guān)系數(shù)據(jù)理論基于集合論，集合及其相關(guān)理論構(gòu)成了整個(gè)關(guān)系數(shù)據(jù)庫領(lǐng)域中最重要的理論理論構(gòu)成了整個(gè)關(guān)系數(shù)據(jù)庫領(lǐng)域中最重要的理論基礎(chǔ)，這給關(guān)系數(shù)據(jù)查詢優(yōu)化處理在理論上提供基礎(chǔ)，這給關(guān)系數(shù)據(jù)查詢優(yōu)化處理在理論上提供了討論的可行性；關(guān)系查詢語言作為高級(jí)語言，了討論的可行性；關(guān)系查詢語言作為高級(jí)語言，具有較高層次的語義特性，為機(jī)器處理查詢優(yōu)化具有較高層次的語義特性，為機(jī)器處理查詢優(yōu)化問題在實(shí)踐上提供了可能性。問題在實(shí)踐上提供了可能性。nDBMSDBM

6、S處理查詢計(jì)劃的過程是這樣的：在做完查詢處理查詢計(jì)劃的過程是這樣的：在做完查詢語句的詞法、語法、語義檢查之后，將語句提交語句的詞法、語法、語義檢查之后，將語句提交給給DBMSDBMS的查詢優(yōu)化器，優(yōu)化器做完代數(shù)優(yōu)化和存的查詢優(yōu)化器，優(yōu)化器做完代數(shù)優(yōu)化和存取路徑優(yōu)化之后，由預(yù)編譯模塊對(duì)語句進(jìn)行處理取路徑優(yōu)化之后，由預(yù)編譯模塊對(duì)語句進(jìn)行處理并生成查詢規(guī)劃，然后在合適的時(shí)間提交給系統(tǒng)并生成查詢規(guī)劃，然后在合適的時(shí)間提交給系統(tǒng)處理執(zhí)行處理執(zhí)行, ,最后將執(zhí)行結(jié)果返回給用戶。最后將執(zhí)行結(jié)果返回給用戶。n下面通過一個(gè)例子來說明查詢優(yōu)化的必要性：下面通過一個(gè)例子來說明查詢優(yōu)化的必要性：n【例【例5.15.1

7、】在關(guān)系模式】在關(guān)系模式S S（學(xué)生），（學(xué)生），C C（課程），（課程），SCSC（選課）中，查詢修讀課程號(hào)為（選課）中，查詢修讀課程號(hào)為C5C5的所有學(xué)生的所有學(xué)生姓名。此查詢的姓名。此查詢的SQLSQL查詢語言的語句形式為：查詢語言的語句形式為：nSELECT S.Sname FROM S,SC WHERE S.Sno=SC.Sno SELECT S.Sname FROM S,SC WHERE S.Sno=SC.Sno AND SC.Cno=C5;AND SC.Cno=C5;n系統(tǒng)可以有多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查系統(tǒng)可以有多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查詢。例如可以寫出下面

8、詢。例如可以寫出下面3 3種表達(dá)式：種表達(dá)式：nQl = Sn(S.Sno = SC.SnoSC.Cno=C5(SQl = Sn(S.Sno = SC.SnoSC.Cno=C5(SSC)SC)；nQ2 = Sn(SC.Cno=C5(S SC)Q2 = Sn(SC.Cno=C5(S SC)）；）；nQ3 = Sn(S SC.Cno=C5(SC)Q3 = Sn(S SC.Cno=C5(SC)。n下面用簡單的方法來計(jì)算這下面用簡單的方法來計(jì)算這3 3種表達(dá)式的查詢所種表達(dá)式的查詢所需時(shí)間。在計(jì)算前先作如下的統(tǒng)一約定：需時(shí)間。在計(jì)算前先作如下的統(tǒng)一約定：n設(shè)設(shè)S S有有10001000個(gè)元組，個(gè)元組，

9、SCSC有有1000010000個(gè)元組，其中修讀個(gè)元組，其中修讀C5C5的元組數(shù)為的元組數(shù)為5050。n磁盤中每個(gè)物理塊能存放磁盤中每個(gè)物理塊能存放1010個(gè)個(gè)S S元組，或元組，或100100個(gè)個(gè)SCSC元元組。組。n內(nèi)存有內(nèi)存有6 6個(gè)塊的緩沖區(qū)，其中個(gè)塊的緩沖區(qū)，其中5 5塊可以存放塊可以存放S S元組，元組，1 1塊存放塊存放SCSC元組。元組。n讀寫一塊磁盤的時(shí)間為讀寫一塊磁盤的時(shí)間為1/201/20秒，即秒，即1 1秒讀寫秒讀寫2020個(gè)個(gè)磁盤塊。磁盤塊。n為了簡化起見，所有內(nèi)存操作所花的時(shí)間忽略不計(jì)。為了簡化起見，所有內(nèi)存操作所花的時(shí)間忽略不計(jì)。n計(jì)算計(jì)算Q Q1 1的查詢時(shí)間的

10、查詢時(shí)間n首先做笛卡爾乘積首先做笛卡爾乘積n將將S S與與SCSC的每個(gè)元組相連接，其方法為先讀入的每個(gè)元組相連接，其方法為先讀入S S中的中的5050個(gè)元組個(gè)元組(5(510)10)至至s s表中的內(nèi)存緩沖區(qū)，然后不斷地將表中的內(nèi)存緩沖區(qū)，然后不斷地將SCSC的元組按的元組按100100位一塊讀入后與位一塊讀入后與S S的元組相連接，直至的元組相連接，直至讀完所有讀完所有SCSC元組（共計(jì)元組（共計(jì)100100次）。這種操作內(nèi)連接滿次）。這種操作內(nèi)連接滿100100位后就寫中間文件一次。反復(fù)進(jìn)行這樣的操作，位后就寫中間文件一次。反復(fù)進(jìn)行這樣的操作，直至做完笛卡爾乘積，此時(shí)共讀取總塊數(shù)為：直至

11、做完笛卡爾乘積，此時(shí)共讀取總塊數(shù)為：n1000/10+1000/1000/10+1000/（1010* *5 5）+1000/100=100+20+1000/100=100+20* *100=2100100=2100塊塊n其中讀其中讀S S表表100100塊，讀塊，讀SCSC表表2020次，每次次，每次100100塊。由于每塊。由于每塊花費(fèi)時(shí)間塊花費(fèi)時(shí)間1/201/20秒，此時(shí)總共花費(fèi)時(shí)間秒，此時(shí)總共花費(fèi)時(shí)間10105 5秒。連接后秒。連接后的元組數(shù)為的元組數(shù)為10103 3x10 x104 4=10=107 7，設(shè)每塊（約）能裝，設(shè)每塊（約）能裝1010個(gè)元組，個(gè)元組，則寫入中間文件要花則寫

12、入中間文件要花10106 6/20=5/20=5l0l04 4S S。n計(jì)算計(jì)算Q Q1 1的查詢時(shí)間的查詢時(shí)間n其次做選擇操作其次做選擇操作n從中間文件中讀出連接后的元組，按選擇要求選取記從中間文件中讀出連接后的元組，按選擇要求選取記錄（此項(xiàng)為內(nèi)存操作，時(shí)間可忽略否計(jì)），此項(xiàng)操作錄（此項(xiàng)為內(nèi)存操作，時(shí)間可忽略否計(jì)），此項(xiàng)操作所需時(shí)間與寫入中間文件時(shí)間一樣，即所需時(shí)間與寫入中間文件時(shí)間一樣，即5 5l0l04 4S S。滿足。滿足條件的元組假設(shè)為條件的元組假設(shè)為5050個(gè)，均放在內(nèi)存。個(gè)，均放在內(nèi)存。n最后做投影操作最后做投影操作n第二項(xiàng)操作的結(jié)果滿足條件的元組數(shù)為第二項(xiàng)操作的結(jié)果滿足條件的元

13、組數(shù)為5050個(gè)，它們可個(gè)，它們可全部存放在內(nèi)存。對(duì)他們?cè)谌看娣旁趦?nèi)存。對(duì)他們?cè)赟 S上做投影操作，由于是上做投影操作，由于是在內(nèi)存中進(jìn)行，其時(shí)間可忽略不計(jì)。這樣在內(nèi)存中進(jìn)行，其時(shí)間可忽略不計(jì)。這樣Q Ql l的全部查的全部查詢時(shí)間約為詢時(shí)間約為10+210+2* *5 5* *l0l04 4l0l05 5S S。注意到一天為。注意到一天為86400s86400s，所以這個(gè)運(yùn)算需要超過一天的時(shí)間來完成。所以這個(gè)運(yùn)算需要超過一天的時(shí)間來完成。n計(jì)算計(jì)算Q Q2 2的查詢時(shí)間的查詢時(shí)間n計(jì)算自然連接：計(jì)算自然連接時(shí)讀取計(jì)算自然連接：計(jì)算自然連接時(shí)讀取S S與與SCSC表的方表的方式與式與Q Q1

14、 1一致，總讀取塊數(shù)為一致，總讀取塊數(shù)為21002100塊，花費(fèi)時(shí)間為塊，花費(fèi)時(shí)間為10105 5秒，但其連接結(jié)果塊數(shù)大為減少，總計(jì)秒，但其連接結(jié)果塊數(shù)大為減少，總計(jì)10104 4個(gè)，所花個(gè)，所花時(shí)間為時(shí)間為l0l04 4/10/20s=50s/10/20s=50s。僅為。僅為Q Ql l的千分之一。的千分之一。n做選擇操作：做選擇操作的時(shí)間為做選擇操作：做選擇操作的時(shí)間為50s50s。n做投影操作：與做投影操作：與Q Q1 1類似，其時(shí)間可忽略不計(jì)。類似，其時(shí)間可忽略不計(jì)。n這樣，這樣，Q Q2 2的全部查詢時(shí)間為的全部查詢時(shí)間為105+50+50=205s105+50+50=205sn計(jì)算

15、計(jì)算Q Q3 3的查詢時(shí)間的查詢時(shí)間n對(duì)對(duì)SCSC做選擇操作：對(duì)做選擇操作：對(duì)SCSC表做選擇操作需讀表做選擇操作需讀SCSC表一遍表一遍共計(jì)讀共計(jì)讀100100塊，花費(fèi)塊，花費(fèi)5s5s，因?yàn)闈M足條件的元件只有，因?yàn)闈M足條件的元件只有5050個(gè)，不必使用中間文件。個(gè)，不必使用中間文件。n做連接運(yùn)算：對(duì)做連接運(yùn)算：對(duì)S S選擇后的選擇后的SCSC左聯(lián)接運(yùn)算，由于選左聯(lián)接運(yùn)算，由于選擇后的擇后的SCSC已全部在內(nèi)存，因此全部操作時(shí)間為已全部在內(nèi)存，因此全部操作時(shí)間為S S讀讀入內(nèi)存的時(shí)間共入內(nèi)存的時(shí)間共100100塊，花費(fèi)時(shí)間為塊，花費(fèi)時(shí)間為5s5s。n作投影運(yùn)算：其時(shí)間忽略不計(jì)。作投影運(yùn)算：其時(shí)

16、間忽略不計(jì)。n這樣，這樣，Q Q3 3的全部查詢時(shí)間為：的全部查詢時(shí)間為：5+5=l0s5+5=l0sn從這從這3 3個(gè)計(jì)算時(shí)間可以看出，個(gè)計(jì)算時(shí)間可以看出，3 3種等價(jià)的查詢表達(dá)種等價(jià)的查詢表達(dá)式具有完全不同的處理時(shí)間，它們分別是式具有完全不同的處理時(shí)間，它們分別是l05sl05s、205s205s和和l0sl0s，其差距之大令人瞠目。，其差距之大令人瞠目。n由上例可知，對(duì)于關(guān)系代數(shù)等價(jià)的不同表達(dá)形式由上例可知，對(duì)于關(guān)系代數(shù)等價(jià)的不同表達(dá)形式而言，相應(yīng)的查詢效率有著而言，相應(yīng)的查詢效率有著“數(shù)量級(jí)數(shù)量級(jí)”上的重大上的重大差異。這是一個(gè)十分重要的事實(shí)，它說明了查詢差異。這是一個(gè)十分重要的事實(shí)，

17、它說明了查詢優(yōu)化的必要性，即合理選取查詢表達(dá)式可以獲取優(yōu)化的必要性，即合理選取查詢表達(dá)式可以獲取較高的查詢效率，這也是查詢優(yōu)化意義所在。較高的查詢效率，這也是查詢優(yōu)化意義所在。n關(guān)系數(shù)據(jù)系統(tǒng)查詢語句表示查詢操作基于集合運(yùn)算，關(guān)系數(shù)據(jù)系統(tǒng)查詢語句表示查詢操作基于集合運(yùn)算，我們稱之為關(guān)系代數(shù)。我們稱之為關(guān)系代數(shù)。n關(guān)系代數(shù)具有關(guān)系代數(shù)具有5 5種基本運(yùn)算，這些運(yùn)算間滿足一定的種基本運(yùn)算，這些運(yùn)算間滿足一定的運(yùn)算定律如結(jié)合律、交換律、分配率和串接率等，這運(yùn)算定律如結(jié)合律、交換律、分配率和串接率等，這就意味著不同的關(guān)系代數(shù)表達(dá)式可以得到同一結(jié)果，就意味著不同的關(guān)系代數(shù)表達(dá)式可以得到同一結(jié)果，因此用關(guān)系

18、代數(shù)語言進(jìn)行查詢需要進(jìn)行必要的優(yōu)化。因此用關(guān)系代數(shù)語言進(jìn)行查詢需要進(jìn)行必要的優(yōu)化。n關(guān)系查詢語句與普通語言相比有堅(jiān)實(shí)的理論支撐，用關(guān)系查詢語句與普通語言相比有堅(jiān)實(shí)的理論支撐，用戶只要提出戶只要提出“干什么干什么”，不必指出，不必指出“怎么干怎么干”，關(guān)系，關(guān)系查詢語言是一種高級(jí)語言，這給查詢優(yōu)化提供了可能查詢語言是一種高級(jí)語言，這給查詢優(yōu)化提供了可能性。性。n5 5. .2 2.1 .1 查詢分析查詢分析n5 5. .2 2.2 .2 查詢檢查查詢檢查n5 5. .2 2.3 .3 查詢優(yōu)化查詢優(yōu)化n5 5. .2 2. .4 4 查詢執(zhí)行查詢執(zhí)行n在關(guān)系型數(shù)據(jù)庫中，查詢處理過程通?？梢苑譃樵?/p>

19、關(guān)系型數(shù)據(jù)庫中，查詢處理過程通?？梢苑譃樗膫€(gè)階段：查詢分析、查詢處理、查詢優(yōu)化和查四個(gè)階段：查詢分析、查詢處理、查詢優(yōu)化和查詢執(zhí)行，如圖詢執(zhí)行，如圖5-15-1所示。所示。圖圖5-1 關(guān)關(guān)系數(shù)據(jù)庫查詢處理步驟系數(shù)據(jù)庫查詢處理步驟n查詢分析要對(duì)查詢語句進(jìn)行掃描、詞法分析和語查詢分析要對(duì)查詢語句進(jìn)行掃描、詞法分析和語法分析。從查詢語句中識(shí)別出語言符號(hào)，如法分析。從查詢語句中識(shí)別出語言符號(hào)，如SQLSQL關(guān)鍵字、屬性和關(guān)系名稱等，并進(jìn)行語法檢查和關(guān)鍵字、屬性和關(guān)系名稱等，并進(jìn)行語法檢查和分析，檢查語句是否符合分析，檢查語句是否符合SQLSQL語法規(guī)則。語法規(guī)則。n查詢檢查首先根據(jù)數(shù)據(jù)字典對(duì)合法的查詢

20、語句進(jìn)行語查詢檢查首先根據(jù)數(shù)據(jù)字典對(duì)合法的查詢語句進(jìn)行語義檢查，檢查語句中識(shí)別出的語言符號(hào)，在數(shù)據(jù)庫中義檢查，檢查語句中識(shí)別出的語言符號(hào)，在數(shù)據(jù)庫中是否存在，是否有效。還要根據(jù)數(shù)據(jù)字典中的用戶權(quán)是否存在，是否有效。還要根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對(duì)用戶進(jìn)行檢查，如果用戶不具限和完整性約束定義對(duì)用戶進(jìn)行檢查，如果用戶不具備相應(yīng)的訪問權(quán)限或者違反了完整性約束原則，就拒備相應(yīng)的訪問權(quán)限或者違反了完整性約束原則，就拒絕執(zhí)行該查詢。檢查通過后，把查詢語句轉(zhuǎn)化成為等絕執(zhí)行該查詢。檢查通過后，把查詢語句轉(zhuǎn)化成為等價(jià)的關(guān)系代數(shù)表達(dá)式。在價(jià)的關(guān)系代數(shù)表達(dá)式。在RDBMSRDBMS中一般都用查詢樹（中

21、一般都用查詢樹（q query treeuery tree），也稱為語法分析樹（），也稱為語法分析樹（syntax treesyntax tree），），來作為查詢內(nèi)部表示形式。來作為查詢內(nèi)部表示形式。n查詢優(yōu)化就是選擇一個(gè)高效的查詢處理策略，查詢優(yōu)化就是選擇一個(gè)高效的查詢處理策略，DBMSDBMS會(huì)調(diào)用系統(tǒng)的優(yōu)化處理器制定一個(gè)執(zhí)行策略，會(huì)調(diào)用系統(tǒng)的優(yōu)化處理器制定一個(gè)執(zhí)行策略，由此產(chǎn)生一個(gè)查詢計(jì)劃，其中包括了如何防偽數(shù)由此產(chǎn)生一個(gè)查詢計(jì)劃，其中包括了如何防偽數(shù)據(jù)庫文件和如何存儲(chǔ)中間結(jié)果等。據(jù)庫文件和如何存儲(chǔ)中間結(jié)果等。n查詢優(yōu)化器是關(guān)系數(shù)據(jù)庫的巨大優(yōu)勢(shì)所在，它是查詢優(yōu)化器是關(guān)系數(shù)據(jù)庫的巨大優(yōu)勢(shì)

22、所在，它是用戶不必考慮如何較好地表達(dá)查詢以獲得較高的用戶不必考慮如何較好地表達(dá)查詢以獲得較高的效率，而且系統(tǒng)自動(dòng)優(yōu)化存取路徑可以比用戶的效率，而且系統(tǒng)自動(dòng)優(yōu)化存取路徑可以比用戶的程序做的更好。程序做的更好。n查詢優(yōu)化有多種方法。代數(shù)優(yōu)化：指關(guān)系代數(shù)表查詢優(yōu)化有多種方法。代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化，即根據(jù)某些啟發(fā)式規(guī)則，改變代數(shù)達(dá)式的優(yōu)化，即根據(jù)某些啟發(fā)式規(guī)則，改變代數(shù)表達(dá)式中的次序和組合，使查詢執(zhí)行的更高效，表達(dá)式中的次序和組合，使查詢執(zhí)行的更高效，例如例如“先選擇、投影和后連接先選擇、投影和后連接”等就可完成優(yōu)化，等就可完成優(yōu)化，所以也成為規(guī)則優(yōu)化；物理優(yōu)化：存取路徑和底所以也成為規(guī)則

23、優(yōu)化；物理優(yōu)化：存取路徑和底層操作算法的選擇，可以是基于規(guī)則的、基于代層操作算法的選擇，可以是基于規(guī)則的、基于代價(jià)的也可以是基于語義的。實(shí)際優(yōu)化過程中為了價(jià)的也可以是基于語義的。實(shí)際優(yōu)化過程中為了達(dá)到更好的優(yōu)化技術(shù)往往都綜合使用這些優(yōu)化技達(dá)到更好的優(yōu)化技術(shù)往往都綜合使用這些優(yōu)化技術(shù)。術(shù)。n依據(jù)查詢優(yōu)化器得到的查詢計(jì)劃，系統(tǒng)的代碼生依據(jù)查詢優(yōu)化器得到的查詢計(jì)劃，系統(tǒng)的代碼生成器產(chǎn)生出這個(gè)計(jì)劃的執(zhí)行代碼。成器產(chǎn)生出這個(gè)計(jì)劃的執(zhí)行代碼。n5 5. .3 3.1 .1 代數(shù)優(yōu)化代數(shù)優(yōu)化n5 5. .3 3.2 .2 物理優(yōu)化物理優(yōu)化n前面已經(jīng)介紹過，查詢語句經(jīng)過查詢分析、查詢前面已經(jīng)介紹過，查詢語句經(jīng)

24、過查詢分析、查詢檢查后變?yōu)椴樵儤?，它是代?shù)表達(dá)式的內(nèi)部表示檢查后變?yōu)椴樵儤洌谴鷶?shù)表達(dá)式的內(nèi)部表示形式。代數(shù)優(yōu)化主要是依據(jù)關(guān)系代數(shù)表達(dá)式的等形式。代數(shù)優(yōu)化主要是依據(jù)關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則所做的優(yōu)化。價(jià)變換規(guī)則所做的優(yōu)化。n代數(shù)優(yōu)化策略是通過對(duì)代數(shù)關(guān)系表達(dá)式的等價(jià)變代數(shù)優(yōu)化策略是通過對(duì)代數(shù)關(guān)系表達(dá)式的等價(jià)變換來提高效率的。關(guān)系代數(shù)表達(dá)式的等價(jià)是指兩換來提高效率的。關(guān)系代數(shù)表達(dá)式的等價(jià)是指兩個(gè)關(guān)系代數(shù)表達(dá)式用同一個(gè)關(guān)系帶入之后得到的個(gè)關(guān)系代數(shù)表達(dá)式用同一個(gè)關(guān)系帶入之后得到的結(jié)果相同，即兩個(gè)相應(yīng)的關(guān)系具有相同的屬性結(jié)結(jié)果相同，即兩個(gè)相應(yīng)的關(guān)系具有相同的屬性結(jié)合和相同的元組集合。合和相同的元組

25、集合。n關(guān)系代數(shù)表達(dá)式變換規(guī)則關(guān)系代數(shù)表達(dá)式變換規(guī)則n常用的代數(shù)表達(dá)式的等價(jià)變換規(guī)則主要有以下幾類，常用的代數(shù)表達(dá)式的等價(jià)變換規(guī)則主要有以下幾類，證明從略。證明從略。n連接、笛卡爾積的交換律連接、笛卡爾積的交換律n 設(shè)設(shè)E1E1和和E2E2是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn) F是連接運(yùn)算條件，是連接運(yùn)算條件，則下列等價(jià)公式成立：則下列等價(jià)公式成立：n笛卡爾積的交換律：笛卡爾積的交換律：E1E1E2 E2E2 E2E1E1n自然連接的交換律：自然連接的交換律：E1 E2 E2 E1E1 E2 E2 E1n條件連接的交換律：條件連接的交換律：E1 E2 E2 E1E1 E2 E2 E1FFn連

26、接、笛卡爾積的結(jié)合律連接、笛卡爾積的結(jié)合律n設(shè)設(shè)E1E1、 E2 E2和和E3E3是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)1F1和和F2F2是連接是連接運(yùn)算條件，則下列等價(jià)公式成立：運(yùn)算條件，則下列等價(jià)公式成立：n笛卡爾積的結(jié)合律：笛卡爾積的結(jié)合律：(E1(E1E2)E2)E3 E1E3 E1(E2(E2E3)E3)n自然連接的結(jié)合律：自然連接的結(jié)合律：(E(E1 1 E E2 2) E) E3 3 E E1 1 (E (E2 2 E E3 3) )n條件連接的結(jié)合律：條件連接的結(jié)合律：(E(E1 1 E E2 2) E) E3 3 E E1 1 (E (E2 2 E E3 3) )F1F1F2

27、F2n選擇、投影的串接定律選擇、投影的串接定律n選擇運(yùn)算串接定律選擇運(yùn)算串接定律n設(shè)設(shè)E E是一個(gè)關(guān)系代數(shù)表達(dá)式，是一個(gè)關(guān)系代數(shù)表達(dá)式，F(xiàn) F1 1和和F F2 2是選擇運(yùn)算條件，是選擇運(yùn)算條件，則下列等價(jià)公式成立：則下列等價(jià)公式成立：n選擇運(yùn)算順序可交換定律：選擇運(yùn)算順序可交換定律：F F1 1(F F2 2(E) (E) F F2 2(F F1 1(E)(E)n合取條件分解定律：合取條件分解定律：F1F1(F2F2(E) (E) F2F1F2F1(E)(E)n投影運(yùn)算串接定律投影運(yùn)算串接定律n設(shè)設(shè)E E是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，A Ai i(i=1,2,n)(i=1,2,n)，B

28、 Bj j(j=1,2,m)(j=1,2,m)是是E E中的某些屬性名，且中的某些屬性名，且AA1 1,A,A2 2,A,An n 是是BB1 1,B,B2 2,B,Bm m 的子集，則下列等價(jià)的子集，則下列等價(jià)公式成立：公式成立：nA1,A2,AnA1,A2,An(B1,B2,BmB1,B2,Bm(E) (E) A1,A2,AnA1,A2,An(E)(E)n選擇與笛卡爾積、選擇與投影的交換律選擇與笛卡爾積、選擇與投影的交換律n選擇與笛卡爾積的交換律選擇與笛卡爾積的交換律n設(shè)設(shè)E E1 1、E E2 2是關(guān)系代數(shù)表達(dá)式，如果是關(guān)系代數(shù)表達(dá)式，如果F F中涉及的屬性都中涉及的屬性都是是E E1

29、1中的屬性，則下列等價(jià)公式成立：中的屬性，則下列等價(jià)公式成立：nF F(E(E1 1E E2 2) ) F F(E(E1 1) )E E2 2n如果如果F = FF = F1 1FF2 2，并且，并且F F1 1只涉及只涉及E E1 1中的屬性，中的屬性，F(xiàn) F2 2只涉及只涉及E E2 2中的屬性，則有上述規(guī)則可推出：中的屬性，則有上述規(guī)則可推出：nF F(E(E1 1E E2 2) ) F1F1(E(E1 1) )F2F2(E(E2 2) )n若若F F1 1只涉及只涉及E E1 1中的屬性，中的屬性，F(xiàn) F2 2涉及涉及E E1 1和和E E2 2兩者的屬性，則兩者的屬性，則有：有：nF

30、 F(E(E1 1E E2 2) ) F2F2(F1F1(E(E1 1) )E E2 2) )n這樣可以使部分選擇運(yùn)算在笛卡爾積前先做。這樣可以使部分選擇運(yùn)算在笛卡爾積前先做。n選擇與投影的交換律選擇與投影的交換律n設(shè)設(shè)E E是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，A Ai i(i=1,2,n)(i=1,2,n)、B Bj j(j=1,2,m)(j=1,2,m)是是E E的屬性，的屬性，A Ai i與與B Bj j不相交，不相交，F(xiàn) F是選擇條是選擇條件。如果件。如果F F只涉及只涉及AA1 1, A, A2 2, A, An n 則下列等價(jià)公式成立：則下列等價(jià)公式成立：F F(A1,A2,A1,

31、A2,An,An(E) (E) A1,A2,A1,A2,An,An(F F(E)(E)n如果如果F F中有不屬于中有不屬于 A A1 1, A, A2 2, A, An n 的屬性的屬性 B B1 1, B , B 2 2, , B Bm m 則有更一般的規(guī)則：則有更一般的規(guī)則：nA1,A2,A1,A2,An,An(F F(E) (E) A1,A2,A1,A2,An,An(F F(A1,A2,A1,A2,An, ,An, B1,B2,B1,B2,Bm,Bm(E)(E)n選擇與并、選擇與差運(yùn)算、選擇與自然連接的分選擇與并、選擇與差運(yùn)算、選擇與自然連接的分配率配率n選擇與并的分配率選擇與并的分配率

32、n設(shè)設(shè)E E1 1和和E E2 2是兩個(gè)關(guān)系代數(shù)表達(dá)式，并且是兩個(gè)關(guān)系代數(shù)表達(dá)式，并且E E1 1和和E E2 2具有相具有相同的屬性名，同的屬性名，F(xiàn) F是選擇條件，則下列等式成立：是選擇條件，則下列等式成立：nF F(E(E1 1EE2 2) ) F F(E(E1 1)F F(E(E2 2) )n選擇與差運(yùn)算的分配率選擇與差運(yùn)算的分配率n設(shè)設(shè)E E1 1和和E E2 2是兩個(gè)關(guān)系代數(shù)表達(dá)式，并且是兩個(gè)關(guān)系代數(shù)表達(dá)式，并且E E1 1和和E E2 2具有相同具有相同的屬性名，的屬性名，F(xiàn) F是選擇條件，則下列等式成立：是選擇條件，則下列等式成立：nF F(E(E1 1-E-E2 2) ) F

33、 F(E(E1 1)-)-F F(E(E2 2) )n選擇與自然連接的分配率選擇與自然連接的分配率n 設(shè)設(shè)E E1 1和和E E2 2是兩個(gè)關(guān)系代數(shù)表達(dá)式，并且是兩個(gè)關(guān)系代數(shù)表達(dá)式，并且E E1 1和和E E2 2具有具有相同的屬性名，相同的屬性名，F(xiàn) F是選擇條件，是選擇條件，F(xiàn) F只涉及只涉及E E1 1與與E E2 2的公的公共屬性，則下列等式成立：共屬性，則下列等式成立：n F F(E(E1 1 E E2 2) ) F F(E(E1 1) ) F F(E(E2 2) )n投影與笛卡爾積、投影與并的分配率投影與笛卡爾積、投影與并的分配率n投影與笛卡爾積的分配率投影與笛卡爾積的分配率n設(shè)設(shè)

34、E E1 1和和E E2 2是兩個(gè)關(guān)系代數(shù)表達(dá)式，是兩個(gè)關(guān)系代數(shù)表達(dá)式，A Ai i(i=1,2,n)(i=1,2,n)是是E E1 1的屬性，的屬性，B Bj j(j=1,2,m)(j=1,2,m)是是E E2 2的屬性，則下列等價(jià)公的屬性，則下列等價(jià)公式成立：式成立：nA1,A2,A1,A2,An, B1,B2,An, B1,B2,Bm ,Bm (E(E1 1E E2 2) ) A1,A2,A1,A2,An,An(E(E1 1) ) B1,B2,B1,B2,Bm,Bm(E(E2 2) )n投影與并的分配率投影與并的分配率n設(shè)設(shè)E E1 1和和E E2 2是兩個(gè)關(guān)系代數(shù)表達(dá)式，是兩個(gè)關(guān)系代數(shù)

35、表達(dá)式，A Ai i(i=1,2,n)(i=1,2,n)是是E E1 1、E E2 2的公共屬性，則下列等價(jià)公式成立：的公共屬性，則下列等價(jià)公式成立：nA1,A2,A1,A2,An ,An (E(E1 1EE2 2) ) A1,A2,A1,A2,An,An(E(E1 1)A1,A2,A1,A2,An,An (E(E2 2) )n查詢樹的啟發(fā)式規(guī)則，本節(jié)討論的是應(yīng)用啟發(fā)式規(guī)查詢樹的啟發(fā)式規(guī)則，本節(jié)討論的是應(yīng)用啟發(fā)式規(guī)則的代數(shù)優(yōu)化。通過啟發(fā)式規(guī)則對(duì)關(guān)系表達(dá)式的查則的代數(shù)優(yōu)化。通過啟發(fā)式規(guī)則對(duì)關(guān)系表達(dá)式的查詢樹表達(dá)形式進(jìn)行優(yōu)化。典型的啟發(fā)式規(guī)則有：詢樹表達(dá)形式進(jìn)行優(yōu)化。典型的啟發(fā)式規(guī)則有：n選擇操作

36、優(yōu)先原則選擇操作優(yōu)先原則n投影操作優(yōu)先原則投影操作優(yōu)先原則n笛卡爾積合并規(guī)則笛卡爾積合并規(guī)則n提取公共表達(dá)式規(guī)則提取公共表達(dá)式規(guī)則n下面給出遵循這些啟發(fā)式規(guī)則，應(yīng)用等價(jià)變換公式來下面給出遵循這些啟發(fā)式規(guī)則，應(yīng)用等價(jià)變換公式來優(yōu)化關(guān)系表達(dá)式的算法。優(yōu)化關(guān)系表達(dá)式的算法。n算法：關(guān)系表達(dá)式的優(yōu)化。算法：關(guān)系表達(dá)式的優(yōu)化。n輸入：一個(gè)關(guān)系表達(dá)式的查詢樹。輸入：一個(gè)關(guān)系表達(dá)式的查詢樹。n輸出：優(yōu)化的查詢樹。輸出：優(yōu)化的查詢樹。n方法：方法： n利用等價(jià)變換規(guī)則把形如利用等價(jià)變換規(guī)則把形如F1F2FnF1F2Fn(E)(E)變換為變換為F1F1(F2F2(FnFn(E)(E)。n對(duì)每一個(gè)選擇，利用等價(jià)變

37、化規(guī)則，盡量把它移到樹對(duì)每一個(gè)選擇，利用等價(jià)變化規(guī)則，盡量把它移到樹的葉端。的葉端。n對(duì)每一個(gè)投影利用等價(jià)變換規(guī)則，盡可能把它移向樹對(duì)每一個(gè)投影利用等價(jià)變換規(guī)則，盡可能把它移向樹的葉端。的葉端。n利用等價(jià)變換規(guī)則，把選擇和投影的串接合并成單利用等價(jià)變換規(guī)則，把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。n把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。n【例【例5.25.2】下面給出一個(gè)】下面給出一個(gè)SQLSQL語句的代數(shù)優(yōu)化示例。語句的代數(shù)優(yōu)化示例。n求選修了求選修了2 2號(hào)課程的學(xué)生姓名。用號(hào)課程的學(xué)生姓名。用SQ

38、LSQL表達(dá)：表達(dá)：nSELECT S.Snane FROM S,SC WHERE S.Sno = SC.Sno AND SELECT S.Snane FROM S,SC WHERE S.Sno = SC.Sno AND SC.Cno=02;SC.Cno=02;n把把SQLSQL語句轉(zhuǎn)換成查詢樹，如圖語句轉(zhuǎn)換成查詢樹，如圖5-25-2所示。為了使用關(guān)系代數(shù)所示。為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，不妨假設(shè)內(nèi)部表示是關(guān)系代數(shù)語法樹，則表達(dá)式的優(yōu)化法，不妨假設(shè)內(nèi)部表示是關(guān)系代數(shù)語法樹，則上面的查詢樹如圖上面的查詢樹如圖5-35-3所示。所示。n對(duì)查詢樹進(jìn)行優(yōu)化。對(duì)查詢樹進(jìn)行優(yōu)化。n利用轉(zhuǎn)換規(guī)則把選擇利

39、用轉(zhuǎn)換規(guī)則把選擇SC.CnoSC.Cno=02=02移到葉端，圖移到葉端，圖5-35-3查詢查詢樹便轉(zhuǎn)換成圖樹便轉(zhuǎn)換成圖5-45-4優(yōu)化的查詢樹。優(yōu)化的查詢樹。n代數(shù)優(yōu)化改變了查詢語句中操作的次序和組合方式，代數(shù)優(yōu)化改變了查詢語句中操作的次序和組合方式，但不涉及底層存取路徑。而物理優(yōu)化主要是選擇合理但不涉及底層存取路徑。而物理優(yōu)化主要是選擇合理高效的操作算法或存取路徑，得到優(yōu)化的查詢計(jì)劃，高效的操作算法或存取路徑，得到優(yōu)化的查詢計(jì)劃，來達(dá)到查詢優(yōu)化的目的。選擇的方式可以是：來達(dá)到查詢優(yōu)化的目的。選擇的方式可以是：n基于啟發(fā)式規(guī)則的優(yōu)化基于啟發(fā)式規(guī)則的優(yōu)化n啟發(fā)式規(guī)則是指那些在大多數(shù)情況下都適用

40、，但是不啟發(fā)式規(guī)則是指那些在大多數(shù)情況下都適用，但是不是在每種情況下都適用的規(guī)則。是在每種情況下都適用的規(guī)則。n基于代價(jià)估計(jì)的優(yōu)化基于代價(jià)估計(jì)的優(yōu)化n由優(yōu)化器估算每種不同執(zhí)行策略的代價(jià)，并選出具有由優(yōu)化器估算每種不同執(zhí)行策略的代價(jià)，并選出具有最小代價(jià)的執(zhí)行計(jì)劃。最小代價(jià)的執(zhí)行計(jì)劃。n兩者相結(jié)合的優(yōu)化方法兩者相結(jié)合的優(yōu)化方法n查詢優(yōu)化器常會(huì)把這兩種技術(shù)結(jié)合在一起使用。查詢優(yōu)化器常會(huì)把這兩種技術(shù)結(jié)合在一起使用。因?yàn)槟軋?zhí)行的策略有很多，要窮盡所有的查詢策因?yàn)槟軋?zhí)行的策略有很多，要窮盡所有的查詢策略進(jìn)行代價(jià)估算往往是不可行的，會(huì)使查詢優(yōu)化略進(jìn)行代價(jià)估算往往是不可行的，會(huì)使查詢優(yōu)化本身付出代價(jià)大于獲得的

41、益處。為此常常先使用本身付出代價(jià)大于獲得的益處。為此常常先使用啟發(fā)式規(guī)則，選取若干較優(yōu)的候選方案以減少代啟發(fā)式規(guī)則，選取若干較優(yōu)的候選方案以減少代價(jià)評(píng)估的工作量；然后分別計(jì)算各方案的執(zhí)行代價(jià)評(píng)估的工作量；然后分別計(jì)算各方案的執(zhí)行代價(jià)，從中較快地選擇出最終的優(yōu)化方案。價(jià)，從中較快地選擇出最終的優(yōu)化方案。n基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化n選擇操作的啟發(fā)式規(guī)則選擇操作的啟發(fā)式規(guī)則n對(duì)小關(guān)系，使用全表掃描，即使列上有索引。對(duì)小關(guān)系，使用全表掃描，即使列上有索引。n對(duì)大關(guān)系：對(duì)于選擇條件是對(duì)大關(guān)系：對(duì)于選擇條件是“主碼主碼= =值值”的查詢，查的查詢，查詢結(jié)果最多是一個(gè)

42、元組，可以選擇主碼索引。一般的詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引。一般的RDBMSRDBMS會(huì)自動(dòng)創(chuàng)建主碼索引。會(huì)自動(dòng)創(chuàng)建主碼索引。n對(duì)于選擇條件是對(duì)于選擇條件是“非主屬性非主屬性= =值值”的查詢，并且選擇的查詢，并且選擇列上有索引，則要估算查詢結(jié)果元組的數(shù)目，如果比列上有索引，則要估算查詢結(jié)果元組的數(shù)目，如果比例較小例較小(10%)(10%)可以使用索引掃描方法，否則應(yīng)該使用可以使用索引掃描方法，否則應(yīng)該使用全表掃描。全表掃描。n對(duì)于選擇條件是屬性上的非等值查詢或者范圍查詢對(duì)于選擇條件是屬性上的非等值查詢或者范圍查詢時(shí)，并且選擇列上有索引，同樣也需要估算查詢結(jié)時(shí)，并且選擇列上有索引，同

43、樣也需要估算查詢結(jié)果的元組數(shù)目，如果比例較小果的元組數(shù)目，如果比例較小(10%)(10%)則可以使用索則可以使用索引掃描方法，否則還是應(yīng)該使用全表掃描。引掃描方法，否則還是應(yīng)該使用全表掃描。n對(duì)于用對(duì)于用ANDAND連接的合取選擇條件，如果有涉及這些連接的合取選擇條件，如果有涉及這些屬性的組合索引，則優(yōu)先采用組合索引掃描方法。屬性的組合索引，則優(yōu)先采用組合索引掃描方法。n對(duì)于用對(duì)于用OROR連接的析取選擇條件，一般使用全表順序連接的析取選擇條件，一般使用全表順序掃描。掃描。n連接操作的啟發(fā)式規(guī)則連接操作的啟發(fā)式規(guī)則n如果兩個(gè)表都已經(jīng)按照連接屬性排序，則選用排序如果兩個(gè)表都已經(jīng)按照連接屬性排序，

44、則選用排序- -合合并方法。并方法。n如果一個(gè)表在連接屬性上有索引，則可以選用索引連接如果一個(gè)表在連接屬性上有索引，則可以選用索引連接方法。方法。n如果上面兩條規(guī)則都不適用，其中一個(gè)表較小，則可選如果上面兩條規(guī)則都不適用，其中一個(gè)表較小，則可選用用Hash joinHash join方法。方法。n最后可以選用嵌套循環(huán)方法，并選用其中較小的表，確最后可以選用嵌套循環(huán)方法，并選用其中較小的表，確切地說是占用的塊數(shù)較少的表，作為外層循環(huán)的表。切地說是占用的塊數(shù)較少的表，作為外層循環(huán)的表。n基于代價(jià)估計(jì)的優(yōu)化基于代價(jià)估計(jì)的優(yōu)化n啟發(fā)式優(yōu)化規(guī)則是定性選擇，比較粗糙，但是實(shí)現(xiàn)啟發(fā)式優(yōu)化規(guī)則是定性選擇，比較

45、粗糙，但是實(shí)現(xiàn)簡單而且優(yōu)化本身代價(jià)較小，適合解釋執(zhí)行系統(tǒng)。簡單而且優(yōu)化本身代價(jià)較小，適合解釋執(zhí)行系統(tǒng)。因?yàn)榻忉寛?zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷因?yàn)榻忉寛?zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之中。而在編譯執(zhí)行的系統(tǒng)中，一次編譯優(yōu)化多次之中。而在編譯執(zhí)行的系統(tǒng)中，一次編譯優(yōu)化多次執(zhí)行，查詢優(yōu)化和查詢執(zhí)行是分開的，因此，可以執(zhí)行，查詢優(yōu)化和查詢執(zhí)行是分開的，因此，可以采用更精細(xì)更復(fù)雜的機(jī)遇代價(jià)的優(yōu)化方法。采用更精細(xì)更復(fù)雜的機(jī)遇代價(jià)的優(yōu)化方法。n信息統(tǒng)計(jì)信息統(tǒng)計(jì)n基于代價(jià)的優(yōu)化方法就是要計(jì)算各種操作算法的執(zhí)行代基于代價(jià)的優(yōu)化方法就是要計(jì)算各種操作算法的執(zhí)行代價(jià)，而代價(jià)的計(jì)算算法與數(shù)據(jù)庫的狀態(tài)密切相關(guān)

46、。為此價(jià)，而代價(jià)的計(jì)算算法與數(shù)據(jù)庫的狀態(tài)密切相關(guān)。為此在數(shù)據(jù)字典中存儲(chǔ)了優(yōu)化器需要的統(tǒng)計(jì)信息在數(shù)據(jù)字典中存儲(chǔ)了優(yōu)化器需要的統(tǒng)計(jì)信息( database ( database statistics)statistics)，這些信息主要有：，這些信息主要有：n基本表：元組總數(shù)基本表：元組總數(shù)(N)(N)、元組長度、元組長度(1)(1)、占用的塊數(shù)、占用的塊數(shù)(B)(B)、占用的溢出塊數(shù)占用的溢出塊數(shù)(BO)(BO)n基本表的列：該列不同值的個(gè)數(shù)基本表的列：該列不同值的個(gè)數(shù)(m)(m)、選擇率、選擇率(f)(f)、該、該列最大值、最小值，該列上是否已經(jīng)建立了索引，及列最大值、最小值，該列上是否已經(jīng)建

47、立了索引，及索引的種類索引的種類n索引：例如索引：例如B+B+樹索引，該索引的層數(shù)樹索引，該索引的層數(shù)(L)(L)、不同索引值、不同索引值的個(gè)數(shù)、索引的選擇基數(shù)的個(gè)數(shù)、索引的選擇基數(shù)S S（有（有S S個(gè)元組具有某個(gè)索引個(gè)元組具有某個(gè)索引值）、索引的葉結(jié)點(diǎn)數(shù)值）、索引的葉結(jié)點(diǎn)數(shù)(Y)(Y)。n除了上面的這些信息，還有一些必要的其他信息。除了上面的這些信息，還有一些必要的其他信息。n估算代價(jià)：在上面這些信息的基礎(chǔ)上查詢優(yōu)化器估算代價(jià)：在上面這些信息的基礎(chǔ)上查詢優(yōu)化器可以采取一些算法來估計(jì)執(zhí)行查詢的代價(jià)。下面可以采取一些算法來估計(jì)執(zhí)行查詢的代價(jià)。下面給出一些常用的操作算法的執(zhí)行代價(jià)估算方法：給出一

48、些常用的操作算法的執(zhí)行代價(jià)估算方法：n全表掃描算法代價(jià)的估算全表掃描算法代價(jià)的估算n索引掃描算法代價(jià)的估算索引掃描算法代價(jià)的估算n嵌套循環(huán)連接算法代價(jià)的估算嵌套循環(huán)連接算法代價(jià)的估算n排序排序- -合并連接算法代價(jià)的估算合并連接算法代價(jià)的估算n全表掃描算法代價(jià)的估算全表掃描算法代價(jià)的估算n如果基本表大小為如果基本表大小為B B塊，則全表掃描算法的代價(jià)塊，則全表掃描算法的代價(jià)cost=Bcost=B；n如果選擇條件是如果選擇條件是“碼碼= =值值”，那么平均搜索代價(jià)，那么平均搜索代價(jià)cost= B/2cost= B/2。n索引掃描算法代價(jià)的估算索引掃描算法代價(jià)的估算n如果選擇條件是如果選擇條件是

49、“碼碼= =值值”，則采用該表的主索引，若，則采用該表的主索引，若為為B+B+樹，層數(shù)為樹，層數(shù)為L L，需要存取，需要存取B+B+樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)L L塊，再加上基本表中該元組所在的那一塊，所以塊，再加上基本表中該元組所在的那一塊，所以cost=L+1cost=L+1。n如果選擇條件涉及非碼屬性，若為如果選擇條件涉及非碼屬性，若為B+B+樹索引，選擇條件樹索引，選擇條件是相等比較，是相等比較，S S是索引的選擇基數(shù)（有是索引的選擇基數(shù)（有S S個(gè)元組滿足條個(gè)元組滿足條件）。因?yàn)闈M足條件的元組可能會(huì)保存在不同的塊上，件）。因?yàn)闈M足條件的元組可能會(huì)保存在不同的塊上，所以（

50、最壞的情況）所以（最壞的情況）cost=L+Scost=L+S。n如果比較條件是非等值操作，假設(shè)有一半的元組滿足條如果比較條件是非等值操作，假設(shè)有一半的元組滿足條件，那么就要存取一半的葉結(jié)點(diǎn)，并通過索引訪問一半件，那么就要存取一半的葉結(jié)點(diǎn)，并通過索引訪問一半的表存儲(chǔ)塊。所以的表存儲(chǔ)塊。所以cost=L+Y/2+B/2cost=L+Y/2+B/2。如果可以獲得更準(zhǔn)。如果可以獲得更準(zhǔn)確的選擇基數(shù)，可以進(jìn)一步修正確的選擇基數(shù)，可以進(jìn)一步修正Y/2Y/2與與B/2B/2。n嵌套循環(huán)連接算法代價(jià)的估算嵌套循環(huán)連接算法代價(jià)的估算n嵌套循環(huán)連接算法的代價(jià)為嵌套循環(huán)連接算法的代價(jià)為cost=Br+Br Bs/

51、cost=Br+Br Bs/（K-K-1 1）。如果需要把連接結(jié)果寫回磁盤，則）。如果需要把連接結(jié)果寫回磁盤，則cost= Br+ cost= Br+ Br Bs/Br Bs/（K-lK-l）+ +（FrsFrs* *NrNr* *NsNs）/Mrs/Mrs。其中。其中FrsFrs為連為連接選擇性接選擇性(join selectivity)(join selectivity)，表示連接結(jié)果元組，表示連接結(jié)果元組數(shù)的比例，數(shù)的比例，MrsMrs是存放連接結(jié)果的塊因子，表示每是存放連接結(jié)果的塊因子，表示每塊中可以存放的結(jié)果元組數(shù)目。塊中可以存放的結(jié)果元組數(shù)目。n排序排序- -合并連接算法代價(jià)的估算

52、合并連接算法代價(jià)的估算n如果連接表已經(jīng)按照連接屬性排好序，則如果連接表已經(jīng)按照連接屬性排好序，則cost= cost= Br+ Bs+Br+ Bs+（Frs Frs * *NrNr* *NsNs）/Mrs/Mrs。n如果必須對(duì)文件排序，那么還需要在代價(jià)函數(shù)中加如果必須對(duì)文件排序，那么還需要在代價(jià)函數(shù)中加上排序的代價(jià)。對(duì)于包含上排序的代價(jià)。對(duì)于包含B B個(gè)塊的文件排序的代價(jià)個(gè)塊的文件排序的代價(jià)大約是（大約是（2 2* *B B）+(2+(2* *B B* *loglog2 2B)B)。n上面僅僅列出了少數(shù)操作算法的代價(jià)估算示例。上面僅僅列出了少數(shù)操作算法的代價(jià)估算示例。在實(shí)際的在實(shí)際的RDBMS

53、RDBMS中代價(jià)估算公式要多得多，也復(fù)中代價(jià)估算公式要多得多，也復(fù)雜得多。雜得多。n5 5. .4 4.1 .1 基于索引的優(yōu)化基于索引的優(yōu)化n5 5. .4 4.2 .2 查詢語句的優(yōu)化查詢語句的優(yōu)化n一般來說，建立和刪除索引的工作都是由數(shù)據(jù)庫管理員一般來說，建立和刪除索引的工作都是由數(shù)據(jù)庫管理員DBADBA或表的主人或表的主人(owner)(owner)，即建立表的主人，負(fù)責(zé)完成。，即建立表的主人，負(fù)責(zé)完成。系統(tǒng)在存取數(shù)據(jù)時(shí)會(huì)自動(dòng)選擇合適的索引作為存取路徑，系統(tǒng)在存取數(shù)據(jù)時(shí)會(huì)自動(dòng)選擇合適的索引作為存取路徑，用戶不必顯式地選擇索引。用戶不必顯式地選擇索引。n使用索引的一個(gè)主要目的是避免全表掃

54、描，減少磁盤使用索引的一個(gè)主要目的是避免全表掃描，減少磁盤I/OI/O，加快數(shù)據(jù)庫查詢的速度。但是，索引的建立降低，加快數(shù)據(jù)庫查詢的速度。但是，索引的建立降低了數(shù)據(jù)更新的速度，因?yàn)閿?shù)據(jù)不僅要增加到表中，而且了數(shù)據(jù)更新的速度，因?yàn)閿?shù)據(jù)不僅要增加到表中，而且還要增加到索引中。另外，索引還需要額外的磁盤空間還要增加到索引中。另外，索引還需要額外的磁盤空間和維護(hù)開銷。所以在設(shè)計(jì)和使用索引時(shí)應(yīng)仔細(xì)考慮實(shí)際和維護(hù)開銷。所以在設(shè)計(jì)和使用索引時(shí)應(yīng)仔細(xì)考慮實(shí)際應(yīng)用中的修改和查詢的頻率，權(quán)衡建立索引的利弊，并應(yīng)用中的修改和查詢的頻率，權(quán)衡建立索引的利弊，并應(yīng)遵循以下原則：應(yīng)遵循以下原則：n值得建索引并且用的上值得建索引并且用的上n先裝數(shù)據(jù)，后建索引。先