基于R樹的空間查詢連接處理優化與實現

呂閩暉 ，呂敏蓉

(1.海軍工程大學 裝備經濟研究所，湖北 武漢 430033；2.湖南女子學院，湖南 長沙 410004)

常見的空間查詢有點查詢、窗口查詢 (或稱范圍查詢)、相交查詢(或稱區域查詢)、被包圍查詢、毗連查詢、最近鄰查詢、空間連接查詢等，其中空間連接查詢是最重要、最耗時的空間查詢[1]。本文首先對Ingres原有空間連接方式進行研究。然后參照已有的相關研究論文，采用基于寬度優先的R樹空間連接算法，并對其進行全面測試(包括功能和性能測試)，并與 Ingres原有空間連接進行性能對比。

1 Ingres空間連接算法

Ingres原有的空間連接執行時，如果兩個表都建有R樹索引，其QEP為TID Join。如有兩個表RTreeJoin1和RTreeJoin2，對應的空間索引為 RTree1和 RTree2，如果執行 Select*from RTreeJoin1，RTreeJoin2 where RTreeJoin1.obj overlaps RTreeJoin2.obj，QEP如圖 1所示。

圖1 Ingres原有空間連接QEP

圖中Spatial Join即Key Join，首先是將RTreeJoin1.obj的值作為鍵值查找索引RTree2，所得對應RTreeJoin2中的TID，然后再以此TID直接訪問RTreeJoin2中的元組，即TID Join。此種方式沒有利用兩個基表都建有RTree的優勢，因此在部分情況下不能獲得最優的性能。這種方法稱為“One-Rtree-Only”空間連接方法[2]。

2 Ingres空間連接算法改進

針對上述分析，希望能夠在過濾階段即利用兩個R樹索引。通過對兩個索引進行按深度或按寬度的遍歷，執行過濾運算，不可能滿足連接條件的空間對象迅速排除[3-4]。本文將參考文獻[5]使用廣度優先遍歷算法優化R樹空間連接。

2.1 在遍歷R樹時剪枝

在R樹中維護的一個重要信息就是它的層次性蘊含著它的包含性。即一個樹結點的MBR總是包圍著它的子孫結點的MBR。利用這一特點可知，一對結點nRir和nSjS需要進行連接僅當它們父結點的MBR相交，稱為剪枝。簡單的從頂至底的圖遍歷算法可以在任何層次上使用這種剪枝。參考文獻[5]中剪枝是在同時深度優先遍歷兩棵輸入的R樹時進行的 (DFRJ)，而參考文獻[6]則是在同時廣度優先遍歷兩棵R樹時進行的(BFRJ)。在R樹的所有層次施行剪枝達到的效果是從頂層起，分別來自兩棵R樹的兩個結點被遍歷到僅當它們父結點的MBR相交。這樣，相比簡單的嵌套循環的遍歷方式，剪枝將使得被遍歷的不相交的結點對數大大減少。

2.2 BFRJ算法

基于廣度優先遍歷的R樹空間連接算法 (BFRJ)步驟為：(1)對兩棵R樹的根結點(NR，NS)做一次結點連接。所謂結點連接，就是對輸入的兩個非葉子結點，返回其相交的元素項對。對根結點做結點連接的結果是一個二元組(oidR0，oidS0)的集合，稱為 0階中間連接索引 IJI0(intermediate join index at level 0)。因為本文主要著眼于對相交運算的空間連接，因此每一個二元組(oidR0，oidS0)意味著這兩個元素項的MBR相交。(2)對于IJI0的每一個二元組，BFRJ找出其在兩棵R樹中對應的結點，進行結點連接。當BFRJ從IJI0中讀入一個二元組進行計算時，它會以二元組(oidR1，oidS1)的形式保存結果，加入當前的1階中間連接索引IJI1。當BFRJ處理完IJI0中的所有二元組后，它會釋放IJI0并開始對IJI1進行相應的連接操作。這個過程隨著BFRJ算法逐層遍歷R樹而繼續著。當中間連接索引由兩棵R樹的葉子結點產生時，算法終止。如果兩棵R樹不等高，算法將在到達一棵樹的葉子結點(如R)時，枚舉葉子結點中的每一個元素項對另一棵樹S中對應子樹做查詢操作。到此，空間連接過濾環節已經結束，當前的(葉子級的)IJI已經不在空間連接的范疇之內了。

2.3 局部優化技術

局部優化技術是在結點連接的過程中進行的。在參考文獻[6]中介紹了兩種局部優化技術，分別為搜索空間限制(Search Space Restriction)和平面掃描(Plane Sweep)。

2.3.1 搜索空間限制

在一對結點nRir和nSjS進行連接時，它們的MBR的交叉區域仍然是 MBR(稱為 intersect-MBR)。如果nRir中的元素項(oidRir，mrbRir)x同nSjS中的元素項(oidSjS，mrbSjS)y相交，則mrbRir和mrbSjS必須同兩個結點的intersect-MBR相交。因此，可以首先對nRir和nSjS的元素項分別進行掃描，排除掉那些MBR同intersect-MBR不相交的元素項。在進行結點連接時，僅對剩余項進行連接。

2.3.2 平面掃描

這一優化方式同合并兩個普通的數據集合時采用的排序-歸并技術類似。在一對結點nRir和nSjS進行連接的過程中，首先分別對兩個結點中的元素項依MBR進行排序。為了對多維數據進行排序，用MBR的最小x值作為關鍵字。在合并階段，依次對排序的MBR進行掃描。對于一棵樹中的MBR，僅對于其x坐標相交的MBR進行相交測試。

這兩種優化技術各有側重，搜索空間限制技術可以對于結點容量較大但元素項分散的數據進行較大優化，而平面掃描對于多維數據的優勢更大。

2.4 全局優化技術

在BFRJ算法框架下，i階中間連接索引(IJIi)在兩棵樹中所有的i層結點連接完畢后產生。而在i層進行結點連接的結點對來自于由更高的 (i-1層)結點連接產生。因此可以在對一層結點進行結點連接之前，獲取該層所有結點訪問預計(包括它們可能的訪問順序和重復訪問次數)的全局信息，可以利用一些技術來對中間連接索引進行高效的管理。

2.4.1 中間連接索引排序

設結點的MBR同R樹S的k個t級結點的MBR相交，則nRit的索引ID在IJIt-1中出現了k次。在計算t層的結點連接時，nRit將被恰好計算k次。對于一個固定大小的LRU系統緩沖，如果ID在IJIt-1中出現的比較分散，則結點nRit將從硬盤中被多次讀取(最多k次)。這是因為第一次和后面出現的對nRit的調用之間可能會比較遠，在需要被再次讀入時可能已經從緩沖區中刪除。因此希望IJI能夠維護在一種有序的狀態下，使得多次出現的相同結點的ID在IJI中出現的位置不要分散得太過稀疏。

2.4.2 中間連接索引內存管理

IJI可以被存儲在內存中或是磁盤上。前者能提高IJI排序的效率并減少讀取IJI時多余的I/O操作；而后者能解放出更多的內存資源用于連接計算。

2.4.3 中間連接索引緩沖管理

IJI排序技術傾向于維護索引的順序，使得任意兩個相同ID出現的位置不會相隔太遠。然而，對兩個項目都實現很好的聚類效果是不可能的，在連接運算中，對一個結點的多次磁盤讀取依然存在。如果緩沖管理可以預測哪個結點已經連接完畢，而哪個結點將來還會參與運算，則這種多次讀取可以被進一步縮減。用這種方式，緩沖管理可以保留那些將來還會參與運算的結點頁面，而將已經結束所有連接運算的結點頁面清理釋放。

3 實驗結果

采用實際數據進行實驗。實驗數據來自www.rtreeportal.org的兩個數據組：

(1)“Germany”數據組，包含四個數據包：

①“roads”：包含了德國的30 674條街道的 MBR；

②“rrlines”：包含了36 334條鐵路線的MBR；

③“utility”：包含了17 790條公用網絡的 MBR；

④“hypsogr”：地勢圖，由 76 999個 MBR組成。

(2)“Greece”數據組，包含兩個數據包：

①“roads”：包含了希臘的23 268條街道的 MBR；

②“rivers”：包含了 24 650條河流的 MBR。

將這些數據包組成四個連接對進行實驗，即“Germany：roads，rrlines”，“Germany：roads，utility”，“Germany：roads，hypsogr”，“Greece：roads，rivers”。

在實驗中，固定了R樹的頁面大小，這樣，影響連接性能的主要參數除了使用的方法外即為緩沖大小。用緩沖區最多存放R樹頁面的個數作為衡量緩沖大小的參數，這樣在不失一般性的同時可以簡化緩沖管理操作在程序內實現。

表1～表 4 給出了連接對 “Germany：roads，rrlines”的實驗結果，其中的數據表示在給定的緩沖大小下給定空間連接方法在給定緩沖大小下對應的頁面I/O次數m。

表1 連接對“Germany：roads，rrlines”實驗結果

表2 連接對“Germany：roads， utility”實驗結果

表3 連接對“Germany：roads， hypsogr”實驗結果

表4 連接對“Greece：rivers，roads”實驗結果

從實驗結果分析各連接方法，Buff size表示緩沖區大小，One-Rree-Only表示只對一個數據包建R樹；DFRJ表示使用DFRJ方法進行R樹連接；OrdOneStorDiskPinNo表示采用基于磁盤存儲的非特定排序優化組合BFRJ方法進行空間連接；OrdOneStorMemPinYes表示采用基于主存存儲的對單棵樹排序優化組合BFRJ方法進行空間連接，OrdSumStorMemPinYes表示采用基于主存存儲的對中值和排序的優化組合BFRJ方法進行空間連接。由于StorMem意味著要將IJI保存在主存中，因此對緩沖大小有要求，當緩沖較小時則不適用，對應的表格項為N/A。

在真實數據的條件下，對于任意的緩沖大小，基于兩棵R樹的空間連接算法(DFRJ和BFRJ)的性能總是優于基于一棵R樹的算法(One-Rree-Only)。而在R樹空間連接方法中，使用適當全局優化組合的BFRJ又明顯優于DFRJ。在緩沖較小時，OrdOneStorDiskPinNo最適用；在適中的緩沖條件下，StorDisk的性能要比StorMem差，OrdOneStorMemPinYes相對更優；而在較大的緩沖條件下，OrdSumStorMemPinYes能夠獲得最好的空間連接性能。

[1]KAMEL I， FALOUTSOS C.Hilbert R-tree： An improved R-treeusingfractals[M].In： Proceedingsofthe20th VLDB， Santiago， Chile， 1994，500-509.

[2]HUANG P W， LIN P L， LIN H Y.Optimizing storage utilizationinR-treedynamicindexstructureforspatialdatabases[J].Journal of Systems and Software， 2001，55(3)：291-299.

[3]BRAKATSOULAS S， PFOSER D， THEODORIDIS Y.Revisiting R-tree construction principles[M].In：Proceedings of the 6th ADBIS， Bratislava， Slovakia， 2002，149-162.

[4]BRINKHOFF T， KRIEGEL H.P， SEEGER B.Efficient processing of spatial joins using R-trees[M].In：Proceedings of ACM SIGMOD， Washington DC， 1993，237-246.

[5]MARTYNOV M.Spatial joins and R-trees.In：Proceedings of the 3rd ADBIS[M]， Moscow， Russia， 1995，295-304.

[6]HUANG Y W，JING N，RUNDENSTEINER E.Spatial joins using R-trees：Breadth First traversal with global optimizations.In：Proceedingsofthe23rdVLDB，Athens，Greece，1997，396-405.