Description:
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, outer joins, hash join dependency, or BNL-specific behavior.
The default optimizer plan chooses the join order:
t1 -> t3 -> t0
This plan scans about 1,000,000 rows from t1 and performs about 1,000,000 index lookups into t3. Almost all of these lookups fail. EXPLAIN ANALYZE reports only 6 rows from the t1->t3 join prefix and 12 final result rows, but the optimizer estimates about 334,077 rows for the t1->t3 prefix and about 5.7 million final rows.
An equivalent hinted query using:
/*+ JOIN_ORDER(t3, t0, t1) */
uses the join order:
t3 -> t0 -> t1
This plan scans about 20,003 rows from t3, probes t0, produces only 6 intermediate rows, and then probes t1 only 6 times. It returns the same 12 result rows.
The cost ranking is inverted. Before histograms, the default plan is estimated at about 2.49e6 cost, while the hinted plan is estimated at about 3.88e9 cost, about 1550x more expensive. In reality, the hinted plan is about 26x faster in direct execution:
default: 1371.783 ms
hinted: 52.169 ms
EXPLAIN ANALYZE shows the same behavior:
default: about 1735 ms
hinted: about 62 ms
I also created histograms on the relevant columns:
ANALYZE TABLE t1 UPDATE HISTOGRAM ON c0 WITH 100 BUCKETS;
ANALYZE TABLE t3 UPDATE HISTOGRAM ON c0, c3 WITH 100 BUCKETS;
ANALYZE TABLE t0 UPDATE HISTOGRAM ON c3 WITH 100 BUCKETS;
After creating histograms and running ANALYZE TABLE again, the optimizer still chooses the same slow default join order and the estimates remain very similar. Direct execution after histograms still shows the same performance gap:
default: 1415.435 ms
hinted: 54.604 ms
This appears to be a join-order cost ranking inversion caused by severe equality-join fanout misestimation under skewed / almost disjoint join-key value domains. Single-column histograms do not correct the estimate in this case.
This is different from Bug #120861. Bug #120861 involves SELECT DISTINCT and a duplicate-insensitive joined table that can be treated as an existence / semijoin check. The present testcase has no DISTINCT, ORDER BY, LIMIT, GROUP BY, or duplicate-insensitive projection semantics. It is a plain INNER JOIN where the cost model misestimates equality-join fanout and ranks a much faster join order as much more expensive.
How to repeat:
Run the attached SQL testcase on MySQL 9.7.1:
mysql --table < mysql_join_order_fanout_testcase.sql > mysql_join_order_fanout_testcase_result.txt
The testcase creates a fresh database, builds three tables t0/t1/t3, inserts data, creates indexes, runs ANALYZE TABLE, compares the default plan with a JOIN_ORDER(t3,t0,t1) hinted plan, then creates histograms and repeats the comparison.
Important sections in the output:
1. SANITY CHECKS BEFORE HISTOGRAMS
Expected / observed:
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.
2. BASE EXPLAIN ANALYZE BEFORE HISTOGRAMS
Observed:
-> Nested loop inner join (cost=2.49e+6 rows=5.72e+6) (actual time=1735..1735 rows=12 loops=1)
-> Nested loop inner join (cost=451964 rows=334077) (actual time=1735..1735 rows=6 loops=1)
-> Filter: (t1.c0 is not null) (cost=101148 rows=996948) (actual time=0.0118..473 rows=1e+6 loops=1)
-> Covering index scan on t1 using i2 (cost=101148 rows=996948) (actual time=0.0111..409 rows=1e+6 loops=1)
-> Filter: ((t3.c1 >= -2066281069) and (t3.c3 is not null)) (cost=0.251 rows=0.335) (actual time=0.00117..0.00117 rows=6e-6 loops=1e+6)
-> Index lookup on t3 using i5 (c0 = t1.c0) (cost=0.251 rows=1.01) (actual time=0.00103..0.00103 rows=6e-6 loops=1e+6)
-> Filter: (t0.c3 = t3.c3) (cost=4.4 rows=17.1) (actual time=0.0107..0.0512 rows=2 loops=6)
-> Index lookup on t0 using i7 (c3 = t3.c3) (cost=4.4 rows=17.1) (actual time=0.00599..0.0476 rows=23 loops=6)
This shows that the default plan scans t1 first and performs about 1,000,000 lookups into t3, producing only 6 matching rows.
3. HINTED EXPLAIN ANALYZE BEFORE HISTOGRAMS
Observed:
-> Nested loop inner join (cost=3.88e+9 rows=38.1e+9) (actual time=62.4..62.6 rows=12 loops=1)
-> Nested loop inner join (cost=42986 rows=114692) (actual time=62.4..62.5 rows=6 loops=1)
-> Filter: ((t3.c1 >= -2066281069) and (t3.c3 is not null) and (t3.c0 is not null)) (cost=2035 rows=6703) (actual time=0.00817..12.4 rows=20003 loops=1)
-> Table scan on t3 (cost=2035 rows=20111) (actual time=0.00712..10.1 rows=20003 loops=1)
-> Filter: (t0.c3 = t3.c3) (cost=4.4 rows=17.1) (actual time=0.00241..0.00242 rows=300e-6 loops=20003)
-> Index lookup on t0 using i7 (c3 = t3.c3) (cost=4.4 rows=17.1) (actual time=0.00228..0.00229 rows=0.00345 loops=20003)
-> Covering index lookup on t1 using i2 (c0 = t3.c0) (cost=608 rows=332316) (actual time=0.00303..0.00399 rows=2 loops=6)
This hinted plan is estimated about 1550x more expensive than the default plan, but it is much faster.
4. DIRECT TIMING BEFORE HISTOGRAMS
Observed:
default: 1371.783 ms
hinted: 52.169 ms
5. CREATE HISTOGRAMS
The testcase then creates histograms on:
t1.c0
t3.c0
t3.c3
t0.c3
All histogram creation statements succeed, followed by ANALYZE TABLE.
6. BASE / HINTED EXPLAIN ANALYZE AFTER HISTOGRAMS
Observed after histograms:
default: about 1732 ms
hinted: about 60.8 ms
The default plan still scans t1 first and performs about 1,000,000 t3 lookups.
7. DIRECT TIMING AFTER HISTOGRAMS
Observed:
default: 1415.435 ms
hinted: 54.604 ms
Thus the testcase demonstrates the same cost-ranking inversion both before and after histograms.
Suggested fix:
The optimizer should improve equality-join fanout estimation for skewed or almost disjoint join-key value domains.
In this testcase, the default t1->t3 prefix is estimated to produce about 334k rows, but it actually produces only 6 rows after 1M index lookups. The alternative t3->t0->t1 plan is estimated to produce tens of billions of rows, mainly because the t1(c0 = t3.c0) lookup is estimated to return hundreds of thousands of rows per lookup, but in the actual plan it is executed only 6 times and returns 2 rows per lookup.
Single-column histograms on the relevant columns do not fix the estimates. It may be useful to make join selectivity estimation account better for skewed key distributions, tiny overlaps between join-key value domains, and the value distribution of rows that survive earlier join predicates.
