TY - JOUR
T1 - Heuristic approach for early separated filter and refinement strategy in spatial query optimization
AU - Park, Ho Hyun
AU - Cho, Hyung Ju
AU - Chung, Chin Wan
PY - 2002/6/15
Y1 - 2002/6/15
N2 - 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 than 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 (II) and the simulated annealing (SA), to the ESFAR optimizer. Additionally we propose a new heuristic algorithm to find a good initial state of II and SA. Through experiments, we show that the II 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 II algorithm with the initial state heuristic rapidly finds a plan of a high quality.
AB - 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 than 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 (II) and the simulated annealing (SA), to the ESFAR optimizer. Additionally we propose a new heuristic algorithm to find a good initial state of II and SA. Through experiments, we show that the II 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 II algorithm with the initial state heuristic rapidly finds a plan of a high quality.
UR - http://www.scopus.com/inward/record.url?scp=0037097053&partnerID=8YFLogxK
U2 - 10.1016/S0164-1212(01)00138-8
DO - 10.1016/S0164-1212(01)00138-8
M3 - Article
AN - SCOPUS:0037097053
SN - 0164-1212
VL - 62
SP - 161
EP - 179
JO - Journal of Systems and Software
JF - Journal of Systems and Software
IS - 3
ER -