revision-id: b0a9bfcf6d187a5de2ebda15d09b3f3779bff264 (mariadb-10.2.31-462-gb0a9bfc) parent(s): 7c5519c12d46ead947d341cbdcbb6fbbe4d4fe1b author: Igor Babaev committer: Igor Babaev timestamp: 2020-09-24 19:56:36 -0700 message: MDEV-23811: With large number of indexes optimizer chooses an inefficient plan This bug could manifest itself for a query with WHERE condition containing top level OR formula such that each conjunct contained a single-range condition supported by the same index. One of these range conditions must be fully covered by another range condition that is used later in the OR formula. Additionally at leat one of these condition should be ANDed with a sargable range condition supported by a different index. There were several attempts to fix related problems for OR conditions after the backport of range optimizer code from MySQL (commit 0e19f3e36f7842583feb6bead2c2600cd620bced). Unfortunately the first of these fixes contained typo remained unnoticed until recently. This typo bug led to rejection of valid range accesses. This patch fixed this typo bug. The fix revealed another two bugs: one in a constructor for SEL_ARG, the other in the function tree_or(). Both are fixed in this patch. --- mysql-test/r/range.result | 74 ++++++++++++++++++++++++- mysql-test/r/range_mrr_icp.result | 74 ++++++++++++++++++++++++- mysql-test/r/range_vs_index_merge_innodb.result | 2 +- mysql-test/t/range.test | 42 ++++++++++++++ sql/opt_range.cc | 20 ++++--- 5 files changed, 201 insertions(+), 11 deletions(-) diff --git a/mysql-test/r/range.result b/mysql-test/r/range.result index 26ea2c6..7299982 100644 --- a/mysql-test/r/range.result +++ b/mysql-test/r/range.result @@ -1274,7 +1274,7 @@ SELECT * FROM t1 WHERE 5 <= a AND b = 3 OR 3 <= a; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range a a 5 NULL 4 Using where; Using index +1 SIMPLE t1 range a a 5 NULL 3 Using where; Using index SELECT * FROM t1 WHERE 3 <= a AND a <= 5 OR 5 <= a AND b = 3 OR @@ -3054,5 +3054,77 @@ a b set eq_range_index_dive_limit=default; drop table t1; # +# MDEV-23811: Both disjunct of WHERE condition contain range conditions +# for the same index such that the second range condition +# fully covers the first one. Additionally one of the disjuncts +# contains a range condition for the other index. +# +create table t1 ( +pk int primary key auto_increment, a int, b int, +index idx1(a), index idx2(b) +); +insert into t1(a,b) values +(5,50), (1,10), (3,30), (7,70), (8,80), (4,40), (2,20), (6,60); +insert into t1(a,b) select a+10, b+100 from t1; +insert into t1(a,b) select a+20, b+200 from t1; +insert into t1(a,b) select a+30, b+300 from t1; +insert into t1(a,b) select a,b from t1; +analyze table t1; +Table Op Msg_type Msg_text +test.t1 analyze status OK +explain select * from t1 where ((a between 3 and 4) and b < 100) or (a between 2 and 5); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range idx1,idx2 idx1 5 NULL 11 Using index condition; Using where +select * from t1 where ((a between 3 and 4) and b < 100) or (a between 2 and 5); +pk a b +7 2 20 +71 2 20 +3 3 30 +67 3 30 +6 4 40 +70 4 40 +1 5 50 +65 5 50 +explain select * from t1 where (a between 2 and 5) or ((a between 3 and 4) and b < 100); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range idx1,idx2 idx1 5 NULL 11 Using index condition; Using where +select * from t1 where (a between 2 and 5) or ((a between 3 and 4) and b < 100); +pk a b +7 2 20 +71 2 20 +3 3 30 +67 3 30 +6 4 40 +70 4 40 +1 5 50 +65 5 50 +explain select * from t1 where (a between 3 and 4) or ((a between 2 and 5) and b < 100); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range idx1,idx2 idx1 5 NULL 11 Using index condition; Using where +select * from t1 where (a between 3 and 4) or ((a between 2 and 5) and b < 100); +pk a b +7 2 20 +71 2 20 +3 3 30 +67 3 30 +6 4 40 +70 4 40 +1 5 50 +65 5 50 +explain select * from t1 where ((a between 2 and 5) and b < 100) or (a between 3 and 4); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range idx1,idx2 idx1 5 NULL 11 Using index condition; Using where +select * from t1 where ((a between 2 and 5) and b < 100) or (a between 3 and 4); +pk a b +7 2 20 +71 2 20 +3 3 30 +67 3 30 +6 4 40 +70 4 40 +1 5 50 +65 5 50 +drop table t1; +# # End of 10.2 tests # diff --git a/mysql-test/r/range_mrr_icp.result b/mysql-test/r/range_mrr_icp.result index fe4eb99..cdaaa5e 100644 --- a/mysql-test/r/range_mrr_icp.result +++ b/mysql-test/r/range_mrr_icp.result @@ -1276,7 +1276,7 @@ SELECT * FROM t1 WHERE 5 <= a AND b = 3 OR 3 <= a; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range a a 5 NULL 4 Using where; Using index +1 SIMPLE t1 range a a 5 NULL 3 Using where; Using index SELECT * FROM t1 WHERE 3 <= a AND a <= 5 OR 5 <= a AND b = 3 OR @@ -3066,6 +3066,78 @@ a b set eq_range_index_dive_limit=default; drop table t1; # +# MDEV-23811: Both disjunct of WHERE condition contain range conditions +# for the same index such that the second range condition +# fully covers the first one. Additionally one of the disjuncts +# contains a range condition for the other index. +# +create table t1 ( +pk int primary key auto_increment, a int, b int, +index idx1(a), index idx2(b) +); +insert into t1(a,b) values +(5,50), (1,10), (3,30), (7,70), (8,80), (4,40), (2,20), (6,60); +insert into t1(a,b) select a+10, b+100 from t1; +insert into t1(a,b) select a+20, b+200 from t1; +insert into t1(a,b) select a+30, b+300 from t1; +insert into t1(a,b) select a,b from t1; +analyze table t1; +Table Op Msg_type Msg_text +test.t1 analyze status OK +explain select * from t1 where ((a between 3 and 4) and b < 100) or (a between 2 and 5); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range idx1,idx2 idx1 5 NULL 11 Using index condition; Using where; Rowid-ordered scan +select * from t1 where ((a between 3 and 4) and b < 100) or (a between 2 and 5); +pk a b +1 5 50 +3 3 30 +6 4 40 +7 2 20 +65 5 50 +67 3 30 +70 4 40 +71 2 20 +explain select * from t1 where (a between 2 and 5) or ((a between 3 and 4) and b < 100); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range idx1,idx2 idx1 5 NULL 11 Using index condition; Using where; Rowid-ordered scan +select * from t1 where (a between 2 and 5) or ((a between 3 and 4) and b < 100); +pk a b +1 5 50 +3 3 30 +6 4 40 +7 2 20 +65 5 50 +67 3 30 +70 4 40 +71 2 20 +explain select * from t1 where (a between 3 and 4) or ((a between 2 and 5) and b < 100); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range idx1,idx2 idx1 5 NULL 11 Using index condition; Using where; Rowid-ordered scan +select * from t1 where (a between 3 and 4) or ((a between 2 and 5) and b < 100); +pk a b +1 5 50 +3 3 30 +6 4 40 +7 2 20 +65 5 50 +67 3 30 +70 4 40 +71 2 20 +explain select * from t1 where ((a between 2 and 5) and b < 100) or (a between 3 and 4); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range idx1,idx2 idx1 5 NULL 11 Using index condition; Using where; Rowid-ordered scan +select * from t1 where ((a between 2 and 5) and b < 100) or (a between 3 and 4); +pk a b +1 5 50 +3 3 30 +6 4 40 +7 2 20 +65 5 50 +67 3 30 +70 4 40 +71 2 20 +drop table t1; +# # End of 10.2 tests # set optimizer_switch=@mrr_icp_extra_tmp; diff --git a/mysql-test/r/range_vs_index_merge_innodb.result b/mysql-test/r/range_vs_index_merge_innodb.result index 581f512..916c30b 100644 --- a/mysql-test/r/range_vs_index_merge_innodb.result +++ b/mysql-test/r/range_vs_index_merge_innodb.result @@ -369,7 +369,7 @@ WHERE ((ID < 200) AND (Name LIKE 'Ha%' OR (Country > 'A' AND Country < 'ARG'))) OR ((ID BETWEEN 100 AND 200) AND (Name LIKE 'Pa%' OR (Population > 103000 AND Population < 104000))); id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE City index_merge PRIMARY,Population,Country,Name Name,Population,PRIMARY 39,4,4 NULL 307 Using sort_union(Name,Population,PRIMARY); Using where +1 SIMPLE City range PRIMARY,Population,Country,Name PRIMARY 4 NULL 200 Using where SELECT * FROM City USE INDEX () WHERE ((ID < 10) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG'))) OR ((ID BETWEEN 100 AND 110) AND diff --git a/mysql-test/t/range.test b/mysql-test/t/range.test index 67d876d..0d2fbe2 100644 --- a/mysql-test/t/range.test +++ b/mysql-test/t/range.test @@ -2096,6 +2096,48 @@ set eq_range_index_dive_limit=default; drop table t1; --echo # +--echo # MDEV-23811: Both disjunct of WHERE condition contain range conditions +--echo # for the same index such that the second range condition +--echo # fully covers the first one. Additionally one of the disjuncts +--echo # contains a range condition for the other index. +--echo # + +create table t1 ( + pk int primary key auto_increment, a int, b int, + index idx1(a), index idx2(b) +); +insert into t1(a,b) values + (5,50), (1,10), (3,30), (7,70), (8,80), (4,40), (2,20), (6,60); +insert into t1(a,b) select a+10, b+100 from t1; +insert into t1(a,b) select a+20, b+200 from t1; +insert into t1(a,b) select a+30, b+300 from t1; +insert into t1(a,b) select a,b from t1; + +analyze table t1; + +let $q1= +select * from t1 where ((a between 3 and 4) and b < 100) or (a between 2 and 5); +eval explain $q1; +eval $q1; + +let $q2= +select * from t1 where (a between 2 and 5) or ((a between 3 and 4) and b < 100); +eval explain $q2; +eval $q2; + +let $q3= +select * from t1 where (a between 3 and 4) or ((a between 2 and 5) and b < 100); +eval explain $q3; +eval $q3; + +let $q4= +select * from t1 where ((a between 2 and 5) and b < 100) or (a between 3 and 4); +eval explain $q4; +eval $q4; + +drop table t1; + +--echo # --echo # End of 10.2 tests --echo # diff --git a/sql/opt_range.cc b/sql/opt_range.cc index e933d2a..cd58202 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -1852,6 +1852,9 @@ SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc() next_key_part=arg.next_key_part; max_part_no= arg.max_part_no; use_count=1; elements=1; + next= 0; + if (next_key_part) + ++next_key_part->use_count; } @@ -8869,9 +8872,15 @@ tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) } bool no_imerge_from_ranges= FALSE; + SEL_TREE *rt1= tree1; + SEL_TREE *rt2= tree2; /* Build the range part of the tree for the formula (1) */ if (sel_trees_can_be_ored(param, tree1, tree2, &ored_keys)) { + if (no_merges1) + rt1= new SEL_TREE(tree1, TRUE, param); + if (no_merges2) + rt2= new SEL_TREE(tree2, TRUE, param); bool must_be_ored= sel_trees_must_be_ored(param, tree1, tree2, ored_keys); no_imerge_from_ranges= must_be_ored; @@ -8929,12 +8938,6 @@ tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) else if (!no_ranges1 && !no_ranges2 && !no_imerge_from_ranges) { /* Build the imerge part of the tree for the formula (1) */ - SEL_TREE *rt1= tree1; - SEL_TREE *rt2= tree2; - if (no_merges1) - rt1= new SEL_TREE(tree1, TRUE, param); - if (no_merges2) - rt2= new SEL_TREE(tree2, TRUE, param); if (!rt1 || !rt2 || result->merges.push_back(imerge_from_ranges) || imerge_from_ranges->or_sel_tree(param, rt1) || @@ -9597,10 +9600,11 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2) if (!tmp->next_key_part) { + SEL_ARG *key2_next= key2->next; if (key2->use_count) { SEL_ARG *key2_cpy= new SEL_ARG(*key2); - if (key2_cpy) + if (!key2_cpy) return 0; key2= key2_cpy; } @@ -9621,7 +9625,7 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2) Move on to next range in key2 */ key2->increment_use_count(-1); // Free not used tree - key2=key2->next; + key2=key2_next; continue; } else