Query Optimization in Distributed Relational Databases |
| |
Authors: | Celso C Ribeiro Cláudio D Ribeiro Rosana SG Lanzelotte |
| |
Institution: | (1) Departamento de Informática, Pontifícia Universidade Católica do Rio de Janeiro, Rua Marquês de São Vicente 225, Rio de Janeiro, 22453, Brazil |
| |
Abstract: | The query optimizer is the DBMS (data base management system) component whose task is to find an optimal execution plan for a given input query. Typically, optimization is performed using dynamic programming. However, in distributed execution environments, this approach becomes intractable, due to the increase in the search space incurred by distribution. We propose the use of the tabu search metaheuristic for distributed query optimization. A hashing-based data structure is used to keep track of the search memory, simplifying significantly the implementation of tabu search. To validate this proposal, we implemented the tabu search strategy in the scope of an existing optimizer, which runs several search strategies. We focus our attention on the more difficult problems in terms of the query execution space, in which the solution space includes bushy execution plans and Cartesian products, which are not dealt with very often in the literature. Using a real-life application, we show the effectiveness of tabu search when compared to other strategies. |
| |
Keywords: | query optimization relational databases distributed systems tabu search |
本文献已被 SpringerLink 等数据库收录! |
|