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

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

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

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

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

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

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

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

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

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';以下考察不同的執(zhí)行策略對數(shù)據(jù)讀寫上需要的時間AnIntroductiontoDatabaseSystem查詢優(yōu)化的必要性（續(xù)）假設：1：Student:1000條，SC:10000條，選修2號課程:50條2：一個內(nèi)存塊可存放元組:10個Student，或100個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ù)時間=2100/20=105秒每次可讀student的10X5個元組，然后以塊為單位讀入全部SC，產(chǎn)生笛卡爾積AnIntroductiontoDatabaseSystem中間結(jié)果大小=1000*10000=107

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

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

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

③П總時間=105＋50000＋50000秒=100105秒

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

讀取總塊數(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執(zhí)行策略3：選擇、自然連接、投影3.Ｑ3＝ПSname(StudentбSC.Cno='2'(SC))

①б

讀SC表總塊數(shù)=10000/100=100塊 讀數(shù)據(jù)時間=100/20=5秒

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

② 讀Student表總塊數(shù)=1000/10=100塊 讀數(shù)據(jù)時間=100/20=5秒

③П

總時間＝5＋5秒＝10秒AnIntroductiontoDatabaseSystem9.3代數(shù)優(yōu)化關系代數(shù)表達式：關系代數(shù)運算符經(jīng)過有限次復合后得到的式子，其值仍為關系。（P60）關系代數(shù)表達式等價：即關系代數(shù)表達式E1和E2中代入相同的關系，其結(jié)果相同，記為：E1≡E2。AnIntroductiontoDatabaseSystem9.3.1關系代數(shù)表達式等價變換規(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)

F1

F2

F1

F2AnIntroductiontoDatabaseSystem關系代數(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}構(gòu)成{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中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價變換規(guī)則1，4，6可推出：

бF(E1×E2)≡бF1(E1)×бF2(E2)

AnIntroductiontoDatabaseSystem關系代數(shù)等價變換規(guī)則（續(xù)）(3)假設：F=F1∧F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則：

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

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

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

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

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

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

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

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

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

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關系代數(shù)