Description:
A three-table inner join chooses a much slower join order even though the
final cost of that plan is higher than the cost of an available alternative
join order.
The issue appears to be caused by an inconsistency between join-order
enumeration and final AccessPath construction when a constant predicate
belongs to an equality class.
The query is:
SELECT t2.c0, t0.c0
FROM t2
JOIN t1 ON t2.c1 = t1.c0
JOIN t0 ON t1.c2 = t0.c2
WHERE t0.c2 = 1000;
With the traditional optimizer, MySQL chooses a plan starting from t2 and
performs 1000 index lookups into t1. On my test system, EXPLAIN ANALYZE reports
about 109 ms.
Forcing the alternative join order:
SELECT /*+ JOIN_ORDER(t0, t1, t2) */
t2.c0, t0.c0
FROM t2
JOIN t1 ON t2.c1 = t1.c0
JOIN t0 ON t1.c2 = t0.c2
WHERE t0.c2 = 1000;
finishes in about 0.468 ms, approximately 230x faster.
The final estimated costs also favor the forced plan:
default plan: approximately 3.13M
JOIN_ORDER(t0,t1,t2): approximately 1.01M
The optimizer trace shows a notable inconsistency.
During join-order enumeration, the selected t2 -> t1 -> t0 order is estimated
at approximately:
cost_for_plan = 320003
because a 0.1 filtering effect is applied when t0 is added to the prefix.
The alternative t0 -> t1 -> t2 order is estimated at approximately:
cost_for_plan = 1.01011e6
and is pruned by cost.
However, after the join order has been selected, equality propagation and
condition attachment result in the constant condition being attached to t1:
t1.c2 = 1000
while t0 keeps only:
t0.c2 = t1.c2
In the final AccessPath, the t1 index lookup is estimated at 31.25 rows and
the subsequent filter "t1.c2 = 1000" is also estimated at 31.25 rows, so the
filtering effect used during join-order enumeration is no longer reflected
there.
Consequently, the final estimated cost of the selected plan becomes
approximately 3.13M, which is higher than the approximately 1.01M cost of
the forced alternative plan.
This therefore results in a cost-ranking inversion:
During join enumeration:
t2 -> t1 -> t0 ~ 0.32M
t0 -> t1 -> t2 ~ 1.01M
Final plans:
t2 -> t1 -> t0 ~ 3.13M
t0 -> t1 -> t2 ~ 1.01M
Setting optimizer_prune_level=0 does not resolve the issue.
Disabling condition_fanout_filter also does not improve runtime; the same
slow join order is still selected.
The Hypergraph Optimizer does not choose the problematic plan for this test
case.
The query returns no rows. The value 1000 is deliberately inside the
observed c2 value range but is absent from both t0.c2 and t1.c2.
No histograms are created.
Expected:
The optimizer should choose the lower-cost join order, or at least use
consistent cardinality and cost estimates when ranking a join order and
constructing its final AccessPath.
Actual:
The selected join order is estimated at about 0.32M during join enumeration,
but its final AccessPath cost becomes about 3.13M. An alternative plan with
a final cost of about 1.01M is not selected and runs approximately 230x
faster in this test.
How to repeat:
Run the attached reproduction script:
mysql_join_filter_cost_repro.sql
The script creates the three test tables, inserts deterministic data, runs
ANALYZE TABLE, and compares:
1. the optimizer-selected plan,
2. JOIN_ORDER(t0, t1, t2),
3. optimizer_prune_level=0,
4. condition_fanout_filter=off, and
5. the Hypergraph Optimizer.
The complete output from my test run is attached as:
mysql_join_filter_cost_repro_output.txt
Suggested fix:
Please ensure that the condition filtering/selectivity used when ranking join
orders remains consistent with the predicates and cardinalities represented
in the final AccessPath.
In particular, when a constant predicate participates in an equality class
(for example, t0.c2 = t1.c2 and t0.c2 = constant), moving or substituting the
predicate to another equality-class member after join-order selection should
not invalidate the filtering effect that was used to compare candidate join
orders.
Alternatively, if final predicate attachment changes the cardinality/cost of
the selected plan enough to change its ranking relative to previously
considered alternatives, the affected plans may need to be re-costed before
the final join order is committed.
Description: A three-table inner join chooses a much slower join order even though the final cost of that plan is higher than the cost of an available alternative join order. The issue appears to be caused by an inconsistency between join-order enumeration and final AccessPath construction when a constant predicate belongs to an equality class. The query is: SELECT t2.c0, t0.c0 FROM t2 JOIN t1 ON t2.c1 = t1.c0 JOIN t0 ON t1.c2 = t0.c2 WHERE t0.c2 = 1000; With the traditional optimizer, MySQL chooses a plan starting from t2 and performs 1000 index lookups into t1. On my test system, EXPLAIN ANALYZE reports about 109 ms. Forcing the alternative join order: SELECT /*+ JOIN_ORDER(t0, t1, t2) */ t2.c0, t0.c0 FROM t2 JOIN t1 ON t2.c1 = t1.c0 JOIN t0 ON t1.c2 = t0.c2 WHERE t0.c2 = 1000; finishes in about 0.468 ms, approximately 230x faster. The final estimated costs also favor the forced plan: default plan: approximately 3.13M JOIN_ORDER(t0,t1,t2): approximately 1.01M The optimizer trace shows a notable inconsistency. During join-order enumeration, the selected t2 -> t1 -> t0 order is estimated at approximately: cost_for_plan = 320003 because a 0.1 filtering effect is applied when t0 is added to the prefix. The alternative t0 -> t1 -> t2 order is estimated at approximately: cost_for_plan = 1.01011e6 and is pruned by cost. However, after the join order has been selected, equality propagation and condition attachment result in the constant condition being attached to t1: t1.c2 = 1000 while t0 keeps only: t0.c2 = t1.c2 In the final AccessPath, the t1 index lookup is estimated at 31.25 rows and the subsequent filter "t1.c2 = 1000" is also estimated at 31.25 rows, so the filtering effect used during join-order enumeration is no longer reflected there. Consequently, the final estimated cost of the selected plan becomes approximately 3.13M, which is higher than the approximately 1.01M cost of the forced alternative plan. This therefore results in a cost-ranking inversion: During join enumeration: t2 -> t1 -> t0 ~ 0.32M t0 -> t1 -> t2 ~ 1.01M Final plans: t2 -> t1 -> t0 ~ 3.13M t0 -> t1 -> t2 ~ 1.01M Setting optimizer_prune_level=0 does not resolve the issue. Disabling condition_fanout_filter also does not improve runtime; the same slow join order is still selected. The Hypergraph Optimizer does not choose the problematic plan for this test case. The query returns no rows. The value 1000 is deliberately inside the observed c2 value range but is absent from both t0.c2 and t1.c2. No histograms are created. Expected: The optimizer should choose the lower-cost join order, or at least use consistent cardinality and cost estimates when ranking a join order and constructing its final AccessPath. Actual: The selected join order is estimated at about 0.32M during join enumeration, but its final AccessPath cost becomes about 3.13M. An alternative plan with a final cost of about 1.01M is not selected and runs approximately 230x faster in this test. How to repeat: Run the attached reproduction script: mysql_join_filter_cost_repro.sql The script creates the three test tables, inserts deterministic data, runs ANALYZE TABLE, and compares: 1. the optimizer-selected plan, 2. JOIN_ORDER(t0, t1, t2), 3. optimizer_prune_level=0, 4. condition_fanout_filter=off, and 5. the Hypergraph Optimizer. The complete output from my test run is attached as: mysql_join_filter_cost_repro_output.txt Suggested fix: Please ensure that the condition filtering/selectivity used when ranking join orders remains consistent with the predicates and cardinalities represented in the final AccessPath. In particular, when a constant predicate participates in an equality class (for example, t0.c2 = t1.c2 and t0.c2 = constant), moving or substituting the predicate to another equality-class member after join-order selection should not invalidate the filtering effect that was used to compare candidate join orders. Alternatively, if final predicate attachment changes the cardinality/cost of the selected plan enough to change its ranking relative to previously considered alternatives, the affected plans may need to be re-costed before the final join order is committed.