A simulation environment for evaluating distributed query processing algorithms

Abstract

Distributed database systems provide users with the facility to utilize and maintain information that is geographically dispersed in files at several sites while they remain unaware of the distribution of the information. The process of retrieving the information is called distributed query processing. The performance of a distributed database depends on the ability of the query processor to derive efficient query processing strategies/or queries requested by users. For this reason various query processing algorithms for distributed database systems have been proposed in the literature. These algorithms differ in terms of their database environment, design issues and query optimization techniques used. A simulation environment is presented with which the different query processing algorithms can be uniformly compared. It consists of three components, a relational distributed database model, a comprehensive cost model and an estimation model. The database model is an extension of a model proposed by P.M.G. Apers. It is extended to incorporate horizontal fragmentation, more information about the distribution of attribute values and the use of key attributes for each relation. The cost model considers costs encountered during the transmission of data and messages across the network, the processing of local operations in terms of I/O and CPU costs, the storage of intermediate result relations, the updating of the database profile and the formulation of the execution strategy. The estimation model is an extension of the Piecewise Uniform Method to include the estimation of the effect of join and semi-join operations with multiple joining attributes. The simulation environment is applied to quantitatively compare three different types of query processing algorithms.