空間數(shù)據(jù)庫PPT課件

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

2、處理基本步驟第3頁/共51頁查詢優(yōu)化概念 查詢優(yōu)化是為關系代數(shù)表達式的計算選擇最有效的查詢計劃的過程 查詢執(zhí)行計劃：用于計算查詢的原語序列 執(zhí)行原語：加了“如何執(zhí)行”注釋的關系代數(shù)運算（選擇、投影） 根據(jù)選擇的算法對文件記錄進行操作第4頁/共51頁查詢優(yōu)化過程 代數(shù)優(yōu)化 力圖找出與給定關系代數(shù)表達式等價的但執(zhí)行效率更高的一個表達式 執(zhí)行策略選擇 對查詢語句處理的詳細策略的選擇 選擇執(zhí)行運算所采用的具體算法 選擇將使用的特定索引等等第5頁/共51頁查詢優(yōu)化過程 可能性 SQL語言和關系代數(shù)表達式的非過程化特點 可行性 查詢優(yōu)化器具有豐富的可使用信息 數(shù)據(jù)庫發(fā)生變化時優(yōu)化器容易再次進行優(yōu)化 優(yōu)化器

3、能夠?qū)Χ喾N實現(xiàn)策略逐一進行考慮 優(yōu)化器集中了最優(yōu)秀的程序員的智慧和經(jīng)驗 第6頁/共51頁代價估算 關系的統(tǒng)計信息 nr：關系r中的元組數(shù)目(number) br：含有關系r的元組的塊數(shù)目(block) sr：關系r中一個元組的大小(size) fr：關系r的塊因子，即一個塊中能存放的關系r的元組數(shù)(factor) 若假定關系r的元組物理上存于同一文件中，則： br = Roof(nr / fr)第7頁/共51頁代價估算 關系的統(tǒng)計信息 V(A,r) ：關系r中屬性A所具有的不同值的數(shù)目。 V(A,r)等于A(r)的大小 若A為關系r的碼，則V(A,r) = nr SC(A,r) ：關系r的屬性

4、A的選擇基數(shù)。表示關系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可以是屬性組。第8頁/共51頁代價估算 索引的統(tǒng)計信息 fi ：樹形結(jié)構(如B+樹)索引i的內(nèi)部結(jié)點的平均扇出。 HTi ：索引i的層數(shù)。 對于關系r的屬性A上所建的平衡樹索引（如B+樹），HTiRoof(logfi(V(A,r) 對于散列索引，HTi1 LBi ：索引i中最低層索引塊數(shù)目，即索引葉層的塊數(shù)。 對于散列索引，LBi就是索引中的

5、塊數(shù)。 算法A的代價估計記為EA第9頁/共51頁查詢代價度量 查詢代價：查詢處理對各種資源的使用情況 磁盤存取 （簡化為磁盤塊傳送數(shù)） CPU時間 通信開銷 一個重要的影響因素：主存中緩沖區(qū)的大小M 最好的情形，所有的數(shù)據(jù)可以讀入到緩沖區(qū)中 最壞的情形，緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊大約每個關系一塊。 第10頁/共51頁基本運算的實現(xiàn)與代價 每個基本關系代數(shù)運算都有多種實現(xiàn)算法 適合不同的情況 等值條件 vs 范圍條件 數(shù)據(jù)是聚集 vs 非聚集 相關屬性上有索引 vs 沒有索引 具有不同的執(zhí)行代價 選擇、排序、連接、其它運算第11頁/共51頁選擇運算：全表掃描 方法：依次訪問表的每一個塊，對于

6、每一個元組，測試它是否滿足選擇條件。 代價：E = br 缺點：效率低 優(yōu)點： 對關系的存儲方式?jīng)]有要求，不需要索引。 適用于任何選擇條件。第12頁/共51頁選擇運算：索引掃描 條件：表在選擇條件的屬性上建有索引。 方法：訪問索引，根據(jù)索引項的指示去訪問數(shù)據(jù)元組。 無序索引：訪問滿足等值條件的元組 有序索引：訪問滿足范圍查找條件的一系列元組。第13頁/共51頁選擇運算：索引掃描代價 利用主索引，等值比較： E = HTi + Roof(SC(A,r) / fr) 利用輔助索引，等值比較： E = HTi + SC(A,r) 利用主索引，非等值比較： E = HTi + br/2 （假設大約一半

7、的元組滿足比較條件） 利用輔助索引，非等值比較： E = HTi + LBi/2 + nr/2第14頁/共51頁選擇運算：復雜條件 復雜條件的選擇 合?。?2n(r) 析取：12n(r) 方法 利用一個索引進行合取選擇。 利用組合索引進行合取選擇。 利用多維索引進行合取選擇。 通過標識符的交集進行合取選擇。 通過標識符的并集進行析取選擇。 第15頁/共51頁排序運算 排序的必要性 SQL查詢可能要求有序的查詢結(jié)果。 事先對于作為運算對象的關系進行排序，可以提高某些關系運算（例如連接）的執(zhí)行效率。 內(nèi)排序：文件較小，整個排序過程都能在內(nèi)存中進行 許多成熟的算法 外排序：文件較大，排序過程需要使用

8、外存。 以內(nèi)排序為基礎 第16頁/共51頁外排序：歸并算法 設內(nèi)存中用于排序的緩沖區(qū)頁面數(shù)為M 第一階段，建立多個已排序的子表。 每次讀入M塊，進行內(nèi)排序，將長度為M塊的已排序子表（共Roof(br /M)個）寫到外存中。 第二階段，對已排序子表進行歸并（可能需進行若干趟）。第17頁/共51頁外排序：歸并算法第二階段 第一趟：將頭M-1個已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出。 將下M-1個已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出。 已排序子表數(shù)目減少到原來的1/（M-1） 第二趟：以第一趟的輸出作為輸入，重復過程。 第三趟：以第二趟的輸出作為輸入，重復歸并過程 直至歸并為一個已排序文件。第

9、18頁/共51頁外排序：歸并算法歸并過程 將頭M-1個已排序子表的每個的第一塊讀入內(nèi)存的一個緩沖頁 repeat 在所有緩沖頁中第一個元組中挑選排序碼值最小的元組； 把該元組寫到第M緩沖頁，將其從原緩沖頁中刪除； if 任何一個歸并段文件Ri的緩沖頁為空且沒有到達Ri末尾 then 讀入Ri的下一塊到相應的緩沖頁； if 第M個緩沖頁滿 then 將第M個緩沖頁寫到磁盤，并清空該緩沖頁； until 所有的緩沖頁均空 將下M-1個已排序子表的每一個的第一塊讀入內(nèi)存，歸并。 .第19頁/共51頁外排序：歸并算法 初始關系初始關系 歸并段文件歸并段文件 歸并段文件歸并段文件 排序結(jié)果排序結(jié)果 第一

10、階段第一階段 第二階段第二階段 第二階段第二階段 創(chuàng)建歸并段文件創(chuàng)建歸并段文件 第一趟歸并第一趟歸并 第二趟歸并第二趟歸并第20頁/共51頁外排序：歸并算法代價估算 趟數(shù) = Roof(logM-1( br /M ) E = br ( 2*Roof(logM-1( br /M ) + 1 ) 第一階段：br 第二階段：br*2*趟數(shù)（每趟的讀+寫）第21頁/共51頁連接運算 二元運算，涉及兩個關系及連接條件 條件連接：r | s 連接運算是非常重要的運算，有多種實現(xiàn)算法第22頁/共51頁連接運算 自然連接結(jié)果集大小的估計： 基于主碼、外碼連接的情況：結(jié)果集的元組數(shù)等于外碼所在關系的元組數(shù)。 一

11、般情況：（假設連接屬性A的每個值在關系的元組中等概率出現(xiàn)）， 結(jié)果集的元組數(shù)為： nr*(ns /V(A,s) 或 ns*( nr /V(A,r) 當V(A,s)與V(A,r)不同時，取兩個估計值中較小者第23頁/共51頁連接運算：實現(xiàn)算法 嵌套循環(huán)連接 塊嵌套循環(huán)連接 索引嵌套循環(huán)連接 排序-歸并連接 散列連接 復雜連接的實現(xiàn) 第24頁/共51頁連接運算：嵌套循環(huán) for each 元組tr in r do begin for each 元組ts in s do begin 測試元組對(tr,ts)是否滿足連接條件 如果滿足，把tr ts加到結(jié)果中 end end第25頁/共51頁連接運算：

12、嵌套循環(huán) 優(yōu)點：對參加運算的關系沒有要求，適合于任何連接條件。 代價： 最壞情況（緩沖區(qū)只能夠容納每個關系的一個塊）： nr*bs + br 或 ns*br + bs 最好情況（內(nèi)層關系s能完全放在內(nèi)存中）： bs + br 第26頁/共51頁連接運算：塊嵌套循環(huán) 塊嵌套循環(huán)連接：以塊的方式循環(huán)，以減少塊讀寫次數(shù) for each 塊Br of r do begin for each 塊Bs of s do begin for each 元組tr in Br do begin for each 元組ts in Bs do begin 測試元組對(tr,ts)是否滿足連接條件 如果滿足，把tr

13、ts加到結(jié)果中 end end end end第27頁/共51頁連接運算：塊嵌套循環(huán) 優(yōu)點：對參加運算的關系沒有要求，適合于任何連接條件。 代價： 最壞情況（緩沖區(qū)只能夠容納每個關系的一個塊）： br * bs + br 或 bs * br + bs 最好情況（內(nèi)層關系s能完全放在內(nèi)存中）： bs + br 第28頁/共51頁連接運算：塊嵌套循環(huán) 一些改進 連接屬性是內(nèi)層關系的碼時，內(nèi)層循環(huán)可中途跳出。 內(nèi)層循環(huán)輪流做正、反向掃描，重用緩沖區(qū)中的數(shù)據(jù)，以減少磁盤讀取。 內(nèi)層循環(huán)利用索引。 第29頁/共51頁連接運算：索引嵌套循環(huán) 索引嵌套循環(huán)連接：在內(nèi)層循環(huán)中利用連接屬性上的索引 for ea

14、ch 元組 tr in r do begin for each 與元組tr滿足連接條件的索引項 in s關系在連接屬性上的索引 do begin 利用索引取到相應的ts 把tr ts加到結(jié)果中 end end第30頁/共51頁對關系S使用連接條件利用索引進行選擇操作的代價連接運算：索引嵌套循環(huán) 代價： 最壞情況（緩沖區(qū)只能夠容納關系r的一個塊和索引的一個塊）： br + nr * c 或 bs + ns * c 最好情況不必考慮，因為不必采用索引嵌套循環(huán)連接方法。 第31頁/共51頁連接運算：排序-歸并 排序-歸并連接 類似于外排序的歸并算法的思路，進行連接運算。 前提：兩個關系的元組都已按連

15、接屬性排好序。 適用于自然連接和等值連接。第32頁/共51頁連接運算：排序-歸并a3b1d8d13f7m5q6aAaGcLdNmB r sa1a2a1a3在歸并連接中使用的已排序關系在歸并連接中使用的已排序關系rs第33頁/共51頁連接運算：排序-歸并pr := r的第一個元組的地址ps := s的第一個元組的地址；while (psnull and prnull) dobegin ts := ps所指向的元組； Ss := ts ； 讓ps指向關系s的下一個元組； done := false; while (not done and psnull) do begin ts:= ps所指向的元

16、組； if (tsJoinAttrs = tsJoinAttrs) then begin Ss := Ss ts； 讓ps指向關系s的下一個元組； end else done := true； end在連接屬性上具有相同值的S元組被加入到了Ss中。Ps指向在連接屬性上具有另一個值的S元組。第34頁/共51頁連接運算：排序-歸并 tr := pr所指向的元組；while (prnull and trJoinAttrs r | q1 計算 r -r(q1)，在s對應的分量填上空值，加到q1中。 聚集 排序的方法 散列的方法第42頁/共51頁關系代數(shù)表達式實現(xiàn) customer_name(balance |customer)customer_name balance | depositor) 第48頁/共51頁等價表達式customer_namebranch_city=”Brooklyn”branchaccountdepositorcu