An Evolutionary Genetic Algorithm for Optimization of Distributed Database Queries

High-performance low-cost PC hardware and high-speed LAN/WAN technologies make distributed database (DDB) systems an attractive research area where query optimization and DDB design are the two important and related problems. Since dynamic programming is not feasible for optimizing queries in a DDB, we propose a new genetic algorithm (GA)-based query optimizer (new genetic algorithm (NGA)) and compare its performance with random and optimal (exhaustive) algorithms. We perform experiments on a synthetic database with replicated relations, but no horizontal or vertical fragmentation. Network links are assumed to be gigabit ethernet. Comparisons with optimal results show that our NGA formulation performs only 20% of the optimal results and we have achieved 50% improvement over a previous GA-based algorithm.