Description:
In MySQL 9.7.1, after ANALYZE TABLE, the unhinted plan for a simple 3-table query is about 39.4x slower on average and has about 29.6x higher estimated top-level cost than a hinted plan. The evidence suggests that the default heuristic pruning setting, optimizer_prune_level=1, prunes a join-connected prefix too early and prevents the optimizer from exploring a much better join order.
With optimizer_prune_level=1 and optimizer_search_depth=62, the optimizer heuristically prunes a join-order prefix that leads to a much better plan, even though the query has only three tables.
The query is:
SELECT t2.c3 AS ref0
FROM t1, t0 NATURAL JOIN t2
GROUP BY t2.c3
ORDER BY t2.c3 ASC;
This query has one independent table and one connected join component. Table t1 has no join condition with the other tables, while t0 and t2 are connected by the equality predicates generated from NATURAL JOIN.
After ANALYZE TABLE, I executed the unhinted query three times with EXPLAIN ANALYZE. The root actual times were about 13.3 ms, 13.3 ms, and 13.5 ms.
I also executed a hinted version three times:
SELECT /*+ JOIN_ORDER(t0, t1) */ t2.c3 AS ref0
FROM t1, t0 NATURAL JOIN t2
GROUP BY t2.c3
ORDER BY t2.c3 ASC;
The root actual times were about 0.362 ms, 0.328 ms, and 0.327 ms.
Therefore, in my environment, the unhinted plan is about 39.4x slower on average. The estimated top-level cost is also much higher: about 4350 for the unhinted plan versus about 147 for the hinted plan, about 29.6x higher.
The unhinted plan joins t1 before the selective t0-t2 join. This creates a Cartesian expansion between t1 and t0. In all three runs, the plan first joins t1 and t0 with no join condition, produces 2640 rows, and then performs 2640 index lookups into t2.
Representative unhinted EXPLAIN ANALYZE output:
-> Sort row IDs: t2.c3 (actual time=13.3..13.3 rows=0 loops=1)
-> Table scan on <temporary> (cost=4344..4350 rows=231) (actual time=13.3..13.3 rows=0 loops=1)
-> Temporary table with deduplication (cost=4344..4344 rows=231) (actual time=13.3..13.3 rows=0 loops=1)
-> Nested loop inner join (cost=4291 rows=231) (actual time=13.2..13.2 rows=0 loops=1)
-> Inner hash join (no condition) (cost=469 rows=4620) (actual time=0.0487..0.228 rows=2640 loops=1)
-> Filter: (t0.c0 is not null) (cost=0.11 rows=70) (actual time=0.00605..0.0594 rows=40 loops=1)
-> Table scan on t0 (cost=0.11 rows=70) (actual time=0.00524..0.0536 rows=70 loops=1)
-> Hash
-> Covering index scan on t1 using c4 (cost=6.85 rows=66) (actual time=0.00719..0.0318 rows=66 loops=1)
-> Filter: ((t2.c5 = t0.c5) and (t2.c4 = t0.c4) and (t2.c3 = t0.c3) and (t2.c2 = t0.c2) and (t2.c1 = t0.c1) and (t2.c0 = t0.c0)) (cost=0.591 rows=0.05) (actual time=0.0048..0.0048 rows=0 loops=2640)
-> Index lookup on t2 using i1 (c0 = t0.c0) (cost=0.591 rows=2.36) (actual time=0.00134..0.00447 rows=3 loops=2640)
The hinted plan joins t0 and t2 first. This join produces an empty result early, so t1 is never executed. In all three runs, the hinted plan performs only 40 index lookups into t2.
Representative hinted EXPLAIN ANALYZE output:
-> Sort row IDs: t2.c3 (actual time=0.328..0.328 rows=0 loops=1)
-> Table scan on <temporary> (cost=142..147 rows=231) (actual time=0.323..0.323 rows=0 loops=1)
-> Temporary table with deduplication (cost=142..142 rows=231) (actual time=0.322..0.322 rows=0 loops=1)
-> Inner hash join (no condition) (cost=88.5 rows=231) (actual time=0.313..0.313 rows=0 loops=1)
-> Covering index scan on t1 using c4 (cost=1.96 rows=66) (never executed)
-> Hash
-> Nested loop inner join (cost=65.2 rows=3.5) (actual time=0.309..0.309 rows=0 loops=1)
-> Filter: (t0.c0 is not null) (cost=7.25 rows=70) (actual time=0.0152..0.0695 rows=40 loops=1)
-> Table scan on t0 (cost=7.25 rows=70) (actual time=0.0145..0.0636 rows=70 loops=1)
-> Filter: ((t2.c5 = t0.c5) and (t2.c4 = t0.c4) and (t2.c3 = t0.c3) and (t2.c2 = t0.c2) and (t2.c1 = t0.c1) and (t2.c0 = t0.c0)) (cost=0.591 rows=0.05) (actual time=0.00586..0.00586 rows=0 loops=40)
-> Index lookup on t2 using i1 (c0 = t0.c0) (cost=0.591 rows=2.36) (actual time=0.00209..0.00543 rows=3 loops=40)
The optimizer trace for the unhinted query shows that the t0-first prefix is pruned by heuristic pruning:
"table": "t0",
"cost_for_plan": 7.25,
"pruned_by_heuristic": true
The t2-first prefix is also pruned by heuristic pruning. Therefore, the optimizer does not appear to explore the full t0 -> t2 -> t1 join order. The issue is not caused by a small optimizer_search_depth, since optimizer_search_depth was 62. The problem appears to be that optimizer_prune_level=1 prunes the join-connected prefix too early, before the optimizer can see that t0 -> t2 is highly selective.
I also tested the same query with optimizer_prune_level=0. In that case, the unhinted optimizer can find the better join order and the problem disappears. This suggests that the bad plan is caused by heuristic pruning rather than by stale statistics or insufficient optimizer_search_depth.
Expected behavior: For a simple 3-table query, the optimizer should avoid pruning the only join-connected prefix too early, especially when the preserved alternative starts with an independent table and causes a Cartesian expansion. The optimizer should be able to consider the t0 -> t2 -> t1 join order, or at least consider one join-connected extension of the t0 prefix before pruning it.
Actual behavior: With optimizer_prune_level=1, the optimizer prunes the t0 prefix and chooses a much slower plan. A JOIN_ORDER hint shows that the pruned branch leads to a significantly cheaper and faster plan. Setting optimizer_prune_level=0 avoids this issue in my test.
This looks like a performance issue in join-order heuristic pruning.
How to repeat:
Please use the two attached SQL files:
1. create_tables_insert_data.sql * Creates and populates tables t0, t1, and t2.
2. run_optimizer_repro_cases.sql * Runs the reproduction cases. And this script assumes that create_tables_insert_data.sql is in the same directory.
Run the reproduction script in an empty test database:
mysql -u <user> -p <database> < run_optimizer_repro_cases.sql
Alternatively, inside the mysql client:
SOURCE run_optimizer_repro_cases.sql;
The script contains the following cases:
Case 1: Default optimizer settings
This case uses the default optimizer settings, including optimizer_prune_level=1 and the default optimizer_search_depth.
Expected observation:
The unhinted query chooses a slower plan. It starts with t1, which is independent from t0 and t2. Then it joins t1 and t0 with no join condition, creates a Cartesian expansion, and performs many repeated index lookups into t2.
In my environment, after ANALYZE TABLE, this plan took about 13.3 / 13.3 / 13.5 ms in three EXPLAIN ANALYZE runs. The top-level estimated cost was about 4350. The t1 x t0 join produced 2640 rows, and the lookup into t2 had loops=2640.
Case 2: JOIN_ORDER(t0, t1) hinted query
This case uses the same query, but adds the JOIN_ORDER(t0, t1) hint.
Expected observation:
The hint exposes a much better plan. MySQL joins t0 and t2 first, finds an empty result early, and t1 is never executed.
In my environment, this plan took about 0.362 / 0.328 / 0.327 ms in three EXPLAIN ANALYZE runs. The top-level estimated cost was about 147. The lookup into t2 had loops=40, and t1 was shown as never executed.
Case 3: Disable heuristic pruning
This case sets:
SET SESSION optimizer_prune_level = 0;
SET SESSION optimizer_search_depth = 62;
Expected observation:
The unhinted optimizer should be able to find the better join order. If this case chooses the t0 -> t2 -> t1 plan, it shows that the bad plan in Case 1 is caused by heuristic pruning rather than by stale statistics or insufficient optimizer_search_depth.
Case 4: Optimizer trace for the default bad case
This case enables optimizer_trace with the default pruning setting.
Expected observation:
The optimizer trace should show that the t0-first prefix is pruned by heuristic pruning. In my environment, the trace contains:
"table": "`t0`",
"pruned_by_heuristic": true
This shows that the optimizer prunes the t0 prefix before exploring the selective t0 -> t2 join.
Case 5: Optimizer trace with heuristic pruning disabled
This case enables optimizer_trace with optimizer_prune_level=0.
Expected observation:
The trace should no longer prune the t0 prefix by heuristic pruning, and the unhinted optimizer should be able to find the better join order.
Summary of the issue:
With optimizer_prune_level=1, the optimizer prunes the t0-first prefix in a simple 3-table query. However, t0 and t2 are the connected join component, while t1 is independent. Because the t0 prefix is pruned too early, the optimizer misses the much better t0 -> t2 -> t1 plan and instead chooses a plan that starts with the independent table t1 and causes a Cartesian expansion.
Disabling heuristic pruning with optimizer_prune_level=0 avoids the issue in my test.
Suggested fix:
Please consider improving join-order heuristic pruning so that it does not prune a join-connected prefix too early in small joins.
In this case, t1 is an independent table, while t0 and t2 form a connected join component through equality predicates generated from NATURAL JOIN. The heuristic appears to preserve the cheapest single-table prefix, t1, but this prefix leads to a Cartesian expansion. The slightly more expensive t0 prefix would allow the optimizer to immediately join t0 with t2 and find an empty result.
Possible improvements:
1. For small joins, such as 3-5 table joins, avoid heuristic pruning of root prefixes or make the pruning rule more conservative.
2. Take join graph connectivity into account before pruning a prefix. A prefix that can immediately join with another table through equality predicates should not be pruned only because its single-table cost is slightly higher than an independent table.
3. If a candidate prefix belongs to a connected join component, consider at least one join-connected extension of that prefix before applying heuristic pruning.
4. Penalize plans that start with an independent table when there exists another prefix that can immediately form a connected join with equality predicates.
5. In this case, the optimizer should be able to explore the t0 -> t2 -> t1 plan, which avoids the Cartesian expansion and is much cheaper than the unhinted plan.
