第四章關(guān)系系統(tǒng)的查詢優(yōu)化

數(shù)據(jù)庫系統(tǒng)原理第四章關(guān)系系統(tǒng)的查詢優(yōu)化4.1關(guān)系系統(tǒng)4.2查詢優(yōu)化處理數(shù)據(jù)庫系統(tǒng)原理

第四章關(guān)系系統(tǒng)的查詢優(yōu)化學(xué)習(xí)要求

了解關(guān)系系統(tǒng)的基本概念及分類標(biāo)準(zhǔn)，初步了解查詢處理的基本步驟，理解查詢優(yōu)化的意義，掌握關(guān)系代數(shù)優(yōu)化的算法及相應(yīng)的等價變換。學(xué)習(xí)重點

利用關(guān)系優(yōu)化規(guī)則對關(guān)系語法樹進行優(yōu)化。

數(shù)據(jù)庫系統(tǒng)原理第四章關(guān)系系統(tǒng)的查詢優(yōu)化

4.1關(guān)系系統(tǒng)4.2查詢優(yōu)化處理數(shù)據(jù)庫系統(tǒng)原理第一節(jié)關(guān)系系統(tǒng)關(guān)系模型關(guān)系數(shù)據(jù)結(jié)構(gòu)域及域上定義的關(guān)系關(guān)系操作關(guān)系代數(shù)：并、交、差、廣義笛卡爾積、選擇、投影、連接、除等關(guān)系完整性實體完整性、參照完整性、用戶自己定義的完整性關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)(續(xù))關(guān)系系統(tǒng)的定義能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)是關(guān)系系統(tǒng)。定義4.1

一個系統(tǒng)是關(guān)系系統(tǒng)當(dāng)且僅當(dāng)它：支持關(guān)系數(shù)據(jù)庫（即關(guān)系數(shù)據(jù)結(jié)構(gòu)）。從用戶觀點看，數(shù)據(jù)庫是由表構(gòu)成的，并且系統(tǒng)中只有表這種結(jié)構(gòu)。支持選擇、投影和（自然）連接運算。對這些運算不要求用戶定義任何物理存取路徑。關(guān)系系統(tǒng)的查詢優(yōu)化二、關(guān)系系統(tǒng)的分類分類依據(jù)─依據(jù)關(guān)系系統(tǒng)支持關(guān)系模型的程度不同。分類S：結(jié)構(gòu)I：完整性M：數(shù)據(jù)操縱關(guān)系系統(tǒng)的查詢優(yōu)化數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操縱數(shù)據(jù)完整性表式結(jié)構(gòu)表××最小關(guān)系系統(tǒng)表選擇、投影、連接×關(guān)系完備的系統(tǒng)表全部×全關(guān)系系統(tǒng)全部全部完全支持關(guān)系系統(tǒng)的分類（續(xù)）關(guān)系系統(tǒng)的查詢優(yōu)化第二節(jié)關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢處理查詢優(yōu)化概述查詢優(yōu)化問題的提出關(guān)系代數(shù)的優(yōu)化規(guī)則關(guān)系代數(shù)的優(yōu)化算法查詢優(yōu)化的一般步驟關(guān)系系統(tǒng)的查詢優(yōu)化一、關(guān)系系統(tǒng)的查詢處理1、查詢處理步驟關(guān)系系統(tǒng)的查詢優(yōu)化查詢語句轉(zhuǎn)化成關(guān)系代數(shù)表達式關(guān)系系統(tǒng)的查詢處理（續(xù)）2、實現(xiàn)查詢操作的算法示例例4.1選擇操作的實現(xiàn)Select*FromStudentWhere<條件表達式>;<條件表達式>的幾種情況：C1:Sno=‘95001’C2:Sage<20C3:Sdept=‘CS’AndSage>20①簡單的全表掃描方法對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出。關(guān)系系統(tǒng)的查詢優(yōu)化

選擇操作的實現(xiàn)示例（續(xù)）②索引掃描方法

通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組。

【C1例】Sno=’95001’，并且在Sno上有索引，則可以使用索引得到Sno為’95001’元組的指針，然后通過元組指針在Student表中檢索到該學(xué)生。

【C2例】Sage>20，并且Sage上有B+樹索引，則可以使用B+樹索引找到Sage=20的索引項，以此為入口點在B+樹的順序集上得到Sage>20的所有元組指針，然后通過這些元組指針到Student表中檢索到所有年齡大于20的學(xué)生。關(guān)系系統(tǒng)的查詢優(yōu)化Sage>20的一組元組指針【C3例】Sdept=‘CS’AndSage>20，如果Sdept和Sage上都有索引，則：

另一種算法：關(guān)系系統(tǒng)的查詢優(yōu)化

選擇操作的實現(xiàn)示例（續(xù)）Sdept=‘CS’的一組元組指針Sdept=‘CS’的一組元組指針Sdept=‘CS’的一組元組指針Sage>20的一組元組指針指針交集滿足條件的學(xué)生信息Student表Student表Sage>20的一組元組指針滿足條件的學(xué)生信息滿足Sdept=‘CS’條件的元組信息實現(xiàn)查詢操作的算法示例（續(xù)）例4.2連接操作的實現(xiàn)

Select*FromStudent,SCWhereStudent.Sno=SC.Sno①嵌套循環(huán)方法

關(guān)系系統(tǒng)的查詢優(yōu)化學(xué)號Sno姓名Sname性別Ssex年齡Sage所在系Sdept95002950019500395004李勇劉晨王敏張立男女女男20191819CSISMAISStudent學(xué)號Sno課程號Cno成績Grade9500195002950019500295002123239290888580SC對Student中的每一個元組，檢查SC中的每一個元組，若在連接屬性上相等，則連接輸出，直到Student中的元組處理完為止。連接操作的實現(xiàn)（續(xù)）②排序-合并方法學(xué)號Sno姓名Sname性別Ssex年齡Sage所在系Sdept95001950029500395004李勇劉晨王敏張立男女女男20191819CSISMAISStudent學(xué)號Sno課程號Cno成績Grade9500195001950019500295002123239285889080SC關(guān)系系統(tǒng)的查詢優(yōu)化取Student表中第一個Sno，依次掃描SC表中具有相同Sno的元組，把他們連接起來；當(dāng)掃描到Sno不相同的第一個SC元組時，返回Student表掃描它的下一個元組，再掃描SC表中具有相同Sno的元組，把它們連接起來。二、查詢優(yōu)化概述

查詢優(yōu)化是從眾多可供選擇的執(zhí)行策略和操作算法中，選擇一個高效執(zhí)行的查詢處理策略。

按照優(yōu)化的層次可以分為代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化：是指關(guān)系代數(shù)表達式的優(yōu)化，按照一定的規(guī)則，改變代數(shù)表達式中操作的次序和組合，使查詢執(zhí)行效率更高。物理優(yōu)化：則是指存取路徑和底層操作算法的選擇。關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述（續(xù)）目前RDBMS通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代價，然后選取代價最小的執(zhí)行方案。查詢的執(zhí)行開銷主要包括集中式數(shù)據(jù)庫磁盤存取塊數(shù)（I/O代價）處理機時間（CPU代價）查詢的內(nèi)存開銷分布式數(shù)據(jù)庫I/O代價+CPU代價+內(nèi)存代價+通信代價查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系表達式的值，使得查詢代價最小。關(guān)系系統(tǒng)的查詢優(yōu)化三、查詢優(yōu)化問題的提出例4.3：求選修了2號課程的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.SnoANDSC.Cno='2';系統(tǒng)可以用多種等價的關(guān)系代數(shù)表達式來完成這一查詢。

關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化問題的提出（續(xù)）假設(shè)1外存：

Student表中有1000條學(xué)生記錄

SC表中有10000條選課記錄 其中選修2號課程的選課記錄為50條假設(shè)2內(nèi)存： 一個內(nèi)存塊可以裝10個Student元組或100個SC元組 一個內(nèi)存塊可以裝10個Student和SC的連接結(jié)果元組 內(nèi)存中一次可以存放5塊Student元組、1塊SC元組和若干塊連接結(jié)果元組假設(shè)3讀寫速度：20塊/秒假設(shè)4連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法關(guān)系系統(tǒng)的查詢優(yōu)化1、第一種方法關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化問題的提出（續(xù)）

內(nèi)存塊100Student表SC表…………內(nèi)存塊1內(nèi)存塊2內(nèi)存塊3內(nèi)存塊4內(nèi)存塊5一般連接的方法：內(nèi)存塊1內(nèi)存塊2內(nèi)存塊100讀Student表100塊，讀SC表20遍，每遍100塊。①計算廣義笛卡爾集Student×SC讀取總塊數(shù)=讀Student表塊數(shù)+讀SC表遍數(shù)*每遍塊數(shù)

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100讀數(shù)據(jù)時間=2100/20=105秒中間結(jié)果大?。ㄟB接后的元組數(shù)）=1000*10000=107

(1千萬條元組)寫中間結(jié)果時間=10000000/10/20=50000秒②選擇操作讀數(shù)據(jù)時間=50000秒

③投影操作

總時間=105＋50000＋50000秒=100105秒=27.8小時關(guān)系系統(tǒng)的查詢優(yōu)化第一種方法（續(xù)）2、第二種方法①計算自然連接

讀取總塊數(shù)=2100塊

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

②選擇操作

讀取中間文件塊，執(zhí)行選擇運算，花費時間50秒

③投影操作

把第二步的結(jié)果投影輸出

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

關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化問題的提出（續(xù)）3、第三種方法Q3=πSname(Student

SC.Cno=‘2’(SC))①選擇操作

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

中間結(jié)果大小=50條（滿足條件的元組只有50個），不必使用中間文件。②自然連接操作 讀Student表總塊數(shù)=1000/10=100塊（只需讀一遍該表） 讀數(shù)據(jù)時間=100/20=5秒

③投影操作

把連接結(jié)果投影輸出。

總時間＝5＋5秒＝10秒關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化問題的提出（續(xù)）四、關(guān)系代數(shù)的優(yōu)化規(guī)則關(guān)系代數(shù)優(yōu)化策略是通過對關(guān)系代數(shù)表達式的等價變換來提高查詢效率。關(guān)系代數(shù)表達式等價指把相同的關(guān)系代入兩個關(guān)系代數(shù)表達式所得到的結(jié)果是相同的。兩個關(guān)系表達式E1和E2是等價的，記為E1≡E2。關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)的優(yōu)化規(guī)則（續(xù)）1、常用的等價變換規(guī)則設(shè)E1、E2是關(guān)系代數(shù)表達式，F(xiàn)是條件表達式。（1）連接、笛卡爾積交換律E1×E2≡E2×E1

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

關(guān)系系統(tǒng)的查詢優(yōu)化FFF1F1F2F2常用的等價變換規(guī)則（續(xù)）（3）投影的級聯(lián)（串接定律）假設(shè)：

1)E是關(guān)系代數(shù)表達式

2)Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名

3){A1,A2,…,An}是{Bl，B2，…，Bm}的子集。則：（4）選擇的級聯(lián)（串接定律）選擇的串接律說明選擇條件可以合并。關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)等價變換規(guī)則（續(xù)）（5）選擇與投影的交換律假設(shè):選擇條件F只涉及屬性A1，…，An假設(shè):F中有不屬于A1,…,An的屬性B1,…,Bm

關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)等價變換規(guī)則（續(xù)）（6）選擇與笛卡爾積的交換律假設(shè)：F中涉及的屬性都是E1中的屬性，則

假設(shè)：F=F1∧F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價變換規(guī)則1，4，6可推出 假設(shè)：F=F1∧F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則

關(guān)系系統(tǒng)的查詢優(yōu)化F

(

E1×E2)≡F1∧F2(E1×E2)≡F2

(F1

(E1×E2))

≡F2

(F1

(E1)×E2)F

(

E1×E2)≡F1∧F2(E1×E2)≡F1

(F2

(E1×E2))

≡F1

(F2

(E2)×E1)

≡F1

(E1)×F2

(E2)

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

（8）選擇與差運算的分配律 假設(shè)：E1與E2有相同的屬性名（9）選擇對自然連接的分配律

假設(shè)：F只涉及E1和E2的公共屬性

F(E1

E2)≡F(E1)F(E2)

關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)等價變換規(guī)則（續(xù)）（10）投影與笛卡爾積的分配律 假設(shè)：E1和E2是兩個關(guān)系表達式，A1，…，An是E1的屬性，B1，…，Bm是E2的屬性，則（11）投影與并的分配 假設(shè)：E1和E2

有相同的屬性名，則

關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)等價變換規(guī)則小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：投影運算的合并或分解4：選擇運算的合并或分解5-6：選擇運算與其他運算的交換律7-9：選擇運算與其他運算的分配律10-11：投影運算與其他運算的分配律關(guān)系系統(tǒng)的查詢優(yōu)化2、關(guān)系代數(shù)的優(yōu)化規(guī)則（1）選擇運算應(yīng)盡可能先做。目的：減少中間結(jié)果大?。?）投影運算和選擇運算同時做。目的：避免重復(fù)掃描關(guān)系（3）將投影運算與其前面或后面的雙目運算結(jié)合。目的：減少掃描關(guān)系的遍數(shù)。關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)等價變換規(guī)則（續(xù)）查詢優(yōu)化的一般準(zhǔn)則（續(xù)）（4）把某些選擇同在它前面執(zhí)行的笛卡兒積結(jié)合起來成為一個連接運算。例：Student.Sno=SC.Sno

(Student×SC)

StudentSC

例4.3中：關(guān)系系統(tǒng)的查詢優(yōu)化（5）提取公共子表達式。一個關(guān)系表達式如果包含多個相同的子表達式，那么只需計算一次公共表達式，把所得的中間結(jié)果存起來，以后每遇到這種子表達式，只需檢索中間結(jié)果而無須重新計算。關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的一般準(zhǔn)則（續(xù)）五、關(guān)系代數(shù)的優(yōu)化算法1、查詢樹在查詢優(yōu)化過程中，查詢語句被轉(zhuǎn)換為更適合處理的內(nèi)部表示，通常這種內(nèi)部表示表現(xiàn)為查詢樹的形式，它的構(gòu)造方法如下:（1）每一個葉節(jié)點對應(yīng)于查詢中的基本關(guān)系;（2）非葉節(jié)點是關(guān)系代數(shù)運算產(chǎn)生的中間關(guān)系;（3）樹的根節(jié)點代表查詢結(jié)果;（4）運算按照從葉到根的順序執(zhí)行。關(guān)系系統(tǒng)的查詢優(yōu)化查詢樹（續(xù)）例4.3中的關(guān)系代數(shù)表達式：轉(zhuǎn)化為查詢樹：關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)的優(yōu)化算法（續(xù)）2、關(guān)系表達式的優(yōu)化算法輸入：一個關(guān)系表達式的查詢樹。輸出：優(yōu)化的查詢樹。方法：1．分解選擇運算。2．通過交換選擇運算，將其盡可能移到葉端。3．通過交換投影運算，將其盡可能移到葉端。4．合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成。5．對內(nèi)結(jié)點分組。6．生成程序。關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)的優(yōu)化算法(續(xù))（1）分解選擇運算。

利用規(guī)則4把形如F1∧F2∧…∧Fn(E)變換為

F1(F2(…(Fn(E))…))（2）通過交換選擇運算，將其每個選擇盡可能移到葉端。對每一個選擇，利用規(guī)則4～9盡可能把它移到樹的葉端。（3）通過交換投影運算，將其盡可能移到葉端。

對每一個投影利用規(guī)則3，5，l0，11中的一般形式盡可能把它移向樹的葉端。關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（4）合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成。利用規(guī)則3～5把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行,或在一次掃描中全部完成。盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（5）對內(nèi)結(jié)點分組把上述得到的語法樹的內(nèi)節(jié)點分組。每一雙目運算(×,,∪,-)和它所有的直接祖先（,π運算）為一組。如果其后代直到葉子全是單目運算，則也將它們并入該組，但當(dāng)雙目運算是笛卡爾積(×)而且其后的選擇不能與它結(jié)合為等值連接時除外。把這些單目運算單獨分為一組。關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（6）生成程序生成一個程序，每組結(jié)點的計算是程序中的一步。各步的順序是任意的，只要保證任何一組的計算不會在它的后代組之前計算。

關(guān)系系統(tǒng)的查詢優(yōu)化例4.4給出例4.3中SQL語句的代數(shù)優(yōu)化算法。（1）把SQL語句轉(zhuǎn)換成查詢樹，對應(yīng)的關(guān)系表達式為：

關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))關(guān)系代數(shù)查詢樹關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))πSname

Student.Sno=SC.Sno

∧SC.Cno=2

×

StudentSC（2）對查詢樹進行優(yōu)化①分解選擇運算，對應(yīng)的關(guān)系代數(shù)表達式為:

Sname(σ

Student.Sno=SC.Sno(σ

SC.Cno=2

(Student×SC)));關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))πSname

SC.Cno=2

×

Stud