DB第9章關(guān)系查詢處理和查詢優(yōu)化

1、An Introduction to Database Systenm1第九章 關(guān)系查詢處理和查詢優(yōu)化王占全An Introduction to Database Systenm2第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化9.3 小結(jié)小結(jié)An Introduction to Database Systenm3關(guān)系數(shù)據(jù)庫系統(tǒng)查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)查詢處理l查詢處理步驟查詢處理步驟l實(shí)現(xiàn)查詢操作的算法示例實(shí)現(xiàn)查詢操作的算法示例An Introduction to Database S

2、ystenm4查詢處理步驟查詢處理步驟l語法分析和翻譯語法分析和翻譯l優(yōu)化優(yōu)化l執(zhí)行執(zhí)行An Introduction to Database Systenm5第第9 9章章 關(guān)系系統(tǒng)及其查詢優(yōu)關(guān)系系統(tǒng)及其查詢優(yōu)化化9.1 關(guān)系系統(tǒng)查詢關(guān)系系統(tǒng)查詢9.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化9.3 小結(jié)小結(jié)An Introduction to Database Systenm69.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述9.2.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性9.2.3 查詢優(yōu)化的一般準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則9.2.4 優(yōu)化的策略：等價(jià)變換優(yōu)化的策略：等

3、價(jià)變換9.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法9.2.6 優(yōu)化的一般步驟優(yōu)化的一般步驟 An Introduction to Database Systenm79.2.1 查詢優(yōu)化概述查詢優(yōu)化概述l為什么要進(jìn)行查詢優(yōu)化為什么要進(jìn)行查詢優(yōu)化 查詢優(yōu)化極大地影響查詢優(yōu)化極大地影響RDBMS的性能。的性能。 l查詢優(yōu)化的可能性查詢優(yōu)化的可能性 關(guān)系數(shù)據(jù)語言為查詢的優(yōu)化提供了可關(guān)系數(shù)據(jù)語言為查詢的優(yōu)化提供了可能性。能性。 An Introduction to Database Systenm8由由DBMS進(jìn)行查詢優(yōu)化的好處進(jìn)行查詢優(yōu)化的好處l用戶不必考慮如何最好地表達(dá)查詢以獲用戶不

4、必考慮如何最好地表達(dá)查詢以獲得較好的效率得較好的效率l系統(tǒng)可以比用戶程序的系統(tǒng)可以比用戶程序的優(yōu)化優(yōu)化做得更好做得更好(1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息而用戶程序則難以獲得這些信息 An Introduction to Database Systenm9由由DBMS進(jìn)行查詢優(yōu)化的好處進(jìn)行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對查如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對查詢詢重新優(yōu)化重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。以選擇相適應(yīng)的執(zhí)行計(jì)劃。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程

5、序員一般優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)An Introduction to Database Systenm10查詢優(yōu)化目標(biāo)查詢優(yōu)化目標(biāo)l查詢優(yōu)化的總目標(biāo)查詢優(yōu)化的總目標(biāo) 選擇有效策略，求得給定關(guān)系表達(dá)式的值選擇有效策略，求得給定關(guān)系表達(dá)式的值查詢優(yōu)化的途徑？An Introduction to Database Systenm11查詢優(yōu)化的途徑包括：查詢優(yōu)化的途徑包括：An Introduction to Database Systenm12實(shí)際系統(tǒng)的查詢

6、優(yōu)化步驟實(shí)際系統(tǒng)的查詢優(yōu)化步驟1. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2. 根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式形式 3. 選擇低層的操作算法選擇低層的操作算法 對于語法樹中的每一個(gè)操作：計(jì)算各種執(zhí)行算法的執(zhí)行對于語法樹中的每一個(gè)操作：計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)；選擇代價(jià)小的執(zhí)行算法代價(jià)；選擇代價(jià)小的執(zhí)行算法 4. 生成查詢計(jì)劃生成查詢計(jì)劃(查詢執(zhí)行方案查詢執(zhí)行方案)An Introduction to Database Systenm13代價(jià)模型代價(jià)模型l集中式數(shù)據(jù)庫集中式數(shù)據(jù)庫 單用戶

7、系統(tǒng)單用戶系統(tǒng)總代價(jià)總代價(jià) = I/O代價(jià)代價(jià) + CPU代價(jià)代價(jià) 多用戶系統(tǒng)多用戶系統(tǒng)總代價(jià)總代價(jià) = I/O代價(jià)代價(jià) + CPU代價(jià)代價(jià) + 內(nèi)存代價(jià)內(nèi)存代價(jià)l分布式數(shù)據(jù)庫分布式數(shù)據(jù)庫 總代價(jià)總代價(jià) = I/O代價(jià)代價(jià) + CPU代價(jià)代價(jià)+ 內(nèi)存代價(jià)內(nèi)存代價(jià) + 通信代價(jià)通信代價(jià) An Introduction to Database Systenm149.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 l9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述l9.2.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性l9.2.3 查詢優(yōu)化的一般準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則l9.2.4 優(yōu)化的策略：等價(jià)變換優(yōu)化的策略：等價(jià)變換l9.

8、2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法l9.2.6 優(yōu)化的一般步驟優(yōu)化的一般步驟 An Introduction to Database Systenm159.2.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性 例：求選修了課程號(hào)為例：求選修了課程號(hào)為2的學(xué)生的姓名的學(xué)生的姓名 SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno=2; DEPT(D# , DNAME , DEAN)Student(Sno# , SNAME , SEX , AGE , D#)C(Cno# , CN , PC# , C

9、REDIT)SC(Sno# , Cno# , SCORE)PROF(P# , PNAME, AGE, D# , SAL)PC(P# , C#)An Introduction to Database Systenm16查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 假設(shè)假設(shè)1：外存：外存：Student:1000條條,SC:10000條條, 選修選修2號(hào)課程號(hào)課程:50條條假設(shè)假設(shè)2：一個(gè)內(nèi)存塊裝元組：一個(gè)內(nèi)存塊裝元組:10個(gè)個(gè)Student, 或或100個(gè)個(gè)SC, 內(nèi)存中一次可以存放內(nèi)存中一次可以存放: 5塊塊Student元組元組, 1塊塊SC元組和若干塊連接結(jié)果元組元組和若干塊連接結(jié)果元組假

10、設(shè)假設(shè)3：讀寫速度：讀寫速度：20塊塊/秒秒 DEPT(D# , DNAME , DEAN)Student(Sno# , SNAME , SEX , AGE , D#)C(Cno# , CN , PC# , CREDIT)SC(Sno# , Cno# , SCORE)PROF(P# , PNAME, AGE, D# , SAL)PC(P# , C#)An Introduction to Database Systenm17執(zhí)行策略執(zhí)行策略11 n a m e(S t u d e n t . S n o =S C . S n o S C . C n o = 2 (StudentSC) Stude

11、ntSC 讀取總塊數(shù)？讀取總塊數(shù)？ = 讀讀Student表塊數(shù)表塊數(shù) + 讀讀SC表遍數(shù)表遍數(shù)*每遍塊數(shù)每遍塊數(shù) =1000/10+(1000/(105) (10000/100) =100+20100=2100 讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=2100/20=105秒秒An Introduction to Database Systenm18不同的執(zhí)行策略不同的執(zhí)行策略,考慮考慮I/O時(shí)間時(shí)間中間結(jié)果大小中間結(jié)果大小 = 1000*10000 = 107 (1千萬條元千萬條元組組)寫中間結(jié)果時(shí)間寫中間結(jié)果時(shí)間 = 10000000/10/20 = 50000秒秒 讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間 = 50000秒

12、秒 總時(shí)間總時(shí)間 =1055000050000秒秒 = 100105秒秒 = 27.8小時(shí)小時(shí)An Introduction to Database Systenm19查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 2. 2 name(SC.Cno= 2 (Student SC) 讀取總塊數(shù)讀取總塊數(shù)= 2100塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=2100/20=105秒秒中間結(jié)果大小中間結(jié)果大小=10000 （減少（減少1000倍）倍）寫中間結(jié)果時(shí)間寫中間結(jié)果時(shí)間=10000/10/20=50秒秒 讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=50秒秒 總時(shí)間總時(shí)間1055050秒秒205秒秒=3.4分分 An Introdu

13、ction to Database Systenm20查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 3. 2 Sname(Student SC.Cno= 2 (SC) 讀讀SC表總塊數(shù)表總塊數(shù)= 10000/100=100塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=100/20=5秒秒 中間結(jié)果大小中間結(jié)果大小=50條條 不必寫入外存不必寫入外存 讀讀Student表總塊數(shù)表總塊數(shù)= 1000/10=100塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=100/20=5秒秒 總時(shí)間總時(shí)間55秒秒10秒秒 An Introduction to Database Systenm21查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 4. 2

14、name(Student SC.Cno=2 (SC)假設(shè)假設(shè)SC表在表在Cno上有索引，上有索引，Student表在表在Sno上有上有索引索引 讀讀SC表索引表索引=讀讀SC表總塊數(shù)表總塊數(shù)= 50/1001塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間 中間結(jié)果大小中間結(jié)果大小=50條條 不必寫入外存不必寫入外存DEPT(D# , DNAME , DEAN)Student(Sno# , SNAME , SEX , AGE , D#)C(Cno# , CN , PC# , CREDIT)SC(Sno# , Cno# , SCORE)PROF(P# , PNAME, AGE, D# , SAL)PC(P# , C#)

15、An Introduction to Database Systenm22查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 讀讀Student表索引表索引=讀讀Student表總塊數(shù)表總塊數(shù)= 50/10=5塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間 總時(shí)間總時(shí)間 連接運(yùn)算連接運(yùn)算 例：例：Student.Sno=SC.Sno (StudentSC) Student SCl6提取公共子表達(dá)式提取公共子表達(dá)式An Introduction to Database Systenm299.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 l9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述l9.2.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性l9.2

16、.3 查詢優(yōu)化的一般準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則l9.2.4 優(yōu)化的策略：等價(jià)變換優(yōu)化的策略：等價(jià)變換l9.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法l9.2.6 優(yōu)化的一般步驟優(yōu)化的一般步驟 An Introduction to Database Systenm309.2.4 優(yōu)化的策略：等價(jià)變換優(yōu)化的策略：等價(jià)變換l關(guān)系代數(shù)表達(dá)式等價(jià)關(guān)系代數(shù)表達(dá)式等價(jià) 指兩個(gè)來自同一個(gè)關(guān)系的不同表達(dá)式所得到指兩個(gè)來自同一個(gè)關(guān)系的不同表達(dá)式所得到的結(jié)果是相同的的結(jié)果是相同的 上面的優(yōu)化策略大部分都涉及到關(guān)系代數(shù)表上面的優(yōu)化策略大部分都涉及到關(guān)系代數(shù)表達(dá)式的等價(jià)變換達(dá)式的等價(jià)變換An Introduc

17、tion to Database Systenm31常用的等價(jià)變換規(guī)則常用的等價(jià)變換規(guī)則設(shè)設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式是條件表達(dá)式 l. 連接、笛卡爾積交換律連接、笛卡爾積交換律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1 An Introduction to Database Systenm32關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 2. 連接、笛卡爾積的結(jié)合律連接、笛卡爾積的結(jié)合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F

18、F F FAn Introduction to Database Systenm33關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）設(shè)設(shè)L1，L2 Ln為屬性集，且為屬性集，且L1 L 2 L3 Ln則則 L1( (Ln-1 (Ln (E) ) L1(E)3. 投影的串接定律An Introduction to Database Systenm34關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 4. 選擇的串接定律選擇的串接定律 F1 （ F2（E） F1 F2(E) 選擇的串接律說明選擇的串接律說明 選擇條件可以合并選擇條件可以合并 這樣一次就可檢查全部條件。這樣一次就可檢查全部條

19、件。 An Introduction to Database Systenm35關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 5. 選擇與投影的交換律選擇與投影的交換律(1)假設(shè)假設(shè): 選擇條件選擇條件F屬性集屬性集LF (L(E) L(F(E)An Introduction to Database Systenm36關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 6. 選擇與笛卡爾積的交換律選擇與笛卡爾積的交換律(1) 假設(shè)：假設(shè)：F中涉及的屬性都是中涉及的屬性都是E1中的屬性中的屬性 F (E1E2)F (E1)E2 (2) 假設(shè)：假設(shè)：F=F1F2，并且，并且F1只涉及只涉

20、及E1中的屬性，中的屬性， F2只涉及只涉及E2中的屬性中的屬性 則由上面的等價(jià)變換規(guī)則則由上面的等價(jià)變換規(guī)則1，4，6可推出：可推出： F(E1E2) F1(E1)F2 (E2) An Introduction to Database Systenm37關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） (3) 假設(shè)：假設(shè)： F=F1F2， F1只涉及只涉及E1中的屬性，中的屬性， F2涉及涉及E1和和E2兩者的屬性兩者的屬性 F(E1E2) F2(F1(E1)E2) 它使部分選擇在笛卡爾積前先做它使部分選擇在笛卡爾積前先做 An Introduction to Database Syst

21、enm38關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 7. 選擇與并的交換選擇與并的交換假設(shè)：假設(shè)：E=E1E2，E1，E2有相同的屬性名有相同的屬性名F(E1E2) F(E1) F(E2) 8. 選擇與差運(yùn)算的交換選擇與差運(yùn)算的交換假設(shè)：假設(shè)：E1與與E2有相同的屬性名有相同的屬性名F(E1-E2) F(E1) - F(E2) An Introduction to Database Systenm39關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 9. 投影與笛卡爾積的交換投影與笛卡爾積的交換假設(shè)：假設(shè)：E1和和E2是兩個(gè)關(guān)系表達(dá)式，是兩個(gè)關(guān)系表達(dá)式， L1是是E1的屬性，的

22、屬性， L2是是E2的屬性的屬性 L1, L2 （E1E2) L1 （E1) L2 (E2)An Introduction to Database Systenm40關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） l0. 投影與并的交換投影與并的交換假設(shè)：假設(shè)：E1和和E2 有相同的屬性名有相同的屬性名 L(E1E2)L(E1) L(E2) 10個(gè)規(guī)則的情況An Introduction to Database Systenm419.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 l9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述l9.2.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性l9.2.3 查詢優(yōu)化的一般準(zhǔn)

23、則查詢優(yōu)化的一般準(zhǔn)則l9.2.4 優(yōu)化的策略：等價(jià)變換優(yōu)化的策略：等價(jià)變換l9.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法l9.2.6 優(yōu)化的一般步驟優(yōu)化的一般步驟 An Introduction to Database Systenm429.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 算法：關(guān)系表達(dá)式的優(yōu)化算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的語法樹（沒有任輸入：一個(gè)關(guān)系表達(dá)式的語法樹（沒有任何優(yōu)化的樹）。何優(yōu)化的樹）。輸出：計(jì)算該表達(dá)式的程序。輸出：計(jì)算該表達(dá)式的程序。方法：方法：（1）分解選擇運(yùn)算）分解選擇運(yùn)算 利用規(guī)則利用規(guī)則4(選擇的串接選擇的串接)

24、把形如把形如F1 F2 Fn (E)變換為變換為 F1 (F2( (Fn(E) ) An Introduction to Database Systenm43關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)續(xù))（2）通過交換選擇運(yùn)算，將其盡可能移到）通過交換選擇運(yùn)算，將其盡可能移到樹的葉端樹的葉端 （3）通過交換投影運(yùn)算，將其盡可能移到）通過交換投影運(yùn)算，將其盡可能移到葉端葉端（4）合并串接的選擇和投影，以便能同時(shí)執(zhí)行）合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成或在一次掃描中完成 An Introduction to Database Systenm44關(guān)系代數(shù)表達(dá)式的優(yōu)化算

25、法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)續(xù))（5）對內(nèi)結(jié)點(diǎn)分組）對內(nèi)結(jié)點(diǎn)分組 每一雙目運(yùn)算每一雙目運(yùn)算(， ，-)和它所有的直和它所有的直接祖先為一組接祖先為一組(這些直接祖先是這些直接祖先是，運(yùn)算運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積()，而且其后的選擇不能與它結(jié)合為等值，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。 An Introduction to Database Systenm45關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系

26、代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)續(xù))（6）生成程序）生成程序 生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。一步。 各步的順序是任意的，只要保證任何一組的各步的順序是任意的，只要保證任何一組的計(jì)算不會(huì)在它的后代組之前計(jì)算計(jì)算不會(huì)在它的后代組之前計(jì)算。 An Introduction to Database Systenm469.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述9.2.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性9.2.3 查詢優(yōu)化的一般準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則9.2.4 優(yōu)化的策略：等價(jià)變換優(yōu)化的策略：等價(jià)變換9.2.5 關(guān)系代

27、數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法9.2.6 優(yōu)化的一般步驟優(yōu)化的一般步驟 An Introduction to Database Systenm479.2.6 優(yōu)化的一般步驟優(yōu)化的一般步驟 1把查詢轉(zhuǎn)換成某種內(nèi)部表示把查詢轉(zhuǎn)換成某種內(nèi)部表示2代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式形式3物理優(yōu)化：選擇低層的存取路徑物理優(yōu)化：選擇低層的存取路徑4生成查詢計(jì)劃，選擇代價(jià)最小的生成查詢計(jì)劃，選擇代價(jià)最小的 An Introduction to Database Systenm48優(yōu)化的一般步驟優(yōu)化的一般步驟 (續(xù)續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示（語法樹

28、）把查詢轉(zhuǎn)換成某種內(nèi)部表示（語法樹） 建立語法樹的規(guī)則： 對一個(gè)關(guān)系表達(dá)式進(jìn)行語法分析，將將關(guān)系作為葉子節(jié)點(diǎn)，而對關(guān)系的操作作關(guān)系作為葉子節(jié)點(diǎn)，而對關(guān)系的操作作為非葉子節(jié)點(diǎn)為非葉子節(jié)點(diǎn)。 例：求選修了課程號(hào)為例：求選修了課程號(hào)為2的學(xué)生姓名的學(xué)生姓名An Introduction to Database Systenm49（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示）把查詢轉(zhuǎn)換成某種內(nèi)部表示Sname SC.Cno=2 Student.Sno=SC.Sno StudentSCAn Introduction to Database Systenm50Sname SC.Cno=2 Student.Sno=SC.

29、Sno StudentSC（2）代數(shù)優(yōu)化）代數(shù)優(yōu)化利用優(yōu)化算法把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式An Introduction to Database Systenm51（2）代數(shù)優(yōu)化）代數(shù)優(yōu)化 Sname Student.Sno=SC.Sno SC.Cno= 2 StudentSCAn Introduction to Database Systenm52（2）代數(shù)優(yōu)化）代數(shù)優(yōu)化Sname SC.Cno= 2 StudentSCAn Introduction to Database Systenm53 所謂選擇所謂選擇低層低層存取路徑，指的就是存取路徑，指的就是要充分利用數(shù)據(jù)庫中已有的索引等信息。

30、要充分利用數(shù)據(jù)庫中已有的索引等信息。假如選擇條件或連接條件所涉及的屬性假如選擇條件或連接條件所涉及的屬性上有索引，那么利用該索引進(jìn)行存取就上有索引，那么利用該索引進(jìn)行存取就可以節(jié)省很多時(shí)間，這也能提高查詢的可以節(jié)省很多時(shí)間，這也能提高查詢的效率。效率。 （3）物理優(yōu)化：選擇低層的存取路徑）物理優(yōu)化：選擇低層的存取路徑An Introduction to Database Systenm54（3）物理優(yōu)化：選擇低層的存取路徑）物理優(yōu)化：選擇低層的存取路徑- 優(yōu)化器查找數(shù)據(jù)字典獲得當(dāng)前數(shù)據(jù)庫狀態(tài)信息優(yōu)化器查找數(shù)據(jù)字典獲得當(dāng)前數(shù)據(jù)庫狀態(tài)信息 選擇字段上是否有索引選擇字段上是否有索引 連接的兩個(gè)表是否

31、有序連接的兩個(gè)表是否有序 連接字段上是否有索引連接字段上是否有索引然后根據(jù)一定的優(yōu)化規(guī)則選擇存取路徑然后根據(jù)一定的優(yōu)化規(guī)則選擇存取路徑 如本例中若如本例中若SC表上建有表上建有Cno的索引，則應(yīng)該利的索引，則應(yīng)該利用這個(gè)索引，而不必順序掃描用這個(gè)索引，而不必順序掃描SC表。表。 An Introduction to Database Systenm55（4）生成查詢計(jì)劃，選擇代價(jià)最小的）生成查詢計(jì)劃，選擇代價(jià)最小的在作連接運(yùn)算時(shí)，若兩個(gè)表在作連接運(yùn)算時(shí)，若兩個(gè)表(設(shè)為設(shè)為R1，R2)均無序，連接均無序，連接屬性上也沒有索引，則可以有下面幾種查詢計(jì)劃屬性上也沒有索引，則可以有下面幾種查詢計(jì)劃：

32、對兩個(gè)表作排序預(yù)處理對兩個(gè)表作排序預(yù)處理 對對R1在連接屬性上建索引在連接屬性上建索引 對對R2在連接屬性上建索引在連接屬性上建索引 在在R1，R2的連接屬性上均建索引的連接屬性上均建索引對不同的查詢計(jì)劃計(jì)算代價(jià)，選擇代價(jià)最小的一個(gè)。對不同的查詢計(jì)劃計(jì)算代價(jià)，選擇代價(jià)最小的一個(gè)。在計(jì)算代價(jià)時(shí)主要考慮磁盤讀寫的在計(jì)算代價(jià)時(shí)主要考慮磁盤讀寫的I/O數(shù)，內(nèi)存數(shù)，內(nèi)存CPU處處理時(shí)間在粗略計(jì)算時(shí)可不考慮。理時(shí)間在粗略計(jì)算時(shí)可不考慮。 An Introduction to Database Systenm56第第9 9章章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化9.1 關(guān)系系統(tǒng)關(guān)系系統(tǒng)9.2 關(guān)系系統(tǒng)

33、的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化9.3 小結(jié)小結(jié)An Introduction to Database Systenm57小結(jié)小結(jié) l關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 代數(shù)優(yōu)化：關(guān)系代數(shù)表達(dá)式的優(yōu)化代數(shù)優(yōu)化：關(guān)系代數(shù)表達(dá)式的優(yōu)化 關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)等價(jià)變換規(guī)則 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 物理優(yōu)化：存取路徑和低層操作算法的選擇物理優(yōu)化：存取路徑和低層操作算法的選擇 An Introduction to Database Systenm58作業(yè)作業(yè)設(shè)有學(xué)生關(guān)系設(shè)有學(xué)生關(guān)系S(Sno,Sname,Sage,Ssex)課程關(guān)系課程關(guān)系C(Cno,Cname,Tname

34、)學(xué)習(xí)關(guān)系學(xué)習(xí)關(guān)系SC(Sno,Cno,grade)查詢學(xué)習(xí)劉紅老師課程的所有女同學(xué)的學(xué)查詢學(xué)習(xí)劉紅老師課程的所有女同學(xué)的學(xué)號(hào)和姓名。要求畫出語法樹并優(yōu)化。號(hào)和姓名。要求畫出語法樹并優(yōu)化。An Introduction to Database Systenm59實(shí)例實(shí)例_查詢優(yōu)化的實(shí)例查詢優(yōu)化的實(shí)例lSELECT Student.Sname FROM Student,SC WHER Student.Sno=SC.Sno AND SC.Cno=2;l系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查詢：系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查詢： 如如 q1= sname( student.sno=o=2(studentsc) q2= sname( o=2(student sc) q3= sname(student o=2(sc)l這三種不同的查詢執(zhí)行策略，其查詢時(shí)間相差很大