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

8 files changed, 1145 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;
diff --git a/mysql-test/t/index_merge_ror.test b/mysql-test/t/index_merge_ror.test
new file mode 100644
index 00000000000..95b6204f424
--- /dev/null
+++ b/mysql-test/t/index_merge_ror.test
@@ -0,0 +1,215 @@
+#
+#  ROR-index_merge tests. 
+#
+--disable_warnings
+drop table if exists  t1,t0;
+--enable_warnings
+--disable_query_log
+create table t1
+(
+  /* Field names reflect value(rowid) distribution, st=STairs, swt= SaWTooth */
+  st_a int not null,
+  swt1a int not null,
+  swt2a int not null,
+
+  st_b int not null,
+  swt1b int not null,
+  swt2b int not null,
+
+  /* fields/keys for row retrieval tests */
+  key1 int,
+  key2 int,
+  key3 int,
+  key4 int,
+
+  /* make rows much bigger then keys */
+  filler1 char (200),
+  filler2 char (200),
+  filler3 char (200),
+  filler4 char (200),
+  filler5 char (200),
+  filler6 char (200),
+  
+  /* order of keys is important */
+  key sta_swt12a(st_a,swt1a,swt2a),
+  key sta_swt1a(st_a,swt1a),
+  key sta_swt2a(st_a,swt2a),
+  key sta_swt21a(st_a,swt2a,swt1a),
+
+  key st_a(st_a),
+  key stb_swt1a_2b(st_b,swt1b,swt2a),
+  key stb_swt1b(st_b,swt1b),
+  key st_b(st_b),
+
+  key(key1),
+  key(key2),
+  key(key3),
+  key(key4)
+) ;
+
+# Fill table 
+create table t0 as select * from t1;
+let $cnt=1000;
+while ($cnt)
+{
+  eval insert into t0 values (1, 2, 3, 1, 2, 3, 0, 0, 0, 0, 'data1', 'data2', 'data3', 'data4', 'data5', 'data6');
+  dec $cnt;
+}
+
+alter table t1 disable keys;
+let $1=4;
+while ($1)
+{
+  let $2=4;
+  while ($2) 
+  {
+    let $3=4;
+    while ($3)
+    {
+      eval insert into t1 select $1, $2, $3, $1 ,$2, $3, key1, key2, key3, key4, filler1, filler2, filler3, filler4, filler5, filler6 from t0;
+      dec $3;
+    }
+    dec $2;
+  }
+ dec $1;
+}
+
+# Row retrieval tests
+# -1 is used for values 'out of any range we are using'
+# insert enough rows for index intersection to be used for (key1,key2)
+insert into t1 (key1, key2, key3, key4, filler1) values (100, 100, 100, 100,'key1-key2-key3-key4');
+let $cnt=400;
+while ($cnt)
+{
+  eval insert into t1 (key1, key2, key3, key4, filler1) values (100, -1, 100, -1,'key1-key3');
+  dec $cnt;
+}
+let $cnt=400;
+while ($cnt)
+{
+  eval insert into t1 (key1, key2, key3, key4, filler1) values (-1, 100, -1, 100,'key2-key4');
+  dec $cnt;
+}
+alter table t1 enable keys;
+--enable_query_log
+select count(*) from t1;
+
+# One row results tests for cases where a single row matches all conditions 
+explain select key1,key2 from t1 where key1=100 and key2=100;
+select key1,key2 from t1 where key1=100 and key2=100;
+
+explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+
+# Several-rows results 
+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');
+
+#  ROR-intersection, not covering
+explain select key1,key2,filler1 from t1 where key1=100 and key2=100;
+select key1,key2,filler1 from t1 where key1=100 and key2=100;
+
+#  ROR-intersection, covering
+explain select key1,key2 from t1 where key1=100 and key2=100;
+select key1,key2 from t1 where key1=100 and key2=100;
+
+#  ROR-union of ROR-intersections
+explain select key1,key2,key3,key4 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+select key1,key2,key3,key4 from t1 where key1=100 and key2=100 or 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;
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+
+#  3-way ROR-intersection
+explain select key1,key2,key3 from t1 where key1=100 and key2=100 and key3=100;
+select key1,key2,key3 from t1 where key1=100 and key2=100 and key3=100;
+
+#  ROR-union(ROR-intersection, ROR-range)
+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;
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=101;
+
+# Run some ROR updates/deletes
+select key1,key2, filler1 from t1 where key1=100 and key2=100;
+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;
+
+# ROR-union(ROR-intersection) with one of ROR-intersection giving empty
+# results
+explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+
+delete from t1 where key3=100 and key4=100;
+
+# ROR-union with all ROR-intersections giving empty results
+explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
+
+# ROR-intersection with empty result
+explain select key1,key2 from t1 where key1=100 and key2=100;
+select key1,key2 from t1 where key1=100 and key2=100;
+
+# ROR-union tests with various cases.
+#  All scans returning duplicate rows: 
+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;
+select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+
+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;
+select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+
+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;
+select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
+
+##
+## Optimizer tests 
+##
+
+# Check that the shortest key is used for ROR-intersection, covering and non-covering.
+explain select * from t1 where st_a=1 and st_b=1;
+explain select st_a,st_b from t1 where st_a=1 and st_b=1;
+
+# Check if "ingore index" syntax works
+explain select st_a from t1 ignore index (st_a) where st_a=1 and st_b=1;
+
+# Do many tests 
+# Check that keys that don't improve selectivity are skipped.
+# 
+
+explain select * from t1 where st_a=1 and swt1a=1 and swt2a=1;
+
+explain select * from t1 where st_b=1 and swt1b=1 and swt2b=1;
+
+explain select * from t1 where st_a=1 and swt1a=1 and swt2a=1 and st_b=1 and swt1b=1 and swt2b=1;
+
+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;
+
+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;
+
+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;
+
+explain select * from t1 
+  where st_a=1 and swt1a=1 and swt2a=1 and st_b=1 and swt1b=1;
+
+explain select * from t1 
+  where st_a=1 and swt1a=1 and st_b=1 and swt1b=1 and swt1b=1;
+
+explain select st_a from t1 
+  where st_a=1 and swt1a=1 and st_b=1 and swt1b=1 and swt1b=1;
+
+explain select st_a from t1 
+  where st_a=1 and swt1a=1 and st_b=1 and swt1b=1 and swt1b=1;
+
+drop table t0,t1;
+
diff --git a/mysql-test/t/index_merge_ror_cpk.test b/mysql-test/t/index_merge_ror_cpk.test
new file mode 100644
index 00000000000..52e946c9be6
--- /dev/null
+++ b/mysql-test/t/index_merge_ror_cpk.test
@@ -0,0 +1,81 @@
+#
+# Clustered PK ROR-index_merge tests
+#
+-- source include/have_innodb.inc
+
+--disable_warnings
+drop table if exists  t1;
+--enable_warnings
+
+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;
+
+--disable_query_log
+set autocommit=0;
+let $1=10000;
+while ($1)
+{
+  eval insert into t1 values ($1 div 10,$1 mod 100,   $1/100,$1/100,   $1/100,$1/100,$1/100,$1/100,$1/100, $1 mod 100, $1/1000,'filler-data-$1','filler2');
+  dec $1;
+}
+set autocommit=1;
+--enable_query_log
+
+# Verify that range scan on CPK is ROR 
+# (use index_intersection because it is impossible to check that for index union) 
+explain select * from t1 where pk1 = 1 and pk2 < 80  and key1=0;
+# CPK scan + 1 ROR range scan is a special case
+select * from t1 where pk1 = 1 and pk2 < 80  and key1=0;
+
+# Verify that CPK fields are considered to be covered by index scans 
+explain select pk1,pk2 from t1 where key1 = 10 and key2=10 and 2*pk1+1 < 2*96+1;
+select pk1,pk2 from t1 where key1 = 10 and key2=10 and 2*pk1+1 < 2*96+1;
+
+# Verify that CPK is always used for index intersection scans
+# (this is because it is used as a filter, not for retrieval)
+explain select * from t1 where badkey=1 and key1=10;
+explain select * from t1 where pk1 < 7500 and key1 = 10;
+  
+# Verify that keys with 'tails' of PK members are ok.
+explain select * from t1 where pktail1ok=1 and key1=10;
+explain select * from t1 where pktail2ok=1 and key1=10;
+
+explain select * from t1 where pktail3bad=1 and key1=10;
+explain select * from t1 where pktail4bad=1 and key1=10;
+explain select * from t1 where pktail5bad=1 and key1=10;
+
+# Test for problem with innodb key values prefetch buffer: 
+explain select pk1,pk2,key1,key2 from t1 where key1 = 10 and key2=10 limit 10;
+select pk1,pk2,key1,key2 from t1 where key1 = 10 and key2=10 limit 10;
+
+drop table t1;
+
diff --git a/mysql-test/t/rowid_order_bdb.test b/mysql-test/t/rowid_order_bdb.test
new file mode 100644
index 00000000000..ef133054c35
--- /dev/null
+++ b/mysql-test/t/rowid_order_bdb.test
@@ -0,0 +1,108 @@
+#
+# Test for rowid ordering (and comparison) functions.
+# do index_merge select for tables with PK of various types. 
+#
+--disable_warnings
+drop table if exists t1, t2, t3,t4;
+--enable_warnings
+
+-- source include/have_bdb.inc
+
+# Signed number as rowid 
+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;
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+drop table t1;
+
+# Unsigned numbers as rowids 
+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;
+drop table t1;
+
+# Case-insensitive char(N)
+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;
+drop table t1;
+
+# Multi-part PK
+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;
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+
+# Hidden PK
+alter table t1 drop primary key;
+select * from t1;
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+drop table t1;
+
+# Variable-length PK
+# this is also test for Bug#2688
+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;
+
+drop table t1;
+
diff --git a/mysql-test/t/rowid_order_innodb.test b/mysql-test/t/rowid_order_innodb.test
new file mode 100644
index 00000000000..fb4959d78e6
--- /dev/null
+++ b/mysql-test/t/rowid_order_innodb.test
@@ -0,0 +1,108 @@
+#
+# Test for rowid ordering (and comparison) functions.
+# do index_merge select for tables with PK of various types. 
+#
+--disable_warnings
+drop table if exists t1, t2, t3,t4;
+--enable_warnings
+
+-- source include/have_innodb.inc
+
+# Signed number as rowid 
+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;
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+drop table t1;
+
+# Unsigned numbers as rowids 
+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;
+drop table t1;
+
+# Case-insensitive char(N)
+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;
+drop table t1;
+
+# Multi-part PK
+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;
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+
+# Hidden PK
+alter table t1 drop primary key;
+select * from t1;
+select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
+drop table t1;
+
+# Variable-length PK
+# this is also test for Bug#2688
+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;
+
+drop table t1;
+