Spatial query optimization utilizing early separated filter and refinementstrategy

Due to the high complexity and large volume of spatial data, a spatial quer y is usually processed in two steps, called the filter step and the refinem ent step. However, the two-step processing of the spatial query has been co nsidered locally in one spatial predicate evaluation at the query execution level. This paper presents query optimization strategies which exploit the two-step processing of a spatial query at the query optimization level. Th e first strategy involves the separation of filter and refinement steps not in the query execution phase but in the query optimization phase. As the s econd strategy, several refinement operations can be combined in processing a complex query if they were already separated, and as the third strategy several filter operations can also be combined. We call the optimization te chnique utilizing these strategies the Early Separated Filter And Refinemen t (ESFAR). This paper also presents an algebra, which is called the Interme diate Spatial Object Algebra (ISOA), and optimization rules for ESFAR. Thro ugh experiments using real data, we compare the ESFAR optimization techniqu e with a traditional optimization technique which does not separate filter and refinement steps from the query optimization phase. The experimental re sults show that the ESFAR optimization technique generates more efficient q uery execution plans than the traditional one in many cases. (C) 2000 Publi shed by Elsevier Science Ltd. All rights reserved.