In the world of databases, optimizing complex queries with many tables can be a daunting task. PostgreSQL offers a unique solution for such scenarios: the Genetic Query Optimizer (GEQO). GEQO leverages genetic algorithms, inspired by natural selection, to efficiently explore vast search spaces of query execution plans, making it ideal for queries involving numerous joins. In this blog, we’ll dive into how GEQO works, its benefits, and practical examples to show it in action.
What is GEQO?
GEQO is a specialized query optimization technique in PostgreSQL designed for queries with many relations (e.g., tables or subqueries). When the number of relations exceeds a configurable threshold (default: 12), GEQO kicks in to avoid the combinatorial explosion that overwhelms the default dynamic programming-based optimizer. By mimicking evolution, GEQO finds near-optimal query execution plans quickly, even for complex queries.
How GEQO Works
GEQO operates using a genetic algorithm with the following steps:
Population Initialization: GEQO creates a set of candidate query execution plans, each representing a possible join order or strategy.
1. Fitness Evaluation: Each plan’s cost (based on I/O, CPU, and memory usage) is calculated using PostgreSQL’s cost model. Lower-cost plans are “fitter.”
2. Selection: Fitter plans are selected to “reproduce,” prioritizing those with lower costs.
3. Crossover: Selected plans are combined to create new plans, such as swapping parts of join sequences.
4. Mutation: Random changes (e.g., altering a join order) are applied to maintain diversity.
5. Iteration: The process repeats over several generations until a good plan is found.
The best plan is then executed. Key parameters like geqo_threshold (to enable GEQO), geqo_effort (to control optimization effort), and geqo_pool_size (population size) allow fine-tuning.
Benefits of GEQO
* Handles Complexity: Optimizes queries with many tables where traditional methods falter.
* Scalability: Scales better than exhaustive search for large search spaces.
* Avoids Local Optima: Stochastic crossover and mutation help escape suboptimal plans.
* Tunable: Adjustable parameters balance planning time and plan quality.
* Robustness: Performs well even with imperfect statistics or complex query structures.
Configuring Genetic Query Optimization
PostgreSQL provides several configuration parameters to tune the genetic optimizer:
* geqo: Enables or disables the genetic optimizer (default: on)
* geqo_threshold: Number of tables at which the genetic optimizer is used (default: 12)
* geqo_effort: Controls the balance between optimization time and quality (1-10, default: 5)
* geqo_pool_size: Number of plans in each generation (default: 0, which means it's calculated based on query complexity)
* geqo_generations: Maximum number of generations (default: 0, which means it's calculated based on query complexity)
Practical Examples of GEQO in Action
Let’s explore a real-world scenario to see how GEQO optimizes complex queries in PostgreSQL.
Example: Multi-Table Join Query for a Sales Report
Scenario: A data warehouse query joins 14 tables to generate a sales report across regions, products, and time periods.
First, let’s check if GEQO is on by using the following command:
SHOW geqo;
If its on then let’s turn off GEQO using the below command:
SET geqo = off;
Now you can get the time taken to execute this query with 14 tables in it, without geqo in action( this is for example purposes and all the tables mentioned in the query are already created):
EXPLAIN ANALYZE SELECT r.region_name, p.product_name, t.year, SUM(s.quantity)
FROM sales s
JOIN regions r ON s.region_id = r.region_id
JOIN products p ON s.product_id = p.product_id
JOIN time t ON s.time_id = t.time_id
JOIN customers c ON s.customer_id = c.customer_id
JOIN stores st ON s.store_id = st.store_id
JOIN promotions pr ON s.promo_id = pr.promo_id
JOIN suppliers sp ON p.supplier_id = sp.supplier_id
JOIN categories cat ON p.category_id = cat.category_id
JOIN employees e ON s.employee_id = e.employee_id
JOIN departments d ON e.department_id = d.department_id
JOIN locations l ON st.location_id = l.location_id
JOIN managers m ON st.manager_id = m.manager_id
JOIN campaigns cm ON pr.campaign_id = cm.campaign_id
GROUP BY r.region_name, p.product_name, t.year;
On running the EXPLAIN ANALYZE of the query, we get the planning and execution time as:
Planning Time: 2.474 ms
Execution Time: 0.337 ms
Now, let's set the GEQO parameter to on:
SET geqo = on;
SHOW geqo;
geqo
------
on
(1 row)
Execute the above query again to see the difference with GEQO enabled:
Planning Time: 1.220 ms
Execution Time: 0.148 ms
Now, you can see the change in planning and execution time.
How GEQO Helps:
* The query involves 14 relations, exceeding the default geqo_threshold (12), so GEQO is automatically triggered when enabled. With GEQO on, it initializes a population of approximately 200 candidate query execution plans and evaluates their costs (e.g., joining sales with regions versus products first, considering index usage and join methods). These plans evolve over multiple generations (e.g., 50 iterations) through selection, crossover, and mutation.
* The result: GEQO produces a plan with a lower estimated cost, reflected in the reduced planning and execution times. Specifically, with GEQO enabled, the query achieves a planning time of 1.220 ms and an execution time of 0.148 ms, compared to the default optimizer (with GEQO off), which takes 2.474 ms for planning and 0.337 ms for execution. This improvement demonstrates GEQO’s ability to find a more efficient join order and execution strategy, significantly reducing both planning overhead and query execution time for complex multi-table queries.
* Benefit: GEQO finds an efficient join order, minimizing I/O and speeding up the query significantly.
How to Use and Tune GEQO
Enable GEQO:
SET geqo = on;
SHOW geqo; -- Should return 'on'
Adjust Threshold:
SET geqo_threshold = 10; -- Enable for queries with 10+ relations
Tune Effort:
SET geqo_effort = 7; -- Higher effort for better plans
Monitor Plans:
EXPLAIN ANALYZE SELECT ...; -- Check planning and execution times
Log GEQO Activity (requires superuser):
SET log_min_messages = debug1;
Tips:
* Increase geqo_effort for analytical queries where planning time is less critical.
* Ensure good statistics with ANALYZE for accurate cost estimates.
* Balance planning time vs. execution time based on workload.
Limitations of GEQO
* Non-Deterministic: May produce different plans across runs due to randomness.
* Overhead: High geqo_effort can slow planning for simple queries.
* Not Always Optimal: May not find the absolute best plan, though it often finds good ones.
When to Use GEQO
GEQO shines in:
* Data warehouses with large, multi-table joins.
* Analytical queries where execution time matters more than planning time.
* Cases where the default optimizer produces suboptimal plans due to search space pruning.
PostgreSQL’s Genetic Query Optimizer is a powerful tool for tackling complex queries with many relations. By using a genetic algorithm, GEQO efficiently explores vast search spaces to find near-optimal execution plans, as shown in our examples of sales reports. With tunable parameters and robust performance, GEQO is a must-know feature for database administrators and developers working with intricate PostgreSQL workloads. Try tweaking geqo_effort or geqo_threshold in your next complex query and see the difference!
Learn how to set up streaming replication using the Repmgr tool on PostgreSQL 17 to ensure high availability, data redundancy, and seamless failover management in your PostgreSQL environment.