Genetic Query Optimization for Large Databases

As the amount of stored data grows, the relational schemas needed to organize all these data get more complex, increasing the number of relations in the database. As a consequence, it becomes necessary to write SQL queries that involve a large number of relations. Once a SQL query is introduced into the DBMS, the query optimizer must find the most efficient query execution plan to solve it. State-of-the-art query optimizers, which typically employ dynamic programming techniques, are limited in the number of joins they can handle. In these situations, optimizers either resort to heuristics or fall back to greedy algorithms. However, greedy algorithms do not consider the entire search space and thus may overlook the optimal plan, resulting in bad query performance. In this book, we present a query optimizer based on genetic programming algorithms. We compare the results yielded by our optimizer with those yielded by the UDB DB2 optimizer, as well as some of the most efficient randomized algorithms proposed in the literature. Our studies show that the larger the number of relations involved in the query, the larger the benefit obtained by this type of optimizers.