Early separated filter/refinement strategies and multi-way spatial joins for spatial query optimization

Abstract

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-tre...