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

9.1關系數(shù)據(jù)庫系統(tǒng)的查詢處理第九章關系查詢處理和查詢優(yōu)化9.2關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.5小結9.1.1查詢處理的步驟RDBMS查詢處理可以分為4個階段：查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行9.1關系數(shù)據(jù)庫系統(tǒng)的查詢處理查詢處理的任務是把用戶提交給RDBMS的查詢語句轉換為高效的執(zhí)行計劃。1、查詢分析對查詢語句進行掃描、詞法分析和語法分析，

即判斷查詢語句是否符合SQL的語法規(guī)則。2、查詢檢查（1）根據(jù)數(shù)據(jù)字典對合法的查詢語句進行語義檢查。檢查語句中的數(shù)據(jù)庫對象（如屬性名、關系名）

是否存在和是否有效。（2）根據(jù)數(shù)據(jù)字典中的用戶權限和完整性約束定義對用戶的存取權限進行檢查。（3）將檢查通過的查詢語句轉換成等價的關系代數(shù)

表達式。（語法分析樹）3、查詢優(yōu)化(QueryOptimization)每個查詢都會有許多可供選擇的執(zhí)行策略和操作算法，查詢優(yōu)化就是選擇一個高效執(zhí)行的查詢策略。查詢優(yōu)化有多種途徑：（1）代數(shù)優(yōu)化將查詢語句轉換成為相應的關系代數(shù)表達式，然后按照一定的規(guī)則，改變關系代數(shù)表達式的操作次序和組合進行優(yōu)化，借此來改變基本操作的次序，使查詢語句執(zhí)行起來更有效。這種查詢優(yōu)化僅涉及查詢語句本身，而不涉及存取路徑，是獨立于存取路徑的優(yōu)化。（2）物理優(yōu)化根據(jù)系統(tǒng)提供的存取路徑，選擇合理的存取路徑

和底層操作算法(例如選用順序搜索或索引進行查找)，

是依賴于存取路徑的優(yōu)化。（3）規(guī)則優(yōu)化查詢的優(yōu)化僅根據(jù)啟發(fā)式規(guī)則選擇執(zhí)行的策略。（4）代價估算優(yōu)化對各種可供選擇的策略進行代價估算，從中選用代價最小的執(zhí)行策略。實際RDBMS中的查詢優(yōu)化器都綜合運用了這些優(yōu)化技術，以獲得最好的查詢優(yōu)化效果。4、查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計劃，由代碼生成器（codegenerator）生成執(zhí)行這個查詢計劃的代碼。9.1.2實現(xiàn)查詢操作的算法示例本節(jié)簡單介紹實現(xiàn)選擇操作和連接操作的幾種主要算法。一、選擇操作的實現(xiàn)[例１]

Select*fromstudentwhere<條件表達式>考慮<條件表達式>的幾種情況：

C1:

無條件；

C2:Sno=‘200215121’；

C3:Sage>20;

C4:Sdept=‘CS’ANDSage>20;對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇條件，把滿足條件的元組作為結果輸出。對于小表，這種方法簡單有效。對于大表，順序掃描十分費時，效率很低。1、簡單的全表掃描方法如果選擇條件中的屬性上有索引（例如Ｂ＋樹索引或者Ｈash索引），可以用索引掃描方法。通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組。2、索引（或散列）掃描方法[例1-C3]以C3為例，Sage>20,并且Sage上有B+樹

索引。可以使用B+樹索引找到Sage＝20的索引項，以此為入口點在B+樹的順序集上得到Sage>20的所有元組指針，然后通過這些元組指針到student表中檢索所有年齡大于20的學生。[例1-C2]以C2為例，Sno=‘200215121’，并且Sno

上有索引?？梢允褂盟饕玫絊no為‘200215121’元組的指針，然后通過元組指針在student表中檢索到該學生。[例1-C4]以C4為例，Sdept=‘CS’ANDSage>20,

假設Sdept和Sage上都有索引。算法1：分別用上面兩種方法分別找到Sdept=‘CS’

的一組元組指針和Sage>20的另一組元組指

針，求這２組指針的交集，再到student表中

檢索。算法2：找到Sdept=‘CS’的一組元組的指針，通

過這些元組指針到student表中檢索，并

對得到的元組檢查另一個選擇條件

（Sage>20）是否滿足，把滿足條件的元組作

為結果輸出。二、連接操作的實現(xiàn)連接操作是查詢處理中最耗時的操作之一。不失一般性，這里只討論等值連接（或自然連接）最常用的實現(xiàn)算法。[例２]SELECT*FROMStudent,SC

WHEREStudent.Sno＝SC.Sno算法１：嵌套循環(huán)方法這是最簡單可行的算法。對外層循環(huán)（Student）

的每一個元組（s），檢索內層循環(huán)（SC）中的每一

個元組（sc），并檢查這兩個元組在連接屬性（Sno）上是否相等。如果滿足連接條件，則串接后作為結果輸，直到外層循環(huán)表中的元組處理完畢為止。算法２：排序－合并方法這也是常用的算法，尤其適合連接的諸表已經排好序的情況。步驟如下：（１）如果連接的表沒有排好序，首先對兩個表都按

連接屬性Sno排序。（２）取Student表中第一個Sno，依次掃描SC表中具

有相同Sno的元組；把它們連接起來（如圖）；95001…95002…95003……9500119295001285950013889500229095002380…（３）當掃描到Sno不相同的第一個SC元組時，返回到Student表掃描它的下一個元組，再掃描SC表中具有相同Sno的元組，把它們連接起來。95001…95002…95003……9500119295001285950013889500229095002380…重復上述步驟直到Student表掃描完畢。這樣Student表和SC表只要掃描一遍。當然，如果２個表原來無序，執(zhí)行時間還要加上對兩個表的排序時間。即使這樣，對于２個大表，先排序后使用sort-mergejoin方法執(zhí)行連接，總的時間一般仍會大大減少。算法３：索引連接方法（１）在SC表上建立屬性Sno的索引（沒有的話）；（２）對Student表中每一個元組，由Sno值通過SC的索引查找相應的SC元組；（３）把這些SC元組和Student表中的元組連接起來。循環(huán)執(zhí)行（２）（３），直到Student表中的元組處理完為止。算法4：HashJoin方法把連接屬性Sno作為Hash碼，用同一個hash函數(shù)

把R和S中的元組散列到同一個hash文件中。第一步，劃分階段，對包含較少元組的表（比如

R）進行一遍處理，把它的元組按hash函數(shù)分散到

hash表的桶中；第二步，試探階段，也稱為連接階段，對另一個

表（S）進行一遍處理，把S的元組散列到適當?shù)膆ash

桶中，并把元組與桶中所有來自R并與之相匹配的元

組連接起來。備注：上述hash

join算法假設兩個表中較小的表在第一階段后完全放入內存的hash桶中。9.2關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

9.2.1查詢優(yōu)化概述■關系系統(tǒng)的查詢優(yōu)化既是RDBMS實現(xiàn)的關鍵技術，也是關系系統(tǒng)的優(yōu)點所在。它減輕了用戶選擇存取路徑的負擔，用戶只須提出“干什么”，而不必指出“怎么干”?！霾樵儍?yōu)化的優(yōu)點不僅在于用戶不必考慮如何最好地表達查詢以獲得最高效率，而且還在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好。關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2一、由RDBMS進行查詢優(yōu)化的好處：(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而

用戶程序則難以獲得這些信息。(2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應的執(zhí)行計劃。在非關系系統(tǒng)中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員

一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復雜的優(yōu)化技術。關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2二、查詢優(yōu)化目標及步驟１、查詢優(yōu)化的總目標選擇有效策略，求得給定關系表達式的值，使得查詢代價最?。ㄝ^?。＃?、實際系統(tǒng)的查詢優(yōu)化步驟1）

將查詢轉換成某種內部表示，通常是語法樹。2）根據(jù)一定的等價變換規(guī)則把語法樹轉換成標準

（優(yōu)化）形式。3）選擇低層的操作算法對于語法樹中的每一個操作：（１）計算各種執(zhí)行算法的執(zhí)行代價；（２）選擇代價小的執(zhí)行算法；關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.24）生成查詢計劃(查詢執(zhí)行方案)查詢計劃是由一系列內部操作組成的。代價計算公式如下：▄集中式數(shù)據(jù)庫

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

?多用戶系統(tǒng)總代價=I/O代價+CPU代價+內存代價一般地，集中式數(shù)據(jù)庫中I/O代價是最主要的。▄分布式數(shù)據(jù)庫總代價=I/O代價+CPU代價+內存代價+通信代價關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化一個實例通過一個簡單的例子，說明為什么要進行查詢優(yōu)化?！纠场浚呵筮x修了2號課程的學生姓名。

用SQL語言實現(xiàn)如下：

SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;假設學生－課程庫中有：1000條Student記錄

10000條SC記錄

其中，50條選修2號課程記錄。關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2系統(tǒng)可用下列3種等價的關系代數(shù)表達式來實現(xiàn)這一查詢操作。到底哪一種策略效率最優(yōu)？關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2假設1、外存：

Student：1000條

SC：10000條

其中，選修2號課程：50條2、一個內存塊可以裝元組:

10個Student,或100個SC

內存中一次可以存放:5塊Student元組,1塊SC元組,

10塊連接結果元組3、讀寫速度：20塊/秒4、連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2①Student×SC

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

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

讀數(shù)據(jù)時間=2100/20=105秒關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2②中間結果寫入內存時間（處理時間忽略不計）中間結果大小=1000*10000=107寫中間結果時間

=107/10/20=50000秒③бStudent.Sno=SC.Sno∧SC.Cno=‘2’時間讀入中間結果時間

（處理時間忽略不計）

讀數(shù)據(jù)時間

=50000秒（結果為50條元組，直接放在內存，不消耗存取時間）④時間：處理時間忽略不計，為０。關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2⑤總時間

=105＋50000＋50000

=100105秒=27.8小時關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2①StudentSC時間讀取總塊數(shù)=1000/10+(1000/(10×5))×(10000/100)=2100塊讀數(shù)據(jù)時間=2100/20=105秒②中間結果寫入內存時間（處理時間忽略不計）中間結果大小=10000（減少1000倍）寫中間結果時間=10000/10/20=50秒

關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2③бSC.Cno=‘2’時間讀入中間結果時間

（處理時間忽略不計）

讀數(shù)據(jù)時間

=50秒（結果為50條元組，直接放在內存，不消耗存取時間）④時間：處理時間忽略不計，為０。⑤總時間

=105＋50＋50

=205秒=3.4分鐘關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2①б時間

讀SC表總塊數(shù)（一遍）=10000/100=100塊

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

（中間結果大小=50條不必寫入外存，不耗時

）②自然連接時間 讀Student表總塊數(shù)（一遍）=1000/10=100塊

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

③總時間＝5＋5秒＝10秒

關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2三種執(zhí)行策略中，第三種最優(yōu)?。。∵@充分說明了查詢優(yōu)化的必要性?。。槭裁?？從中我們可以發(fā)現(xiàn)什么規(guī)律？？？關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2把代數(shù)表達式Q1變化成Q2、Q3，即有選擇和連接操作時，應當先做選擇操作，這樣連接的元組就可以大大減少，這就是代數(shù)優(yōu)化。在Q3中，SC表的選擇操作算法有全表掃描和索引掃描2種方法，經過初步估算，索引掃描方法較優(yōu)。同樣對于Student和SC的連接，利用Student表上的索引，采用indexjoin代價也較小，這就是物理優(yōu)化。SQL查詢語句代數(shù)表達式代數(shù)優(yōu)化物理優(yōu)化執(zhí)行轉換關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2（局限性）9.3代數(shù)優(yōu)化

9.3.1關系代數(shù)表達式等價變換規(guī)則代數(shù)優(yōu)化9.3關系代數(shù)表達式等價：用相同的關系代替兩個表達式

中相應的關系所得到的結果相同。兩個關系表達式E1、E2等價，記為：E1≡E2下面介紹常用的關系代數(shù)等價變換規(guī)則常用的關系代數(shù)等價變換規(guī)則代數(shù)優(yōu)化—

等價變化規(guī)則9.31.連接、笛卡爾積交換律

設E1、E2為關系代數(shù)表達式，F(xiàn)為連接運算的條件。

E1×E2≡E2×E1

E1∞E2≡E2∞E1

E1∞E2≡E2∞E1FF2.連接、笛卡爾積的結合律

設E1、E2、E3為關系代數(shù)表達式，F(xiàn)1、F2為連接運

算的條件。(E1×E2)×E3≡E1×(E2×E3)(E1∞E2)∞E3≡E1∞(E2∞E3)(E1∞E2)∞E3≡E1∞(E2∞E3)F1F2F1F2

3.投影的串接定律

πA1,A2,…,An(πB1,B2,…,Bm(E))≡πA1,A2,…,An(E)這里，E是關系代數(shù)表達式。屬性組{A1,A2,…,An}是屬性組{B1,B2,…,Bm}的子集。如：πsno(πsno,sname(Stuent))≡πsno(Stuent)代數(shù)優(yōu)化—

等價變化規(guī)則9.34.選擇的串接定律

σF1(σF2(E))≡σF1∧F2(E)如：σJNO=‘J1’(σPNO=‘P1’(SPJ))≡σJNO=‘J1’∧PNO=‘P1’(SPJ)5.選擇與投影的交換律

σF(πA1,A2,…,An(E))≡πA1,A2,…,An

(σF(E))這里，選擇條件F只涉及屬性A1,A2,…,An。代數(shù)優(yōu)化—

等價變化規(guī)則9.3若F中有不屬于A1,A2,…,An的屬性B1,B2,…,Bm,則πA1,A2,…,An(σF(E))

≡πA1,A2,…,An(σF(πA1,A2,…,An,B1,B2,…,Bm(E)))

6.選擇與笛卡爾積的交換律

1）若F中涉及的屬性都是E1中的屬性,則

σF(E1×E2)≡σF(E1)×E2

2）若F=F1∧F2，且F1只涉及E1中的屬性，F(xiàn)2只涉及E2

中的屬性，則

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

代數(shù)優(yōu)化—

等價變化規(guī)則9.3

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

它使部分笛卡爾積先做。3）若F=F1∧F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及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)代數(shù)優(yōu)化—

等價變化規(guī)則9.39.選擇對自然連接的分配律

σF(E1∞E2)≡σF(E1)∞σF(E2)10.投影與笛卡爾積的分配律

設A1,…,An是關系表達式E1的屬性，B1,…,Bm是關系表達式E2的屬性

πA1,…,An,B1,…,Bm

(E1×E2)≡πA1,…,An(E1)×πB1,…,Bm(E2)代數(shù)優(yōu)化—

等價變化規(guī)則9.311.投影與并的分配律

設E1和E2具有相同的屬性名

πA1,…,An(E1∪E2)≡πA1,…,An(E1)∪πA1,…,An(E2)9.3.2查詢樹的啟發(fā)式優(yōu)化代數(shù)優(yōu)化—啟發(fā)式規(guī)則9.3本節(jié)討論應用啟發(fā)式規(guī)則的代數(shù)優(yōu)化。這是對關系代數(shù)表達式的查詢樹進行優(yōu)化的方法。典型的啟發(fā)式優(yōu)化規(guī)則有：一、選擇運算應盡可能先做。

在優(yōu)化策略中這是最重要、最基本的一條。因為選擇運算一般能使計算的中間結果大大減少，所以常?？墒箞?zhí)行查詢的時間降低幾個數(shù)量級。二、將投影運算和選擇運算同時進行。三、將投影同其前或其后的雙目運算結合起來，

沒有必要為了去掉某些字段而掃描一遍關系四、將某些選擇運算同在其前面要執(zhí)行的笛

卡爾積運算結合起來成為一個連接運算。五、找出公共子表達式。先求出公共子表達式的值，然后將此值存入中間文件中。代數(shù)優(yōu)化—啟發(fā)式規(guī)則9.3σStudent.Sno=SC.Sno(Student×SC)Student∞SC代數(shù)優(yōu)化—

等價變化規(guī)則9.3【例３】：求選修了2號課程的學生姓名。

用SQL語言實現(xiàn)如下：

SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;代數(shù)優(yōu)化示例一、將查詢轉換成某種內部表示“內部表示”一般采用語法樹。結果Project(Sname)Select(SC.Cno=‘2’)join(Student.Sno=SC.Sno)StudentSC

為了進一步使用關系代數(shù)表達式的優(yōu)化準則，須將以上語法樹轉換成關系代數(shù)語法樹。πSnameσSC.Cno=‘2’σStudent.Sno=SC.Sno×StudentSC二、將語法樹轉換成標準優(yōu)化形式πSnameσSC.Cno=‘2’σStudent.Sno=SC.Sno×StudentSCπSname(Student∞σSC.Cno=‘2’(SC)）9.4物理優(yōu)化代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑對于一個查詢語句有許多存取方案，它們的執(zhí)行效率不同，僅僅進行代數(shù)優(yōu)化是不夠的物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計劃選擇的方法：基于規(guī)則的啟發(fā)式優(yōu)化基于代價估算的優(yōu)化兩者結合的優(yōu)化方法9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化一、選擇操作的啟發(fā)式規(guī)則:1.對于小關系，使用全表順序掃描，即使選

擇列上有索引對于大關系，啟發(fā)式規(guī)則有：2.對于選擇條件是主碼＝值的查詢查詢結果最多是一個元組，可以選擇主碼索引一般的RDBMS會自動建立主碼索引。3.對于選擇條件是非主屬性＝值的查詢，并且選擇列

上有索引要估算查詢結果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描4.對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引要估算查詢結果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描

5.對于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引,則優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引，則可以用［例1-C4］中介紹的索引掃描方法，否則使用全表順序掃描。

6.對于用OR連接的析取選擇條件，一般使用全表順序掃描二、連接操作的啟發(fā)式規(guī)則：

1.如果2個表都已經按照連接屬性排序選用排序-合并方法

2.如果一個表在連接屬性上有索引選用索引連接方法

3.如果上面2個規(guī)則都不適用，其中一個表較小選用Hashjoin方法

4.可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表)。理由：設連接表R與S分別占用的塊數(shù)為Br與Bs連接操作使用的內存緩沖區(qū)塊數(shù)為K分配K-1塊給外表如果R為外表，則嵌套循環(huán)法存取的塊數(shù)為Br+(Br/K-1)Bs顯然應該選塊數(shù)小的表作為外表9.4.2基于代價的優(yōu)化

啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之中編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開的可以采用精細復雜一些的基于代價的優(yōu)化方法一、統(tǒng)計信息基于代價的優(yōu)化方法要計算各種操作算法的執(zhí)行代價，與數(shù)據(jù)庫的狀態(tài)密切相關數(shù)據(jù)字典中存儲的優(yōu)化器需要的統(tǒng)計信息：1.對每個基本表該表的元組總數(shù)(N)元組長度(l)占用的塊數(shù)(B)占用的溢出塊數(shù)(BO)

2.對基表的每個列該列不同值的個數(shù)(m)選擇率(f)如果不同值的分布是均