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

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

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系系統(tǒng)9.2關(guān)系系統(tǒng)的查詢優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem關(guān)系系統(tǒng)能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)是關(guān)系系統(tǒng)。由于關(guān)系模型中并非每一部分都是同等重要的并不苛求一個(gè)實(shí)際的關(guān)系系統(tǒng)必須完全支持關(guān)系模型。AnIntroductiontoDatabaseSystem關(guān)系系統(tǒng)與關(guān)系模型關(guān)系數(shù)據(jù)結(jié)構(gòu)域及域上定義的關(guān)系關(guān)系操作并、交、差、廣義笛卡爾積、選擇、投影、連接、除等關(guān)系完整性實(shí)體完整性、參照完整性、用戶自己定義的完整性AnIntroductiontoDatabaseSystem關(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)的最低要求AnIntroductiontoDatabaseSystem關(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)率支持選擇、投影和連接運(yùn)算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關(guān)系系統(tǒng)原因：就降低或喪失了數(shù)據(jù)的物理獨(dú)立性選擇、投影、連接運(yùn)算是最有用的運(yùn)算AnIntroductiontoDatabaseSystem9.1.2關(guān)系系統(tǒng)的分類分類依據(jù)：支持關(guān)系模型的程度分類⒈表式系統(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)系模型的所有特征

AnIntroductiontoDatabaseSystem關(guān)系系統(tǒng)的分類（續(xù)）

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作完整性表式系統(tǒng)表(最小)關(guān)系系統(tǒng)表選擇、投影、連接關(guān)系完備的系統(tǒng)表全關(guān)系系統(tǒng)AnIntroductiontoDatabaseSystem第四章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系系統(tǒng)9.2關(guān)系系統(tǒng)的查詢優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem9.2關(guān)系系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述9.2.2查詢優(yōu)化的必要性9.2.3查詢優(yōu)化的一般準(zhǔn)則9.2.4關(guān)系代數(shù)等價(jià)變換規(guī)則9.2.5關(guān)系代數(shù)表達(dá)式的優(yōu)化算法9.2.6優(yōu)化的一般步驟AnIntroductiontoDatabaseSystem9.2.1查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。

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

AnIntroductiontoDatabaseSystem由DBMS進(jìn)行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)AnIntroductiontoDatabaseSystem查詢優(yōu)化目標(biāo)查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系表達(dá)式的值實(shí)際系統(tǒng)的查詢優(yōu)化步驟1.將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2.根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式AnIntroductiontoDatabaseSystem實(shí)際系統(tǒng)的查詢優(yōu)化步驟3.選擇低層的操作算法對(duì)于語法樹中的每一個(gè)操作計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)選擇代價(jià)小的執(zhí)行算法4.生成查詢計(jì)劃(查詢執(zhí)行方案)查詢計(jì)劃是由一系列內(nèi)部操作組成的。AnIntroductiontoDatabaseSystem

代價(jià)模型

集中式數(shù)據(jù)庫單用戶系統(tǒng)

總代價(jià)=I/O代價(jià)+CPU代價(jià)多用戶系統(tǒng)

總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)分布式數(shù)據(jù)庫 總代價(jià)=I/O代價(jià)+CPU代價(jià)[+內(nèi)存代價(jià)]+通信代價(jià)AnIntroductiontoDatabaseSystem9.2.2查詢優(yōu)化的必要性例：求選修了課程Ｃ2的學(xué)生姓名

SELECTS.Sname FROMS,SC WHERES.Sno=SC.Sno ANDSC.Cno='C2';AnIntroductiontoDatabaseSystem查詢優(yōu)化的必要性（續(xù)）假設(shè)1：外存： S:1000條,SC:10000條,選修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)法

AnIntroductiontoDatabaseSystem執(zhí)行策略1Ｑ1＝Пs,name(бS.Sno=SC.Sno

∧SC.Cno='2'

(S×SC))

①S×SC讀取總塊數(shù)=讀S表塊數(shù)+讀SC表遍數(shù)*每遍塊數(shù)

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100

讀數(shù)據(jù)時(shí)間=2100/20=105秒AnIntroductiontoDatabaseSystem不同的執(zhí)行策略,考慮I/O時(shí)間

中間結(jié)果大小=1000*10000=107(1千萬條元組)

寫中間結(jié)果時(shí)間=10000000/10/20=50000秒

②б

讀數(shù)據(jù)時(shí)間=50000秒

③П總時(shí)間=105＋50000＋50000秒=100105秒=27.8小時(shí)AnIntroductiontoDatabaseSystem查詢優(yōu)化的必要性（續(xù)）2.Ｑ2＝ПＳ,name(бSC.Cno='2'(SSC))

① 讀取總塊數(shù)=2100塊 讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小=10000（減少1000倍） 寫中間結(jié)果時(shí)間=10000/10/20=50秒

②б

讀數(shù)據(jù)時(shí)間=50秒

③П

總時(shí)間＝105＋50＋50秒＝205秒=3.4分

AnIntroductiontoDatabaseSystem查詢優(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í)間＝5＋5秒＝10秒AnIntroductiontoDatabaseSystem9.2.3查詢優(yōu)化的一般準(zhǔn)則選擇運(yùn)算應(yīng)盡可能先做

目的：減小中間關(guān)系在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理按連接屬性排序在連接屬性上建立索引

投影運(yùn)算和選擇運(yùn)算同時(shí)做目的：避免重復(fù)掃描關(guān)系將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)AnIntroductiontoDatabaseSystem查詢優(yōu)化的一般準(zhǔn)則（續(xù)）某些選擇運(yùn)算＋在其前面執(zhí)行的笛卡爾積===>連接運(yùn)算例：бS.Sno=SC.Sno(S×SC)

SSC提取公共子表達(dá)式AnIntroductiontoDatabaseSystem9.2.4關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換AnIntroductiontoDatabaseSystem

常用的等價(jià)變換規(guī)則

設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式

l.連接、笛卡爾積交換律 E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

AnIntroductiontoDatabaseSystem關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）

2.連接、笛卡爾積的結(jié)合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

FAnIntroductiontoDatabaseSystem關(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}的子集AnIntroductiontoDatabaseSystem關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。AnIntroductiontoDatabaseSystem關(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)))AnIntroductiontoDatabaseSystem關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）6.選擇與笛卡爾積的交換律(1)假設(shè)：F中涉及的屬性都是E1中的屬性 бF(E1×E2)≡бF(E1)×E2

(2)假設(shè)：F=F1∧F2，并且F1只涉及E1中的屬性，

F2只涉及E2中的屬性 則由上面的等價(jià)變換規(guī)則1，4，6可推出： бF(E1×E2)≡бF1(E1)×бF2(E2)

AnIntroductiontoDatabaseSystem關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）(3)假設(shè)：F=F1∧F2，

F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性 бF(E1×E2)≡бF2(бF1(E1)×E2)

它使部分選擇在笛卡爾積前先做

AnIntroductiontoDatabaseSystem關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）7.選擇與并的交換 假設(shè)：E=E1∪E2，E1，E2有相同的屬性名 бF(E1∪E2)≡бF(E1)∪бF(E2)

8.選擇與差運(yùn)算的交換 假設(shè)：E1與E2有相同的屬性名 бF(E1-E2)≡бF(E1)-бF(E2)AnIntroductiontoDatabaseSystem關(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（E1×E2)≡ πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)AnIntroductiontoDatabaseSystem關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）l0.投影與并的交換

假設(shè)：E1和E2有相同的屬性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)AnIntroductiontoDatabaseSystem9.2關(guān)系系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述9.2.2查詢優(yōu)化的必要性9.2.3查詢優(yōu)化的一般準(zhǔn)則9.2.4關(guān)系代數(shù)等價(jià)變換規(guī)則9.2.5關(guān)系代數(shù)表達(dá)式的優(yōu)化算法9.2.6優(yōu)化的一般步驟AnIntroductiontoDatabaseSystem語法分析、轉(zhuǎn)換、優(yōu)化、形成訪問路徑（執(zhí)行計(jì)劃）、計(jì)算結(jié)果對(duì)S（供應(yīng)商），P（零件），SP（供應(yīng)關(guān)系）三個(gè)關(guān)系查詢供應(yīng)一個(gè)部門10000個(gè)螺栓以上，且供應(yīng)商位于南京的供應(yīng)商名字。Selectsnamefroms,p,spwheres.snum=sp.snumandsp.pnum=p.pnumands.city=‘南京’andp.pname=‘螺栓’andsp.quan>10000原始查詢樹（一種查詢語句的內(nèi)部表示法）語法分析優(yōu)化的查詢樹優(yōu)化執(zhí)行計(jì)劃（見下一頁）AnIntroductiontoDatabaseSystem代數(shù)優(yōu)化完全基于關(guān)系代數(shù)，把由查詢語句生成代數(shù)表達(dá)式（查詢樹）中的操作次序進(jìn)行等價(jià)變換。例如：先做選擇和投影，再做連接先做小關(guān)系上的連接，再做大關(guān)系上的連接變換原則：盡量減少查詢過程中的中間結(jié)果的大小。AnIntroductiontoDatabaseSystem代數(shù)優(yōu)化一般步驟1.

將合取選擇分解成一組單選擇操作2.

在查詢樹上把選擇操作下移，讓其盡早執(zhí)行3.

先執(zhí)行能夠產(chǎn)生最小的關(guān)系的操作4.

將有選擇條件的笛卡兒集操作替換成連接操作5.

將投影屬性分解并在操作樹中盡量下移，必要時(shí)生成新的投影運(yùn)算AnIntroductiontoDatabaseSystem基于代數(shù)優(yōu)化的一個(gè)例子對(duì)于關(guān)系模式： S（SNUM，SNAME，CITY） P（PNUM，PNAME，WEIGHT，SIZE） SP（SNUM，PNUM，DEPT，QUAN）執(zhí)行查詢Q：SELECTSNAMEFROMS，P，SPWHERE