Spatial query optimization utilizing early separated filter and refinement strategy

Due to the high complexity and large volume of spatial data, a spatial query is usually 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 paper 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 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 technique utilizing these strategies the Early Separated Filter And Refinement (ESFAR). This paper also presents an algebra, which is called the Intermediate Spatial Object Algebra (ISOA), and optimization rules for ESFAR. Through experiments using real data, we compare the ESFAR optimization technique with a traditional optimization technique which does not separate filter and refinement steps from the query optimization phase. The experimental results show that the ESFAR optimization technique generates more efficient query execution plans than the traditional one in many cases. (C) 2000 Published by Elsevier Science Ltd. All rights reserved.
Publisher
PERGAMON-ELSEVIER SCIENCE LTD
Issue Date
2000-03
Language
ENG
Citation

INFORMATION SYSTEMS, v.25, no.1, pp.1 - 22

ISSN
0306-4379
URI
http://hdl.handle.net/10203/1929
Appears in Collection
CS-Journal Papers(저널논문)
  • Hit : 379
  • Download : 7
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 10 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0