HP Labs Technical Reports

Optimization and Execution Strategy for Multidatabase Queries

Du, Weimin; Shan, Ming-Chien; Davis, Jim

HPL-94-74

Keyword(s):

Abstract: Query optimization and execution in multidatabase systems is different from that of distributed homogeneous database systems, due to not only the lack of information about cost formulae of local database systems, but also less control over local query execution and greater overhead of data access. For example, performance of nested loop join of tables in different databases degrades rapidly as the number of inner table searches increases. This is true even if a clustered index exists on the join column of the inner table. In this paper, we study the execution of multidatabase queries and its impacts on optimization. The main contributions of the paper are twofold: developing a technique which reduces the costs of multidatabase joins using partial query results and statistical data, and proposing a query optimization and execution strategy for multidatabase queries that reflects unique features of multidatabase systems. Experiments in Pegasus show that the technique and the strategy, though simple, are effective in reducing the elapsed time of multidatabase queries.

Back to Index