Optimizer chooses 30x slower join order due to equality-join fanout misestimation

Summary

A plain 3-table INNER JOIN is optimized to a much slower join order. The query has no ORDER BY, LIMIT, DISTINCT, GROUP BY, subqueries, or outer joins.

The optimizer chooses:

t1 -> t3 -> t0

but an equivalent forced plan:

STRAIGHT_JOIN t3 -> t0 -> t1

returns the same 12 rows and runs about 30x faster.

Testcase shape

The attached testcase creates three InnoDB tables: t0, t1, and t3.

The final result is not empty:

t0_rows = 300006

t1_rows = 1000006

t3_rows = 20003

t1_t3_matches = 6

t3_t0_matches = 6

final_result_rows = 12

So this is not an empty-result testcase.

The query under test is a plain INNER JOIN:

SELECT t0.c4 AS ref0, t0.c3 AS ref1

FROM t3

INNER JOIN t0 ON t3.c3 = t0.c3

INNER JOIN t1 ON t3.c0 = t1.c0

WHERE t3.c1 >= -2066281069;

Observed bad default plan

The default optimizer plan is:

t1 -> t3 -> t0

EXPLAIN FORMAT=JSON estimates this plan at about:

cost = 2983528

The plan scans t1 first and then probes t3 using i5(c0):

t1: index scan on i2, rows = 1000006

t3: ref lookup using i5(c0 = t1.c0), loops = 1000006

t0: ref lookup using i7(c3 = t3.c3)

ANALYZE FORMAT=JSON shows that this is very inefficient in reality:

BASE total time: about 1077 ms

t1 actual rows: 1000006

t3 lookup loops: 1000006

t3 actual average rows per lookup: 5.999964e-6

So the default plan performs about 1,000,006 index lookups into t3, but only 6 rows match in total.

Faster equivalent plan

The following equivalent query forces the join order t3 -> t0 -> t1:

SELECT t0.c4 AS ref0, t0.c3 AS ref1

FROM t3

STRAIGHT_JOIN t0 ON t3.c3 = t0.c3

STRAIGHT_JOIN t1 ON t3.c0 = t1.c0

WHERE t3.c1 >= -2066281069;

MariaDB estimates this forced plan as much more expensive:

FORCED_FAST estimated cost = 2201419665

BASE estimated cost        = 2983528

So the faster plan is estimated about 738x more expensive than the default plan.

However, ANALYZE FORMAT=JSON shows the opposite:

FORCED_FAST total time: about 37 ms

t3 actual rows: 20003

t0 lookup loops: 20003

t0 actual average rows per lookup: 0.003449483

t1 lookup loops: 6

t1 actual rows per lookup: 2

The forced plan scans t3, probes t0, reduces the intermediate result to 6 rows, and then probes t1 only 6 times.

Direct timing before persistent statistics

The direct timing results before the second persistent-statistics step were:

BASE:        1104.510 ms

FORCED_FAST:   34.363 ms

FORCED_SLOW: 1063.890 ms

So the optimizer-selected BASE plan is close to the forced slow plan and about 32x slower than the forced fast plan.

Persistent statistics do not fix the plan

The testcase then runs:

ANALYZE TABLE t0, t1, t3 PERSISTENT FOR ALL;

MariaDB reports:

Engine-independent statistics collected OK

for all three tables.

After collecting persistent statistics, the optimizer still chooses the same slow join order:

t1 -> t3 -> t0

The direct timing after persistent statistics is still:

BASE:        1058.494 ms

FORCED_FAST:   35.156 ms

FORCED_SLOW: 1041.656 ms

So persistent optimizer statistics do not change the chosen plan or fix the estimates.

Why this looks like an optimizer bug

This appears to be a join-order cost ranking inversion caused by equality-join fanout misestimation under skewed / almost disjoint join-key value domains.

The optimizer estimates the t1 -> t3 -> t0 plan as much cheaper, but in reality it performs about 1M almost-all-failing index lookups into t3.

The t3 -> t0 -> t1 plan is estimated as much more expensive, mainly because the fanout of t0(c3 = t3.c3) and t1(c0 = t3.c0) is greatly overestimated. In reality, t3 -> t0 produces only 6 intermediate rows, and t1 is probed only 6 times.

Reproduction

Run the attached testcase:

mariadb --table < mariadb_join_order_fanout_misestimation_testcase.sql > mariadb_join_order_fanout_misestimation_testcase_result.txt

The attached result file contains the full output with EXPLAIN FORMAT=JSON, ANALYZE FORMAT=JSON, direct timings, and the persistent-statistics comparison.

Attachments

mariadb_join_order_fanout_misestimation_testcase.sql

mariadb_join_order_fanout_misestimation_testcase_result.txt

Possible investigation direction

The issue seems to be in equality-join fanout / cardinality estimation for skewed or almost disjoint join-key value domains.

In this testcase, the optimizer estimates the t1-first plan as much cheaper, but it actually performs about 1M mostly unsuccessful index lookups into t3. The t3-first plan is estimated as much more expensive, mainly because the fanout of t0(c3 = t3.c3) and t1(c0 = t3.c0) is greatly overestimated.

In reality, t3 -> t0 produces only 6 intermediate rows, and t1 is probed only 6 times.

Persistent optimizer statistics and JSON_HB histograms do not change the chosen plan or fix the estimates. This suggests that the current statistics/costing path does not capture the tiny overlap between the join-key value domains, or the value distribution of rows that survive earlier join predicates.

I understand that exact join cardinality estimation can be difficult in general, but this testcase shows a large cost-ranking inversion: the optimizer-selected plan is about 30x slower, while the faster equivalent join order is estimated as hundreds of times more expensive.