MDEV-27262 Unexpected index intersection with full index scan for an index

If when extracting a range condition for an index from the WHERE condition
Range Optimizer sees that the range condition covers the whole index then
such condition should be discarded because it cannot be used in any range
scan. In some cases Range Optimizer really does it, but there remained some
conditions for which it was not done. As a result the optimizer could
produce index merge plans with the full index scan for one of the indexes
participating in the index merge.
This could be observed in one of the test cases from index_merge1.inc
where a plan with index_merge_sort_union was produced and in the test case
reported for this bug where a plan with index_merge_sort_intersect was
produced. In both cases one of two index scans participating in index merge
ran over the whole index.
The patch slightly changes the original above mentioned test case from
index_merge1.inc to be able to produce an intended plan employing
index_merge_sort_union. The original query was left to show that index
merge is not used for it anymore.
It should be noted that for the plan with index_merge_sort_intersect could
be chosen for execution only due to a defect in the InnoDB code that
returns wrong estimates for the cardinality of big ranges.

This bug led to serious problems in 10.4+ where the optimization using
Rowid filters is employed (see mdev-26446).

Approved by Sergey Petrunia <sergey@mariadb.com>

5 files changed, 243 insertions, 6 deletions

diff --git a/mysql-test/include/index_merge1.inc b/mysql-test/include/index_merge1.inc
index b168a767d7c..ebadb5077ae 100644
--- a/mysql-test/include/index_merge1.inc
+++ b/mysql-test/include/index_merge1.inc
@@ -150,12 +150,22 @@ explain select * from t0 where
     (((key3 <7 and key7 < 6) or key5 < 2) and (key5 < 5 or key6 < 6));
 
 explain select * from t0 where
-    ((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
+    ((key3 < 4 or key5 < 4) and (key1 < 4 or key2 < 4))
   or
     ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
 
 explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
-    ((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
+    ((key3 < 4 or key5 < 4) and (key1 < 4 or key2 < 4))
+  or
+    ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
+
+explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
+    ((key3 < 5 or key5 < 4) and (key1 < 4 or key2 < 4))
+  or
+    ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
+
+explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
+    ((key3 < 10 or key5 < 4) and (key1 < 4 or key2 < 4))
   or
     ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
 
diff --git a/mysql-test/r/index_merge_myisam.result b/mysql-test/r/index_merge_myisam.result
index 5a23092457d..a3e9e4f5881 100644
--- a/mysql-test/r/index_merge_myisam.result
+++ b/mysql-test/r/index_merge_myisam.result
@@ -173,17 +173,29 @@ or
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6,i7	i3,i5	4,4	NULL	11	Using sort_union(i3,i5); Using where
 explain select * from t0 where
-((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
+((key3 < 4 or key5 < 4) and (key1 < 4 or key2 < 4))
 or
 ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t0	ALL	i1,i2,i3,i5,i6	NULL	NULL	NULL	1024	Using where
 explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
-((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
+((key3 < 4 or key5 < 4) and (key1 < 4 or key2 < 4))
+or
+((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6	i3,i5	4,4	NULL	1024	Using sort_union(i3,i5); Using where
+explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
+((key3 < 5 or key5 < 4) and (key1 < 4 or key2 < 4))
 or
 ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6	i3,i5	0,4	NULL	1024	Using sort_union(i3,i5); Using where
+1	SIMPLE	t0	ALL	i1,i2,i3,i5,i6	NULL	NULL	NULL	1024	Using where
+explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
+((key3 < 10 or key5 < 4) and (key1 < 4 or key2 < 4))
+or
+((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t0	ALL	i1,i2,i3,i5,i6	NULL	NULL	NULL	1024	Using where
 select * from t0 where key1 < 5 or key8 < 4 order by key1;
 key1	key2	key3	key4	key5	key6	key7	key8
 1	1	1	1	1	1	1	1023
diff --git a/mysql-test/r/range_innodb.result b/mysql-test/r/range_innodb.result
index f2349f26571..df111bc05be 100644
--- a/mysql-test/r/range_innodb.result
+++ b/mysql-test/r/range_innodb.result
@@ -108,3 +108,108 @@ DROP TABLE t0,t1;
 SET @@GLOBAL.debug_dbug = @saved_dbug;
 set @@optimizer_switch= @optimizer_switch_save;
 # End of 10.1 tests
+#
+# MDEV-27262: Index intersection with full scan over an index
+#
+CREATE TABLE t1 (
+id int(10) unsigned NOT NULL AUTO_INCREMENT,
+p char(32) DEFAULT NULL,
+es tinyint(3) unsigned NOT NULL DEFAULT 0,
+er tinyint(3) unsigned NOT NULL DEFAULT 0,
+x mediumint(8) unsigned NOT NULL DEFAULT 0,
+PRIMARY KEY (id),
+INDEX es (es),
+INDEX x (x),
+INDEX er (er,x),
+INDEX p (p)
+) ENGINE=InnoDB DEFAULT CHARSET=latin1;
+insert into t1(es,er) select 0, 1 from seq_1_to_45;
+insert into t1(es,er) select 0, 2 from seq_1_to_49;
+insert into t1(es,er) select 0, 3 from seq_1_to_951;
+insert into t1(es,er) select 0, 3 from seq_1_to_1054;
+insert into t1(es,er) select 0, 6 from seq_1_to_25;
+insert into t1(es,er) select 0, 11 from seq_1_to_1;
+insert into t1(es,er) select 1, 1 from seq_1_to_45;
+insert into t1(es,er) select 1, 2 from seq_1_to_16;
+insert into t1(es,er) select 1, 3 from seq_1_to_511;
+insert into t1(es,er) select 1, 4 from seq_1_to_687;
+insert into t1(es,er) select 1, 6 from seq_1_to_50;
+insert into t1(es,er) select 1, 7 from seq_1_to_4;
+insert into t1(es,er) select 1, 11 from seq_1_to_1;
+insert into t1(es,er) select 2, 1 from seq_1_to_82;
+insert into t1(es,er) select 2, 2 from seq_1_to_82;
+insert into t1(es,er) select 2, 3 from seq_1_to_1626;
+insert into t1(es,er) select 2, 4 from seq_1_to_977;
+insert into t1(es,er) select 2, 6 from seq_1_to_33;
+insert into t1(es,er) select 2, 11 from seq_1_to_1;
+insert into t1(es,er) select 3, 1 from seq_1_to_245;
+insert into t1(es,er) select 3, 2 from seq_1_to_81;
+insert into t1(es,er) select 3, 3 from seq_1_to_852;
+insert into t1(es,er) select 3, 4 from seq_1_to_2243;
+insert into t1(es,er) select 3, 6 from seq_1_to_44;
+insert into t1(es,er) select 3, 11 from seq_1_to_1;
+insert into t1(es,er) select 4, 1 from seq_1_to_91;
+insert into t1(es,er) select 4, 2 from seq_1_to_83;
+insert into t1(es,er) select 4, 3 from seq_1_to_297;
+insert into t1(es,er) select 4, 4 from seq_1_to_2456;
+insert into t1(es,er) select 4, 6 from seq_1_to_19;
+insert into t1(es,er) select 4, 11 from seq_1_to_1;
+update t1 set p='foobar';
+update t1 set x=0;
+set @save_isp=@@innodb_stats_persistent;
+set global innodb_stats_persistent= 1;
+analyze table t1;
+Table	Op	Msg_type	Msg_text
+test.t1	analyze	status	OK
+set optimizer_switch='index_merge_sort_intersection=on';
+SELECT * FROM t1
+WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
+id	p	es	er	x
+14645	foobar	4	4	0
+14646	foobar	4	4	0
+EXPLAIN EXTENDED SELECT * FROM t1
+WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	range	es,er,p	es	1	NULL	#	100.00	Using index condition; Using where
+Warnings:
+Note	1003	select `test`.`t1`.`id` AS `id`,`test`.`t1`.`p` AS `p`,`test`.`t1`.`es` AS `es`,`test`.`t1`.`er` AS `er`,`test`.`t1`.`x` AS `x` from `test`.`t1` where (`test`.`t1`.`p` = 'foo' and `test`.`t1`.`er` <> 4 or `test`.`t1`.`er` = 4) and `test`.`t1`.`es` >= 4 limit 2
+set optimizer_switch='index_merge_sort_intersection=off';
+SELECT * FROM t1
+WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
+id	p	es	er	x
+14645	foobar	4	4	0
+14646	foobar	4	4	0
+EXPLAIN EXTENDED SELECT * FROM t1
+WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	range	es,er,p	es	1	NULL	#	100.00	Using index condition; Using where
+Warnings:
+Note	1003	select `test`.`t1`.`id` AS `id`,`test`.`t1`.`p` AS `p`,`test`.`t1`.`es` AS `es`,`test`.`t1`.`er` AS `er`,`test`.`t1`.`x` AS `x` from `test`.`t1` where (`test`.`t1`.`p` = 'foo' and `test`.`t1`.`er` <> 4 or `test`.`t1`.`er` = 4) and `test`.`t1`.`es` >= 4 limit 2
+set optimizer_switch='index_merge_sort_intersection=on';
+SELECT * FROM t1
+WHERE ((p = 'foo' AND er < 6) OR er >=2 ) AND (es >= 4) LIMIT 2;
+id	p	es	er	x
+14007	foobar	4	2	0
+14008	foobar	4	2	0
+EXPLAIN EXTENDED SELECT * FROM t1
+WHERE ((p = 'foo' AND er < 6) OR er >=2 ) AND (es >= 4) LIMIT 2;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	range	es,er,p	es	1	NULL	#	100.00	Using index condition; Using where
+Warnings:
+Note	1003	select `test`.`t1`.`id` AS `id`,`test`.`t1`.`p` AS `p`,`test`.`t1`.`es` AS `es`,`test`.`t1`.`er` AS `er`,`test`.`t1`.`x` AS `x` from `test`.`t1` where (`test`.`t1`.`p` = 'foo' and `test`.`t1`.`er` < 6 or `test`.`t1`.`er` >= 2) and `test`.`t1`.`es` >= 4 limit 2
+set optimizer_switch='index_merge_sort_intersection=off';
+SELECT * FROM t1
+WHERE ((p = 'foo' AND er < 6) OR er >=2 ) AND (es >= 4) LIMIT 2;
+id	p	es	er	x
+14007	foobar	4	2	0
+14008	foobar	4	2	0
+EXPLAIN EXTENDED SELECT * FROM t1
+WHERE ((p = 'foo' AND er < 6) OR er >=2 ) AND (es >= 4) LIMIT 2;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	range	es,er,p	es	1	NULL	#	100.00	Using index condition; Using where
+Warnings:
+Note	1003	select `test`.`t1`.`id` AS `id`,`test`.`t1`.`p` AS `p`,`test`.`t1`.`es` AS `es`,`test`.`t1`.`er` AS `er`,`test`.`t1`.`x` AS `x` from `test`.`t1` where (`test`.`t1`.`p` = 'foo' and `test`.`t1`.`er` < 6 or `test`.`t1`.`er` >= 2) and `test`.`t1`.`es` >= 4 limit 2
+set optimizer_switch='index_merge_sort_intersection=default';
+set global innodb_stats_persistent= @save_isp;
+DROP TABLE t1;
+# End of 10.2 tests
diff --git a/mysql-test/t/range_innodb.test b/mysql-test/t/range_innodb.test
index 428e5c26e5c..b8a6a7c960c 100644
--- a/mysql-test/t/range_innodb.test
+++ b/mysql-test/t/range_innodb.test
@@ -116,3 +116,96 @@ SET @@GLOBAL.debug_dbug = @saved_dbug;
 set @@optimizer_switch= @optimizer_switch_save;
 
 --echo # End of 10.1 tests
+
+--echo #
+--echo # MDEV-27262: Index intersection with full scan over an index
+--echo #
+
+--source include/have_sequence.inc
+
+CREATE TABLE t1 (
+  id int(10) unsigned NOT NULL AUTO_INCREMENT,
+  p char(32) DEFAULT NULL,
+  es tinyint(3) unsigned NOT NULL DEFAULT 0,
+  er tinyint(3) unsigned NOT NULL DEFAULT 0,
+  x mediumint(8) unsigned NOT NULL DEFAULT 0,
+  PRIMARY KEY (id),
+  INDEX es (es),
+  INDEX x (x),
+  INDEX er (er,x),
+  INDEX p (p)
+) ENGINE=InnoDB DEFAULT CHARSET=latin1;
+
+insert into t1(es,er) select 0, 1 from seq_1_to_45;
+insert into t1(es,er) select 0, 2 from seq_1_to_49;
+insert into t1(es,er) select 0, 3 from seq_1_to_951;
+insert into t1(es,er) select 0, 3 from seq_1_to_1054;
+insert into t1(es,er) select 0, 6 from seq_1_to_25;
+insert into t1(es,er) select 0, 11 from seq_1_to_1;
+insert into t1(es,er) select 1, 1 from seq_1_to_45;
+insert into t1(es,er) select 1, 2 from seq_1_to_16;
+insert into t1(es,er) select 1, 3 from seq_1_to_511;
+insert into t1(es,er) select 1, 4 from seq_1_to_687;
+insert into t1(es,er) select 1, 6 from seq_1_to_50;
+insert into t1(es,er) select 1, 7 from seq_1_to_4;
+insert into t1(es,er) select 1, 11 from seq_1_to_1;
+insert into t1(es,er) select 2, 1 from seq_1_to_82;
+insert into t1(es,er) select 2, 2 from seq_1_to_82;
+insert into t1(es,er) select 2, 3 from seq_1_to_1626;
+insert into t1(es,er) select 2, 4 from seq_1_to_977;
+insert into t1(es,er) select 2, 6 from seq_1_to_33;
+insert into t1(es,er) select 2, 11 from seq_1_to_1;
+insert into t1(es,er) select 3, 1 from seq_1_to_245;
+insert into t1(es,er) select 3, 2 from seq_1_to_81;
+insert into t1(es,er) select 3, 3 from seq_1_to_852;
+insert into t1(es,er) select 3, 4 from seq_1_to_2243;
+insert into t1(es,er) select 3, 6 from seq_1_to_44;
+insert into t1(es,er) select 3, 11 from seq_1_to_1;
+insert into t1(es,er) select 4, 1 from seq_1_to_91;
+insert into t1(es,er) select 4, 2 from seq_1_to_83;
+insert into t1(es,er) select 4, 3 from seq_1_to_297;
+insert into t1(es,er) select 4, 4 from seq_1_to_2456;
+insert into t1(es,er) select 4, 6 from seq_1_to_19;
+insert into t1(es,er) select 4, 11 from seq_1_to_1;
+update t1 set p='foobar';
+update t1 set x=0;
+set @save_isp=@@innodb_stats_persistent;
+set global innodb_stats_persistent= 1;
+analyze table t1;
+
+let $q=
+SELECT * FROM t1
+  WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
+
+set optimizer_switch='index_merge_sort_intersection=on';
+eval $q;
+--replace_column 9 #
+eval EXPLAIN EXTENDED $q;
+
+set optimizer_switch='index_merge_sort_intersection=off';
+# execution of $q and explain for it led to an assertion failure in 10.4
+# (with the optimizer switch rowid_filter set to 'on')
+eval $q;
+--replace_column 9 #
+eval EXPLAIN EXTENDED $q;
+
+let $q=
+SELECT * FROM t1
+  WHERE ((p = 'foo' AND er < 6) OR er >=2 ) AND (es >= 4) LIMIT 2;
+
+set optimizer_switch='index_merge_sort_intersection=on';
+eval $q;
+--replace_column 9 #
+eval EXPLAIN EXTENDED $q;
+
+set optimizer_switch='index_merge_sort_intersection=off';
+eval $q;
+--replace_column 9 #
+eval EXPLAIN EXTENDED $q;
+
+set optimizer_switch='index_merge_sort_intersection=default';
+
+set global innodb_stats_persistent= @save_isp;
+DROP TABLE t1;
+
+--echo # End of 10.2 tests
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index f3f184367c9..89ee8cf98e1 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -9329,7 +9329,7 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
 
   uint max_part_no= MY_MAX(key1->max_part_no, key2->max_part_no);
 
-  for (key2=key2->first(); key2; )
+  for (key2=key2->first(); ; )
   {
     /*
       key1 consists of one or more ranges. tmp is the range currently
@@ -9343,6 +9343,16 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
                   ^
                   tmp
     */
+    if (key1->min_flag & NO_MIN_RANGE &&
+        key1->max_flag & NO_MAX_RANGE)
+    {
+      if (key1->maybe_flag)
+        return new SEL_ARG(SEL_ARG::MAYBE_KEY);
+      return 0;   // Always true OR
+    }
+    if (!key2)
+      break;
+
     SEL_ARG *tmp=key1->find_range(key2);
 
     /*
@@ -9413,6 +9423,13 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
         key2->copy_min(tmp);
         if (!(key1=key1->tree_delete(tmp)))
         {                                       // Only one key in tree
+          if (key2->min_flag & NO_MIN_RANGE &&
+              key2->max_flag & NO_MAX_RANGE)
+          {
+            if (key2->maybe_flag)
+              return new SEL_ARG(SEL_ARG::MAYBE_KEY);
+            return 0;   // Always true OR
+          }
           key1=key2;
           key1->make_root();
           key2=key2_next;