Chapter 11. Genetic Query Optimization (GEQO)

The GEQO module enables the PostgreSQL query optimizer to support complex join queries effectively through non-exhaustive search. The Genetic Query Optimizer (GEQO) is used for queries that have at least GEQO_THRESHOLD FROM items involved. (Note that a JOIN construct counts as only one FROM item.) For simpler queries, the default deterministic (exhaustive search) planner is used.

Query Handling as a Complex Optimization Problem

Among all relational operators the most difficult to process and optimize is the join. Furthermore, the number of alternative plans to answer a query grows exponentially with the number of join commands. Additional plans arise from the support of a variety of join methods (for example, nested loop, hash join, merge join in PostgreSQL) available to process individual join commands and the possible availability of indexes (for example, r-tree, b-tree, hash in PostgreSQL) as access paths for relations.

The current PostgreSQL optimizer implementation performs a near-exhaustive search over the space of alternative strategies. This query optimization technique is inadequate to support database application domains that involve the need for complex queries, such as artificial intelligence.

The overhead in exploring the space of possible query plans in this class of queries created the demand for a new optimization technique. PostgreSQL uses a Genetic Algorithm as an optional database query optimization method.