Merge

33 files changed, 4032 insertions, 488 deletions

diff --git a/include/my_tree.h b/include/my_tree.h
index ceeb849ad0c..ca207932c73 100644
--- a/include/my_tree.h
+++ b/include/my_tree.h
@@ -31,6 +31,7 @@ extern "C" {
 #define tree_set_pointer(element,ptr) *((uchar **) (element+1))=((uchar*) (ptr))
 
 #define TREE_NO_DUPS 1
+#define TREE_ONLY_DUPS 2
 
 typedef enum { left_root_right, right_root_left } TREE_WALK;
 typedef uint32 element_count;
diff --git a/mysql-test/include/index_merge1.inc b/mysql-test/include/index_merge1.inc
index b3e61802dcf..dbe056cfdae 100644
--- a/mysql-test/include/index_merge1.inc
+++ b/mysql-test/include/index_merge1.inc
@@ -539,7 +539,7 @@ INSERT INTO t1 SELECT * FROM t1;
 INSERT INTO t1 SELECT * FROM t1;
 INSERT INTO t1 SELECT * FROM t1;
 INSERT INTO t1 SELECT * FROM t1;
-SET SESSION sort_buffer_size=1;
+SET SESSION sort_buffer_size=1024*8;
 EXPLAIN 
 SELECT * FROM t1 FORCE INDEX(a,b) WHERE a LIKE 'a%' OR b LIKE 'b%' 
   ORDER BY a,b;
diff --git a/mysql-test/r/index_intersect.result b/mysql-test/r/index_intersect.result
new file mode 100644
index 00000000000..fdb4885e071
--- /dev/null
+++ b/mysql-test/r/index_intersect.result
@@ -0,0 +1,1052 @@
+DROP TABLE IF EXISTS t1,t2,t3,t4;
+DROP DATABASE IF EXISTS world;
+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)
+);
+SELECT COUNT(*) FROM Country;
+COUNT(*)
+239
+SELECT COUNT(*) FROM City;
+COUNT(*)
+4079
+SELECT COUNT(*) FROM CountryLanguage;
+COUNT(*)
+984
+CREATE INDEX Name ON City(Name);
+SET SESSION optimizer_switch='index_merge_sort_intersection=on';
+SELECT COUNT(*) FROM City;
+COUNT(*)
+4079
+SELECT COUNT(*) FROM City WHERE Name LIKE 'C%';
+COUNT(*)
+281
+SELECT COUNT(*) FROM City WHERE Name LIKE 'M%';
+COUNT(*)
+301
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+COUNT(*)
+237
+SELECT COUNT(*) FROM City WHERE Population > 1500000;
+COUNT(*)
+129
+SELECT COUNT(*) FROM City WHERE Population > 300000;
+COUNT(*)
+1062
+SELECT COUNT(*) FROM City WHERE Population > 5000000;
+COUNT(*)
+24
+EXPLAIN
+SELECT * FROM City WHERE
+Name LIKE 'C%' AND Population > 1000000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Name,Population	35,4	NULL	9	Using sort_intersect(Name,Population); Using where
+EXPLAIN
+SELECT * FROM City WHERE
+Name LIKE 'M%' AND Population > 1500000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Population,Name	4,35	NULL	5	Using sort_intersect(Population,Name); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Name LIKE 'M%' AND Population > 300000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Name	35	NULL	164	Using where
+EXPLAIN
+SELECT * FROM City
+WHERE Name LIKE 'M%' AND Population > 5000000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Population	4	NULL	25	Using where
+SELECT * FROM City USE INDEX ()
+WHERE Name LIKE 'C%' AND Population > 1000000;
+ID	Name	Country	Population
+71	Córdoba	ARG	1157507
+151	Chittagong	BGD	1392860
+212	Curitiba	BRA	1584232
+608	Cairo	EGY	6789479
+712	Cape Town	ZAF	2352121
+926	Conakry	GIN	1090610
+1026	Calcutta [Kolkata]	IND	4399819
+1027	Chennai (Madras)	IND	3841396
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+2258	Cali	COL	2077386
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+3539	Caracas	VEN	1975294
+3795	Chicago	USA	2896016
+SELECT * FROM City
+WHERE Name LIKE 'C%' AND Population > 1000000;
+ID	Name	Country	Population
+71	Córdoba	ARG	1157507
+151	Chittagong	BGD	1392860
+212	Curitiba	BRA	1584232
+608	Cairo	EGY	6789479
+712	Cape Town	ZAF	2352121
+926	Conakry	GIN	1090610
+1026	Calcutta [Kolkata]	IND	4399819
+1027	Chennai (Madras)	IND	3841396
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+2258	Cali	COL	2077386
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+3539	Caracas	VEN	1975294
+3795	Chicago	USA	2896016
+SELECT * FROM City USE INDEX ()
+WHERE Name LIKE 'M%' AND Population > 1500000;
+ID	Name	Country	Population
+131	Melbourne	AUS	2865329
+653	Madrid	ESP	2879052
+766	Manila	PHL	1581082
+942	Medan	IDN	1843919
+1024	Mumbai (Bombay)	IND	10500000
+1381	Mashhad	IRN	1887405
+2259	Medellín	COL	1861265
+3520	Minsk	BLR	1674000
+3580	Moscow	RUS	8389200
+SELECT * FROM City 
+WHERE Name LIKE 'M%' AND Population > 1500000;
+ID	Name	Country	Population
+131	Melbourne	AUS	2865329
+653	Madrid	ESP	2879052
+766	Manila	PHL	1581082
+942	Medan	IDN	1843919
+1024	Mumbai (Bombay)	IND	10500000
+1381	Mashhad	IRN	1887405
+2259	Medellín	COL	1861265
+3520	Minsk	BLR	1674000
+3580	Moscow	RUS	8389200
+SELECT * FROM City USE INDEX ()
+WHERE Name LIKE 'M%' AND Population > 300000;
+ID	Name	Country	Population
+77	Mar del Plata	ARG	512880
+80	Merlo	ARG	463846
+83	Moreno	ARG	356993
+87	Morón	ARG	349246
+131	Melbourne	AUS	2865329
+215	Manaus	BRA	1255049
+223	Maceió	BRA	786288
+250	Mauá	BRA	375055
+256	Moji das Cruzes	BRA	339194
+462	Manchester	GBR	430000
+653	Madrid	ESP	2879052
+658	Málaga	ESP	530553
+661	Murcia	ESP	353504
+766	Manila	PHL	1581082
+778	Makati	PHL	444867
+781	Marikina	PHL	391170
+783	Muntinlupa	PHL	379310
+786	Malabon	PHL	338855
+942	Medan	IDN	1843919
+947	Malang	IDN	716862
+962	Manado	IDN	332288
+963	Mataram	IDN	306600
+1024	Mumbai (Bombay)	IND	10500000
+1042	Madurai	IND	977856
+1051	Meerut	IND	753778
+1074	Mysore	IND	480692
+1081	Moradabad	IND	429214
+1098	Malegaon	IND	342595
+1366	Mosul	IRQ	879000
+1381	Mashhad	IRN	1887405
+1465	Milano	ITA	1300977
+1559	Matsuyama	JPN	466133
+1560	Matsudo	JPN	461126
+1578	Machida	JPN	364197
+1595	Miyazaki	JPN	303784
+1810	Montréal	CAN	1016376
+1816	Mississauga	CAN	608072
+1882	Mombasa	KEN	461753
+1945	Mudanjiang	CHN	570000
+2005	Ma´anshan	CHN	305421
+2259	Medellín	COL	1861265
+2267	Manizales	COL	337580
+2300	Mbuji-Mayi	COD	806475
+2348	Masan	KOR	441242
+2440	Monrovia	LBR	850000
+2454	Macao	MAC	437500
+2487	Marrakech	MAR	621914
+2491	Meknès	MAR	460000
+2523	Monterrey	MEX	1108499
+2526	Mexicali	MEX	764902
+2530	Mérida	MEX	703324
+2537	Morelia	MEX	619958
+2554	Matamoros	MEX	416428
+2557	Mazatlán	MEX	380265
+2698	Maputo	MOZ	1018938
+2699	Matola	MOZ	424662
+2711	Mandalay	MMR	885300
+2712	Moulmein (Mawlamyine)	MMR	307900
+2734	Managua	NIC	959000
+2756	Mushin	NGA	333200
+2757	Maiduguri	NGA	320000
+2826	Multan	PAK	1182441
+2975	Marseille	FRA	798430
+3070	Munich [München]	DEU	1194560
+3086	Mannheim	DEU	307730
+3175	Mekka	SAU	965700
+3176	Medina	SAU	608300
+3214	Mogadishu	SOM	997000
+3364	Mersin (Içel)	TUR	587212
+3371	Malatya	TUR	330312
+3434	Mykolajiv	UKR	508000
+3435	Mariupol	UKR	490000
+3438	Makijivka	UKR	384000
+3492	Montevideo	URY	1236000
+3520	Minsk	BLR	1674000
+3522	Mogiljov	BLR	356000
+3540	Maracaíbo	VEN	1304776
+3545	Maracay	VEN	444443
+3547	Maturín	VEN	319726
+3580	Moscow	RUS	8389200
+3622	Magnitogorsk	RUS	427900
+3625	Murmansk	RUS	376300
+3636	Mahat?kala	RUS	332800
+3810	Memphis	USA	650100
+3811	Milwaukee	USA	596974
+3834	Mesa	USA	396375
+3837	Minneapolis	USA	382618
+3839	Miami	USA	362470
+SELECT * FROM City 
+WHERE Name LIKE 'M%' AND Population > 300000;
+ID	Name	Country	Population
+2454	Macao	MAC	437500
+223	Maceió	BRA	786288
+1578	Machida	JPN	364197
+653	Madrid	ESP	2879052
+1042	Madurai	IND	977856
+3622	Magnitogorsk	RUS	427900
+3636	Mahat?kala	RUS	332800
+2757	Maiduguri	NGA	320000
+778	Makati	PHL	444867
+3438	Makijivka	UKR	384000
+786	Malabon	PHL	338855
+658	Málaga	ESP	530553
+947	Malang	IDN	716862
+3371	Malatya	TUR	330312
+1098	Malegaon	IND	342595
+962	Manado	IDN	332288
+2734	Managua	NIC	959000
+215	Manaus	BRA	1255049
+462	Manchester	GBR	430000
+2711	Mandalay	MMR	885300
+766	Manila	PHL	1581082
+2267	Manizales	COL	337580
+3086	Mannheim	DEU	307730
+2698	Maputo	MOZ	1018938
+77	Mar del Plata	ARG	512880
+3540	Maracaíbo	VEN	1304776
+3545	Maracay	VEN	444443
+781	Marikina	PHL	391170
+3435	Mariupol	UKR	490000
+2487	Marrakech	MAR	621914
+2975	Marseille	FRA	798430
+2348	Masan	KOR	441242
+1381	Mashhad	IRN	1887405
+2554	Matamoros	MEX	416428
+963	Mataram	IDN	306600
+2699	Matola	MOZ	424662
+1560	Matsudo	JPN	461126
+1559	Matsuyama	JPN	466133
+3547	Maturín	VEN	319726
+250	Mauá	BRA	375055
+2557	Mazatlán	MEX	380265
+2005	Ma´anshan	CHN	305421
+2300	Mbuji-Mayi	COD	806475
+942	Medan	IDN	1843919
+2259	Medellín	COL	1861265
+3176	Medina	SAU	608300
+1051	Meerut	IND	753778
+3175	Mekka	SAU	965700
+2491	Meknès	MAR	460000
+131	Melbourne	AUS	2865329
+3810	Memphis	USA	650100
+2530	Mérida	MEX	703324
+80	Merlo	ARG	463846
+3364	Mersin (Içel)	TUR	587212
+3834	Mesa	USA	396375
+2526	Mexicali	MEX	764902
+3839	Miami	USA	362470
+1465	Milano	ITA	1300977
+3811	Milwaukee	USA	596974
+3837	Minneapolis	USA	382618
+3520	Minsk	BLR	1674000
+1816	Mississauga	CAN	608072
+1595	Miyazaki	JPN	303784
+3214	Mogadishu	SOM	997000
+3522	Mogiljov	BLR	356000
+256	Moji das Cruzes	BRA	339194
+1882	Mombasa	KEN	461753
+2440	Monrovia	LBR	850000
+2523	Monterrey	MEX	1108499
+3492	Montevideo	URY	1236000
+1810	Montréal	CAN	1016376
+1081	Moradabad	IND	429214
+2537	Morelia	MEX	619958
+83	Moreno	ARG	356993
+87	Morón	ARG	349246
+3580	Moscow	RUS	8389200
+1366	Mosul	IRQ	879000
+2712	Moulmein (Mawlamyine)	MMR	307900
+1945	Mudanjiang	CHN	570000
+2826	Multan	PAK	1182441
+1024	Mumbai (Bombay)	IND	10500000
+3070	Munich [München]	DEU	1194560
+783	Muntinlupa	PHL	379310
+661	Murcia	ESP	353504
+3625	Murmansk	RUS	376300
+2756	Mushin	NGA	333200
+3434	Mykolajiv	UKR	508000
+1074	Mysore	IND	480692
+SELECT * FROM City USE INDEX ()
+WHERE Name LIKE 'M%' AND Population > 5000000;
+ID	Name	Country	Population
+1024	Mumbai (Bombay)	IND	10500000
+3580	Moscow	RUS	8389200
+SELECT * FROM City
+WHERE Name LIKE 'M%' AND Population > 5000000;
+ID	Name	Country	Population
+3580	Moscow	RUS	8389200
+1024	Mumbai (Bombay)	IND	10500000
+SELECT COUNT(*) FROM City WHERE Name BETWEEN 'M' AND 'N';
+COUNT(*)
+301
+SELECT COUNT(*) FROM City WHERE Name BETWEEN 'G' AND 'J';
+COUNT(*)
+408
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+COUNT(*)
+237
+SELECT COUNT(*) FROM City WHERE Population > 500000;
+COUNT(*)
+539
+SELECT COUNT(*) FROM City WHERE Country LIKE 'C%';
+COUNT(*)
+551
+SELECT COUNT(*) FROM City WHERE Country LIKE 'B%';
+COUNT(*)
+339
+EXPLAIN
+SELECT * FROM City
+WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Name,Population	35,4	NULL	9	Using sort_intersect(Name,Population); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Population,Country	4,3	NULL	19	Using sort_intersect(Population,Country); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Name	35	NULL	225	Using where
+SELECT * FROM City USE INDEX ()
+WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1810	Montréal	CAN	1016376
+2259	Medellín	COL	1861265
+SELECT * FROM City
+WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1810	Montréal	CAN	1016376
+2259	Medellín	COL	1861265
+SELECT * FROM City USE INDEX ()
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+ID	Name	Country	Population
+217	Guarulhos	BRA	1095874
+218	Goiânia	BRA	1056330
+SELECT * FROM City 
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+ID	Name	Country	Population
+217	Guarulhos	BRA	1095874
+218	Goiânia	BRA	1056330
+SELECT * FROM City USE INDEX ()
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1895	Harbin	CHN	4289800
+1905	Hangzhou	CHN	2190500
+1914	Guiyang	CHN	1465200
+1916	Hefei	CHN	1369100
+1927	Hohhot	CHN	916700
+1928	Handan	CHN	840000
+1937	Huainan	CHN	700000
+1950	Hegang	CHN	520000
+SELECT * FROM City 
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1914	Guiyang	CHN	1465200
+1928	Handan	CHN	840000
+1905	Hangzhou	CHN	2190500
+1895	Harbin	CHN	4289800
+1916	Hefei	CHN	1369100
+1950	Hegang	CHN	520000
+1927	Hohhot	CHN	916700
+1937	Huainan	CHN	700000
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 501 AND 1000;
+COUNT(*)
+500
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 1 AND 500;
+COUNT(*)
+500
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 2001 AND 2500;
+COUNT(*)
+500
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 3701 AND 4000;
+COUNT(*)
+300
+SELECT COUNT(*) FROM City WHERE Population > 700000;
+COUNT(*)
+358
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+COUNT(*)
+237
+SELECT COUNT(*) FROM City WHERE Population > 300000;
+COUNT(*)
+1062
+SELECT COUNT(*) FROM City WHERE Population > 600000;
+COUNT(*)
+428
+SELECT COUNT(*) FROM City WHERE Country LIKE 'C%';
+COUNT(*)
+551
+SELECT COUNT(*) FROM City WHERE Country LIKE 'A%';
+COUNT(*)
+107
+SELECT COUNT(*) FROM City WHERE Country LIKE 'L%';
+COUNT(*)
+29
+SELECT COUNT(*) FROM City WHERE Country BETWEEN 'S' AND 'Z';
+COUNT(*)
+682
+EXPLAIN
+SELECT * FROM City
+WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	Population	4	NULL	359	Using where
+EXPLAIN
+SELECT * FROM City
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	Country,Population	3,4	NULL	6	Using sort_intersect(Country,Population); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	Country	3	NULL	28	Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE ID BETWEEN 3701 AND 4000 AND Population > 1000000
+AND Country BETWEEN 'S' AND 'Z';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	Population,PRIMARY	4,4	NULL	17	Using sort_intersect(Population,PRIMARY); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z' ;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	Population	4	NULL	429	Using where
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+554	Santiago de Chile	CHL	4703954
+SELECT * FROM City
+WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+554	Santiago de Chile	CHL	4703954
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+ID	Name	Country	Population
+1	Kabul	AFG	1780000
+56	Luanda	AGO	2022000
+69	Buenos Aires	ARG	2982146
+70	La Matanza	ARG	1266461
+71	Córdoba	ARG	1157507
+126	Yerevan	ARM	1248700
+130	Sydney	AUS	3276207
+131	Melbourne	AUS	2865329
+132	Brisbane	AUS	1291117
+133	Perth	AUS	1096829
+144	Baku	AZE	1787800
+SELECT * FROM City
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+ID	Name	Country	Population
+1	Kabul	AFG	1780000
+56	Luanda	AGO	2022000
+69	Buenos Aires	ARG	2982146
+70	La Matanza	ARG	1266461
+71	Córdoba	ARG	1157507
+126	Yerevan	ARM	1248700
+130	Sydney	AUS	3276207
+131	Melbourne	AUS	2865329
+132	Brisbane	AUS	1291117
+133	Perth	AUS	1096829
+144	Baku	AZE	1787800
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+ID	Name	Country	Population
+2432	Vientiane	LAO	531800
+2434	Riga	LVA	764328
+2438	Beirut	LBN	1100000
+2440	Monrovia	LBR	850000
+2441	Tripoli	LBY	1682000
+2442	Bengasi	LBY	804000
+2447	Vilnius	LTU	577969
+2448	Kaunas	LTU	412639
+SELECT * FROM City 
+WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+ID	Name	Country	Population
+2432	Vientiane	LAO	531800
+2438	Beirut	LBN	1100000
+2440	Monrovia	LBR	850000
+2441	Tripoli	LBY	1682000
+2442	Bengasi	LBY	804000
+2447	Vilnius	LTU	577969
+2448	Kaunas	LTU	412639
+2434	Riga	LVA	764328
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 3701 AND 4000 AND Population > 700000
+AND Country BETWEEN 'S' AND 'Z';
+ID	Name	Country	Population
+3769	Ho Chi Minh City	VNM	3980000
+3770	Hanoi	VNM	1410000
+3771	Haiphong	VNM	783133
+3793	New York	USA	8008278
+3794	Los Angeles	USA	3694820
+3795	Chicago	USA	2896016
+3796	Houston	USA	1953631
+3797	Philadelphia	USA	1517550
+3798	Phoenix	USA	1321045
+3799	San Diego	USA	1223400
+3800	Dallas	USA	1188580
+3801	San Antonio	USA	1144646
+3802	Detroit	USA	951270
+3803	San Jose	USA	894943
+3804	Indianapolis	USA	791926
+3805	San Francisco	USA	776733
+3806	Jacksonville	USA	735167
+3807	Columbus	USA	711470
+SELECT * FROM City 
+WHERE ID BETWEEN 3701 AND 4000 AND Population > 700000
+AND Country BETWEEN 'S' AND 'Z';
+ID	Name	Country	Population
+3769	Ho Chi Minh City	VNM	3980000
+3770	Hanoi	VNM	1410000
+3771	Haiphong	VNM	783133
+3793	New York	USA	8008278
+3794	Los Angeles	USA	3694820
+3795	Chicago	USA	2896016
+3796	Houston	USA	1953631
+3797	Philadelphia	USA	1517550
+3798	Phoenix	USA	1321045
+3799	San Diego	USA	1223400
+3800	Dallas	USA	1188580
+3801	San Antonio	USA	1144646
+3802	Detroit	USA	951270
+3803	San Jose	USA	894943
+3804	Indianapolis	USA	791926
+3805	San Francisco	USA	776733
+3806	Jacksonville	USA	735167
+3807	Columbus	USA	711470
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z' ;
+ID	Name	Country	Population
+3048	Stockholm	SWE	750348
+3173	Riyadh	SAU	3324000
+3174	Jedda	SAU	2046300
+3175	Mekka	SAU	965700
+3176	Medina	SAU	608300
+3197	Pikine	SEN	855287
+3198	Dakar	SEN	785071
+3207	Freetown	SLE	850000
+3208	Singapore	SGP	4017733
+3214	Mogadishu	SOM	997000
+3224	Omdurman	SDN	1271403
+3225	Khartum	SDN	947483
+3226	Sharq al-Nil	SDN	700887
+3250	Damascus	SYR	1347000
+3251	Aleppo	SYR	1261983
+3263	Taipei	TWN	2641312
+3264	Kaohsiung	TWN	1475505
+3265	Taichung	TWN	940589
+3266	Tainan	TWN	728060
+3305	Dar es Salaam	TZA	1747000
+3320	Bangkok	THA	6320174
+3349	Tunis	TUN	690600
+3357	Istanbul	TUR	8787958
+3358	Ankara	TUR	3038159
+3359	Izmir	TUR	2130359
+3360	Adana	TUR	1131198
+3361	Bursa	TUR	1095842
+3362	Gaziantep	TUR	789056
+3363	Konya	TUR	628364
+3425	Kampala	UGA	890800
+3426	Kyiv	UKR	2624000
+3427	Harkova [Harkiv]	UKR	1500000
+3428	Dnipropetrovsk	UKR	1103000
+3429	Donetsk	UKR	1050000
+3430	Odesa	UKR	1011000
+3431	Zaporizzja	UKR	848000
+3432	Lviv	UKR	788000
+3433	Kryvyi Rig	UKR	703000
+3492	Montevideo	URY	1236000
+3503	Toskent	UZB	2117500
+3539	Caracas	VEN	1975294
+3540	Maracaíbo	VEN	1304776
+3541	Barquisimeto	VEN	877239
+3542	Valencia	VEN	794246
+3543	Ciudad Guayana	VEN	663713
+3769	Ho Chi Minh City	VNM	3980000
+3770	Hanoi	VNM	1410000
+3771	Haiphong	VNM	783133
+3793	New York	USA	8008278
+3794	Los Angeles	USA	3694820
+3795	Chicago	USA	2896016
+3796	Houston	USA	1953631
+3797	Philadelphia	USA	1517550
+3798	Phoenix	USA	1321045
+3799	San Diego	USA	1223400
+3800	Dallas	USA	1188580
+3801	San Antonio	USA	1144646
+3802	Detroit	USA	951270
+3803	San Jose	USA	894943
+3804	Indianapolis	USA	791926
+3805	San Francisco	USA	776733
+3806	Jacksonville	USA	735167
+3807	Columbus	USA	711470
+3808	Austin	USA	656562
+3809	Baltimore	USA	651154
+3810	Memphis	USA	650100
+SELECT * FROM City 
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z' ;
+ID	Name	Country	Population
+3176	Medina	SAU	608300
+3363	Konya	TUR	628364
+3810	Memphis	USA	650100
+3809	Baltimore	USA	651154
+3808	Austin	USA	656562
+3543	Ciudad Guayana	VEN	663713
+3349	Tunis	TUN	690600
+3226	Sharq al-Nil	SDN	700887
+3433	Kryvyi Rig	UKR	703000
+3807	Columbus	USA	711470
+3266	Tainan	TWN	728060
+3806	Jacksonville	USA	735167
+3048	Stockholm	SWE	750348
+3805	San Francisco	USA	776733
+3771	Haiphong	VNM	783133
+3198	Dakar	SEN	785071
+3432	Lviv	UKR	788000
+3362	Gaziantep	TUR	789056
+3804	Indianapolis	USA	791926
+3542	Valencia	VEN	794246
+3431	Zaporizzja	UKR	848000
+3207	Freetown	SLE	850000
+3197	Pikine	SEN	855287
+3541	Barquisimeto	VEN	877239
+3425	Kampala	UGA	890800
+3803	San Jose	USA	894943
+3265	Taichung	TWN	940589
+3225	Khartum	SDN	947483
+3802	Detroit	USA	951270
+3175	Mekka	SAU	965700
+3214	Mogadishu	SOM	997000
+3430	Odesa	UKR	1011000
+3429	Donetsk	UKR	1050000
+3361	Bursa	TUR	1095842
+3428	Dnipropetrovsk	UKR	1103000
+3360	Adana	TUR	1131198
+3801	San Antonio	USA	1144646
+3800	Dallas	USA	1188580
+3799	San Diego	USA	1223400
+3492	Montevideo	URY	1236000
+3251	Aleppo	SYR	1261983
+3224	Omdurman	SDN	1271403
+3540	Maracaíbo	VEN	1304776
+3798	Phoenix	USA	1321045
+3250	Damascus	SYR	1347000
+3770	Hanoi	VNM	1410000
+3264	Kaohsiung	TWN	1475505
+3427	Harkova [Harkiv]	UKR	1500000
+3797	Philadelphia	USA	1517550
+3305	Dar es Salaam	TZA	1747000
+3796	Houston	USA	1953631
+3539	Caracas	VEN	1975294
+3174	Jedda	SAU	2046300
+3503	Toskent	UZB	2117500
+3359	Izmir	TUR	2130359
+3426	Kyiv	UKR	2624000
+3263	Taipei	TWN	2641312
+3795	Chicago	USA	2896016
+3358	Ankara	TUR	3038159
+3173	Riyadh	SAU	3324000
+3794	Los Angeles	USA	3694820
+3769	Ho Chi Minh City	VNM	3980000
+3208	Singapore	SGP	4017733
+3320	Bangkok	THA	6320174
+3793	New York	USA	8008278
+3357	Istanbul	TUR	8787958
+SET SESSION sort_buffer_size = 2048;
+EXPLAIN
+SELECT * FROM City WHERE
+Name LIKE 'C%' AND Population > 1000000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Name,Population	35,4	NULL	9	Using sort_intersect(Name,Population); Using where
+EXPLAIN
+SELECT * FROM City WHERE
+Name LIKE 'M%' AND Population > 1500000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Population,Name	4,35	NULL	5	Using sort_intersect(Population,Name); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE  Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Name	35	NULL	225	Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE  Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Name	35	NULL	225	Using where
+EXPLAIN
+SELECT * FROM City
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	Country,Population	3,4	NULL	6	Using sort_intersect(Country,Population); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	Population	4	NULL	429	Using where
+SELECT * FROM City WHERE
+Name LIKE 'C%' AND Population > 1000000;
+ID	Name	Country	Population
+71	Córdoba	ARG	1157507
+151	Chittagong	BGD	1392860
+212	Curitiba	BRA	1584232
+608	Cairo	EGY	6789479
+712	Cape Town	ZAF	2352121
+926	Conakry	GIN	1090610
+1026	Calcutta [Kolkata]	IND	4399819
+1027	Chennai (Madras)	IND	3841396
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+2258	Cali	COL	2077386
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+3539	Caracas	VEN	1975294
+3795	Chicago	USA	2896016
+SELECT * FROM City WHERE
+Name LIKE 'M%' AND Population > 1500000;
+ID	Name	Country	Population
+131	Melbourne	AUS	2865329
+653	Madrid	ESP	2879052
+766	Manila	PHL	1581082
+942	Medan	IDN	1843919
+1024	Mumbai (Bombay)	IND	10500000
+1381	Mashhad	IRN	1887405
+2259	Medellín	COL	1861265
+3520	Minsk	BLR	1674000
+3580	Moscow	RUS	8389200
+SELECT * FROM City 
+WHERE  Name BETWEEN 'G' AND 'J' AND Population > 700000 AND Country LIKE 'B%';
+ID	Name	Country	Population
+218	Goiânia	BRA	1056330
+217	Guarulhos	BRA	1095874
+SELECT * FROM City 
+WHERE  Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1914	Guiyang	CHN	1465200
+1928	Handan	CHN	840000
+1905	Hangzhou	CHN	2190500
+1895	Harbin	CHN	4289800
+1916	Hefei	CHN	1369100
+1950	Hegang	CHN	520000
+1927	Hohhot	CHN	916700
+1937	Huainan	CHN	700000
+SELECT * FROM City
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+ID	Name	Country	Population
+1	Kabul	AFG	1780000
+56	Luanda	AGO	2022000
+69	Buenos Aires	ARG	2982146
+70	La Matanza	ARG	1266461
+71	Córdoba	ARG	1157507
+126	Yerevan	ARM	1248700
+130	Sydney	AUS	3276207
+131	Melbourne	AUS	2865329
+132	Brisbane	AUS	1291117
+133	Perth	AUS	1096829
+144	Baku	AZE	1787800
+SELECT * FROM City 
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z';
+ID	Name	Country	Population
+3176	Medina	SAU	608300
+3363	Konya	TUR	628364
+3810	Memphis	USA	650100
+3809	Baltimore	USA	651154
+3808	Austin	USA	656562
+3543	Ciudad Guayana	VEN	663713
+3349	Tunis	TUN	690600
+3226	Sharq al-Nil	SDN	700887
+3433	Kryvyi Rig	UKR	703000
+3807	Columbus	USA	711470
+3266	Tainan	TWN	728060
+3806	Jacksonville	USA	735167
+3048	Stockholm	SWE	750348
+3805	San Francisco	USA	776733
+3771	Haiphong	VNM	783133
+3198	Dakar	SEN	785071
+3432	Lviv	UKR	788000
+3362	Gaziantep	TUR	789056
+3804	Indianapolis	USA	791926
+3542	Valencia	VEN	794246
+3431	Zaporizzja	UKR	848000
+3207	Freetown	SLE	850000
+3197	Pikine	SEN	855287
+3541	Barquisimeto	VEN	877239
+3425	Kampala	UGA	890800
+3803	San Jose	USA	894943
+3265	Taichung	TWN	940589
+3225	Khartum	SDN	947483
+3802	Detroit	USA	951270
+3175	Mekka	SAU	965700
+3214	Mogadishu	SOM	997000
+3430	Odesa	UKR	1011000
+3429	Donetsk	UKR	1050000
+3361	Bursa	TUR	1095842
+3428	Dnipropetrovsk	UKR	1103000
+3360	Adana	TUR	1131198
+3801	San Antonio	USA	1144646
+3800	Dallas	USA	1188580
+3799	San Diego	USA	1223400
+3492	Montevideo	URY	1236000
+3251	Aleppo	SYR	1261983
+3224	Omdurman	SDN	1271403
+3540	Maracaíbo	VEN	1304776
+3798	Phoenix	USA	1321045
+3250	Damascus	SYR	1347000
+3770	Hanoi	VNM	1410000
+3264	Kaohsiung	TWN	1475505
+3427	Harkova [Harkiv]	UKR	1500000
+3797	Philadelphia	USA	1517550
+3305	Dar es Salaam	TZA	1747000
+3796	Houston	USA	1953631
+3539	Caracas	VEN	1975294
+3174	Jedda	SAU	2046300
+3503	Toskent	UZB	2117500
+3359	Izmir	TUR	2130359
+3426	Kyiv	UKR	2624000
+3263	Taipei	TWN	2641312
+3795	Chicago	USA	2896016
+3358	Ankara	TUR	3038159
+3173	Riyadh	SAU	3324000
+3794	Los Angeles	USA	3694820
+3769	Ho Chi Minh City	VNM	3980000
+3208	Singapore	SGP	4017733
+3320	Bangkok	THA	6320174
+3793	New York	USA	8008278
+3357	Istanbul	TUR	8787958
+SET SESSION sort_buffer_size = default;
+DROP INDEX Country ON City;
+CREATE INDEX CountryID ON City(Country,ID);
+CREATE INDEX CountryName ON City(Country,Name);
+EXPLAIN
+SELECT * FROM City 
+WHERE Country LIKE 'M%' AND Population > 1000000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,CountryID,CountryName	Population,CountryID	4,3	NULL	15	Using sort_intersect(Population,CountryID); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Country='CHN' AND Population > 1500000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,CountryID,CountryName	Population,CountryID	4,3	NULL	11	Using sort_intersect(Population,CountryID); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name,CountryID,CountryName	CountryName,Population	38,4	NULL	1	Using sort_intersect(CountryName,Population); Using where
+SELECT * FROM City USE INDEX ()
+WHERE Country LIKE 'M%' AND Population > 1000000;
+ID	Name	Country	Population
+2464	Kuala Lumpur	MYS	1297526
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+2516	Guadalajara	MEX	1647720
+2517	Ecatepec de Morelos	MEX	1620303
+2518	Puebla	MEX	1346176
+2519	Nezahualcóyotl	MEX	1224924
+2520	Juárez	MEX	1217818
+2521	Tijuana	MEX	1212232
+2522	León	MEX	1133576
+2523	Monterrey	MEX	1108499
+2524	Zapopan	MEX	1002239
+2698	Maputo	MOZ	1018938
+2710	Rangoon (Yangon)	MMR	3361700
+SELECT * FROM City 
+WHERE Country LIKE 'M%' AND Population > 700000;
+ID	Name	Country	Population
+2485	Casablanca	MAR	2940623
+2690	Chisinau	MDA	719900
+2515	Ciudad de México	MEX	8591309
+2516	Guadalajara	MEX	1647720
+2517	Ecatepec de Morelos	MEX	1620303
+2518	Puebla	MEX	1346176
+2519	Nezahualcóyotl	MEX	1224924
+2520	Juárez	MEX	1217818
+2521	Tijuana	MEX	1212232
+2522	León	MEX	1133576
+2523	Monterrey	MEX	1108499
+2524	Zapopan	MEX	1002239
+2525	Naucalpan de Juárez	MEX	857511
+2526	Mexicali	MEX	764902
+2527	Culiacán	MEX	744859
+2528	Acapulco de Juárez	MEX	721011
+2529	Tlalnepantla de Baz	MEX	720755
+2530	Mérida	MEX	703324
+2482	Bamako	MLI	809552
+2710	Rangoon (Yangon)	MMR	3361700
+2711	Mandalay	MMR	885300
+2696	Ulan Bator	MNG	773700
+2698	Maputo	MOZ	1018938
+2464	Kuala Lumpur	MYS	1297526
+SELECT * FROM City USE INDEX ()
+WHERE Country='CHN' AND Population > 1500000;
+ID	Name	Country	Population
+1890	Shanghai	CHN	9696300
+1891	Peking	CHN	7472000
+1892	Chongqing	CHN	6351600
+1893	Tianjin	CHN	5286800
+1894	Wuhan	CHN	4344600
+1895	Harbin	CHN	4289800
+1896	Shenyang	CHN	4265200
+1897	Kanton [Guangzhou]	CHN	4256300
+1898	Chengdu	CHN	3361500
+1899	Nanking [Nanjing]	CHN	2870300
+1900	Changchun	CHN	2812000
+1901	Xi´an	CHN	2761400
+1902	Dalian	CHN	2697000
+1903	Qingdao	CHN	2596000
+1904	Jinan	CHN	2278100
+1905	Hangzhou	CHN	2190500
+1906	Zhengzhou	CHN	2107200
+1907	Shijiazhuang	CHN	2041500
+1908	Taiyuan	CHN	1968400
+1909	Kunming	CHN	1829500
+1910	Changsha	CHN	1809800
+1911	Nanchang	CHN	1691600
+1912	Fuzhou	CHN	1593800
+1913	Lanzhou	CHN	1565800
+SELECT * FROM City 
+WHERE Country='CHN' AND Population > 1500000;
+ID	Name	Country	Population
+1890	Shanghai	CHN	9696300
+1891	Peking	CHN	7472000
+1892	Chongqing	CHN	6351600
+1893	Tianjin	CHN	5286800
+1894	Wuhan	CHN	4344600
+1895	Harbin	CHN	4289800
+1896	Shenyang	CHN	4265200
+1897	Kanton [Guangzhou]	CHN	4256300
+1898	Chengdu	CHN	3361500
+1899	Nanking [Nanjing]	CHN	2870300
+1900	Changchun	CHN	2812000
+1901	Xi´an	CHN	2761400
+1902	Dalian	CHN	2697000
+1903	Qingdao	CHN	2596000
+1904	Jinan	CHN	2278100
+1905	Hangzhou	CHN	2190500
+1906	Zhengzhou	CHN	2107200
+1907	Shijiazhuang	CHN	2041500
+1908	Taiyuan	CHN	1968400
+1909	Kunming	CHN	1829500
+1910	Changsha	CHN	1809800
+1911	Nanchang	CHN	1691600
+1912	Fuzhou	CHN	1593800
+1913	Lanzhou	CHN	1565800
+SELECT * FROM City USE INDEX ()
+WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+ID	Name	Country	Population
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+SELECT * FROM City 
+WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+ID	Name	Country	Population
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+DROP DATABASE world;
+use test;
+CREATE TABLE t1 (
+f1 int,
+f4 varchar(32),
+f5 int,
+PRIMARY KEY (f1),
+KEY (f4)
+) ENGINE=InnoDB;
+Warnings:
+Warning	1286	Unknown table engine 'InnoDB'
+Warning	1266	Using storage engine MyISAM for table 't1'
+INSERT INTO t1 VALUES 
+(5,'H',1), (9,'g',0), (527,'i',0), (528,'y',1), (529,'S',6),
+(530,'m',7), (531,'b',2), (532,'N',1), (533,'V',NULL), (534,'l',1),
+(535,'M',0), (536,'w',1), (537,'j',5), (538,'l',0), (539,'n',2),
+(540,'m',2), (541,'r',2), (542,'l',2), (543,'h',3),(544,'o',0),
+(956,'h',0), (957,'g',0), (958,'W',5), (959,'s',3), (960,'w',0),
+(961,'q',0), (962,'e',NULL), (963,'u',7), (964,'q',1), (965,'N',NULL),
+(966,'e',0), (967,'t',3), (968,'e',6), (969,'f',NULL), (970,'j',0),
+(971,'s',3), (972,'I',0), (973,'h',4), (974,'g',1), (975,'s',0),
+(976,'r',3), (977,'x',1), (978,'v',8), (979,'j',NULL), (980,'z',7),
+(981,'t',9), (982,'j',5), (983,'u',NULL), (984,'g',6), (985,'w',1),
+(986,'h',1), (987,'v',0), (988,'v',0), (989,'c',2), (990,'b',7),
+(991,'z',0), (992,'M',1), (993,'u',2), (994,'r',2), (995,'b',4),
+(996,'A',2), (997,'u',0), (998,'a',0), (999,'j',2), (1,'I',2);
+EXPLAIN
+SELECT * FROM t1
+WHERE (f1 < 535  OR  f1 > 985) AND ( f4='r' OR f4 LIKE 'a%' ) ;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	PRIMARY,f4	f4	35	NULL	5	Using where
+SELECT * FROM t1
+WHERE (f1 < 535  OR  f1 > 985) AND ( f4='r' OR f4 LIKE 'a%' ) ;
+f1	f4	f5
+996	A	2
+998	a	0
+994	r	2
+DROP TABLE t1;
+SET SESSION optimizer_switch='index_merge_sort_intersection=on';
diff --git a/mysql-test/r/index_intersect_innodb.result b/mysql-test/r/index_intersect_innodb.result
new file mode 100644
index 00000000000..7b53761935a
--- /dev/null
+++ b/mysql-test/r/index_intersect_innodb.result
@@ -0,0 +1,1051 @@
+SET SESSION STORAGE_ENGINE='InnoDB';
+DROP TABLE IF EXISTS t1,t2,t3,t4;
+DROP DATABASE IF EXISTS world;
+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)
+);
+SELECT COUNT(*) FROM Country;
+COUNT(*)
+239
+SELECT COUNT(*) FROM City;
+COUNT(*)
+4079
+SELECT COUNT(*) FROM CountryLanguage;
+COUNT(*)
+984
+CREATE INDEX Name ON City(Name);
+SET SESSION optimizer_switch='index_merge_sort_intersection=on';
+SELECT COUNT(*) FROM City;
+COUNT(*)
+4079
+SELECT COUNT(*) FROM City WHERE Name LIKE 'C%';
+COUNT(*)
+281
+SELECT COUNT(*) FROM City WHERE Name LIKE 'M%';
+COUNT(*)
+301
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+COUNT(*)
+237
+SELECT COUNT(*) FROM City WHERE Population > 1500000;
+COUNT(*)
+129
+SELECT COUNT(*) FROM City WHERE Population > 300000;
+COUNT(*)
+1062
+SELECT COUNT(*) FROM City WHERE Population > 5000000;
+COUNT(*)
+24
+EXPLAIN
+SELECT * FROM City WHERE
+Name LIKE 'C%' AND Population > 1000000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Population,Name	4,35	NULL	16	Using sort_intersect(Population,Name); Using where
+EXPLAIN
+SELECT * FROM City WHERE
+Name LIKE 'M%' AND Population > 1500000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Population,Name	4,35	NULL	9	Using sort_intersect(Population,Name); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Name LIKE 'M%' AND Population > 300000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Name,Population	35,4	NULL	79	Using sort_intersect(Name,Population); Using where
+EXPLAIN
+SELECT * FROM City
+WHERE Name LIKE 'M%' AND Population > 5000000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Population,Name	4,35	NULL	1	Using sort_intersect(Population,Name); Using where
+SELECT * FROM City USE INDEX ()
+WHERE Name LIKE 'C%' AND Population > 1000000;
+ID	Name	Country	Population
+71	Córdoba	ARG	1157507
+151	Chittagong	BGD	1392860
+212	Curitiba	BRA	1584232
+608	Cairo	EGY	6789479
+712	Cape Town	ZAF	2352121
+926	Conakry	GIN	1090610
+1026	Calcutta [Kolkata]	IND	4399819
+1027	Chennai (Madras)	IND	3841396
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+2258	Cali	COL	2077386
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+3539	Caracas	VEN	1975294
+3795	Chicago	USA	2896016
+SELECT * FROM City
+WHERE Name LIKE 'C%' AND Population > 1000000;
+ID	Name	Country	Population
+71	Córdoba	ARG	1157507
+151	Chittagong	BGD	1392860
+212	Curitiba	BRA	1584232
+608	Cairo	EGY	6789479
+712	Cape Town	ZAF	2352121
+926	Conakry	GIN	1090610
+1026	Calcutta [Kolkata]	IND	4399819
+1027	Chennai (Madras)	IND	3841396
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+2258	Cali	COL	2077386
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+3539	Caracas	VEN	1975294
+3795	Chicago	USA	2896016
+SELECT * FROM City USE INDEX ()
+WHERE Name LIKE 'M%' AND Population > 1500000;
+ID	Name	Country	Population
+131	Melbourne	AUS	2865329
+653	Madrid	ESP	2879052
+766	Manila	PHL	1581082
+942	Medan	IDN	1843919
+1024	Mumbai (Bombay)	IND	10500000
+1381	Mashhad	IRN	1887405
+2259	Medellín	COL	1861265
+3520	Minsk	BLR	1674000
+3580	Moscow	RUS	8389200
+SELECT * FROM City 
+WHERE Name LIKE 'M%' AND Population > 1500000;
+ID	Name	Country	Population
+131	Melbourne	AUS	2865329
+653	Madrid	ESP	2879052
+766	Manila	PHL	1581082
+942	Medan	IDN	1843919
+1024	Mumbai (Bombay)	IND	10500000
+1381	Mashhad	IRN	1887405
+2259	Medellín	COL	1861265
+3520	Minsk	BLR	1674000
+3580	Moscow	RUS	8389200
+SELECT * FROM City USE INDEX ()
+WHERE Name LIKE 'M%' AND Population > 300000;
+ID	Name	Country	Population
+77	Mar del Plata	ARG	512880
+80	Merlo	ARG	463846
+83	Moreno	ARG	356993
+87	Morón	ARG	349246
+131	Melbourne	AUS	2865329
+215	Manaus	BRA	1255049
+223	Maceió	BRA	786288
+250	Mauá	BRA	375055
+256	Moji das Cruzes	BRA	339194
+462	Manchester	GBR	430000
+653	Madrid	ESP	2879052
+658	Málaga	ESP	530553
+661	Murcia	ESP	353504
+766	Manila	PHL	1581082
+778	Makati	PHL	444867
+781	Marikina	PHL	391170
+783	Muntinlupa	PHL	379310
+786	Malabon	PHL	338855
+942	Medan	IDN	1843919
+947	Malang	IDN	716862
+962	Manado	IDN	332288
+963	Mataram	IDN	306600
+1024	Mumbai (Bombay)	IND	10500000
+1042	Madurai	IND	977856
+1051	Meerut	IND	753778
+1074	Mysore	IND	480692
+1081	Moradabad	IND	429214
+1098	Malegaon	IND	342595
+1366	Mosul	IRQ	879000
+1381	Mashhad	IRN	1887405
+1465	Milano	ITA	1300977
+1559	Matsuyama	JPN	466133
+1560	Matsudo	JPN	461126
+1578	Machida	JPN	364197
+1595	Miyazaki	JPN	303784
+1810	Montréal	CAN	1016376
+1816	Mississauga	CAN	608072
+1882	Mombasa	KEN	461753
+1945	Mudanjiang	CHN	570000
+2005	Ma´anshan	CHN	305421
+2259	Medellín	COL	1861265
+2267	Manizales	COL	337580
+2300	Mbuji-Mayi	COD	806475
+2348	Masan	KOR	441242
+2440	Monrovia	LBR	850000
+2454	Macao	MAC	437500
+2487	Marrakech	MAR	621914
+2491	Meknès	MAR	460000
+2523	Monterrey	MEX	1108499
+2526	Mexicali	MEX	764902
+2530	Mérida	MEX	703324
+2537	Morelia	MEX	619958
+2554	Matamoros	MEX	416428
+2557	Mazatlán	MEX	380265
+2698	Maputo	MOZ	1018938
+2699	Matola	MOZ	424662
+2711	Mandalay	MMR	885300
+2712	Moulmein (Mawlamyine)	MMR	307900
+2734	Managua	NIC	959000
+2756	Mushin	NGA	333200
+2757	Maiduguri	NGA	320000
+2826	Multan	PAK	1182441
+2975	Marseille	FRA	798430
+3070	Munich [München]	DEU	1194560
+3086	Mannheim	DEU	307730
+3175	Mekka	SAU	965700
+3176	Medina	SAU	608300
+3214	Mogadishu	SOM	997000
+3364	Mersin (Içel)	TUR	587212
+3371	Malatya	TUR	330312
+3434	Mykolajiv	UKR	508000
+3435	Mariupol	UKR	490000
+3438	Makijivka	UKR	384000
+3492	Montevideo	URY	1236000
+3520	Minsk	BLR	1674000
+3522	Mogiljov	BLR	356000
+3540	Maracaíbo	VEN	1304776
+3545	Maracay	VEN	444443
+3547	Maturín	VEN	319726
+3580	Moscow	RUS	8389200
+3622	Magnitogorsk	RUS	427900
+3625	Murmansk	RUS	376300
+3636	Mahat?kala	RUS	332800
+3810	Memphis	USA	650100
+3811	Milwaukee	USA	596974
+3834	Mesa	USA	396375
+3837	Minneapolis	USA	382618
+3839	Miami	USA	362470
+SELECT * FROM City 
+WHERE Name LIKE 'M%' AND Population > 300000;
+ID	Name	Country	Population
+77	Mar del Plata	ARG	512880
+80	Merlo	ARG	463846
+83	Moreno	ARG	356993
+87	Morón	ARG	349246
+131	Melbourne	AUS	2865329
+215	Manaus	BRA	1255049
+223	Maceió	BRA	786288
+250	Mauá	BRA	375055
+256	Moji das Cruzes	BRA	339194
+462	Manchester	GBR	430000
+653	Madrid	ESP	2879052
+658	Málaga	ESP	530553
+661	Murcia	ESP	353504
+766	Manila	PHL	1581082
+778	Makati	PHL	444867
+781	Marikina	PHL	391170
+783	Muntinlupa	PHL	379310
+786	Malabon	PHL	338855
+942	Medan	IDN	1843919
+947	Malang	IDN	716862
+962	Manado	IDN	332288
+963	Mataram	IDN	306600
+1024	Mumbai (Bombay)	IND	10500000
+1042	Madurai	IND	977856
+1051	Meerut	IND	753778
+1074	Mysore	IND	480692
+1081	Moradabad	IND	429214
+1098	Malegaon	IND	342595
+1366	Mosul	IRQ	879000
+1381	Mashhad	IRN	1887405
+1465	Milano	ITA	1300977
+1559	Matsuyama	JPN	466133
+1560	Matsudo	JPN	461126
+1578	Machida	JPN	364197
+1595	Miyazaki	JPN	303784
+1810	Montréal	CAN	1016376
+1816	Mississauga	CAN	608072
+1882	Mombasa	KEN	461753
+1945	Mudanjiang	CHN	570000
+2005	Ma´anshan	CHN	305421
+2259	Medellín	COL	1861265
+2267	Manizales	COL	337580
+2300	Mbuji-Mayi	COD	806475
+2348	Masan	KOR	441242
+2440	Monrovia	LBR	850000
+2454	Macao	MAC	437500
+2487	Marrakech	MAR	621914
+2491	Meknès	MAR	460000
+2523	Monterrey	MEX	1108499
+2526	Mexicali	MEX	764902
+2530	Mérida	MEX	703324
+2537	Morelia	MEX	619958
+2554	Matamoros	MEX	416428
+2557	Mazatlán	MEX	380265
+2698	Maputo	MOZ	1018938
+2699	Matola	MOZ	424662
+2711	Mandalay	MMR	885300
+2712	Moulmein (Mawlamyine)	MMR	307900
+2734	Managua	NIC	959000
+2756	Mushin	NGA	333200
+2757	Maiduguri	NGA	320000
+2826	Multan	PAK	1182441
+2975	Marseille	FRA	798430
+3070	Munich [München]	DEU	1194560
+3086	Mannheim	DEU	307730
+3175	Mekka	SAU	965700
+3176	Medina	SAU	608300
+3214	Mogadishu	SOM	997000
+3364	Mersin (Içel)	TUR	587212
+3371	Malatya	TUR	330312
+3434	Mykolajiv	UKR	508000
+3435	Mariupol	UKR	490000
+3438	Makijivka	UKR	384000
+3492	Montevideo	URY	1236000
+3520	Minsk	BLR	1674000
+3522	Mogiljov	BLR	356000
+3540	Maracaíbo	VEN	1304776
+3545	Maracay	VEN	444443
+3547	Maturín	VEN	319726
+3580	Moscow	RUS	8389200
+3622	Magnitogorsk	RUS	427900
+3625	Murmansk	RUS	376300
+3636	Mahat?kala	RUS	332800
+3810	Memphis	USA	650100
+3811	Milwaukee	USA	596974
+3834	Mesa	USA	396375
+3837	Minneapolis	USA	382618
+3839	Miami	USA	362470
+SELECT * FROM City USE INDEX ()
+WHERE Name LIKE 'M%' AND Population > 5000000;
+ID	Name	Country	Population
+1024	Mumbai (Bombay)	IND	10500000
+3580	Moscow	RUS	8389200
+SELECT * FROM City
+WHERE Name LIKE 'M%' AND Population > 5000000;
+ID	Name	Country	Population
+1024	Mumbai (Bombay)	IND	10500000
+3580	Moscow	RUS	8389200
+SELECT COUNT(*) FROM City WHERE Name BETWEEN 'M' AND 'N';
+COUNT(*)
+301
+SELECT COUNT(*) FROM City WHERE Name BETWEEN 'G' AND 'J';
+COUNT(*)
+408
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+COUNT(*)
+237
+SELECT COUNT(*) FROM City WHERE Population > 500000;
+COUNT(*)
+539
+SELECT COUNT(*) FROM City WHERE Country LIKE 'C%';
+COUNT(*)
+551
+SELECT COUNT(*) FROM City WHERE Country LIKE 'B%';
+COUNT(*)
+339
+EXPLAIN
+SELECT * FROM City
+WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Population,Name,Country	4,35,3	NULL	2	Using sort_intersect(Population,Name,Country); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Population,Country,Name	4,3,35	NULL	2	Using sort_intersect(Population,Country,Name); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Name,Population,Country	35,4,3	NULL	7	Using sort_intersect(Name,Population,Country); Using where
+SELECT * FROM City USE INDEX ()
+WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1810	Montréal	CAN	1016376
+2259	Medellín	COL	1861265
+SELECT * FROM City
+WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1810	Montréal	CAN	1016376
+2259	Medellín	COL	1861265
+SELECT * FROM City USE INDEX ()
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+ID	Name	Country	Population
+217	Guarulhos	BRA	1095874
+218	Goiânia	BRA	1056330
+SELECT * FROM City 
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+ID	Name	Country	Population
+217	Guarulhos	BRA	1095874
+218	Goiânia	BRA	1056330
+SELECT * FROM City USE INDEX ()
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1895	Harbin	CHN	4289800
+1905	Hangzhou	CHN	2190500
+1914	Guiyang	CHN	1465200
+1916	Hefei	CHN	1369100
+1927	Hohhot	CHN	916700
+1928	Handan	CHN	840000
+1937	Huainan	CHN	700000
+1950	Hegang	CHN	520000
+SELECT * FROM City 
+WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1895	Harbin	CHN	4289800
+1905	Hangzhou	CHN	2190500
+1914	Guiyang	CHN	1465200
+1916	Hefei	CHN	1369100
+1927	Hohhot	CHN	916700
+1928	Handan	CHN	840000
+1937	Huainan	CHN	700000
+1950	Hegang	CHN	520000
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 501 AND 1000;
+COUNT(*)
+500
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 1 AND 500;
+COUNT(*)
+500
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 2001 AND 2500;
+COUNT(*)
+500
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 3701 AND 4000;
+COUNT(*)
+300
+SELECT COUNT(*) FROM City WHERE Population > 700000;
+COUNT(*)
+358
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+COUNT(*)
+237
+SELECT COUNT(*) FROM City WHERE Population > 300000;
+COUNT(*)
+1062
+SELECT COUNT(*) FROM City WHERE Population > 600000;
+COUNT(*)
+428
+SELECT COUNT(*) FROM City WHERE Country LIKE 'C%';
+COUNT(*)
+551
+SELECT COUNT(*) FROM City WHERE Country LIKE 'A%';
+COUNT(*)
+107
+SELECT COUNT(*) FROM City WHERE Country LIKE 'L%';
+COUNT(*)
+29
+SELECT COUNT(*) FROM City WHERE Country BETWEEN 'S' AND 'Z';
+COUNT(*)
+682
+EXPLAIN
+SELECT * FROM City
+WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	PRIMARY,Country,Population	4,3,4	NULL	11	Using sort_intersect(PRIMARY,Country,Population); Using where
+EXPLAIN
+SELECT * FROM City
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	PRIMARY,Population,Country	4,4,3	NULL	1	Using sort_intersect(PRIMARY,Population,Country); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	PRIMARY,Country	4,3	NULL	10	Using sort_intersect(PRIMARY,Country); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE ID BETWEEN 3701 AND 4000 AND Population > 1000000
+AND Country BETWEEN 'S' AND 'Z';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	PRIMARY,Country,Population	4,3,4	NULL	2	Using sort_intersect(PRIMARY,Country,Population); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z' ;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	PRIMARY,Population,Country	4,4,3	NULL	30	Using sort_intersect(PRIMARY,Population,Country); Using where
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+554	Santiago de Chile	CHL	4703954
+SELECT * FROM City
+WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+554	Santiago de Chile	CHL	4703954
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+ID	Name	Country	Population
+1	Kabul	AFG	1780000
+56	Luanda	AGO	2022000
+69	Buenos Aires	ARG	2982146
+70	La Matanza	ARG	1266461
+71	Córdoba	ARG	1157507
+126	Yerevan	ARM	1248700
+130	Sydney	AUS	3276207
+131	Melbourne	AUS	2865329
+132	Brisbane	AUS	1291117
+133	Perth	AUS	1096829
+144	Baku	AZE	1787800
+SELECT * FROM City
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+ID	Name	Country	Population
+1	Kabul	AFG	1780000
+56	Luanda	AGO	2022000
+69	Buenos Aires	ARG	2982146
+70	La Matanza	ARG	1266461
+71	Córdoba	ARG	1157507
+126	Yerevan	ARM	1248700
+130	Sydney	AUS	3276207
+131	Melbourne	AUS	2865329
+132	Brisbane	AUS	1291117
+133	Perth	AUS	1096829
+144	Baku	AZE	1787800
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+ID	Name	Country	Population
+2432	Vientiane	LAO	531800
+2434	Riga	LVA	764328
+2438	Beirut	LBN	1100000
+2440	Monrovia	LBR	850000
+2441	Tripoli	LBY	1682000
+2442	Bengasi	LBY	804000
+2447	Vilnius	LTU	577969
+2448	Kaunas	LTU	412639
+SELECT * FROM City 
+WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+ID	Name	Country	Population
+2432	Vientiane	LAO	531800
+2434	Riga	LVA	764328
+2438	Beirut	LBN	1100000
+2440	Monrovia	LBR	850000
+2441	Tripoli	LBY	1682000
+2442	Bengasi	LBY	804000
+2447	Vilnius	LTU	577969
+2448	Kaunas	LTU	412639
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 3701 AND 4000 AND Population > 700000
+AND Country BETWEEN 'S' AND 'Z';
+ID	Name	Country	Population
+3769	Ho Chi Minh City	VNM	3980000
+3770	Hanoi	VNM	1410000
+3771	Haiphong	VNM	783133
+3793	New York	USA	8008278
+3794	Los Angeles	USA	3694820
+3795	Chicago	USA	2896016
+3796	Houston	USA	1953631
+3797	Philadelphia	USA	1517550
+3798	Phoenix	USA	1321045
+3799	San Diego	USA	1223400
+3800	Dallas	USA	1188580
+3801	San Antonio	USA	1144646
+3802	Detroit	USA	951270
+3803	San Jose	USA	894943
+3804	Indianapolis	USA	791926
+3805	San Francisco	USA	776733
+3806	Jacksonville	USA	735167
+3807	Columbus	USA	711470
+SELECT * FROM City 
+WHERE ID BETWEEN 3701 AND 4000 AND Population > 700000
+AND Country BETWEEN 'S' AND 'Z';
+ID	Name	Country	Population
+3769	Ho Chi Minh City	VNM	3980000
+3770	Hanoi	VNM	1410000
+3771	Haiphong	VNM	783133
+3793	New York	USA	8008278
+3794	Los Angeles	USA	3694820
+3795	Chicago	USA	2896016
+3796	Houston	USA	1953631
+3797	Philadelphia	USA	1517550
+3798	Phoenix	USA	1321045
+3799	San Diego	USA	1223400
+3800	Dallas	USA	1188580
+3801	San Antonio	USA	1144646
+3802	Detroit	USA	951270
+3803	San Jose	USA	894943
+3804	Indianapolis	USA	791926
+3805	San Francisco	USA	776733
+3806	Jacksonville	USA	735167
+3807	Columbus	USA	711470
+SELECT * FROM City USE INDEX ()
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z' ;
+ID	Name	Country	Population
+3048	Stockholm	SWE	750348
+3173	Riyadh	SAU	3324000
+3174	Jedda	SAU	2046300
+3175	Mekka	SAU	965700
+3176	Medina	SAU	608300
+3197	Pikine	SEN	855287
+3198	Dakar	SEN	785071
+3207	Freetown	SLE	850000
+3208	Singapore	SGP	4017733
+3214	Mogadishu	SOM	997000
+3224	Omdurman	SDN	1271403
+3225	Khartum	SDN	947483
+3226	Sharq al-Nil	SDN	700887
+3250	Damascus	SYR	1347000
+3251	Aleppo	SYR	1261983
+3263	Taipei	TWN	2641312
+3264	Kaohsiung	TWN	1475505
+3265	Taichung	TWN	940589
+3266	Tainan	TWN	728060
+3305	Dar es Salaam	TZA	1747000
+3320	Bangkok	THA	6320174
+3349	Tunis	TUN	690600
+3357	Istanbul	TUR	8787958
+3358	Ankara	TUR	3038159
+3359	Izmir	TUR	2130359
+3360	Adana	TUR	1131198
+3361	Bursa	TUR	1095842
+3362	Gaziantep	TUR	789056
+3363	Konya	TUR	628364
+3425	Kampala	UGA	890800
+3426	Kyiv	UKR	2624000
+3427	Harkova [Harkiv]	UKR	1500000
+3428	Dnipropetrovsk	UKR	1103000
+3429	Donetsk	UKR	1050000
+3430	Odesa	UKR	1011000
+3431	Zaporizzja	UKR	848000
+3432	Lviv	UKR	788000
+3433	Kryvyi Rig	UKR	703000
+3492	Montevideo	URY	1236000
+3503	Toskent	UZB	2117500
+3539	Caracas	VEN	1975294
+3540	Maracaíbo	VEN	1304776
+3541	Barquisimeto	VEN	877239
+3542	Valencia	VEN	794246
+3543	Ciudad Guayana	VEN	663713
+3769	Ho Chi Minh City	VNM	3980000
+3770	Hanoi	VNM	1410000
+3771	Haiphong	VNM	783133
+3793	New York	USA	8008278
+3794	Los Angeles	USA	3694820
+3795	Chicago	USA	2896016
+3796	Houston	USA	1953631
+3797	Philadelphia	USA	1517550
+3798	Phoenix	USA	1321045
+3799	San Diego	USA	1223400
+3800	Dallas	USA	1188580
+3801	San Antonio	USA	1144646
+3802	Detroit	USA	951270
+3803	San Jose	USA	894943
+3804	Indianapolis	USA	791926
+3805	San Francisco	USA	776733
+3806	Jacksonville	USA	735167
+3807	Columbus	USA	711470
+3808	Austin	USA	656562
+3809	Baltimore	USA	651154
+3810	Memphis	USA	650100
+SELECT * FROM City 
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z' ;
+ID	Name	Country	Population
+3048	Stockholm	SWE	750348
+3173	Riyadh	SAU	3324000
+3174	Jedda	SAU	2046300
+3175	Mekka	SAU	965700
+3176	Medina	SAU	608300
+3197	Pikine	SEN	855287
+3198	Dakar	SEN	785071
+3207	Freetown	SLE	850000
+3208	Singapore	SGP	4017733
+3214	Mogadishu	SOM	997000
+3224	Omdurman	SDN	1271403
+3225	Khartum	SDN	947483
+3226	Sharq al-Nil	SDN	700887
+3250	Damascus	SYR	1347000
+3251	Aleppo	SYR	1261983
+3263	Taipei	TWN	2641312
+3264	Kaohsiung	TWN	1475505
+3265	Taichung	TWN	940589
+3266	Tainan	TWN	728060
+3305	Dar es Salaam	TZA	1747000
+3320	Bangkok	THA	6320174
+3349	Tunis	TUN	690600
+3357	Istanbul	TUR	8787958
+3358	Ankara	TUR	3038159
+3359	Izmir	TUR	2130359
+3360	Adana	TUR	1131198
+3361	Bursa	TUR	1095842
+3362	Gaziantep	TUR	789056
+3363	Konya	TUR	628364
+3425	Kampala	UGA	890800
+3426	Kyiv	UKR	2624000
+3427	Harkova [Harkiv]	UKR	1500000
+3428	Dnipropetrovsk	UKR	1103000
+3429	Donetsk	UKR	1050000
+3430	Odesa	UKR	1011000
+3431	Zaporizzja	UKR	848000
+3432	Lviv	UKR	788000
+3433	Kryvyi Rig	UKR	703000
+3492	Montevideo	URY	1236000
+3503	Toskent	UZB	2117500
+3539	Caracas	VEN	1975294
+3540	Maracaíbo	VEN	1304776
+3541	Barquisimeto	VEN	877239
+3542	Valencia	VEN	794246
+3543	Ciudad Guayana	VEN	663713
+3769	Ho Chi Minh City	VNM	3980000
+3770	Hanoi	VNM	1410000
+3771	Haiphong	VNM	783133
+3793	New York	USA	8008278
+3794	Los Angeles	USA	3694820
+3795	Chicago	USA	2896016
+3796	Houston	USA	1953631
+3797	Philadelphia	USA	1517550
+3798	Phoenix	USA	1321045
+3799	San Diego	USA	1223400
+3800	Dallas	USA	1188580
+3801	San Antonio	USA	1144646
+3802	Detroit	USA	951270
+3803	San Jose	USA	894943
+3804	Indianapolis	USA	791926
+3805	San Francisco	USA	776733
+3806	Jacksonville	USA	735167
+3807	Columbus	USA	711470
+3808	Austin	USA	656562
+3809	Baltimore	USA	651154
+3810	Memphis	USA	650100
+SET SESSION sort_buffer_size = 2048;
+EXPLAIN
+SELECT * FROM City WHERE
+Name LIKE 'C%' AND Population > 1000000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Population,Name	4,35	NULL	16	Using sort_intersect(Population,Name); Using where
+EXPLAIN
+SELECT * FROM City WHERE
+Name LIKE 'M%' AND Population > 1500000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name	Population,Name	4,35	NULL	9	Using sort_intersect(Population,Name); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE  Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Population,Country,Name	4,3,35	NULL	2	Using sort_intersect(Population,Country,Name); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE  Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Country,Name	Name,Population,Country	35,4,3	NULL	7	Using sort_intersect(Name,Population,Country); Using where
+EXPLAIN
+SELECT * FROM City
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	PRIMARY,Population,Country	4,4,3	NULL	1	Using sort_intersect(PRIMARY,Population,Country); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	PRIMARY,Population,Country	PRIMARY,Country,Population	4,3,4	NULL	30	Using sort_intersect(PRIMARY,Country,Population); Using where
+SELECT * FROM City WHERE
+Name LIKE 'C%' AND Population > 1000000;
+ID	Name	Country	Population
+71	Córdoba	ARG	1157507
+151	Chittagong	BGD	1392860
+212	Curitiba	BRA	1584232
+608	Cairo	EGY	6789479
+712	Cape Town	ZAF	2352121
+926	Conakry	GIN	1090610
+1026	Calcutta [Kolkata]	IND	4399819
+1027	Chennai (Madras)	IND	3841396
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+2258	Cali	COL	2077386
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+3539	Caracas	VEN	1975294
+3795	Chicago	USA	2896016
+SELECT * FROM City WHERE
+Name LIKE 'M%' AND Population > 1500000;
+ID	Name	Country	Population
+131	Melbourne	AUS	2865329
+653	Madrid	ESP	2879052
+766	Manila	PHL	1581082
+942	Medan	IDN	1843919
+1024	Mumbai (Bombay)	IND	10500000
+1381	Mashhad	IRN	1887405
+2259	Medellín	COL	1861265
+3520	Minsk	BLR	1674000
+3580	Moscow	RUS	8389200
+SELECT * FROM City 
+WHERE  Name BETWEEN 'G' AND 'J' AND Population > 700000 AND Country LIKE 'B%';
+ID	Name	Country	Population
+217	Guarulhos	BRA	1095874
+218	Goiânia	BRA	1056330
+SELECT * FROM City 
+WHERE  Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+ID	Name	Country	Population
+1895	Harbin	CHN	4289800
+1905	Hangzhou	CHN	2190500
+1914	Guiyang	CHN	1465200
+1916	Hefei	CHN	1369100
+1927	Hohhot	CHN	916700
+1928	Handan	CHN	840000
+1937	Huainan	CHN	700000
+1950	Hegang	CHN	520000
+SELECT * FROM City
+WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+ID	Name	Country	Population
+1	Kabul	AFG	1780000
+56	Luanda	AGO	2022000
+69	Buenos Aires	ARG	2982146
+70	La Matanza	ARG	1266461
+71	Córdoba	ARG	1157507
+126	Yerevan	ARM	1248700
+130	Sydney	AUS	3276207
+131	Melbourne	AUS	2865329
+132	Brisbane	AUS	1291117
+133	Perth	AUS	1096829
+144	Baku	AZE	1787800
+SELECT * FROM City 
+WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+AND Country BETWEEN 'S' AND 'Z';
+ID	Name	Country	Population
+3048	Stockholm	SWE	750348
+3173	Riyadh	SAU	3324000
+3174	Jedda	SAU	2046300
+3175	Mekka	SAU	965700
+3176	Medina	SAU	608300
+3197	Pikine	SEN	855287
+3198	Dakar	SEN	785071
+3207	Freetown	SLE	850000
+3208	Singapore	SGP	4017733
+3214	Mogadishu	SOM	997000
+3224	Omdurman	SDN	1271403
+3225	Khartum	SDN	947483
+3226	Sharq al-Nil	SDN	700887
+3250	Damascus	SYR	1347000
+3251	Aleppo	SYR	1261983
+3263	Taipei	TWN	2641312
+3264	Kaohsiung	TWN	1475505
+3265	Taichung	TWN	940589
+3266	Tainan	TWN	728060
+3305	Dar es Salaam	TZA	1747000
+3320	Bangkok	THA	6320174
+3349	Tunis	TUN	690600
+3357	Istanbul	TUR	8787958
+3358	Ankara	TUR	3038159
+3359	Izmir	TUR	2130359
+3360	Adana	TUR	1131198
+3361	Bursa	TUR	1095842
+3362	Gaziantep	TUR	789056
+3363	Konya	TUR	628364
+3425	Kampala	UGA	890800
+3426	Kyiv	UKR	2624000
+3427	Harkova [Harkiv]	UKR	1500000
+3428	Dnipropetrovsk	UKR	1103000
+3429	Donetsk	UKR	1050000
+3430	Odesa	UKR	1011000
+3431	Zaporizzja	UKR	848000
+3432	Lviv	UKR	788000
+3433	Kryvyi Rig	UKR	703000
+3492	Montevideo	URY	1236000
+3503	Toskent	UZB	2117500
+3539	Caracas	VEN	1975294
+3540	Maracaíbo	VEN	1304776
+3541	Barquisimeto	VEN	877239
+3542	Valencia	VEN	794246
+3543	Ciudad Guayana	VEN	663713
+3769	Ho Chi Minh City	VNM	3980000
+3770	Hanoi	VNM	1410000
+3771	Haiphong	VNM	783133
+3793	New York	USA	8008278
+3794	Los Angeles	USA	3694820
+3795	Chicago	USA	2896016
+3796	Houston	USA	1953631
+3797	Philadelphia	USA	1517550
+3798	Phoenix	USA	1321045
+3799	San Diego	USA	1223400
+3800	Dallas	USA	1188580
+3801	San Antonio	USA	1144646
+3802	Detroit	USA	951270
+3803	San Jose	USA	894943
+3804	Indianapolis	USA	791926
+3805	San Francisco	USA	776733
+3806	Jacksonville	USA	735167
+3807	Columbus	USA	711470
+3808	Austin	USA	656562
+3809	Baltimore	USA	651154
+3810	Memphis	USA	650100
+SET SESSION sort_buffer_size = default;
+DROP INDEX Country ON City;
+CREATE INDEX CountryID ON City(Country,ID);
+CREATE INDEX CountryName ON City(Country,Name);
+EXPLAIN
+SELECT * FROM City 
+WHERE Country LIKE 'M%' AND Population > 1000000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,CountryID,CountryName	Population,CountryID	4,3	NULL	16	Using sort_intersect(Population,CountryID); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Country='CHN' AND Population > 1500000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,CountryID,CountryName	Population,CountryID	4,3	NULL	11	Using sort_intersect(Population,CountryID); Using where
+EXPLAIN
+SELECT * FROM City 
+WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	range	Population,Name,CountryID,CountryName	CountryName,Population	38,4	NULL	1	Using sort_intersect(CountryName,Population); Using where
+SELECT * FROM City USE INDEX ()
+WHERE Country LIKE 'M%' AND Population > 1000000;
+ID	Name	Country	Population
+2464	Kuala Lumpur	MYS	1297526
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+2516	Guadalajara	MEX	1647720
+2517	Ecatepec de Morelos	MEX	1620303
+2518	Puebla	MEX	1346176
+2519	Nezahualcóyotl	MEX	1224924
+2520	Juárez	MEX	1217818
+2521	Tijuana	MEX	1212232
+2522	León	MEX	1133576
+2523	Monterrey	MEX	1108499
+2524	Zapopan	MEX	1002239
+2698	Maputo	MOZ	1018938
+2710	Rangoon (Yangon)	MMR	3361700
+SELECT * FROM City 
+WHERE Country LIKE 'M%' AND Population > 700000;
+ID	Name	Country	Population
+2464	Kuala Lumpur	MYS	1297526
+2482	Bamako	MLI	809552
+2485	Casablanca	MAR	2940623
+2515	Ciudad de México	MEX	8591309
+2516	Guadalajara	MEX	1647720
+2517	Ecatepec de Morelos	MEX	1620303
+2518	Puebla	MEX	1346176
+2519	Nezahualcóyotl	MEX	1224924
+2520	Juárez	MEX	1217818
+2521	Tijuana	MEX	1212232
+2522	León	MEX	1133576
+2523	Monterrey	MEX	1108499
+2524	Zapopan	MEX	1002239
+2525	Naucalpan de Juárez	MEX	857511
+2526	Mexicali	MEX	764902
+2527	Culiacán	MEX	744859
+2528	Acapulco de Juárez	MEX	721011
+2529	Tlalnepantla de Baz	MEX	720755
+2530	Mérida	MEX	703324
+2690	Chisinau	MDA	719900
+2696	Ulan Bator	MNG	773700
+2698	Maputo	MOZ	1018938
+2710	Rangoon (Yangon)	MMR	3361700
+2711	Mandalay	MMR	885300
+SELECT * FROM City USE INDEX ()
+WHERE Country='CHN' AND Population > 1500000;
+ID	Name	Country	Population
+1890	Shanghai	CHN	9696300
+1891	Peking	CHN	7472000
+1892	Chongqing	CHN	6351600
+1893	Tianjin	CHN	5286800
+1894	Wuhan	CHN	4344600
+1895	Harbin	CHN	4289800
+1896	Shenyang	CHN	4265200
+1897	Kanton [Guangzhou]	CHN	4256300
+1898	Chengdu	CHN	3361500
+1899	Nanking [Nanjing]	CHN	2870300
+1900	Changchun	CHN	2812000
+1901	Xi´an	CHN	2761400
+1902	Dalian	CHN	2697000
+1903	Qingdao	CHN	2596000
+1904	Jinan	CHN	2278100
+1905	Hangzhou	CHN	2190500
+1906	Zhengzhou	CHN	2107200
+1907	Shijiazhuang	CHN	2041500
+1908	Taiyuan	CHN	1968400
+1909	Kunming	CHN	1829500
+1910	Changsha	CHN	1809800
+1911	Nanchang	CHN	1691600
+1912	Fuzhou	CHN	1593800
+1913	Lanzhou	CHN	1565800
+SELECT * FROM City 
+WHERE Country='CHN' AND Population > 1500000;
+ID	Name	Country	Population
+1890	Shanghai	CHN	9696300
+1891	Peking	CHN	7472000
+1892	Chongqing	CHN	6351600
+1893	Tianjin	CHN	5286800
+1894	Wuhan	CHN	4344600
+1895	Harbin	CHN	4289800
+1896	Shenyang	CHN	4265200
+1897	Kanton [Guangzhou]	CHN	4256300
+1898	Chengdu	CHN	3361500
+1899	Nanking [Nanjing]	CHN	2870300
+1900	Changchun	CHN	2812000
+1901	Xi´an	CHN	2761400
+1902	Dalian	CHN	2697000
+1903	Qingdao	CHN	2596000
+1904	Jinan	CHN	2278100
+1905	Hangzhou	CHN	2190500
+1906	Zhengzhou	CHN	2107200
+1907	Shijiazhuang	CHN	2041500
+1908	Taiyuan	CHN	1968400
+1909	Kunming	CHN	1829500
+1910	Changsha	CHN	1809800
+1911	Nanchang	CHN	1691600
+1912	Fuzhou	CHN	1593800
+1913	Lanzhou	CHN	1565800
+SELECT * FROM City USE INDEX ()
+WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+ID	Name	Country	Population
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+SELECT * FROM City 
+WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+ID	Name	Country	Population
+1892	Chongqing	CHN	6351600
+1898	Chengdu	CHN	3361500
+1900	Changchun	CHN	2812000
+1910	Changsha	CHN	1809800
+DROP DATABASE world;
+use test;
+CREATE TABLE t1 (
+f1 int,
+f4 varchar(32),
+f5 int,
+PRIMARY KEY (f1),
+KEY (f4)
+) ENGINE=InnoDB;
+INSERT INTO t1 VALUES 
+(5,'H',1), (9,'g',0), (527,'i',0), (528,'y',1), (529,'S',6),
+(530,'m',7), (531,'b',2), (532,'N',1), (533,'V',NULL), (534,'l',1),
+(535,'M',0), (536,'w',1), (537,'j',5), (538,'l',0), (539,'n',2),
+(540,'m',2), (541,'r',2), (542,'l',2), (543,'h',3),(544,'o',0),
+(956,'h',0), (957,'g',0), (958,'W',5), (959,'s',3), (960,'w',0),
+(961,'q',0), (962,'e',NULL), (963,'u',7), (964,'q',1), (965,'N',NULL),
+(966,'e',0), (967,'t',3), (968,'e',6), (969,'f',NULL), (970,'j',0),
+(971,'s',3), (972,'I',0), (973,'h',4), (974,'g',1), (975,'s',0),
+(976,'r',3), (977,'x',1), (978,'v',8), (979,'j',NULL), (980,'z',7),
+(981,'t',9), (982,'j',5), (983,'u',NULL), (984,'g',6), (985,'w',1),
+(986,'h',1), (987,'v',0), (988,'v',0), (989,'c',2), (990,'b',7),
+(991,'z',0), (992,'M',1), (993,'u',2), (994,'r',2), (995,'b',4),
+(996,'A',2), (997,'u',0), (998,'a',0), (999,'j',2), (1,'I',2);
+EXPLAIN
+SELECT * FROM t1
+WHERE (f1 < 535  OR  f1 > 985) AND ( f4='r' OR f4 LIKE 'a%' ) ;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	PRIMARY,f4	PRIMARY,f4	4,35	NULL	1	Using sort_intersect(PRIMARY,f4); Using where
+SELECT * FROM t1
+WHERE (f1 < 535  OR  f1 > 985) AND ( f4='r' OR f4 LIKE 'a%' ) ;
+f1	f4	f5
+994	r	2
+996	A	2
+998	a	0
+DROP TABLE t1;
+SET SESSION optimizer_switch='index_merge_sort_intersection=on';
+SET SESSION STORAGE_ENGINE=DEFAULT;
diff --git a/mysql-test/r/index_merge_innodb.result b/mysql-test/r/index_merge_innodb.result
index fdc5b57a2e3..e8fda5b4655 100644
--- a/mysql-test/r/index_merge_innodb.result
+++ b/mysql-test/r/index_merge_innodb.result
@@ -1,3 +1,5 @@
+set @optimizer_switch_save= @@optimizer_switch;
+set optimizer_switch='index_merge_sort_intersection=off';
 #---------------- Index merge test 2 -------------------------------------------
 SET SESSION STORAGE_ENGINE = InnoDB;
 drop table if exists t1,t2;
@@ -709,3 +711,4 @@ WHERE a BETWEEN 2 AND 7 OR pk=1000000) AS t;
 COUNT(*)
 6145
 DROP TABLE t1;
+set optimizer_switch= @optimizer_switch_save;
diff --git a/mysql-test/r/index_merge_myisam.result b/mysql-test/r/index_merge_myisam.result
index db0b4abb7d5..01465ea6483 100644
--- a/mysql-test/r/index_merge_myisam.result
+++ b/mysql-test/r/index_merge_myisam.result
@@ -1,3 +1,5 @@
+set @optimizer_switch_save= @@optimizer_switch;
+set optimizer_switch='index_merge_sort_intersection=off';
 #---------------- Index merge test 1 -------------------------------------------
 SET SESSION STORAGE_ENGINE = MyISAM;
 drop table if exists t0, t1, t2, t3, t4;
@@ -205,10 +207,10 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	index_merge	i1_3,i2_3	i1_3,i2_3	4,4	NULL	2	Using sort_union(i1_3,i2_3); Using where
 explain select key3 from t2 where key1 <100 or key2 < 100;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	index	i1_3,i2_3	i321	12	NULL	1024	Using where; Using index
+1	SIMPLE	t2	index_merge	i1_3,i2_3	i1_3,i2_3	4,4	NULL	188	Using sort_union(i1_3,i2_3); Using where
 explain select key7 from t2 where key1 <100 or key2 < 100;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	i1_3,i2_3	NULL	NULL	NULL	1024	Using where
+1	SIMPLE	t2	index_merge	i1_3,i2_3	i1_3,i2_3	4,4	NULL	188	Using sort_union(i1_3,i2_3); Using where
 create table t4 (
 key1a int not null,
 key1b int not null,
@@ -569,9 +571,7 @@ INSERT INTO t1 SELECT * FROM t1;
 INSERT INTO t1 SELECT * FROM t1;
 INSERT INTO t1 SELECT * FROM t1;
 INSERT INTO t1 SELECT * FROM t1;
-SET SESSION sort_buffer_size=1;
-Warnings:
-Warning	1292	Truncated incorrect sort_buffer_size value: '1'
+SET SESSION sort_buffer_size=1024*8;
 EXPLAIN 
 SELECT * FROM t1 FORCE INDEX(a,b) WHERE a LIKE 'a%' OR b LIKE 'b%' 
 ORDER BY a,b;
@@ -1494,19 +1494,19 @@ DROP TABLE t1,t2;
 #
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=off
 set optimizer_switch='index_merge=off,index_merge_union=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on
+index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=off
 set optimizer_switch='index_merge_union=on';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=off,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on
+index_merge=off,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=off
 set optimizer_switch='default,index_merge_sort_union=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=off,index_merge_intersection=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=off,index_merge_intersection=on,index_merge_sort_intersection=on
 set optimizer_switch=4;
 ERROR 42000: Variable 'optimizer_switch' can't be set to the value of '4'
 set optimizer_switch=NULL;
@@ -1533,21 +1533,21 @@ set optimizer_switch=default;
 set optimizer_switch='index_merge=off,index_merge_union=off,default';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on
+index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=on
 set optimizer_switch=default;
 select @@global.optimizer_switch;
 @@global.optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=on
 set @@global.optimizer_switch=default;
 select @@global.optimizer_switch;
 @@global.optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=on
 #
 # Check index_merge's @@optimizer_switch flags
 #
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=on
 create table t0 (a int);
 insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
 create table t1 (a int, b int, c int, filler char(100), 
@@ -1624,7 +1624,7 @@ explain select * from t1 where a=10 and b=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	a,b	a	5	const	49	Using where
 No intersect if it is disabled:
-set optimizer_switch='default,index_merge_intersection=off';
+set optimizer_switch='default,index_merge_sort_intersection=off,index_merge_intersection=off';
 explain select * from t1 where a=10 and b=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	a,b	a	5	const	49	Using where
@@ -1657,5 +1657,6 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 set optimizer_switch=default;
 show variables like 'optimizer_switch';
 Variable_name	Value
-optimizer_switch	index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on
+optimizer_switch	index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=on
 drop table t0, t1;
+set optimizer_switch= @optimizer_switch_save;
diff --git a/mysql-test/r/order_by.result b/mysql-test/r/order_by.result
index ba639fa9763..eea5e1166b8 100644
--- a/mysql-test/r/order_by.result
+++ b/mysql-test/r/order_by.result
@@ -1421,9 +1421,9 @@ DROP TABLE t1;
 #
 create table t1(a int, b tinytext);
 insert into t1 values (1,2),(3,2);
-set session sort_buffer_size= 30000;
+set session sort_buffer_size= 1000;
 Warnings:
-Warning	1292	Truncated incorrect sort_buffer_size value: '30000'
+Warning	1292	Truncated incorrect sort_buffer_size value: '1000'
 set session max_sort_length= 2180;
 select * from t1 order by b;
 ERROR HY001: Out of sort memory; increase server sort buffer size
diff --git a/mysql-test/r/range_vs_index_merge.result b/mysql-test/r/range_vs_index_merge.result
index dccb2e3b836..a8b6ab8272f 100644
--- a/mysql-test/r/range_vs_index_merge.result
+++ b/mysql-test/r/range_vs_index_merge.result
@@ -38,6 +38,7 @@ SELECT COUNT(*) FROM CountryLanguage;
 COUNT(*)
 984
 CREATE INDEX Name ON City(Name);
+set session optimizer_switch='index_merge_sort_intersection=off';
 EXPLAIN
 SELECT * FROM City
 WHERE (Population >= 100000 OR Name LIKE 'P%' OR Population < 100000);
@@ -71,9 +72,9 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	range	Population	Population	4	NULL	459	Using where
 EXPLAIN 
 SELECT * FROM City
-WHERE (Population > 101000 AND Population < 103000);
+WHERE (Population > 101000 AND Population < 102000);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	Population	Population	4	NULL	81	Using where
+1	SIMPLE	City	range	Population	Population	4	NULL	39	Using where
 EXPLAIN 
 SELECT * FROM City
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'));
@@ -88,9 +89,9 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 EXPLAIN 
 SELECT * FROM City
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-AND (Population > 101000 AND Population < 103000);
+AND (Population > 101000 AND Population < 102000);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	Population,Country,Name	Population	4	NULL	81	Using where
+1	SIMPLE	City	range	Population,Country,Name	Population	4	NULL	39	Using where
 SELECT * FROM City USE INDEX ()
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
 AND (Population > 101000 AND Population < 115000);
@@ -153,24 +154,20 @@ ID	Name	Country	Population
 4032	Cambridge	USA	101355
 SELECT * FROM City USE INDEX ()
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-AND (Population > 101000 AND Population < 103000);
+AND (Population > 101000 AND Population < 102000);
 ID	Name	Country	Population
 637	Mit Ghamr	EGY	101801
 707	Marbella	ESP	101144
-3411	Ceyhan	TUR	102412
 3792	Tartu	EST	101246
-4027	Cape Coral	USA	102286
 4032	Cambridge	USA	101355
 SELECT * FROM City
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-AND (Population > 101000 AND Population < 103000);
+AND (Population > 101000 AND Population < 102000);
 ID	Name	Country	Population
 707	Marbella	ESP	101144
 3792	Tartu	EST	101246
 4032	Cambridge	USA	101355
 637	Mit Ghamr	EGY	101801
-4027	Cape Coral	USA	102286
-3411	Ceyhan	TUR	102412
 EXPLAIN
 SELECT  * FROM City WHERE (Name < 'Ac');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
@@ -328,9 +325,9 @@ ID	Name	Country	Population
 1003	Pemalang	IDN	103500
 2663	Río Bravo	MEX	103901
 EXPLAIN
-SELECT * FROM City WHERE (ID < 50) OR (ID BETWEEN 100 AND 110);
+SELECT * FROM City WHERE (ID < 30) OR (ID BETWEEN 100 AND 150);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	PRIMARY	PRIMARY	4	NULL	61	Using where
+1	SIMPLE	City	range	PRIMARY	PRIMARY	4	NULL	81	Using where
 EXPLAIN
 SELECT * FROM City WHERE (ID < 200) OR (ID BETWEEN 300 AND 600);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
@@ -353,11 +350,11 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	range	Name	Name	35	NULL	72	Using where
 EXPLAIN
 SELECT * FROM City
-WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
 OR ((ID BETWEEN 100 AND 110) AND 
 (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	PRIMARY,Population,Country,Name	PRIMARY	4	NULL	61	Using where
+1	SIMPLE	City	range	PRIMARY,Population,Country,Name	PRIMARY	4	NULL	41	Using where
 EXPLAIN
 SELECT * FROM City
 WHERE ((ID < 800) AND (Name LIKE 'Ha%' OR (Country > 'A' AND Country < 'ARG')))
@@ -373,7 +370,7 @@ OR ((ID BETWEEN 300 AND 600) AND
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	index_merge	PRIMARY,Population,Country,Name	Name,Country,Population	35,3,4	NULL	128	Using sort_union(Name,Country,Population); Using where
 SELECT * FROM City USE INDEX ()
-WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
 OR ((ID BETWEEN 100 AND 110) AND 
 (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 ID	Name	Country	Population
@@ -384,13 +381,10 @@ ID	Name	Country	Population
 7	Haag	NLD	440900
 16	Haarlem	NLD	148772
 25	Haarlemmermeer	NLD	110722
-31	Heerlen	NLD	95052
-33	Willemstad	ANT	2345
-34	Tirana	ALB	270000
 100	Paraná	ARG	207041
 102	Posadas	ARG	201273
 SELECT * FROM City
-WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
 OR ((ID BETWEEN 100 AND 110) AND 
 (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 ID	Name	Country	Population
@@ -401,9 +395,6 @@ ID	Name	Country	Population
 7	Haag	NLD	440900
 16	Haarlem	NLD	148772
 25	Haarlemmermeer	NLD	110722
-31	Heerlen	NLD	95052
-33	Willemstad	ANT	2345
-34	Tirana	ALB	270000
 100	Paraná	ARG	207041
 102	Posadas	ARG	201273
 SELECT * FROM City USE INDEX()
@@ -726,119 +717,55 @@ SELECT * FROM City WHERE Name LIKE 'P%';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	range	Name	Name	35	NULL	135	Using where
 EXPLAIN
-SELECT * FROM City WHERE (Population > 101000 AND Population < 103000);
+SELECT * FROM City WHERE (Population > 101000 AND Population < 102000);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	Population	Population	4	NULL	81	Using where
+1	SIMPLE	City	range	Population	Population	4	NULL	39	Using where
 EXPLAIN
 SELECT * FROM City WHERE Country='USA';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	ref	Country,CountryPopulation	Country	3	const	267	Using where
 EXPLAIN
 SELECT * FROM City 
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
 AND Country='USA';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	index_merge	Population,Country,Name,CountryPopulation	CountryPopulation,Name	7,35	NULL	15	Using sort_union(CountryPopulation,Name); Using where
+1	SIMPLE	City	index_merge	Population,Country,Name,CountryPopulation	CountryPopulation,Name	7,35	NULL	8	Using sort_union(CountryPopulation,Name); Using where
 EXPLAIN
 SELECT * FROM City 
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-AND Country='USA';
+WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%' )
+AND Country='USA' AND Name LIKE '%port';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	ref	Population,Country,Name,CountryPopulation	Country	3	const	267	Using where
 SELECT * FROM City 
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
 AND Country='USA';
 ID	Name	Country	Population
 3943	Pasadena	USA	141674
 3953	Pasadena	USA	133936
-4023	Gary	USA	102746
-4024	Berkeley	USA	102743
-4025	Santa Clara	USA	102361
-4026	Green Bay	USA	102313
-4027	Cape Coral	USA	102286
-4028	Arvada	USA	102153
-4029	Pueblo	USA	102121
 4030	Sandy	USA	101853
 4031	Athens-Clarke County	USA	101489
 4032	Cambridge	USA	101355
 SELECT * FROM City USE INDEX ()
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
 AND Country='USA';
 ID	Name	Country	Population
 3943	Pasadena	USA	141674
 3953	Pasadena	USA	133936
-4023	Gary	USA	102746
-4024	Berkeley	USA	102743
-4025	Santa Clara	USA	102361
-4026	Green Bay	USA	102313
-4027	Cape Coral	USA	102286
-4028	Arvada	USA	102153
-4029	Pueblo	USA	102121
 4030	Sandy	USA	101853
 4031	Athens-Clarke County	USA	101489
 4032	Cambridge	USA	101355
 SELECT * FROM City 
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-AND Country='USA';
+WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%')
+AND Country='USA' AND Name LIKE '%port';
 ID	Name	Country	Population
-3797	Philadelphia	USA	1517550
-3798	Phoenix	USA	1321045
-3820	Portland	USA	529121
-3844	Pittsburgh	USA	334563
-3870	Plano	USA	222030
-3912	Providence	USA	173618
-3930	Pomona	USA	149473
-3932	Paterson	USA	149222
-3943	Pasadena	USA	141674
-3951	Pembroke Pines	USA	137427
-3953	Pasadena	USA	133936
-3967	Paradise	USA	124682
-3986	Palmdale	USA	116670
-3996	Peoria	USA	112936
-4007	Peoria	USA	108364
-4016	Provo	USA	105166
-4023	Gary	USA	102746
-4024	Berkeley	USA	102743
-4025	Santa Clara	USA	102361
-4026	Green Bay	USA	102313
-4027	Cape Coral	USA	102286
-4028	Arvada	USA	102153
-4029	Pueblo	USA	102121
-4030	Sandy	USA	101853
-4031	Athens-Clarke County	USA	101489
-4032	Cambridge	USA	101355
-4035	Portsmouth	USA	100565
+3880	Shreveport	USA	200145
+3946	Bridgeport	USA	139529
 SELECT * FROM City USE INDEX ()
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-AND Country='USA';
+WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%')
+AND Country='USA' AND Name LIKE '%port';
 ID	Name	Country	Population
-3797	Philadelphia	USA	1517550
-3798	Phoenix	USA	1321045
-3820	Portland	USA	529121
-3844	Pittsburgh	USA	334563
-3870	Plano	USA	222030
-3912	Providence	USA	173618
-3930	Pomona	USA	149473
-3932	Paterson	USA	149222
-3943	Pasadena	USA	141674
-3951	Pembroke Pines	USA	137427
-3953	Pasadena	USA	133936
-3967	Paradise	USA	124682
-3986	Palmdale	USA	116670
-3996	Peoria	USA	112936
-4007	Peoria	USA	108364
-4016	Provo	USA	105166
-4023	Gary	USA	102746
-4024	Berkeley	USA	102743
-4025	Santa Clara	USA	102361
-4026	Green Bay	USA	102313
-4027	Cape Coral	USA	102286
-4028	Arvada	USA	102153
-4029	Pueblo	USA	102121
-4030	Sandy	USA	101853
-4031	Athens-Clarke County	USA	101489
-4032	Cambridge	USA	101355
-4035	Portsmouth	USA	100565
+3880	Shreveport	USA	200145
+3946	Bridgeport	USA	139529
 CREATE INDEX CountryName ON City(Country,Name);
 EXPLAIN
 SELECT * FROM City WHERE Country='USA';
@@ -900,9 +827,10 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	index_merge	PRIMARY,Population,Country,Name,CountryPopulation,CountryName	CountryName,PRIMARY	38,4	NULL	11	Using sort_union(CountryName,PRIMARY); Using where
 EXPLAIN
 SELECT * FROM City
-WHERE ((Population > 101000 AND Population < 110000) OR
-ID BETWEEN 3500 AND 3800) AND Country='USA'
-        AND (Name BETWEEN 'P' AND 'T' OR ID BETWEEN 4000 AND 4300);
+WHERE ((Population > 101000 AND Population < 1000000) OR
+ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+AND Name LIKE '%port';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	ref	PRIMARY,Population,Country,Name,CountryPopulation,CountryName	Country	3	const	267	Using where
 SELECT * FROM City USE INDEX ()
@@ -938,21 +866,21 @@ ID	Name	Country	Population
 4031	Athens-Clarke County	USA	101489
 4032	Cambridge	USA	101355
 SELECT * FROM City USE INDEX ()
-WHERE ((Population > 101000 AND Population < 102000) OR
-ID BETWEEN 3790 AND 3800) AND Country='USA'
-        AND (Name LIKE 'Pa%' OR ID BETWEEN 4025 AND 4035);
+WHERE ((Population > 101000 AND Population < 1000000) OR
+ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+AND Name LIKE '%port';
 ID	Name	Country	Population
-4030	Sandy	USA	101853
-4031	Athens-Clarke County	USA	101489
-4032	Cambridge	USA	101355
+3880	Shreveport	USA	200145
+3946	Bridgeport	USA	139529
 SELECT * FROM City
-WHERE ((Population > 101000 AND Population < 102000) OR
-ID BETWEEN 3790 AND 3800) AND Country='USA'
-        AND (Name LIKE 'Pa%' OR ID BETWEEN 4025 AND 4035);
+WHERE ((Population > 101000 AND Population < 1000000) OR
+ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+AND Name LIKE '%port';
 ID	Name	Country	Population
-4030	Sandy	USA	101853
-4031	Athens-Clarke County	USA	101489
-4032	Cambridge	USA	101355
+3880	Shreveport	USA	200145
+3946	Bridgeport	USA	139529
 EXPLAIN
 SELECT * FROM City
 WHERE ((Population > 101000 and Population < 102000) OR
@@ -1460,3 +1388,4 @@ f1	f2	f3	f4
 9	0	2	6
 SET SESSION optimizer_switch=DEFAULT;
 DROP TABLE t1;
+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 ae831aa10b5..051b2c3bb65 100644
--- a/mysql-test/r/range_vs_index_merge_innodb.result
+++ b/mysql-test/r/range_vs_index_merge_innodb.result
@@ -39,6 +39,7 @@ SELECT COUNT(*) FROM CountryLanguage;
 COUNT(*)
 984
 CREATE INDEX Name ON City(Name);
+set session optimizer_switch='index_merge_sort_intersection=off';
 EXPLAIN
 SELECT * FROM City
 WHERE (Population >= 100000 OR Name LIKE 'P%' OR Population < 100000);
@@ -72,9 +73,9 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	range	Population	Population	4	NULL	458	Using where
 EXPLAIN 
 SELECT * FROM City
-WHERE (Population > 101000 AND Population < 103000);
+WHERE (Population > 101000 AND Population < 102000);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	Population	Population	4	NULL	80	Using where
+1	SIMPLE	City	range	Population	Population	4	NULL	38	Using where
 EXPLAIN 
 SELECT * FROM City
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'));
@@ -89,9 +90,9 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 EXPLAIN 
 SELECT * FROM City
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-AND (Population > 101000 AND Population < 103000);
+AND (Population > 101000 AND Population < 102000);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	Population,Country,Name	Population	4	NULL	80	Using where
+1	SIMPLE	City	range	Population,Country,Name	Population	4	NULL	38	Using where
 SELECT * FROM City USE INDEX ()
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
 AND (Population > 101000 AND Population < 115000);
@@ -154,24 +155,20 @@ ID	Name	Country	Population
 4032	Cambridge	USA	101355
 SELECT * FROM City USE INDEX ()
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-AND (Population > 101000 AND Population < 103000);
+AND (Population > 101000 AND Population < 102000);
 ID	Name	Country	Population
 637	Mit Ghamr	EGY	101801
 707	Marbella	ESP	101144
-3411	Ceyhan	TUR	102412
 3792	Tartu	EST	101246
-4027	Cape Coral	USA	102286
 4032	Cambridge	USA	101355
 SELECT * FROM City
 WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-AND (Population > 101000 AND Population < 103000);
+AND (Population > 101000 AND Population < 102000);
 ID	Name	Country	Population
 707	Marbella	ESP	101144
 3792	Tartu	EST	101246
 4032	Cambridge	USA	101355
 637	Mit Ghamr	EGY	101801
-4027	Cape Coral	USA	102286
-3411	Ceyhan	TUR	102412
 EXPLAIN
 SELECT  * FROM City WHERE (Name < 'Ac');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
@@ -329,9 +326,9 @@ ID	Name	Country	Population
 1003	Pemalang	IDN	103500
 2663	Río Bravo	MEX	103901
 EXPLAIN
-SELECT * FROM City WHERE (ID < 50) OR (ID BETWEEN 100 AND 110);
+SELECT * FROM City WHERE (ID < 30) OR (ID BETWEEN 100 AND 150);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	PRIMARY	PRIMARY	4	NULL	60	Using where
+1	SIMPLE	City	range	PRIMARY	PRIMARY	4	NULL	79	Using where
 EXPLAIN
 SELECT * FROM City WHERE (ID < 200) OR (ID BETWEEN 300 AND 600);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
@@ -354,11 +351,11 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	range	Name	Name	35	NULL	133	Using where
 EXPLAIN
 SELECT * FROM City
-WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
 OR ((ID BETWEEN 100 AND 110) AND 
 (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	PRIMARY,Population,Country,Name	PRIMARY	4	NULL	60	Using where
+1	SIMPLE	City	range	PRIMARY,Population,Country,Name	PRIMARY	4	NULL	40	Using where
 EXPLAIN
 SELECT * FROM City
 WHERE ((ID < 800) AND (Name LIKE 'Ha%' OR (Country > 'A' AND Country < 'ARG')))
@@ -372,9 +369,9 @@ WHERE ((ID < 600) AND (Name LIKE 'Ha%' OR (Country > 'A' AND Country < 'ARG')))
 OR ((ID BETWEEN 300 AND 600) 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	range	PRIMARY,Population,Country,Name	PRIMARY	4	NULL	1242	Using where
+1	SIMPLE	City	index_merge	PRIMARY,Population,Country,Name	Name,Country,Population	35,3,4	NULL	188	Using sort_union(Name,Country,Population); Using where
 SELECT * FROM City USE INDEX ()
-WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
 OR ((ID BETWEEN 100 AND 110) AND 
 (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 ID	Name	Country	Population
@@ -385,13 +382,10 @@ ID	Name	Country	Population
 7	Haag	NLD	440900
 16	Haarlem	NLD	148772
 25	Haarlemmermeer	NLD	110722
-31	Heerlen	NLD	95052
-33	Willemstad	ANT	2345
-34	Tirana	ALB	270000
 100	Paraná	ARG	207041
 102	Posadas	ARG	201273
 SELECT * FROM City
-WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
 OR ((ID BETWEEN 100 AND 110) AND 
 (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 ID	Name	Country	Population
@@ -402,9 +396,6 @@ ID	Name	Country	Population
 7	Haag	NLD	440900
 16	Haarlem	NLD	148772
 25	Haarlemmermeer	NLD	110722
-31	Heerlen	NLD	95052
-33	Willemstad	ANT	2345
-34	Tirana	ALB	270000
 100	Paraná	ARG	207041
 102	Posadas	ARG	201273
 SELECT * FROM City USE INDEX()
@@ -577,6 +568,20 @@ WHERE ((ID < 200) AND (Name LIKE 'Ha%' OR (Country > 'A' AND Country < 'ARG')))
 OR ((ID BETWEEN 300 AND 600) AND 
 (Name LIKE 'Pa%' OR (Population > 103000 AND Population < 104000)));
 ID	Name	Country	Population
+339	Passo Fundo	BRA	166343
+364	Parnaíba	BRA	129756
+372	Paranaguá	BRA	126076
+379	Palmas	BRA	121919
+386	Patos de Minas	BRA	119262
+411	Guaratinguetá	BRA	103433
+412	Cachoeirinha	BRA	103240
+413	Codó	BRA	103153
+424	Passos	BRA	98570
+430	Paulo Afonso	BRA	97291
+435	Parnamirim	BRA	96210
+448	Patos	BRA	90519
+451	Palhoça	BRA	89465
+517	Oldham	GBR	103931
 1	Kabul	AFG	1780000
 2	Qandahar	AFG	237500
 3	Herat	AFG	186800
@@ -601,20 +606,6 @@ ID	Name	Country	Population
 68	Ajman	ARE	114395
 129	Oranjestad	ABW	29034
 191	Hamilton	BMU	1200
-339	Passo Fundo	BRA	166343
-364	Parnaíba	BRA	129756
-372	Paranaguá	BRA	126076
-379	Palmas	BRA	121919
-386	Patos de Minas	BRA	119262
-411	Guaratinguetá	BRA	103433
-412	Cachoeirinha	BRA	103240
-413	Codó	BRA	103153
-424	Passos	BRA	98570
-430	Paulo Afonso	BRA	97291
-435	Parnamirim	BRA	96210
-448	Patos	BRA	90519
-451	Palhoça	BRA	89465
-517	Oldham	GBR	103931
 EXPLAIN 
 SELECT * FROM City WHERE Population > 101000 AND Population < 102000;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
@@ -727,119 +718,55 @@ SELECT * FROM City WHERE Name LIKE 'P%';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	range	Name	Name	35	NULL	235	Using where
 EXPLAIN
-SELECT * FROM City WHERE (Population > 101000 AND Population < 103000);
+SELECT * FROM City WHERE (Population > 101000 AND Population < 102000);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	range	Population	Population	4	NULL	80	Using where
+1	SIMPLE	City	range	Population	Population	4	NULL	38	Using where
 EXPLAIN
 SELECT * FROM City WHERE Country='USA';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	ref	Country,CountryPopulation	Country	3	const	274	Using where
 EXPLAIN
 SELECT * FROM City 
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
 AND Country='USA';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	City	index_merge	Population,Country,Name,CountryPopulation	CountryPopulation,Name	7,35	NULL	17	Using sort_union(CountryPopulation,Name); Using where
+1	SIMPLE	City	index_merge	Population,Country,Name,CountryPopulation	CountryPopulation,Name	7,35	NULL	10	Using sort_union(CountryPopulation,Name); Using where
 EXPLAIN
 SELECT * FROM City 
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-AND Country='USA';
+WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%' )
+AND Country='USA' AND Name LIKE '%port';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	ref	Population,Country,Name,CountryPopulation	Country	3	const	274	Using where
 SELECT * FROM City 
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
 AND Country='USA';
 ID	Name	Country	Population
 3943	Pasadena	USA	141674
 3953	Pasadena	USA	133936
-4023	Gary	USA	102746
-4024	Berkeley	USA	102743
-4025	Santa Clara	USA	102361
-4026	Green Bay	USA	102313
-4027	Cape Coral	USA	102286
-4028	Arvada	USA	102153
-4029	Pueblo	USA	102121
 4030	Sandy	USA	101853
 4031	Athens-Clarke County	USA	101489
 4032	Cambridge	USA	101355
 SELECT * FROM City USE INDEX ()
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
 AND Country='USA';
 ID	Name	Country	Population
 3943	Pasadena	USA	141674
 3953	Pasadena	USA	133936
-4023	Gary	USA	102746
-4024	Berkeley	USA	102743
-4025	Santa Clara	USA	102361
-4026	Green Bay	USA	102313
-4027	Cape Coral	USA	102286
-4028	Arvada	USA	102153
-4029	Pueblo	USA	102121
 4030	Sandy	USA	101853
 4031	Athens-Clarke County	USA	101489
 4032	Cambridge	USA	101355
 SELECT * FROM City 
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-AND Country='USA';
+WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%')
+AND Country='USA' AND Name LIKE '%port';
 ID	Name	Country	Population
-3797	Philadelphia	USA	1517550
-3798	Phoenix	USA	1321045
-3820	Portland	USA	529121
-3844	Pittsburgh	USA	334563
-3870	Plano	USA	222030
-3912	Providence	USA	173618
-3930	Pomona	USA	149473
-3932	Paterson	USA	149222
-3943	Pasadena	USA	141674
-3951	Pembroke Pines	USA	137427
-3953	Pasadena	USA	133936
-3967	Paradise	USA	124682
-3986	Palmdale	USA	116670
-3996	Peoria	USA	112936
-4007	Peoria	USA	108364
-4016	Provo	USA	105166
-4023	Gary	USA	102746
-4024	Berkeley	USA	102743
-4025	Santa Clara	USA	102361
-4026	Green Bay	USA	102313
-4027	Cape Coral	USA	102286
-4028	Arvada	USA	102153
-4029	Pueblo	USA	102121
-4030	Sandy	USA	101853
-4031	Athens-Clarke County	USA	101489
-4032	Cambridge	USA	101355
-4035	Portsmouth	USA	100565
+3880	Shreveport	USA	200145
+3946	Bridgeport	USA	139529
 SELECT * FROM City USE INDEX ()
-WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-AND Country='USA';
+WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%')
+AND Country='USA' AND Name LIKE '%port';
 ID	Name	Country	Population
-3797	Philadelphia	USA	1517550
-3798	Phoenix	USA	1321045
-3820	Portland	USA	529121
-3844	Pittsburgh	USA	334563
-3870	Plano	USA	222030
-3912	Providence	USA	173618
-3930	Pomona	USA	149473
-3932	Paterson	USA	149222
-3943	Pasadena	USA	141674
-3951	Pembroke Pines	USA	137427
-3953	Pasadena	USA	133936
-3967	Paradise	USA	124682
-3986	Palmdale	USA	116670
-3996	Peoria	USA	112936
-4007	Peoria	USA	108364
-4016	Provo	USA	105166
-4023	Gary	USA	102746
-4024	Berkeley	USA	102743
-4025	Santa Clara	USA	102361
-4026	Green Bay	USA	102313
-4027	Cape Coral	USA	102286
-4028	Arvada	USA	102153
-4029	Pueblo	USA	102121
-4030	Sandy	USA	101853
-4031	Athens-Clarke County	USA	101489
-4032	Cambridge	USA	101355
-4035	Portsmouth	USA	100565
+3880	Shreveport	USA	200145
+3946	Bridgeport	USA	139529
 CREATE INDEX CountryName ON City(Country,Name);
 EXPLAIN
 SELECT * FROM City WHERE Country='USA';
@@ -901,9 +828,10 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	index_merge	PRIMARY,Population,Country,Name,CountryPopulation,CountryName	CountryName,PRIMARY	38,4	NULL	10	Using sort_union(CountryName,PRIMARY); Using where
 EXPLAIN
 SELECT * FROM City
-WHERE ((Population > 101000 AND Population < 110000) OR
-ID BETWEEN 3500 AND 3800) AND Country='USA'
-        AND (Name BETWEEN 'P' AND 'T' OR ID BETWEEN 4000 AND 4300);
+WHERE ((Population > 101000 AND Population < 1000000) OR
+ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+AND Name LIKE '%port';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	City	ref	PRIMARY,Population,Country,Name,CountryPopulation,CountryName	Country	3	const	274	Using where
 SELECT * FROM City USE INDEX ()
@@ -939,21 +867,21 @@ ID	Name	Country	Population
 4031	Athens-Clarke County	USA	101489
 4032	Cambridge	USA	101355
 SELECT * FROM City USE INDEX ()
-WHERE ((Population > 101000 AND Population < 102000) OR
-ID BETWEEN 3790 AND 3800) AND Country='USA'
-        AND (Name LIKE 'Pa%' OR ID BETWEEN 4025 AND 4035);
+WHERE ((Population > 101000 AND Population < 1000000) OR
+ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+AND Name LIKE '%port';
 ID	Name	Country	Population
-4030	Sandy	USA	101853
-4031	Athens-Clarke County	USA	101489
-4032	Cambridge	USA	101355
+3880	Shreveport	USA	200145
+3946	Bridgeport	USA	139529
 SELECT * FROM City
-WHERE ((Population > 101000 AND Population < 102000) OR
-ID BETWEEN 3790 AND 3800) AND Country='USA'
-        AND (Name LIKE 'Pa%' OR ID BETWEEN 4025 AND 4035);
+WHERE ((Population > 101000 AND Population < 1000000) OR
+ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+AND Name LIKE '%port';
 ID	Name	Country	Population
-4030	Sandy	USA	101853
-4031	Athens-Clarke County	USA	101489
-4032	Cambridge	USA	101355
+3880	Shreveport	USA	200145
+3946	Bridgeport	USA	139529
 EXPLAIN
 SELECT * FROM City
 WHERE ((Population > 101000 and Population < 102000) OR
@@ -1461,4 +1389,5 @@ f1	f2	f3	f4
 9	0	2	6
 SET SESSION optimizer_switch=DEFAULT;
 DROP TABLE t1;
+set session optimizer_switch='index_merge_sort_intersection=default';
 SET SESSION STORAGE_ENGINE=DEFAULT;
diff --git a/mysql-test/r/subselect.result b/mysql-test/r/subselect.result
index 6d8cb7f5b9a..e08ececafb4 100644
--- a/mysql-test/r/subselect.result
+++ b/mysql-test/r/subselect.result
@@ -3667,8 +3667,6 @@ CREATE TABLE t1 (a int, b int auto_increment, PRIMARY KEY (b));
 CREATE TABLE t2 (x int auto_increment, y int, z int,
 PRIMARY KEY (x), FOREIGN KEY (y) REFERENCES t1 (b));
 SET SESSION sort_buffer_size = 32 * 1024;
-Warnings:
-Warning	1292	Truncated incorrect sort_buffer_size value: '32768'
 SELECT SQL_NO_CACHE COUNT(*)
 FROM (SELECT  a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
 FROM t1) t;
@@ -4104,8 +4102,6 @@ INSERT INTO `t1` VALUES ('asdf','2007-02-08 01:11:26');
 INSERT INTO `t2` VALUES ('abcdefghijk');
 INSERT INTO `t2` VALUES ('asdf');
 SET session sort_buffer_size=8192;
-Warnings:
-Warning	1292	Truncated incorrect sort_buffer_size value: '8192'
 SELECT (SELECT 1 FROM  t1 WHERE t1.a=t2.a ORDER BY t1.b LIMIT 1) AS d1 FROM t2;
 d1
 1
diff --git a/mysql-test/r/variables.result b/mysql-test/r/variables.result
index 832c679f8d5..f1133b7fb4d 100644
--- a/mysql-test/r/variables.result
+++ b/mysql-test/r/variables.result
@@ -971,6 +971,7 @@ tmpdir	#
 select * from information_schema.session_variables where variable_name like 'tmpdir';
 VARIABLE_NAME	VARIABLE_VALUE
 TMPDIR	#
+set sort_buffer_size=1024*8;
 select @@ssl_ca, @@ssl_capath, @@ssl_cert, @@ssl_cipher, @@ssl_key;
 @@ssl_ca	@@ssl_capath	@@ssl_cert	@@ssl_cipher	@@ssl_key
 #	#	#	#	#
diff --git a/mysql-test/suite/innodb/r/innodb_mysql.result b/mysql-test/suite/innodb/r/innodb_mysql.result
index 5d90a96f61c..ec4e4036ca0 100644
--- a/mysql-test/suite/innodb/r/innodb_mysql.result
+++ b/mysql-test/suite/innodb/r/innodb_mysql.result
@@ -679,8 +679,6 @@ INSERT INTO t1(b,c) SELECT b,c FROM t2;
 UPDATE t2 SET c='2007-01-03';
 INSERT INTO t1(b,c) SELECT b,c FROM t2;
 set @@sort_buffer_size=8192;
-Warnings:
-Warning	1292	Truncated incorrect sort_buffer_size value: '8192'
 SELECT COUNT(*) FROM t1;
 COUNT(*)
 3072
diff --git a/mysql-test/suite/innodb_plugin/r/innodb_mysql.result b/mysql-test/suite/innodb_plugin/r/innodb_mysql.result
index 32ee3c21946..77e3f4813df 100644
--- a/mysql-test/suite/innodb_plugin/r/innodb_mysql.result
+++ b/mysql-test/suite/innodb_plugin/r/innodb_mysql.result
@@ -679,8 +679,6 @@ INSERT INTO t1(b,c) SELECT b,c FROM t2;
 UPDATE t2 SET c='2007-01-03';
 INSERT INTO t1(b,c) SELECT b,c FROM t2;
 set @@sort_buffer_size=8192;
-Warnings:
-Warning	1292	Truncated incorrect sort_buffer_size value: '8192'
 SELECT COUNT(*) FROM t1;
 COUNT(*)
 3072
diff --git a/mysql-test/suite/pbxt/r/subselect.result b/mysql-test/suite/pbxt/r/subselect.result
index ebe74e442a2..b68654db911 100644
--- a/mysql-test/suite/pbxt/r/subselect.result
+++ b/mysql-test/suite/pbxt/r/subselect.result
@@ -3667,8 +3667,6 @@ CREATE TABLE t1 (a int, b int auto_increment, PRIMARY KEY (b));
 CREATE TABLE t2 (x int auto_increment, y int, z int,
 PRIMARY KEY (x), FOREIGN KEY (y) REFERENCES t1 (b));
 SET SESSION sort_buffer_size = 32 * 1024;
-Warnings:
-Warning	1292	Truncated incorrect sort_buffer_size value: '32768'
 SELECT SQL_NO_CACHE COUNT(*) 
 FROM (SELECT  a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
 FROM t1) t;
@@ -4104,8 +4102,6 @@ INSERT INTO `t1` VALUES ('asdf','2007-02-08 01:11:26');
 INSERT INTO `t2` VALUES ('abcdefghijk');
 INSERT INTO `t2` VALUES ('asdf');
 SET session sort_buffer_size=8192;
-Warnings:
-Warning	1292	Truncated incorrect sort_buffer_size value: '8192'
 SELECT (SELECT 1 FROM  t1 WHERE t1.a=t2.a ORDER BY t1.b LIMIT 1) AS d1 FROM t2;
 d1
 1
diff --git a/mysql-test/t/index_intersect.test b/mysql-test/t/index_intersect.test
new file mode 100644
index 00000000000..d8fad05a4b0
--- /dev/null
+++ b/mysql-test/t/index_intersect.test
@@ -0,0 +1,419 @@
+--disable_warnings
+DROP TABLE IF EXISTS t1,t2,t3,t4;
+DROP DATABASE IF EXISTS world;
+--enable_warnings
+
+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
+
+SELECT COUNT(*) FROM Country;
+SELECT COUNT(*) FROM City;
+SELECT COUNT(*) FROM CountryLanguage;
+
+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
+
+
+SET SESSION optimizer_switch='index_merge_sort_intersection=on';
+
+SELECT COUNT(*) FROM City;
+
+# The output of the next 6 queries tells us about selectivities
+# of the conditions utilized in 4 queries following after them  
+
+SELECT COUNT(*) FROM City WHERE Name LIKE 'C%';
+SELECT COUNT(*) FROM City WHERE Name LIKE 'M%';
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+SELECT COUNT(*) FROM City WHERE Population > 1500000;
+SELECT COUNT(*) FROM City WHERE Population > 300000;
+SELECT COUNT(*) FROM City WHERE Population > 5000000;
+
+# The pattern of the WHERE condition used in the following 4 queries is
+#   range(key1) AND range(key2)
+# Varying values of the constants in the  conjuncts of the condition
+# we can get either an index intersection retrieval over key1 and key2
+# or a range index scan for one of these indexes
+
+EXPLAIN
+SELECT * FROM City WHERE
+  Name LIKE 'C%' AND Population > 1000000; 
+
+EXPLAIN
+SELECT * FROM City WHERE
+  Name LIKE 'M%' AND Population > 1500000; 
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE Name LIKE 'M%' AND Population > 300000;
+
+EXPLAIN
+SELECT * FROM City
+  WHERE Name LIKE 'M%' AND Population > 5000000;
+
+
+# The following 8 queries check that 
+# the previous 4 plans are valid and return
+# the correct results when executed
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Name LIKE 'C%' AND Population > 1000000;
+ 
+SELECT * FROM City
+  WHERE Name LIKE 'C%' AND Population > 1000000; 
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Name LIKE 'M%' AND Population > 1500000; 
+
+SELECT * FROM City 
+  WHERE Name LIKE 'M%' AND Population > 1500000; 
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Name LIKE 'M%' AND Population > 300000;
+
+SELECT * FROM City 
+  WHERE Name LIKE 'M%' AND Population > 300000;
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Name LIKE 'M%' AND Population > 5000000;
+
+SELECT * FROM City
+  WHERE Name LIKE 'M%' AND Population > 5000000;
+
+
+# The output of the next 6 queries tells us about selectivities
+# of the conditions utilized in 3 queries following after them  
+
+SELECT COUNT(*) FROM City WHERE Name BETWEEN 'M' AND 'N';
+SELECT COUNT(*) FROM City WHERE Name BETWEEN 'G' AND 'J'; 
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+SELECT COUNT(*) FROM City WHERE Population > 500000;
+SELECT COUNT(*) FROM City WHERE Country LIKE 'C%';
+SELECT COUNT(*) FROM City WHERE Country LIKE 'B%';
+
+
+# The pattern of the WHERE condition used in the following 3 queries is
+#   range(key1) AND range(key2) AND range(key3)
+# Varying values of the constants in the  conjuncts of the condition
+# we can get index intersection over different pairs of keys:
+# over(key1,key2), over(key1,key3) and over(key2,key3)
+
+
+EXPLAIN
+SELECT * FROM City
+  WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+
+
+# The following 6 queries check that 
+# the previous 3 plans are valid and return
+# the correct results when executed
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+
+SELECT * FROM City
+  WHERE Name BETWEEN 'M' AND 'N' AND Population > 1000000 AND Country LIKE 'C%';
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+
+SELECT * FROM City 
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+
+SELECT * FROM City 
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+
+
+# The output of the next 12 queries tells us about selectivities
+# of the conditions utilized in 5 queries following after them  
+
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 501 AND 1000;
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 1 AND 500;
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 2001 AND 2500;
+SELECT COUNT(*) FROM City WHERE ID BETWEEN 3701 AND 4000;
+SELECT COUNT(*) FROM City WHERE Population > 700000;
+SELECT COUNT(*) FROM City WHERE Population > 1000000;
+SELECT COUNT(*) FROM City WHERE Population > 300000;
+SELECT COUNT(*) FROM City WHERE Population > 600000;
+SELECT COUNT(*) FROM City WHERE Country LIKE 'C%';
+SELECT COUNT(*) FROM City WHERE Country LIKE 'A%';
+SELECT COUNT(*) FROM City WHERE Country LIKE 'L%';
+SELECT COUNT(*) FROM City WHERE Country BETWEEN 'S' AND 'Z';
+
+
+# The pattern of the WHERE condition used in the following 5 queries is
+#   range(key1) AND range(key2) AND range(key3)
+# with key1 happens to be a primary key (it matters only for InnoDB)
+# Varying values of the constants in the  conjuncts of the condition
+# we can get index intersection  either over all three keys, or over
+# different pairs, or a range scan over one of these keys.
+# Bear in mind that the condition (Country LIKE 'A%') is actually
+# equivalent to the condition (Country BETWEEN 'A' AND 'B') for the
+# tested instance the table City. 
+
+
+EXPLAIN
+SELECT * FROM City
+  WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+
+EXPLAIN
+SELECT * FROM City
+  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE ID BETWEEN 3701 AND 4000 AND Population > 1000000
+        AND Country BETWEEN 'S' AND 'Z';
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+        AND Country BETWEEN 'S' AND 'Z' ;
+
+
+# The following 10 queries check that 
+# the previous 5 plans are valid and return
+# the correct results when executed
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+
+SELECT * FROM City
+  WHERE ID BETWEEN 501 AND 1000 AND Population > 700000 AND Country LIKE 'C%';
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+
+SELECT * FROM City
+  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+
+SELECT * FROM City 
+  WHERE ID BETWEEN 2001 AND 2500 AND Population > 300000 AND Country LIKE 'L%';
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE ID BETWEEN 3701 AND 4000 AND Population > 700000
+        AND Country BETWEEN 'S' AND 'Z';
+
+SELECT * FROM City 
+  WHERE ID BETWEEN 3701 AND 4000 AND Population > 700000
+        AND Country BETWEEN 'S' AND 'Z';
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+        AND Country BETWEEN 'S' AND 'Z' ;
+
+SELECT * FROM City 
+  WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+        AND Country BETWEEN 'S' AND 'Z' ;
+
+
+SET SESSION sort_buffer_size = 2048;
+
+
+# The following EXPLAIN command demonstrate that the execution plans
+# may be different if sort_buffer_size is set to a small value
+
+
+EXPLAIN
+SELECT * FROM City WHERE
+  Name LIKE 'C%' AND Population > 1000000; 
+
+EXPLAIN
+SELECT * FROM City WHERE
+  Name LIKE 'M%' AND Population > 1500000; 
+
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE  Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE  Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+
+
+EXPLAIN
+SELECT * FROM City
+  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+        AND Country BETWEEN 'S' AND 'Z';
+
+
+#Yet the query themselves return the correct results in this case as well
+
+
+SELECT * FROM City WHERE
+  Name LIKE 'C%' AND Population > 1000000; 
+
+SELECT * FROM City WHERE
+  Name LIKE 'M%' AND Population > 1500000; 
+
+
+SELECT * FROM City 
+  WHERE  Name BETWEEN 'G' AND 'J' AND Population > 700000 AND Country LIKE 'B%';
+
+SELECT * FROM City 
+  WHERE  Name BETWEEN 'G' AND 'J' AND Population > 500000 AND Country LIKE 'C%';
+
+
+SELECT * FROM City
+  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+
+SELECT * FROM City 
+  WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
+        AND Country BETWEEN 'S' AND 'Z';
+
+
+SET SESSION sort_buffer_size = default;
+
+# Instead of the index on the column Country create two compound indexes
+# including this column as the first component
+
+DROP INDEX Country ON City;
+
+CREATE INDEX CountryID ON City(Country,ID);
+CREATE INDEX CountryName ON City(Country,Name);
+
+--disable_query_log
+--disable_result_log
+--disable_warnings
+ANALYZE TABLE City;
+--enable_warnings
+--enable_result_log
+--enable_query_log
+
+# Check that the first component of a compound index can be used for
+# index intersection, even in the cases when we have a ref access
+# for this component
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE Country LIKE 'M%' AND Population > 1000000;
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE Country='CHN' AND Population > 1500000;
+
+EXPLAIN
+SELECT * FROM City 
+  WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+
+
+# Check that the previous 3 plans return the right results when executed
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Country LIKE 'M%' AND Population > 1000000;
+
+SELECT * FROM City 
+  WHERE Country LIKE 'M%' AND Population > 700000;
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Country='CHN' AND Population > 1500000;
+
+SELECT * FROM City 
+  WHERE Country='CHN' AND Population > 1500000;
+
+
+SELECT * FROM City USE INDEX ()
+  WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+
+SELECT * FROM City 
+  WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+
+
+DROP DATABASE world;
+
+use test;
+
+#
+# Bug #684086: crash with EXPLAIN in InnoDB for index intersection
+#              of two indexes one of which is primary
+#
+
+CREATE TABLE t1 (
+  f1 int,
+  f4 varchar(32),
+  f5 int,
+  PRIMARY KEY (f1),
+  KEY (f4)
+) ENGINE=InnoDB;
+
+INSERT INTO t1 VALUES 
+  (5,'H',1), (9,'g',0), (527,'i',0), (528,'y',1), (529,'S',6),
+  (530,'m',7), (531,'b',2), (532,'N',1), (533,'V',NULL), (534,'l',1),
+  (535,'M',0), (536,'w',1), (537,'j',5), (538,'l',0), (539,'n',2),
+  (540,'m',2), (541,'r',2), (542,'l',2), (543,'h',3),(544,'o',0),
+  (956,'h',0), (957,'g',0), (958,'W',5), (959,'s',3), (960,'w',0),
+  (961,'q',0), (962,'e',NULL), (963,'u',7), (964,'q',1), (965,'N',NULL),
+  (966,'e',0), (967,'t',3), (968,'e',6), (969,'f',NULL), (970,'j',0),
+  (971,'s',3), (972,'I',0), (973,'h',4), (974,'g',1), (975,'s',0),
+  (976,'r',3), (977,'x',1), (978,'v',8), (979,'j',NULL), (980,'z',7),
+  (981,'t',9), (982,'j',5), (983,'u',NULL), (984,'g',6), (985,'w',1),
+  (986,'h',1), (987,'v',0), (988,'v',0), (989,'c',2), (990,'b',7),
+  (991,'z',0), (992,'M',1), (993,'u',2), (994,'r',2), (995,'b',4),
+  (996,'A',2), (997,'u',0), (998,'a',0), (999,'j',2), (1,'I',2);
+
+EXPLAIN
+SELECT * FROM t1
+WHERE (f1 < 535  OR  f1 > 985) AND ( f4='r' OR f4 LIKE 'a%' ) ;
+
+SELECT * FROM t1
+WHERE (f1 < 535  OR  f1 > 985) AND ( f4='r' OR f4 LIKE 'a%' ) ;
+
+DROP TABLE t1;
+
+SET SESSION optimizer_switch='index_merge_sort_intersection=on';
diff --git a/mysql-test/t/index_intersect_innodb.test b/mysql-test/t/index_intersect_innodb.test
new file mode 100644
index 00000000000..22c0e807558
--- /dev/null
+++ b/mysql-test/t/index_intersect_innodb.test
@@ -0,0 +1,7 @@
+--source include/have_innodb.inc
+
+SET SESSION STORAGE_ENGINE='InnoDB';
+
+--source t/index_intersect.test
+
+SET SESSION STORAGE_ENGINE=DEFAULT;
diff --git a/mysql-test/t/index_merge_innodb.test b/mysql-test/t/index_merge_innodb.test
index 04f8c5a659b..1d11488c187 100644
--- a/mysql-test/t/index_merge_innodb.test
+++ b/mysql-test/t/index_merge_innodb.test
@@ -18,6 +18,11 @@ let $engine_type= InnoDB;
 # InnoDB does not support Merge tables (affects include/index_merge1.inc)
 let $merge_table_support= 0;
 
+set @optimizer_switch_save= @@optimizer_switch;
+
+set optimizer_switch='index_merge_sort_intersection=off';
+
+
 # The first two tests are disabled because of non deterministic explain output.
 # If include/index_merge1.inc can be enabled for InnoDB and all other
 # storage engines, please remove the subtest for Bug#21277 from
@@ -84,3 +89,5 @@ SELECT COUNT(*) FROM
      WHERE a BETWEEN 2 AND 7 OR pk=1000000) AS t;
 
 DROP TABLE t1;
+
+set optimizer_switch= @optimizer_switch_save;
diff --git a/mysql-test/t/index_merge_myisam.test b/mysql-test/t/index_merge_myisam.test
index 0c4b9c6886c..26f7f0518c6 100644
--- a/mysql-test/t/index_merge_myisam.test
+++ b/mysql-test/t/index_merge_myisam.test
@@ -14,6 +14,10 @@ let $engine_type= MyISAM;
 # MyISAM supports Merge tables
 let $merge_table_support= 1;
 
+set @optimizer_switch_save= @@optimizer_switch;
+
+set optimizer_switch='index_merge_sort_intersection=off';
+
 --source include/index_merge1.inc
 --source include/index_merge_ror.inc
 --source include/index_merge2.inc
@@ -164,7 +168,7 @@ set optimizer_switch='default,index_merge=off';
 explain select * from t1 where a=10 and b=10;
 
 --echo No intersect if it is disabled:
-set optimizer_switch='default,index_merge_intersection=off';
+set optimizer_switch='default,index_merge_sort_intersection=off,index_merge_intersection=off';
 explain select * from t1 where a=10 and b=10;
 
 --echo Do intersect when union was disabled
@@ -195,3 +199,5 @@ show variables like 'optimizer_switch';
 
 drop table t0, t1;
 
+set optimizer_switch= @optimizer_switch_save;
+
diff --git a/mysql-test/t/order_by.test b/mysql-test/t/order_by.test
index 0bacd785808..6dcf93dbac5 100644
--- a/mysql-test/t/order_by.test
+++ b/mysql-test/t/order_by.test
@@ -843,7 +843,7 @@ DROP TABLE t1;
 --echo #
 create table t1(a int, b tinytext);
 insert into t1 values (1,2),(3,2);
-set session sort_buffer_size= 30000;
+set session sort_buffer_size= 1000;
 set session max_sort_length= 2180;
 --error 1038
 select * from t1 order by b;
diff --git a/mysql-test/t/range_vs_index_merge.test b/mysql-test/t/range_vs_index_merge.test
index a6dc21bf05a..e5f73764984 100755
--- a/mysql-test/t/range_vs_index_merge.test
+++ b/mysql-test/t/range_vs_index_merge.test
@@ -33,6 +33,8 @@ ANALYZE TABLE City;
 --enable_result_log
 --enable_query_log
 
+set session optimizer_switch='index_merge_sort_intersection=off';
+
 # The following 4 queries are added for code coverage 
 
 #the exptected # of rows differ on 32-bit and 64-bit platforms for innodb 
@@ -68,7 +70,7 @@ SELECT * FROM City
 
 EXPLAIN 
 SELECT * FROM City
-  WHERE (Population > 101000 AND Population < 103000);
+  WHERE (Population > 101000 AND Population < 102000);
 
 EXPLAIN 
 SELECT * FROM City
@@ -88,7 +90,7 @@ SELECT * FROM City
 EXPLAIN 
 SELECT * FROM City
   WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-        AND (Population > 101000 AND Population < 103000);
+        AND (Population > 101000 AND Population < 102000);
 
 # The following 4 queries check that the plans
 # for the previous 2 plans are valid
@@ -103,11 +105,11 @@ SELECT * FROM City
 
 SELECT * FROM City USE INDEX ()
   WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-        AND (Population > 101000 AND Population < 103000);
+        AND (Population > 101000 AND Population < 102000);
 
 SELECT * FROM City
   WHERE ((Name > 'Ca' AND Name < 'Cf') OR (Country > 'E' AND Country < 'F'))
-        AND (Population > 101000 AND Population < 103000);
+        AND (Population > 101000 AND Population < 102000);
 
 # The output of the next 7 commands tells us about selectivities
 # of the conditions utilized in 4 queries following after them  
@@ -197,9 +199,10 @@ SELECT  * FROM City
 # of the conditions utilized in 3 queries following after them  
 
 EXPLAIN
-SELECT * FROM City WHERE (ID < 50) OR (ID BETWEEN 100 AND 110);
+SELECT * FROM City WHERE (ID < 30) OR (ID BETWEEN 100 AND 150);
 EXPLAIN
 SELECT * FROM City WHERE (ID < 200) OR (ID BETWEEN 300 AND 600);
+--replace_result 2921 2950
 EXPLAIN
 SELECT * FROM City WHERE (ID < 600) OR (ID BETWEEN 900 AND 1800);
 EXPLAIN
@@ -219,7 +222,7 @@ SELECT * FROM City WHERE Name LIKE 'Ha%' OR Name LIKE 'Pa%' ;
 
 EXPLAIN
 SELECT * FROM City
-  WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+  WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
         OR ((ID BETWEEN 100 AND 110) AND 
             (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 
@@ -240,12 +243,12 @@ SELECT * FROM City
 # for the previous 3 plans are valid
 
 SELECT * FROM City USE INDEX ()
-  WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+  WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
         OR ((ID BETWEEN 100 AND 110) AND 
             (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 
 SELECT * FROM City
-  WHERE ((ID < 50) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
+  WHERE ((ID < 30) AND (Name LIKE 'H%' OR (Country > 'A' AND Country < 'ARG')))
         OR ((ID BETWEEN 100 AND 110) AND 
             (Name LIKE 'P%' OR (Population > 103000 AND Population < 104000)));
 
@@ -361,7 +364,7 @@ SELECT * FROM City WHERE Name LIKE 'Pas%';
 EXPLAIN
 SELECT * FROM City WHERE Name LIKE 'P%';
 EXPLAIN
-SELECT * FROM City WHERE (Population > 101000 AND Population < 103000);
+SELECT * FROM City WHERE (Population > 101000 AND Population < 102000);
 EXPLAIN
 SELECT * FROM City WHERE Country='USA';
 
@@ -374,32 +377,32 @@ SELECT * FROM City WHERE Country='USA';
 
 EXPLAIN
 SELECT * FROM City 
-  WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+  WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
         AND Country='USA';
 
 EXPLAIN
 SELECT * FROM City 
-  WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-        AND Country='USA';
+  WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%' )
+        AND Country='USA' AND Name LIKE '%port';
 
 # The following 4 queries check that the plans
 # for the previous 2 plans are valid
 
 SELECT * FROM City 
-  WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+  WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
         AND Country='USA';
 
 SELECT * FROM City USE INDEX ()
-  WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'Pas%')
+  WHERE ((Population > 101000 AND Population < 102000) OR Name LIKE 'Pas%')
         AND Country='USA';
 
 SELECT * FROM City 
-  WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-        AND Country='USA';
+  WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%')
+        AND Country='USA' AND Name LIKE '%port';
 
 SELECT * FROM City USE INDEX ()
-  WHERE ((Population > 101000 AND Population < 103000) OR Name LIKE 'P%')
-        AND Country='USA';
+  WHERE ((Population > 101000 AND Population < 1000000) OR Name LIKE 'P%')
+        AND Country='USA' AND Name LIKE '%port';
 
 
 CREATE INDEX CountryName ON City(Country,Name);
@@ -463,9 +466,10 @@ SELECT * FROM City
 
 EXPLAIN
 SELECT * FROM City
-  WHERE ((Population > 101000 AND Population < 110000) OR
-          ID BETWEEN 3500 AND 3800) AND Country='USA'
-        AND (Name BETWEEN 'P' AND 'T' OR ID BETWEEN 4000 AND 4300);
+  WHERE ((Population > 101000 AND Population < 1000000) OR
+          ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+        AND Name LIKE '%port';
 
 # The following 6 queries check that the plans
 # for the previous 3 plans are valid
@@ -491,14 +495,16 @@ SELECT * FROM City
         AND (Name LIKE 'Pa%' OR ID BETWEEN 4028 AND 4032);
 
 SELECT * FROM City USE INDEX ()
-  WHERE ((Population > 101000 AND Population < 102000) OR
-          ID BETWEEN 3790 AND 3800) AND Country='USA'
-        AND (Name LIKE 'Pa%' OR ID BETWEEN 4025 AND 4035);
+  WHERE ((Population > 101000 AND Population < 1000000) OR
+          ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+        AND Name LIKE '%port';
 
 SELECT * FROM City
-  WHERE ((Population > 101000 AND Population < 102000) OR
-          ID BETWEEN 3790 AND 3800) AND Country='USA'
-        AND (Name LIKE 'Pa%' OR ID BETWEEN 4025 AND 4035);
+  WHERE ((Population > 101000 AND Population < 1000000) OR
+          ID BETWEEN 3000 AND 3800) AND Country='USA'
+        AND (Name BETWEEN 'P' AND 'Z' OR ID BETWEEN 3500 AND 4300)
+        AND Name LIKE '%port';
 
 
 # The pattern of the WHERE condition used in the following query is
@@ -1003,3 +1009,6 @@ SELECT * FROM t1 FORCE KEY (PRIMARY,f3,f4)
 SET SESSION optimizer_switch=DEFAULT;
 
 DROP TABLE t1;
+
+#the following command must be the last one in the file
+set session optimizer_switch='index_merge_sort_intersection=default';
diff --git a/mysql-test/t/variables.test b/mysql-test/t/variables.test
index 3e9dc5e39d3..3bd192f8cd1 100644
--- a/mysql-test/t/variables.test
+++ b/mysql-test/t/variables.test
@@ -736,6 +736,7 @@ select * from information_schema.session_variables where variable_name like 'tmp
 # Bug #19606: make ssl settings available via SHOW VARIABLES and @@variables
 # 
 # Don't actually output, since it depends on the system
+set sort_buffer_size=1024*8;
 --replace_column 1 # 2 # 3 # 4 # 5 #
 select @@ssl_ca, @@ssl_capath, @@ssl_cert, @@ssl_cipher, @@ssl_key;
 --replace_column 2 #
diff --git a/mysys/tree.c b/mysys/tree.c
index e4854581204..70f2972b03f 100644
--- a/mysys/tree.c
+++ b/mysys/tree.c
@@ -221,6 +221,8 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
   }
   if (element == &tree->null_element)
   {
+    if (tree->flag & TREE_ONLY_DUPS)
+      return((TREE_ELEMENT *) 1);
     uint alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
     tree->allocated+=alloc_size;
 
diff --git a/sql/filesort.cc b/sql/filesort.cc
index 0e476d3d957..42ce33af1ca 100644
--- a/sql/filesort.cc
+++ b/sql/filesort.cc
@@ -50,10 +50,6 @@ static int write_keys(SORTPARAM *param,uchar * *sort_keys,
 		      uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
 static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos);
 static void register_used_fields(SORTPARAM *param);
-static int merge_index(SORTPARAM *param,uchar *sort_buffer,
-		       BUFFPEK *buffpek,
-		       uint maxbuffer,IO_CACHE *tempfile,
-		       IO_CACHE *outfile);
 static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count, 
                        FILESORT_INFO *table_sort);
 static uint suffix_length(ulong string_length);
@@ -145,6 +141,7 @@ ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
   /* filesort cannot handle zero-length records. */
   DBUG_ASSERT(param.sort_length);
   param.ref_length= table->file->ref_length;
+  param.min_dupl_count= 0;
   param.addon_field= 0;
   param.addon_length= 0;
   if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
@@ -1216,7 +1213,13 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
   rec_length= param->rec_length;
   res_length= param->res_length;
   sort_length= param->sort_length;
-  offset= rec_length-res_length;
+  element_count dupl_count;
+  uchar *src;
+  uint dupl_count_ofs= rec_length-sizeof(element_count);
+  uint min_dupl_count= param->min_dupl_count;
+  offset= rec_length-
+          (flag && min_dupl_count ? sizeof(dupl_count) : 0)-res_length;
+  uint wr_len= flag ? res_length : rec_length;
   maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1));
   to_start_filepos= my_b_tell(to_file);
   strpos= sort_buffer;
@@ -1262,16 +1265,20 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
     */
     buffpek= (BUFFPEK*) queue_top(&queue);
     memcpy(param->unique_buff, buffpek->key, rec_length);
-    if (my_b_write(to_file, (uchar*) buffpek->key, rec_length))
-    {
-      error=1; goto err;                        /* purecov: inspected */
-    }
+    if (min_dupl_count)
+      memcpy(&dupl_count, param->unique_buff+dupl_count_ofs, 
+             sizeof(dupl_count));
     buffpek->key+= rec_length;
-    buffpek->mem_count--;
-    if (!--max_rows)
+    if (! --buffpek->mem_count)
     {
-      error= 0;                                       /* purecov: inspected */
-      goto end;                                       /* purecov: inspected */
+      if (!(error= (int) read_to_buffer(from_file,buffpek,
+                                        rec_length)))
+      {
+        VOID(queue_remove(&queue,0));
+        reuse_freed_buff(&queue, buffpek, rec_length);
+      }
+      else if (error == -1)
+        goto err;                        /* purecov: inspected */ 
     }
     queue_replaced(&queue);                        // Top element has been used
   }
@@ -1287,27 +1294,42 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
     for (;;)
     {
       buffpek= (BUFFPEK*) queue_top(&queue);
+      src= buffpek->key;
       if (cmp)                                        // Remove duplicates
       {
         if (!(*cmp)(first_cmp_arg, &(param->unique_buff),
                     (uchar**) &buffpek->key))
-              goto skip_duplicate;
-            memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length);
-      }
-      if (flag == 0)
-      {
-        if (my_b_write(to_file,(uchar*) buffpek->key, rec_length))
-        {
-          error=1; goto err;                        /* purecov: inspected */
+	{
+          if (min_dupl_count)
+	  {
+            element_count cnt;
+            memcpy(&cnt, (uchar *) buffpek->key+dupl_count_ofs, sizeof(cnt));
+            dupl_count+= cnt;
+          }
+          goto skip_duplicate;
         }
+        if (min_dupl_count)
+	{
+          memcpy(param->unique_buff+dupl_count_ofs, &dupl_count,
+                 sizeof(dupl_count));
+        }
+	src= param->unique_buff;
       }
-      else
+        
+      if (!flag || !min_dupl_count || dupl_count >= min_dupl_count)
       {
-        if (my_b_write(to_file, (uchar*) buffpek->key+offset, res_length))
+        if (my_b_write(to_file, src+(flag ? offset : 0), wr_len))
         {
           error=1; goto err;                        /* purecov: inspected */
         }
       }
+      if (cmp)
+      {   
+        memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length);
+        if (min_dupl_count)
+          memcpy(&dupl_count, param->unique_buff+dupl_count_ofs, 
+                 sizeof(dupl_count));
+      }
       if (!--max_rows)
       {
         error= 0;                               /* purecov: inspected */
@@ -1343,9 +1365,33 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
   {
     if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (uchar**) &buffpek->key))
     {
-      buffpek->key+= rec_length;         // Remove duplicate
+      if (min_dupl_count)
+      {
+        element_count cnt;
+        memcpy(&cnt, (uchar *) buffpek->key+dupl_count_ofs, sizeof(cnt));
+        dupl_count+= cnt;
+      }
+      buffpek->key+= rec_length;         
       --buffpek->mem_count;
     }
+
+    if (min_dupl_count)
+      memcpy(param->unique_buff+dupl_count_ofs, &dupl_count,
+             sizeof(dupl_count));
+          
+    if (!flag || !min_dupl_count || dupl_count >= min_dupl_count)
+    {
+      src= param->unique_buff;
+      if (my_b_write(to_file, src+(flag ? offset : 0), wr_len))
+      {
+        error=1; goto err;                        /* purecov: inspected */
+      }
+      if (!--max_rows)
+      {
+        error= 0;                               
+        goto end;                             
+      }
+    }   
   }
 
   do
@@ -1367,12 +1413,17 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
     else
     {
       register uchar *end;
-      strpos= buffpek->key+offset;
-      for (end= strpos+buffpek->mem_count*rec_length ;
-           strpos != end ;
-           strpos+= rec_length)
-      {     
-        if (my_b_write(to_file, strpos, res_length))
+      src= buffpek->key+offset;
+      for (end= src+buffpek->mem_count*rec_length ;
+           src != end ;
+           src+= rec_length)
+      {
+        if (flag && min_dupl_count &&
+            memcmp(&min_dupl_count, src+dupl_count_ofs, 
+                   sizeof(dupl_count_ofs))<0)
+	  continue;
+        
+        if (my_b_write(to_file, src, wr_len))
         {
           error=1; goto err;                        
         }
@@ -1393,7 +1444,7 @@ err:
 
 	/* Do a merge to output-file (save only positions) */
 
-static int merge_index(SORTPARAM *param, uchar *sort_buffer,
+int merge_index(SORTPARAM *param, uchar *sort_buffer,
 		       BUFFPEK *buffpek, uint maxbuffer,
 		       IO_CACHE *tempfile, IO_CACHE *outfile)
 {
@@ -1699,3 +1750,4 @@ void change_double_for_sort(double nr,uchar *to)
     }
   }
 }
+
diff --git a/sql/mysql_priv.h b/sql/mysql_priv.h
index 7905a0f52e5..f8c36d87d52 100644
--- a/sql/mysql_priv.h
+++ b/sql/mysql_priv.h
@@ -338,7 +338,7 @@ protected:
   Number of comparisons of table rowids equivalent to reading one row from a 
   table.
 */
-#define TIME_FOR_COMPARE_ROWID  (TIME_FOR_COMPARE*2)
+#define TIME_FOR_COMPARE_ROWID  (TIME_FOR_COMPARE*100)
 
 /*
   For sequential disk seeks the cost formula is:
@@ -542,12 +542,13 @@ protected:
 #define OPTIMIZER_SWITCH_INDEX_MERGE_UNION 2
 #define OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION 4
 #define OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT 8
+#define OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT 16
 
 #ifdef DBUG_OFF
-#  define OPTIMIZER_SWITCH_LAST 16
-#else
-#  define OPTIMIZER_SWITCH_TABLE_ELIMINATION 16
 #  define OPTIMIZER_SWITCH_LAST 32
+#else
+#  define OPTIMIZER_SWITCH_TABLE_ELIMINATION 32
+#  define OPTIMIZER_SWITCH_LAST 64
 #endif
 
 #ifdef DBUG_OFF 
@@ -555,12 +556,14 @@ protected:
 #  define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
                                     OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
                                     OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
-                                    OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT)
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT | \
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT)
 #else 
 #  define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
                                     OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
                                     OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
                                     OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT | \
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT | \
                                     OPTIMIZER_SWITCH_TABLE_ELIMINATION)
 #endif
 
@@ -2233,6 +2236,8 @@ ha_rows filesort(THD *thd, TABLE *form,struct st_sort_field *sortorder,
 		 ha_rows max_rows, bool sort_positions,
                  ha_rows *examined_rows);
 void filesort_free_buffers(TABLE *table, bool full);
+double get_merge_many_buffs_cost(uint *buffer, uint last_n_elems,
+                                 int elem_size);
 void change_double_for_sort(double nr,uchar *to);
 double my_double_round(double value, longlong dec, bool dec_unsigned,
                        bool truncate);
diff --git a/sql/mysqld.cc b/sql/mysqld.cc
index c3d58349ad5..9d662ea0174 100644
--- a/sql/mysqld.cc
+++ b/sql/mysqld.cc
@@ -338,7 +338,7 @@ TYPELIB sql_mode_typelib= { array_elements(sql_mode_names)-1,"",
 static const char *optimizer_switch_names[]=
 {
   "index_merge","index_merge_union","index_merge_sort_union",
-  "index_merge_intersection",
+  "index_merge_intersection","index_merge_sort_intersection",
 #ifndef DBUG_OFF
   "table_elimination",
 #endif
@@ -352,6 +352,7 @@ static const unsigned int optimizer_switch_names_len[]=
   sizeof("index_merge_union") - 1,
   sizeof("index_merge_sort_union") - 1,
   sizeof("index_merge_intersection") - 1,
+  sizeof("index_merge_sort_intersection") - 1,
 #ifndef DBUG_OFF
   sizeof("table_elimination") - 1,
 #endif
@@ -431,7 +432,8 @@ static const char *sql_mode_str= "OFF";
 /* Text representation for OPTIMIZER_SWITCH_DEFAULT */
 static const char *optimizer_switch_str="index_merge=on,index_merge_union=on,"
                                         "index_merge_sort_union=on,"
-                                        "index_merge_intersection=on"
+                                        "index_merge_intersection=on,"
+                                        "index_merge_sort_intersection=on"
 #ifndef DBUG_OFF                                        
                                         ",table_elimination=on";
 #else
@@ -7297,7 +7299,8 @@ thread is in the relay logs.",
    0, GET_ULONG, OPT_ARG, MAX_TABLES+1, 0, MAX_TABLES+2, 0, 1, 0},
   {"optimizer_switch", OPT_OPTIMIZER_SWITCH,
    "optimizer_switch=option=val[,option=val...], where option={index_merge, "
-   "index_merge_union, index_merge_sort_union, index_merge_intersection"
+   "index_merge_union, index_merge_sort_union, index_merge_intersection, "
+   "index_merge_sort_intersection"
 #ifndef DBUG_OFF
    ", table_elimination"
 #endif 
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index 6ca9ff5e823..47d0b6a58a8 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -697,6 +697,9 @@ public:
   key_map ror_scans_map;   /* bitmask of ROR scan-able elements in keys */
   uint    n_ror_scans;     /* number of set bits in ror_scans_map */
 
+  struct st_index_scan_info **index_scans;     /* list of index scans */
+  struct st_index_scan_info **index_scans_end; /* last index scan */
+
   struct st_ror_scan_info **ror_scans;     /* list of ROR key scans */
   struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
   /* Note that #records for each key scan is stored in table->quick_rows */
@@ -776,9 +779,11 @@ class TABLE_READ_PLAN;
   class TRP_RANGE;
   class TRP_ROR_INTERSECT;
   class TRP_ROR_UNION;
+  class TRP_INDEX_INTERSECT;
   class TRP_INDEX_MERGE;
   class TRP_GROUP_MIN_MAX;
 
+struct st_index_scan_info;
 struct st_ror_scan_info;
 
 static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
@@ -804,6 +809,9 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
                                        bool update_tbl_stats,
                                        double read_time);
 static
+TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree,
+                                              double read_time);
+static
 TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
                                           double read_time,
                                           bool *are_all_covering);
@@ -1093,7 +1101,7 @@ int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param,
     {
       bool must_be_ored= sel_trees_must_be_ored(param, *or_tree, tree,
                                                 ored_keys);
-      if (must_be_ored == is_first_check_pass) 
+      if (must_be_ored || !is_first_check_pass) 
       {
         result_keys.clear_all();
         result= *or_tree;
@@ -1749,7 +1757,7 @@ int QUICK_INDEX_MERGE_SELECT::init()
 int QUICK_INDEX_MERGE_SELECT::reset()
 {
   DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::reset");
-  DBUG_RETURN(read_keys_and_merge());
+  DBUG_RETURN (read_keys_and_merge());
 }
 
 bool
@@ -1785,6 +1793,64 @@ QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
   DBUG_VOID_RETURN;
 }
 
+QUICK_INDEX_INTERSECT_SELECT::QUICK_INDEX_INTERSECT_SELECT(THD *thd_param,
+                                                           TABLE *table)
+  :unique(NULL), pk_quick_select(NULL), thd(thd_param)
+{
+  DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::QUICK_INDEX_INTERSECT_SELECT");
+  index= MAX_KEY;
+  head= table;
+  bzero(&read_record, sizeof(read_record));
+  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
+  DBUG_VOID_RETURN;
+}
+
+int QUICK_INDEX_INTERSECT_SELECT::init()
+{
+  DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::init");
+  DBUG_RETURN(0);
+}
+
+int QUICK_INDEX_INTERSECT_SELECT::reset()
+{
+  DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::reset");
+  DBUG_RETURN (read_keys_and_merge());
+}
+
+bool
+QUICK_INDEX_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
+{
+  /*
+    Save quick_select that does scan on clustered primary key as it will be
+    processed separately.
+  */
+  if (head->file->primary_key_is_clustered() &&
+      quick_sel_range->index == head->s->primary_key)
+    pk_quick_select= quick_sel_range;
+  else
+    return quick_selects.push_back(quick_sel_range);
+  return 0;
+}
+
+QUICK_INDEX_INTERSECT_SELECT::~QUICK_INDEX_INTERSECT_SELECT()
+{
+  List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
+  QUICK_RANGE_SELECT* quick;
+  DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::~QUICK_INDEX_INTERSECT_SELECT");
+  delete unique;
+  quick_it.rewind();
+  while ((quick= quick_it++))
+    quick->file= NULL;
+  quick_selects.delete_elements();
+  delete pk_quick_select;
+  /* It's ok to call the next two even if they are already deinitialized */
+  end_read_record(&read_record);
+  free_io_cache(head);
+  free_root(&alloc,MYF(0));
+  DBUG_VOID_RETURN;
+}
+
+
 
 QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
                                                        TABLE *table,
@@ -2576,6 +2642,24 @@ public:
 
 
 /*
+  Plan for QUICK_INDEX_INTERSECT_SELECT scan.
+  QUICK_INDEX_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
+  is ignored by make_quick.
+*/
+
+class TRP_INDEX_INTERSECT : public TABLE_READ_PLAN
+{
+public:
+  TRP_INDEX_INTERSECT() {}                        /* Remove gcc warning */
+  virtual ~TRP_INDEX_INTERSECT() {}               /* Remove gcc warning */
+  QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows,
+                             MEM_ROOT *parent_alloc);
+  TRP_RANGE **range_scans; /* array of ptrs to plans of intersected scans */
+  TRP_RANGE **range_scans_end; /* end of the array */
+};
+
+
+/*
   Plan for QUICK_INDEX_MERGE_SELECT scan.
   QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
   is ignored by make_quick.
@@ -2642,6 +2726,35 @@ public:
 };
 
 
+typedef struct st_index_scan_info
+{
+  uint      idx;      /* # of used key in param->keys */
+  uint      keynr;    /* # of used key in table */
+  uint      range_count;
+  ha_rows   records;  /* estimate of # records this scan will return */
+
+  /* Set of intervals over key fields that will be used for row retrieval. */
+  SEL_ARG   *sel_arg;
+
+  KEY *key_info;
+  uint used_key_parts;
+
+  MY_BITMAP used_fields;
+
+  /* Fields used in the query and covered by ROR scan. */
+  MY_BITMAP covered_fields;
+  uint      used_fields_covered; /* # of set bits in covered_fields */
+  int       key_rec_length; /* length of key record (including rowid) */
+
+  /*
+    Cost of reading all index records with values in sel_arg intervals set
+    (assuming there is no need to access full table records)
+  */
+  double    index_read_cost;
+  uint      first_uncovered_field; /* first unused bit in covered_fields */
+  uint      key_components; /* # of parts in the key */
+} INDEX_SCAN_INFO;
+
 /*
   Fill param->needed_fields with bitmap of fields used in the query.
   SYNOPSIS
@@ -2919,6 +3032,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
       */
       TRP_RANGE         *range_trp;
       TRP_ROR_INTERSECT *rori_trp;
+      TRP_INDEX_INTERSECT *intersect_trp;
       bool can_build_covering= FALSE;
       
       remove_nonrange_trees(&param, tree);
@@ -2958,6 +3072,17 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
             best_trp= rori_trp;
         }
       }
+      if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE) &&
+          optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT))
+      {
+        if ((intersect_trp= get_best_index_intersect(&param, tree,
+                                                    best_read_time)))
+        {
+          best_trp= intersect_trp;
+          best_read_time= best_trp->read_cost;
+          
+        }
+      }
 
       if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE))
       {
@@ -4388,7 +4513,9 @@ TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
   imerge_cost +=
     Unique::get_use_cost(param->imerge_cost_buff, (uint)non_cpk_scan_records,
                          param->table->file->ref_length,
-                         param->thd->variables.sortbuff_size);
+                         param->thd->variables.sortbuff_size,
+                         TIME_FOR_COMPARE_ROWID,
+                         FALSE, NULL);
   DBUG_PRINT("info",("index_merge total cost: %g (wanted: less then %g)",
                      imerge_cost, read_time));
   if (imerge_cost < read_time)
@@ -4621,27 +4748,680 @@ TABLE_READ_PLAN *merge_same_index_scans(PARAM *param, SEL_IMERGE *imerge,
   DBUG_RETURN(trp); 
 }
 
-typedef struct st_ror_scan_info
+
+/*
+  This structure contains the info common for all steps of a partial
+  index intersection plan. Morever it contains also the info common
+  for index intersect plans. This info is filled in by the function
+  prepare_search_best just before searching for the best index
+  intersection plan.
+*/  
+
+typedef struct st_common_index_intersection_info
+{
+  PARAM *param;           /* context info for range optimizations            */
+  uint key_size;          /* size of a ROWID element stored in Unique object */
+  uint compare_factor;         /* 1/compare - cost to compare two ROWIDs     */
+  ulonglong max_memory_size;   /* maximum space allowed for Unique objects   */   
+  ha_rows table_cardinality;   /* estimate of the number of records in table */
+  double cutoff_cost;        /* discard index intersects with greater costs  */ 
+  INDEX_SCAN_INFO *cpk_scan;  /* clustered primary key used in intersection  */
+
+  bool in_memory;  /* unique object for intersection is completely in memory */
+  /* estimate of the number of records filtered out from the first scan by
+     ranges for the clustered primary key scan (cpk_scan)                    */
+  ha_rows filtered_out_records;
+  double filter_cost;  /* cost of checking the the cpk_scan rabhe conditions */
+
+  INDEX_SCAN_INFO **search_scans;    /* scans possibly included in intersect */ 
+  uint n_search_scans;               /* number of elements in search_scans   */
+
+  bool best_uses_cpk;   /* current best intersect uses clustered primary key */
+  double best_cost;       /* cost of the current best index intersection     */
+  /* estimate of the number of records in the current best intersection      */
+  ha_rows best_records;
+  uint best_length;    /* number of indexes in the current best intersection */
+  INDEX_SCAN_INFO **best_intersect;  /* the current best index intersection  */
+
+  uint *buff_elems;        /* buffer to calculate cost of index intersection */
+  
+} COMMON_INDEX_INTERSECTION_INFO;
+
+
+/*
+  This structure contains the info specific for one step of an index
+  intersection plan. The structure is filled in by the function 
+   check_index_intersect_extension.
+*/
+
+typedef struct st_partial_index_intersection_info
 {
-  uint      idx;      /* # of used key in param->keys */
-  uint      keynr;    /* # of used key in table */
-  ha_rows   records;  /* estimate of # records this scan will return */
+  COMMON_INDEX_INTERSECTION_INFO *common_info; /* shared by index intersects */
+  uint length;         /* number of index scans in the partial intersection  */
+  ha_rows records;     /* estimate of the number of records in intersection  */
+  double cost;         /* cost of the partial index intersection             */
 
-  /* Set of intervals over key fields that will be used for row retrieval. */
-  SEL_ARG   *sel_arg;
+  /* estimate of total number of records in all index scans of intersection  */
+  ha_rows records_in_scans;
 
-  /* Fields used in the query and covered by this ROR scan. */
-  MY_BITMAP covered_fields;
-  uint      used_fields_covered; /* # of set bits in covered_fields */
-  int       key_rec_length; /* length of key record (including rowid) */
+  /* total cost of the scans of indexes from the partial index intersection  */
+  double index_read_cost; 
 
-  /*
-    Cost of reading all index records with values in sel_arg intervals set
-    (assuming there is no need to access full table records)
-  */
-  double    index_read_cost;
-  uint      first_uncovered_field; /* first unused bit in covered_fields */
-  uint      key_components; /* # of parts in the key */
+  bool with_cpk_filter;      /* cpk filter is to be used for the first scan  */
+  bool in_memory;            /* uses unique object in memory                 */
+  double in_memory_cost;     /* cost of using unique object in memory        */
+         
+  MY_BITMAP *intersect_fields;     /* bitmap of fields used in intersection  */
+} PARTIAL_INDEX_INTERSECTION_INFO;
+
+
+/* Check whether two indexes have the same first n components */
+
+static
+bool same_index_prefix(KEY *key1, KEY *key2, uint used_parts)
+{
+  KEY_PART_INFO *part1= key1->key_part;
+  KEY_PART_INFO *part2= key2->key_part;
+  for(uint i= 0; i < used_parts; i++, part1++, part2++)
+  {
+    if (part1->fieldnr != part2->fieldnr)
+      return FALSE;
+  }
+  return TRUE;
+}
+
+
+/* Create a bitmap for all fields of a table */
+
+static
+bool create_fields_bitmap(PARAM *param, MY_BITMAP *fields_bitmap)
+{
+  my_bitmap_map *bitmap_buf;
+
+  if (!(bitmap_buf= (my_bitmap_map *) alloc_root(param->mem_root,
+                                                 param->fields_bitmap_size)))
+    return TRUE;
+  if (bitmap_init(fields_bitmap, bitmap_buf, param->table->s->fields, FALSE))
+    return TRUE;
+  
+  return FALSE;
+}
+
+/* Compare two indexes scans for sort before search for the best intersection */
+
+static
+int cmp_intersect_index_scan(INDEX_SCAN_INFO **a, INDEX_SCAN_INFO **b)
+{
+  return (*a)->records < (*b)->records ?
+          -1 : (*a)->records == (*b)->records ? 0 : 1;
+}
+
+
+/*
+  Round up table cardinality read from statistics provided by engine.
+  This function should go away when mysql test will allow to handle
+  more or less easily in the test suites deviations of InnoDB 
+  statistical data.
+*/
+ 
+static inline
+ha_rows get_table_cardinality_for_index_intersect(TABLE *table)
+{
+  if (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT)
+    return table->file->stats.records;
+  else
+  {
+    ha_rows d;
+    double q;
+    for (q= table->file->stats.records, d= 1 ; q >= 10; q/= 10, d*= 10 ) ;
+    return (ha_rows) (round(q) * d);
+  } 
+}
+
+  
+/*
+  Prepare to search for the best index intersection
+
+  SYNOPSIS
+    prepare_search_best_index_intersect()
+      param         common info about index ranges
+      tree          tree of ranges for indexes than can be intersected
+      common    OUT info needed for search to be filled by the function 
+      init      OUT info for an initial pseudo step of the intersection plans
+      cutoff_cost   cut off cost of the interesting index intersection 
+
+  NOTES
+    The function initializes all fields of the structure 'common' to be used
+    when searching for the best intersection plan. It also allocates
+    memory to store the most cheap index intersection.
+
+  RETURN
+    FALSE  in the case of success
+    TRUE   otherwise
+*/
+
+static
+bool prepare_search_best_index_intersect(PARAM *param, 
+                                         SEL_TREE *tree,
+                                         COMMON_INDEX_INTERSECTION_INFO *common,
+                                         PARTIAL_INDEX_INTERSECTION_INFO *init,
+                                         double cutoff_cost)
+{
+  uint i;
+  double cost;
+  INDEX_SCAN_INFO **index_scan;
+  INDEX_SCAN_INFO **scan_ptr;
+  INDEX_SCAN_INFO *cpk_scan= NULL;
+  TABLE *table= param->table;
+  uint n_index_scans= tree->index_scans_end - tree->index_scans;
+
+  if (!n_index_scans)
+    return 1;
+
+  bzero(init, sizeof(PARTIAL_INDEX_INTERSECTION_INFO));
+  init->common_info= common;
+  init->cost= cutoff_cost+2*0.01;
+
+  common->param= param;
+  common->key_size= table->file->ref_length;
+  common->compare_factor= TIME_FOR_COMPARE_ROWID;
+  common->max_memory_size= param->thd->variables.sortbuff_size;
+  common->cutoff_cost= cutoff_cost;
+  common->cpk_scan= NULL;
+  common->filtered_out_records= 0;
+  common->table_cardinality= 
+    get_table_cardinality_for_index_intersect(table);
+
+  if (n_index_scans <= 1)
+    return TRUE;
+
+  for (i=0, index_scan= tree->index_scans; i < n_index_scans; i++, index_scan++)
+  {  
+    if ((*index_scan)->keynr == table->s->primary_key &&
+        table->file->primary_key_is_clustered())
+    {
+      common->cpk_scan= cpk_scan= *index_scan;
+      break;
+    }
+  }
+
+  i= n_index_scans - test(cpk_scan != NULL) + 1;
+
+  if (!(common->search_scans =
+	(INDEX_SCAN_INFO **) alloc_root (param->mem_root,
+                                         sizeof(INDEX_SCAN_INFO *) * i)))
+    return TRUE;
+  bzero(common->search_scans, sizeof(INDEX_SCAN_INFO *) * i);
+
+  INDEX_SCAN_INFO **selected_index_scans= common->search_scans;
+    
+  for (i=0, index_scan= tree->index_scans; i < n_index_scans; i++, index_scan++)
+  {
+    uint used_key_parts= (*index_scan)->used_key_parts;
+    KEY *key_info= (*index_scan)->key_info;
+
+    if (*index_scan == cpk_scan)
+      continue;
+    if (cpk_scan && cpk_scan->used_key_parts == used_key_parts &&
+        same_index_prefix(cpk_scan->key_info, key_info, used_key_parts))
+      continue;
+
+    cost= table->file->keyread_time((*index_scan)->keynr,
+                                    (*index_scan)->range_count,
+                                    (*index_scan)->records);
+    if (cost >= cutoff_cost)
+      continue;
+   
+    for (scan_ptr= selected_index_scans; *scan_ptr ; scan_ptr++)
+    {
+      if ((*scan_ptr)->used_key_parts == used_key_parts &&
+          same_index_prefix((*scan_ptr)->key_info, key_info, used_key_parts))
+        break;
+    }
+    if (!*scan_ptr || cost < (*scan_ptr)->index_read_cost)
+    {
+      (*index_scan)->index_read_cost= cost;
+      *scan_ptr= *index_scan;
+    }
+  } 
+
+  ha_rows records_in_scans= 0;
+
+  for (scan_ptr=selected_index_scans, i= 0; *scan_ptr; scan_ptr++, i++)
+  {
+    if (create_fields_bitmap(param, &(*scan_ptr)->used_fields))
+      return TRUE;
+    records_in_scans+= (*scan_ptr)->records;
+  }
+
+  if (cpk_scan && create_fields_bitmap(param, &cpk_scan->used_fields))
+    return TRUE;
+  
+  if (!(common->n_search_scans= i))
+    return TRUE;
+    
+  common->best_uses_cpk= FALSE;
+  common->best_cost= cutoff_cost + 0.01;
+  common->best_length= 0;
+
+  if (!(common->best_intersect=
+	(INDEX_SCAN_INFO **) alloc_root (param->mem_root,
+                                         sizeof(INDEX_SCAN_INFO *) *
+                                         (i + test(cpk_scan != NULL)))))
+    return TRUE;
+
+  uint calc_cost_buff_size=
+         Unique::get_cost_calc_buff_size(records_in_scans,
+                                         common->key_size,
+				         common->max_memory_size);
+  if (!(common->buff_elems= (uint *) alloc_root(param->mem_root,
+                                                calc_cost_buff_size)))
+    return TRUE;
+
+  my_qsort(selected_index_scans, i, sizeof(INDEX_SCAN_INFO *),
+           (qsort_cmp) cmp_intersect_index_scan);
+
+  return FALSE;
+}
+
+
+static inline
+void set_field_bitmap_for_index_prefix(MY_BITMAP *field_bitmap,
+                                       KEY_PART_INFO *key_part,
+                                       uint used_key_parts)
+{
+  bitmap_clear_all(field_bitmap);
+  for (KEY_PART_INFO *key_part_end= key_part+used_key_parts;
+       key_part < key_part_end; key_part++)
+  {
+    bitmap_set_bit(field_bitmap, key_part->fieldnr-1);
+  }
+}
+
+/*
+  Estimate the number of records selected by an extension a partial intersection
+
+  SYNOPSIS
+    records_in_index_intersect_extension()
+     curr            partial intersection plan to be extended
+     ext_index_scan  the evaluated extension of this partial plan
+
+  NOTES
+    The function figures out how many records can be expected if the
+    index scans from curr is intersected with ext_index_scan
+
+  RETURN
+    The expected number of rows in the extended index intersection
+*/
+
+static
+ha_rows records_in_index_intersect_extension(PARTIAL_INDEX_INTERSECTION_INFO *curr,
+                                             INDEX_SCAN_INFO *ext_index_scan)
+{
+  KEY *key_info= ext_index_scan->key_info;
+  KEY_PART_INFO* key_part= key_info->key_part;
+  KEY_PART_INFO* key_part_end= key_part+ext_index_scan->used_key_parts;
+  uint key_parts= key_info->key_parts;
+  MY_BITMAP *used_fields= &ext_index_scan->used_fields;
+  
+  if (!curr->length)
+  {
+    set_field_bitmap_for_index_prefix(used_fields, key_part,
+                                      ext_index_scan->used_key_parts);
+    return ext_index_scan->records;
+  }
+  else
+  {
+    bool better_selectivity= FALSE;
+    ha_rows table_cardinality= curr->common_info->table_cardinality;
+    ha_rows records= curr->records;
+    bitmap_copy(used_fields, curr->intersect_fields);
+    records= (double) records / table_cardinality * ext_index_scan->records;
+    set_if_bigger(records, 1);
+    for (uint i= 0 ; key_part < key_part_end; i++, key_part++)
+    {
+      if (bitmap_is_set(used_fields, key_part->fieldnr-1))
+      {
+        ulong *rec_per_key= key_info->rec_per_key+i;
+        ulong f1= rec_per_key[0] ? rec_per_key[0] : 1;
+        ulong f2= i+1 < key_parts && rec_per_key[1] ? rec_per_key[1] : 1;
+	records= (double) records / f2 * f1;
+      }
+      else
+      { 
+        better_selectivity= TRUE;
+        bitmap_set_bit(used_fields, key_part->fieldnr-1);
+      }
+    }
+    return !better_selectivity ? curr->records+1 :
+                                 !records ? 1 : records;
+  }  
+}
+
+
+static inline
+double get_unique_intersect_cost(COMMON_INDEX_INTERSECTION_INFO *common,
+                                 uint length, ha_rows records_in_scans,
+                                 ha_rows filtered_out_records,
+                                 ha_rows last_index_records,
+                                 bool *in_memory,
+                                 double *in_memory_cost)
+{
+  double cost;
+  if (length > 1 && *in_memory)
+  { 
+    ha_rows records_in_first_scan= common->search_scans[0]->records;
+    ha_rows elems_in_tree= records_in_first_scan-filtered_out_records;
+    *in_memory_cost+= Unique::get_search_cost(elems_in_tree,
+                                              common->compare_factor) * 
+                      last_index_records;
+    cost= *in_memory_cost;
+  }
+  else
+  {
+    ha_rows records_to_intersect= records_in_scans-filtered_out_records;
+    cost= Unique::get_use_cost(common->buff_elems,
+                               records_to_intersect,
+                               common->key_size,
+                               common->max_memory_size,
+                               common->compare_factor,
+                               TRUE, in_memory);
+    if (*in_memory)
+      *in_memory_cost= cost;
+  }
+  return cost;
+}
+
+
+static inline
+double get_cpk_filter_cost(INDEX_SCAN_INFO *index_scan, 
+                           INDEX_SCAN_INFO *cpk_scan,
+                           double compare_factor)
+{
+  return log((double) (cpk_scan->range_count+1)) / (compare_factor * M_LN2) *
+         index_scan->records;
+}
+
+
+/*
+  Check whether a patial index intersection plan can be extended 
+
+  SYNOPSIS
+    check_index_intersect_extension()
+     curr            partial intersection plan to be extended
+     ext_index_scan  a possible extension of this plan to be checked
+     next       OUT  the structure to be filled for the extended plan 
+
+  NOTES
+    The function checks whether it makes sense to extend the index
+    intersection plan adding the index ext_index_scan, and, if this
+    the case, the function fills in the structure fir the extended plan.
+
+  RETURN
+    TRUE      if the given plan makes to extend
+    FALSE     otherwise
+*/
+
+static
+bool check_index_intersect_extension(PARTIAL_INDEX_INTERSECTION_INFO *curr,
+                                     INDEX_SCAN_INFO *ext_index_scan,
+                                     PARTIAL_INDEX_INTERSECTION_INFO *next)
+{
+  ha_rows records;
+  ha_rows records2;
+  ha_rows records_in_scans;
+  double cost;
+  ha_rows filtered_out_records= 0;
+  ha_rows index_scan_records= ext_index_scan->records;
+  COMMON_INDEX_INTERSECTION_INFO *common_info= curr->common_info;
+  INDEX_SCAN_INFO *cpk_scan= common_info->cpk_scan;
+  double cutoff_cost= common_info->cutoff_cost;
+  uint compare_factor= common_info->compare_factor;
+  uint idx= curr->length;
+  bool with_cpk_filter= curr->with_cpk_filter;
+
+  if (with_cpk_filter)
+    filtered_out_records= common_info->filtered_out_records; 
+
+  next->index_read_cost= curr->index_read_cost+ext_index_scan->index_read_cost;
+  if (next->index_read_cost > cutoff_cost)
+    return FALSE; 
+
+  records_in_scans= curr->records_in_scans + index_scan_records;
+  if ((next->in_memory= curr->in_memory))
+    next->in_memory_cost= curr->in_memory_cost;
+
+  records= records_in_index_intersect_extension(curr, ext_index_scan);
+  if (idx && records > curr->records)
+    return FALSE;
+
+  next->records= records;
+  next->intersect_fields= &ext_index_scan->used_fields;
+
+  cost= get_unique_intersect_cost(common_info, idx+1, records_in_scans,
+                                  filtered_out_records, index_scan_records,
+                                  &next->in_memory, &next->in_memory_cost);
+                                               
+  if (idx == 0 && cpk_scan)
+  {
+    next->length= 1;
+    records2= records_in_index_intersect_extension(next, cpk_scan);
+    next->length= 0;
+    if (records2 < records)
+      filtered_out_records= records-records2;
+  
+    common_info->filter_cost= get_cpk_filter_cost(ext_index_scan, cpk_scan,
+                                                  compare_factor);
+    common_info->filtered_out_records= filtered_out_records;
+  }
+  
+  next->records_in_scans= records_in_scans;
+  next->with_cpk_filter= with_cpk_filter;
+     
+  if (!with_cpk_filter && common_info->filtered_out_records)
+  {
+    double cost2;
+    bool in_memory_save= next->in_memory;
+    if (idx)
+    {
+      next->length= curr->length+1;
+      records2= records_in_index_intersect_extension(next, cpk_scan);
+      next->length= curr->length;
+    }
+    cost2= get_unique_intersect_cost(common_info, idx+1, records_in_scans,
+                                     filtered_out_records, index_scan_records, 
+                                     &next->in_memory, &next->in_memory_cost);
+    cost2+= common_info->filter_cost;
+    if (cost2 < cost)
+    {
+      cost= cost2;
+      records= records2;
+      next->with_cpk_filter= TRUE;
+      *next->intersect_fields= cpk_scan->used_fields;
+    }
+    else
+      next->in_memory= in_memory_save;
+  }
+   
+  cost+= next->index_read_cost;
+  if (cost >= cutoff_cost)
+    return FALSE;
+
+  next->records= records;
+
+  cost+=  get_sweep_read_cost(common_info->param, records);
+
+  next->cost= cost;
+  next->length= curr->length+1;
+
+  return TRUE;
+}
+
+
+/*
+  Search for the cheapest extensions of range scans used to access a table    
+
+  SYNOPSIS
+    find_index_intersect_best_extension()
+      curr        partial intersection to evaluate all possible extension for 
+
+  NOTES
+    The function tries to extend the partial plan curr in all possible ways
+    to look for a cheapest index intersection whose cost less than the 
+    cut off value set in curr->common_info.cutoff_cost. 
+*/
+
+static 
+void find_index_intersect_best_extension(PARTIAL_INDEX_INTERSECTION_INFO *curr)
+{
+  PARTIAL_INDEX_INTERSECTION_INFO next;
+  COMMON_INDEX_INTERSECTION_INFO *common_info= curr->common_info;
+  INDEX_SCAN_INFO **index_scans= common_info->search_scans;
+  uint idx= curr->length;
+  INDEX_SCAN_INFO **rem_first_index_scan_ptr= &index_scans[idx];
+  double cost= curr->cost;
+
+  if (cost < common_info->best_cost)
+  {
+    common_info->best_cost= cost;
+    common_info->best_length= curr->length;
+    common_info->best_records= curr->records;
+    common_info->best_uses_cpk= curr->with_cpk_filter;
+    uint sz= sizeof(INDEX_SCAN_INFO *) * curr->length;
+    memcpy(common_info->best_intersect, common_info->search_scans, sz);
+    common_info->cutoff_cost= cost;
+  }   
+
+  if (!(*rem_first_index_scan_ptr))
+    return;  
+
+  next.common_info= common_info;
+ 
+  INDEX_SCAN_INFO *rem_first_index_scan= *rem_first_index_scan_ptr;
+  for (INDEX_SCAN_INFO **index_scan_ptr= rem_first_index_scan_ptr;
+       *index_scan_ptr; index_scan_ptr++)
+  {
+    *rem_first_index_scan_ptr= *index_scan_ptr;
+    *index_scan_ptr= rem_first_index_scan;
+    if (check_index_intersect_extension(curr, *rem_first_index_scan_ptr, &next))
+      find_index_intersect_best_extension(&next);
+    *index_scan_ptr= *rem_first_index_scan_ptr;
+    *rem_first_index_scan_ptr= rem_first_index_scan;
+  }
+}
+
+
+/*
+  Get the plan of the best intersection of range scans used to access a table    
+
+  SYNOPSIS
+    get_best_index_intersect()
+      param         common info about index ranges
+      tree          tree of ranges for indexes than can be intersected
+      read_time     cut off value for the evaluated plans 
+
+  NOTES
+    The function looks for the cheapest index intersection of the range
+    scans to access a table. The info about the ranges for all indexes
+    is provided by the range optimizer and is passed through the
+    parameters param and tree. Any plan whose cost is greater than read_time
+    is rejected. 
+    After the best index intersection is found the function constructs
+    the structure that manages the execution by the chosen plan.
+
+  RETURN
+    Pointer to the generated execution structure if a success,
+    0 - otherwise.
+*/
+
+static
+TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree,
+                                              double read_time)
+{
+  uint i;
+  uint count;
+  TRP_RANGE **cur_range;
+  TRP_RANGE **range_scans;
+  INDEX_SCAN_INFO *index_scan;
+  COMMON_INDEX_INTERSECTION_INFO common;
+  PARTIAL_INDEX_INTERSECTION_INFO init;
+  TRP_INDEX_INTERSECT *intersect_trp= NULL;
+  TABLE *table= param->table;
+  
+  
+  DBUG_ENTER("get_best_index_intersect");
+
+  if (prepare_search_best_index_intersect(param, tree, &common, &init,
+                                          read_time))
+    DBUG_RETURN(NULL);
+
+  find_index_intersect_best_extension(&init);
+
+  if (common.best_length <= 1 && !common.best_uses_cpk)
+    DBUG_RETURN(NULL);
+
+  if (common.best_uses_cpk)
+  {
+    memmove((char *) (common.best_intersect+1), (char *) common.best_intersect,
+            sizeof(INDEX_SCAN_INFO *) * common.best_length);
+    common.best_intersect[0]= common.cpk_scan;
+    common.best_length++;
+  }
+
+  count= common.best_length;
+
+  if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,
+                                            sizeof(TRP_RANGE *)*
+                                            count)))
+    DBUG_RETURN(NULL);
+
+  for (i= 0, cur_range= range_scans; i < count; i++)
+  {
+    index_scan= common.best_intersect[i];
+    if ((*cur_range= new (param->mem_root) TRP_RANGE(index_scan->sel_arg,
+                                                     index_scan->idx)))
+    {  
+      TRP_RANGE *trp= *cur_range;  
+      trp->read_cost= index_scan->index_read_cost;  
+      trp->records= index_scan->records;
+      trp->is_ror= FALSE;
+      table->intersect_keys.set_bit(index_scan->keynr);
+      cur_range++;
+    }
+  }
+  
+  count= tree->index_scans_end - tree->index_scans;
+  for (i= 0; i < count; i++)
+  {
+    index_scan= tree->index_scans[i]; 
+    if (!table->intersect_keys.is_set(index_scan->keynr))
+    {
+      for (uint j= 0; j < common.best_length; j++)
+      {
+	INDEX_SCAN_INFO *scan= common.best_intersect[j];
+        if (same_index_prefix(index_scan->key_info, scan->key_info,
+                              scan->used_key_parts))
+	{
+          table->intersect_keys.set_bit(index_scan->keynr);
+          break;
+        } 
+      }
+    }
+  }
+      
+  if ((intersect_trp= new (param->mem_root)TRP_INDEX_INTERSECT))
+  {
+    intersect_trp->read_cost= common.best_cost;
+    intersect_trp->records= common.best_records;
+    intersect_trp->range_scans= range_scans;
+    intersect_trp->range_scans_end= cur_range;
+  }
+  DBUG_RETURN(intersect_trp);
+}
+
+
+typedef struct st_ror_scan_info : INDEX_SCAN_INFO
+{ 
 } ROR_SCAN_INFO;
 
 
@@ -5313,7 +6093,7 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
 /*
   Get best covering ROR-intersection.
   SYNOPSIS
-    get_best_covering_ror_intersect()
+    get_best_ntersectcovering_ror_intersect()
       param     Parameter from test_quick_select function.
       tree      SEL_TREE with sets of intervals for different keys.
       read_time Don't return table read plans with cost > read_time.
@@ -5500,6 +6280,14 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
                                       "tree scans"););
   tree->ror_scans_map.clear_all();
   tree->n_ror_scans= 0;
+  tree->index_scans= 0;
+  if (!tree->keys_map.is_clear_all())
+  {
+    tree->index_scans=
+      (INDEX_SCAN_INFO **) alloc_root(param->mem_root,
+                                      sizeof(INDEX_SCAN_INFO *) * param->keys);
+  }
+  tree->index_scans_end= tree->index_scans;                                                  
   for (idx= 0,key=tree->keys, end=key+param->keys;
        key != end ;
        key++,idx++)
@@ -5508,6 +6296,7 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
     double found_read_time;
     if (*key)
     {
+      INDEX_SCAN_INFO *index_scan;
       uint keynr= param->real_keynr[idx];
       if ((*key)->type == SEL_ARG::MAYBE_KEY ||
           (*key)->maybe_flag)
@@ -5517,6 +6306,19 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
                             (bool) param->table->covering_keys.is_set(keynr);
 
       found_records= check_quick_select(param, idx, *key, update_tbl_stats);
+      if (found_records != HA_POS_ERROR && tree->index_scans &&
+          (index_scan= (INDEX_SCAN_INFO *)alloc_root(param->mem_root,
+						     sizeof(INDEX_SCAN_INFO))))
+      {
+        index_scan->idx= idx;
+        index_scan->keynr= keynr;
+        index_scan->key_info= &param->table->key_info[keynr];
+        index_scan->used_key_parts= param->max_key_part+1;
+        index_scan->range_count= param->range_count;
+        index_scan->records= found_records;
+        index_scan->sel_arg= *key;
+        *tree->index_scans_end++= index_scan;
+      }        
       if (param->is_ror_scan)
       {
         tree->n_ror_scans++;
@@ -5611,6 +6413,35 @@ QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param,
   return quick_imerge;
 }
 
+
+QUICK_SELECT_I *TRP_INDEX_INTERSECT::make_quick(PARAM *param,
+                                                bool retrieve_full_rows,
+                                                MEM_ROOT *parent_alloc)
+{
+  QUICK_INDEX_INTERSECT_SELECT *quick_intersect;
+  QUICK_RANGE_SELECT *quick;
+  /* index_merge always retrieves full rows, ignore retrieve_full_rows */
+  if (!(quick_intersect= new QUICK_INDEX_INTERSECT_SELECT(param->thd, param->table)))
+    return NULL;
+
+  quick_intersect->records= records;
+  quick_intersect->read_time= read_cost;
+  for (TRP_RANGE **range_scan= range_scans; range_scan != range_scans_end;
+       range_scan++)
+  {
+    if (!(quick= (QUICK_RANGE_SELECT*)
+          ((*range_scan)->make_quick(param, FALSE, &quick_intersect->alloc)))||
+        quick_intersect->push_quick_back(quick))
+    {
+      delete quick;
+      delete quick_intersect;
+      return NULL;
+    }
+  }
+  return quick_intersect;
+}
+
+
 QUICK_SELECT_I *TRP_ROR_INTERSECT::make_quick(PARAM *param,
                                               bool retrieve_full_rows,
                                               MEM_ROOT *parent_alloc)
@@ -9008,6 +9839,18 @@ bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const MY_BITMAP *fields)
   return 0;
 }
 
+bool QUICK_INDEX_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields)
+{
+  QUICK_RANGE_SELECT *quick;
+  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+  while ((quick= it++))
+  {
+    if (is_key_used(head, quick->index, fields))
+      return 1;
+  }
+  return 0;
+}
+
 bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields)
 {
   QUICK_SELECT_WITH_RECORD *qr;
@@ -9153,13 +9996,20 @@ err:
     other error
 */
 
-int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
+int read_keys_and_merge_scans(THD *thd,
+                              TABLE *head,
+                              List<QUICK_RANGE_SELECT> quick_selects,
+                              QUICK_RANGE_SELECT *pk_quick_select,
+                              READ_RECORD *read_record,
+                              bool intersection,
+                              Unique **unique_ptr)
 {
   List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
   QUICK_RANGE_SELECT* cur_quick;
   int result;
+  Unique *unique= *unique_ptr;
   handler *file= head->file;
-  DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");
+  DBUG_ENTER("read_keys_and_merge");
 
   /* We're going to just read rowids. */
   if (!head->key_read)
@@ -9170,6 +10020,7 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
 
   cur_quick_it.rewind();
   cur_quick= cur_quick_it++;
+  bool first_quick= TRUE;
   DBUG_ASSERT(cur_quick != 0);
   
   /*
@@ -9187,9 +10038,11 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
 
     unique= new Unique(refpos_order_cmp, (void *)file,
                        file->ref_length,
-                       thd->variables.sortbuff_size);
+                       thd->variables.sortbuff_size,
+		       intersection ? quick_selects.elements : 0);                     
     if (!unique)
       goto err;
+    *unique_ptr= unique;
   }
   else
     unique->reset();
@@ -9201,6 +10054,12 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
   {
     while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
     {
+      if (first_quick)
+      {
+        first_quick= FALSE;
+        if (intersection && unique->is_in_memory())
+          unique->close_for_expansion();
+      }
       cur_quick->range_end();
       cur_quick= cur_quick_it++;
       if (!cur_quick)
@@ -9225,10 +10084,18 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
     if (thd->killed)
       goto err;
 
-    /* skip row if it will be retrieved by clustered PK scan */
-    if (pk_quick_select && pk_quick_select->row_in_ranges())
-      continue;
-
+    if (intersection)
+    {
+      if (first_quick && 
+          pk_quick_select && !pk_quick_select->row_in_ranges())
+        continue;
+    }
+    else
+    {
+       /* skip row if it will be retrieved by clustered PK scan */
+      if (pk_quick_select && pk_quick_select->row_in_ranges())
+        continue;
+    }
     cur_quick->file->position(cur_quick->record);
     if (unique->unique_add((char*)cur_quick->file->ref))
       goto err;
@@ -9240,12 +10107,11 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
     sequence.
   */
   result= unique->get(head);
-  doing_pk_scan= FALSE;
   /*
     index_merge currently doesn't support "using index" at all
   */
   head->disable_keyread();
-  init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE);
+  init_read_record(read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE);
   DBUG_RETURN(result);
 
 err:
@@ -9254,6 +10120,17 @@ err:
 }
 
 
+int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
+
+{
+  int result;
+  DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");
+  result= read_keys_and_merge_scans(thd, head, quick_selects, pk_quick_select,
+                                    &read_record, FALSE, &unique);
+  doing_pk_scan= FALSE;
+  DBUG_RETURN(result);
+}
+
 /*
   Get next row for index_merge.
   NOTES
@@ -9290,6 +10167,33 @@ int QUICK_INDEX_MERGE_SELECT::get_next()
   DBUG_RETURN(result);
 }
 
+int QUICK_INDEX_INTERSECT_SELECT::read_keys_and_merge()
+
+{
+  int result;
+  DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::read_keys_and_merge");
+  result= read_keys_and_merge_scans(thd, head, quick_selects, pk_quick_select,
+                                    &read_record, TRUE, &unique);
+  doing_pk_scan= FALSE;
+  DBUG_RETURN(result);
+}
+
+int QUICK_INDEX_INTERSECT_SELECT::get_next()
+{
+  int result;
+  DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::get_next");
+
+  if ((result= read_record.read_record(&read_record)) == -1)
+  {
+    result= HA_ERR_END_OF_FILE;
+    end_read_record(&read_record);
+    free_io_cache(head);
+    /* All rows from Unique have been retrieved, do a clustered PK scan */
+  }
+
+  DBUG_RETURN(result);
+}
+
 
 /*
   Retrieve next record.
@@ -9999,30 +10903,53 @@ bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
 }
 
 
-void QUICK_RANGE_SELECT::add_info_string(String *str)
+void QUICK_SELECT_I::add_key_name(String *str, bool *first)
 {
   KEY *key_info= head->key_info + index;
+
+  if (*first)
+    *first= FALSE;
+  else
+    str->append(',');
   str->append(key_info->name);
 }
+ 
+
+void QUICK_RANGE_SELECT::add_info_string(String *str)
+{
+  bool first= TRUE;
+  
+  add_key_name(str, &first);
+}
 
 void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
 {
   QUICK_RANGE_SELECT *quick;
   bool first= TRUE;
   List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+
   str->append(STRING_WITH_LEN("sort_union("));
   while ((quick= it++))
   {
-    if (!first)
-      str->append(',');
-    else
-      first= FALSE;
-    quick->add_info_string(str);
+    quick->add_key_name(str, &first);
   }
   if (pk_quick_select)
+    pk_quick_select->add_key_name(str, &first);
+  str->append(')');
+}
+
+void QUICK_INDEX_INTERSECT_SELECT::add_info_string(String *str)
+{
+  QUICK_RANGE_SELECT *quick;
+  bool first= TRUE;
+  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+
+  str->append(STRING_WITH_LEN("sort_intersect("));
+  if (pk_quick_select)
+    pk_quick_select->add_key_name(str, &first);
+  while ((quick= it++))
   {
-    str->append(',');
-    pk_quick_select->add_info_string(str);
+    quick->add_key_name(str, &first);
   }
   str->append(')');
 }
@@ -10032,129 +10959,125 @@ void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
   bool first= TRUE;
   QUICK_SELECT_WITH_RECORD *qr;
   List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects);
+
   str->append(STRING_WITH_LEN("intersect("));
   while ((qr= it++))
   {
-    KEY *key_info= head->key_info + qr->quick->index;
-    if (!first)
-      str->append(',');
-    else
-      first= FALSE;
-    str->append(key_info->name);
+    qr->quick->add_key_name(str, &first);
   }
   if (cpk_quick)
-  {
-    KEY *key_info= head->key_info + cpk_quick->index;
-    str->append(',');
-    str->append(key_info->name);
-  }
+    cpk_quick->add_key_name(str, &first);
   str->append(')');
 }
 
+
 void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
 {
-  bool first= TRUE;
   QUICK_SELECT_I *quick;
+  bool first= TRUE;
   List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
+
   str->append(STRING_WITH_LEN("union("));
   while ((quick= it++))
   {
-    if (!first)
-      str->append(',');
-    else
+    if (first)
       first= FALSE;
+    else
+      str->append(',');
     quick->add_info_string(str);
   }
   str->append(')');
 }
 
 
-void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
-                                              String *used_lengths)
+void QUICK_SELECT_I::add_key_and_length(String *key_names,
+                                        String *used_lengths,
+                                        bool *first)
 {
   char buf[64];
   uint length;
   KEY *key_info= head->key_info + index;
+
+  if (*first)
+    *first= FALSE;
+  else
+  {
+    key_names->append(',');
+    used_lengths->append(',');
+  }
   key_names->append(key_info->name);
   length= longlong2str(max_used_key_length, buf, 10) - buf;
   used_lengths->append(buf, length);
 }
 
+
+void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
+                                              String *used_lengths)
+{
+  bool first= TRUE;
+
+  add_key_and_length(key_names, used_lengths, &first);
+}
+
 void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
                                                     String *used_lengths)
 {
-  char buf[64];
-  uint length;
-  bool first= TRUE;
   QUICK_RANGE_SELECT *quick;
+  bool first= TRUE;
 
   List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+
   while ((quick= it++))
   {
-    if (first)
-      first= FALSE;
-    else
-    {
-      key_names->append(',');
-      used_lengths->append(',');
-    }
-
-    KEY *key_info= head->key_info + quick->index;
-    key_names->append(key_info->name);
-    length= longlong2str(quick->max_used_key_length, buf, 10) - buf;
-    used_lengths->append(buf, length);
+    quick->add_key_and_length(key_names, used_lengths, &first);
   }
+
   if (pk_quick_select)
+    pk_quick_select->add_key_and_length(key_names, used_lengths, &first);
+}
+
+
+void QUICK_INDEX_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
+                                                        String *used_lengths)
+{
+  QUICK_RANGE_SELECT *quick;
+  bool first= TRUE;
+
+  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+
+  if (pk_quick_select)
+    pk_quick_select->add_key_and_length(key_names, used_lengths, &first);
+
+  while ((quick= it++))
   {
-    KEY *key_info= head->key_info + pk_quick_select->index;
-    key_names->append(',');
-    key_names->append(key_info->name);
-    length= longlong2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
-    used_lengths->append(',');
-    used_lengths->append(buf, length);
+    quick->add_key_and_length(key_names, used_lengths, &first);
   }
 }
 
 void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
                                                       String *used_lengths)
 {
-  char buf[64];
-  uint length;
-  bool first= TRUE;
   QUICK_SELECT_WITH_RECORD *qr;
+  bool first= TRUE;
+
   List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects);
+
   while ((qr= it++))
   {
-    KEY *key_info= head->key_info + qr->quick->index;
-    if (first)
-      first= FALSE;
-    else
-    {
-      key_names->append(',');
-      used_lengths->append(',');
-    }
-    key_names->append(key_info->name);
-    length= longlong2str(qr->quick->max_used_key_length, buf, 10) - buf;
-    used_lengths->append(buf, length);
+    qr->quick->add_key_and_length(key_names, used_lengths, &first);
   }
-
   if (cpk_quick)
-  {
-    KEY *key_info= head->key_info + cpk_quick->index;
-    key_names->append(',');
-    key_names->append(key_info->name);
-    length= longlong2str(cpk_quick->max_used_key_length, buf, 10) - buf;
-    used_lengths->append(',');
-    used_lengths->append(buf, length);
-  }
+    cpk_quick->add_key_and_length(key_names, used_lengths, &first);
 }
 
 void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
                                                   String *used_lengths)
 {
-  bool first= TRUE;
   QUICK_SELECT_I *quick;
+  bool first= TRUE;
+
   List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
+
   while ((quick= it++))
   {
     if (first)
@@ -12300,11 +13223,9 @@ void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
 void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
                                                       String *used_lengths)
 {
-  char buf[64];
-  uint length;
-  key_names->append(index_info->name);
-  length= longlong2str(max_used_key_length, buf, 10) - buf;
-  used_lengths->append(buf, length);
+  bool first= TRUE;
+
+  add_key_and_length(key_names, used_lengths, &first);
 }
 
 
@@ -12486,6 +13407,22 @@ void QUICK_INDEX_MERGE_SELECT::dbug_dump(int indent, bool verbose)
   fprintf(DBUG_FILE, "%*s}\n", indent, "");
 }
 
+void QUICK_INDEX_INTERSECT_SELECT::dbug_dump(int indent, bool verbose)
+{
+  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+  QUICK_RANGE_SELECT *quick;
+  fprintf(DBUG_FILE, "%*squick index_intersect select\n", indent, "");
+  fprintf(DBUG_FILE, "%*smerged scans {\n", indent, "");
+  while ((quick= it++))
+    quick->dbug_dump(indent+2, verbose);
+  if (pk_quick_select)
+  {
+    fprintf(DBUG_FILE, "%*sclustered PK quick:\n", indent, "");
+    pk_quick_select->dbug_dump(indent+2, verbose);
+  }
+  fprintf(DBUG_FILE, "%*s}\n", indent, "");
+}
+
 void QUICK_ROR_INTERSECT_SELECT::dbug_dump(int indent, bool verbose)
 {
   List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects);
diff --git a/sql/opt_range.h b/sql/opt_range.h
index 1e3008d78aa..d894cfaf91d 100644
--- a/sql/opt_range.h
+++ b/sql/opt_range.h
@@ -274,12 +274,13 @@ public:
 
   enum {
     QS_TYPE_RANGE = 0,
-    QS_TYPE_INDEX_MERGE = 1,
-    QS_TYPE_RANGE_DESC = 2,
-    QS_TYPE_FULLTEXT   = 3,
-    QS_TYPE_ROR_INTERSECT = 4,
-    QS_TYPE_ROR_UNION = 5,
-    QS_TYPE_GROUP_MIN_MAX = 6
+    QS_TYPE_INDEX_INTERSECT = 1,
+    QS_TYPE_INDEX_MERGE = 2,
+    QS_TYPE_RANGE_DESC = 3,
+    QS_TYPE_FULLTEXT   = 4,
+    QS_TYPE_ROR_INTERSECT = 5,
+    QS_TYPE_ROR_UNION = 6,
+    QS_TYPE_GROUP_MIN_MAX = 7
   };
 
   /* Get type of this quick select - one of the QS_TYPE_* values */
@@ -305,6 +306,10 @@ public:
     Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
   */
   virtual void save_last_pos(){};
+  
+  void add_key_and_length(String *key_names,
+                          String *used_lengths,
+                          bool *first);
 
   /*
     Append comma-separated list of keys this quick select uses to key_names;
@@ -314,13 +319,15 @@ public:
   virtual void add_keys_and_lengths(String *key_names,
                                     String *used_lengths)=0;
 
+  void add_key_name(String *str, bool *first);
+
   /*
     Append text representation of quick select structure (what and how is
     merged) to str. The result is added to "Extra" field in EXPLAIN output.
     This function is implemented only by quick selects that merge other quick
     selects output and/or can produce output suitable for merging.
   */
-  virtual void add_info_string(String *str) {};
+  virtual void add_info_string(String *str) {}
   /*
     Return 1 if any index used by this quick select
     uses field which is marked in passed bitmap.
@@ -393,8 +400,17 @@ protected:
   friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx,
                                               SEL_ARG *key_tree,
                                               MEM_ROOT *alloc);
+  friend 
+  int read_keys_and_merge_scans(THD *thd, TABLE *head,
+                                List<QUICK_RANGE_SELECT> quick_selects,
+                                QUICK_RANGE_SELECT *pk_quick_select,
+                                READ_RECORD *read_record,
+                                bool intersection,
+                                Unique **unique_ptr);
+
   friend class QUICK_SELECT_DESC;
   friend class QUICK_INDEX_MERGE_SELECT;
+  friend class QUICK_INDEX_INTERSECT_SELECT;
   friend class QUICK_ROR_INTERSECT_SELECT;
   friend class QUICK_GROUP_MIN_MAX_SELECT;
 
@@ -545,6 +561,45 @@ public:
   READ_RECORD read_record;
 };
 
+class QUICK_INDEX_INTERSECT_SELECT : public QUICK_SELECT_I
+{
+  Unique *unique;
+public:
+  QUICK_INDEX_INTERSECT_SELECT(THD *thd, TABLE *table);
+  ~QUICK_INDEX_INTERSECT_SELECT();
+
+  int  init();
+  int  reset(void);
+  int  get_next();
+  bool reverse_sorted() { return false; }
+  bool unique_key_range() { return false; }
+  int get_type() { return QS_TYPE_INDEX_INTERSECT; }
+  void add_keys_and_lengths(String *key_names, String *used_lengths);
+  void add_info_string(String *str);
+  bool is_keys_used(const MY_BITMAP *fields);
+#ifndef DBUG_OFF
+  void dbug_dump(int indent, bool verbose);
+#endif
+
+  bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
+
+  /* range quick selects this index_merge read consists of */
+  List<QUICK_RANGE_SELECT> quick_selects;
+
+  /* quick select that uses clustered primary key (NULL if none) */
+  QUICK_RANGE_SELECT* pk_quick_select;
+
+  /* true if this select is currently doing a clustered PK scan */
+  bool  doing_pk_scan;
+
+  MEM_ROOT alloc;
+  THD *thd;
+  int read_keys_and_merge();
+
+  /* used to get rows collected in Unique */
+  READ_RECORD read_record;
+};
+
 
 /*
   Rowid-Ordered Retrieval (ROR) index intersection quick select.
diff --git a/sql/sql_class.h b/sql/sql_class.h
index db0842e7547..6d51e972c85 100644
--- a/sql/sql_class.h
+++ b/sql/sql_class.h
@@ -2977,6 +2977,7 @@ class user_var_entry
   DTCollation collation;
 };
 
+
 /*
    Unique -- class for unique (removing of duplicates).
    Puts all values to the TREE. If the tree becomes too big,
@@ -2993,27 +2994,42 @@ class Unique :public Sql_alloc
   IO_CACHE file;
   TREE tree;
   uchar *record_pointers;
+  ulong filtered_out_elems;
   bool flush();
   uint size;
+  uint full_size;
+  uint min_dupl_count;
 
 public:
   ulong elements;
   Unique(qsort_cmp2 comp_func, void *comp_func_fixed_arg,
-	 uint size_arg, ulonglong max_in_memory_size_arg);
+	 uint size_arg, ulonglong max_in_memory_size_arg,
+         uint min_dupl_count_arg= 0);
   ~Unique();
   ulong elements_in_tree() { return tree.elements_in_tree; }
   inline bool unique_add(void *ptr)
   {
     DBUG_ENTER("unique_add");
     DBUG_PRINT("info", ("tree %u - %lu", tree.elements_in_tree, max_elements));
-    if (tree.elements_in_tree > max_elements && flush())
+    if (!(tree.flag & TREE_ONLY_DUPS) && 
+        tree.elements_in_tree >= max_elements && flush())
       DBUG_RETURN(1);
     DBUG_RETURN(!tree_insert(&tree, ptr, 0, tree.custom_arg));
   }
 
+  bool is_in_memory() { return (my_b_tell(&file) == 0); }
+  void close_for_expansion() { tree.flag= TREE_ONLY_DUPS; }
+
   bool get(TABLE *table);
+  
+  inline static double get_search_cost(uint tree_elems, uint compare_factor)
+  {
+    return log((double) tree_elems) / (compare_factor * M_LN2);
+  }  
+
   static double get_use_cost(uint *buffer, uint nkeys, uint key_size,
-                             ulonglong max_in_memory_size);
+                             ulonglong max_in_memory_size, uint compare_factor,
+                             bool intersect_fl, bool *in_memory);
   inline static int get_cost_calc_buff_size(ulong nkeys, uint key_size,
                                             ulonglong max_in_memory_size)
   {
@@ -3030,6 +3046,11 @@ public:
 
   friend int unique_write_to_file(uchar* key, element_count count, Unique *unique);
   friend int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique);
+
+  friend int unique_write_to_file_with_count(uchar* key, element_count count,
+                                             Unique *unique);
+  friend int unique_intersect_write_to_ptrs(uchar* key, element_count count, 
+				            Unique *unique);
 };
 
 
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 60bfa0dfcd6..288369eedba 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -2688,6 +2688,7 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds,
       goto error;
     }
     table->quick_keys.clear_all();
+    table->intersect_keys.clear_all();
     table->reginfo.join_tab=s;
     table->reginfo.not_exists_optimize=0;
     bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->s->keys);
@@ -6373,8 +6374,10 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
       used_tables|=current_map;
 
       if (tab->type == JT_REF && tab->quick &&
-	  (uint) tab->ref.key == tab->quick->index &&
-	  tab->ref.key_length < tab->quick->max_used_key_length)
+	  (((uint) tab->ref.key == tab->quick->index &&
+	    tab->ref.key_length < tab->quick->max_used_key_length) ||
+	   (!tab->table->intersect_keys.is_clear_all() &&
+	    tab->table->intersect_keys.is_set(tab->ref.key))))
       {
 	/* Range uses longer key;  Use this instead of ref on key */
 	tab->type=JT_ALL;
@@ -10186,6 +10189,7 @@ create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
   table->quick_keys.init();
   table->covering_keys.init();
   table->merge_keys.init();
+  table->intersect_keys.init();
   table->keys_in_use_for_query.init();
 
   table->s= share;
@@ -13678,7 +13682,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
       by clustered PK values.
     */
   
-    if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE || 
+    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_ROR_UNION || 
         quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)
       DBUG_RETURN(0);
@@ -14084,6 +14089,7 @@ check_reverse_order:
         QUICK_SELECT_DESC *tmp;
         int quick_type= select->quick->get_type();
         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_ROR_INTERSECT ||
             quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
             quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
@@ -14256,6 +14262,7 @@ create_sort_index(THD *thd, JOIN *join, ORDER *order,
     select->cleanup();				// filesort did select
     tab->select= 0;
     table->quick_keys.clear_all();  // as far as we cleanup select->quick
+    table->intersect_keys.clear_all();
     table->sort.io_cache= tablesort_result_cache;
   }
   tab->select_cond=0;
@@ -16880,6 +16887,7 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
         quick_type= tab->select->quick->get_type();
         if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
             (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
+            (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
             (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
           tab->type = JT_INDEX_MERGE;
         else
@@ -17092,6 +17100,7 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
       {
         if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || 
             quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
+            quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT ||
             quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
         {
           extra.append(STRING_WITH_LEN("; Using "));
diff --git a/sql/sql_sort.h b/sql/sql_sort.h
index f54b085eeda..fc4117e2767 100644
--- a/sql/sql_sort.h
+++ b/sql/sql_sort.h
@@ -57,6 +57,7 @@ typedef struct st_sort_param {
   uint addon_length;        /* Length of added packed fields */
   uint res_length;          /* Length of records in final sorted file/buffer */
   uint keys;				/* Max keys / buffer */
+  element_count min_dupl_count;
   ha_rows max_rows,examined_rows;
   TABLE *sort_form;			/* For quicker make_sortkey */
   SORT_FIELD *local_sortorder;
@@ -80,4 +81,9 @@ int merge_buffers(SORTPARAM *param,IO_CACHE *from_file,
 		  IO_CACHE *to_file, uchar *sort_buffer,
 		  BUFFPEK *lastbuff,BUFFPEK *Fb,
 		  BUFFPEK *Tb,int flag);
+int merge_index(SORTPARAM *param, uchar *sort_buffer,
+		BUFFPEK *buffpek, uint maxbuffer,
+		IO_CACHE *tempfile, IO_CACHE *outfile);
+
 void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint key_length);
+
diff --git a/sql/table.h b/sql/table.h
index 828d01f3783..25e90e33b5e 100644
--- a/sql/table.h
+++ b/sql/table.h
@@ -683,7 +683,7 @@ struct st_table {
     needed by the query without reading the row.
   */
   key_map covering_keys;
-  key_map quick_keys, merge_keys;
+  key_map quick_keys, merge_keys,intersect_keys;
   /*
     A set of keys that can be used in the query that references this
     table.
diff --git a/sql/uniques.cc b/sql/uniques.cc
index 3d1ea9243b9..141504df610 100644
--- a/sql/uniques.cc
+++ b/sql/uniques.cc
@@ -33,7 +33,6 @@
 #include "mysql_priv.h"
 #include "sql_sort.h"
 
-
 int unique_write_to_file(uchar* key, element_count count, Unique *unique)
 {
   /*
@@ -45,6 +44,12 @@ int unique_write_to_file(uchar* key, element_count count, Unique *unique)
   return my_b_write(&unique->file, key, unique->size) ? 1 : 0;
 }
 
+int unique_write_to_file_with_count(uchar* key, element_count count, Unique *unique)
+{
+  return my_b_write(&unique->file, key, unique->size) ||
+         my_b_write(&unique->file, &count, sizeof(element_count)) ? 1 : 0;
+}
+
 int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique)
 {
   memcpy(unique->record_pointers, key, unique->size);
@@ -52,10 +57,28 @@ int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique)
   return 0;
 }
 
+int unique_intersect_write_to_ptrs(uchar* key, element_count count, Unique *unique)
+{
+  if (count >= unique->min_dupl_count)
+  {
+    memcpy(unique->record_pointers, key, unique->size);
+    unique->record_pointers+=unique->size;
+  }
+  else
+    unique->filtered_out_elems++;
+  return 0;
+}
+
+
 Unique::Unique(qsort_cmp2 comp_func, void * comp_func_fixed_arg,
-	       uint size_arg, ulonglong max_in_memory_size_arg)
+	       uint size_arg, ulonglong max_in_memory_size_arg,
+               uint min_dupl_count_arg)
   :max_in_memory_size(max_in_memory_size_arg), size(size_arg), elements(0)
 {
+  min_dupl_count= min_dupl_count_arg;
+  full_size= size;
+  if (min_dupl_count_arg)
+    full_size+= sizeof(element_count);
   my_b_clear(&file);
   init_tree(&tree, (ulong) (max_in_memory_size / 16), 0, size, comp_func, 0,
             NULL, comp_func_fixed_arg);
@@ -123,7 +146,8 @@ inline double log2_n_fact(double x)
 */
 
 static double get_merge_buffers_cost(uint *buff_elems, uint elem_size,
-                                     uint *first, uint *last)
+                                     uint *first, uint *last,
+                                     uint compare_factor)
 {
   uint total_buf_elems= 0;
   for (uint *pbuf= first; pbuf <= last; pbuf++)
@@ -134,7 +158,7 @@ static double get_merge_buffers_cost(uint *buff_elems, uint elem_size,
 
   /* Using log2(n)=log(n)/log(2) formula */
   return 2*((double)total_buf_elems*elem_size) / IO_SIZE +
-     total_buf_elems*log((double) n_buffers) / (TIME_FOR_COMPARE_ROWID * M_LN2);
+     total_buf_elems*log((double) n_buffers) / (compare_factor * M_LN2);
 }
 
 
@@ -167,7 +191,8 @@ static double get_merge_buffers_cost(uint *buff_elems, uint elem_size,
 
 static double get_merge_many_buffs_cost(uint *buffer,
                                         uint maxbuffer, uint max_n_elems,
-                                        uint last_n_elems, int elem_size)
+                                        uint last_n_elems, int elem_size,
+                                        uint compare_factor)
 {
   register int i;
   double total_cost= 0.0;
@@ -194,19 +219,22 @@ static double get_merge_many_buffs_cost(uint *buffer,
       {
         total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
                                            buff_elems + i,
-                                           buff_elems + i + MERGEBUFF-1);
+                                           buff_elems + i + MERGEBUFF-1,
+                                           compare_factor);
 	lastbuff++;
       }
       total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
                                          buff_elems + i,
-                                         buff_elems + maxbuffer);
+                                         buff_elems + maxbuffer,
+                                         compare_factor);
       maxbuffer= lastbuff;
     }
   }
 
   /* Simulate final merge_buff call. */
   total_cost += get_merge_buffers_cost(buff_elems, elem_size,
-                                       buff_elems, buff_elems + maxbuffer);
+                                       buff_elems, buff_elems + maxbuffer,
+                                       compare_factor);
   return total_cost;
 }
 
@@ -221,7 +249,11 @@ static double get_merge_many_buffs_cost(uint *buffer,
                 to get # bytes needed.
       nkeys     #of elements in Unique
       key_size  size of each elements in bytes
-      max_in_memory_size amount of memory Unique will be allowed to use
+      max_in_memory_size   amount of memory Unique will be allowed to use
+      compare_factor   used to calculate cost of one comparison
+      write_fl  if the result must be saved written to disk
+      in_memory_elems  OUT estimate of the number of elements in memory
+                           if disk is not used  
 
   RETURN
     Cost in disk seeks.
@@ -259,7 +291,9 @@ static double get_merge_many_buffs_cost(uint *buffer,
 */
 
 double Unique::get_use_cost(uint *buffer, uint nkeys, uint key_size,
-                            ulonglong max_in_memory_size)
+                            ulonglong max_in_memory_size,
+                            uint compare_factor,
+                            bool intersect_fl, bool *in_memory)
 {
   ulong max_elements_in_tree;
   ulong last_tree_elems;
@@ -276,12 +310,15 @@ double Unique::get_use_cost(uint *buffer, uint nkeys, uint key_size,
   result= 2*log2_n_fact(last_tree_elems + 1.0);
   if (n_full_trees)
     result+= n_full_trees * log2_n_fact(max_elements_in_tree + 1.0);
-  result /= TIME_FOR_COMPARE_ROWID;
+  result /= compare_factor;
 
   DBUG_PRINT("info",("unique trees sizes: %u=%u*%lu + %lu", nkeys,
                      n_full_trees, n_full_trees?max_elements_in_tree:0,
                      last_tree_elems));
 
+  if (in_memory)
+    *in_memory= !n_full_trees;
+
   if (!n_full_trees)
     return result;
 
@@ -295,12 +332,12 @@ double Unique::get_use_cost(uint *buffer, uint nkeys, uint key_size,
   result += DISK_SEEK_BASE_COST * ceil(((double) key_size)*last_tree_elems / IO_SIZE);
 
   /* Cost of merge */
+  if (intersect_fl)
+    key_size+= sizeof(element_count);
   double merge_cost= get_merge_many_buffs_cost(buffer, n_full_trees,
                                                max_elements_in_tree,
-                                               last_tree_elems, key_size);
-  if (merge_cost < 0.0)
-    return merge_cost;
-
+                                               last_tree_elems, key_size,
+                                               compare_factor);
   result += merge_cost;
   /*
     Add cost of reading the resulting sequence, assuming there were no
@@ -327,7 +364,10 @@ bool Unique::flush()
   file_ptr.count=tree.elements_in_tree;
   file_ptr.file_pos=my_b_tell(&file);
 
-  if (tree_walk(&tree, (tree_walk_action) unique_write_to_file,
+  tree_walk_action action= min_dupl_count ?
+		           (tree_walk_action) unique_write_to_file_with_count :
+		           (tree_walk_action) unique_write_to_file;
+  if (tree_walk(&tree, action,
 		(void*) this, left_root_right) ||
       insert_dynamic(&file_ptrs, (uchar*) &file_ptr))
     return 1;
@@ -357,6 +397,7 @@ Unique::reset()
     reinit_io_cache(&file, WRITE_CACHE, 0L, 0, 1);
   }
   elements= 0;
+  tree.flag= 0;
 }
 
 /*
@@ -576,15 +617,19 @@ bool Unique::get(TABLE *table)
 {
   SORTPARAM sort_param;
   table->sort.found_records=elements+tree.elements_in_tree;
-
   if (my_b_tell(&file) == 0)
   {
     /* Whole tree is in memory;  Don't use disk if you don't need to */
     if ((record_pointers=table->sort.record_pointers= (uchar*)
 	 my_malloc(size * tree.elements_in_tree, MYF(0))))
     {
-      (void) tree_walk(&tree, (tree_walk_action) unique_write_to_ptrs,
+      tree_walk_action action= min_dupl_count ?
+		         (tree_walk_action) unique_intersect_write_to_ptrs :
+		         (tree_walk_action) unique_write_to_ptrs;
+      filtered_out_elems= 0;
+      (void) tree_walk(&tree, action,
 		       this, left_root_right);
+      table->sort.found_records-= filtered_out_elems;
       return 0;
     }
   }
@@ -614,7 +659,9 @@ bool Unique::get(TABLE *table)
   sort_param.max_rows= elements;
   sort_param.sort_form=table;
   sort_param.rec_length= sort_param.sort_length= sort_param.ref_length=
-    size;
+   full_size;
+  sort_param.min_dupl_count= min_dupl_count;
+  sort_param.res_length= 0;
   sort_param.keys= (uint) (max_in_memory_size / sort_param.sort_length);
   sort_param.not_killable=1;
 
@@ -635,8 +682,9 @@ bool Unique::get(TABLE *table)
   if (flush_io_cache(&file) ||
       reinit_io_cache(&file,READ_CACHE,0L,0,0))
     goto err;
-  if (merge_buffers(&sort_param, &file, outfile, sort_buffer, file_ptr,
-		    file_ptr, file_ptr+maxbuffer,0))
+  sort_param.res_length= sort_param.rec_length-
+                         (min_dupl_count ? sizeof(min_dupl_count) : 0);
+  if (merge_index(&sort_param, sort_buffer, file_ptr, maxbuffer, &file, outfile))
     goto err;
   error=0;
 err:
@@ -651,3 +699,5 @@ err:
   outfile->end_of_file=save_pos;
   return error;
 }
+
+
diff --git a/sql/unireg.h b/sql/unireg.h
index 88a5ca5c12f..b3bf44173e7 100644
--- a/sql/unireg.h
+++ b/sql/unireg.h
@@ -89,7 +89,7 @@
 #define MAX_SELECT_NESTING (sizeof(nesting_map)*8-1)
 
 #define MAX_SORT_MEMORY (2048*1024-MALLOC_OVERHEAD)
-#define MIN_SORT_MEMORY (32*1024-MALLOC_OVERHEAD)
+#define MIN_SORT_MEMORY (1024-MALLOC_OVERHEAD)
 
 /* Memory allocated when parsing a statement / saving a statement */
 #define MEM_ROOT_BLOCK_SIZE       8192