1、整理ppt第七章第七章 查詢優(yōu)化技術(shù)查詢優(yōu)化技術(shù) 查詢處理器是數(shù)據(jù)庫管理系統(tǒng)DBMS的一個(gè)部件，它把用戶的查詢命令轉(zhuǎn)換成對(duì)數(shù)據(jù)庫的一連串操作。鑒于用查詢語言SQL表達(dá)查詢是在較高的層次上，查詢處理器必須提供如何進(jìn)行查詢的諸多細(xì)節(jié)。整理ppt 設(shè)S是一個(gè)存儲(chǔ)有關(guān)學(xué)生信息的關(guān)系，包括學(xué)號(hào)S#和姓名SN等屬性。SC是存儲(chǔ)學(xué)生選課情況的關(guān)系，包括學(xué)號(hào)S#和課程號(hào)C#等屬性。下邊的SQL語句表示查詢“列出所有選修課程C2的學(xué)生姓名”：SELECT DISTINCT S.SNFROM S, SCWHERE S.S#SC.S# AND SC.C#“C2”。查詢優(yōu)化例查詢優(yōu)化例整理ppt 假定S中包含1000

2、個(gè)學(xué)生記錄，SC中包含10000個(gè)選課記錄，其中選修C2課程的選課記錄為50個(gè)。我們用三個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式來表示這個(gè)查詢的三種處理策略： Q1=SN(s.s#sc.s#) (sc.c#=”c2”)(ssc)； Q2SN(sc.c#”c2”) (s s.s#=sc.s# sc)； Q3SN(sc.c#”c2”sc s.s#=sc.s# s)三種查詢處理策略整理ppt Q1=SN(s.s#sc.s#) (sc.c#=”c2”)(ssc) 執(zhí)行過程和時(shí)間開銷分析(1)計(jì)算S和SC的笛卡爾積。步驟1，使用一個(gè)內(nèi)存緩沖區(qū)BS讀入某個(gè)關(guān)系(如S)的未處理元組；步驟2，使用另一個(gè)內(nèi)存緩沖區(qū)BSC讀入另一

3、個(gè)關(guān)系(如SC)的未處理元組；步驟3，把BS中的每個(gè)元組和BSC中每個(gè)元組相連接，并送人輸出緩沖區(qū)BO；步驟4，如果BO已滿則寫到一個(gè)臨時(shí)文件； 步驟5，重復(fù)步驟，直至SC中元組全部處理完； 步驟6，重復(fù)步驟，直至S中元組全部處理完。整理ppt 設(shè)BS能裝50個(gè)S的元組，BSC能裝100個(gè)SC的元組，每個(gè)磁盤塊能裝10個(gè)S的元組或100個(gè)SC的元組。上述算法需要讀關(guān)系S的100個(gè)磁盤塊數(shù)據(jù)，需要20遍讀SC關(guān)系，每遍讀100個(gè)磁盤塊，讀取總塊數(shù)為：2100。 若每秒可讀20個(gè)磁盤塊，則總計(jì)要花105秒。 S和SC的笛卡爾積的結(jié)果元組數(shù)為10000000。設(shè)每個(gè)磁盤塊能裝5個(gè)結(jié)果元組，則結(jié)果元組

4、的寫出要花費(fèi)100000秒(設(shè)每秒寫20塊)。 整理ppt (2)從臨時(shí)文件讀入S和SC的笛卡爾積，按照選擇條件選取滿足要求的記錄。這一步讀取中間文件花費(fèi)的時(shí)間為100000秒(同寫中間文件一樣)。 (3)把第2步的結(jié)果在SN上作投影輸出，得到最終結(jié)果。設(shè)滿足條件的元組數(shù)為50，可存放在內(nèi)存中。忽略CPU時(shí)間，Q1需要的處理時(shí)間大于200105秒。整理ppt Q2的處理過程和時(shí)間開銷分析 (1)計(jì)算自然連接。為了執(zhí)行自然連接，讀取S和SC表的策略不變，總的讀取塊數(shù)仍為2100塊，需要105秒的時(shí)間。但自然連接的結(jié)果大大減少，為l000個(gè)元組。因此寫出這些元組花費(fèi)的時(shí)間為l0秒。 (2)讀取中間

5、文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)間也為10秒。 (3)把第2步結(jié)果投影輸出。如果忽略CPU時(shí)間，Q2的處理時(shí)間約為125秒。整理ppt Q3的處理過程和時(shí)間開銷分析 (1)先對(duì)SC作選擇運(yùn)算，只需讀一遍SC表，存取100塊花費(fèi)時(shí)間為5秒。因?yàn)闈M足條件的元組僅50個(gè)，不必使用中間文件。 (2)讀取S表，把讀入的S元組和內(nèi)存中的SC元組作連接。這一步只需讀一遍S，共100塊，需要5秒鐘的時(shí)間。 (3)把連接結(jié)果投影輸出。 忽略CPU時(shí)間，Q3的處理時(shí)間約為10秒。整理ppt 本章的開始部分，將考察用于改善邏輯查詢方案的各種代數(shù)法則。并考察每一種關(guān)系代數(shù)算符的可能算法。將一個(gè)邏輯查詢方案轉(zhuǎn)換為一個(gè)物理查

6、詢方案，不僅要定義出所用的算子，還要給出如何實(shí)現(xiàn)算子及如何將數(shù)據(jù)傳給另一算子的方法。本章主要內(nèi)容整理ppt 關(guān)系代數(shù)關(guān)系代數(shù) 傳統(tǒng)的關(guān)系代數(shù)假設(shè)關(guān)系是在集合的基礎(chǔ)上設(shè)計(jì)出來的，而SQL中的關(guān)系實(shí)際上是包(bag)，或稱多重集。也就是說， SQL關(guān)系中可以存在任意個(gè)重復(fù)元組。因此，我們將引入一種包上的關(guān)系代數(shù)。整理ppt 并，交，差并，交，差在RS中，元組t 在運(yùn)算結(jié)果中出現(xiàn)的次數(shù)，等于在R中出現(xiàn)的次數(shù)與S中出現(xiàn)的次數(shù)之和。在RS中，元組t 在運(yùn)算結(jié)果中出現(xiàn)次數(shù)，是R中出現(xiàn)次數(shù)與S中出現(xiàn)次數(shù)的較小者。在R-S中，元組t 在運(yùn)算結(jié)果中出現(xiàn)次數(shù)，等于R中出現(xiàn)次數(shù)減去S中出現(xiàn)次數(shù)之差，但不少于零它們對(duì)

7、應(yīng)著SQL中的UNION, INTERSECT和EXCEPT運(yùn)算。整理ppt 選擇運(yùn)算選擇運(yùn)算 假設(shè)R是一個(gè)關(guān)系，C是條件, 則C(R)表示對(duì)關(guān)系R進(jìn)行選擇運(yùn)算。 它是R中符合條件C的元組的包。運(yùn)算結(jié)果的域與R的域相同。 運(yùn)算被稱為關(guān)系代數(shù)的選擇運(yùn)算。整理ppt 投影運(yùn)算投影運(yùn)算若R是一個(gè)關(guān)系，則L（R）為R在投影屬性表L上的投影。將擴(kuò)充這一運(yùn)算，使之模擬SQL的SELECT子句。 允許屬性的重命名，用來指示重命名。例如， L中的成員xy表示取R的x屬性列并重新命名為y。 允許表L中包括屬性的算術(shù)或條件運(yùn)算。 若L的成員不是單個(gè)的屬性，則必須由箭號(hào)和屬性來命名表達(dá)式的結(jié)果。整理ppt例例 7.

8、3 7.3 令 R 為如下的關(guān)系：abc012012345則a,b+cx（R）的運(yùn)算結(jié)果為：ax030339整理ppt笛卡爾乘積運(yùn)算笛卡爾乘積運(yùn)算 若R和S是關(guān)系，則RS也是關(guān)系，其結(jié)果關(guān)系的域來自于R的域加上S的域。 若某一個(gè)屬性，如a，在兩個(gè)關(guān)系中都有，則在結(jié)果域中用R.a和S.a作為這兩個(gè)屬性的名字。 結(jié)果關(guān)系的元組都是由從R中取一個(gè)元組且在這一元組的分量后接S的任一元組的分量而形成的。 若一元組r在R中出現(xiàn)n次，另一元組s在S中出現(xiàn)m次，則元組rs在結(jié)果中出現(xiàn)nm次。整理ppt 假設(shè) R(a,b)為關(guān)系: ab012323 關(guān)系 S(b,c)為: bc141425整理ppt圖圖 7 7

9、. .2 2 關(guān)系 R 和 S 的積aR.bS.bc011401140125231423142325231423142325整理ppt 連接運(yùn)算連接運(yùn)算 最簡(jiǎn)單的連接是自然連接；我們用RS來表示R和S的自然連接。 自然連接可分解為 L（C(RS)），其中：.C是使R和S中所有同名的屬性對(duì)相等的條件。.L是R和S的所有屬性的列表，只是每一對(duì)相等的屬性中去掉一個(gè)。若R.x和S.x是相等的屬性，則因?yàn)樵谕队暗慕Y(jié)果中只有一個(gè)屬性x， 任取R.x和S.x之一, 并重新命名為x。整理ppt 用于改善查詢方案的代數(shù)定律用于改善查詢方案的代數(shù)定律 關(guān)系代數(shù)表達(dá)式可以用樹結(jié)構(gòu)來表示。在不改變查詢結(jié)果的前提下，將

10、這棵樹進(jìn)行變換，以達(dá)到降低查詢的時(shí)間和空間復(fù)雜性的目的。這一工作稱為關(guān)系代數(shù)優(yōu)化。 這一工作是在較高的抽象層次上即邏輯數(shù)據(jù)結(jié)構(gòu)層上進(jìn)行的。整理ppt查詢的符號(hào)表示形式：查詢樹 查詢樹是一種表示關(guān)系代數(shù)表達(dá)式的樹形結(jié)構(gòu)。在一個(gè)查詢樹中，葉子節(jié)點(diǎn)表示關(guān)系，內(nèi)部節(jié)點(diǎn)表示關(guān)系代數(shù)操作。查詢樹以自底向上的方式執(zhí)行： 當(dāng)一個(gè)內(nèi)部節(jié)點(diǎn)的操作分量有值時(shí)，這個(gè)內(nèi)部節(jié)點(diǎn)所表示的操作開始啟動(dòng)執(zhí)行，執(zhí)行結(jié)束后用結(jié)果關(guān)系代替這個(gè)內(nèi)部節(jié)點(diǎn)。整理ppt給定一個(gè)用SQL語言定義的查詢：SELECT listFROM R1，R2，RnWHERE C其中，C是條件表達(dá)式，list是輸出屬性表?？梢园凑杖缦路椒ò堰@個(gè)查詢轉(zhuǎn)換為關(guān)系

11、代數(shù)表達(dá)式：1）使用FROM從句中的關(guān)系R1、R2、Rn構(gòu)造笛卡爾乘積R1R2Rn；2）在第1步的基礎(chǔ)上構(gòu)造一個(gè)選擇操作：C（R1R2Rn）；在第2步的基礎(chǔ)上構(gòu)造一個(gè)投影操作：list(C（R1R2Rn）)。整理ppt 假設(shè)有關(guān)系MovieStar(name,addr,gender,birthdate)StarsIn(title,year,starName)從中我們要查找出那些在1996年的影片中出現(xiàn)的女演員的出生日期和影片名：SELECT title, birthdateFROM MovieStar, StarsInWHERE year=1996 AND gender=F AND starN

12、ame=name;整理ppt整理ppt等價(jià)的表達(dá)方式下圖中所用的方案與上圖明顯不同。第一，應(yīng)用于兩個(gè)關(guān)系的乘積上的WHERE子句中的條件starName=name是一個(gè)等值連接。一般地，連接運(yùn)算產(chǎn)生的元組比乘積運(yùn)算產(chǎn)生的結(jié)果元組要少，因此，如有可能，盡量使用連接運(yùn)算。第二，WHERE子句的其他兩個(gè)條件被分成了兩個(gè)運(yùn)算，并且兩個(gè)運(yùn)算都被順著樹往下移。其中，因?yàn)檫x擇運(yùn)算year=1996只涉及到StarsIn的一個(gè)屬性year，所以，它可直接應(yīng)用到關(guān)系StarsIn之上。整理ppt有幾個(gè)關(guān)系代數(shù)的運(yùn)算符是既可結(jié)合又可交換的。例如：1 RSSR； （RS）TR（ST） 。2 RSSR； （RS）TR

13、（ST） 。3 RSSR； （RS）TR（ST） 。4 RSSR； （RS）TR（ST） 。注意不管關(guān)系是集合還是包，以上所述的并和交的規(guī)則總是適用的。整理ppt的兩個(gè)分離規(guī)則：lC1 AND C2(R)C1 (C2(R)。lC1 OR C2(R) (C1 (R) (C2(R)。注意和的次序是靈活的。例如，我們也可以把上面的第一個(gè)規(guī)則寫成在之后進(jìn)行操作，即C2(C1(R)。實(shí)際上，運(yùn)算符的次序可任意交換。lC1 (C2(R) C2(C1(R)。 優(yōu)化查詢過程的一個(gè)最重要的思想，是不改變表達(dá)式的作用而盡量將選擇操作順著查詢樹往下移整理ppt例例 給出關(guān)系R（a，b）、S（b，c）和表達(dá)式(a=1

14、 OR a=3) AND bc (RS)。條件bc可單獨(dú)應(yīng)用于S，條件a1 OR a3可單獨(dú)應(yīng)用于R，因此，從分解這兩個(gè)條件的AND開始，得 a=1 OR a=3 (bc(R S)。接著，可以將選擇bc下移至S，得到表達(dá)式： a=1 OR a=3 (R bc(S)最后，將第一個(gè)條件移至R， 生成a=1 OR a=3 (R) bc(S)整理ppt設(shè)有關(guān)系MovieStar(name,addr,gender,birthdate)StarsIn(title,year,starName)并且想知道對(duì)每一年出現(xiàn)在該年影片中的最年輕演員的生日。我們可以把這一查詢表達(dá)為：SELECT year,MAX(birthdate)FROM MovieStar,StarsInWHERE nam