Description:
I believe this is an optimizer performance issue related to UPDATE HISTOGRAM, cardinality estimation, and join-order selection.
After creating the tables and inserting the data, I did not run ordinary ANALYZE TABLE for table/index statistics. At this point, mysql.innodb_table_stats showed stale persistent table statistics:
t0: n_rows = 39 actual table rows = 94
t1: n_rows = 13 actual table rows = 56
t2: n_rows = 6 actual table rows = 181
t3: n_rows = 0 actual table rows = 7
No column histograms were present at this point.
I then executed the target query before any ordinary ANALYZE TABLE was run:
SELECT DISTINCTROW t1.c1 AS ref0
FROM t0, t1 INNER JOIN t2 ON t2.c2
WHERE (((NULL) NOT IN (0.3859724501080619)) > (-650789194))
OR ((+ ((t1.c5) IN (t0.c5, "1e500"))))
GROUP BY t1.c1;
The optimizer did not appear to use the old persistent n_rows values shown in mysql.innodb_table_stats. Instead, EXPLAIN ANALYZE showed base-table estimates that matched the actual table sizes:
| -> Table scan on <temporary> (cost=264110..273759 rows=771755) (actual time=2.67..2.67 rows=4 loops=1)
-> Temporary table with deduplication (cost=264110..264110 rows=771755) (actual time=2.67..2.67 rows=4 loops=1)
-> Inner hash join (no condition) (cost=86286 rows=771755) (actual time=2.21..2.42 rows=1349 loops=1)
-> Filter: (0 <> t2.c2) (cost=0.00366 rows=163) (actual time=0.0116..0.121 rows=71 loops=1)
-> Table scan on t2 (cost=0.00366 rows=181) (actual time=0.00734..0.0888 rows=181 loops=1)
-> Hash
-> Filter: (t1.c5 in (t0.c5,'1e500')) (cost=533 rows=5264) (actual time=0.601..2.19 rows=19 loops=1)
-> Inner hash join (no condition) (cost=533 rows=5264) (actual time=0.0552..0.41 rows=5264 loops=1)
-> Table scan on t0 (cost=0.172 rows=94) (actual time=0.00542..0.0484 rows=94 loops=1)
-> Hash
-> Table scan on t1 (cost=5.85 rows=56) (actual time=0.00882..0.037 rows=56 loops=1)
|
1 row in set, 5245 warnings (0.003 sec)
Summary of the base-table estimates before UPDATE HISTOGRAM:
t0: estimated 94 rows, actual 94 rows
t1: estimated 56 rows, actual 56 rows
t2: estimated 181 rows, actual 181 rows
The selected plan was good. The optimizer preserved the t0/t1 join prefix, applied the selective predicate between t0 and t1:
t1.c5 IN (t0.c5, '1e500')
and then joined t2. In this plan, the t0/t1 join produced 5,264 candidate pairs, which were reduced to 19 rows by the selective predicate before joining t2. The query completed in about 2.6 ms.
However, after I created column histograms using ANALYZE TABLE ... UPDATE HISTOGRAM, without running ordinary ANALYZE TABLE for table/index statistics, the same query immediately changed to a much worse plan.
After UPDATE HISTOGRAM, mysql.innodb_table_stats still showed the same stale persistent table statistics:
t0: n_rows = 39
t1: n_rows = 13
t2: n_rows = 6
t3: n_rows = 0
Column histograms were now present. In this state, EXPLAIN ANALYZE showed that the optimizer used stale or stale-like base-table estimates:
| -> Table scan on <temporary> (cost=846..880 rows=2535) (actual time=170..170 rows=4 loops=1)
-> Temporary table with deduplication (cost=846..846 rows=2535) (actual time=170..170 rows=4 loops=1)
-> Filter: (t1.c5 in (t0.c5,'1e500')) (cost=262 rows=2535) (actual time=36..170 rows=1349 loops=1)
-> Inner hash join (no condition) (cost=262 rows=2535) (actual time=0.937..48 rows=373744 loops=1)
-> Table scan on t0 (cost=0.0665 rows=39) (actual time=0.00282..0.0669 rows=94 loops=1)
-> Hash
-> Inner hash join (no condition) (cost=7.61 rows=65) (actual time=0.138..0.541 rows=3976 loops=1)
-> Table scan on t1 (cost=0.313 rows=13) (actual time=0.00369..0.0316 rows=56 loops=1)
-> Hash
-> Filter: (0 <> t2.c2) (cost=0.85 rows=5) (actual time=0.0156..0.122 rows=71 loops=1)
-> Table scan on t2 (cost=0.85 rows=6) (actual time=0.0115..0.0908 rows=181 loops=1)
|
1 row in set, 65535 warnings (0.171 sec)
Summary of the base-table estimates after UPDATE HISTOGRAM:
t0: estimated 39 rows, actual 94 rows
t1: estimated 13 rows, actual 56 rows
t2: estimated 6 rows, actual 181 rows
In particular, the filtered cardinality of t2 was estimated as only 5 rows, while the actual filtered cardinality was 71 rows:
0 <> t2.c2
Based on these estimates, the optimizer chose a much worse join order. It joined t2 before the selective t0/t1 predicate could be applied. The execution first produced 3,976 rows from the t1/t2 part, then 373,744 intermediate rows after joining t0. Only after that was the selective t0/t1 predicate applied, reducing the result to 1,349 rows. The same query then took about 164-170 ms.
A JOIN_PREFIX(t0,t1) hint exposes the faster plan in the problematic state. The hinted plan preserves the t0/t1 prefix, applies the selective predicate early, and runs in about 2.5 ms, which is roughly 60x-65x faster than the default plan after UPDATE HISTOGRAM.
I understand that InnoDB table statistics may be refreshed asynchronously, and that the bad plan can disappear after table statistics are eventually refreshed. However, the issue here is the problematic transient optimizer state immediately after ANALYZE TABLE ... UPDATE HISTOGRAM. In my test, this state lasted for roughly 10 seconds. During this window, the optimizer can choose a severely suboptimal plan.
My hypothesis is that UPDATE HISTOGRAM may invalidate or reload optimizer statistics metadata. During subsequent optimization, the base-table cardinality estimates for some tables appear to fall back to stale persistent InnoDB statistics, while the newly created column histograms are already available. This creates a mixed statistics state, where fresh column histograms are used together with stale or stale-like base-table cardinalities.
This suggests that the issue is not merely that the persistent table statistics are stale. Rather, UPDATE HISTOGRAM appears to change which base cardinalities are used during optimization. In the transient mixed-statistics state, the optimizer significantly underestimates t2, makes the delayed t0/t1 predicate look artificially cheap, and chooses a plan that is about 60x slower than the corresponding JOIN_PREFIX(t0,t1) plan.
How to repeat:
A complete self-contained testcase is attached.
The attachment contains:
repro.sql
case1_update_histogram_no_analyze_table_bad_plan.sql
case1_update_histogram_no_analyze_table_bad_plan.out
case2_no_update_histogram_no_analyze_table_good_plan.sql
case2_no_update_histogram_no_analyze_table_good_plan.out
case3_analyze_table_and_update_histogram_good_plan.sql
case3_analyze_table_and_update_histogram_good_plan.out
case4_analyze_table_no_update_histogram_good_plan.sql
case4_analyze_table_no_update_histogram_good_plan.out
Each case script should be run after reloading the schema and data from repro.sql, so that the four cases are isolated from each other.
Example:
mysql < repro.sql
mysql < case1_update_histogram_no_analyze_table_bad_plan.sql
mysql < repro.sql
mysql < case2_no_update_histogram_no_analyze_table_good_plan.sql
mysql < repro.sql
mysql < case3_analyze_table_and_update_histogram_good_plan.sql
mysql < repro.sql
mysql < case4_analyze_table_no_update_histogram_good_plan.sql
The most important case is:
case1_update_histogram_no_analyze_table_bad_plan.sql
It performs the following steps:
1. Check mysql.innodb_table_stats before UPDATE HISTOGRAM.
2. Check that no column histograms are present.
3. Create column histograms using ANALYZE TABLE ... UPDATE HISTOGRAM.
4. Check mysql.innodb_table_stats again.
5. Check that histograms have been created.
6. Run the target query with EXPLAIN ANALYZE three times.
7. Run the JOIN_PREFIX(t0,t1) hinted query with EXPLAIN ANALYZE three times.
8. Check mysql.innodb_table_stats again.
Observed result for case 1:
Before and immediately after UPDATE HISTOGRAM:
mysql.innodb_table_stats still shows:
t0=39, t1=13, t2=6, t3=0
After UPDATE HISTOGRAM:
the default query estimates:
t0=39, t1=13, t2=6
```
the default plan joins t2 before the selective t0/t1 predicate can be applied,
produces 373,744 intermediate rows,
and runs in about 164-170 ms.
the JOIN_PREFIX(t0,t1) hinted plan applies the selective t0/t1 predicate early
and runs in about 2.5 ms.
```
The other three scripts are control cases:
case2_no_update_histogram_no_analyze_table_good_plan.sql
No ordinary ANALYZE TABLE and no UPDATE HISTOGRAM.
mysql.innodb_table_stats still shows stale n_rows values, but the optimizer
uses base-table estimates matching the actual table sizes and chooses the good plan.
case3_analyze_table_and_update_histogram_good_plan.sql
Ordinary ANALYZE TABLE is run and histograms are also created.
The optimizer chooses the good plan.
case4_analyze_table_no_update_histogram_good_plan.sql
Ordinary ANALYZE TABLE is run and no histograms are present.
The optimizer chooses the good plan.
Suggested fix:
Suggested areas to investigate:
1. Check whether ANALYZE TABLE ... UPDATE HISTOGRAM changes or invalidates the optimizer's base-table cardinality-estimation path.
2. In this testcase, before UPDATE HISTOGRAM the optimizer uses base-table estimates matching the actual table sizes, even though mysql.innodb_table_stats still shows stale persistent n_rows values. After UPDATE HISTOGRAM, the optimizer appears to use stale or stale-like base-table cardinalities together with newly created column histograms. This change causes a much worse join order.
3. Ensure that UPDATE HISTOGRAM does not cause newly created column histograms to be combined with stale or stale-like base-table cardinalities in a way that regresses plan quality.
4. Consider making join-order selection more robust when table-level cardinalities and column histograms may be in a mixed or inconsistent state, especially when a selective cross-table predicate can only be applied if a particular join prefix is preserved.
5. If this behavior is expected, it would be helpful to document that UPDATE HISTOGRAM may change base-table cardinality estimates or plan selection unless ordinary ANALYZE TABLE is also run for table/index statistics.
