| Bug #121331 | Optimizer discards the chosen range access and falls back to a table scan for antijoin / LEFT JOIN queries | ||
|---|---|---|---|
| Submitted: | 21 Sep 5:05 | Modified: | 21 Sep 9:29 |
| Reporter: | Yutaro Inoue | Email Updates: | |
| Status: | Verified | Impact on me: | |
| Category: | MySQL Server: Optimizer | Severity: | S3 (Non-critical) |
| Version: | 8.4.12, 9.7.3, 26.7.1 | OS: | Linux |
| Assigned to: | CPU Architecture: | Any | |
| Tags: | antijoin, left join, Optimizer, SUB QUERY | ||
[21 Sep 5:06]
Yutaro Inoue
The same behaviour is not limited to antijoins; it also shows up with the following LEFT JOIN query.
SELECT t1.id
FROM t1
LEFT JOIN (t2 JOIN t3 ON t3.id >= t2.b AND t3.id <= t2.b
AND t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59')
ON t2.a = t1.id
WHERE t1.id BETWEEN 1 AND 10000
Execution plan (EXPLAIN FORMAT=TRADITIONAL):
+----+-------------+-------+------------+-------+---------------------+------------+---------+--------------+--------+----------+--------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------------+------------+---------+--------------+--------+----------+--------------------------+
| 1 | SIMPLE | t1 | NULL | range | PRIMARY | PRIMARY | 8 | NULL | 19138 | 100.00 | Using where; Using index |
| 1 | SIMPLE | t2 | NULL | ref | idx_t2_a_b,idx_t2_b | idx_t2_a_b | 8 | rt_msk.t1.id | 1 | 100.00 | Using index |
| 1 | SIMPLE | t3 | NULL | ALL | PRIMARY,idx_t3_d_id | NULL | NULL | NULL | 998222 | 100.00 | Using where |
+----+-------------+-------+------------+-------+---------------------+------------+---------+--------------+--------+----------+--------------------------+
3 rows in set, 1 warning (0.00 sec)
Note (Code 1003): /* select#1 */ select `rt_msk`.`t1`.`id` AS `id` from `rt_msk`.`t1` left join (`rt_msk`.`t2` join `rt_msk`.`t3`) on(((`rt_msk`.`t2`.`a` = `rt_msk`.`t1`.`id`) and (`rt_msk`.`t3`.`id` >= `rt_msk`.`t2`.`b`) and (`rt_msk`.`t3`.`id` <= `rt_msk`.`t2`.`b`) and (`rt_msk`.`t3`.`d` between '2026-08-27 15:00:00' and '2026-08-28 14:59:59'))) where (`rt_msk`.`t1`.`id` between 1 and 10000)
Excerpt from the optimizer trace:
"rest_of_plan": [
{
"plan_prefix": [
"`t1`",
"`t2`"
],
"table": "`t3`",
"best_access_path": {
"considered_access_paths": [
{
"rows_to_scan": 1440,
"access_type": "range",
"range_details": {
"used_index": "idx_t3_d_id"
},
"resulting_rows": 1440,
"cost": 7.89192e+06,
"chosen": true
}
]
},
Antijoin queries are internally converted to use a LEFT JOIN -> https://github.com/mysql/mysql-server/blob/mysql-8.4.11/sql/sql_resolver.cc#L3006-L3053
This is only a guess, but the inability of `rechecking_index_usage` to account for `t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59'` may be specific to the LEFT JOIN form. That would explain why the problem is observed with both antijoin and LEFT JOIN queries.
[21 Sep 5:06]
Yutaro Inoue
With the semijoin query below, the range access on t3 is retained.
SELECT t1.id
FROM t1
WHERE t1.id BETWEEN 1 AND 10000
AND EXISTS (
SELECT * FROM t2
WHERE t2.b IN (SELECT t3.id FROM t3
WHERE t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59')
AND t2.a = t1.id)
Execution plan (EXPLAIN FORMAT=TRADITIONAL):
+----+--------------+-------------+------------+--------+---------------------+-------------+---------+---------------+------+----------+--------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+--------------+-------------+------------+--------+---------------------+-------------+---------+---------------+------+----------+--------------------------+
| 1 | SIMPLE | <subquery2> | NULL | ALL | NULL | NULL | NULL | NULL | NULL | 100.00 | Using where |
| 1 | SIMPLE | t1 | NULL | eq_ref | PRIMARY | PRIMARY | 8 | <subquery2>.a | 1 | 100.00 | Using index |
| 2 | MATERIALIZED | t3 | NULL | range | PRIMARY,idx_t3_d_id | idx_t3_d_id | 5 | NULL | 1440 | 100.00 | Using where; Using index |
| 2 | MATERIALIZED | t2 | NULL | ref | idx_t2_a_b,idx_t2_b | idx_t2_b | 8 | rt_msk.t3.id | 1 | 3.57 | NULL |
+----+--------------+-------------+------------+--------+---------------------+-------------+---------+---------------+------+----------+--------------------------+
4 rows in set, 2 warnings (0.01 sec)
Note (Code 1276): Field or reference 'rt_msk.t1.id' of SELECT #2 was resolved in SELECT #1
Note (Code 1003): /* select#1 */ select `rt_msk`.`t1`.`id` AS `id` from `rt_msk`.`t1` semi join (`rt_msk`.`t2` join `rt_msk`.`t3`) where ((`rt_msk`.`t1`.`id` = `<subquery2>`.`a`) and (`rt_msk`.`t2`.`b` = `rt_msk`.`t3`.`id`) and (`<subquery2>`.`a` between 1 and 10000) and (`rt_msk`.`t3`.`d` between '2026-08-27 15:00:00' and '2026-08-28 14:59:59'))
In the semijoin case, `rechecking_index_usage` contains an `analyzing_range_alternatives` section, which indicates that the optimizer does recognize the predicate (`t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59'`) at that point.
Excerpt from the optimizer trace:
"analyzing_range_alternatives": {
"range_scan_alternatives": [
{
"index": "idx_t3_d_id",
"ranges": [
"'2026-08-27 15:00:00' <= d <= '2026-08-28 14:59:59'"
],
"index_dives_for_eq_ranges": true,
"rowid_ordered": false,
"using_mrr": false,
"index_only": true,
"in_memory": 0.00263158,
"rows": 1440,
"cost": 148.681,
"chosen": true
}
],
[21 Sep 9:29]
Chaithra Marsur Gopala Reddy
Hi Yutaro Inoue, Thank you for the test case. Verified as described.
Description: For SELECT statements involving an antijoin or a LEFT JOIN, the optimizer initially picks a range access for one of the tables, but that choice is later discarded and the plan ends up using a full table scan instead. This behaviour is reproducible on at least the current latest minor releases (8.4.12, 9.7.3, 26.7.1). How to repeat: # Create a database and tables DROP DATABASE IF EXISTS rt_msk; CREATE DATABASE rt_msk; USE rt_msk; CREATE TABLE t1 ( id BIGINT NOT NULL, PRIMARY KEY (id) ); CREATE TABLE t2 ( id BIGINT NOT NULL AUTO_INCREMENT, a BIGINT NOT NULL, b BIGINT NOT NULL, PRIMARY KEY (id), KEY idx_t2_a_b (a, b), KEY idx_t2_b (b) ); CREATE TABLE t3 ( id BIGINT NOT NULL, d DATETIME NOT NULL, PRIMARY KEY (id), KEY idx_t3_d_id (d, id) ); SET SESSION cte_max_recursion_depth = 1500000; # Insert data INSERT INTO t1 (id) WITH RECURSIVE seq(n) AS ( SELECT 1 UNION ALL SELECT n + 1 FROM seq WHERE n < 1000000 ) SELECT n FROM seq; INSERT INTO t2 (a, b) WITH RECURSIVE seq(n) AS ( SELECT 1 UNION ALL SELECT n + 1 FROM seq WHERE n < 1400000 ) SELECT ((n * 48271) MOD 1000000) + 1, ((n * 2654435761) MOD 1000000) + 1 FROM seq; INSERT INTO t3 (id, d) WITH RECURSIVE seq(n) AS ( SELECT 1 UNION ALL SELECT n + 1 FROM seq WHERE n < 1000000 ) SELECT n, TIMESTAMP('2025-01-01 00:00:00') + INTERVAL (n MOD (730*24*60)) MINUTE FROM seq; ANALYZE TABLE t1, t2, t3; # Check version and optimizer_switch mysql> SELECT version(),@@optimizer_switch, @@eq_range_index_dive_limit\G *************************** 1. row *************************** version(): 8.4.12 @@optimizer_switch: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on,use_invisible_indexes=off,skip_scan=on,hash_join=on,subquery_to_derived=off,prefer_ordering_index=on,hypergraph_optimizer=off,derived_condition_pushdown=on,hash_set_operations=on @@eq_range_index_dive_limit: 200 1 row in set (0.01 sec) # Query A (MaterializeLookup) SELECT t1.id FROM t1 WHERE t1.id BETWEEN 1 AND 10000 AND NOT EXISTS ( SELECT * FROM t2 WHERE t2.b IN (SELECT t3.id FROM t3 WHERE t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59') AND t2.a = t1.id); Execution plan (EXPLAIN FORMAT=TRADITIONAL): +----+--------------+-------------+------------+--------+---------------------+---------------------+---------+--------------+--------+----------+--------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+--------------+-------------+------------+--------+---------------------+---------------------+---------+--------------+--------+----------+--------------------------+ | 1 | SIMPLE | t1 | NULL | range | PRIMARY | PRIMARY | 8 | NULL | 19138 | 100.00 | Using where; Using index | | 1 | SIMPLE | <subquery2> | NULL | eq_ref | <auto_distinct_key> | <auto_distinct_key> | 9 | rt_msk.t1.id | 1 | 100.00 | Using where; Not exists | | 2 | MATERIALIZED | t3 | NULL | ALL | PRIMARY,idx_t3_d_id | NULL | NULL | NULL | 998222 | 100.00 | Using where | | 2 | MATERIALIZED | t2 | NULL | ref | idx_t2_a_b,idx_t2_b | idx_t2_b | 8 | rt_msk.t3.id | 1 | 100.00 | NULL | +----+--------------+-------------+------------+--------+---------------------+---------------------+---------+--------------+--------+----------+--------------------------+ 4 rows in set, 2 warnings (0.01 sec) Note (Code 1276): Field or reference 'rt_msk.t1.id' of SELECT #2 was resolved in SELECT #1 Note (Code 1003): /* select#1 */ select `rt_msk`.`t1`.`id` AS `id` from `rt_msk`.`t1` anti join (`rt_msk`.`t2` join `rt_msk`.`t3`) on(((`<subquery2>`.`a` = `rt_msk`.`t1`.`id`) and (`rt_msk`.`t2`.`b` = `rt_msk`.`t3`.`id`) and (`rt_msk`.`t3`.`d` between '2026-08-27 15:00:00' and '2026-08-28 14:59:59'))) where (`rt_msk`.`t1`.`id` between 1 and 10000) Note that t3 is accessed with type=ALL. The optimizer trace, however, shows that a range access on idx_t3_d_id had been chosen for t3 earlier on. Given the predicate `WHERE t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59'`, a range scan on `idx_t3_d_id` should clearly be the more efficient choice. In the `rechecking_index_usage` section of the trace, no range access is selected. Excerpt from the optimizer trace: "rest_of_plan": [ { "plan_prefix": [ "`t1`" ], "table": "`t3`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "PRIMARY", "usable": false, "chosen": false }, { "rows_to_scan": 1440, "access_type": "range", "range_details": { "used_index": "idx_t3_d_id" }, "resulting_rows": 1440, "cost": 5.60151e+06, "chosen": true } ] }, ..... "attaching_conditions_to_tables": { "original_condition": "(`t1`.`id` between 1 and 10000)", "attached_conditions_computation": [ { "table": "`t3`", "rechecking_index_usage": { "recheck_reason": "not_first_table", "range_analysis": { "table_scan": { "rows": 998222, "cost": 101908 }, "potential_range_indexes": [ { "index": "PRIMARY", "usable": true, "key_parts": [ "id" ] }, { "index": "idx_t3_d_id", "usable": true, "key_parts": [ "d", "id" ] } ], "best_covering_index_scan": { "index": "idx_t3_d_id", "cost": 102376, "chosen": false, "cause": "cost" }, "setup_range_conditions": [], "range_scan_possible": false, "cause": "condition_always_true", "group_index_skip_scan": { "chosen": false, "cause": "not_original_query_table" }, "skip_scan_range": { "chosen": false, "cause": "not_single_table" } } } } ], # Query B (FirstMatch) SELECT t1.id FROM t1 WHERE t1.id BETWEEN 1 AND 10000 AND NOT EXISTS ( SELECT 1 FROM t2, t3 WHERE t3.id >= t2.b AND t3.id <= t2.b AND t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59' AND t2.a = t1.id) Execution plan (EXPLAIN FORMAT=TRADITIONAL): +----+-------------+-------+------------+-------+---------------------+------------+---------+--------------+--------+----------+--------------------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------------+------------+---------+--------------+--------+----------+--------------------------------------+ | 1 | SIMPLE | t1 | NULL | range | PRIMARY | PRIMARY | 8 | NULL | 19138 | 100.00 | Using where; Using index | | 1 | SIMPLE | t2 | NULL | ref | idx_t2_a_b,idx_t2_b | idx_t2_a_b | 8 | rt_msk.t1.id | 1 | 100.00 | Using where; Not exists; Using index | | 1 | SIMPLE | t3 | NULL | ALL | PRIMARY,idx_t3_d_id | NULL | NULL | NULL | 998222 | 100.00 | Using where | +----+-------------+-------+------------+-------+---------------------+------------+---------+--------------+--------+----------+--------------------------------------+ 3 rows in set, 2 warnings (0.00 sec) Note (Code 1276): Field or reference 'rt_msk.t1.id' of SELECT #2 was resolved in SELECT #1 Note (Code 1003): /* select#1 */ select `rt_msk`.`t1`.`id` AS `id` from `rt_msk`.`t1` anti join (`rt_msk`.`t2` join `rt_msk`.`t3`) on(((`rt_msk`.`t2`.`a` = `rt_msk`.`t1`.`id`) and (`rt_msk`.`t3`.`id` >= `rt_msk`.`t2`.`b`) and (`rt_msk`.`t3`.`id` <= `rt_msk`.`t2`.`b`) and (`rt_msk`.`t3`.`d` between '2026-08-27 15:00:00' and '2026-08-28 14:59:59'))) where (`rt_msk`.`t1`.`id` between 1 and 10000) As with Query A, t3 ends up with type=ALL, even though a range access on idx_t3_d_id was originally chosen here as well. Excerpt from the optimizer trace: "rest_of_plan": [ { "plan_prefix": [ "`t1`", "`t2`" ], "table": "`t3`", "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 1440, "access_type": "range", "range_details": { "used_index": "idx_t3_d_id" }, "resulting_rows": 1440, "cost": 7.89192e+06, "chosen": true } ] }, I tested both queries across several versions. The results are as follows. Table: is t3 accessed with type=ALL? Version Query A Query B -------------------------------------- -------- -------- MySQL 8.0.31 No No MySQL 8.0.32 Yes Yes MySQL 8.0.32 (Commit 40c62c4 reverted) No No MySQL 8.4.11 Yes Yes MySQL 8.4.12 Yes Yes MySQL 9.7.3 Yes Yes MySQL 26.7.1 Yes Yes Analysis: - Debugging with a debug build of MySQL 8.4.11 suggests the following explanation for why the range access that was originally chosen gets thrown away. - While finalizing the plan, there is a phase that re-examines whether an index should be used (the `rechecking_index_usage` section in the optimizer trace) -> https://github.com/mysql/mysql-server/blob/mysql-8.4.11/sql/sql_optimizer.cc#L9893-L9922 - In that phase, if the table was previously assigned a range access, the access method is first overwritten with ALL -> https://github.com/mysql/mysql-server/blob/mysql-8.4.11/sql/sql_optimizer.cc#L10067-L10071 - Commit 40c62c4 (https://github.com/mysql/mysql-server/commit/40c62c41cb664b378c2237e4ea3756f0636bee8f) widened the cases in which range access is considered, so that a range access on t3 is now chosen for Queries A and B. As a consequence, t3 is the table whose access method gets reset to ALL during the recheck. - During the recheck, the optimizer appears unable to take the predicate `t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59'` into account. - Because of that, it cannot conclude that a range access on t3 is possible, and the plan is left with the ALL access method that overwrote the original choice. - https://bugs.mysql.com/bug.php?id=117770 looks superficially similar, but the behaviour described in that report does not reproduce on 8.4.12, 9.7.3 or 26.7.1, so I believe it is a different issue. Suggested fix: - In `rechecking_index_usage`, do not overwrite the access method with ALL up front; keep the existing choice (a range access in this case) until a better alternative is actually found. - Make `rechecking_index_usage` able to take the conditions on the table into account (here, `t3.d BETWEEN '2026-08-27 15:00:00' AND '2026-08-28 14:59:59'`).