Optimization of Spatial Joins Using Filters

H.M. Veenhof, Peter M.G. Apers, M.A.W. Houtsma

Research output: Contribution to conferencePaperpeer-review

72 Downloads (Pure)


When viewing present-day technical applications that rely on the use of database systems, one notices that new techniques must be integrated in database management systems to be able to support these applications efficiently. This paper discusses one of these techniques in the context of supporting a Geographic Information System. It is known that the use of filters on geometric objects has a significant impact on the processing of 2-way spatial join queries. For this purpose, filters require approximations of objects. Queries can be optimized by filtering data not with just one but with several filters. Existing join methods are based on a combination of filters and a spatial index. The index is used to reduce the cost of the filter step and to minimize the cost of retrieving geometric objects from disk. In this paper we examine n-way spatial joins. Complex n-way spatial join queries require solving several 2-way joins of intermediate results. In this case, not only the profit gained from using both filters and spatial indices but also the additional cost due to using these techniques are examined. For 2-way joins of base relations these costs are considered part of physical database design. We focus on the criteria for mutually comparing filters and not on those for spatial indices. Important aspects of a multi-step filter-based n-way spatial join method are described together with performance experiments. The winning join method uses several filters with approximations that are constructed by rotating two parallel lines around the object.
Original languageUndefined
Number of pages19
Publication statusPublished - Jul 1995
Event13th British National Conference on Databases: Advances in Databases (BNCOD 1995) - Manchester, UK
Duration: 12 Jul 199514 Jul 1995


Conference13th British National Conference on Databases: Advances in Databases (BNCOD 1995)
Other12-14 Jul 1995


  • IR-66460
  • EWI-7345

Cite this