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.