空間數據庫精品課件

空間數據庫（7）

2021/4/171查詢處理與優(yōu)化查詢處理概覽代價估算基本運算的實現與代價關系代數表達式實現關系代數表達式轉換選擇執(zhí)行計劃空間查詢處理與優(yōu)化2021/4/172查詢處理概覽查詢處理是指從數據庫中提取數據的一系列活動。主要包括：將用高層數據庫語言表示的查詢語句翻譯為能在文件系統(tǒng)這一物理層次上實現的表達式為優(yōu)化查詢而進行各種轉換查詢的實際執(zhí)行輸入：SQL語句；輸出：滿足查詢條件的數據

2021/4/173語法分析與翻譯優(yōu)化執(zhí)行語法分析與翻譯關系代數表達式執(zhí)行計劃優(yōu)化器查詢語句執(zhí)行引擎查詢結果有關數據的統(tǒng)計值數據查詢處理基本步驟2021/4/174查詢優(yōu)化概念查詢優(yōu)化是為關系代數表達式的計算選擇最有效的查詢計劃的過程查詢執(zhí)行計劃：用于計算查詢的原語序列執(zhí)行原語：加了“如何執(zhí)行”注釋的關系代數運算（選擇、投影……）根據選擇的算法對文件記錄進行操作2021/4/175查詢優(yōu)化過程代數優(yōu)化力圖找出與給定關系代數表達式等價的但執(zhí)行效率更高的一個表達式執(zhí)行策略選擇對查詢語句處理的詳細策略的選擇選擇執(zhí)行運算所采用的具體算法選擇將使用的特定索引等等2021/4/176查詢優(yōu)化過程可能性SQL語言和關系代數表達式的非過程化特點可行性查詢優(yōu)化器具有豐富的可使用信息數據庫發(fā)生變化時優(yōu)化器容易再次進行優(yōu)化優(yōu)化器能夠對多種實現策略逐一進行考慮優(yōu)化器集中了最優(yōu)秀的程序員的智慧和經驗2021/4/177代價估算關系的統(tǒng)計信息nr：關系r中的元組數目(number)br：含有關系r的元組的塊數目(block)sr：關系r中一個元組的大小(size)fr：關系r的塊因子，即一個塊中能存放的關系r的元組數(factor)若假定關系r的元組物理上存于同一文件中，則：br=Roof(nr/fr)2021/4/178代價估算關系的統(tǒng)計信息V(A,r)：關系r中屬性A所具有的不同值的數目。V(A,r)等于ΠA(r)的大小若A為關系r的碼，則V(A,r)=nrSC(A,r)：關系r的屬性A的選擇基數。表示關系r中滿足屬性A上的一個等值條件的平均元組數。若A為r的碼屬性，則SC(A,r)＝1若A為非碼屬性，并假定V(A,r)個不同的值在元組上均勻分布，則SC(A,r)＝(nr/V(A,r))。說明：V(A,r)與SC(A,r)中的A可以是屬性組。2021/4/179代價估算索引的統(tǒng)計信息fi

：樹形結構(如B+樹)索引i的內部結點的平均扇出。HTi

：索引i的層數。對于關系r的屬性A上所建的平衡樹索引（如B+樹），HTi＝Roof(logfi(V(A,r)))對于散列索引，HTi＝1LBi

：索引i中最低層索引塊數目，即索引葉層的塊數。對于散列索引，LBi就是索引中的塊數。算法A的代價估計記為EA2021/4/17109、人的價值，在招收誘惑的一瞬間被決定。2023/2/32023/2/3Friday,February3,202310、低頭要有勇氣，抬頭要有低氣。2023/2/32023/2/32023/2/32/3/20234:38:05PM11、人總是珍惜為得到。2023/2/32023/2/32023/2/3Feb-2303-Feb-2312、人亂于心，不寬余請。2023/2/32023/2/32023/2/3Friday,February3,202313、生氣是拿別人做錯的事來懲罰自己。2023/2/32023/2/32023/2/32023/2/32/3/202314、抱最大的希望，作最大的努力。03二月20232023/2/32023/2/32023/2/315、一個人炫耀什么，說明他內心缺少什么。。二月232023/2/32023/2/32023/2/32/3/202316、業(yè)余生活要有意義，不要越軌。2023/2/32023/2/303February202317、一個人即使已登上頂峰，也仍要自強不息。2023/2/32023/2/32023/2/32023/2/3查詢代價度量查詢代價：查詢處理對各種資源的使用情況磁盤存?。ê喕癁榇疟P塊傳送數）CPU時間通信開銷一個重要的影響因素：主存中緩沖區(qū)的大小M最好的情形，所有的數據可以讀入到緩沖區(qū)中最壞的情形，緩沖區(qū)只能容納數目不多的數據塊——大約每個關系一塊。2021/4/1712基本運算的實現與代價每個基本關系代數運算都有多種實現算法適合不同的情況等值條件vs范圍條件數據是聚集vs非聚集相關屬性上有索引vs沒有索引具有不同的執(zhí)行代價選擇、排序、連接、其它運算2021/4/1713選擇運算：全表掃描方法：依次訪問表的每一個塊，對于每一個元組，測試它是否滿足選擇條件。代價：E=br缺點：效率低優(yōu)點：對關系的存儲方式沒有要求，不需要索引。適用于任何選擇條件。2021/4/1714選擇運算：索引掃描條件：表在選擇條件的屬性上建有索引。方法：訪問索引，根據索引項的指示去訪問數據元組。無序索引：訪問滿足等值條件的元組有序索引：訪問滿足范圍查找條件的一系列元組。2021/4/1715選擇運算：索引掃描代價利用主索引，等值比較：E=HTi+Roof(SC(A,r)/fr)利用輔助索引，等值比較：E=HTi+SC(A,r)利用主索引，非等值比較：E=HTi+br/2（假設大約一半的元組滿足比較條件）利用輔助索引，非等值比較：E=HTi+LBi/2+nr/22021/4/1716選擇運算：復雜條件復雜條件的選擇合?。害姚?∧θ2∧…∧θn(r)析取：σθ1∨θ2∨…∨θn(r)方法利用一個索引進行合取選擇。利用組合索引進行合取選擇。利用多維索引進行合取選擇。通過標識符的交集進行合取選擇。通過標識符的并集進行析取選擇。2021/4/1717排序運算排序的必要性SQL查詢可能要求有序的查詢結果。事先對于作為運算對象的關系進行排序，可以提高某些關系運算（例如連接）的執(zhí)行效率。內排序：文件較小，整個排序過程都能在內存中進行許多成熟的算法外排序：文件較大，排序過程需要使用外存。以內排序為基礎2021/4/1718外排序：歸并算法設內存中用于排序的緩沖區(qū)頁面數為M第一階段，建立多個已排序的子表。每次讀入M塊，進行內排序，將長度為M塊的已排序子表（共Roof(br/M)個）寫到外存中。第二階段，對已排序子表進行歸并（可能需進行若干趟）。2021/4/1719外排序：歸并算法第二階段第一趟：將頭M-1個已排序子表的各塊逐步讀入內存，歸并并輸出。將下M-1個已排序子表的各塊逐步讀入內存，歸并并輸出。……已排序子表數目減少到原來的1/（M-1）第二趟：以第一趟的輸出作為輸入，重復過程。第三趟：以第二趟的輸出作為輸入，重復歸并過程……直至歸并為一個已排序文件。2021/4/1720外排序：歸并算法歸并過程將頭M-1個已排序子表的每個的第一塊讀入內存的一個緩沖頁repeat在所有緩沖頁中第一個元組中挑選排序碼值最小的元組；把該元組寫到第M緩沖頁，將其從原緩沖頁中刪除；if任何一個歸并段文件Ri的緩沖頁為空且沒有到達Ri末尾then讀入Ri的下一塊到相應的緩沖頁；if第M個緩沖頁滿then將第M個緩沖頁寫到磁盤，并清空該緩沖頁；until所有的緩沖頁均空將下M-1個已排序子表的每一個的第一塊讀入內存，歸并?！?2021/4/1721外排序：歸并算法

初始關系

歸并段文件歸并段文件

排序結果第一階段第二階段第二階段創(chuàng)建歸并段文件第一趟歸并第二趟歸并2021/4/1722外排序：歸并算法代價估算趟數=Roof(logM-1(br/M))E=br(2*Roof(logM-1(br/M))+1)第一階段：br第二階段：br*2*趟數（每趟的讀+寫）2021/4/1723連接運算二元運算，涉及兩個關系及連接條件條件連接：r|><|θs自然連接：r|><|s連接運算是非常重要的運算，有多種實現算法2021/4/1724連接運算自然連接結果集大小的估計：基于主碼、外碼連接的情況：結果集的元組數等于外碼所在關系的元組數。一般情況：（假設連接屬性A的每個值在關系的元組中等概率出現），結果集的元組數為：nr*(ns/V(A,s))或ns*(nr/V(A,r))當V(A,s)與V(A,r)不同時，取兩個估計值中較小者2021/4/1725連接運算：實現算法嵌套循環(huán)連接塊嵌套循環(huán)連接索引嵌套循環(huán)連接排序-歸并連接散列連接復雜連接的實現2021/4/1726連接運算：嵌套循環(huán)foreach元組trinrdobeginforeach元組tsinsdobegin測試元組對(tr,ts)是否滿足連接條件θ如果滿足，把trts加到結果中endend2021/4/1727連接運算：嵌套循環(huán)優(yōu)點：對參加運算的關系沒有要求，適合于任何連接條件。代價：最壞情況（緩沖區(qū)只能夠容納每個關系的一個塊）：nr*bs+br

或ns*br+bs最好情況（內層關系s能完全放在內存中）：bs+br2021/4/1728連接運算：塊嵌套循環(huán)塊嵌套循環(huán)連接：以塊的方式循環(huán)，以減少塊讀寫次數foreach塊Brofrdobeginforeach塊Bsofsdobeginforeach元組trinBrdobeginforeach元組tsinBsdobegin測試元組對(tr,ts)是否滿足連接條件θ如果滿足，把trts加到結果中endendendend2021/4/1729連接運算：塊嵌套循環(huán)優(yōu)點：對參加運算的關系沒有要求，適合于任何連接條件。代價：最壞情況（緩沖區(qū)只能夠容納每個關系的一個塊）：br*bs+br

或bs*br+bs最好情況（內層關系s能完全放在內存中）：bs+br

2021/4/1730連接運算：塊嵌套循環(huán)一些改進連接屬性是內層關系的碼時，內層循環(huán)可中途跳出。內層循環(huán)輪流做正、反向掃描，重用緩沖區(qū)中的數據，以減少磁盤讀取。內層循環(huán)利用索引。2021/4/1731連接運算：索引嵌套循環(huán)索引嵌套循環(huán)連接：在內層循環(huán)中利用連接屬性上的索引foreach元組trinrdobeginforeach與元組tr滿足連接條件的索引項ins關系在連接屬性上的索引dobegin利用索引取到相應的ts把trts加到結果中endend2021/4/1732對關系S使用連接條件利用索引進行選擇操作的代價連接運算：索引嵌套循環(huán)代價：最壞情況（緩沖區(qū)只能夠容納關系r的一個塊和索引的一個塊）：br+nr*c

或bs+ns*c最好情況不必考慮，因為不必采用索引嵌套循環(huán)連接方法。2021/4/1733連接運算：排序-歸并排序-歸并連接類似于外排序的歸并算法的思路，進行連接運算。前提：兩個關系的元組都已按連接屬性排好序。適用于自然連接和等值連接。2021/4/1734連接運算：排序-歸并a3b1d8d13f7m5q6aAaGcLdNmB

rsa1a2a1a3在歸并連接中使用的已排序關系rs2021/4/1735連接運算：排序-歸并pr:=r的第一個元組的地址ps:=s的第一個元組的地址；while(ps≠nullandpr≠null)dobegints:=ps所指向的元組；Ss:={ts}； 讓ps指向關系s的下一個元組；done:=false; while(notdoneandps≠null)dobegints’:=ps所指向的元組；

if(ts’[JoinAttrs]=ts[JoinAttrs])thenbeginSs:=Ss∪{ts’}； 讓ps指向關系s的下一個元組；

endelsedone:=true；

end在連接屬性上具有相同值的S元組被加入到了Ss中。Ps指向在連接屬性上具有另一個值的S元組。2021/4/1736連接運算：排序-歸并tr:=pr所指向的元組；

while(pr≠nullandtr[JoinAttrs]<ts[JoinAttrs])do begin

讓pr指向關系r的下一個元組；

tr:=pr所指向的元組；

end while(pr≠nullandtr[JoinAttrs]=ts[JoinAttrs])do beginforeachtsinSsdo begin將tstr加入結果中；end

讓pr指向關系r的下一個元組；

tr:=pr所指向的元組；

endend在r中跳過中不能與Ss中的s元組匹配的r元組。在r中前進，將r元組與Ss中的每個s元組連接，直至r元組中的連接屬性值大于s元組的連接屬性值。

2021/4/1737連接運算：排序-歸并

在歸并連接中使用的已排序關系代價：br+bsa3b1d8d13f7m5q6aAaGcLdNmBprpsa1a2a1a3在歸并連接中使用的已排序關系rs2021/4/1738連接運算：散列連接適用于自然連接和等值連接。非等值/范圍基本思想將兩個關系按連接屬性值劃分成有相同散列函數值的元組集合。關系r在一個散列劃分中的元組只需要與關系s在對應的劃分中的元組相比較。在r和s的每一對劃分中進行索引嵌套循環(huán)連接（散列索引）。2021/4/1739連接運算：散列連接方法：確定連接屬性上的散列函數h，用于對s元組和r元組進行劃分。確定連接屬性上的散列函數h’，用于逐個對每一劃分中的s元組構造散列索引，再對同一劃分中的r元組查找散列索引，同時進行連接。2021/4/1740連接運算：散列連接rs關系r的散列劃分關系s的散列劃分01234012342021/4/1741連接運算：復雜連接合取式：r|><|1∧2∧…∧ns

用一種高效技術計算某一條件下的連接r|><|1s，在生成結果元組時測試其他條件。析取式：r|><|1∨2∨…∨ns==>r|><|1sr|><|2s…r|><|ns2021/4/1742其它運算消除重復用排序的方法用散列的方法投影投影，消除重復并、交、差排序的方法散列的方法2021/4/1743其它運算外連接計算連接，然后將適當的元組加到結果中。例r]><|θs計算r|><|θs==>q1計算r-∏r(q1)，在s對應的分量填上空值，加到q1中。聚集排序的方法散列的方法2021/4/1744關系代數表達式實現Пcustomer_name(σbalance<2500(account)|><|customer)Пcustomer_nameσbalance<2500customeraccount|><|2021/4/1745關系代數表達式實現實體化的方法建立臨時關系代價：各個運算的代價加上中間結果寫到磁盤的代價。(nr/fr)流水線的方法不建臨時關系，一個操作的結果傳給下一個操作作為輸入。2021/4/1746關系代數表達式實現流水線的實現：需求驅動：在操作樹的頂端將數據往上拉。生產者驅動：將數據從操作樹的底層往上推需求驅動的流水線方法比生產者驅動的流水線方法使用更廣泛，因為它更容易實現。2021/4/1747關系代數表達式實現權衡：流水線技術限制了實現操作的可用算法。例：若連接運算的左端輸入來自流水線，則不可用排序-歸并連接算法，可用索引嵌套循環(huán)連接算法。若連接運算的兩端輸入均來自流水線，則限制更大。并非所有情況下都是流水線方法的代價小于實體化方法的代價2021/4/1748關系代數表達式轉換查詢優(yōu)化是為關系代數表達式的計算選擇最有效的查詢計劃的過程。查詢優(yōu)化的過程：代數優(yōu)化：力圖找出與給定關系代數表達式等價的但執(zhí)行效率更高的一個表達式。

查詢語句處理的詳細策略的選擇，例如選擇執(zhí)行運算所采用的具體算法，選擇將使用的特定索引等等。2021/4/1749等價表達式兩個表達式等價：產生的結果關系具有相同的屬性集和相同的元組集。例Пcustomer_name(σbranch-city=”Brooklyn”

(branch|><|(account|><|depositor)))等價于Пcustomer_name((σbranch-city=”Brooklyn”(branch))|><|(account|><|