| Bug #116875 | condition of 'ReuseRangeEstimateForRef-4' is wrong and cannot correct the fanout estimation for a REF of join | ||
|---|---|---|---|
| Submitted: | 4 Dec 2024 16:25 | Modified: | 5 Dec 2024 11:31 |
| Reporter: | NANLONG YU | Email Updates: | |
| Status: | Verified | Impact on me: | |
| Category: | MySQL Server: Optimizer | Severity: | S4 (Feature request) |
| Version: | 8.0 | OS: | Any |
| Assigned to: | CPU Architecture: | Any | |
| Tags: | Optimizer, Optimizer bug | ||
[4 Dec 2024 16:27]
NANLONG YU
there is create info and data of table t2 in t2.sql
Attachment: t2.sql (application/octet-stream, text), 1.71 KiB.
[4 Dec 2024 16:28]
NANLONG YU
there is create info and data of t1 in t1.sql
Attachment: t1.sql (application/octet-stream, text), 6.66 KiB.
[4 Dec 2024 17:00]
MySQL Verification Team
Hi Mr. YU, Thank you for your bug report. However, we can not repeat it. In order to repeat it, we need rows for the table(s). When you send us table contents, we shall try to repeat it. Thanks in advance.
[5 Dec 2024 10:50]
MySQL Verification Team
Hi Mr. YU, Thank you for your bug report. This is now a verified Optimiser feature request covering all versions from 8.0 to 9.1. It is a feature request because the change that you recommended would work for this type of query, but not for some other query types. Verified.
[5 Dec 2024 11:15]
NANLONG YU
Hi Thank u for verifying this. Based on the comments in the code of 'ReuseRangeEstimateForRef-4', I think the original intention of the person who wrote this code is as I have described. The code of 'ReuseRangeEstimateForRef-2' serves a similar function and can be referenced for comparison. To clarify, the code of 'ReuseRangeEstimateForRef-4' performs a fix when not all columns in the index are covered, while the code of 'ReuseRangeEstimateForRef-2' performs a fix when all columns in the index are covered. In summary, I believe that it was a subtle mistake made by the person writing the code, rather than any other intention.
[5 Dec 2024 11:31]
NANLONG YU
Hi, Thanks again for verifying this bug. Based on the comments in the code of 'ReuseRangeEstimateForRef-4', I think the original intention of the person who wrote this code is as I have described. The code of 'ReuseRangeEstimateForRef-2' serves a similar function and can be referenced for comparison. To clarify, the code of 'ReuseRangeEstimateForRef-4' performs a fix when not all columns in the index are covered, while the code of 'ReuseRangeEstimateForRef-2' performs a fix when all columns in the index are covered. In summary, I believe that it was a subtle mistake made by the person writing the code, rather than any other intention. Let me clarify further: for this if-condition, `table->quick_key_parts[key]` represents the number of prefix columns of the index used by the ref access. The value of `(1 << table->quick_key_parts[key])` with a bit of 1 actually indicates the position of a column in the index that is not used by the ref access. Since this column is not being used at all, why should we use the cardinality estimation from the ref access to make corrections? Best regards
[5 Dec 2024 11:52]
MySQL Verification Team
Thank you, Mr. Yu.
Description: In the following case, there are two indexes in table `t1`, `idx_abc(a, b, c)` and `idx_d(d)`. MySQL [test]> show create table t1\G *************************** 1. row *************************** Table: t1 Create Table: CREATE TABLE `t1` ( `a` int(11) DEFAULT NULL, `b` int(11) DEFAULT NULL, `c` int(11) DEFAULT NULL, `d` int(11) DEFAULT NULL, KEY `idx_abc` (`a`,`b`,`c`), KEY `idx_d` (`d`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 /*!50100 PARTITION BY HASH (`a`) PARTITIONS 2 */ 1 row in set (0.00 sec) MySQL [test]> show create table t2\G *************************** 1. row *************************** Table: t2 Create Table: CREATE TABLE `t2` ( `a` int(11) DEFAULT NULL ) ENGINE=InnoDB DEFAULT CHARSET=utf8 1 row in set (0.00 sec) MySQL [test]> explain select * from t2 join t1 on t1.a = 2 and t1.b = t2.a and t1.d = 4; +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+ | 1 | SIMPLE | t2 | NULL | ALL | NULL | NULL | NULL | NULL | 1 | 100.00 | NULL | | 1 | SIMPLE | t1 | p0 | ref | idx_abc,idx_d | idx_d | 5 | const | 149 | 2.14 | Using where | +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+ 2 rows in set, 1 warning (0.00 sec) In the above join statement, apparently `idx_abc(a, b, c)` is better than `idx_d(d)`. Because for the condition `t1.a = 2` with `idx_abc(a, b, c)`, the result rows from index diving is 40, which means the fanout of the condition `t1.a = 2` and t1.b = t2.a` is less than or equal to 40. And for the condition `t1.d = 4` with idx_d(d), the result rows from index diving is 149. The corresponding optimizer trace is as follows: "analyzing_range_alternatives": { "range_scan_alternatives": [ { "index": "idx_abc", "ranges": [ "2 <= a <= 2" ], "index_dives_for_eq_ranges": true, "rowid_ordered": false, "using_mrr": false, "index_only": false, "in_memory": -1, "rows": 40, "cost": 14.26, "chosen": true }, { "index": "idx_d", "ranges": [ "4 <= d <= 4" ], "index_dives_for_eq_ranges": true, "rowid_ordered": true, "using_mrr": false, "index_only": false, "in_memory": -1, "rows": 149, "cost": 52.41, "chosen": false, "cause": "cost" } ], "analyzing_roworder_intersect": { "usable": false, "cause": "too_few_roworder_scans" } }, However, according to the optimizer trace, the fanout of the condition `t1.a = 2 and t1.b = t2.a` is 150, which derives from the num-of-distinct-value of the biggest partition `t1#P#p1`. As a result, `idx_d(d)` is finally chosen in the above explain output of the join statement. The corresponding optimizer trace is as follows: "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "idx_abc", "rows": 150, "cost": 15.75, "chosen": true }, { "access_type": "ref", "index": "idx_d", "rows": 149, "cost": 15.65, "chosen": true }, { "rows_to_scan": 40, "filtering_effect": [ ], "final_filtering_effect": 0.7968, "access_type": "range", "range_details": { "used_index": "idx_abc" }, "resulting_rows": 31.872, "cost": 18.26, "chosen": false } ] }, As there is row estimation from index diving, the fanout of the condition `t1.a = 2 and t1.b = t2.a` should be fixed by 'ReuseRangeEstimateForRef-4'. But the if-condition of 'ReuseRangeEstimateForRef-4' is wrong so that the fanout of the condition `t1.a = 2 and t1.b = t2.a` cannot be fixed in actual. All in all, in some cases, row estimation from num-distinct-value should be fixed by row estimation from index diving of a REF's 'const part', but there is error in if-condition of 'ReuseRangeEstimateForRef-4' so that the row estimation cannot be fixed. How to repeat: 1. source the two sql files to create table and load the data of t1 and t2(source t1.sql; source t2.sql;) 2. analyze table t1 3. analyze table t2 4. execute the statement `explain select * from t2 join t1 on t1.a = 2 and t1.b = t2.a and t1.d = 4;` Suggested fix: change the if-condition of ReuseRangeEstimateForRef-4 from const_part & ((key_part_map)1 << table->quick_key_parts[key]) to const_part & (((key_part_map)1 << table->quick_key_parts[key]) - 1)