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

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

關系系統(tǒng)及其查詢優(yōu)化9.1關系系統(tǒng)9.2關系系統(tǒng)的查詢優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem關系系統(tǒng)能夠在一定程度上支持關系模型的數(shù)據(jù)庫管理系統(tǒng)是關系系統(tǒng)。由于關系模型中并非每一部分都是同等重要的并不苛求一個實際的關系系統(tǒng)必須完全支持關系模型。AnIntroductiontoDatabaseSystem關系系統(tǒng)與關系模型關系數(shù)據(jù)結(jié)構域及域上定義的關系關系操作并、交、差、廣義笛卡爾積、選擇、投影、連接、除等關系完整性實體完整性、參照完整性、用戶自己定義的完整性AnIntroductiontoDatabaseSystem關系系統(tǒng)的定義一個數(shù)據(jù)庫管理系統(tǒng)可定義為關系系統(tǒng)，當且僅當它至少支持：1.關系數(shù)據(jù)庫（即關系數(shù)據(jù)結(jié)構）系統(tǒng)中只有表這種結(jié)構2.支持選擇、投影和（自然）連接運算對這些運算不要求用戶定義任何物理存取路徑對關系系統(tǒng)的最低要求AnIntroductiontoDatabaseSystem關系系統(tǒng)的定義不支持關系數(shù)據(jù)結(jié)構的系統(tǒng)顯然不能稱為關系系統(tǒng)僅支持關系數(shù)據(jù)結(jié)構，但沒有選擇、投影和連接運算功能的系統(tǒng)仍不能算作關系系統(tǒng)。原因：不能提高用戶的生產(chǎn)率支持選擇、投影和連接運算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關系系統(tǒng)原因：就降低或喪失了數(shù)據(jù)的物理獨立性選擇、投影、連接運算是最有用的運算AnIntroductiontoDatabaseSystem9.1.2關系系統(tǒng)的分類分類依據(jù)：支持關系模型的程度分類⒈表式系統(tǒng)：支持關系數(shù)據(jù)結(jié)構(即表)⒉(最小)關系系統(tǒng)支持：關系數(shù)據(jù)結(jié)構；選擇、投影、連接關系操作⒊關系完備的系統(tǒng)支持：關系數(shù)據(jù)結(jié)構；所有的關系代數(shù)操作⒋全關系系統(tǒng)支持：關系模型的所有特征

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

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

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

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

代價模型

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

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

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

SELECTS.Sname FROMS,SC WHERES.Sno=SC.Sno ANDSC.Cno='C2';AnIntroductiontoDatabaseSystem查詢優(yōu)化的必要性（續(xù)）假設1：外存： S:1000條,SC:10000條,選修C2號課程:50條假設2：一個內(nèi)存塊裝元組:10條S,或100條SC, 內(nèi)存中一次可以存放:5塊S元組,1塊SC元組和若干塊連接結(jié)果元組假設3：讀寫速度：20塊/秒假設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ù)時間=2100/20=105秒AnIntroductiontoDatabaseSystem不同的執(zhí)行策略,考慮I/O時間

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

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

②б

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

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

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

②б

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

③П

總時間＝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ù)時間=100/20=5秒

中間結(jié)果大小=50條不必寫入外存

② 讀S表總塊數(shù)=1000/10=100塊

讀數(shù)據(jù)時間=100/20=5秒

③П

總時間＝5＋5秒＝10秒AnIntroductiontoDatabaseSystem9.2.3查詢優(yōu)化的一般準則選擇運算應盡可能先做

目的：減小中間關系在執(zhí)行連接操作前對關系適當進行預處理按連接屬性排序在連接屬性上建立索引

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

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

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

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

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

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

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

F

F

F

FAnIntroductiontoDatabaseSystem關系代數(shù)等價變換規(guī)則（續(xù)）3.投影的串接定律

π

A1,A2,

,An(π

B1,B2,,Bm(E))≡π

A1,A2,,An(E)假設：1) E是關系代數(shù)表達式2) Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名3){A1,A2,…,An}構成{Bl，B2，…，Bm}的子集AnIntroductiontoDatabaseSystem關系代數(shù)等價變換規(guī)則（續(xù)）4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。AnIntroductiontoDatabaseSystem關系代數(shù)等價變換規(guī)則（續(xù)）5.選擇與投影的交換律(1)假設:選擇條件F只涉及屬性A1，…，AnбF(πA1,A2,,An(

E))≡πA1,A2,,An(бF(E))

(2)假設:F中有不屬于A1,…,An的屬性B1,…,Bmπ

A1,A2,,An

(

бF(E))≡

πA1,A2,,An(бF

(πA1,A2,,An,B1,B2,,Bm(E)))AnIntroductiontoDatabaseSystem關系代數(shù)等價變換規(guī)則（續(xù)）6.選擇與笛卡爾積的交換律(1)假設：F中涉及的屬性都是E1中的屬性 бF(E1×E2)≡бF(E1)×E2

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

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

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

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

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

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

8.選擇與差運算的交換 假設：E1與E2有相同的屬性名 бF(E1-E2)≡бF(E1)-бF(E2)AnIntroductiontoDatabaseSystem關系代數(shù)等價變換規(guī)則（續(xù)）9.投影與笛卡爾積的交換

假設：E1和E2是兩個關系表達式，

A1，…，An是E1的屬性，

B1，…，Bm是E2的屬性πA1,A2,…,An,B1,B2,…,Bm（E1×E2)≡ πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)AnIntroductiontoDatabaseSystem關系代數(shù)等價變換規(guī)則（續(xù)）l0.投影與并的交換

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

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

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

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

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

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