Genetic Optimization for the Join Ordering Problem of Database Queries

A query optimizer is a core component of any Database Management System. As a database query optimizer might face different voluminous and complex queries, leading to a huge search space of alternative query plans, it should be appropriate to adapt the search strategy to the problem solving technique which handles complex and large data. Genetic Algorithms (GAs) avoid the high cost of optimization and provide flexibility by being independent of the problem specific knowledge. These qualities make them a viable option for solving the query optimization problem. All query optimization algorithms primarily deal with joins. Our study concerns the use of GA for join order optimization. Prior theories indicate that genetic algorithms are apposite for optimizing join expressions and produce solutions of high quality within a reasonable running time. We have implemented the GA technique on RDBMS queries and found that the GA based optimizer performs better for queries involving large number of joins.