空間數(shù)據(jù)庫(kù)精品課件

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

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

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

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

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

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

初始關(guān)系

歸并段文件歸并段文件

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

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

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

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

或bs+ns*c最好情況不必考慮，因?yàn)椴槐夭捎盟饕短籽h(huán)連接方法。2021/4/1733連接運(yùn)算：排序-歸并排序-歸并連接類似于外排序的歸并算法的思路，進(jìn)行連接運(yùn)算。前提：兩個(gè)關(guān)系的元組都已按連接屬性排好序。適用于自然連接和等值連接。2021/4/1734連接運(yùn)算：排序-歸并a3b1d8d13f7m5q6aAaGcLdNmB

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

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

endelsedone:=true；

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

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

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

tr:=pr所指向的元組；

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

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

tr:=pr所指向的元組；

endend在r中跳過(guò)中不能與Ss中的s元組匹配的r元組。在r中前進(jìn)，將r元組與Ss中的每個(gè)s元組連接，直至r元組中的連接屬性值大于s元組的連接屬性值。

2021/4/1737連接運(yùn)算：排序-歸并

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

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

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

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