Fixed bug mdev-585 (LP bug #637962)

If, when executing a query with ORDER BY col LIMIT n, the optimizer chose
an index-merge scan to access the table containing col while there existed
an index defined over col then optimizer did not consider the possibility
of using an alternative range scan by this index to avoid filesort. This
could cause a performance degradation if the optimizer flag index_merge was
set up to 'on'.

4 files changed, 356 insertions, 6 deletions

diff --git a/mysql-test/r/range_vs_index_merge.result b/mysql-test/r/range_vs_index_merge.result
index faaa6d2429e..dfd00204c95 100644
--- a/mysql-test/r/range_vs_index_merge.result
+++ b/mysql-test/r/range_vs_index_merge.result
@@ -1221,6 +1221,150 @@ Lugansk	UKR	469000
 Seattle	USA	563374
 Caracas	VEN	1975294
 set optimizer_switch=@save_optimizer_switch;
+# 
+# Bug mdev-585: range vs index-merge with ORDER BY ... LIMIT n
+# (LP bug #637962)
+# 
+DROP INDEX CountryPopulation ON City;
+DROP INDEX CountryName ON City;
+DROP INDEX CityName on City;
+CREATE INDEX Name ON City(Name);
+CREATE INDEX Population ON City(Population);
+EXPLAIN 
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	index_merge	Country,Name,Population	Name,Country	35,3	NULL	#	Using sort_union(Name,Country); Using where
+FLUSH STATUS;
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000);
+ID	Name	Country	Population
+384	Cabo Frio	BRA	119503
+387	Camaragibe	BRA	118968
+403	Catanduva	BRA	107761
+412	Cachoeirinha	BRA	103240
+508	Watford	GBR	113080
+509	Ipswich	GBR	114000
+510	Slough	GBR	112000
+511	Exeter	GBR	111000
+512	Cheltenham	GBR	106000
+513	Gloucester	GBR	107000
+514	Saint Helens	GBR	106293
+515	Sutton Coldfield	GBR	106001
+516	York	GBR	104425
+517	Oldham	GBR	103931
+518	Basildon	GBR	100924
+519	Worthing	GBR	100000
+635	Mallawi	EGY	119283
+636	Bilbays	EGY	113608
+637	Mit Ghamr	EGY	101801
+638	al-Arish	EGY	100447
+701	Tarragona	ESP	113016
+702	Lleida (Lérida)	ESP	112207
+703	Jaén	ESP	109247
+704	Ourense (Orense)	ESP	109120
+705	Mataró	ESP	104095
+706	Algeciras	ESP	103106
+707	Marbella	ESP	101144
+759	Gonder	ETH	112249
+869	Cabuyao	PHL	106630
+870	Calapan	PHL	105910
+873	Cauayan	PHL	103952
+903	Serekunda	GMB	102600
+909	Sohumi	GEO	111700
+913	Tema	GHA	109975
+914	Sekondi-Takoradi	GHA	103653
+924	Villa Nueva	GTM	101295
+1844	Cape Breton	CAN	114733
+1847	Cambridge	CAN	109186
+2406	Herakleion	GRC	116178
+2407	Kallithea	GRC	114233
+2408	Larisa	GRC	113090
+2908	Cajamarca	PER	108009
+3002	Besançon	FRA	117733
+3003	Caen	FRA	113987
+3004	Orléans	FRA	113126
+3005	Mulhouse	FRA	110359
+3006	Rouen	FRA	106592
+3007	Boulogne-Billancourt	FRA	106367
+3008	Perpignan	FRA	105115
+3009	Nancy	FRA	103605
+3411	Ceyhan	TUR	102412
+3567	Carúpano	VEN	119639
+3568	Catia La Mar	VEN	117012
+3571	Calabozo	VEN	107146
+3786	Cam Ranh	VNM	114041
+3792	Tartu	EST	101246
+4002	Carrollton	USA	109576
+4027	Cape Coral	USA	102286
+4032	Cambridge	USA	101355
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	2
+Handler_read_next	385
+Handler_read_prev	0
+Handler_read_rnd	377
+Handler_read_rnd_deleted	0
+Handler_read_rnd_next	0
+EXPLAIN 
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Country,Name,Population	Population	4	NULL	#	Using where
+FLUSH STATUS;
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+ID	Name	Country	Population
+519	Worthing	GBR	100000
+638	al-Arish	EGY	100447
+518	Basildon	GBR	100924
+707	Marbella	ESP	101144
+3792	Tartu	EST	101246
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	1
+Handler_read_next	59
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_deleted	0
+Handler_read_rnd_next	0
+set optimizer_switch='index_merge=off';
+EXPLAIN 
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Country,Name,Population	Population	4	NULL	#	Using index condition; Using where
+FLUSH STATUS;
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+ID	Name	Country	Population
+519	Worthing	GBR	100000
+638	al-Arish	EGY	100447
+518	Basildon	GBR	100924
+707	Marbella	ESP	101144
+3792	Tartu	EST	101246
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	1
+Handler_read_next	59
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_deleted	0
+Handler_read_rnd_next	0
+set optimizer_switch=@save_optimizer_switch;
 DROP DATABASE world;
 use test;
 CREATE TABLE t1 (
diff --git a/mysql-test/r/range_vs_index_merge_innodb.result b/mysql-test/r/range_vs_index_merge_innodb.result
index df3a2af0753..4970900a061 100644
--- a/mysql-test/r/range_vs_index_merge_innodb.result
+++ b/mysql-test/r/range_vs_index_merge_innodb.result
@@ -1222,6 +1222,150 @@ Lugansk	UKR	469000
 Seattle	USA	563374
 Caracas	VEN	1975294
 set optimizer_switch=@save_optimizer_switch;
+# 
+# Bug mdev-585: range vs index-merge with ORDER BY ... LIMIT n
+# (LP bug #637962)
+# 
+DROP INDEX CountryPopulation ON City;
+DROP INDEX CountryName ON City;
+DROP INDEX CityName on City;
+CREATE INDEX Name ON City(Name);
+CREATE INDEX Population ON City(Population);
+EXPLAIN 
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	index_merge	Country,Name,Population	Name,Country	35,3	NULL	#	Using sort_union(Name,Country); Using where
+FLUSH STATUS;
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000);
+ID	Name	Country	Population
+384	Cabo Frio	BRA	119503
+387	Camaragibe	BRA	118968
+403	Catanduva	BRA	107761
+412	Cachoeirinha	BRA	103240
+508	Watford	GBR	113080
+509	Ipswich	GBR	114000
+510	Slough	GBR	112000
+511	Exeter	GBR	111000
+512	Cheltenham	GBR	106000
+513	Gloucester	GBR	107000
+514	Saint Helens	GBR	106293
+515	Sutton Coldfield	GBR	106001
+516	York	GBR	104425
+517	Oldham	GBR	103931
+518	Basildon	GBR	100924
+519	Worthing	GBR	100000
+635	Mallawi	EGY	119283
+636	Bilbays	EGY	113608
+637	Mit Ghamr	EGY	101801
+638	al-Arish	EGY	100447
+701	Tarragona	ESP	113016
+702	Lleida (Lérida)	ESP	112207
+703	Jaén	ESP	109247
+704	Ourense (Orense)	ESP	109120
+705	Mataró	ESP	104095
+706	Algeciras	ESP	103106
+707	Marbella	ESP	101144
+759	Gonder	ETH	112249
+869	Cabuyao	PHL	106630
+870	Calapan	PHL	105910
+873	Cauayan	PHL	103952
+903	Serekunda	GMB	102600
+909	Sohumi	GEO	111700
+913	Tema	GHA	109975
+914	Sekondi-Takoradi	GHA	103653
+924	Villa Nueva	GTM	101295
+1844	Cape Breton	CAN	114733
+1847	Cambridge	CAN	109186
+2406	Herakleion	GRC	116178
+2407	Kallithea	GRC	114233
+2408	Larisa	GRC	113090
+2908	Cajamarca	PER	108009
+3002	Besançon	FRA	117733
+3003	Caen	FRA	113987
+3004	Orléans	FRA	113126
+3005	Mulhouse	FRA	110359
+3006	Rouen	FRA	106592
+3007	Boulogne-Billancourt	FRA	106367
+3008	Perpignan	FRA	105115
+3009	Nancy	FRA	103605
+3411	Ceyhan	TUR	102412
+3567	Carúpano	VEN	119639
+3568	Catia La Mar	VEN	117012
+3571	Calabozo	VEN	107146
+3786	Cam Ranh	VNM	114041
+3792	Tartu	EST	101246
+4002	Carrollton	USA	109576
+4027	Cape Coral	USA	102286
+4032	Cambridge	USA	101355
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	2
+Handler_read_next	385
+Handler_read_prev	0
+Handler_read_rnd	377
+Handler_read_rnd_deleted	0
+Handler_read_rnd_next	0
+EXPLAIN 
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Country,Name,Population	Population	4	NULL	#	Using where
+FLUSH STATUS;
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+ID	Name	Country	Population
+519	Worthing	GBR	100000
+638	al-Arish	EGY	100447
+518	Basildon	GBR	100924
+707	Marbella	ESP	101144
+3792	Tartu	EST	101246
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	1
+Handler_read_next	59
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_deleted	0
+Handler_read_rnd_next	0
+set optimizer_switch='index_merge=off';
+EXPLAIN 
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Country,Name,Population	Population	4	NULL	#	Using index condition; Using where
+FLUSH STATUS;
+SELECT * FROM City
+WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+ID	Name	Country	Population
+519	Worthing	GBR	100000
+638	al-Arish	EGY	100447
+518	Basildon	GBR	100924
+707	Marbella	ESP	101144
+3792	Tartu	EST	101246
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	1
+Handler_read_next	59
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_deleted	0
+Handler_read_rnd_next	0
+set optimizer_switch=@save_optimizer_switch;
 DROP DATABASE world;
 use test;
 CREATE TABLE t1 (
diff --git a/mysql-test/t/range_vs_index_merge.test b/mysql-test/t/range_vs_index_merge.test
index 613a7cf5760..fb8fd778559 100755
--- a/mysql-test/t/range_vs_index_merge.test
+++ b/mysql-test/t/range_vs_index_merge.test
@@ -675,6 +675,64 @@ SELECT Name, Country, Population FROM City WHERE
 $cond;
 
 set optimizer_switch=@save_optimizer_switch;
+
+--echo # 
+--echo # Bug mdev-585: range vs index-merge with ORDER BY ... LIMIT n
+--echo # (LP bug #637962)
+--echo # 
+
+DROP INDEX CountryPopulation ON City;
+DROP INDEX CountryName ON City;
+DROP INDEX CityName on City;
+
+CREATE INDEX Name ON City(Name);
+CREATE INDEX Population ON City(Population);
+
+
+--replace_column 9 #
+EXPLAIN 
+SELECT * FROM City
+  WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+        AND (Population >= 100000 AND Population < 120000);
+FLUSH STATUS;
+SELECT * FROM City
+  WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+        AND (Population >= 100000 AND Population < 120000);
+SHOW STATUS LIKE 'Handler_read_%';
+
+
+--replace_column 9 #
+EXPLAIN 
+SELECT * FROM City
+  WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+        AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+
+FLUSH STATUS;
+SELECT * FROM City
+  WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+        AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+SHOW STATUS LIKE 'Handler_read_%';
+
+
+set optimizer_switch='index_merge=off';
+
+--replace_column 9 #
+EXPLAIN 
+SELECT * FROM City
+  WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+        AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+
+FLUSH STATUS;
+SELECT * FROM City
+  WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'H'))
+        AND (Population >= 100000 AND Population < 120000)
+ORDER BY Population LIMIT 5;
+SHOW STATUS LIKE 'Handler_read_%';
+
+set optimizer_switch=@save_optimizer_switch;
           
 
 DROP DATABASE world;
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 438cec61c6d..122c19ee73d 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -18079,15 +18079,18 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit_arg,
     */
   
     if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
-        quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT || 
+        quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT ||
         quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || 
         quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)
-      goto use_filesort;
-    ref_key=	   select->quick->index;
-    ref_key_parts= select->quick->used_key_parts;
+      ref_key= MAX_KEY;
+    else
+    {
+      ref_key= select->quick->index;
+      ref_key_parts= select->quick->used_key_parts;
+    }
   }
 
-  if (ref_key >= 0)
+  if (ref_key >= 0 && ref_key != MAX_KEY)
   {
     /*
       We come here when there is a REF key.
@@ -18229,7 +18232,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit_arg,
     else
       keys= usable_keys;
 
-    if (ref_key >= 0 && table->covering_keys.is_set(ref_key))
+    if (ref_key >= 0 && ref_key != MAX_KEY &&
+        table->covering_keys.is_set(ref_key))
       ref_key_quick_rows= table->quick_rows[ref_key];
 
     read_time= join->best_positions[tablenr].read_time;