Fixed the bug mdev-11574.

Do not build an index merge of two indexes when one index is
an infix of the other index.

4 files changed, 246 insertions, 8 deletions

diff --git a/mysql-test/r/range_vs_index_merge.result b/mysql-test/r/range_vs_index_merge.result
index 6813c40a5cf..bc46a4fdd0b 100644
--- a/mysql-test/r/range_vs_index_merge.result
+++ b/mysql-test/r/range_vs_index_merge.result
@@ -1807,4 +1807,85 @@ id	state	capital
 7	Pennsylvania	Harrisburg
 8	Virginia	Richmond
 DROP TABLE t1;
+#
+# mdev-11574: do not build index merge of two indexes when
+#             one index is an infix of the other index
+#
+set names utf8;
+CREATE DATABASE world;
+use world;
+CREATE TABLE Country (
+Code char(3) NOT NULL default '',
+Name char(52) NOT NULL default '',
+SurfaceArea float(10,2) NOT NULL default '0.00',
+Population int(11) NOT NULL default '0',
+Capital int(11) default NULL,
+PRIMARY KEY  (Code),
+UNIQUE INDEX (Name)
+);
+CREATE TABLE City (
+ID int(11) NOT NULL auto_increment,
+Name char(35) NOT NULL default '',
+Country char(3) NOT NULL default '',
+Population int(11) NOT NULL default '0',
+PRIMARY KEY  (ID),
+INDEX (Population),
+INDEX (Country) 
+);
+CREATE TABLE CountryLanguage (
+Country char(3) NOT NULL default '',
+Language char(30) NOT NULL default '',
+Percentage float(3,1) NOT NULL default '0.0',
+PRIMARY KEY  (Country, Language),
+INDEX (Percentage)
+);
+DROP INDEX Country ON City;
+CREATE INDEX CountryName ON City(Country,Name);
+CREATE INDEX Name ON City(Name);
+select * from City
+where
+Country='FIN' AND Name IN ('Lahti','Imatra') OR
+Country='RUS' AND Name IN ('St Petersburg', 'Moscow') OR
+Country='SWE' AND Name IN ('Stockholm', 'Uppsala') OR
+Country='DEU' AND Name IN ('Berlin', 'Bonn') OR
+Country='BEL' AND Name IN ('Antwerpen', 'Gent') OR
+Country='PRT' AND Name IN ('Braga', 'Porto') OR
+Country='FRA' AND Name IN ('Paris', 'Marcel') OR
+Country='POL' AND Name IN ('Warszawa', 'Wroclaw') OR
+Country='NOR' AND Name IN ('Oslo', 'Bergen') OR
+Country='ITA' AND Name IN ('Napoli', 'Venezia');
+ID	Name	Country	Population
+175	Antwerpen	BEL	446525
+176	Gent	BEL	224180
+3068	Berlin	DEU	3386667
+3087	Bonn	DEU	301048
+3242	Lahti	FIN	96921
+2974	Paris	FRA	2125246
+1466	Napoli	ITA	1002619
+1474	Venezia	ITA	277305
+2808	Bergen	NOR	230948
+2807	Oslo	NOR	508726
+2928	Warszawa	POL	1615369
+2931	Wroclaw	POL	636765
+2918	Braga	PRT	90535
+2915	Porto	PRT	273060
+3580	Moscow	RUS	8389200
+3581	St Petersburg	RUS	4694000
+3048	Stockholm	SWE	750348
+3051	Uppsala	SWE	189569
+explain select * from City
+where
+Country='FIN' AND Name IN ('Lahti','Imatra') OR
+Country='RUS' AND Name IN ('St Petersburg', 'Moscow') OR
+Country='SWE' AND Name IN ('Stockholm', 'Uppsala') OR
+Country='DEU' AND Name IN ('Berlin', 'Bonn') OR
+Country='BEL' AND Name IN ('Antwerpen', 'Gent') OR
+Country='PRT' AND Name IN ('Braga', 'Porto') OR
+Country='FRA' AND Name IN ('Paris', 'Marcel') OR
+Country='POL' AND Name IN ('Warszawa', 'Wroclaw') OR
+Country='NOR' AND Name IN ('Oslo', 'Bergen') OR
+Country='ITA' AND Name IN ('Napoli', 'Venezia');
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	CountryName,Name	CountryName	38	NULL	22	Using index condition; Using where
+DROP DATABASE world;
 set session optimizer_switch='index_merge_sort_intersection=default';
diff --git a/mysql-test/r/range_vs_index_merge_innodb.result b/mysql-test/r/range_vs_index_merge_innodb.result
index 13fbc0ac3ef..a6ec200538d 100644
--- a/mysql-test/r/range_vs_index_merge_innodb.result
+++ b/mysql-test/r/range_vs_index_merge_innodb.result
@@ -1808,5 +1808,86 @@ id	state	capital
 7	Pennsylvania	Harrisburg
 8	Virginia	Richmond
 DROP TABLE t1;
+#
+# mdev-11574: do not build index merge of two indexes when
+#             one index is an infix of the other index
+#
+set names utf8;
+CREATE DATABASE world;
+use world;
+CREATE TABLE Country (
+Code char(3) NOT NULL default '',
+Name char(52) NOT NULL default '',
+SurfaceArea float(10,2) NOT NULL default '0.00',
+Population int(11) NOT NULL default '0',
+Capital int(11) default NULL,
+PRIMARY KEY  (Code),
+UNIQUE INDEX (Name)
+);
+CREATE TABLE City (
+ID int(11) NOT NULL auto_increment,
+Name char(35) NOT NULL default '',
+Country char(3) NOT NULL default '',
+Population int(11) NOT NULL default '0',
+PRIMARY KEY  (ID),
+INDEX (Population),
+INDEX (Country) 
+);
+CREATE TABLE CountryLanguage (
+Country char(3) NOT NULL default '',
+Language char(30) NOT NULL default '',
+Percentage float(3,1) NOT NULL default '0.0',
+PRIMARY KEY  (Country, Language),
+INDEX (Percentage)
+);
+DROP INDEX Country ON City;
+CREATE INDEX CountryName ON City(Country,Name);
+CREATE INDEX Name ON City(Name);
+select * from City
+where
+Country='FIN' AND Name IN ('Lahti','Imatra') OR
+Country='RUS' AND Name IN ('St Petersburg', 'Moscow') OR
+Country='SWE' AND Name IN ('Stockholm', 'Uppsala') OR
+Country='DEU' AND Name IN ('Berlin', 'Bonn') OR
+Country='BEL' AND Name IN ('Antwerpen', 'Gent') OR
+Country='PRT' AND Name IN ('Braga', 'Porto') OR
+Country='FRA' AND Name IN ('Paris', 'Marcel') OR
+Country='POL' AND Name IN ('Warszawa', 'Wroclaw') OR
+Country='NOR' AND Name IN ('Oslo', 'Bergen') OR
+Country='ITA' AND Name IN ('Napoli', 'Venezia');
+ID	Name	Country	Population
+175	Antwerpen	BEL	446525
+176	Gent	BEL	224180
+3068	Berlin	DEU	3386667
+3087	Bonn	DEU	301048
+3242	Lahti	FIN	96921
+2974	Paris	FRA	2125246
+1466	Napoli	ITA	1002619
+1474	Venezia	ITA	277305
+2808	Bergen	NOR	230948
+2807	Oslo	NOR	508726
+2928	Warszawa	POL	1615369
+2931	Wroclaw	POL	636765
+2918	Braga	PRT	90535
+2915	Porto	PRT	273060
+3580	Moscow	RUS	8389200
+3581	St Petersburg	RUS	4694000
+3048	Stockholm	SWE	750348
+3051	Uppsala	SWE	189569
+explain select * from City
+where
+Country='FIN' AND Name IN ('Lahti','Imatra') OR
+Country='RUS' AND Name IN ('St Petersburg', 'Moscow') OR
+Country='SWE' AND Name IN ('Stockholm', 'Uppsala') OR
+Country='DEU' AND Name IN ('Berlin', 'Bonn') OR
+Country='BEL' AND Name IN ('Antwerpen', 'Gent') OR
+Country='PRT' AND Name IN ('Braga', 'Porto') OR
+Country='FRA' AND Name IN ('Paris', 'Marcel') OR
+Country='POL' AND Name IN ('Warszawa', 'Wroclaw') OR
+Country='NOR' AND Name IN ('Oslo', 'Bergen') OR
+Country='ITA' AND Name IN ('Napoli', 'Venezia');
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	CountryName,Name	CountryName	38	NULL	20	Using index condition; Using where
+DROP DATABASE world;
 set session optimizer_switch='index_merge_sort_intersection=default';
 SET SESSION STORAGE_ENGINE=DEFAULT;
diff --git a/mysql-test/t/range_vs_index_merge.test b/mysql-test/t/range_vs_index_merge.test
index 5d12d46c9e9..84b87579e85 100644
--- a/mysql-test/t/range_vs_index_merge.test
+++ b/mysql-test/t/range_vs_index_merge.test
@@ -1241,6 +1241,59 @@ WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9
 
 DROP TABLE t1;
 
+--echo #
+--echo # mdev-11574: do not build index merge of two indexes when
+--echo #             one index is an infix of the other index
+--echo #
+
+set names utf8;
+
+CREATE DATABASE world;
+
+use world;
+
+--source include/world_schema.inc
+
+--disable_query_log
+--disable_result_log
+--disable_warnings
+--source include/world.inc
+--enable_warnings
+--enable_result_log
+--enable_query_log
+
+DROP INDEX Country ON City;
+CREATE INDEX CountryName ON City(Country,Name);
+CREATE INDEX Name ON City(Name);
+
+--disable_query_log
+--disable_result_log
+--disable_warnings
+ANALYZE TABLE City;
+--enable_warnings
+--enable_result_log
+--enable_query_log
+
+let $q=
+select * from City
+where
+ Country='FIN' AND Name IN ('Lahti','Imatra') OR
+ Country='RUS' AND Name IN ('St Petersburg', 'Moscow') OR
+ Country='SWE' AND Name IN ('Stockholm', 'Uppsala') OR
+ Country='DEU' AND Name IN ('Berlin', 'Bonn') OR
+ Country='BEL' AND Name IN ('Antwerpen', 'Gent') OR
+ Country='PRT' AND Name IN ('Braga', 'Porto') OR
+ Country='FRA' AND Name IN ('Paris', 'Marcel') OR
+ Country='POL' AND Name IN ('Warszawa', 'Wroclaw') OR
+ Country='NOR' AND Name IN ('Oslo', 'Bergen') OR
+ Country='ITA' AND Name IN ('Napoli', 'Venezia');
+
+eval $q;
+eval explain $q;
+
+
+DROP DATABASE world;
+
 #the following command must be the last one in the file
 set session optimizer_switch='index_merge_sort_intersection=default';
 
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index 3563058282b..7b29e8b2b7b 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -8991,6 +8991,34 @@ bool sel_trees_can_be_ored(RANGE_OPT_PARAM* param,
 }
 
 /*
+  Check whether the key parts inf_init..inf_end-1 of one index can compose
+  an infix for the key parts key_init..key_end-1 of another index
+*/
+
+static
+bool is_key_infix(KEY_PART *key_init, KEY_PART *key_end,
+                  KEY_PART *inf_init, KEY_PART *inf_end)
+{
+  KEY_PART *key_part, *inf_part;
+  for (key_part= key_init; key_part < key_end; key_part++)
+  {
+    if (key_part->field->eq(inf_init->field))
+      break;
+  }
+  if (key_part == key_end)
+    return false;
+  for (key_part++, inf_part= inf_init + 1;
+       key_part < key_end && inf_part < inf_end;
+       key_part++, inf_part++)
+  { 
+    if (!key_part->field->eq(inf_part->field))
+      return false;
+  }
+  return inf_part == inf_end;
+}
+
+
+/*
   Check whether range parts of two trees must be ored for some indexes
 
   SYNOPSIS
@@ -9046,14 +9074,9 @@ bool sel_trees_must_be_ored(RANGE_OPT_PARAM* param,
       
       KEY_PART *key2_init= param->key[idx2]+tree2->keys[idx2]->part;
       KEY_PART *key2_end= param->key[idx2]+tree2->keys[idx2]->max_part_no;
-      KEY_PART *part1, *part2;
-      for (part1= key1_init, part2= key2_init;
-           part1 < key1_end && part2 < key2_end;
-           part1++, part2++)
-      { 
-        if (!part1->field->eq(part2->field))
-          DBUG_RETURN(FALSE);
-      }
+      if (!is_key_infix(key1_init, key1_end, key2_init, key2_end) &&
+          !is_key_infix(key2_init, key2_end, key1_init, key1_end))
+        DBUG_RETURN(FALSE);
     }
   }