第9章查詢優(yōu)化

1、An Introduction to Database System數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論An Introduction to Database System第九章第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化An Introduction to Database System第九章第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化9.1 關(guān)系系統(tǒng)9.2 關(guān)系系統(tǒng)的查詢優(yōu)化9.3 小結(jié)An Introduction to Database System關(guān)系系統(tǒng)關(guān)系系統(tǒng)v 能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)是關(guān)系系統(tǒng)。v 由于關(guān)系模型中并非每一部分都是同等重要的v 并不苛求一個(gè)實(shí)

2、際的關(guān)系系統(tǒng)必須完全支持關(guān)系模型。 An Introduction to Database System關(guān)系系統(tǒng)與關(guān)系模型關(guān)系系統(tǒng)與關(guān)系模型v 關(guān)系數(shù)據(jù)結(jié)構(gòu) 域及域上定義的關(guān)系v 關(guān)系操作 并、交、差、廣義笛卡爾積、選擇、投影、連接、除等 v 關(guān)系完整性 實(shí)體完整性、參照完整性、用戶自己定義的完整性An Introduction to Database System關(guān)系系統(tǒng)的定義關(guān)系系統(tǒng)的定義 一個(gè)數(shù)據(jù)庫管理系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它至少支持：1. 關(guān)系數(shù)據(jù)庫（即關(guān)系數(shù)據(jù)結(jié)構(gòu)） 系統(tǒng)中只有表這種結(jié)構(gòu)2. 支持選擇、投影和（自然）連接運(yùn)算 對(duì)這些運(yùn)算不要求用戶定義任何物理存取路徑對(duì)關(guān)系系統(tǒng)

3、的最低要求An Introduction to Database System關(guān)系系統(tǒng)的定義關(guān)系系統(tǒng)的定義 不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)顯然不能稱為關(guān)系系統(tǒng) 僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，但沒有選擇、投影和連接運(yùn)算功能的系統(tǒng)仍不能算作關(guān)系系統(tǒng)。 原因：不能提高用戶的生產(chǎn)率v 支持選擇、投影和連接運(yùn)算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關(guān)系系統(tǒng) 原因：就降低或喪失了數(shù)據(jù)的物理獨(dú)立性v 選擇、投影、連接運(yùn)算是最有用的運(yùn)算An Introduction to Database System9.1.2 關(guān)系系統(tǒng)的分類關(guān)系系統(tǒng)的分類 v 分類依據(jù)：支持關(guān)系模型的程度v 分類 表式系統(tǒng)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)(

4、即表) (最小)關(guān)系系統(tǒng) 支持：關(guān)系數(shù)據(jù)結(jié)構(gòu)； 選擇、投影、連接關(guān)系操作 關(guān)系完備的系統(tǒng) 支持：關(guān)系數(shù)據(jù)結(jié)構(gòu)； 所有的關(guān)系代數(shù)操作 全關(guān)系系統(tǒng) 支持：關(guān)系模型的所有特征 An Introduction to Database System關(guān)系系統(tǒng)的分類關(guān)系系統(tǒng)的分類 （續(xù)）（續(xù)）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)操作完整性完整性表式系統(tǒng)表式系統(tǒng)表表 (最小最小)關(guān)系系統(tǒng)關(guān)系系統(tǒng)表表選擇、投影、選擇、投影、連接連接 關(guān)系完備的系統(tǒng)關(guān)系完備的系統(tǒng)表表 全關(guān)系系統(tǒng)全關(guān)系系統(tǒng) An Introduction to Database System第四章第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化9.1 關(guān)

5、系系統(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 System9.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 關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)等價(jià)變換規(guī)則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 System9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述v查詢優(yōu)化的必要性查詢優(yōu)化

6、的必要性 查詢優(yōu)化極大地影響查詢優(yōu)化極大地影響RDBMS的性能。的性能。 v查詢優(yōu)化的可能性查詢優(yōu)化的可能性 關(guān)系數(shù)據(jù)語言的關(guān)系數(shù)據(jù)語言的級(jí)別很高級(jí)別很高，使，使DBMS可以從關(guān)可以從關(guān)系表達(dá)式中分析查詢系表達(dá)式中分析查詢語義語義。 An Introduction to Database System由由DBMS進(jìn)行查詢優(yōu)化的好處進(jìn)行查詢優(yōu)化的好處v用戶不必考慮如何最好地表達(dá)查詢以獲得較好的用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率效率v系統(tǒng)可以比用戶程序的系統(tǒng)可以比用戶程序的優(yōu)化優(yōu)化做得更好做得更好(1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)

7、信息，而用戶程序則難以獲得這些信息序則難以獲得這些信息 An Introduction to Database System由由DBMS進(jìn)行查詢優(yōu)化的好處進(jìn)行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢?nèi)绻麛?shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。以選擇相適應(yīng)的執(zhí)行計(jì)劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的?？赡艿?。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮

8、有限的幾種可能性限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)An Introduction to Database System查詢優(yōu)化目標(biāo)查詢優(yōu)化目標(biāo)v 查詢優(yōu)化的總目標(biāo)查詢優(yōu)化的總目標(biāo) 選擇有效策略，求得給定關(guān)系表達(dá)式的值選擇有效策略，求得給定關(guān)系表達(dá)式的值v 實(shí)際系統(tǒng)的查詢優(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)根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn) （優(yōu)化）形式（優(yōu)化）形式An Introduction to Database

9、 System實(shí)際系統(tǒng)的查詢優(yōu)化步驟實(shí)際系統(tǒng)的查詢優(yōu)化步驟3. 選擇低層的操作算法選擇低層的操作算法對(duì)于語法樹中的每一個(gè)操作對(duì)于語法樹中的每一個(gè)操作 計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià) 選擇代價(jià)小的執(zhí)行算法選擇代價(jià)小的執(zhí)行算法4. 生成查詢計(jì)劃生成查詢計(jì)劃(查詢執(zhí)行方案查詢執(zhí)行方案) 查詢計(jì)劃是由一系列內(nèi)部操作組成的。查詢計(jì)劃是由一系列內(nèi)部操作組成的。An Introduction to Database System代價(jià)模型代價(jià)模型v集中式數(shù)據(jù)庫集中式數(shù)據(jù)庫 單用戶系統(tǒng)單用戶系統(tǒng)總代價(jià)總代價(jià) = I/O代價(jià)代價(jià) + CPU代價(jià)代價(jià) 多用戶系統(tǒng)多用戶系統(tǒng)總代價(jià)總代價(jià) = I/

10、O代價(jià)代價(jià) + CPU代價(jià)代價(jià) + 內(nèi)存代價(jià)內(nèi)存代價(jià)v分布式數(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 System9.2.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性 例：求選修了課程2的學(xué)生姓名 SELECT S.SnameFROM S, SCWHERE S.Sno=SC.SnoAND SC.Cno= C2; An Introduction to Database System查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 假設(shè)1：外存：S:1000條,SC:10000條,

11、 選修C2號(hào)課程:50條假設(shè)2：一個(gè)內(nèi)存塊裝元組:10條S, 或100條SC, 內(nèi)存中一次可以存放: 5塊S元組, 1塊SC元組和若干塊連接結(jié)果元組假設(shè)3：讀寫速度：20塊/秒假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法 An Introduction to Database System執(zhí)行策略執(zhí)行策略11 s,name(S.Sno=SC.Sno SC.Cno=2 (SSC) SSC 讀取總塊數(shù)= 讀S表塊數(shù) + 讀SC表遍數(shù) *每遍塊數(shù) =1000/10+(1000/(105) (10000/100) =100+20100=2100 讀數(shù)據(jù)時(shí)間=2100/20=105秒An Introduct

12、ion to Database System不同的執(zhí)行策略不同的執(zhí)行策略,考慮考慮I/O時(shí)間時(shí)間中間結(jié)果大小 = 1000*10000 = 107 (1千萬條元組)寫中間結(jié)果時(shí)間 = 10000000/10/20 = 50000秒 讀數(shù)據(jù)時(shí)間 = 50000秒 總時(shí)間 =1055000050000秒 = 100105秒 = 27.8小時(shí)An Introduction to Database System查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 2. 2 ,name(SC.Cno= 2 (S SC) 讀取總塊數(shù)= 2100塊讀數(shù)據(jù)時(shí)間=2100/20=105秒中間結(jié)果大小=10000 （減少

13、1000倍）寫中間結(jié)果時(shí)間=10000/10/20=50秒 讀數(shù)據(jù)時(shí)間=50秒 總時(shí)間1055050秒205秒=3.4分 An Introduction to Database System查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 3. 2 Sname(S SC.Cno= 2 (SC) 讀SC表總塊數(shù)= 10000/100=100塊讀數(shù)據(jù)時(shí)間=100/20=5秒 中間結(jié)果大小=50條 不必寫入外存 讀S表總塊數(shù)= 1000/10=100塊讀數(shù)據(jù)時(shí)間=100/20=5秒 總時(shí)間55秒10秒 An Introduction to Database System9.2.3 查詢優(yōu)化的一般準(zhǔn)則查詢

14、優(yōu)化的一般準(zhǔn)則 v 選擇運(yùn)算應(yīng)盡可能先做 目的：減小中間關(guān)系v 在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理 按連接屬性排序 在連接屬性上建立索引 v 投影運(yùn)算和選擇運(yùn)算同時(shí)做 目的：避免重復(fù)掃描關(guān)系v 將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合 目的：減少掃描關(guān)系的遍數(shù)An Introduction to Database System查詢優(yōu)化的一般準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則 （續(xù)）（續(xù)）v 某些選擇運(yùn)算在其前面執(zhí)行的笛卡爾積 = 連接運(yùn)算 例：S.Sno=SC.Sno (SSC) S SCv 提取公共子表達(dá)式An Introduction to Database System9.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)

15、則關(guān)系代數(shù)等價(jià)變換規(guī)則 v關(guān)系代數(shù)表達(dá)式等價(jià) 指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的 上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換An Introduction to Database System常用的等價(jià)變換規(guī)則常用的等價(jià)變換規(guī)則設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式 l. 連接、笛卡爾積交換律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1 An Introduction to Database System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 2. 連接、笛卡爾積的結(jié)合律 (E1E2) E3 E1 (E2E3) (E1

16、 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F FAn Introduction to Database System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 3. 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E)假設(shè)：1) E是關(guān)系代數(shù)表達(dá)式2) Ai(i=1，2，n), Bj(j=l，2，m)是屬性名3)A1, A2, , An構(gòu)成Bl，B2，Bm的子集 An Introduction to Database System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 4. 選擇

17、的串接定律 F1 （ F2（E） F1 F2(E) 選擇的串接律說明 選擇條件可以合并 這樣一次就可檢查全部條件。 An Introduction to Database System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 5. 選擇與投影的交換律(1)假設(shè): 選擇條件F只涉及屬性A1，An F (A1,A2, ,An ( E) A1,A2, ,An(F(E) (2)假設(shè): F中有不屬于A1, ,An的屬性B1,Bm A1,A2, ,An ( F ( E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E)An Introduction to Datab

18、ase System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 6. 選擇與笛卡爾積的交換律(1) 假設(shè)：F中涉及的屬性都是E1中的屬性 F (E1E2)F (E1)E2 (2) 假設(shè)：F=F1F2，并且F1只涉及E1中的屬性， F2只涉及E2中的屬性 則由上面的等價(jià)變換規(guī)則1，4，6可推出： F(E1E2) F1(E1)F2 (E2) An Introduction to Database System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） (3) 假設(shè)： F=F1F2， F1只涉及E1中的屬性， F2涉及E1和E2兩者的屬性 F(E1E2) F2(F1(E1)E2)

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

20、2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2)An Introduction to Database System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） l0. 投影與并的交換假設(shè)：E1和E2 有相同的屬性名 A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2) An Introduction to Database System9.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)化的一般

21、準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則9.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)等價(jià)變換規(guī)則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 System語法分析、轉(zhuǎn)換、優(yōu)化、形成訪問路徑（執(zhí)行計(jì)劃）、計(jì)語法分析、轉(zhuǎn)換、優(yōu)化、形成訪問路徑（執(zhí)行計(jì)劃）、計(jì)算結(jié)果算結(jié)果對(duì)對(duì)S S（供應(yīng)商），（供應(yīng)商），P P（零件），（零件），SPSP（供應(yīng)關(guān)系）三個(gè)關(guān)系查詢（供應(yīng)關(guān)系）三個(gè)關(guān)系查詢供應(yīng)一個(gè)部門供應(yīng)一個(gè)部門1000010000個(gè)螺栓以上，個(gè)螺栓以上，且供應(yīng)商位于南京的供應(yīng)商名字。且供應(yīng)商位于南京的供應(yīng)商名字。

22、Selectsnamefroms,p,spwheres.snum=sp.snumandsp.pnum=p.pnumands.city=南京andp.pname=螺栓andsp.quan10000原始查詢樹（一種查詢語句的內(nèi)部表示法）語法分析優(yōu)化的查詢樹優(yōu)化執(zhí)行計(jì)劃（見下一頁）An Introduction to Database System代數(shù)優(yōu)化代數(shù)優(yōu)化v完全基于關(guān)系代數(shù)，把由查詢語句生成代數(shù)表達(dá)式（查詢樹）中的操作次序進(jìn)行等價(jià)變換。例如：先做選擇和投影，再做連接先做小關(guān)系上的連接，再做大關(guān)系上的連接v變換原則：盡量減少查詢過程中的中間結(jié)果的大小。An Introduction to Database System代數(shù)優(yōu)化一般步驟代數(shù)優(yōu)化一般步驟1. 將合取選擇分解成一組單選擇操作2. 在查詢樹上把選擇操作下移，讓其盡早執(zhí)行3. 先執(zhí)行能夠產(chǎn)生