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

AnIntroductiontoDatabaseSystem上海第二工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)庫系統(tǒng)概論AnIntroductiontoDatabaseSystem第九章關(guān)系查詢處理和查詢優(yōu)化AnIntroductiontoDatabaseSystem第九章

關(guān)系查詢處理和查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化AnIntroductiontoDatabaseSystem9.1關(guān)系數(shù)據(jù)庫的查詢處理9.1.1查詢處理的步驟查詢分析：對(duì)查詢語句進(jìn)行語法和詞法分析查詢檢查：檢查語義：語句中使用的對(duì)象的存在性和有效性用戶權(quán)限和和完整性檢查檢查通過后，把查詢語句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式（查詢樹即語法分析樹）AnIntroductiontoDatabaseSystem語法分析樹：結(jié)果project(Sname)

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

StudentSCAnIntroductiontoDatabaseSystem查詢優(yōu)化：選擇一個(gè)高效的查詢處理策略，方法有代數(shù)優(yōu)化、物理優(yōu)化，選擇的依據(jù)有基于規(guī)則、基于代價(jià)或基于語義執(zhí)行查詢：依據(jù)優(yōu)化器得到的策略生成查詢計(jì)劃，由代碼生成器生成可執(zhí)行代碼。AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例1.選擇操作的常用算法全表掃描，選出符合條件的元組使用索引可快速獲取符合選擇條件的元組指針，如sage=20或sage>20。組合條件如：sage>20andsdept=‘CS’方法1：分別選出符合sage>20條件的元組指針和符合sdept=‘CS’條件的元組指針，然后求它們的交集方法2：先選出符合sage>20條件的元組指針，然后對(duì)選出的元組判斷是否符合sdept=‘CS’條件。第一種方法在sage和sdept上均有索引的情況下比較有效，第二種方法應(yīng)該優(yōu)先選出選擇條件中有索引的元組。AnIntroductiontoDatabaseSystem2.連接操作的常用算法（假定為等值連接）：

Selecta.sno,a.sname,o,b.gradefromstudenta,scbwherea.sno=b.sno連接的總體思路：掃描student，對(duì)每一元組的sno，掃描grade的sno，把相同值的元組和student對(duì)應(yīng)元組進(jìn)行連接后輸出。AnIntroductiontoDatabaseSystem循環(huán)嵌套方法：嵌套掃描兩個(gè)表，總循環(huán)次數(shù)為兩個(gè)元組個(gè)數(shù)的乘積。排序-合并方法：根據(jù)兩個(gè)表的sno進(jìn)行排序，兩個(gè)循環(huán)均不必進(jìn)行全表掃描。效率大大提高。索引連接方法：對(duì)sc關(guān)于sno建立索引，內(nèi)層循環(huán)中由于sc建立的索引，所以不必全表掃描。AnIntroductiontoDatabaseSystemHashjoin方法：適用大表和小表的連接1依據(jù)Hash函數(shù)把小表數(shù)據(jù)放入內(nèi)存（可保留少量數(shù)據(jù)在臨時(shí)表空間中）（小表數(shù)據(jù)的一次掃描）2每讀取大表的一條記錄（大表數(shù)據(jù)的一次掃描），就和小表中內(nèi)存中的數(shù)據(jù)進(jìn)行比較（有了hash函數(shù)，比較就不需要掃描小表），如果符合，則立即輸出數(shù)據(jù)。而如果大表的數(shù)據(jù)與小表中臨時(shí)表空間的數(shù)據(jù)相符合，先不輸出，而等大表的所有數(shù)據(jù)都讀取完畢，才一起輸出（減少讀取硬盤的次數(shù)）。

3.HashJoin方法只需要對(duì)兩個(gè)表進(jìn)行一次掃描，并且極大地降低了讀取硬盤的次數(shù)。AnIntroductiontoDatabaseSystem9.2.1查詢優(yōu)化概述查詢效率是衡量RDBMS重要性能指標(biāo)。RDBMS通過查詢優(yōu)化提升查詢效率。關(guān)系的結(jié)構(gòu)化查詢語言SQL高級(jí)別的語義（只需指出做什么而不必給出怎么做），使RDBMS進(jìn)行查詢優(yōu)化成為可能。RDBMS的查詢優(yōu)化，使用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率。AnIntroductiontoDatabaseSystem系統(tǒng)進(jìn)行優(yōu)化較用戶優(yōu)化的優(yōu)勢(shì)：優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息。如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃而不必重寫程序。優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)。AnIntroductiontoDatabaseSystem查詢優(yōu)化目標(biāo)查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系代數(shù)表達(dá)式的值（關(guān)系），使得查詢代價(jià)最小。查詢執(zhí)行策略的代價(jià)構(gòu)成：

總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)+通信代價(jià)

AnIntroductiontoDatabaseSystem9.2.2查詢優(yōu)化的必要性例：求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';以下考察不同的執(zhí)行策略對(duì)數(shù)據(jù)讀寫上需要的時(shí)間AnIntroductiontoDatabaseSystem查詢優(yōu)化的必要性（續(xù)）假設(shè)：1：Student:1000條，SC:10000條，選修2號(hào)課程:50條2：一個(gè)內(nèi)存塊可存放元組:10個(gè)Student，或100個(gè)SC，內(nèi)存容量可以存放:5塊Student元組、

1塊SC元組和若干塊連接結(jié)果元組3：讀寫速度：20塊/秒4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法

AnIntroductiontoDatabaseSystem執(zhí)行策略1:笛卡爾積、選擇、投影Q1＝sname(бStudent.Sno=SC.Sno∧SC.Cno='2'

(Student×SC))

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

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

讀數(shù)據(jù)時(shí)間=2100/20=105秒每次可讀student的10X5個(gè)元組，然后以塊為單位讀入全部SC，產(chǎn)生笛卡爾積AnIntroductiontoDatabaseSystem中間結(jié)果大小=1000*10000=107

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

（假設(shè)每個(gè)內(nèi)存塊可存放10個(gè)元組的中間結(jié)果）②б

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

③П總時(shí)間=105＋50000＋50000秒=100105秒

=27.8小時(shí)AnIntroductiontoDatabaseSystem執(zhí)行策略2：自然連接、選擇、投影2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))①

讀取總塊數(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執(zhí)行策略3：選擇、自然連接、投影3.Ｑ3＝П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í)間＝5＋5秒＝10秒AnIntroductiontoDatabaseSystem9.3代數(shù)優(yōu)化關(guān)系代數(shù)表達(dá)式：關(guān)系代數(shù)運(yùn)算符經(jīng)過有限次復(fù)合后得到的式子，其值仍為關(guān)系。（P60）關(guān)系代數(shù)表達(dá)式等價(jià)：即關(guān)系代數(shù)表達(dá)式E1和E2中代入相同的關(guān)系，其結(jié)果相同，記為：E1≡E2。AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)表達(dá)式等價(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)

F1

F2

F1

F2AnIntroductiontoDatabaseSystem關(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中的屬性，F(xiàn)2只涉及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，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則：

бF(E1×E2)≡бF2(бF1(E1)×E2)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)AnIntroductiontoDatabaseSystem小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：合并或分解投影運(yùn)算4：合并或分解選擇運(yùn)算5-8：選擇運(yùn)算與其他運(yùn)算交換5，9，10：投影運(yùn)算與其他運(yùn)算交換AnIntroductiontoDatabaseSystem9.3.2關(guān)系代數(shù)的啟發(fā)式的優(yōu)化算法選擇運(yùn)算應(yīng)盡可能先做：選擇運(yùn)算減小了中間關(guān)系中元組數(shù)量在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理按連接屬性排序在連接屬性上建立索引

投影運(yùn)算和選擇運(yùn)算同時(shí)做：在掃描關(guān)系時(shí)同時(shí)進(jìn)行投影運(yùn)算和選擇運(yùn)算，避免重復(fù)掃描關(guān)系將投影運(yùn)算與其前面或后面的雙目運(yùn)算(關(guān)系代數(shù)的運(yùn)算符除投影和選擇外均為雙目運(yùn)算符)一起做。AnIntroductiontoDatabaseSystem某些選擇運(yùn)算同它前面要執(zhí)行的笛卡爾積結(jié)合起來成為連接運(yùn)算，連接運(yùn)算比產(chǎn)生笛卡爾后進(jìn)行選擇運(yùn)算要快的多提取公共子表達(dá)式：可把滿足公共子表達(dá)式的關(guān)系（不太大的情況下）讀入內(nèi)存以提高查詢效率。AnIntroductiontoDatabaseSystem遵循啟發(fā)式規(guī)則，運(yùn)用等價(jià)變換規(guī)則優(yōu)化關(guān)系表達(dá)式的算法：算法：關(guān)系代數(shù)表達(dá)式的優(yōu)化算法輸入：依據(jù)一個(gè)關(guān)系表達(dá)式的查詢樹。算法輸出：優(yōu)化的查詢樹方法：（1）分解選擇運(yùn)算 利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為

бF1(бF2(…(бFn(E))…))，為（2）做準(zhǔn)備。AnIntroductiontoDatabaseSystem關(guān)系代數(shù)表達(dá)式的優(yōu)化算法

(續(xù))（2）對(duì)每一個(gè)選擇運(yùn)算，利用規(guī)則4～8盡可能把它移到樹的葉端。（選擇優(yōu)先）（3）對(duì)每一個(gè)投影運(yùn)算，利用規(guī)則3，5，l0，11中的一般形式盡可能把它移向樹的葉端。（投影優(yōu)先）選擇和投影運(yùn)算均能減少中間結(jié)果，具體哪個(gè)更優(yōu)先，取決于具體關(guān)系中行和列哪個(gè)數(shù)據(jù)量更大。AnIntroductiontoDatabaseSystem（4）利用等價(jià)變化3-5，合并串接的選擇運(yùn)算成一個(gè)選擇運(yùn)算和合并串接的投影運(yùn)算成一個(gè)投影運(yùn)算，以便能在一次掃描中完成運(yùn)算，如：

бA<3(бA<5(E))бA<3(E)

πA1(πA1,A2(E))πA1(E)AnIntroductiontoDatabaseSystem關(guān)系代數(shù)表達(dá)式的優(yōu)化算法

(續(xù))（5）對(duì)內(nèi)結(jié)點(diǎn)（除葉結(jié)點(diǎn)外的所有結(jié)點(diǎn)）分組：每一雙目運(yùn)算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是б，π運(yùn)算)，如下例第1，3組；如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組。如下例第1組。當(dāng)雙目運(yùn)算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時(shí)，可把這些單目運(yùn)算單獨(dú)分為一組。

如下例中注釋部分。每組結(jié)點(diǎn)對(duì)應(yīng)計(jì)算程序中的一步，各步程序的順序可任意，但任何一組的計(jì)算必須在它的父代組之前計(jì)算。如下例中第1和第2組結(jié)果必須在第3組計(jì)算之間產(chǎn)生。AnIntroductiontoDatabaseSystem分組實(shí)例：查詢男同學(xué)選課學(xué)分大于4分的姓名和課程名studentcoursescббπ第1組π第3組第2組π若為“X”，則下面可分成兩組ssex=‘男’Sno,cnosname,cnoCcredit>4Sname,cnameπsno,sname,ssexAnIntroductiontoDatabaseSystem9.4物理優(yōu)化物理優(yōu)化指存取路徑和底層操作算法的選擇，主要研究根據(jù)查詢的不同特點(diǎn)，選擇操作和連接操作中對(duì)9.1.2中各種算法的選擇。有基于啟發(fā)式、基于代價(jià)估算和兩者結(jié)合的優(yōu)化方法。AnIntroductiontoDatabaseSystem基于啟發(fā)式的優(yōu)化：一.選擇操作的優(yōu)化規(guī)則對(duì)于小關(guān)系，不論是否有索引，均使用全表掃描。下面規(guī)則則對(duì)大關(guān)系而言。包含主碼等值的查詢，一定使用主碼索引。包含非主屬性等值查詢，若有關(guān)于該非主屬性的索引，則估算查詢結(jié)果的元組數(shù)量，與整個(gè)元組數(shù)量比例大的話，使用全表掃描，否則使用索引掃描。AnIntroductiontoDatabaseSystem對(duì)and連接的條件，若有相應(yīng)的組合索引，則使用索引掃描；若部分有索引，則先使用索引掃描，選出符合部分條件的元組，在其中再選出符合其他條件的元組。對(duì)or連接的條件，一般使用全表掃描。例如關(guān)于A,B有索引，（notA）or（notB）可優(yōu)化為not(AandB)，事實(shí)上一些DBMS也會(huì)作此優(yōu)化(前者若使用索引，必須兩次全表掃描，而后者一次全表，一次在前一次結(jié)果上再掃描)。……

AnIntroductiontoDatabaseSystem二.連接操作的優(yōu)化規(guī)則連接屬性均排序，使用排序-合并方法僅一個(gè)表的連接屬性有索引，使用索引連接方法。上述條件均不滿足，若一個(gè)表較小，則可以選用Hashjoin方法嵌套循環(huán)方法不需要任何前提條件，但較小的表的掃描應(yīng)作為外循環(huán)，可減少讀塊的次數(shù)。（極端情況下，小表只要讀一次）AnIntroductiontoDatabaseSystem基于代價(jià)估算的優(yōu)化根據(jù)數(shù)據(jù)庫的狀態(tài)計(jì)算各種操作算法的執(zhí)行代價(jià)，選擇代價(jià)最小的算法。執(zhí)行代價(jià)的計(jì)算方法：在數(shù)據(jù)字典中存放優(yōu)化器所需要的統(tǒng)計(jì)信息，如表的元組數(shù)，元組長度、列值個(gè)數(shù)、最大、最小值、列上是否有索引等。根據(jù)以上的統(tǒng)計(jì)信息，計(jì)算各種算法的代價(jià)估值。AnIntroductiontoDatabaseSystem優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示 例：求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';AnIntroductiontoDatabaseSystem（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示語法樹結(jié)果project(Sname)

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

StudentSCAnIntroductiontoDatabaseSystem關(guān)系代數(shù)