[計算機]數(shù)據(jù)庫系統(tǒng)實現(xiàn)ppt課件

1、第六章查詢執(zhí)行查詢執(zhí)行1.一種查詢代數(shù)一種查詢代數(shù)2.物理查詢計劃操作符介紹物理查詢計劃操作符介紹3.數(shù)據(jù)庫操作的一趟算法數(shù)據(jù)庫操作的一趟算法4.嵌套循環(huán)連接嵌套循環(huán)連接5.基于排序的兩趟算法基于排序的兩趟算法6.基于散列的兩趟算法基于散列的兩趟算法7.基于索引的算法基于索引的算法8.緩沖區(qū)管理緩沖區(qū)管理9.使用超過兩趟的算法使用超過兩趟的算法引言主要任務(wù): 1)對使用諸如SQL的某種語言所寫的查詢進行語法分析,也即將 查詢語句 轉(zhuǎn)換成按某種有用方式表示查詢語句結(jié)構(gòu)的語法樹. 2)將語法分析樹轉(zhuǎn)換成關(guān)系代數(shù)表達式樹(或某種類似標記形 式),也稱為邏輯查詢計劃 3)邏輯查詢計劃轉(zhuǎn)換為物理查詢計劃

2、: a)指明要執(zhí)行的操作 b)找出這些操作執(zhí)行的順序 c)執(zhí)行每步所用的算法 d)獲得所存儲數(shù)據(jù)的方法 e)數(shù)據(jù)從一個操作傳遞到另一個操作的方式查詢處理器的主要組成部分: 查詢 查詢計劃 元數(shù)據(jù) 數(shù)據(jù) 查詢編譯查詢執(zhí)行DB DBMS處理查詢計劃的過程是這樣的： 在做完查詢語句的詞法、語法檢查之后，將語句提交給DBMS的查詢優(yōu)化器，優(yōu)化器做完代數(shù)優(yōu)化和存取路徑的優(yōu)化之后，由預(yù)編譯模塊對語句進行處理并生成查詢規(guī)劃，然后在合適的時間提交給系統(tǒng)處理執(zhí)行，最后將執(zhí)行結(jié)果返回給用戶。 在實際的數(shù)據(jù)庫產(chǎn)品(如Oracle、Sybase等)的高版本中都是采用基于代價的優(yōu)化方法，這種優(yōu)化能根據(jù)從系統(tǒng)字典表所得到

3、的信息來估計不同的查詢規(guī)劃的代價，然后選擇一個較優(yōu)的規(guī)劃。 雖然現(xiàn)在的數(shù)據(jù)庫產(chǎn)品在查詢優(yōu)化方面已經(jīng)做得越來越好，但由用戶提交的SQL語句是系統(tǒng)優(yōu)化的基礎(chǔ)，很難設(shè)想一個原本糟糕的查詢計劃經(jīng)過系統(tǒng)的優(yōu)化之后會變得高效，因此用戶所寫語句的優(yōu)劣至關(guān)重要。DBMS中的存儲統(tǒng)計信息:有關(guān)關(guān)系的統(tǒng)計信息關(guān)系R R中的元組數(shù)目含有關(guān)系R R的元組的塊數(shù)目關(guān)系R R中每個元組的字節(jié)數(shù)關(guān)系R R的塊因子，即一個塊中能存放的關(guān)系 統(tǒng)計信息的維護 每次關(guān)系修改時，更新統(tǒng)計信息 系統(tǒng)處于輕負載時，更新統(tǒng)計信息查詢處理的步驟:語法分析器與翻譯器查詢關(guān)系代數(shù)表達式優(yōu)化器執(zhí)行引擎查詢結(jié)果執(zhí)行計劃db分析: 例:SELECT

4、SNAME FROM S,C,SC WHERE S.SNO=SC.SNO AND C.CNO=SC.CNO AND C.CNAME=DATABASE SYSTEM S=10000,C=1000,SC=100000 查詢方案: 1) sname( S.SNO=SC.SNO AND(sXc)Xsc) C.CNO=SC.CNO AND C.CNAME=DATABASE SYSTEM) 2) sname(C.CNAME=DATABASE SYSTEM (sc) sc) 3) sname( (s C.CNAME=DATABASE SYSTEM (c) sc) 1.1.一種基于包的查詢代數(shù)一種基于包的查詢

5、代數(shù)包與集合的區(qū)別:包是多重集SQL關(guān)系與集合的區(qū)別: 1)關(guān)系是包 2)關(guān)系有模式1.并,交和差:2.選擇操作符:3.投影操作符:4.關(guān)系的積:5.連接操作:6.消除重復(fù):7.分組和聚集:8.排序操作符:9.表達式樹:1.并,交和差: 基于包的并,交和差的語義: 1)RS:一個元組t在結(jié)果中出現(xiàn)的次數(shù)是在中出現(xiàn)的次數(shù)與中出現(xiàn)的次數(shù)之和 2)RS:一個元組t在結(jié)果中出現(xiàn)的次數(shù)是在中出現(xiàn)的次數(shù)與中出現(xiàn)的次數(shù)之間的最小值 3)R-S:一個元組t在結(jié)果中出現(xiàn)的次數(shù)是在中出現(xiàn)的次數(shù)減去中現(xiàn)的次數(shù) 例：如果，是兩個包那么： 1)RS 2)RS 3)R-S考慮：，時，2.選擇操作符:c(R)產(chǎn)生由中滿足條

6、件的元組構(gòu)成的包，結(jié)果關(guān)系的模式與的模式一樣例：3.投影操作符:（）是在列表上的投影，不去掉重復(fù)的元組的構(gòu)成：）：的單個屬性）：表達式xy，其中x,y是屬性名字列表，將x換名為y）：表達式ez, 例：4.關(guān)系的積（笛卡兒積）如果和是關(guān)系，則是一個模式中包含的屬性和的屬性的關(guān)系，在結(jié)果積中不去掉重復(fù)的屬性例：5.連接操作:）自然連接R S）等值連接R S）連接R S6.消除重復(fù): (R)與distinct 對應(yīng),是將包轉(zhuǎn)換為集合的操作符 SQL的UNION,INTERSET,EXCEPT均按集合方式理解,故轉(zhuǎn)為包的表示時,用消除重復(fù). 如:R UNION S 可表示為(RS)7.分組和聚集: 三

7、要素: (1)聚集操作符: 出現(xiàn)在SQL的SELECT中,對屬性應(yīng)用AVG,SUM,COUNT,MIN和MAX,產(chǎn)生 相應(yīng)的結(jié)果. (2)分組: 出現(xiàn)在SQL的SELECT中,以GROUP BY 方式,其主要作用為: 1)對由FROM 和 WHERE 所描述的關(guān)系按照GROUP BY 后面的屬性 分組 2)將聚集作用到每個分組上 (3)HAVING條件: 給出查詢結(jié)果中的每個分組所必須滿足的條件 符號表示: (1)符號表示分組和聚集: L(R) R是關(guān)系 L是元素的列表: a) GROUP BY 后面所跟的屬性b)聚集操作符，如SUM(X)SX (2) L(R)的執(zhí)行過程：1)將的元組劃分為組

8、如果沒有分組屬性，則整個關(guān)系就是一個組2)對每一個組產(chǎn)生一個元組，它包括：a)該組的分組屬性的值b)根據(jù)列表定義的聚集屬性在該組中所有元組上得到的聚集例：（見書圖）8.排序操作符:1)操作符: L(R)對應(yīng)中的2)說明：結(jié)果是元組列表，而不是集合，因而該操作符常常作用于關(guān)系代數(shù)表達式的最后 9.表達式樹: (1)表達式樹: (2)表達式的計算: 1)物化的實現(xiàn)方法:產(chǎn)生實際的中間結(jié)果 產(chǎn)生實際的中間結(jié)果建立臨時關(guān)系 代價：各個運算的代價加上中間結(jié)果寫到磁盤的代價。 2)流水線的實現(xiàn)方法: 為了減少中間結(jié)果,通過將多個操作符組合成一個運算的流水 線,即將一個操作的結(jié)果傳送到下一個操作. 它又分為

9、兩種實現(xiàn)方法: a.需求驅(qū)動:在操作樹的頂端將數(shù)據(jù)往上拉。 b.生產(chǎn)者驅(qū)動:將數(shù)據(jù)從操作樹的底層往上推例： （見書圖） 2.物理查詢計劃操作符介紹物理查詢計劃操作符介紹物理查詢計劃是由一系列的操作符實現(xiàn)，主要關(guān)心兩個方面：1.操作符的實現(xiàn)算法2.操作符之間結(jié)果的傳遞1.掃描表:(底層操作)2.掃描表時的排序:3.物理操作符計算模型:4.衡量代價的參數(shù):5.掃描操作符的I/O代價:6.實現(xiàn)物理操作符的迭代器:1.掃描表:(底層操作)；掃描表是整個查詢過程中，首先要考慮的問題其實現(xiàn)方法分為兩種：）表掃描：系統(tǒng)根據(jù)表，就可以獲知該表的所有塊，并且一塊一塊地讀出）索引掃描：如果的任意一個屬性上有索引，

10、則可以使用索引來獲得的所有元組2.掃描表時的排序:原因：1)滿足order by的需要 2)其它操作符實現(xiàn)算法的要求 實現(xiàn): 1)如果希望產(chǎn)生按照屬性a排序的R,并且在a上有索引,則按索引掃描即可 2)如果R很小,可以裝入內(nèi)存,則可在內(nèi)存中,根據(jù)若干算法進行排序 3)如果R太大不能裝入內(nèi)存,則采用多路歸并方法,但排好序的結(jié)果不寫回磁盤 3.物理操作符計算模型: 任何操作符的操作對象都位于磁盤上,而操作符的結(jié)果放在內(nèi)存中4.衡量代價的參數(shù): 三類參數(shù): B:關(guān)系R的所有元組所需的塊數(shù),記為B(R) T:R中元組的數(shù)目,記為T(R) V:R中某個屬性或某組屬性上不同值的個數(shù)5.掃描操作符的I/O代

11、價: 1)表-掃描: R是聚簇的存儲: a)不考慮排序: I/O數(shù)為B b)不考慮排序: R小,則I/O數(shù)為B,R大,則采用兩路歸并方法,其I/O數(shù)為3B R不是聚簇的存儲: a)不考慮排序: I/O數(shù)為T b)不考慮排序: R小,則I/O數(shù)為T,R大,則采用兩路歸并方法,其I/O數(shù)為T+2B 2)索引-掃描: R是聚簇的存儲:I/O數(shù)為B R不是聚簇的存儲:I/O數(shù)為T 6.實現(xiàn)物理操作符的迭代器: 在前面表達式的計算中:“ 1)物化的實現(xiàn)方法:產(chǎn)生實際的中間結(jié)果 2)流水線的實現(xiàn)方法: 為了減少中間結(jié)果,通過將多個操作符組合成一個運算的流水 線,即將一個操作的結(jié)果傳送到下一個操作,它又分為

12、兩種實現(xiàn)方法: a.需求驅(qū)動 b.生產(chǎn)者驅(qū)動”需求驅(qū)動被普遍使用,一種較好的實現(xiàn)方法就是迭代器 1)迭代器的組成: OPEN:初始化 GETNEXT:獲取一個元組 CLOSE:結(jié)束迭代 2)迭代器的使用方式: 例1(書190 圖6-8) 例2 (書191 圖6-9)3.3.數(shù)據(jù)庫操作的一趟算法數(shù)據(jù)庫操作的一趟算法操作算法的分類: 1)基于排序的方法 2)基于散列的方法 3)基于索引的方法操作算法按照難度和代價的分類: 1)一趟算法 2)兩趟算法 3)多趟算法操作符的分類: 1)一次多元組,一元操作 2)整個關(guān)系,一元操作 3)整個關(guān)系,二元操作1.一次多元組操作的一趟算法:2.全關(guān)系的一元操作的一趟算法:3.二元操作的一趟算法:1.一次多元組操作的一趟算法: 主要用于一元操作符: 選擇 c(R) 和投影（） 執(zhí)行過程:2.全關(guān)系的一元操作的一趟算法: 主要用于操作符: 消除重復(fù) (R) 和 分組L(R)3.二元操作的一趟