This is first cset for WL#1394 "Optimize index merge when all involved index ranges include only values with equal keys"

The main idea is to exploit the fact that key scans for "key=const" return ordered sequences of rowids.


include/my_base.h:
  Added HA_EXTRA_KEYREAD_PRESERVE_FIELDS flag
include/my_bitmap.h:
  Added a couple of utility functions
include/my_sys.h:
  Added my_conunt_bits_ushort function
innobase/include/row0mysql.h:
  Added support for HA_EXTRA_KEYREAD_PRESERVE_FIELDS
innobase/row/row0sel.c:
  Added support for HA_EXTRA_KEYREAD_PRESERVE_FIELDS
mysys/my_bit.c:
  Added my_count_bits_ushort function
mysys/my_bitmap.c:
  Added a couple of utility functions
sql/ha_berkeley.cc:
  Added cmp_ref rowid comparison function.
sql/ha_berkeley.h:
  Added cmp_ref rowid comparison function.
sql/ha_heap.h:
  Added cmp_ref rowid comparison function.
sql/ha_innodb.cc:
  Added cmp_ref rowid comparison function and support from HA_EXTRA_KEYREAD_PRESERVE_FIELDS
sql/ha_innodb.h:
  Added cmp_ref rowid comparison function.
sql/handler.h:
  Added cmp_ref rowid comparison function.
sql/opt_range.cc:
  Added QUICK_ROR_{INTERSECT,UNION}_SELECT classes and related optimizer code
sql/opt_range.h:
  Added QUICK_ROR_{INTERSECT,UNION}_SELECT classes
sql/sql_delete.cc:
  Changed to use new ROWID comparison function
  also always call quick->reset() for quick selects
sql/sql_select.cc:
  Account for new quick select types
sql/sql_select.h:
  New, proper rowid ordering/comparison function to be used with Unique class etc.
sql/sql_test.cc:
  Account for new quick select types
sql/sql_update.cc:
  Account for new quick select types

4 files changed, 633 insertions, 0 deletions

diff --git a/mysql-test/r/index_merge_ror.result b/mysql-test/r/index_merge_ror.result
new file mode 100644
index 00000000000..94d03e8bf03
--- /dev/null
+++ b/mysql-test/r/index_merge_ror.result
@@ -0,0 +1,168 @@
+drop table if exists  t1,t0;
+select count(*) from t1;
+count(*)
+64801
+explain select key1,key2 from t1 where key1=100 and key2=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2	key1,key2	5,5	NULL	3	Using where; Using index
+select key1,key2 from t1 where key1=100 and key2=100;
+key1	key2
+100	100
+explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	8	Using where
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+key1	key2	key3	key4	filler1
+100	100	100	100	key1-key2-key3-key4
+insert into t1 (key1, key2, key3, key4, filler1) values (100, 100, -1, -1, 'key1-key2');
+insert into t1 (key1, key2, key3, key4, filler1) values (-1, -1, 100, 100, 'key4-key3');
+explain select key1,key2,filler1 from t1 where key1=100 and key2=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2	key1,key2	5,5	NULL	3	Using where
+select key1,key2,filler1 from t1 where key1=100 and key2=100;
+key1	key2	filler1
+100	100	key1-key2-key3-key4
+100	100	key1-key2
+explain select key1,key2 from t1 where key1=100 and key2=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2	key1,key2	5,5	NULL	3	Using where; Using index
+select key1,key2 from t1 where key1=100 and key2=100;
+key1	key2
+100	100
+100	100
+explain select key1,key2,key3,key4 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	8	Using where
+select key1,key2,key3,key4 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+key1	key2	key3	key4
+100	100	100	100
+100	100	-1	-1
+-1	-1	100	100
+explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	8	Using where
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+key1	key2	key3	key4	filler1
+100	100	100	100	key1-key2-key3-key4
+100	100	-1	-1	key1-key2
+-1	-1	100	100	key4-key3
+explain select key1,key2,key3 from t1 where key1=100 and key2=100 and key3=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3	key1,key2,key3	5,5,5	NULL	1	Using where; Using index
+select key1,key2,key3 from t1 where key1=100 and key2=100 and key3=100;
+key1	key2	key3
+100	100	100
+insert into t1 (key1,key2,key3,key4,filler1) values (101,101,101,101, 'key1234-101');
+explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=101;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3	key1,key2,key3	5,5,5	NULL	5	Using where
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=101;
+key1	key2	key3	key4	filler1
+100	100	100	100	key1-key2-key3-key4
+100	100	-1	-1	key1-key2
+101	101	101	101	key1234-101
+select key1,key2, filler1 from t1 where key1=100 and key2=100;
+key1	key2	filler1
+100	100	key1-key2-key3-key4
+100	100	key1-key2
+update t1 set filler1='to be deleted' where key1=100 and key2=100;
+update t1 set key1=200,key2=200 where key1=100 and key2=100;
+delete from t1 where key1=200 and key2=200;
+select key1,key2,filler1 from t1 where key2=100 and key2=200;
+key1	key2	filler1
+explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	8	Using where
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+key1	key2	key3	key4	filler1
+-1	-1	100	100	key4-key3
+delete from t1 where key3=100 and key4=100;
+explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	8	Using where
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+key1	key2	key3	key4	filler1
+explain select key1,key2 from t1 where key1=100 and key2=100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2	key1,key2	5,5	NULL	3	Using where; Using index
+select key1,key2 from t1 where key1=100 and key2=100;
+key1	key2
+insert into t1 (key1, key2, key3, key4, filler1) values (100, 100, 200, 200,'key1-key2-key3-key4-1');
+insert into t1 (key1, key2, key3, key4, filler1) values (100, 100, 200, 200,'key1-key2-key3-key4-2');
+insert into t1 (key1, key2, key3, key4, filler1) values (100, 100, 200, 200,'key1-key2-key3-key4-3');
+explain select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	16	Using where
+select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+key1	key2	key3	key4	filler1
+100	100	200	200	key1-key2-key3-key4-3
+100	100	200	200	key1-key2-key3-key4-2
+100	100	200	200	key1-key2-key3-key4-1
+insert into t1 (key1, key2, key3, key4, filler1) values (-1, -1, -1, 200,'key4');
+explain select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	18	Using where
+select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+key1	key2	key3	key4	filler1
+100	100	200	200	key1-key2-key3-key4-3
+100	100	200	200	key1-key2-key3-key4-2
+100	100	200	200	key1-key2-key3-key4-1
+-1	-1	-1	200	key4
+insert into t1 (key1, key2, key3, key4, filler1) values (-1, -1, 200, -1,'key3');
+explain select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	20	Using where
+select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+key1	key2	key3	key4	filler1
+100	100	200	200	key1-key2-key3-key4-3
+100	100	200	200	key1-key2-key3-key4-2
+100	100	200	200	key1-key2-key3-key4-1
+-1	-1	-1	200	key4
+-1	-1	200	-1	key3
+explain select * from t1 where st_a=1 and st_b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a,stb_swt1a_2b,stb_swt1b,st_b	st_a,st_b	4,4	NULL	2508	Using where
+explain select st_a,st_b from t1 where st_a=1 and st_b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a,stb_swt1a_2b,stb_swt1b,st_b	st_a,st_b	4,4	NULL	2508	Using where; Using index
+explain select st_a from t1 ignore index (st_a) where st_a=1 and st_b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,stb_swt1a_2b,stb_swt1b,st_b	st_b	4	const	14720	Using where
+explain select * from t1 where st_a=1 and swt1a=1 and swt2a=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a	sta_swt12a	12	const,const,const	958	Using where
+explain select * from t1 where st_b=1 and swt1b=1 and swt2b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	stb_swt1a_2b,stb_swt1b,st_b	stb_swt1b	8	const,const	3757	Using where
+explain select * from t1 where st_a=1 and swt1a=1 and swt2a=1 and st_b=1 and swt1b=1 and swt2b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a,stb_swt1a_2b,stb_swt1b,st_b	sta_swt12a,stb_swt1a_2b	12,12	NULL	42	Using where
+explain select * from t1 ignore index (sta_swt21a, stb_swt1a_2b) 
+where st_a=1 and swt1a=1 and swt2a=1 and st_b=1 and swt1b=1 and swt2b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,st_a,stb_swt1b,st_b	sta_swt12a,stb_swt1b	12,8	NULL	42	Using where
+explain select * from t1 ignore index (sta_swt21a, sta_swt12a, stb_swt1a_2b) 
+where st_a=1 and swt1a=1 and swt2a=1 and st_b=1 and swt1b=1 and swt2b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt1a,sta_swt2a,st_a,stb_swt1b,st_b	sta_swt1a,stb_swt1b	8,8	NULL	163	Using where
+explain select * from t1 ignore index (sta_swt21a, sta_swt12a, stb_swt1a_2b, stb_swt1b) 
+where st_a=1 and swt1a=1 and swt2a=1 and st_b=1 and swt1b=1 and swt2b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt1a,sta_swt2a,st_a,st_b	sta_swt1a,st_b	8,4	NULL	640	Using where
+explain select * from t1 
+where st_a=1 and swt1a=1 and swt2a=1 and st_b=1 and swt1b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a,stb_swt1a_2b,stb_swt1b,st_b	sta_swt12a,stb_swt1a_2b	12,12	NULL	42	Using where
+explain select * from t1 
+where st_a=1 and swt1a=1 and st_b=1 and swt1b=1 and swt1b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a,stb_swt1a_2b,stb_swt1b,st_b	sta_swt1a,stb_swt1b	8,8	NULL	163	Using where
+explain select st_a from t1 
+where st_a=1 and swt1a=1 and st_b=1 and swt1b=1 and swt1b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a,stb_swt1a_2b,stb_swt1b,st_b	sta_swt1a,stb_swt1b	8,8	NULL	163	Using where; Using index
+explain select st_a from t1 
+where st_a=1 and swt1a=1 and st_b=1 and swt1b=1 and swt1b=1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a,stb_swt1a_2b,stb_swt1b,st_b	sta_swt1a,stb_swt1b	8,8	NULL	163	Using where; Using index
+drop table t0,t1;
diff --git a/mysql-test/r/index_merge_ror_cpk.result b/mysql-test/r/index_merge_ror_cpk.result
new file mode 100644
index 00000000000..10b4b74d3cd
--- /dev/null
+++ b/mysql-test/r/index_merge_ror_cpk.result
@@ -0,0 +1,93 @@
+drop table if exists  t1;
+create table t1
+(
+pk1 int not null, 
+pk2 int not null,
+key1 int not null,
+key2 int not null,
+pktail1ok  int not null, 
+pktail2ok  int not null, 
+pktail3bad int not null,
+pktail4bad int not null,
+pktail5bad int not null,
+pk2copy int not null,
+badkey  int not null,
+filler1 char (200),
+filler2 char (200),
+key (key1),
+key (key2),
+/* keys with tails from CPK members */
+key (pktail1ok, pk1),
+key (pktail2ok, pk1, pk2),
+key (pktail3bad, pk2, pk1),
+key (pktail4bad, pk1, pk2copy),
+key (pktail5bad, pk1, pk2, pk2copy),
+primary key (pk1, pk2)
+) engine=innodb;
+explain select * from t1 where pk1 = 1 and pk2 < 80  and key1=0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	PRIMARY,key1	PRIMARY	4	const	1	Using where
+select * from t1 where pk1 = 1 and pk2 < 80  and key1=0;
+pk1	pk2	key1	key2	pktail1ok	pktail2ok	pktail3bad	pktail4bad	pktail5bad	pk2copy	badkey	filler1	filler2
+1	10	0	0	0	0	0	0	0	10	0	filler-data-10	filler2
+1	11	0	0	0	0	0	0	0	11	0	filler-data-11	filler2
+1	12	0	0	0	0	0	0	0	12	0	filler-data-12	filler2
+1	13	0	0	0	0	0	0	0	13	0	filler-data-13	filler2
+1	14	0	0	0	0	0	0	0	14	0	filler-data-14	filler2
+1	15	0	0	0	0	0	0	0	15	0	filler-data-15	filler2
+1	16	0	0	0	0	0	0	0	16	0	filler-data-16	filler2
+1	17	0	0	0	0	0	0	0	17	0	filler-data-17	filler2
+1	18	0	0	0	0	0	0	0	18	0	filler-data-18	filler2
+1	19	0	0	0	0	0	0	0	19	0	filler-data-19	filler2
+explain select pk1,pk2 from t1 where key1 = 10 and key2=10 and 2*pk1+1 < 2*96+1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2	intr(key1,key2)	4,4	NULL	1	Using where; Using index
+select pk1,pk2 from t1 where key1 = 10 and key2=10 and 2*pk1+1 < 2*96+1;
+pk1	pk2
+95	50
+95	51
+95	52
+95	53
+95	54
+95	55
+95	56
+95	57
+95	58
+95	59
+explain select * from t1 where badkey=1 and key1=10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	key1	key1	4	const	101	Using where
+explain select * from t1 where pk1 < 7500 and key1 = 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	PRIMARY,key1	intr(key1:PRIMARY)	4:4	NULL	38	Using where
+explain select * from t1 where pktail1ok=1 and key1=10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,pktail1ok	intr(key1,pktail1ok)	4,4	NULL	1	Using where
+explain select * from t1 where pktail2ok=1 and key1=10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,pktail2ok	intr(key1,pktail2ok)	4,4	NULL	1	Using where
+explain select * from t1 where pktail3bad=1 and key1=10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	key1,pktail3bad	pktail3bad	4	const	98	Using where
+explain select * from t1 where pktail4bad=1 and key1=10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	key1,pktail4bad	pktail4bad	4	const	99	Using where
+explain select * from t1 where pktail5bad=1 and key1=10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	key1,pktail5bad	pktail5bad	4	const	99	Using where
+explain select pk1,pk2,key1,key2 from t1 where key1 = 10 and key2=10 limit 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2	intr(key1,key2)	4,4	NULL	1	Using where; Using index
+select pk1,pk2,key1,key2 from t1 where key1 = 10 and key2=10 limit 10;
+pk1	pk2	key1	key2
+95	50	10	10
+95	51	10	10
+95	52	10	10
+95	53	10	10
+95	54	10	10
+95	55	10	10
+95	56	10	10
+95	57	10	10
+95	58	10	10
+95	59	10	10
+drop table t1;
diff --git a/mysql-test/r/rowid_order_bdb.result b/mysql-test/r/rowid_order_bdb.result
new file mode 100644
index 00000000000..8f385dfc75f
--- /dev/null
+++ b/mysql-test/r/rowid_order_bdb.result
@@ -0,0 +1,186 @@
+drop table if exists t1, t2, t3,t4;
+create table t1 ( 
+pk1 int not NULL,
+key1 int(11),
+key2 int(11),
+PRIMARY KEY  (pk1),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=bdb;
+insert into t1 values (-5, 1, 1),
+(-100, 1, 1),
+(3, 1, 1),
+(0, 1, 1),
+(10, 1, 1);
+explain select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2	key1,key2	5,5	NULL	5	Using where
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	key1	key2
+-100	1	1
+-5	1	1
+0	1	1
+3	1	1
+10	1	1
+drop table t1;
+create table t1 ( 
+pk1 int unsigned not NULL,
+key1 int(11),
+key2 int(11),
+PRIMARY KEY  (pk1),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=bdb;
+insert into t1 values (0, 1, 1),
+(0xFFFFFFFF, 1, 1),
+(0xFFFFFFFE, 1, 1),
+(1, 1, 1),
+(2, 1, 1);
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	key1	key2
+0	1	1
+1	1	1
+2	1	1
+4294967294	1	1
+4294967295	1	1
+drop table t1;
+create table t1 ( 
+pk1 char(4) not NULL,
+key1 int(11),
+key2 int(11),
+PRIMARY KEY  (pk1),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=bdb collate latin2_general_ci;
+insert into t1 values ('a1', 1, 1),
+('b2', 1, 1),
+('A3', 1, 1),
+('B4', 1, 1);
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	key1	key2
+a1	1	1
+A3	1	1
+b2	1	1
+B4	1	1
+drop table t1;
+create table t1 (
+pk1 int not NULL,
+pk2 char(4) not NULL collate latin1_german1_ci,
+pk3 char(4) not NULL collate latin1_bin,
+key1 int(11),
+key2 int(11),
+PRIMARY KEY  (pk1,pk2,pk3),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=bdb;
+insert into t1 values 
+(1, 'u', 'u',        1, 1),
+(1, 'u', char(0xEC), 1, 1),
+(1, 'u', 'x',        1, 1);
+insert ignore into t1 select pk1, char(0xEC), pk3, key1, key2  from t1;
+insert ignore into t1 select pk1, 'x', pk3, key1, key2  from t1 where pk2='u';
+insert ignore into t1 select 2, pk2, pk3, key1, key2  from t1;
+select * from t1;
+pk1	pk2	pk3	key1	key2
+1	ì	u	1	1
+1	ì	x	1	1
+1	ì	ì	1	1
+1	u	u	1	1
+1	u	x	1	1
+1	u	ì	1	1
+1	x	u	1	1
+1	x	x	1	1
+1	x	ì	1	1
+2	ì	u	1	1
+2	ì	x	1	1
+2	ì	ì	1	1
+2	u	u	1	1
+2	u	x	1	1
+2	u	ì	1	1
+2	x	u	1	1
+2	x	x	1	1
+2	x	ì	1	1
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	pk2	pk3	key1	key2
+1	ì	u	1	1
+1	ì	x	1	1
+1	ì	ì	1	1
+1	u	u	1	1
+1	u	x	1	1
+1	u	ì	1	1
+1	x	u	1	1
+1	x	x	1	1
+1	x	ì	1	1
+2	ì	u	1	1
+2	ì	x	1	1
+2	ì	ì	1	1
+2	u	u	1	1
+2	u	x	1	1
+2	u	ì	1	1
+2	x	u	1	1
+2	x	x	1	1
+2	x	ì	1	1
+alter table t1 drop primary key;
+select * from t1;
+pk1	pk2	pk3	key1	key2
+1	ì	u	1	1
+1	ì	x	1	1
+1	ì	ì	1	1
+1	u	u	1	1
+1	u	x	1	1
+1	u	ì	1	1
+1	x	u	1	1
+1	x	x	1	1
+1	x	ì	1	1
+2	ì	u	1	1
+2	ì	x	1	1
+2	ì	ì	1	1
+2	u	u	1	1
+2	u	x	1	1
+2	u	ì	1	1
+2	x	u	1	1
+2	x	x	1	1
+2	x	ì	1	1
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	pk2	pk3	key1	key2
+1	ì	u	1	1
+1	ì	x	1	1
+1	ì	ì	1	1
+1	u	u	1	1
+1	u	x	1	1
+1	u	ì	1	1
+1	x	u	1	1
+1	x	x	1	1
+1	x	ì	1	1
+2	ì	u	1	1
+2	ì	x	1	1
+2	ì	ì	1	1
+2	u	u	1	1
+2	u	x	1	1
+2	u	ì	1	1
+2	x	u	1	1
+2	x	x	1	1
+2	x	ì	1	1
+drop table t1;
+create table t1  (
+pk1 varchar(8) NOT NULL default '',
+pk2 varchar(4) NOT NULL default '',
+key1 int(11),
+key2 int(11),
+primary key(pk1, pk2),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=bdb;
+insert into t1 values ('','empt',2,2),
+('a','a--a',2,2),
+('bb','b--b',2,2),
+('ccc','c--c',2,2),
+('dddd','d--d',2,2);
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	pk2	key1	key2
+	empt	2	2
+a	a--a	2	2
+bb	b--b	2	2
+ccc	c--c	2	2
+dddd	d--d	2	2
+drop table t1;
diff --git a/mysql-test/r/rowid_order_innodb.result b/mysql-test/r/rowid_order_innodb.result
new file mode 100644
index 00000000000..b1de1b37e73
--- /dev/null
+++ b/mysql-test/r/rowid_order_innodb.result
@@ -0,0 +1,186 @@
+drop table if exists t1, t2, t3,t4;
+create table t1 ( 
+pk1 int not NULL,
+key1 int(11),
+key2 int(11),
+PRIMARY KEY  (pk1),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=innodb;
+insert into t1 values (-5, 1, 1),
+(-100, 1, 1),
+(3, 1, 1),
+(0, 1, 1),
+(10, 1, 1);
+explain select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index_merge	key1,key2	key1,key2	5,5	NULL	4	Using where
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	key1	key2
+-100	1	1
+-5	1	1
+0	1	1
+3	1	1
+10	1	1
+drop table t1;
+create table t1 ( 
+pk1 int unsigned not NULL,
+key1 int(11),
+key2 int(11),
+PRIMARY KEY  (pk1),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=innodb;
+insert into t1 values (0, 1, 1),
+(0xFFFFFFFF, 1, 1),
+(0xFFFFFFFE, 1, 1),
+(1, 1, 1),
+(2, 1, 1);
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	key1	key2
+0	1	1
+1	1	1
+2	1	1
+4294967294	1	1
+4294967295	1	1
+drop table t1;
+create table t1 ( 
+pk1 char(4) not NULL,
+key1 int(11),
+key2 int(11),
+PRIMARY KEY  (pk1),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=innodb collate latin2_general_ci;
+insert into t1 values ('a1', 1, 1),
+('b2', 1, 1),
+('A3', 1, 1),
+('B4', 1, 1);
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	key1	key2
+a1	1	1
+A3	1	1
+b2	1	1
+B4	1	1
+drop table t1;
+create table t1 (
+pk1 int not NULL,
+pk2 char(4) not NULL collate latin1_german1_ci,
+pk3 char(4) not NULL collate latin1_bin,
+key1 int(11),
+key2 int(11),
+PRIMARY KEY  (pk1,pk2,pk3),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=innodb;
+insert into t1 values 
+(1, 'u', 'u',        1, 1),
+(1, 'u', char(0xEC), 1, 1),
+(1, 'u', 'x',        1, 1);
+insert ignore into t1 select pk1, char(0xEC), pk3, key1, key2  from t1;
+insert ignore into t1 select pk1, 'x', pk3, key1, key2  from t1 where pk2='u';
+insert ignore into t1 select 2, pk2, pk3, key1, key2  from t1;
+select * from t1;
+pk1	pk2	pk3	key1	key2
+1	ì	u	1	1
+1	ì	x	1	1
+1	ì	ì	1	1
+1	u	u	1	1
+1	u	x	1	1
+1	u	ì	1	1
+1	x	u	1	1
+1	x	x	1	1
+1	x	ì	1	1
+2	ì	u	1	1
+2	ì	x	1	1
+2	ì	ì	1	1
+2	u	u	1	1
+2	u	x	1	1
+2	u	ì	1	1
+2	x	u	1	1
+2	x	x	1	1
+2	x	ì	1	1
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	pk2	pk3	key1	key2
+1	ì	u	1	1
+1	ì	x	1	1
+1	ì	ì	1	1
+1	u	u	1	1
+1	u	x	1	1
+1	u	ì	1	1
+1	x	u	1	1
+1	x	x	1	1
+1	x	ì	1	1
+2	ì	u	1	1
+2	ì	x	1	1
+2	ì	ì	1	1
+2	u	u	1	1
+2	u	x	1	1
+2	u	ì	1	1
+2	x	u	1	1
+2	x	x	1	1
+2	x	ì	1	1
+alter table t1 drop primary key;
+select * from t1;
+pk1	pk2	pk3	key1	key2
+1	ì	u	1	1
+1	ì	x	1	1
+1	ì	ì	1	1
+1	u	u	1	1
+1	u	x	1	1
+1	u	ì	1	1
+1	x	u	1	1
+1	x	x	1	1
+1	x	ì	1	1
+2	ì	u	1	1
+2	ì	x	1	1
+2	ì	ì	1	1
+2	u	u	1	1
+2	u	x	1	1
+2	u	ì	1	1
+2	x	u	1	1
+2	x	x	1	1
+2	x	ì	1	1
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	pk2	pk3	key1	key2
+1	ì	u	1	1
+1	ì	x	1	1
+1	ì	ì	1	1
+1	u	u	1	1
+1	u	x	1	1
+1	u	ì	1	1
+1	x	u	1	1
+1	x	x	1	1
+1	x	ì	1	1
+2	ì	u	1	1
+2	ì	x	1	1
+2	ì	ì	1	1
+2	u	u	1	1
+2	u	x	1	1
+2	u	ì	1	1
+2	x	u	1	1
+2	x	x	1	1
+2	x	ì	1	1
+drop table t1;
+create table t1  (
+pk1 varchar(8) NOT NULL default '',
+pk2 varchar(4) NOT NULL default '',
+key1 int(11),
+key2 int(11),
+primary key(pk1, pk2),
+KEY key1 (key1),
+KEY key2 (key2)
+) engine=innodb;
+insert into t1 values ('','empt',2,2),
+('a','a--a',2,2),
+('bb','b--b',2,2),
+('ccc','c--c',2,2),
+('dddd','d--d',2,2);
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+pk1	pk2	key1	key2
+	empt	2	2
+a	a--a	2	2
+bb	b--b	2	2
+ccc	c--c	2	2
+dddd	d--d	2	2
+drop table t1;