Join Order Optimization and Genetic Algorithms

In this lesson, you will learn how the PostgreSQL query optimizer handles the "join explosion" problem using Genetic Algorithms when planning complex queries with many tables.

The Combinatorial Explosion

When you join three or four tables, the number of possible join orders is small enough for the optimizer to evaluate them all using dynamic programming. However, if you join 15 or 20 tables, the number of permutations grows factorially. Evaluating every possible join path would consume more time than the actual execution of the query.

The Genetic Approach

To prevent the optimizer from hanging on massive joins, PostgreSQL switches from exhaustive search to a Genetic Query Optimizer (GEQO). Think of this as an evolutionary simulation:

1. Population: The optimizer creates a random set of "candidate" join orders.
2. Fitness: It calculates the estimated cost of each plan (based on the cost models we discussed in previous lessons).
3. Selection & Crossover: It keeps the "fittest" (cheapest) plans and "breeds" them by combining their parts to create a new generation of plans.
4. Mutation: It randomly alters some plans to explore new, potentially better paths that haven't been considered yet.

This process repeats for a set number of generations until the optimizer finds a "good enough" plan.

When does it trigger?

You can control this behavior using the geqo_threshold parameter. By default, it is set to 12. This means if your query involves 12 or more relations, the optimizer abandons the exhaustive search and invokes the genetic algorithm:

-- View the current threshold for GEQO
SHOW geqo_threshold;

-- If you have a complex query involving 15 tables, 
-- you might see GEQO kick in automatically:
EXPLAIN SELECT * FROM t1 JOIN t2 ... JOIN t15 ON (...);

While GEQO is faster for complex queries, it is non-deterministic. Because it relies on randomness, the same query might occasionally produce slightly different execution plans across different runs, which is a trade-off for the massive performance gain in planning time.

Key Takeaway: When joining many tables exceeds the geqo_threshold, PostgreSQL uses a Genetic Algorithm to evolve an efficient join order rather than attempting to brute-force every possible combination.