空間數(shù)據(jù)庫（7）

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

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

：樹形結(jié)構(gòu)(如B+樹)索引i的內(nèi)部結(jié)點的平均扇出。HTi

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

：索引i中最低層索引塊數(shù)目，即索引葉層的塊數(shù)。對于散列索引，LBi就是索引中的塊數(shù)。算法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、一個人炫耀什么，說明他內(nèi)心缺少什么。。二月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塊傳送數(shù)）CPU時間通信開銷一個重要的影響因素：主存中緩沖區(qū)的大小M最好的情形，所有的數(shù)據(jù)可以讀入到緩沖區(qū)中最壞的情形，緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊——大約每個關(guān)系一塊。2021/4/1712基本運算的實現(xiàn)與代價每個基本關(guān)系代數(shù)運算都有多種實現(xiàn)算法適合不同的情況等值條件vs范圍條件數(shù)據(jù)是聚集vs非聚集相關(guān)屬性上有索引vs沒有索引具有不同的執(zhí)行代價選擇、排序、連接、其它運算2021/4/1713選擇運算：全表掃描方法：依次訪問表的每一個塊，對于每一個元組，測試它是否滿足選擇條件。代價：E=br缺點：效率低優(yōu)點：對關(guān)系的存儲方式?jīng)]有要求，不需要索引。適用于任何選擇條件。2021/4/1714選擇運算：索引掃描條件：表在選擇條件的屬性上建有索引。方法：訪問索引，根據(jù)索引項的指示去訪問數(shù)據(jù)元組。無序索引：訪問滿足等值條件的元組有序索引：訪問滿足范圍查找條件的一系列元組。2021/4/1715選擇運算：索引掃描代價利用主索引，等值比較：E=HTi+Roof(SC(A,r)/fr)利用輔助索引，等值比較：E=HTi+SC(A,r)利用主索引，非等值比較：E=HTi+br/2（假設(shè)大約一半的元組滿足比較條件）利用輔助索引，非等值比較：E=HTi+LBi/2+nr/22021/4/1716選擇運算：復(fù)雜條件復(fù)雜條件的選擇合取：σθ1∧θ2∧…∧θn(r)析?。害姚?∨θ2∨…∨θn(r)方法利用一個索引進行合取選擇。利用組合索引進行合取選擇。利用多維索引進行合取選擇。通過標(biāo)識符的交集進行合取選擇。通過標(biāo)識符的并集進行析取選擇。2021/4/1717排序運算排序的必要性SQL查詢可能要求有序的查詢結(jié)果。事先對于作為運算對象的關(guān)系進行排序，可以提高某些關(guān)系運算（例如連接）的執(zhí)行效率。內(nèi)排序：文件較小，整個排序過程都能在內(nèi)存中進行許多成熟的算法外排序：文件較大，排序過程需要使用外存。以內(nèi)排序為基礎(chǔ)2021/4/1718外排序：歸并算法設(shè)內(nèi)存中用于排序的緩沖區(qū)頁面數(shù)為M第一階段，建立多個已排序的子表。每次讀入M塊，進行內(nèi)排序，將長度為M塊的已排序子表（共Roof(br/M)個）寫到外存中。第二階段，對已排序子表進行歸并（可能需進行若干趟）。2021/4/1719外排序：歸并算法第二階段第一趟：將頭M-1個已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出。將下M-1個已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出。……已排序子表數(shù)目減少到原來的1/（M-1）第二趟：以第一趟的輸出作為輸入，重復(fù)過程。第三趟：以第二趟的輸出作為輸入，重復(fù)歸并過程……直至歸并為一個已排序文件。2021/4/1720外排序：歸并算法歸并過程將頭M-1個已排序子表的每個的第一塊讀入內(nèi)存的一個緩沖頁repeat在所有緩沖頁中第一個元組中挑選排序碼值最小的元組；把該元組寫到第M緩沖頁，將其從原緩沖頁中刪除；if任何一個歸并段文件Ri的緩沖頁為空且沒有到達Ri末尾then讀入Ri的下一塊到相應(yīng)的緩沖頁；if第M個緩沖頁滿then將第M個緩沖頁寫到磁盤，并清空該緩沖頁；until所有的緩沖頁均空將下M-1個已排序子表的每一個的第一塊讀入內(nèi)存，歸并。…….2021/4/1721外排序：歸并算法

初始關(guān)系

歸并段文件歸并段文件

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

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

或bs*br+bs最好情況（內(nèi)層關(guān)系s能完全放在內(nèi)存中）：bs+br

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

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

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

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

endelsedone:=true；

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

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

讓pr指向關(guān)系r的下一個元組；

tr:=pr所指向的元組；

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

讓pr指向關(guān)系r的下一個元組；

tr:=pr所指向的元組；

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

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

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

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

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

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