MDEV-23811: With large number of indexes optimizer chooses an inefficient planmariadb-10.2.36

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 least 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.

5 files changed, 194 insertions, 4 deletions

diff --git a/mysql-test/r/range.result b/mysql-test/r/range.result
index b3324601e47..9ea0dc12a0b 100644
--- a/mysql-test/r/range.result
+++ b/mysql-test/r/range.result
@@ -3087,5 +3087,77 @@ set max_session_mem_used=@tmp_24117;
 deallocate prepare s;
 drop table t0,t1,t2;
 #
+# 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 d614a3397ee..55613261ce9 100644
--- a/mysql-test/r/range_mrr_icp.result
+++ b/mysql-test/r/range_mrr_icp.result
@@ -3099,6 +3099,78 @@ set max_session_mem_used=@tmp_24117;
 deallocate prepare s;
 drop table t0,t1,t2;
 #
+# 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 581f512768c..916c30bb770 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 f34ac2049e1..264f7c784ce 100644
--- a/mysql-test/t/range.test
+++ b/mysql-test/t/range.test
@@ -2142,6 +2142,48 @@ deallocate prepare s;
 
 drop table t0,t1,t2;
 --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 e933d2af355..798b1f284bc 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;
 }
 
 
@@ -9597,10 +9600,11 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
 
       if (!tmp->next_key_part)
       {
-        if (key2->use_count)
+	SEL_ARG *key2_next= key2->next;
+	if (key2_shared)
 	{
 	  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