Processing and Optimization of Join Operation in Spatial Database
空间数据库中连接运算的处理与优化

The performance problem of spatial database limits its application and development seriously. Spatial join is the most complex and time consuming operation in spatial database system. Its efficiency determines the performance of the whole spatial database system to a great extent. Although there are many spatial join algorithms already, cost estimation and query optimization of spatial join operation need further study. Most spatial join algorithms are implemented based on R tree index, but if the corresponding relations have no indices, or only have partly indices, special algorithms should be used to handle the situation. Cost estimation models of each algorithm need a relatively uniform calculation method. Considering the characteristic of spatial database, it's reasonable to use I/O cost to estimate the complexity of each algorithm. Based on the above approaches, and because complex spatial queries may include multiple relations for spatial join, dynamic programming algorithm should be used to choose the proper join order which has minimum cost. It becomes a universal algorithm framework. Through the complexity analysis of the algorithm framework, the spatial database query optimization system implemented base on this approach will have better spatial and temporal efficiency, and can handle very complex spatial queries.