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. Since Dynamic programming is not feasible for optimizing queries in a DDB, we propose a GA based query optimizer and compare its performance to random and optimal algorithms. We analyzed a set of possible GA parameters and determined that two-point truncate technique using GA gives the best results. New mutation and crossover operators have also been defined and experimentally analyzed. We performed 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 found by exhaustive search show that our new GA formulation performs only 20% off the optimal results and we have achieved a 50% improvement over a previous GA based algorithm.