1、編著編著嚴冬梅嚴冬梅 陳立君陳立君 張鎧張鎧 饒俊饒俊宋麗紅宋麗紅 李玉芝李玉芝 但志廣但志廣n本章主要介紹關系型數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化技術。本章主要介紹關系型數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化技術。查詢優(yōu)化技術在關系型數(shù)據(jù)庫中有著非常重要的查詢優(yōu)化技術在關系型數(shù)據(jù)庫中有著非常重要的作用，本章將使讀者初步了解作用，本章將使讀者初步了解RDBMSRDBMS查詢的基本查詢的基本處理過程，查詢優(yōu)化的基本概念和基本方法，并處理過程，查詢優(yōu)化的基本概念和基本方法，并給出了一些在實際應用中的查詢優(yōu)化方法。給出了一些在實際應用中的查詢優(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 實際應用中的查詢優(yōu)化實際應用中的查詢優(yōu)化5 5. .5 5 本章小結(jié)本章小結(jié)5 5. .6 6 習題習題n查詢優(yōu)化對關系型系統(tǒng)來說既是挑戰(zhàn)又是機遇。所謂查詢優(yōu)化對關系型系統(tǒng)來說既是挑戰(zhàn)又是機遇。所謂挑戰(zhàn)是指關系系統(tǒng)為了達到用戶可接受的性能必須進挑戰(zhàn)是指關系系統(tǒng)為了達到用戶可接受的性能必須進行查詢優(yōu)化。由于關系表達式的語義級別很高，使得行查詢優(yōu)化。由于關系表達式的語義級別很高，使得關系系統(tǒng)能夠從關系表達式中分析查詢語義，提供了關系系統(tǒng)能夠從關系表達式中分析查詢語義，提供了查詢優(yōu)化的可行性。這為關系系統(tǒng)在性能上接近甚至查詢優(yōu)化的可

3、行性。這為關系系統(tǒng)在性能上接近甚至超過非關系系統(tǒng)提供了機遇。超過非關系系統(tǒng)提供了機遇。n本節(jié)主要討論查詢優(yōu)化問題的背景、查詢優(yōu)化的必要本節(jié)主要討論查詢優(yōu)化問題的背景、查詢優(yōu)化的必要性和在關系數(shù)據(jù)庫中進行查詢的可行性。性和在關系數(shù)據(jù)庫中進行查詢的可行性。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)中的最基本、最常用和最復雜的數(shù)據(jù)操作。復雜的數(shù)據(jù)操作。n查詢處理的代價通常取決于查詢過程對磁盤的訪查詢處

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

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

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

7、】在關系模式】在關系模式S S（學生），（學生），C C（課程），（課程），SCSC（選課）中，查詢修讀課程號為（選課）中，查詢修讀課程號為C5C5的所有學生的所有學生姓名。此查詢的姓名。此查詢的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)可以有多種等價的關系代數(shù)表達式來完成這一查系統(tǒng)可以有多種等價的關系代數(shù)表達式來完成這一查詢。例如可以寫出下面

8、詢。例如可以寫出下面3 3種表達式：種表達式：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下面用簡單的方法來計算這下面用簡單的方法來計算這3 3種表達式的查詢所種表達式的查詢所需時間。在計算前先作如下的統(tǒng)一約定：需時間。在計算前先作如下的統(tǒng)一約定：n設設S S有有10001000個元組，個元組，

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

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

11、做完笛卡爾乘積，此時共讀取總塊數(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塊。由于每塊。由于每塊花費時間塊花費時間1/201/20秒，此時總共花費時間秒，此時總共花費時間10105 5秒。連接后秒。連接后的元組數(shù)為的元組數(shù)為10103 3x10 x104 4=10=107 7，設每塊（約）能裝，設每塊（約）能裝1010個元組，個元組，則寫入中間文件要花則寫

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

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

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

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

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

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

18、代數(shù)語言進行查詢需要進行必要的優(yōu)化。因此用關系代數(shù)語言進行查詢需要進行必要的優(yōu)化。n關系查詢語句與普通語言相比有堅實的理論支撐，用關系查詢語句與普通語言相比有堅實的理論支撐，用戶只要提出戶只要提出“干什么干什么”，不必指出，不必指出“怎么干怎么干”，關系，關系查詢語言是一種高級語言，這給查詢優(yōu)化提供了可能查詢語言是一種高級語言，這給查詢優(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在關系型數(shù)據(jù)庫中，查詢處理過程通?？梢苑譃樵?/p>

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

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

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

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

23、優(yōu)化；物理優(yōu)化：存取路徑和底層操作算法的選擇，可以是基于規(guī)則的、基于代層操作算法的選擇，可以是基于規(guī)則的、基于代價的也可以是基于語義的。實際優(yōu)化過程中為了價的也可以是基于語義的。實際優(yōu)化過程中為了達到更好的優(yōu)化技術往往都綜合使用這些優(yōu)化技達到更好的優(yōu)化技術往往都綜合使用這些優(yōu)化技術。術。n依據(jù)查詢優(yōu)化器得到的查詢計劃，系統(tǒng)的代碼生依據(jù)查詢優(yōu)化器得到的查詢計劃，系統(tǒng)的代碼生成器產(chǎn)生出這個計劃的執(zhí)行代碼。成器產(chǎn)生出這個計劃的執(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ù)表達式的內(nèi)部表示檢查后變?yōu)椴樵儤?，它是代?shù)表達式的內(nèi)部表示形式。代數(shù)優(yōu)化主要是依據(jù)關系代數(shù)表達式的等形式。代數(shù)優(yōu)化主要是依據(jù)關系代數(shù)表達式的等價變換規(guī)則所做的優(yōu)化。價變換規(guī)則所做的優(yōu)化。n代數(shù)優(yōu)化策略是通過對代數(shù)關系表達式的等價變代數(shù)優(yōu)化策略是通過對代數(shù)關系表達式的等價變換來提高效率的。關系代數(shù)表達式的等價是指兩換來提高效率的。關系代數(shù)表達式的等價是指兩個關系代數(shù)表達式用同一個關系帶入之后得到的個關系代數(shù)表達式用同一個關系帶入之后得到的結(jié)果相同，即兩個相應的關系具有相同的屬性結(jié)結(jié)果相同，即兩個相應的關系具有相同的屬性結(jié)合和相同的元組集合。合和相同的元組

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

26、接、笛卡爾積的結(jié)合律連接、笛卡爾積的結(jié)合律n設設E1E1、 E2 E2和和E3E3是關系代數(shù)表達式，是關系代數(shù)表達式，F(xiàn)1F1和和F2F2是連接是連接運算條件，則下列等價公式成立：運算條件，則下列等價公式成立：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選擇運算串接定律選擇運算串接定律n設設E E是一個關系代數(shù)表達式，是一個關系代數(shù)表達式，F(xiàn) F1 1和和F F2 2是選擇運算條件，是選擇運算條件，則下列等價公式成立：則下列等價公式成立：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投影運算串接定律投影運算串接定律n設設E E是關系代數(shù)表達式，是關系代數(shù)表達式，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 的子集，則下列等價的子集，則下列等價公式成立：公式成立：nA1,A2,AnA1,A2,An(B1,B2,BmB1,B2,Bm(E) (E) A1,A2,AnA1,A2,An(E)(E)n選擇與笛卡爾積、選擇與投影的交換律選擇與笛卡爾積、選擇與投影的交換律n選擇與笛卡爾積的交換律選擇與笛卡爾積的交換律n設設E E1 1、E E2 2是關系代數(shù)表達式，如果是關系代數(shù)表達式，如果F F中涉及的屬性都中涉及的屬性都是是E E1

29、1中的屬性，則下列等價公式成立：中的屬性，則下列等價公式成立：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這樣可以使部分選擇運算在笛卡爾積前先做。這樣可以使部分選擇運算在笛卡爾積前先做。n選擇與投影的交換律選擇與投影的交換律n設設E E是關系代數(shù)表達式，是關系代數(shù)表達式，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 則下列等價公式成立：則下列等價公式成立：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選擇與并、選擇與差運算、選擇與自然連接的分選擇與并、選擇與差運算、選擇與自然連接的分配率配率n選擇與并的分配率選擇與并的分配率

32、n設設E E1 1和和E E2 2是兩個關系代數(shù)表達式，并且是兩個關系代數(shù)表達式，并且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選擇與差運算的分配率選擇與差運算的分配率n設設E E1 1和和E E2 2是兩個關系代數(shù)表達式，并且是兩個關系代數(shù)表達式，并且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 設設E E1 1和和E E2 2是兩個關系代數(shù)表達式，并且是兩個關系代數(shù)表達式，并且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設設

34、E E1 1和和E E2 2是兩個關系代數(shù)表達式，是兩個關系代數(shù)表達式，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的屬性，則下列等價公的屬性，則下列等價公式成立：式成立：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設設E E1 1和和E E2 2是兩個關系代數(shù)表達式，是兩個關系代數(shù)

35、表達式，A Ai i(i=1,2,n)(i=1,2,n)是是E E1 1、E E2 2的公共屬性，則下列等價公式成立：的公共屬性，則下列等價公式成立：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é)討論的是應用啟發(fā)式規(guī)查詢樹的啟發(fā)式規(guī)則，本節(jié)討論的是應用啟發(fā)式規(guī)則的代數(shù)優(yōu)化。通過啟發(fā)式規(guī)則對關系表達式的查則的代數(shù)優(yōu)化。通過啟發(fā)式規(guī)則對關系表達式的查詢樹表達形式進行優(yōu)化。典型的啟發(fā)式規(guī)則有：詢樹表達形式進行優(yōu)化。典型的啟發(fā)式規(guī)則有：n選擇操作

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

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

38、LSQL表達：表達：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所示。為了使用關系代數(shù)所示。為了使用關系代數(shù)表達式的優(yōu)化法，不妨假設內(nèi)部表示是關系代數(shù)語法樹，則表達式的優(yōu)化法，不妨假設內(nèi)部表示是關系代數(shù)語法樹，則上面的查詢樹如圖上面的查詢樹如圖5-35-3所示。所示。n對查詢樹進行優(yōu)化。對查詢樹進行優(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)化的查詢計劃，高效的操作算法或存取路徑，得到優(yōu)化的查詢計劃，來達到查詢優(yōu)化的目的。選擇的方式可以是：來達到查詢優(yōu)化的目的。選擇的方式可以是：n基于啟發(fā)式規(guī)則的優(yōu)化基于啟發(fā)式規(guī)則的優(yōu)化n啟發(fā)式規(guī)則是指那些在大多數(shù)情況下都適用

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

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

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

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

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

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

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

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

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

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

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

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

53、RDBMS中代價估算公式要多得多，也復中代價估算公式要多得多，也復雜得多。雜得多。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)，即建立表的主人，負責完成。，即建立表的主人，負責完成。系統(tǒng)在存取數(shù)據(jù)時會自動選擇合適的索引作為存取路徑，系統(tǒng)在存取數(shù)據(jù)時會自動選擇合適的索引作為存取路徑，用戶不必顯式地選擇索引。用戶不必顯式地選擇索引。n使用索引的一個主要目的是避免全表掃

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