Due to the high complexity and large volume of spatial data, a spatial query has been processed in two steps, called the filter step and the refinement step. However, the two-step processing of the spatial query has been considered locally in one spatial predicate evaluation at the query execution level. This thesis presents query optimization strategies which exploit the two-step processing of a spatial query at the query optimization level. The first strategy involves the separation of filter and refinement steps not in the query execution phase but in the query optimization phase. As the second strategy, several refinement operations can be combined if they were already separated, and as the third strategy several filter operations can also be combined. We call the optimization technique utilizing these strategies the Early Separated Filter And Refinement (ESFAR). We define the Spatial Object Algebra (SOA), which extends a normal object algebra to process spatial predicates as well, and use SOA to represent the input query of our optimizer. This thesis also presents an algebra, which is called the Intermediate Spatial Object Algebra (ISOA), and optimization rules for ESFAR.
Actually the ESFAR optimizer always generates more efficient execution plans than the traditional optimizer because the ISOA operators include the traditional operators and the ESFAR rules include the traditional optimization rules. However, because of more operators and more rules, the ESFAR optimizer consumes more optimization time than the traditional optimizer. In this thesis, we apply two well known heuristic algorithms, the iterative improvement (II) and the simulated annealing (SA), to the ESFAR optimizer. Additionally we propose a new heuristic algorithm to find a good initial state of II and SA.
We also propose a new multi-way spatial join algorithm called M-way R-tree join (MRJ) which synchronously traverses M R-trees. MRJ can be considered as a generalization of the 2-way R-tree join. Although a generalization of the 2-way R-tree join has recently been studied, it did not properly take into account the optimization techniques, search space restriction and plane sweep, of the original algorithm. Here, we extend these optimization techniques for multi-way spatial joins. Since the join ordering was considered to be important in the multi-way join literature (e.g., relational join), we especially consider the ordering of the search space restriction and the plane sweep. Additionally, we introduce indirect predicates in MRJ and propose an optimization technique called indirect predicate filtering (IPF) to improve the performance of MRJ.
Recently, formulae of estimating the result sizes of multi-way spatial joins for two kinds of query types, tree and clique, were developed. However, the formulae considered only the placement distribution of spatial data by assuming that the placements of all spatial objects are uniformly distributed. Therefore, the formulae are satisfied only in some special cases of the area distribution. This thesis extends the formula to the arbitrary area of spatial data, and then analyzes the characteristics and complexities of the extended formula. Especially, we describe the number and sort of the statistics which the query optimizer should keep in order to calculate the multi-way join result size.
공간 데이타의 복잡성과 방대함으로 인해 공간 질의는 여과 단계와 정제 단계로 불리는 이단계로 처리되어 왔다. 그러나 공간 질의의 이런한 이단계 처리 기법은 질의 실행 단계에서의 공간 술어 처리에 국한되어 고려되었다. 본 논문에서는 공간 질의의 이단계 처리 기법을 질의 최적화 단계에서 부터 활용할 수 있는 질의 최적화 전략을 제시한다. 첫번째 전략은 여과 단계와 정제 단계를 질의 실행 단계가 아닌 질의 최적화 단계에서 분리하는 것이다. 두번째 전략으로는 여러 정제 단계들이 합쳐질 수 있고, 세번째 전략으로는 여러 여과 단계도 합쳐질 수 있다. 우리는 이러한 전략들을 이용하는 질의 최적화 기법을 여과/정제 조기 분리(ESFAR) 최적화 기법이라 부른다. 우리는 일반 객체 대수를 공간 술어 까지 처리할 수 있도록 확장한 공간 객체 대수(SOA)를 정의하고, 본 논문에서 질의를 대수적 형태로 표현하는데 SOA를 사용한다. 본 논문에서는 또한 중간 공간 객체 대수(ISOA)라 불리는 새로운 대수와 ESFAR를 위한 새로운 질의 최적화 규칙을 제안한다.
ISOA 연산자가 종래 최적화기의 연산자를 모두 포함하고 ESFAR 규칙이 종래 최적화기의 규칙을 모두 포함하므로, ESFAR 질의 최적화기는 종래의 질의 최적화기에 비해 항상 보다 효율적인 실행 계획을 생성한다. 그러나 이렇게 많은 연산자와 규칙 때문에 ESFAR 최적화기는 종래의 최적화기에 비해 보다 많은 질의 최적화 시간을 필요로 한다. 본 논문에서는 반복 개선 기법(II)과 모의 담금질 기법(SA)으로 알려져 있는 두개의 경험적 알고리즘을 ESFAR 최적화기에 적용한다. 추가적으로 우리는 II와 SA에서 좋은 초기 상태를 찾기 위한 새로운 경험적 알고리즘도 제안한다.
우리는 또한 다중 R-트리 조인(MRJ)이라 불리는 새로운 다중 공간 조인 알고리즘을 제안한다. MRJ는 M 개의 R-트리를 동시에 순회하는 방법으로 R-트리 조인의 일반화로 간주될 수 있다. 비록 최근에 R-트리 조인의 일반화에 대한 연구가 있었다 할지라도 그것은 원래의 R-트리 조인에서 사용하던 검색 공간 제한(search space restriction)과 평면 쓸기(plane sweep) 기법을 적절히 고려하지 못했다. 우리는 R-트리 조인에서의 위의 두 최적화 기법을 다중 공간 조인으로 확장한다. 다중 조인 분야(예, 관계형 조인)에서는 조인 순서가 중요하게 여겨져 왔으므로 우리도 MRJ에서 검색 공간 제한과 평면 쓸기의 순서를 특별히 중요하게 고려한다. 추가적으로 우리는 MRJ에 간접 술어(indirect predicate) 개념을 도입하여 간접 술어 여과(IPF) 기법을 이용한 MRJ 알고리즘을 제안한다.
최근에 공간 객체들이 균등하게 분포되어 있다는 가정하에 트리와 클릭이라는 두가지 질의 그래프 형식에 대해 다중 공간 조인의 결과 크기를 예측할 수 있는 공식이 개발되었다. 그러나 이 공식은 공간 데이타의 위치 분포만을 고려하였다. 따라서 그 공식은 공간 객체의 크기 분포에 대해서는 특수한 경우에만 성립한다. 본 논문에서는 공간 객체의 임의의 크기 분포에 대해서도 만족할 수 있도록 원래 공식을 확장하고, 확장된 공식에 대한 복잡도와 특성에 대해서 분석한다. 특히 우리는 다중 공간 조인의 결과 크기를 예측하기 위해서 질의 최적화기가 보유해야 하는 통계량의 종류와 갯수에 대해서 기술한다.
