Cost Estimation for Queries Experiencing Multiple Contention States in Dynamic Multidatabase Environments

Abstract

Accurate query cost estimation is crucial to query optimization in a multidatabase system. Several estimation techniques for a static environment have been suggested in the literature. To develop a cost model for a dynamic environment, we recently introduced a multistate query-sampling method. It has been shown that this technique is promising in estimating the cost ofa query run in any given contention state for a dynamic environment. In this paper, we study a new problem on how to estimate the cost of a large query that may experience multiple contention states. Following the discussion of limitations for two simple approaches, i.e., single state analysis and average cost analysis, we propose two novel techniques to tackle this challenge. The first one, called fractional analysis, is suitable for a gradually and smoothly changing environment, while the second one, called the probabilistic approach, is developed for a rapidly and randomly changing environment. The former estimates a query cost by analyzing its fractions, and the latter estimates a query cost based on Markov chain theory. The related issues including cost formula development, error analysis, and comparison among different approaches are discussed. Experiments demonstrate that the proposed techniques are quite promising in solving the new problem.