數(shù)據(jù)庫(kù)系統(tǒng)概論關(guān)系系統(tǒng)及其查詢優(yōu)化

1、An Introduction to Database System中國(guó)人民大學(xué)信息學(xué)院計(jì)算機(jī)系中國(guó)人民大學(xué)信息學(xué)院計(jì)算機(jī)系數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(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)化4.1 關(guān)系系統(tǒng)4.2 關(guān)系系統(tǒng)的查詢優(yōu)化4.3 小結(jié)An Introduction to Database System關(guān)系系統(tǒng)關(guān)系系統(tǒng)n能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫(kù)管理系統(tǒng)是關(guān)系系統(tǒng)。n由于關(guān)

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

3、運(yùn)算不要求用戶定義任何物理存取路徑對(duì)關(guān)系系統(tǒng)的最低要求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)，但沒(méi)有選擇、投影和連接運(yùn)算功能的系統(tǒng)仍不能算作關(guān)系系統(tǒng)。n原因：不能提高用戶的生產(chǎn)率n支持選擇、投影和連接運(yùn)算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關(guān)系系統(tǒng)n原因：就降低或喪失了數(shù)據(jù)的物理獨(dú)立性n選擇、投影、連接運(yùn)算是最有用的運(yùn)算An Introduction to Database System4.1.2 關(guān)系系統(tǒng)的分類關(guān)系系統(tǒng)的分類 n分類依據(jù)：支持關(guān)系模型的程度n

4、分類 表式系統(tǒng)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)(即表) (最小)關(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)系模型的所有特征 特別是:數(shù)據(jù)結(jié)構(gòu)中域的概念 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第四

5、章第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化4.1 關(guān)系系統(tǒng)4.2 關(guān)系系統(tǒng)的查詢優(yōu)化4.3 小結(jié)An Introduction to Database System4.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 4.2.1 查詢優(yōu)化概述4.2.2 查詢優(yōu)化的必要性4.2.3 查詢優(yōu)化的一般準(zhǔn)則4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法4.2.6 優(yōu)化的一般步驟 An Introduction to Database System4.2.1 查詢優(yōu)化概述查詢優(yōu)化概述n查詢優(yōu)化的必要性n查詢優(yōu)化極大地影響RDBMS的性能。 n查詢優(yōu)化的可能性n關(guān)系數(shù)據(jù)語(yǔ)言的級(jí)別很高

6、，使DBMS可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義。 An Introduction to Database System由由DBMS進(jìn)行查詢優(yōu)化的好處進(jìn)行查詢優(yōu)化的好處n用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率n系統(tǒng)可以比用戶程序的優(yōu)化做得更好(1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息 An Introduction to Database System由由DBMS進(jìn)行查詢優(yōu)化的好處進(jìn)行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。(3

7、)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)An Introduction to Database System查詢優(yōu)化目標(biāo)查詢優(yōu)化目標(biāo)n查詢優(yōu)化的總目標(biāo) 選擇有效策略，求得給定關(guān)系表達(dá)式的值n實(shí)際系統(tǒng)的查詢優(yōu)化步驟1. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹(shù)2. 根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn) （優(yōu)化）形式An Introduction to Database System實(shí)際系統(tǒng)的查詢優(yōu)化步驟實(shí)際系統(tǒng)的查詢優(yōu)化步驟3. 選擇低層的操作算法對(duì)于語(yǔ)法樹(shù)中的每一個(gè)操作n計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)n選擇代價(jià)小的執(zhí)行算法

8、4. 生成查詢計(jì)劃(查詢執(zhí)行方案)n查詢計(jì)劃是由一系列內(nèi)部操作組成的。An Introduction to Database System代價(jià)模型代價(jià)模型n集中式數(shù)據(jù)庫(kù)n單用戶系統(tǒng)總代價(jià) = I/O代價(jià) + CPU代價(jià)n多用戶系統(tǒng)總代價(jià) = I/O代價(jià) + CPU代價(jià) + 內(nèi)存代價(jià)n分布式數(shù)據(jù)庫(kù) 總代價(jià) = I/O代價(jià) + CPU代價(jià)+ 內(nèi)存代價(jià) + 通信代價(jià) An Introduction to Database System4.2.2 查詢優(yōu)化的必要性查詢優(yōu)化的必要性 例：求選修了課程2的學(xué)生姓名 SELECT Student.SnameFROM Student, SCWHERE Stud

9、ent.Sno=SC.SnoAND SC.Cno=2; An Introduction to Database System查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 假設(shè)1：外存：Student:1000條,SC:10000條, 選修2號(hào)課程:50條假設(shè)2：一個(gè)內(nèi)存塊裝元組:10個(gè)Student, 或100個(gè)SC, 內(nèi)存中一次可以存放: 5塊Student元組, 1塊SC元組和若干塊連接結(jié)果元組假設(shè)3：讀寫速度：20塊/秒假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法 An Introduction to Database System執(zhí)行策略執(zhí)行策略11 n a m e(S t u d e n

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

11、0000秒 總時(shí)間 =1055000050000秒 = 100105秒 = 27.8小時(shí)An Introduction to Database System查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 2. 2 name(SC.Cno= 2 (Student SC) 讀取總塊數(shù)= 2100塊讀數(shù)據(jù)時(shí)間=2100/20=105秒中間結(jié)果大小=10000 （減少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.

12、 2 Sname(Student SC.Cno= 2 (SC) 讀SC表總塊數(shù)= 10000/100=100塊讀數(shù)據(jù)時(shí)間=100/20=5秒 中間結(jié)果大小=50條 不必寫入外存 讀Student表總塊數(shù)= 1000/10=100塊讀數(shù)據(jù)時(shí)間=100/20=5秒 總時(shí)間55秒10秒 An Introduction to Database System查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 4. 2 name(Student SC.Cno=2 (SC)假設(shè)SC表在Cno上有索引，Student表在Sno上有索引 讀SC表索引=讀SC表總塊數(shù)= 50/1001塊讀數(shù)據(jù)時(shí)間 中間結(jié)果大小=50條

13、 不必寫入外存An Introduction to Database System查詢優(yōu)化的必要性（續(xù)）查詢優(yōu)化的必要性（續(xù)） 讀Student表索引=讀Student表總塊數(shù)= 50/10=5塊讀數(shù)據(jù)時(shí)間 總時(shí)間 連接運(yùn)算 例：Student.Sno=SC.Sno (StudentSC) Student SCn提取公共子表達(dá)式An Introduction to Database System4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)等價(jià)變換規(guī)則 n關(guān)系代數(shù)表達(dá)式等價(jià)n指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的n上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換An Introdu

14、ction 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 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F FAn Introduction to Database System關(guān)系代數(shù)

15、等價(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. 選擇的串接定律 F1 （ F2（E） F1 F2(E)n選擇的串接律說(shuō)明 選擇條件可以合并n這樣一次就可檢查全部條件。 An Introduction to Database Sy

16、stem關(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 Database System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 6. 選擇與笛卡爾積的交換律(1) 假設(shè)：F中涉及的屬性都是E1中的屬性 F (E1E2)F (E1)E2

17、(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) 它使部分選擇在笛卡爾積前先做 An Introduction to Database System關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)） 7. 選擇與并的交換假設(shè)：E

18、=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,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2)An Introduction to Database System關(guān)系代

19、數(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 System小結(jié)小結(jié)1-2: 連接、笛卡爾積的交換律、結(jié)合律3： 合并或分解投影運(yùn)算4： 合并或分解選擇運(yùn)算5-8： 選擇運(yùn)算與其他運(yùn)算交換5，9，10： 投影運(yùn)算與其他運(yùn)算交換 An Introduction to Database System4.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 4.2.1 查詢優(yōu)化概述4.2.2 查詢優(yōu)化的必要性

20、4.2.3 查詢優(yōu)化的一般準(zhǔn)則4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法4.2.6 優(yōu)化的一般步驟 An Introduction to Database System4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的語(yǔ)法樹(shù)。輸出：計(jì)算該表達(dá)式的程序。方法：（1）分解選擇運(yùn)算 利用規(guī)則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ) An Introduction to Database System關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)續(xù))（2）通過(guò)交換選擇運(yùn)算，將其盡可

21、能移到葉端 對(duì)每一個(gè)選擇，利用規(guī)則48盡可能把它移到樹(shù)的葉端。 （3）通過(guò)交換投影運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)投影利用規(guī)則3，9，l0，5中的一般形式盡可能把它移向樹(shù)的葉端。 An Introduction to Database System關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)續(xù))（4）合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成n利用規(guī)則35把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。n使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成n盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。 An Introduction t

22、o Database System關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)續(xù))（5）對(duì)內(nèi)結(jié)點(diǎn)分組n把上述得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組。n每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一組(這些直接祖先是，運(yùn)算)。n如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積()，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。 An Introduction to Database System關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)續(xù))（6）生成程序n生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。n各步的順序是任意的，只要保證任何一組

23、的計(jì)算不會(huì)在它的后代組之前計(jì)算。 An Introduction to Database System4.2 關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化 4.2.1 查詢優(yōu)化概述4.2.2 查詢優(yōu)化的必要性4.2.3 查詢優(yōu)化的一般準(zhǔn)則4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法4.2.6 優(yōu)化的一般步驟 An Introduction to Database System4.2.6 優(yōu)化的一般步驟優(yōu)化的一般步驟 1把查詢轉(zhuǎn)換成某種內(nèi)部表示2代數(shù)優(yōu)化：把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化） 形式3物理優(yōu)化：選擇低層的存取路徑4生成查詢計(jì)劃，選擇代價(jià)最小的 An Introduction

24、to Database System優(yōu)化的一般步驟優(yōu)化的一般步驟 (續(xù)續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示例：求選修了課程2的學(xué)生姓名SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno=2; An Introduction to Database System（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示）把查詢轉(zhuǎn)換成某種內(nèi)部表示語(yǔ)法樹(shù) 結(jié)果結(jié)果project(Sname) select(SC.Cno= 2 ) join(Student.Sno=SC.Sno) StudentSCAn Introduction to Database System關(guān)系代數(shù)語(yǔ)法樹(shù)關(guān)系代數(shù)語(yǔ)法樹(shù)Sname SC.Cno=2 Student.Sno=SC.S StudentSCAn Introduction to Database System（2）代數(shù)優(yōu)化）代數(shù)優(yōu)化利用優(yōu)化算法把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式 Sname Student.Sno=SC.Sno SC.Cno= 2 StudentSCAn Introduction to Database System（3）物理優(yōu)化：選擇低層的存取路徑）物理優(yōu)化：選擇低層的存取路