Heuristic approach for early separated filter and refinement strategy in spatial query optimization

Abstract

Recently, we proposed an optimization strategy for spatial and non-spatial mixed queries. In the strategy, the filter step and the refinement step of a spatial operator are regarded as individual algebraic operators, and are early separated at the algebraic level by the query optimizer. By doing so, the optimizer using the strategy could generate more diverse and efficient plans that the traditional optimizer. We called this optimization strategy the Early Separated Filter And Refinement (ESFAR). In this paper, we improved the cost model of the ESFAR optimizer considering the real life environment such as the LRU buffer, the clustering of the dataset, and the selectivity of the real data distribution. And we conducted a new experiment for ESFAR by comparing the optimization result generated by the new cost model and the actual execution result using real data. The experimental result showed that our cost model is accurate and our ESFAR optimizer estimates the costs of execution plans well. Since the ESFAR strategy has more operators and more rules than the traditional one, it consumes more optimization time. In this paper, we apply two existing heuristic algorithms, the iterative improvement (11) and the simulated annealing (SA), to the ESFAR optimizer. Additionally we propose a new heuristic algorithm to find a good initial state of 11 and SA. Through experiments, we show that the 11 and SA algorithms in the ESFAR strategy find a good sub-optimal plan in reasonable time. Mostly the heuristic algorithms find a lower cost plan in less time than the optimal plan generated by the traditional optimizer. Especially the 11 algorithm with the initial state heuristic rapidly finds a plan of a high quality. (C) 2001 Elsevier Science Inc. All rights reserved.