The query optimization problem has been widely addressed in Relational Database Management Systems (RDBMS). Many strategies have been implemented to solve this problem including deterministic algorithms, randomized algorithms, meta-heuristic algorithms and hybrid approaches. This book provides a literature review that includes solutions to the join-ordering problem using simulated annealing, genetic algorithms and ant colony optimization.
Such methodologies deeply depend on the correct configuration of various input parameters. This book also introduces a new meta-heuristic approach based on the automata theory adapted to solve the join-ordering problem. The proposed method requires only a single input parameter that facilitates its usage respect to other methods. The algorithm was embedded into PostgreSQL and compared with the genetic competitor using random and star database schemas.