數(shù)據(jù)庫(kù)系統(tǒng)教學(xué)課件：第12講-_關(guān)系查詢處理

1、第12講: (第11章) 查詢處理（基本操作） 重慶大學(xué)計(jì)算機(jī)學(xué)院 課程名稱: 數(shù)據(jù)庫(kù)系統(tǒng) -1內(nèi)容目標(biāo)基本過(guò)程代價(jià)度量基本關(guān)系代數(shù)運(yùn)算的處理基本運(yùn)算單表運(yùn)算多表運(yùn)算多運(yùn)算表達(dá)式3RDBMS用戶或應(yīng)用檢查語(yǔ)法和關(guān)系有效性 + 轉(zhuǎn)換為關(guān)系代數(shù)操作執(zhí)行優(yōu)化計(jì)劃,形成返回結(jié)果salary75000(salary(instructor) salary(salary75000(instructor)通過(guò)等價(jià)變換得到優(yōu)化執(zhí)行方案（操作執(zhí)行次序）含注釋是否需要采用索引查詢執(zhí)行計(jì)劃:執(zhí)行一個(gè)查詢的計(jì)算原語(yǔ)(標(biāo)注了如何執(zhí)行的一個(gè)或多個(gè)關(guān)系代數(shù)操作)的操作序列一、Query Processing （查詢處理過(guò)程）

2、二、Measures of Query Cost （查詢代價(jià)度量）Cost is generally measured as total elapsed time for answering queryMany factors contribute to time costdisk accesses, CPU, or even network communicationTypically disk access is the predominant cost, and is also relatively easy to estimate. Measured by taking into ac

3、countNumber of seeks * average-seek-costNumber of blocks read * average-block-read-costNumber of blocks written * average-block-write-costCost to write a block is greater than cost to read a block data is read back after being written to ensure that the write was successfulMeasures of Query Cost (Co

4、nt.)For simplicity we just use the number of block transfers from disk and the number of seeks as the cost measurestT time to transfer one blocktS time for one seekCost for b block transfers plus S seeks b * tT + S * tS We ignore CPU costs for simplicityReal systems do take CPU cost into accountWe d

5、o not include cost to writing output to disk in our cost formulaeMeasures of Query Cost (Cont.)Several algorithms can reduce disk IO by using extra buffer space Amount of real memory available to buffer depends on other concurrent queries and OS processes, known only during executionWe often use wor

6、st case estimates, assuming only the minimum amount of memory needed for the operation is availableRequired data may be buffer resident already, avoiding disk I/OBut hard to take into account for cost estimation例1Select * from student where ；考慮的幾種情況： C1：無(wú)條件； C2：Sno200215121； C3：Sage20； C4：SdeptCS AN

7、D Sage20； 三、選擇運(yùn)算的處理7選擇運(yùn)算典型處理方法：1. 簡(jiǎn)單的文件掃描方法 （線性搜索）對(duì)查詢的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出 適合小表，不適合大表2. 索引(或散列)掃描方法 適合選擇條件中的屬性上有索引(例如B+樹(shù)索引或Hash索引) 通過(guò)索引先找到滿足條件的元組主碼或元組指針，再通過(guò)元組指針直接在查詢的基本表中找到元組 選擇運(yùn)算的處理（續(xù)）8例1-C2 以C2為例，Sno200215121，并且Sno上有索引(或Sno是散列碼)使用索引(或散列)得到Sno為200215121 元組的指針通過(guò)元組指針在student表中檢索到該學(xué)

8、生例1-C3 以C3為例，Sage20，并且Sage 上有B+樹(shù)索引使用B+樹(shù)索引找到Sage20的索引項(xiàng)，以此為入口點(diǎn)在B+樹(shù)的順序集上得到Sage20的所有元組指針通過(guò)這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。 選擇運(yùn)算的處理（續(xù)）9例1-C4 以C4為例，SdeptCS AND Sage20，如果Sdept和Sage上都有索引：算法一：分別用上面兩種方法分別找到SdeptCS的一組元組指針和Sage20的另一組元組指針求這2組指針的交集到student表中檢索得到計(jì)算機(jī)系年齡大于20的學(xué)生算法二：找到SdeptCS的一組元組指針，通過(guò)這些元組指針到student表中檢

9、索對(duì)得到的元組檢查另一些選擇條件(如Sage20)是否滿足把滿足條件的元組作為結(jié)果輸出。 選擇運(yùn)算的處理（續(xù)）1011ts+br*tT(hi+1)*(tT+ts)(hi*(tT+ts)+ts+b*tT(hi+n)*(tT+ts)ts+br*tT(hi+1)*(tT+ts)(hi*(tT+ts)+ts+b*tT(hi+n)*(tT+ts)ts+br*tThi*(ts+tT)+(ts+tT)hi*(ts+tT)+(ts+b*tT)hi*(ts+tT)+n*(ts+tT)各種等值比較情況的執(zhí)行開(kāi)銷分析圖12-3ts+br*tT(hi+1)*(tT+ts)(hi*(tT+ts)+ts+b*tT(hi+

10、n)*(tT+ts)ts+br*tThi*(ts+tT)+(ts+tT)hi*(ts+tT)+(ts+b*tT)hi*(ts+tT)+n*(ts+tT)ts+br*tT(hi+1)*(tT+ts)(hi*(tT+ts)+ts+b*tT(hi+n)*(tT+ts)ts+br*tThi*(ts+tT)+(ts+tT)hi*(ts+tT)+(ts+b*tT)hi*(ts+tT)+n*(ts+tT)ts+br*tThi*(ts+tT)+(ts+tT)hi*(ts+tT)+(ts+b*tT)hi*(ts+tT)+n*(ts+tT)ts-搜索1個(gè)磁盤(pán)塊的時(shí)間tT-傳輸1個(gè)磁盤(pán)塊的時(shí)間ts+br*tThi*

11、(ts+tT)+(ts+tT)hi*(ts+tT)+(ts+b*tT)hi*(ts+tT)+n*(ts+tT)ts-搜索1個(gè)磁盤(pán)塊的時(shí)間tT-傳輸1個(gè)磁盤(pán)塊的時(shí)間hi*(ts+tT)+(ts+tT)涉及范圍比較的選擇運(yùn)算各種算法執(zhí)行代價(jià)分析12hi*(ts+tT)+(ts+b*tT)hi*(ts+tT)+n*(ts+tT)n-所取記錄數(shù)第1項(xiàng)-找到滿足A=v的首條記錄第1項(xiàng)-找到滿足A=v的首條記錄b-包含具有指定搜 索碼記錄的塊數(shù)第1項(xiàng)-找到滿足A=v的首條記錄第1項(xiàng)-找到滿足A=v的首條記錄連接運(yùn)算是查詢處理中最耗時(shí)的操作之一 只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法 1. 嵌套循環(huán)方

12、法(nested loop) 2.索引連接(index join)方法 3.排序-合并方法(sort-merge join 或merge join) 4. Hash Join方法 四、 連接運(yùn)算的處理 1314for each tuple tr in r do begin for each tuple ts in s do begin test pair (tr , ts) to see if they satisfy the join condition if they do, add tr ts to the result. endendr-外層關(guān)系s-內(nèi)層關(guān)系分析案例：嵌套循環(huán)連接的代價(jià)

13、估算圖12-5 嵌套循環(huán)連接1.嵌套循環(huán)連接算法r s15嵌套循環(huán)連接算法的代價(jià)估算worst case: if there is enough memory only to hold one block of each relation, the estimated cost : (br -包含r記錄的磁盤(pán)塊數(shù)，nr - r的記錄數(shù)) nr bs + br block transfers, and (內(nèi)循環(huán)s讀nr 次+ 外循環(huán)關(guān)系r讀一次) nr + br seeks (讀s每次尋道1次,但循環(huán)nr次 + 讀r的所有塊尋道br 次)best case: if both relations

14、fit entirely in memory, use the smaller one as the inner relation s. Reduces cost to br + bs block transfers and 2 seeks (尋道兩次將兩關(guān)系連續(xù)全部讀進(jìn)內(nèi)存中,且s和r都僅讀一次)例示：Assuming worst case memory availability cost estimate iswith student as the outer relation:5000 400 + 100 = 2,000,100 block transfers, and5000 + 10

15、0 = 5100 seeks with takes as the outer relation 更快！(因內(nèi)關(guān)系student更小)10000 100 + 400 = 1,000,400 block transfers, and 10000 + 400 = 10,400 seeksIn the best case, the cost estimate will be 400+100=500 block transfers. 一般把小關(guān)系作為內(nèi)層關(guān)系效率更高162.塊嵌套循環(huán)連接算法for each block Br of r do begin for each block Bs of s do

16、 begin for each tuple tr in Br do begin for each tuple ts in Bs do begin Check if (tr,ts) satisfy the join condition if they do, add tr ts to the result. end end endend圖12-6 塊嵌套循環(huán)連接如何改進(jìn)嵌套循環(huán)連接算法？17塊嵌套循環(huán)連接算法的代價(jià)估算Worst case estimate: br bs + br block transfers and br+br =2*br seeksEach block in the inn

17、er relation s is read once for each block in the outer relationBest case: br + bs block transfers + 2 seeks(同嵌套循環(huán)). 比嵌套循環(huán)連接高效！*Improvements to nested loop and block nested loop algorithms:In block nested-loop, use M - 2 disk blocks as blocking unit for outer relations, where M = memory size in block

18、s; use remaining two blocks to buffer inner relation and output Cost = br / (M-2) bs + br block transfers and 2 br / (M-2) seeks*If equi-join attribute forms a key or inner relation, stop inner loop on first match*Scan inner loop forward and backward alternately, to make use of the blocks remaining

19、in buffer (with LRU replacement)*Use index on inner relation if available*上兩種算法還有改善余地嗎？嵌套循環(huán)連接代價(jià)：nr bs + br block transfers,and nr + br seeks算法步驟： 在內(nèi)表s上為連接屬性建立索引，如果原來(lái)沒(méi)有該索引 對(duì)外表r中每一個(gè)元組，由連接屬性值通過(guò)內(nèi)表的索引查找相應(yīng)的內(nèi)表元組 把這些內(nèi)表元組和外表元組連接起來(lái) 循環(huán)執(zhí)行，直到外表r中的元組處理完為止 最壞情況下,內(nèi)存只能容納外表r的一塊和索引的一塊,因此,執(zhí)行代價(jià)為:其中,讀取r需要br次I/O操作, nr是外表r

20、中的記錄數(shù),c是用連接條件對(duì)內(nèi)表s進(jìn)行單次選擇運(yùn)算的執(zhí)行代價(jià)若兩個(gè)表均有索引時(shí),一般把小關(guān)系作為外層關(guān)系效率更高3. 索引連接(index join)方法18適合連接的諸表已經(jīng)排好序的情況 排序合并連接方法的步驟：如果連接的表沒(méi)有排好序，先對(duì)r表和s表按連接屬性排序 取r表中第一個(gè)連接屬性值，依次掃描s表中具有相同屬性值的元組 當(dāng)掃描到s表中不相同的第一個(gè)元組時(shí)，返回r表掃描它的下一個(gè)元組，再掃描s表中具有相同屬性值的元組，把它們連接起來(lái) 重復(fù)上述步驟直到r 表掃描完4. 排序-合并方法(sort-merge join 或merge join) 19代價(jià)分析:對(duì)兩表都只要掃描一遍,如果2個(gè)表原

21、來(lái)無(wú)序，執(zhí)行時(shí)間要加上對(duì)兩個(gè)表的排序時(shí)間對(duì)于2個(gè)大表，先排序后使用sort-merge join方法執(zhí)行連接，總的時(shí)間一般仍會(huì)大大減少 把連接屬性作為hash碼，用同一個(gè)hash函數(shù)把R和S中的元組散列到同一個(gè)hash文件中步驟：劃分階段(partitioning phase)：對(duì)包含較少元組的表(比如R)進(jìn)行一遍處理把它的元組按hash函數(shù)分散到hash表的桶中試探階段(probing phase)：也稱為連接階段(join phase) 對(duì)另一個(gè)表(S)進(jìn)行一遍處理把S的元組散列到適當(dāng)?shù)膆ash桶中把元組與桶中所有來(lái)自R并與之相匹配的元組連接起來(lái) 上面hash join算法前提：假設(shè)兩個(gè)表

22、中較小的表在第一階段后可以完全放入內(nèi)存的hash桶中 以上的算法思想可以推廣到更加一般的多個(gè)表的連接算法上 205. 散列連接方法 21如何計(jì)算包含多個(gè)運(yùn)算的表達(dá)式Materialized evaluation物化計(jì)算: evaluate one operation at a time, starting at the lowest-level. Use intermediate results materialized into temporary relations to evaluate next-level operations.E.g., in the figure below, c

23、ompute and storeThen compute the store its join with instructor, and store the second result Finally compute the projection on name. Materialization(物化)(若該結(jié)果關(guān)系很小，則不用寫(xiě)入磁盤(pán))(指中間結(jié)果)(基于新的中間結(jié)果)查詢優(yōu)化在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中有著非常重要的地位 關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素 由于關(guān)系表達(dá)式的語(yǔ)義級(jí)別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義，提供了執(zhí)行查詢優(yōu)化的可能性 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化22查詢優(yōu)化

24、的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好 (1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫(xiě)程序，而重寫(xiě)程序在實(shí)際應(yīng)用中往往是不太可能的。查詢優(yōu)化概述23(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)查詢優(yōu)化概述24RDBMS通過(guò)某種代

25、價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案集中式數(shù)據(jù)庫(kù)執(zhí)行開(kāi)銷主要包括：磁盤(pán)存取塊數(shù)(I/O代價(jià))處理機(jī)時(shí)間(CPU代價(jià))查詢的內(nèi)存開(kāi)銷 I/O代價(jià)是最主要的 分布式數(shù)據(jù)庫(kù)總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)通信代價(jià) 查詢優(yōu)化概述25查詢優(yōu)化的總目標(biāo)：選擇有效的策略求得給定關(guān)系表達(dá)式的值使得查詢代價(jià)最小(實(shí)際上是較小) 查詢優(yōu)化概述261. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹(shù)2. 根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn) （優(yōu)化）形式3. 選擇低層的操作算法對(duì)于語(yǔ)法樹(shù)中的每一個(gè)操作計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)選擇代價(jià)小的執(zhí)行算法4. 生成查詢計(jì)劃(查詢執(zhí)行方案)查

26、詢計(jì)劃是由一系列內(nèi)部操作組成的。實(shí)際系統(tǒng)的查詢優(yōu)化步驟27例3 求選修了2號(hào)課程的學(xué)生姓名。用SQL表達(dá)： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； 假定學(xué)生-課程數(shù)據(jù)庫(kù)中有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄其中選修2號(hào)課程的選課記錄為50個(gè) 28系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來(lái)完成這一查詢Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)Q2=Sname(Sc.Cno=2 (Student SC)Q3=Sname(Student

27、Sc.Cno=2 (SC)29一、第一種情況 Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 StudentSC)1. 計(jì)算廣義笛卡爾積 把Student和SC的每個(gè)元組連接起來(lái)的做法：在內(nèi)存中盡可能多地裝入某個(gè)表(如Student表)的若干塊，留出一塊存放另一個(gè)表(如SC表)的元組。把SC中的每個(gè)元組和Student中每個(gè)元組連接，連接后的元組裝滿一塊后就寫(xiě)到中間文件上從SC中讀入一塊和內(nèi)存中的Student元組連接，直到SC表處理完。再讀入若干塊Student元組，讀入一塊SC元組重復(fù)上述處理過(guò)程，直到把Student表處理完30設(shè)一個(gè)塊能裝10個(gè)Student元組

28、或100個(gè)SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為 =100+20100=2100塊其中，讀Student表100塊。讀SC表20遍，每遍100塊。若每秒讀寫(xiě)20塊，則總計(jì)要花105s 連接后的元組數(shù)為103104=107。設(shè)每塊能裝10個(gè)元組，則寫(xiě)出這些塊要用106/20=5104s 312. 作選擇操作 依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄 假定內(nèi)存處理時(shí)間忽略。讀取中間文件花費(fèi)的時(shí)間(同寫(xiě)中間文件一樣)需5104s 滿足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存 323. 作投影操作 把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果 第一種

29、情況下執(zhí)行查詢的總時(shí)間105+25104105s所有內(nèi)存處理時(shí)間均忽略不計(jì) 33二、 第二種情況 Q2=Sname(Sc.Cno=2 (Student SC)1. 計(jì)算自然連接 執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為2100塊花費(fèi)105 s 自然連接的結(jié)果比第一種情況大大減少，為104個(gè) 寫(xiě)出這些元組時(shí)間為104/10/20=50s，為第一種情況的千分之一 2. 讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)間也為50s。3. 把第2步結(jié)果投影輸出。 第二種情況總的執(zhí)行時(shí)間105+50+50205s 34三、 第三種情況 Q3=Sname(Student Sc.Cno=2(

30、SC)1. 先對(duì)SC表作選擇運(yùn)算，只需讀一遍SC表，存取100塊花費(fèi)時(shí)間為5s，因?yàn)闈M足條件的元組僅50個(gè)，不必使用中間文件。2. 讀取Student表，把讀入的Student元組和內(nèi)存中的SC元組作連接。也只需讀一遍Student表共100塊，花費(fèi)時(shí)間為5s。3. 把連接結(jié)果投影輸出 第三種情況總的執(zhí)行時(shí)間5+510s 35假如SC表的Cno字段上有索引第一步就不必讀取所有的SC元組而只需讀取Cno=2的那些元組(50個(gè))存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共34塊若Student表在Sno上也有索引第二步也不必讀取所有的Student元組因?yàn)闈M足條件的SC記錄僅50個(gè)，涉及最多50個(gè)

31、Student記錄讀取Student表的塊數(shù)也可大大減少 總的存取時(shí)間將進(jìn)一步減少到數(shù)秒 36把代數(shù)表達(dá)式Q1變換為Q2、 Q3，即有選擇和連接操作時(shí)，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化在Q3中SC表的選擇操作算法有全表掃描和索引掃描2種方法，經(jīng)過(guò)初步估算，索引掃描方法較優(yōu) 對(duì)于Student和SC表的連接，利用Student表上的索引，采用index join代價(jià)也較小，這就是物理優(yōu)化 37關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 查詢樹(shù)的啟發(fā)式優(yōu)化 代 數(shù) 優(yōu) 化38代數(shù)優(yōu)化策略：通過(guò)對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換來(lái)提高查詢效率 關(guān)系代數(shù)表達(dá)式的等價(jià)：指用相同的關(guān)系代替兩個(gè)表達(dá)式中

32、相應(yīng)的關(guān)系所得到的結(jié)果是相同的兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的，可記為E1E2 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 39關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）常用的等價(jià)變換規(guī)則：1. 連接、笛卡爾積交換律 設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12. 連接、笛卡爾積的結(jié)合律 設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) 3. 投影的串接定律 ( (E ) (E)這里，E是關(guān)系代數(shù)表

33、達(dá)式，Ai(i=1，2，n)，Bj(j=1，2，m)是屬性名且A1，A2，An構(gòu)成B1，B2，Bm的子集。4. 選擇的串接定律 ( (E) (E)這里，E是關(guān)系代數(shù)表達(dá)式，F(xiàn)1、F2是選擇條件。 選擇的串接律說(shuō)明選擇條件可以合并。這樣一次就可檢查全部條件。關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）415. 選擇與投影操作的交換律 F( (E ) (F(E)選擇條件F只涉及屬性A1，An。若F中有不屬于A1，An的屬性B1，Bm則有更一般的規(guī)則： (F(E) (F( (E)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）426. 選擇與笛卡爾積的交換律如果F中涉及的屬性都是E1中的屬性，則 (E1E2) (E1)E2如果

34、F=F1F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價(jià)變換規(guī)則1，4，6可推出： (E1E2) (E1) (E2)若F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則仍有 (E1E2) ( (E1)E2)它使部分選擇在笛卡爾積前先做。 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）437. 選擇與并的分配律設(shè)E=E1E2，E1，E2有相同的屬性名，則 F(E1E2)F(E1)F(E2)8. 選擇與差運(yùn)算的分配律若E1與E2有相同的屬性名，則 F(E1-E2)F(E1)-F(E2)9. 選擇對(duì)自然連接的分配律 F(E1 E2)F(E1) F(E2) F只涉及E1與E2的公共屬性

35、 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）4410. 投影與笛卡爾積的分配律設(shè)E1和E2是兩個(gè)關(guān)系表達(dá)式，A1，An是E1的屬性，B1，Bm是E2的屬性，則 (E1E2) (E1) (E2)11. 投影與并的分配律設(shè)E1和E2有相同的屬性名，則 (E1E2) (E1) (E2)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）45典型的啟發(fā)式規(guī)則：1. 選擇運(yùn)算應(yīng)盡可能先做。在優(yōu)化策略中這是最重要、最基本的一條2. 把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行如有若干投影和選擇運(yùn)算，并且它們都對(duì)同一個(gè)關(guān)系操作，則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系查詢樹(shù)的啟發(fā)式優(yōu)化 463. 把投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái)

36、4. 把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算 例：Student.Sno=SC.Sno (StudentSC) Student SC5. 找出公共子表達(dá)式如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系并且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少得多，則先計(jì)算一次公共子表達(dá)式并把結(jié)果寫(xiě)入中間文件是合算的當(dāng)查詢的是視圖時(shí)，定義視圖的表達(dá)式就是公共子表達(dá)式的情況查詢樹(shù)的啟發(fā)式優(yōu)化（續(xù)）47遵循這些啟發(fā)式規(guī)則，應(yīng)用9.3.1的等價(jià)變換公式來(lái)優(yōu)化關(guān)系表達(dá)式的算法。算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的查詢樹(shù)輸出：優(yōu)化的查詢樹(shù)方法：(1) 利用等價(jià)變換規(guī)則4把形如F1F2F

37、n(E)變換為F1(F2(Fn(E)。(2) 對(duì)每一個(gè)選擇，利用等價(jià)變換規(guī)則49盡可能把它移到樹(shù)的葉端。查詢樹(shù)的啟發(fā)式優(yōu)化（續(xù)）48(3) 對(duì)每一個(gè)投影利用等價(jià)變換規(guī)則3，5，10，11中的一般形式盡可能把它移向樹(shù)的葉端。注意： 等價(jià)變換規(guī)則3使一些投影消失規(guī)則5把一個(gè)投影分裂為兩個(gè)，其中一個(gè)有可能被移向樹(shù)的葉端 (4) 利用等價(jià)變換規(guī)則35把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成 查詢樹(shù)的啟發(fā)式優(yōu)化（續(xù)）49 (5) 把上述得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一組(這些直接祖先是(，

38、運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組但當(dāng)雙目運(yùn)算是笛卡爾積()，而且后面不是與它組成等值連接的選擇時(shí)，則不能把選擇與這個(gè)雙目運(yùn)算組成同一組，把這些單目運(yùn)算單獨(dú)分為一組 查詢樹(shù)的啟發(fā)式優(yōu)化（續(xù)）50例4 下面給出例3中 SQL語(yǔ)句的代數(shù)優(yōu)化示例。 (1) 把SQL語(yǔ)句轉(zhuǎn)換成查詢樹(shù)，如下圖所示查詢樹(shù)的啟發(fā)式優(yōu)化（續(xù)）查詢樹(shù)51為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)系代數(shù)語(yǔ)法樹(shù)，則上面的查詢樹(shù)如下圖所示。查詢樹(shù)的啟發(fā)式優(yōu)化（續(xù)） 關(guān)系代數(shù)語(yǔ)法樹(shù) 52(2) 對(duì)查詢樹(shù)進(jìn)行優(yōu)化利用規(guī)則4、6把選擇SC.Cno=2移到葉端，查詢樹(shù)便轉(zhuǎn)換成下圖所示的優(yōu)化的查詢樹(shù)。這就是9.2

39、.2節(jié)中Q3的查詢樹(shù)表示查詢樹(shù)的啟發(fā)式優(yōu)化（續(xù)）優(yōu)化后的查詢樹(shù) 53Transformation Example: Pushing SelectionsQuery: Find the names of all instructors in the Music department, along with the titles of the courses that they teachname, title(dept_name= “Music”(instructor (teaches course_id, title (course)Transformation using rule 7a.n

40、ame, title(dept_name= “Music”(instructor) (teaches course_id, title (course)Performing the selection as early as possible reduces the size of the relation to be joined. Example with Multiple TransformationsQuery: Find the names of all instructors in the Music department who have taught a course in 2

41、009, along with the titles of the courses that they taughtname, title(dept_name= “Music”year = 2009 (instructor (teaches course_id, title (course)Transformation using join associatively (Rule 6a):name, title(dept_name= “Music”year = 2009 (instructor teaches) course_id, title (course)Second form prov

42、ides an opportunity to apply the “perform selections early” rule, resulting in the subexpression dept_name = “Music” (instructor) year = 2009 (teaches)Transformation Example: Pushing ProjectionsConsider: name, title(dept_name= “Music” (instructor) teaches) course_id, title (course)When we compute(de

43、pt_name = “Music” (instructor teaches)we obtain a relation whose schema is:(ID, name, dept_name, salary, course_id, sec_id, semester, year)Push projections using equivalence rules 8a and 8b; eliminate unneeded attributes from intermediate results to get: name, title(name, course_id ( dept_name= “Mus

44、ic” (instructor) teaches) course_id, title (course)Performing the projection as early as possible reduces the size of the relation to be joined. Multiple Transformations (Cont.)Join Ordering ExampleFor all relations r1, r2, and r3,(r1 r2) r3 = r1 (r2 r3 )(Join Associativity)If r2 r3 is quite large a

45、nd r1 r2 is small, we choose (r1 r2) r3 so that we compute and store a smaller temporary relation.Join Ordering Example (Cont.)Consider the expressionname, title(dept_name= “Music” (instructor) teaches) course_id, title (course)Could compute teaches course_id, title (course) first, and join result w

46、ith dept_name= “Music” (instructor) but the result of the first join is likely to be a large relation.Only a small fraction of the universitys instructors are likely to be from the Music department it is better to compute dept_name= “Music” (instructor) teaches first. 代數(shù)優(yōu)化改變查詢語(yǔ)句中操作的次序和組合，不涉及底層的存取路徑對(duì)

47、于一個(gè)查詢語(yǔ)句有許多存取方案，它們的執(zhí)行效率不同， 僅僅進(jìn)行代數(shù)優(yōu)化是不夠的 物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計(jì)劃 物理優(yōu)化60選擇的方法： 基于規(guī)則的啟發(fā)式優(yōu)化基于代價(jià)估算的優(yōu)化兩者結(jié)合的優(yōu)化方法物理優(yōu)化（續(xù)）61一、 選擇操作的啟發(fā)式規(guī)則 二、 連接操作的啟發(fā)式規(guī)則 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化62一、 選擇操作的啟發(fā)式規(guī)則:1. 對(duì)于小關(guān)系，使用全表順序掃描，即使選擇列上有索引 對(duì)于大關(guān)系，啟發(fā)式規(guī)則有：2. 對(duì)于選擇條件是主碼值的查詢查詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引一般的RDBMS會(huì)自動(dòng)建立主碼索引。基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))633

48、. 對(duì)于選擇條件是非主屬性值的查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))644. 對(duì)于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))655. 對(duì)于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引則可以用例1-C4中介紹的索引掃描方法否則使用全表順序掃描。6. 對(duì)于用OR連接的析取選擇條件，

49、一般使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))66二、 連接操作的啟發(fā)式規(guī)則：1. 如果2個(gè)表都已經(jīng)按照連接屬性排序 選用排序-合并方法2. 如果一個(gè)表在連接屬性上有索引 選用索引連接方法3. 如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小 選用Hash join方法基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))674. 可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表) 。 理由：設(shè)連接表R與S分別占用的塊數(shù)為Br與Bs連接操作使用的內(nèi)存緩沖區(qū)塊數(shù)為K分配K-1塊給外表如果R為外表，則嵌套循環(huán)法存取的塊數(shù)為Br+( Br/K-1)Bs顯然應(yīng)該選塊數(shù)小的表作為外表 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))68啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行的系統(tǒng)，優(yōu)化開(kāi)銷包含在查詢總開(kāi)銷之中 編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開(kāi)的可以采用精細(xì)復(fù)雜一些的基于代價(jià)的優(yōu)化方法 基于代價(jià)的優(yōu)化 69高