Selectivity Estimation of Complex Spatial Queries

Several studies have focused on the efficient processing of simple spatial query types such as selections and spatial joins. Little work, however, has been done towards the optimization of queries that process several spatial inputs and combine them through join and selection conditions. This paper identifies the dependencies between spatial operators and illustrates how they can affect the outcome of complex queries. A thorough analysis yields selectivity estimations that can be used to optimize any combination of spatial and non-spatial selection and join operators. The accuracy of the formulae is evaluated through experimentation with various queries. In addition to their importance for spatial databases, the presented results can be applied in several other domains, where dependencies exist between operators.