← Back to team overview

maria-developers team mailing list archive

DS-MRR improvements patch r3 ready for review

 

Hello Igor,

Please find attached the combined patch that addresses all of the review
feedback provided so far.
 
The tree is in launchpad and buildbot also:
https://code.launchpad.net/~maria-captains/maria/5.3-dsmrr-cpk
 
BR
 Sergey
-- 
Sergey Petrunia, Software Developer
Monty Program AB, http://askmonty.org
Blog: http://s.petrunia.net/blog
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/innodb_mrr_cpk.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/innodb_mrr_cpk.result
--- 5.3-noc/mysql-test/r/innodb_mrr_cpk.result	1970-01-01 03:00:00.000000000 +0300
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/innodb_mrr_cpk.result	2010-08-14 19:28:23.000000000 +0400
@@ -0,0 +1,148 @@
+drop table if exists t0,t1,t2,t3;
+set @save_join_cache_level=@@join_cache_level;
+set join_cache_level=6;
+set @save_storage_engine=@@storage_engine;
+set storage_engine=innodb;
+create table t0(a int);
+insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t1(a char(8), b char(8), filler char(100), primary key(a));
+show create table t1;
+Table	Create Table
+t1	CREATE TABLE `t1` (
+  `a` char(8) NOT NULL DEFAULT '',
+  `b` char(8) DEFAULT NULL,
+  `filler` char(100) DEFAULT NULL,
+  PRIMARY KEY (`a`)
+) ENGINE=InnoDB DEFAULT CHARSET=latin1
+insert into t1 select 
+concat('a-', 1000 + A.a + B.a*10 + C.a*100, '=A'),
+concat('b-', 1000 + A.a + B.a*10 + C.a*100, '=B'),
+'filler'
+from t0 A, t0 B, t0 C;
+create table t2 (a char(8));
+insert into t2 values ('a-1010=A'), ('a-1030=A'), ('a-1020=A');
+This should use join buffer:
+explain select * from t1, t2 where t1.a=t2.a;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	
+1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	8	test.t2.a	1	Using join buffer
+This output must be sorted by value of t1.a:
+select * from t1, t2 where t1.a=t2.a;
+a	b	filler	a
+a-1010=A	b-1010=B	filler	a-1010=A
+a-1020=A	b-1020=B	filler	a-1020=A
+a-1030=A	b-1030=B	filler	a-1030=A
+drop table t1, t2;
+create table t1(
+a char(8) character set utf8, b int, filler char(100), 
+primary key(a,b)
+);
+insert into t1 select 
+concat('a-', 1000 + A.a + B.a*10 + C.a*100, '=A'),
+1000 + A.a + B.a*10 + C.a*100,
+'filler'
+from t0 A, t0 B, t0 C;
+create table t2 (a char(8) character set utf8, b int);
+insert into t2 values ('a-1010=A', 1010), ('a-1030=A', 1030), ('a-1020=A', 1020);
+explain select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	
+1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	28	test.t2.a,test.t2.b	1	Using join buffer
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+a	b	filler	a	b
+a-1010=A	1010	filler	a-1010=A	1010
+a-1020=A	1020	filler	a-1020=A	1020
+a-1030=A	1030	filler	a-1030=A	1030
+insert into t2 values ('a-1030=A', 1030), ('a-1020=A', 1020);
+explain select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	5	
+1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	28	test.t2.a,test.t2.b	1	Using join buffer
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+a	b	filler	a	b
+a-1010=A	1010	filler	a-1010=A	1010
+a-1020=A	1020	filler	a-1020=A	1020
+a-1020=A	1020	filler	a-1020=A	1020
+a-1030=A	1030	filler	a-1030=A	1030
+a-1030=A	1030	filler	a-1030=A	1030
+drop table t1, t2;
+create table t1(
+a varchar(8) character set utf8, b int, filler char(100), 
+primary key(a,b)
+);
+insert into t1 select 
+concat('a-', 1000 + A.a + B.a*10 + C.a*100, '=A'),
+1000 + A.a + B.a*10 + C.a*100,
+'filler'
+from t0 A, t0 B, t0 C;
+create table t2 (a char(8) character set utf8, b int);
+insert into t2 values ('a-1010=A', 1010), ('a-1030=A', 1030), ('a-1020=A', 1020);
+explain select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	
+1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	30	test.t2.a,test.t2.b	1	Using index condition(BKA); Using join buffer
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+a	b	filler	a	b
+a-1010=A	1010	filler	a-1010=A	1010
+a-1020=A	1020	filler	a-1020=A	1020
+a-1030=A	1030	filler	a-1030=A	1030
+explain select * from t1, t2 where t1.a=t2.a;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	
+1	SIMPLE	t1	ref	PRIMARY	PRIMARY	26	test.t2.a	1	Using index condition(BKA); Using join buffer
+select * from t1, t2 where t1.a=t2.a;
+a	b	filler	a	b
+a-1010=A	1010	filler	a-1010=A	1010
+a-1020=A	1020	filler	a-1020=A	1020
+a-1030=A	1030	filler	a-1030=A	1030
+drop table t1, t2;
+create table t1 (a int, b int, c int, filler char(100), primary key(a,b,c));
+insert into t1 select A.a, B.a, C.a, 'filler' from t0 A, t0 B, t0 C;
+insert into t1 values (11, 11, 11,   'filler');
+insert into t1 values (11, 11, 12,   'filler');
+insert into t1 values (11, 11, 13,   'filler');
+insert into t1 values (11, 22, 1234, 'filler');
+insert into t1 values (11, 33, 124,  'filler');
+insert into t1 values (11, 33, 125,  'filler');
+create table t2 (a int, b int);
+insert into t2 values (11,33), (11,22), (11,11);
+explain select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	
+1	SIMPLE	t1	ref	PRIMARY	PRIMARY	8	test.t2.a,test.t2.b	1	Using join buffer
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+a	b	c	filler	a	b
+11	11	11	filler	11	11
+11	11	12	filler	11	11
+11	11	13	filler	11	11
+11	22	1234	filler	11	22
+11	33	124	filler	11	33
+11	33	125	filler	11	33
+set join_cache_level=0;
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+a	b	c	filler	a	b
+11	33	124	filler	11	33
+11	33	125	filler	11	33
+11	22	1234	filler	11	22
+11	11	11	filler	11	11
+11	11	12	filler	11	11
+11	11	13	filler	11	11
+set join_cache_level=6;
+explain select * from t1, t2 where t1.a=t2.a and t2.b + t1.b > 100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	
+1	SIMPLE	t1	ref	PRIMARY	PRIMARY	4	test.t2.a	1	Using index condition(BKA); Using join buffer
+select * from t1, t2 where t1.a=t2.a and t2.b + t1.b > 100;
+a	b	c	filler	a	b
+set optimizer_switch='index_condition_pushdown=off';
+explain select * from t1, t2 where t1.a=t2.a and t2.b + t1.b > 100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	
+1	SIMPLE	t1	ref	PRIMARY	PRIMARY	4	test.t2.a	1	Using where; Using join buffer
+select * from t1, t2 where t1.a=t2.a and t2.b + t1.b > 100;
+a	b	c	filler	a	b
+set optimizer_switch='index_condition_pushdown=on';
+drop table t1,t2;
+set @@join_cache_level= @save_join_cache_level;
+set storage_engine=@save_storage_engine;
+drop table t0;
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/innodb_mrr.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/innodb_mrr.result
--- 5.3-noc/mysql-test/r/innodb_mrr.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/innodb_mrr.result	2010-09-21 20:21:11.000000000 +0400
@@ -402,3 +402,33 @@
 id	parent_id	name
 60	40	F
 drop table t1;
+#
+# BUG#628785: multi_range_read.cc:430: int DsMrr_impl::dsmrr_init(): Assertion `do_sort_keys || do_rowid_fetch' failed 
+#
+set @save_join_cache_level= @@join_cache_level;
+set @save_optimizer_switch= @@optimizer_switch;
+SET SESSION join_cache_level=9;
+Warnings:
+Warning	1292	Truncated incorrect join_cache_level value: '9'
+SET SESSION optimizer_switch='mrr_sort_keys=off';
+CREATE TABLE `t1` (
+`pk` int(11) NOT NULL AUTO_INCREMENT,
+`col_int_nokey` int(11) DEFAULT NULL,
+`col_int_key` int(11) DEFAULT NULL,
+`col_varchar_key` varchar(1) DEFAULT NULL,
+`col_varchar_nokey` varchar(1) DEFAULT NULL,
+PRIMARY KEY (`pk`),
+KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`)
+) ENGINE=InnoDB AUTO_INCREMENT=101 DEFAULT CHARSET=latin1;
+INSERT INTO `t1` VALUES (1,6,NULL,'r','r');
+INSERT INTO `t1` VALUES (2,8,0,'c','c');
+INSERT INTO `t1` VALUES (97,7,0,'z','z');
+INSERT INTO `t1` VALUES (98,1,1,'j','j');
+INSERT INTO `t1` VALUES (99,7,8,'c','c');
+INSERT INTO `t1` VALUES (100,2,5,'f','f');
+SELECT table1 .`col_varchar_key`
+FROM t1 table1 STRAIGHT_JOIN ( t1 table3 JOIN t1 table4 ON table4 .`pk` = table3 .`col_int_nokey` ) ON table4 .`col_varchar_nokey` ;
+col_varchar_key
+DROP TABLE t1;
+set join_cache_level=@save_join_cache_level;
+set optimizer_switch=@save_optimizer_switch;
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/maria_mrr.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/maria_mrr.result
--- 5.3-noc/mysql-test/r/maria_mrr.result	1970-01-01 03:00:00.000000000 +0300
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/maria_mrr.result	2010-09-21 20:21:11.000000000 +0400
@@ -0,0 +1,324 @@
+drop table if exists t1, t2, t3;
+set @mrr_buffer_size_save= @@mrr_buffer_size;
+set @save_storage_engine= @@storage_engine;
+set storage_engine=Maria;
+create table t1(a int);
+show create table t1;
+Table	Create Table
+t1	CREATE TABLE `t1` (
+  `a` int(11) DEFAULT NULL
+) ENGINE=MARIA DEFAULT CHARSET=latin1 PAGE_CHECKSUM=1
+insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t2(a int);
+insert into t2 select A.a + 10*(B.a + 10*C.a) from t1 A, t1 B, t1 C;
+create table t3 (
+a char(8) not null, b char(8) not null, filler char(200),
+key(a)
+);
+insert into t3 select @a:=concat('c-', 1000+ A.a, '=w'), @a, 'filler' from t2 A;
+insert into t3 select concat('c-', 1000+A.a, '=w'), concat('c-', 2000+A.a, '=w'), 
+'filler-1' from t2 A;
+insert into t3 select concat('c-', 1000+A.a, '=w'), concat('c-', 3000+A.a, '=w'), 
+'filler-2' from t2 A;
+select a,filler from t3 where a >= 'c-9011=w';
+a	filler
+select a,filler from t3 where a >= 'c-1011=w' and a <= 'c-1015=w';
+a	filler
+c-1011=w	filler
+c-1012=w	filler
+c-1013=w	filler
+c-1014=w	filler
+c-1015=w	filler
+c-1011=w	filler-1
+c-1012=w	filler-1
+c-1013=w	filler-1
+c-1014=w	filler-1
+c-1015=w	filler-1
+c-1011=w	filler-2
+c-1012=w	filler-2
+c-1013=w	filler-2
+c-1014=w	filler-2
+c-1015=w	filler-2
+select a,filler from t3 where (a>='c-1011=w' and a <= 'c-1013=w') or
+(a>='c-1014=w' and a <= 'c-1015=w');
+a	filler
+c-1011=w	filler
+c-1012=w	filler
+c-1013=w	filler
+c-1014=w	filler
+c-1015=w	filler
+c-1011=w	filler-1
+c-1012=w	filler-1
+c-1013=w	filler-1
+c-1014=w	filler-1
+c-1015=w	filler-1
+c-1011=w	filler-2
+c-1012=w	filler-2
+c-1013=w	filler-2
+c-1014=w	filler-2
+c-1015=w	filler-2
+insert into t3 values ('c-1013=z', 'c-1013=z', 'err');
+insert into t3 values ('a-1014=w', 'a-1014=w', 'err');
+select a,filler from t3 where (a>='c-1011=w' and a <= 'c-1013=w') or
+(a>='c-1014=w' and a <= 'c-1015=w');
+a	filler
+c-1011=w	filler
+c-1012=w	filler
+c-1013=w	filler
+c-1014=w	filler
+c-1015=w	filler
+c-1011=w	filler-1
+c-1012=w	filler-1
+c-1013=w	filler-1
+c-1014=w	filler-1
+c-1015=w	filler-1
+c-1011=w	filler-2
+c-1012=w	filler-2
+c-1013=w	filler-2
+c-1014=w	filler-2
+c-1015=w	filler-2
+delete from t3 where b in ('c-1013=z', 'a-1014=w');
+select a,filler from t3 where a='c-1011=w' or a='c-1012=w' or a='c-1013=w' or
+a='c-1014=w' or a='c-1015=w';
+a	filler
+c-1011=w	filler
+c-1012=w	filler
+c-1013=w	filler
+c-1014=w	filler
+c-1015=w	filler
+c-1011=w	filler-1
+c-1012=w	filler-1
+c-1013=w	filler-1
+c-1014=w	filler-1
+c-1015=w	filler-1
+c-1011=w	filler-2
+c-1012=w	filler-2
+c-1013=w	filler-2
+c-1014=w	filler-2
+c-1015=w	filler-2
+insert into t3 values ('c-1013=w', 'del-me', 'inserted');
+select a,filler from t3 where a='c-1011=w' or a='c-1012=w' or a='c-1013=w' or
+a='c-1014=w' or a='c-1015=w';
+a	filler
+c-1011=w	filler
+c-1012=w	filler
+c-1013=w	filler
+c-1014=w	filler
+c-1015=w	filler
+c-1011=w	filler-1
+c-1012=w	filler-1
+c-1013=w	filler-1
+c-1014=w	filler-1
+c-1015=w	filler-1
+c-1011=w	filler-2
+c-1012=w	filler-2
+c-1013=w	filler-2
+c-1014=w	filler-2
+c-1015=w	filler-2
+c-1013=w	inserted
+delete from t3 where b='del-me';
+alter table t3 add primary key(b);
+select b,filler from t3 where (b>='c-1011=w' and b<= 'c-1018=w') or 
+b IN ('c-1019=w', 'c-1020=w', 'c-1021=w', 
+'c-1022=w', 'c-1023=w', 'c-1024=w');
+b	filler
+c-1011=w	filler
+c-1012=w	filler
+c-1013=w	filler
+c-1014=w	filler
+c-1015=w	filler
+c-1016=w	filler
+c-1017=w	filler
+c-1018=w	filler
+c-1019=w	filler
+c-1020=w	filler
+c-1021=w	filler
+c-1022=w	filler
+c-1023=w	filler
+c-1024=w	filler
+select b,filler from t3 where (b>='c-1011=w' and b<= 'c-1020=w') or 
+b IN ('c-1021=w', 'c-1022=w', 'c-1023=w');
+b	filler
+c-1011=w	filler
+c-1012=w	filler
+c-1013=w	filler
+c-1014=w	filler
+c-1015=w	filler
+c-1016=w	filler
+c-1017=w	filler
+c-1018=w	filler
+c-1019=w	filler
+c-1020=w	filler
+c-1021=w	filler
+c-1022=w	filler
+c-1023=w	filler
+select b,filler from t3 where (b>='c-1011=w' and b<= 'c-1018=w') or 
+b IN ('c-1019=w', 'c-1020=w') or 
+(b>='c-1021=w' and b<= 'c-1023=w');
+b	filler
+c-1011=w	filler
+c-1012=w	filler
+c-1013=w	filler
+c-1014=w	filler
+c-1015=w	filler
+c-1016=w	filler
+c-1017=w	filler
+c-1018=w	filler
+c-1019=w	filler
+c-1020=w	filler
+c-1021=w	filler
+c-1022=w	filler
+c-1023=w	filler
+create table t4 (a varchar(10), b int, c char(10), filler char(200),
+key idx1 (a, b, c));
+insert into t4 (filler) select concat('NULL-', 15-a) from t2 order by a limit 15;
+insert into t4 (a,b,c,filler) 
+select 'b-1',NULL,'c-1', concat('NULL-', 15-a) from t2 order by a limit 15;
+insert into t4 (a,b,c,filler) 
+select 'b-1',NULL,'c-222', concat('NULL-', 15-a) from t2 order by a limit 15;
+insert into t4 (a,b,c,filler) 
+select 'bb-1',NULL,'cc-2', concat('NULL-', 15-a) from t2 order by a limit 15;
+insert into t4 (a,b,c,filler) 
+select 'zz-1',NULL,'cc-2', 'filler-data' from t2 order by a limit 500;
+explain 
+select * from t4 where a IS NULL and b IS NULL and (c IS NULL or c='no-such-row1'
+                                                      or c='no-such-row2');
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t4	range	idx1	idx1	29	NULL	16	Using index condition; Using MRR
+select * from t4 where a IS NULL and b IS NULL and (c IS NULL or c='no-such-row1'
+                                                    or c='no-such-row2');
+a	b	c	filler
+NULL	NULL	NULL	NULL-15
+NULL	NULL	NULL	NULL-14
+NULL	NULL	NULL	NULL-13
+NULL	NULL	NULL	NULL-12
+NULL	NULL	NULL	NULL-11
+NULL	NULL	NULL	NULL-10
+NULL	NULL	NULL	NULL-9
+NULL	NULL	NULL	NULL-8
+NULL	NULL	NULL	NULL-7
+NULL	NULL	NULL	NULL-6
+NULL	NULL	NULL	NULL-5
+NULL	NULL	NULL	NULL-4
+NULL	NULL	NULL	NULL-3
+NULL	NULL	NULL	NULL-2
+NULL	NULL	NULL	NULL-1
+explain 
+select * from t4 where (a ='b-1' or a='bb-1') and b IS NULL and (c='c-1' or c='cc-2');
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t4	range	idx1	idx1	29	NULL	32	Using index condition; Using MRR
+select * from t4 where (a ='b-1' or a='bb-1') and b IS NULL and (c='c-1' or c='cc-2');
+a	b	c	filler
+b-1	NULL	c-1	NULL-15
+b-1	NULL	c-1	NULL-14
+b-1	NULL	c-1	NULL-13
+b-1	NULL	c-1	NULL-12
+b-1	NULL	c-1	NULL-11
+b-1	NULL	c-1	NULL-10
+b-1	NULL	c-1	NULL-9
+b-1	NULL	c-1	NULL-8
+b-1	NULL	c-1	NULL-7
+b-1	NULL	c-1	NULL-6
+b-1	NULL	c-1	NULL-5
+b-1	NULL	c-1	NULL-4
+b-1	NULL	c-1	NULL-3
+b-1	NULL	c-1	NULL-2
+b-1	NULL	c-1	NULL-1
+bb-1	NULL	cc-2	NULL-15
+bb-1	NULL	cc-2	NULL-14
+bb-1	NULL	cc-2	NULL-13
+bb-1	NULL	cc-2	NULL-12
+bb-1	NULL	cc-2	NULL-11
+bb-1	NULL	cc-2	NULL-10
+bb-1	NULL	cc-2	NULL-9
+bb-1	NULL	cc-2	NULL-8
+bb-1	NULL	cc-2	NULL-7
+bb-1	NULL	cc-2	NULL-6
+bb-1	NULL	cc-2	NULL-5
+bb-1	NULL	cc-2	NULL-4
+bb-1	NULL	cc-2	NULL-3
+bb-1	NULL	cc-2	NULL-2
+bb-1	NULL	cc-2	NULL-1
+select * from t4 ignore index(idx1) where (a ='b-1' or a='bb-1') and b IS NULL and (c='c-1' or c='cc-2');
+a	b	c	filler
+b-1	NULL	c-1	NULL-15
+b-1	NULL	c-1	NULL-14
+b-1	NULL	c-1	NULL-13
+b-1	NULL	c-1	NULL-12
+b-1	NULL	c-1	NULL-11
+b-1	NULL	c-1	NULL-10
+b-1	NULL	c-1	NULL-9
+b-1	NULL	c-1	NULL-8
+b-1	NULL	c-1	NULL-7
+b-1	NULL	c-1	NULL-6
+b-1	NULL	c-1	NULL-5
+b-1	NULL	c-1	NULL-4
+b-1	NULL	c-1	NULL-3
+b-1	NULL	c-1	NULL-2
+b-1	NULL	c-1	NULL-1
+bb-1	NULL	cc-2	NULL-15
+bb-1	NULL	cc-2	NULL-14
+bb-1	NULL	cc-2	NULL-13
+bb-1	NULL	cc-2	NULL-12
+bb-1	NULL	cc-2	NULL-11
+bb-1	NULL	cc-2	NULL-10
+bb-1	NULL	cc-2	NULL-9
+bb-1	NULL	cc-2	NULL-8
+bb-1	NULL	cc-2	NULL-7
+bb-1	NULL	cc-2	NULL-6
+bb-1	NULL	cc-2	NULL-5
+bb-1	NULL	cc-2	NULL-4
+bb-1	NULL	cc-2	NULL-3
+bb-1	NULL	cc-2	NULL-2
+bb-1	NULL	cc-2	NULL-1
+drop table t1, t2, t3, t4;
+create table t1 (a int, b int not null,unique key (a,b),index(b));
+insert ignore into t1 values (1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(null,7),(9,9),(8,8),(7,7),(null,9),(null,9),(6,6);
+create table t2 like t1;
+insert into t2 select * from t1;
+alter table t1 modify b blob not null, add c int not null, drop key a, add unique key (a,b(20),c), drop key b, add key (b(10));
+select * from t1 where a is null;
+a	b	c
+NULL	7	0
+NULL	9	0
+NULL	9	0
+select * from t1 where (a is null or a > 0 and a < 3) and b > 7 limit 3;
+a	b	c
+NULL	9	0
+NULL	9	0
+select * from t1 where a is null and b=9 or a is null and b=7 limit 3;
+a	b	c
+NULL	7	0
+NULL	9	0
+NULL	9	0
+drop table t1, t2;
+set storage_engine= @save_storage_engine;
+set @@mrr_buffer_size= @mrr_buffer_size_save;
+# 
+# Crash in quick_range_seq_next() in maria-5.3-dsmrr-cpk with join_cache_level = {8,1}
+# 
+set @save_join_cache_level= @@join_cache_level;
+SET SESSION join_cache_level = 8;
+CREATE TABLE `t1` (
+`col_int_key` int(11) DEFAULT NULL,
+`col_datetime_key` datetime DEFAULT NULL,
+`col_varchar_key` varchar(1) DEFAULT NULL,
+`col_varchar_nokey` varchar(1) DEFAULT NULL,
+KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`)
+) ENGINE=MARIA DEFAULT CHARSET=latin1 PAGE_CHECKSUM=1;
+INSERT INTO `t1` VALUES (6,'2005-10-07 00:00:00','e','e');
+INSERT INTO `t1` VALUES (51,'2000-07-15 05:00:34','f','f');
+CREATE TABLE `t2` (
+`col_int_key` int(11) DEFAULT NULL,
+`col_datetime_key` datetime DEFAULT NULL,
+`col_varchar_key` varchar(1) DEFAULT NULL,
+`col_varchar_nokey` varchar(1) DEFAULT NULL,
+KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`)
+) ENGINE=MARIA DEFAULT CHARSET=latin1 PAGE_CHECKSUM=1;
+INSERT INTO `t2` VALUES (2,'2004-10-11 18:13:16','w','w');
+INSERT INTO `t2` VALUES (2,'1900-01-01 00:00:00','d','d');
+SELECT table2 .`col_datetime_key`
+FROM t2 JOIN ( t1 table2 JOIN t2 table3 ON table3 .`col_varchar_key` < table2 .`col_varchar_key` ) ON table3 .`col_varchar_nokey` ;
+col_datetime_key
+drop table t1, t2;
+set join_cache_level=@save_join_cache_level;
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/myisam_mrr.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/myisam_mrr.result
--- 5.3-noc/mysql-test/r/myisam_mrr.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/myisam_mrr.result	2010-09-21 20:21:11.000000000 +0400
@@ -413,4 +413,52 @@
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	range	a	a	5	NULL	20	Using index condition; Using MRR
 set optimizer_switch=@save_optimizer_switch;
+# 
+# BUG#629684: Unreachable code in multi_range_read.cc in maria-5.3-dsmrr-cpk
+#
+delete from t0 where a > 2;
+insert into t0 values (NULL),(NULL);
+insert into t1 values (NULL, 1234), (NULL, 5678);
+set @save_join_cache_level=@@join_cache_level;
+set @@join_cache_level=6;
+explain 
+select * from t0, t1 where t0.a<=>t1.a;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t0	ALL	NULL	NULL	NULL	NULL	5	
+1	SIMPLE	t1	ref	a	a	5	test.t0.a	1	Using index condition(BKA); Using join buffer
+select * from t0, t1 where t0.a<=>t1.a;
+a	a	b
+0	0	0
+1	1	1
+2	2	2
+NULL	NULL	1234
+NULL	NULL	1234
+NULL	NULL	5678
+NULL	NULL	5678
+set @@join_cache_level=@save_join_cache_level;
 drop table t0, t1;
+#
+# BUG#625841: Assertion `!table || (!table->read_set || bitmap_is_set
+#             (table->read_set, field_index))' on REPLACE ... SELECT with MRR
+#
+create table t0 (a int);
+insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t1 (
+key1 varchar(10),
+col1 char(255), col2 char(255),
+col3 char(244), col4 char(255),
+key(key1)
+);
+create table t2 like t1;
+insert into t1
+select
+1000+A.a+100*B.a + 10*C.a,
+'col1val', 'col2val',
+'col3val', 'col4val'
+from t0 A, t0 B, t0 C;
+REPLACE INTO t2(col2,col3,col4)
+SELECT col2,col3,col4
+FROM t1
+WHERE `key1` LIKE CONCAT( LEFT( '1' , 7 ) , '%' )
+ORDER BY col1 LIMIT 7;
+drop table t0, t1, t2;
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/optimizer_switch.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/optimizer_switch.result
--- 5.3-noc/mysql-test/r/optimizer_switch.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/optimizer_switch.result	2010-08-14 19:28:23.000000000 +0400
@@ -4,19 +4,19 @@
 #
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 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_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 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_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=off,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 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_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=off,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch=4;
 ERROR 42000: Variable 'optimizer_switch' can't be set to the value of '4'
 set optimizer_switch=NULL;
@@ -43,57 +43,57 @@
 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_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=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_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=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_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=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_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 
 BUG#37120 optimizer_switch allowable values not according to specification
 
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch='default,materialization=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch='default,semijoin=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch='default,loosescan=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch='default,semijoin=off,materialization=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch='default,materialization=off,semijoin=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch='default,semijoin=off,materialization=off,loosescan=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch='default,semijoin=off,loosescan=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch='default,materialization=off,loosescan=off';
 select @@optimizer_switch;
 @@optimizer_switch
-index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=off,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on
+index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=off,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr_sort_keys=on
 set optimizer_switch=default;
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/order_by.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/order_by.result
--- 5.3-noc/mysql-test/r/order_by.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/order_by.result	2010-09-21 20:21:11.000000000 +0400
@@ -1489,7 +1489,7 @@
 WHERE t2.b=14 AND t2.a=t1.a AND 5.1<t2.c AND t1.b='DE'
 ORDER BY t2.c LIMIT 1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	a,b	b	4	const	4	Using index condition; Using temporary; Using filesort
+1	SIMPLE	t1	ref	a,b	b	4	const	4	Using index condition; Using where; Using temporary; Using filesort
 1	SIMPLE	t2	ref	a,b,c	a	40	test.t1.a,const	11	Using index condition
 SELECT d FROM t1, t2
 WHERE t2.b=14 AND t2.a=t1.a AND 5.1<t2.c AND t1.b='DE'
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/select_jcl6.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/select_jcl6.result
--- 5.3-noc/mysql-test/r/select_jcl6.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/select_jcl6.result	2010-09-21 20:21:11.000000000 +0400
@@ -3566,19 +3566,19 @@
 FROM t1 JOIN t2 ON t2.fk=t1.pk
 WHERE t2.fk < 'c' AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	3	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	3	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where; Using join buffer
 EXPLAIN SELECT t2.* 
 FROM t1 JOIN t2 ON t2.fk=t1.pk 
 WHERE t2.fk BETWEEN 'a' AND 'b' AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where; Using join buffer
 EXPLAIN SELECT t2.* 
 FROM t1 JOIN t2 ON t2.fk=t1.pk 
 WHERE t2.fk IN ('a','b') AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where; Using join buffer
 DROP TABLE t1,t2;
 CREATE TABLE t1 (a int, b varchar(20) NOT NULL, PRIMARY KEY(a));
@@ -3612,7 +3612,7 @@
 t3.a=t2.a AND t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si	si	5	NULL	4	Using index condition; Using MRR
+1	SIMPLE	t2	range	si	si	5	NULL	4	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where; Using join buffer
 EXPLAIN
 SELECT t3.a FROM t1,t2,t3
@@ -3620,7 +3620,7 @@
 t3.a=t2.a AND t3.c IN ('bb','ee') ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si,ai	si	5	NULL	4	Using index condition; Using MRR
+1	SIMPLE	t2	range	si,ai	si	5	NULL	4	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where; Using join buffer
 EXPLAIN 
 SELECT t3.a FROM t1,t2 FORCE INDEX (si),t3
@@ -3628,7 +3628,7 @@
 t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si	si	5	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t2	range	si	si	5	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where; Using join buffer
 EXPLAIN 
 SELECT t3.a FROM t1,t2,t3
@@ -3636,7 +3636,7 @@
 t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si,ai	si	5	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t2	range	si,ai	si	5	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where; Using join buffer
 DROP TABLE t1,t2,t3;
 CREATE TABLE t1 ( f1 int primary key, f2 int, f3 int, f4 int, f5 int, f6 int, checked_out int);
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/select_pkeycache.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/select_pkeycache.result
--- 5.3-noc/mysql-test/r/select_pkeycache.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/select_pkeycache.result	2010-09-21 20:21:11.000000000 +0400
@@ -3562,19 +3562,19 @@
 FROM t1 JOIN t2 ON t2.fk=t1.pk
 WHERE t2.fk < 'c' AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	3	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	3	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where
 EXPLAIN SELECT t2.* 
 FROM t1 JOIN t2 ON t2.fk=t1.pk 
 WHERE t2.fk BETWEEN 'a' AND 'b' AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where
 EXPLAIN SELECT t2.* 
 FROM t1 JOIN t2 ON t2.fk=t1.pk 
 WHERE t2.fk IN ('a','b') AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where
 DROP TABLE t1,t2;
 CREATE TABLE t1 (a int, b varchar(20) NOT NULL, PRIMARY KEY(a));
@@ -3608,7 +3608,7 @@
 t3.a=t2.a AND t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si	si	5	NULL	4	Using index condition; Using MRR
+1	SIMPLE	t2	range	si	si	5	NULL	4	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
 EXPLAIN
 SELECT t3.a FROM t1,t2,t3
@@ -3616,7 +3616,7 @@
 t3.a=t2.a AND t3.c IN ('bb','ee') ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si,ai	si	5	NULL	4	Using index condition; Using MRR
+1	SIMPLE	t2	range	si,ai	si	5	NULL	4	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
 EXPLAIN 
 SELECT t3.a FROM t1,t2 FORCE INDEX (si),t3
@@ -3624,7 +3624,7 @@
 t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si	si	5	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t2	range	si	si	5	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
 EXPLAIN 
 SELECT t3.a FROM t1,t2,t3
@@ -3632,7 +3632,7 @@
 t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si,ai	si	5	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t2	range	si,ai	si	5	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
 DROP TABLE t1,t2,t3;
 CREATE TABLE t1 ( f1 int primary key, f2 int, f3 int, f4 int, f5 int, f6 int, checked_out int);
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/select.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/select.result
--- 5.3-noc/mysql-test/r/select.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/select.result	2010-09-21 20:21:11.000000000 +0400
@@ -3562,19 +3562,19 @@
 FROM t1 JOIN t2 ON t2.fk=t1.pk
 WHERE t2.fk < 'c' AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	3	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	3	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where
 EXPLAIN SELECT t2.* 
 FROM t1 JOIN t2 ON t2.fk=t1.pk 
 WHERE t2.fk BETWEEN 'a' AND 'b' AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where
 EXPLAIN SELECT t2.* 
 FROM t1 JOIN t2 ON t2.fk=t1.pk 
 WHERE t2.fk IN ('a','b') AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where
 DROP TABLE t1,t2;
 CREATE TABLE t1 (a int, b varchar(20) NOT NULL, PRIMARY KEY(a));
@@ -3608,7 +3608,7 @@
 t3.a=t2.a AND t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si	si	5	NULL	4	Using index condition; Using MRR
+1	SIMPLE	t2	range	si	si	5	NULL	4	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
 EXPLAIN
 SELECT t3.a FROM t1,t2,t3
@@ -3616,7 +3616,7 @@
 t3.a=t2.a AND t3.c IN ('bb','ee') ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si,ai	si	5	NULL	4	Using index condition; Using MRR
+1	SIMPLE	t2	range	si,ai	si	5	NULL	4	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
 EXPLAIN 
 SELECT t3.a FROM t1,t2 FORCE INDEX (si),t3
@@ -3624,7 +3624,7 @@
 t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si	si	5	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t2	range	si	si	5	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
 EXPLAIN 
 SELECT t3.a FROM t1,t2,t3
@@ -3632,7 +3632,7 @@
 t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	range	si,ai	si	5	NULL	2	Using index condition; Using MRR
+1	SIMPLE	t2	range	si,ai	si	5	NULL	2	Using index condition; Using where; Using MRR
 1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
 DROP TABLE t1,t2,t3;
 CREATE TABLE t1 ( f1 int primary key, f2 int, f3 int, f4 int, f5 int, f6 int, checked_out int);
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/subselect3_jcl6.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/subselect3_jcl6.result
--- 5.3-noc/mysql-test/r/subselect3_jcl6.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/subselect3_jcl6.result	2010-09-21 20:21:11.000000000 +0400
@@ -1135,7 +1135,7 @@
 explain select * from t3 where a in (select t1.kp1 from t1,t4 where kp1<20
 and t4.pk=t1.c);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	range	kp1	kp1	5	NULL	48	Using index condition; Using MRR; LooseScan
+1	PRIMARY	t1	range	kp1	kp1	5	NULL	48	Using index condition; Using where; Using MRR; LooseScan
 1	PRIMARY	t4	eq_ref	PRIMARY	PRIMARY	4	test.t1.c	1	Using index; FirstMatch(t1)
 1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	100	Using where; Using join buffer
 drop table t1, t3, t4;
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/subselect3.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/subselect3.result
--- 5.3-noc/mysql-test/r/subselect3.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/subselect3.result	2010-09-21 20:21:11.000000000 +0400
@@ -1130,7 +1130,7 @@
 explain select * from t3 where a in (select t1.kp1 from t1,t4 where kp1<20
 and t4.pk=t1.c);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	range	kp1	kp1	5	NULL	48	Using index condition; Using MRR; LooseScan
+1	PRIMARY	t1	range	kp1	kp1	5	NULL	48	Using index condition; Using where; Using MRR; LooseScan
 1	PRIMARY	t4	eq_ref	PRIMARY	PRIMARY	4	test.t1.c	1	Using index; FirstMatch(t1)
 1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	100	Using where; Using join buffer
 drop table t1, t3, t4;
diff -urN --exclude='.*' 5.3-noc/mysql-test/r/table_elim.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/table_elim.result
--- 5.3-noc/mysql-test/r/table_elim.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/r/table_elim.result	2010-09-21 20:21:11.000000000 +0400
@@ -128,7 +128,7 @@
 This should use facts and a1 tables:
 explain extended select id from v1 where attr1 between 12 and 14;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	a1	range	PRIMARY,attr1	attr1	5	NULL	2	100.00	Using index condition; Using MRR
+1	PRIMARY	a1	range	PRIMARY,attr1	attr1	5	NULL	2	100.00	Using index condition; Using where; Using MRR
 1	PRIMARY	f	eq_ref	PRIMARY	PRIMARY	4	test.a1.id	1	100.00	Using index
 Warnings:
 Note	1276	Field or reference 'test.a2.id' of SELECT #3 was resolved in SELECT #1
@@ -156,7 +156,7 @@
 This should use facts and a1 tables:
 explain extended select id from v2 where attr1 between 12 and 14;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	a1	range	PRIMARY,attr1	attr1	5	NULL	2	100.00	Using index condition; Using MRR
+1	PRIMARY	a1	range	PRIMARY,attr1	attr1	5	NULL	2	100.00	Using index condition; Using where; Using MRR
 1	PRIMARY	f	eq_ref	PRIMARY	PRIMARY	4	test.a1.id	1	100.00	Using index
 Warnings:
 Note	1276	Field or reference 'test.f.id' of SELECT #3 was resolved in SELECT #1
@@ -164,7 +164,7 @@
 This should use facts, a2 and its subquery:
 explain extended select id from v2 where attr2 between 12 and 14;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	a2	range	PRIMARY,attr2	attr2	5	NULL	5	100.00	Using index condition; Using MRR
+1	PRIMARY	a2	range	PRIMARY,attr2	attr2	5	NULL	5	100.00	Using index condition; Using where; Using MRR
 1	PRIMARY	f	eq_ref	PRIMARY	PRIMARY	4	test.a2.id	1	100.00	Using where; Using index
 3	DEPENDENT SUBQUERY	t2	ref	PRIMARY	PRIMARY	4	test.f.id	2	100.00	Using index
 Warnings:
diff -urN --exclude='.*' 5.3-noc/mysql-test/suite/vcol/r/vcol_misc.result maria-5.3-dsmrr-cpk-r5-noc/mysql-test/suite/vcol/r/vcol_misc.result
--- 5.3-noc/mysql-test/suite/vcol/r/vcol_misc.result	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/suite/vcol/r/vcol_misc.result	2010-08-20 00:41:38.000000000 +0400
@@ -13,8 +13,8 @@
 1	SIMPLE	t2	ref	idx	idx	5	test.t1.b	2	Using where; Using join buffer
 select * from t1,t2 where t1.b=t2.c and d <= 100;
 a	b	c	d	v
-4	20	20	100	101
 1	20	20	100	101
 3	30	30	100	101
+4	20	20	100	101
 set join_cache_level=default;
 drop table t1, t2;
diff -urN --exclude='.*' 5.3-noc/mysql-test/suite/vcol/t/vcol_misc.test maria-5.3-dsmrr-cpk-r5-noc/mysql-test/suite/vcol/t/vcol_misc.test
--- 5.3-noc/mysql-test/suite/vcol/t/vcol_misc.test	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/suite/vcol/t/vcol_misc.test	2010-08-20 00:41:38.000000000 +0400
@@ -17,7 +17,8 @@
 explain
 select * from t1,t2 where t1.b=t2.c and d <= 100;
 
+--sorted_result
 select * from t1,t2 where t1.b=t2.c and d <= 100;
 set join_cache_level=default;
 
-drop table t1, t2;
\ No newline at end of file
+drop table t1, t2;
diff -urN --exclude='.*' 5.3-noc/mysql-test/t/innodb_mrr_cpk.test maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/innodb_mrr_cpk.test
--- 5.3-noc/mysql-test/t/innodb_mrr_cpk.test	1970-01-01 03:00:00.000000000 +0300
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/innodb_mrr_cpk.test	2010-08-14 19:28:23.000000000 +0400
@@ -0,0 +1,137 @@
+# 
+# Tests for DS-MRR over clustered primary key. The only engine that supports
+# this is InnoDB/XtraDB.
+#
+# Basic idea about testing
+#  - DS-MRR/CPK works only with BKA
+#  - Should also test index condition pushdown
+#  - Should also test whatever uses RANGE_SEQ_IF::skip_record() for filtering
+#  - Also test access using prefix of primary key
+# 
+#  - Forget about cost model, BKA's multi_range_read_info() call passes 10 for
+#    #rows, the call is there at all only for applicability check
+# 
+-- source include/have_innodb.inc
+
+--disable_warnings
+drop table if exists t0,t1,t2,t3;
+--enable_warnings
+
+set @save_join_cache_level=@@join_cache_level;
+set join_cache_level=6;
+
+set @save_storage_engine=@@storage_engine;
+set storage_engine=innodb;
+
+create table t0(a int);
+insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t1(a char(8), b char(8), filler char(100), primary key(a));
+show create table t1;
+
+insert into t1 select 
+  concat('a-', 1000 + A.a + B.a*10 + C.a*100, '=A'),
+  concat('b-', 1000 + A.a + B.a*10 + C.a*100, '=B'),
+  'filler'
+from t0 A, t0 B, t0 C;
+
+create table t2 (a char(8));
+insert into t2 values ('a-1010=A'), ('a-1030=A'), ('a-1020=A');
+
+--echo This should use join buffer:
+explain select * from t1, t2 where t1.a=t2.a;
+
+--echo This output must be sorted by value of t1.a:
+select * from t1, t2 where t1.a=t2.a;
+drop table t1, t2;
+
+# Try multi-column indexes
+create table t1(
+  a char(8) character set utf8, b int, filler char(100), 
+  primary key(a,b)
+);
+
+insert into t1 select 
+  concat('a-', 1000 + A.a + B.a*10 + C.a*100, '=A'),
+  1000 + A.a + B.a*10 + C.a*100,
+  'filler'
+from t0 A, t0 B, t0 C;
+
+create table t2 (a char(8) character set utf8, b int);
+insert into t2 values ('a-1010=A', 1010), ('a-1030=A', 1030), ('a-1020=A', 1020);
+explain select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+
+# Try with dataset that causes identical lookup keys:
+insert into t2 values ('a-1030=A', 1030), ('a-1020=A', 1020);
+explain select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+
+drop table t1, t2;
+
+create table t1(
+  a varchar(8) character set utf8, b int, filler char(100), 
+  primary key(a,b)
+);
+
+insert into t1 select 
+  concat('a-', 1000 + A.a + B.a*10 + C.a*100, '=A'),
+  1000 + A.a + B.a*10 + C.a*100,
+  'filler'
+from t0 A, t0 B, t0 C;
+
+create table t2 (a char(8) character set utf8, b int);
+insert into t2 values ('a-1010=A', 1010), ('a-1030=A', 1030), ('a-1020=A', 1020);
+explain select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+
+# 
+# Try scanning on a CPK prefix
+#
+explain select * from t1, t2 where t1.a=t2.a;
+select * from t1, t2 where t1.a=t2.a;
+drop table t1, t2;
+
+#
+# The above example is not very interesting, as CPK prefix has 
+# only one match.  Create a dataset where scan on CPK prefix 
+# would produce multiple matches:
+#
+create table t1 (a int, b int, c int, filler char(100), primary key(a,b,c));
+insert into t1 select A.a, B.a, C.a, 'filler' from t0 A, t0 B, t0 C;
+
+insert into t1 values (11, 11, 11,   'filler');
+insert into t1 values (11, 11, 12,   'filler');
+insert into t1 values (11, 11, 13,   'filler');
+insert into t1 values (11, 22, 1234, 'filler');
+insert into t1 values (11, 33, 124,  'filler');
+insert into t1 values (11, 33, 125,  'filler');
+
+create table t2 (a int, b int);
+insert into t2 values (11,33), (11,22), (11,11);
+
+explain select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+
+# Check a real resultset for comaprison:
+set join_cache_level=0;
+select * from t1, t2 where t1.a=t2.a and t1.b=t2.b;
+set join_cache_level=6;
+
+
+#
+# Check that Index Condition Pushdown (BKA) actually works:
+#
+explain select * from t1, t2 where t1.a=t2.a and t2.b + t1.b > 100;
+select * from t1, t2 where t1.a=t2.a and t2.b + t1.b > 100;
+
+set optimizer_switch='index_condition_pushdown=off';
+explain select * from t1, t2 where t1.a=t2.a and t2.b + t1.b > 100;
+select * from t1, t2 where t1.a=t2.a and t2.b + t1.b > 100;
+set optimizer_switch='index_condition_pushdown=on';
+
+drop table t1,t2;
+
+set @@join_cache_level= @save_join_cache_level;
+set storage_engine=@save_storage_engine;
+drop table t0;
+
diff -urN --exclude='.*' 5.3-noc/mysql-test/t/innodb_mrr.test maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/innodb_mrr.test
--- 5.3-noc/mysql-test/t/innodb_mrr.test	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/innodb_mrr.test	2010-09-21 20:21:11.000000000 +0400
@@ -123,3 +123,34 @@
 explain SELECT * FROM t1 FORCE INDEX (PRIMARY) WHERE parent_id IS NOT NULL ORDER BY id DESC LIMIT 1;
 SELECT * FROM t1 WHERE parent_id IS NOT NULL ORDER BY id DESC LIMIT 1;
 drop table t1;
+
+
+-- echo #
+-- echo # BUG#628785: multi_range_read.cc:430: int DsMrr_impl::dsmrr_init(): Assertion `do_sort_keys || do_rowid_fetch' failed 
+-- echo #
+set @save_join_cache_level= @@join_cache_level;
+set @save_optimizer_switch= @@optimizer_switch;
+SET SESSION join_cache_level=9;
+SET SESSION optimizer_switch='mrr_sort_keys=off';
+
+CREATE TABLE `t1` (
+  `pk` int(11) NOT NULL AUTO_INCREMENT,
+  `col_int_nokey` int(11) DEFAULT NULL,
+  `col_int_key` int(11) DEFAULT NULL,
+  `col_varchar_key` varchar(1) DEFAULT NULL,
+  `col_varchar_nokey` varchar(1) DEFAULT NULL,
+  PRIMARY KEY (`pk`),
+  KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`)
+) ENGINE=InnoDB AUTO_INCREMENT=101 DEFAULT CHARSET=latin1;
+INSERT INTO `t1` VALUES (1,6,NULL,'r','r');
+INSERT INTO `t1` VALUES (2,8,0,'c','c');
+INSERT INTO `t1` VALUES (97,7,0,'z','z');
+INSERT INTO `t1` VALUES (98,1,1,'j','j');
+INSERT INTO `t1` VALUES (99,7,8,'c','c');
+INSERT INTO `t1` VALUES (100,2,5,'f','f');
+SELECT table1 .`col_varchar_key`
+FROM t1 table1 STRAIGHT_JOIN ( t1 table3 JOIN t1 table4 ON table4 .`pk` = table3 .`col_int_nokey` ) ON table4 .`col_varchar_nokey` ;
+DROP TABLE t1;
+set join_cache_level=@save_join_cache_level;
+set optimizer_switch=@save_optimizer_switch;
+
diff -urN --exclude='.*' 5.3-noc/mysql-test/t/join_nested.test maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/join_nested.test
--- 5.3-noc/mysql-test/t/join_nested.test	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/join_nested.test	2010-10-04 10:47:05.000000000 +0400
@@ -462,7 +462,6 @@
        LEFT JOIN              
        (t1,t2)
        ON t3.a=1 AND t3.b=t2.b AND t2.b=t4.b;
-
 SELECT t2.a,t2.b,t3.a,t3.b,t4.a,t4.b
   FROM (t3,t4)
        LEFT JOIN              
diff -urN --exclude='.*' 5.3-noc/mysql-test/t/maria_mrr.test maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/maria_mrr.test
--- 5.3-noc/mysql-test/t/maria_mrr.test	1970-01-01 03:00:00.000000000 +0300
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/maria_mrr.test	2010-09-21 20:21:11.000000000 +0400
@@ -0,0 +1,47 @@
+-- source include/have_maria.inc
+#
+# MRR/Maria tests.
+#
+
+--disable_warnings
+drop table if exists t1, t2, t3;
+--enable_warnings
+
+set @mrr_buffer_size_save= @@mrr_buffer_size;
+
+set @save_storage_engine= @@storage_engine;
+set storage_engine=Maria;
+-- source include/mrr_tests.inc
+set storage_engine= @save_storage_engine;
+
+set @@mrr_buffer_size= @mrr_buffer_size_save;
+
+--echo # 
+--echo # Crash in quick_range_seq_next() in maria-5.3-dsmrr-cpk with join_cache_level = {8,1}
+--echo # 
+set @save_join_cache_level= @@join_cache_level;
+SET SESSION join_cache_level = 8;
+CREATE TABLE `t1` (
+  `col_int_key` int(11) DEFAULT NULL,
+  `col_datetime_key` datetime DEFAULT NULL,
+  `col_varchar_key` varchar(1) DEFAULT NULL,
+  `col_varchar_nokey` varchar(1) DEFAULT NULL,
+  KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`)
+) ENGINE=MARIA DEFAULT CHARSET=latin1 PAGE_CHECKSUM=1;
+INSERT INTO `t1` VALUES (6,'2005-10-07 00:00:00','e','e');
+INSERT INTO `t1` VALUES (51,'2000-07-15 05:00:34','f','f');
+CREATE TABLE `t2` (
+  `col_int_key` int(11) DEFAULT NULL,
+  `col_datetime_key` datetime DEFAULT NULL,
+  `col_varchar_key` varchar(1) DEFAULT NULL,
+  `col_varchar_nokey` varchar(1) DEFAULT NULL,
+  KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`)
+) ENGINE=MARIA DEFAULT CHARSET=latin1 PAGE_CHECKSUM=1;
+INSERT INTO `t2` VALUES (2,'2004-10-11 18:13:16','w','w');
+INSERT INTO `t2` VALUES (2,'1900-01-01 00:00:00','d','d');
+SELECT table2 .`col_datetime_key`
+FROM t2 JOIN ( t1 table2 JOIN t2 table3 ON table3 .`col_varchar_key` < table2 .`col_varchar_key` ) ON table3 .`col_varchar_nokey` ;
+
+drop table t1, t2;
+set join_cache_level=@save_join_cache_level;
+
diff -urN --exclude='.*' 5.3-noc/mysql-test/t/myisam_mrr.test maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/myisam_mrr.test
--- 5.3-noc/mysql-test/t/myisam_mrr.test	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/myisam_mrr.test	2010-09-21 20:21:11.000000000 +0400
@@ -123,4 +123,49 @@
 
 set optimizer_switch=@save_optimizer_switch;
 
+
+--echo # 
+--echo # BUG#629684: Unreachable code in multi_range_read.cc in maria-5.3-dsmrr-cpk
+--echo #
+
+delete from t0 where a > 2;
+insert into t0 values (NULL),(NULL);
+insert into t1 values (NULL, 1234), (NULL, 5678);
+
+set @save_join_cache_level=@@join_cache_level;
+set @@join_cache_level=6;
+explain 
+select * from t0, t1 where t0.a<=>t1.a;
+select * from t0, t1 where t0.a<=>t1.a;
+
+set @@join_cache_level=@save_join_cache_level;
 drop table t0, t1;
+
+--echo #
+--echo # BUG#625841: Assertion `!table || (!table->read_set || bitmap_is_set
+--echo #             (table->read_set, field_index))' on REPLACE ... SELECT with MRR
+--echo #
+create table t0 (a int);
+insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+
+create table t1 (
+  key1 varchar(10),
+  col1 char(255), col2 char(255),
+  col3 char(244), col4 char(255),
+  key(key1)
+);
+create table t2 like t1;
+
+insert into t1
+select
+  1000+A.a+100*B.a + 10*C.a,
+  'col1val', 'col2val',
+  'col3val', 'col4val'
+from t0 A, t0 B, t0 C;
+
+REPLACE INTO t2(col2,col3,col4)
+SELECT col2,col3,col4
+FROM t1
+WHERE `key1` LIKE CONCAT( LEFT( '1' , 7 ) , '%' )
+ORDER BY col1 LIMIT 7;
+drop table t0, t1, t2;
diff -urN --exclude='.*' 5.3-noc/mysql-test/t/subselect_sj2.test maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/subselect_sj2.test
--- 5.3-noc/mysql-test/t/subselect_sj2.test	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/mysql-test/t/subselect_sj2.test	2010-10-04 10:47:05.000000000 +0400
@@ -586,6 +586,7 @@
   --echo # Not anymore:
   --echo # The following query gives wrong result due to Bug#49129
 }
+
 select * from t0 where t0.a in 
   (select t1.a from t1, t2 where t2.a=t0.a and t1.b=t2.b);
 
diff -urN --exclude='.*' 5.3-noc/sql/CMakeLists.txt maria-5.3-dsmrr-cpk-r5-noc/sql/CMakeLists.txt
--- 5.3-noc/sql/CMakeLists.txt	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/CMakeLists.txt	2010-10-04 10:47:05.000000000 +0400
@@ -63,6 +63,7 @@
                sql_cache.cc sql_class.cc sql_client.cc sql_crypt.cc sql_crypt.h 
                sql_cursor.cc sql_db.cc sql_delete.cc sql_derived.cc sql_do.cc 
                sql_error.cc sql_handler.cc sql_help.cc sql_insert.cc
+               sql_lifo_buffer.h
                sql_join_cache.cc sql_lex.cc sql_list.cc sql_load.cc sql_manager.cc
                sql_map.cc sql_parse.cc  sql_partition.cc sql_plugin.cc
                sql_prepare.cc sql_rename.cc 
diff -urN --exclude='.*' 5.3-noc/sql/filesort.cc maria-5.3-dsmrr-cpk-r5-noc/sql/filesort.cc
--- 5.3-noc/sql/filesort.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/filesort.cc	2010-09-21 20:21:11.000000000 +0400
@@ -542,11 +542,6 @@
 		    current_thd->variables.read_buff_size);
   }
 
-  if (quick_select)
-  {
-    if (select->quick->reset())
-      DBUG_RETURN(HA_POS_ERROR);
-  }
 
   /* Remember original bitmaps */
   save_read_set=  sort_form->read_set;
@@ -559,8 +554,18 @@
   if (select && select->cond)
     select->cond->walk(&Item::register_field_in_read_map, 1,
                        (uchar*) sort_form);
+  if (select && select->pre_idx_push_select_cond)
+    select->pre_idx_push_select_cond->walk(&Item::register_field_in_read_map,
+                                           1, (uchar*) sort_form);
+
   sort_form->column_bitmaps_set(&sort_form->tmp_set, &sort_form->tmp_set);
 
+  if (quick_select)
+  {
+    if (select->quick->reset())
+      DBUG_RETURN(HA_POS_ERROR);
+  }
+
   for (;;)
   {
     if (quick_select)
diff -urN --exclude='.*' 5.3-noc/sql/handler.h maria-5.3-dsmrr-cpk-r5-noc/sql/handler.h
--- 5.3-noc/sql/handler.h	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/handler.h	2010-10-04 10:47:05.000000000 +0400
@@ -1278,9 +1278,9 @@
                          COST_VECT *cost);
 
 /*
-  The below two are not used (and not handled) in this milestone of this WL
-  entry because there seems to be no use for them at this stage of
-  implementation.
+  Indicates that all scanned ranges will be singlepoint (aka equality) ranges.
+  The ranges may not use the full key but all of them will use the same number
+  of key parts.
 */
 #define HA_MRR_SINGLE_POINT 1
 #define HA_MRR_FIXED_KEY  2
@@ -1322,6 +1322,16 @@
 */
 #define HA_MRR_NO_NULL_ENDPOINTS 128
 
+/*
+  The MRR user has materialized range keys somewhere in the user's buffer.
+  This can be used for optimization of the procedure that sorts these keys
+  since in this case key values don't have to be copied into the MRR buffer.
+
+  In other words, it is guaranteed that after RANGE_SEQ_IF::next() call the 
+  pointer in range->start_key.key will point to a key value that will remain 
+  there until the end of the MRR scan.
+*/
+#define HA_MRR_MATERIALIZED_KEYS 256
 
 
 /*
@@ -1801,14 +1811,19 @@
   inline int ha_index_first(uchar * buf);
   inline int ha_index_last(uchar * buf);
   inline int ha_index_next_same(uchar *buf, const uchar *key, uint keylen);
+  /*
+    TODO: should we make for those functions non-virtual ha_func_name wrappers,
+    too?
+  */
   virtual ha_rows multi_range_read_info_const(uint keyno, RANGE_SEQ_IF *seq,
                                               void *seq_init_param, 
                                               uint n_ranges, uint *bufsz,
                                               uint *flags, COST_VECT *cost);
   virtual ha_rows multi_range_read_info(uint keyno, uint n_ranges, uint keys,
-                                        uint *bufsz, uint *flags, COST_VECT *cost);
+                                        uint key_parts, uint *bufsz, 
+                                        uint *flags, COST_VECT *cost);
   virtual int multi_range_read_init(RANGE_SEQ_IF *seq, void *seq_init_param,
-                                    uint n_ranges, uint mode,
+                                    uint n_ranges, uint mode, 
                                     HANDLER_BUFFER *buf);
   virtual int multi_range_read_next(char **range_info);
   virtual int read_range_first(const key_range *start_key,
diff -urN --exclude='.*' 5.3-noc/sql/Makefile.am maria-5.3-dsmrr-cpk-r5-noc/sql/Makefile.am
--- 5.3-noc/sql/Makefile.am	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/Makefile.am	2010-10-04 10:47:05.000000000 +0400
@@ -66,6 +66,7 @@
 			log.h log_slow.h sql_show.h rpl_rli.h rpl_mi.h \
 			sql_select.h structs.h table.h sql_udf.h hash_filo.h \
 			lex.h lex_symbol.h sql_acl.h sql_crypt.h  \
+                        sql_lifo_buffer.h \
 			sql_repl.h slave.h rpl_filter.h rpl_injector.h \
 			log_event.h rpl_record.h \
 			log_event_old.h rpl_record_old.h \
diff -urN --exclude='.*' 5.3-noc/sql/multi_range_read.cc maria-5.3-dsmrr-cpk-r5-noc/sql/multi_range_read.cc
--- 5.3-noc/sql/multi_range_read.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/multi_range_read.cc	2010-10-04 10:48:03.000000000 +0400
@@ -1,4 +1,5 @@
 #include "mysql_priv.h"
+#include <my_bit.h>
 #include "sql_select.h"
 
 /****************************************************************************
@@ -136,10 +137,16 @@
 */
 
 ha_rows handler::multi_range_read_info(uint keyno, uint n_ranges, uint n_rows,
-                                       uint *bufsz, uint *flags, COST_VECT *cost)
+                                       uint key_parts, uint *bufsz, 
+                                       uint *flags, COST_VECT *cost)
 {
-  *bufsz= 0; /* Default implementation doesn't need a buffer */
+  /* 
+    Currently we expect this function to be called only in preparation of scan
+    with HA_MRR_SINGLE_POINT property.
+  */
+  DBUG_ASSERT(*flags | HA_MRR_SINGLE_POINT);
 
+  *bufsz= 0; /* Default implementation doesn't need a buffer */
   *flags |= HA_MRR_USE_DEFAULT_IMPL;
 
   cost->zero();
@@ -276,6 +283,7 @@
   DBUG_RETURN(result);
 }
 
+
 /****************************************************************************
  * DS-MRR implementation 
  ***************************************************************************/
@@ -302,9 +310,9 @@
                            void *seq_init_param, uint n_ranges, uint mode,
                            HANDLER_BUFFER *buf)
 {
-  uint elem_size;
   Item *pushed_cond= NULL;
   handler *new_h2= 0;
+  THD *thd= current_thd;
   DBUG_ENTER("DsMrr_impl::dsmrr_init");
 
   /*
@@ -316,25 +324,75 @@
   {
     use_default_impl= TRUE;
     const int retval=
-      h->handler::multi_range_read_init(seq_funcs, seq_init_param,
-                                        n_ranges, mode, buf);
+      h->handler::multi_range_read_init(seq_funcs, seq_init_param, n_ranges, 
+                                        mode, buf);
     DBUG_RETURN(retval);
   }
-  rowids_buf= buf->buffer;
-
+  use_default_impl= FALSE;
   is_mrr_assoc= !test(mode & HA_MRR_NO_ASSOCIATION);
+  
+  /*
+    Determine whether we'll need to do key sorting and/or rnd_pos() scan
+  */
+  do_sort_keys= FALSE;
+  if ((mode & HA_MRR_SINGLE_POINT) && 
+       optimizer_flag(thd, OPTIMIZER_SWITCH_MRR_SORT_KEYS))
+  {
+    do_sort_keys= TRUE;
+    use_key_pointers= test(mode & HA_MRR_MATERIALIZED_KEYS);
+  }
 
+  do_rndpos_scan= FALSE;
+  bool doing_cpk_scan= check_cpk_scan(thd, h->inited == handler::INDEX? 
+                                      h->active_index: h2->active_index, mode);
+  if (!doing_cpk_scan /* && !index_only_read */)
+  {
+    /* Will use rowid buffer to store/sort rowids, etc */
+    do_rndpos_scan= TRUE;
+  }
+
+  /* 
+    We should either sort keys, or do ordered rnd_pos scan, or both. If we
+    decide to do neither, we should have used default MRR implementation.
+  */
+  DBUG_ASSERT(do_sort_keys || do_rndpos_scan);
+
+  
   if (is_mrr_assoc)
     status_var_increment(table->in_use->status_var.ha_multi_range_read_init_count);
- 
-  rowids_buf_end= buf->buffer_end;
-  elem_size= h->ref_length + (int)is_mrr_assoc * sizeof(void*);
-  rowids_buf_last= rowids_buf + 
-                      ((rowids_buf_end - rowids_buf)/ elem_size)*
-                      elem_size;
-  rowids_buf_end= rowids_buf_last;
 
-    /*
+  /* 
+    At start, alloc all of the buffer for rowids. When/if key sorting code
+    figures how much buffer space it needs, it will call setup_buffer_sizes()
+    to re-distribute the buffer space.
+  */
+  full_buf= buf->buffer;
+  full_buf_end= buf->buffer_end;
+  rowid_buffer.set_buffer_space(full_buf, full_buf_end);
+  
+  if (do_sort_keys)
+  {
+    know_key_tuple_params= FALSE;
+    h->mrr_iter= seq_funcs->init(seq_init_param, n_ranges, mode);
+    h->mrr_funcs= *seq_funcs;
+    keyno= (h->inited == handler::INDEX)? h->active_index : h2->active_index;
+    dsmrr_fill_key_buffer();
+    
+    if (dsmrr_eof && !do_rndpos_scan)
+      buf->end_of_used_area= key_buffer->end_of_space();
+  }
+
+  if (!do_rndpos_scan)
+  {
+    /* 
+      We have the keys and won't need to fetch rowids, as key lookup will be
+      the last operation, done in multi_range_read_next().
+    */
+    DBUG_RETURN(0);
+  }
+
+  rowid_buff_elem_size= h->ref_length + (is_mrr_assoc? sizeof(char*) : 0);
+  /*
     There can be two cases:
     - This is the first call since index_init(), h2==NULL
        Need to setup h2 then.
@@ -344,8 +402,7 @@
   */
   if (!h2)
   {
-    /* Create a separate handler object to do rndpos() calls. */
-    THD *thd= current_thd;
+    /* Create a separate handler object to do rnd_pos() calls. */
     /*
       ::clone() takes up a lot of stack, especially on 64 bit platforms.
       The constant 5 is an empiric result.
@@ -353,9 +410,9 @@
     if (check_stack_overrun(thd, 5*STACK_MIN_SIZE, (uchar*) &new_h2))
       DBUG_RETURN(1);
     DBUG_ASSERT(h->active_index != MAX_KEY);
-    uint mrr_keyno= h->active_index;
+    keyno= h->active_index;
 
-    /* Create a separate handler object to do rndpos() calls. */
+    /* Create a separate handler object to do rnd_pos() calls. */
     if (!(new_h2= h->clone(thd->mem_root)) || 
         new_h2->ha_external_lock(thd, F_RDLCK))
     {
@@ -363,7 +420,7 @@
       DBUG_RETURN(1);
     }
 
-    if (mrr_keyno == h->pushed_idx_cond_keyno)
+    if (keyno == h->pushed_idx_cond_keyno)
       pushed_cond= h->pushed_idx_cond;
 
     /*
@@ -376,16 +433,18 @@
       goto error;
     }
 
+    use_default_impl= FALSE;
     h2= new_h2; /* Ok, now can put it into h2 */
     table->prepare_for_position();
     h2->extra(HA_EXTRA_KEYREAD);
-  
-    if (h2->ha_index_init(mrr_keyno, FALSE))
+    h2->mrr_funcs= *seq_funcs; //psergey3-todo: sort out where to store
+    h2->mrr_iter= h->mrr_iter;
+
+    if (h2->ha_index_init(keyno, FALSE))
       goto error;
 
-    use_default_impl= FALSE;
     if (pushed_cond)
-      h2->idx_cond_push(mrr_keyno, pushed_cond);
+      h2->idx_cond_push(keyno, pushed_cond);
   }
   else
   {
@@ -405,10 +464,15 @@
     if (res)
       goto error;
   }
+  
+  if (!do_sort_keys && 
+      h2->handler::multi_range_read_init(seq_funcs, seq_init_param, n_ranges, 
+                                         mode, buf))
+  {
+    goto error;
+  }
 
-  if (h2->handler::multi_range_read_init(seq_funcs, seq_init_param, n_ranges,
-                                          mode, buf) || 
-      dsmrr_fill_buffer())
+  if (dsmrr_fill_rowid_buffer())
   {
     goto error;
   }
@@ -416,8 +480,8 @@
     If the above call has scanned through all intervals in *seq, then
     adjust *buf to indicate that the remaining buffer space will not be used.
   */
-  if (dsmrr_eof) 
-    buf->end_of_used_area= rowids_buf_last;
+//  if (dsmrr_eof) 
+//    buf->end_of_used_area= rowid_buffer.end_of_space();
 
   /*
      h->inited == INDEX may occur when 'range checked for each record' is
@@ -428,7 +492,6 @@
        (h->ha_rnd_init(FALSE))))
       goto error;
 
-  use_default_impl= FALSE;
   h->mrr_funcs= *seq_funcs;
   
   DBUG_RETURN(0);
@@ -458,123 +521,601 @@
 }
 
 
-static int rowid_cmp(void *h, uchar *a, uchar *b)
+static int rowid_cmp_reverse(void *h, uchar *a, uchar *b)
 {
-  return ((handler*)h)->cmp_ref(a, b);
+  return - ((handler*)h)->cmp_ref(a, b);
 }
 
 
 /**
-  DS-MRR: Fill the buffer with rowids and sort it by rowid
+  DS-MRR: Fill and sort the rowid buffer
 
-  {This is an internal function of DiskSweep MRR implementation}
   Scan the MRR ranges and collect ROWIDs (or {ROWID, range_id} pairs) into 
   buffer. When the buffer is full or scan is completed, sort the buffer by 
   rowid and return.
+
+  When this function returns, either rowid buffer is not empty, or the source
+  of lookup keys (i.e. ranges) is exhaused.
   
-  The function assumes that rowids buffer is empty when it is invoked. 
-  
-  @param h  Table handler
+  dsmrr_eof is set to indicate whether we've exhausted the list of ranges we're
+  scanning. This function never returns HA_ERR_END_OF_FILE.
 
   @retval 0      OK, the next portion of rowids is in the buffer,
                  properly ordered
   @retval other  Error
 */
 
-int DsMrr_impl::dsmrr_fill_buffer()
+int DsMrr_impl::dsmrr_fill_rowid_buffer()
 {
   char *range_info;
+  uchar **range_info_ptr= (uchar**)&range_info;
   int res;
-  DBUG_ENTER("DsMrr_impl::dsmrr_fill_buffer");
+  DBUG_ENTER("DsMrr_impl::dsmrr_fill_rowid_buffer");
+  
+  DBUG_ASSERT(rowid_buffer.is_empty());
+  rowid_buffer.reset();
+  rowid_buffer.setup_writing(&h2->ref, h2->ref_length,
+                             is_mrr_assoc? (uchar**)&range_info_ptr: NULL,
+                             sizeof(void*));
+
+  last_identical_rowid= NULL;
+
+  while (rowid_buffer.can_write())
+  {
+    if (do_sort_keys)
+      res= dsmrr_next_from_index(&range_info);
+    else 
+      res= h2->handler::multi_range_read_next(&range_info);
+
+    if (res)
+      break;
 
-  rowids_buf_cur= rowids_buf;
-  while ((rowids_buf_cur < rowids_buf_end) && 
-         !(res= h2->handler::multi_range_read_next(&range_info)))
-  {
     KEY_MULTI_RANGE *curr_range= &h2->handler::mrr_cur_range;
-    if (h2->mrr_funcs.skip_index_tuple &&
+    if (!do_sort_keys && /* If keys are sorted then this check is already done */
+        h2->mrr_funcs.skip_index_tuple &&
         h2->mrr_funcs.skip_index_tuple(h2->mrr_iter, curr_range->ptr))
       continue;
-    
+
     /* Put rowid, or {rowid, range_id} pair into the buffer */
     h2->position(table->record[0]);
-    memcpy(rowids_buf_cur, h2->ref, h2->ref_length);
-    rowids_buf_cur += h2->ref_length;
 
-    if (is_mrr_assoc)
-    {
-      memcpy(rowids_buf_cur, &range_info, sizeof(void*));
-      rowids_buf_cur += sizeof(void*);
-    }
+    rowid_buffer.write();
   }
 
   if (res && res != HA_ERR_END_OF_FILE)
     DBUG_RETURN(res); 
-  dsmrr_eof= test(res == HA_ERR_END_OF_FILE);
+
+  if (!do_sort_keys)
+    dsmrr_eof= test(res == HA_ERR_END_OF_FILE);
 
   /* Sort the buffer contents by rowid */
-  uint elem_size= h->ref_length + (int)is_mrr_assoc * sizeof(void*);
-  uint n_rowids= (rowids_buf_cur - rowids_buf) / elem_size;
+  rowid_buffer.sort((qsort2_cmp)rowid_cmp_reverse, (void*)h);
+
+  rowid_buffer.setup_reading(&rowid, h->ref_length,
+                             is_mrr_assoc? (uchar**)&rowids_range_id: NULL, sizeof(void*));
+  DBUG_RETURN(0);
+}
+
+
+/* 
+  my_qsort2-compatible function to compare key tuples 
+*/
+
+int DsMrr_impl::key_tuple_cmp(void* arg, uchar* key1, uchar* key2)
+{
+  DsMrr_impl *dsmrr= (DsMrr_impl*)arg;
+  TABLE *table= dsmrr->h->table;
+  int res;
+  KEY_PART_INFO *part= table->key_info[dsmrr->keyno].key_part;
+  
+  if (dsmrr->use_key_pointers)
+  {
+    /* the buffer stores pointers to keys, get to the keys */
+    key1= *((uchar**)key1);
+    key2= *((uchar**)key2);  // todo is this alignment-safe?
+  }
+
+  uchar *key1_end= key1 + dsmrr->key_tuple_length;
+
+  while (key1 < key1_end)
+  {
+    Field* f = part->field;
+    int len = part->store_length;
+    if (part->null_bit)
+    {
+      if (*key1) // key1 == NULL
+      {
+        if (!*key2) // key1(NULL) < key2(notNULL)
+          return -1;
+        goto equals;
+      }
+      else if (*key2) // key1(notNULL) > key2 (NULL)
+        return 1;
+      // Step over NULL byte for f->cmp().
+      key1++;
+      key2++;
+      len--;
+    }
+    
+    if ((res= f->key_cmp(key1, key2)))
+      return res;
+equals:
+    key1 += len;
+    key2 += len;
+    part++;
+  }
+  return 0;
+}
+
+
+int DsMrr_impl::key_tuple_cmp_reverse(void* arg, uchar* key1, uchar* key2)
+{
+  return -key_tuple_cmp(arg, key1, key2);
+}
+
+
+/**
+  Setup key/rowid buffer sizes based on sample_key and its length.
+  
+  @param
+    sample_key  A lookup key to use as a sample. It is assumed that
+                all other keys will have the same length/etc.
+  @note
+    This function must be called when all buffers are empty
+*/
+
+void DsMrr_impl::setup_buffer_sizes(key_range *sample_key)
+{
+  key_tuple_length= sample_key->length;
+  key_tuple_map= sample_key->keypart_map;
+  key_size_in_keybuf= use_key_pointers ? sizeof(char*) : 
+                                       key_tuple_length;
+  key_buff_elem_size= key_size_in_keybuf + 
+                      (int)is_mrr_assoc * sizeof(void*);
+  
+  KEY *key_info= &h->table->key_info[keyno];
+  index_ranges_unique= test(key_info->flags & HA_NOSAME && 
+                            key_info->key_parts == 
+                              my_count_bits(sample_key->keypart_map));
+  if (!do_rndpos_scan)
+  {
+    /* Give all space to forward key buffer. */
+    key_buffer= &forward_key_buf;
+    //identical_key_it= &forward_key_it;
+    key_buffer->set_buffer_space(full_buf, full_buf_end);
+
+    /* Just in case, tell rowid buffer that it has zero size: */
+    rowid_buffer.set_buffer_space(full_buf_end, full_buf_end);
+    return;
+  }
+  
+  /* 
+    Ok if we got here we need to allocate one part of the buffer 
+    for keys and another part for rowids.
+  */
+  uint rowid_buf_elem_size= h->ref_length + 
+                            (int)is_mrr_assoc * sizeof(char*);
+  
+  /*
+    Use rec_per_key statistics as a basis to find out how many rowids 
+    we'll get for each key value.
+     TODO: are we guaranteed to get r_p_c==1 for unique keys?
+     TODO: what should be the default value to use when there is no 
+           statistics?
+  */
+  uint parts= my_count_bits(key_tuple_map);
+  ulong rpc;
+  if ((rpc= key_info->rec_per_key[parts - 1]))
+  {
+    rowid_buf_elem_size *= rpc;
+  }
+
+  double fraction_for_rowids=
+    ((double) rowid_buf_elem_size / 
+         ((double)rowid_buf_elem_size + key_buff_elem_size));
+
+  size_t bytes_for_rowids= 
+    round(fraction_for_rowids * (full_buf_end - full_buf));
+  
+  uint bytes_for_keys= (full_buf_end - full_buf) - bytes_for_rowids;
+
+  if (bytes_for_keys < key_buff_elem_size + 1)
+  {
+    uint add= key_buff_elem_size + 1 - bytes_for_keys;
+    bytes_for_rowids -= add;
+    DBUG_ASSERT(bytes_for_rowids >= 
+                (h->ref_length + (int)is_mrr_assoc * sizeof(char*) + 1));
+  }
+
+  rowid_buffer_end= full_buf + bytes_for_rowids;
+  rowid_buffer.set_buffer_space(full_buf, rowid_buffer_end);
+  key_buffer= &backward_key_buf;
+  //identical_key_it= &backward_key_it;
+  key_buffer->set_buffer_space(rowid_buffer_end, full_buf_end); 
+}
+
+
+/**
+  DS-MRR/CPK: Fill the buffer with (lookup_tuple, range_id) pairs and sort
+  
+  Enumerate the input range (=key) sequence, fill the key buffer with 
+  (lookup_key, range_id) pairs and sort it.
+
+  When this function returns, either
+   - key buffer is non-empty, or
+   - key buffer is empty and source range sequence is exhausted
+  
+  @note
+    dsmrr_eof is set to indicate whether we've exhausted the list of ranges 
+    we're scanning.
+*/
+
+void DsMrr_impl::dsmrr_fill_key_buffer()
+{
+  int res;
+  KEY_MULTI_RANGE cur_range;
+  uchar **range_info_ptr= (uchar**)&cur_range.ptr;
+  DBUG_ENTER("DsMrr_impl::dsmrr_fill_key_buffer");
+
+  DBUG_ASSERT(!know_key_tuple_params || key_buffer->is_empty());
+
+  uchar *key_ptr;
+  if (know_key_tuple_params)
+  {
+    if (do_rndpos_scan && rowid_buffer.is_empty())
+    {
+      /*
+        We're using two buffers and both of them are empty now. Restore the
+        original sizes
+      */
+      rowid_buffer.set_buffer_space(full_buf, rowid_buffer_end);
+      key_buffer= &backward_key_buf;
+      key_buffer->set_buffer_space(rowid_buffer_end, full_buf_end);
+    }
+    key_buffer->reset();
+    key_buffer->setup_writing(&key_ptr, key_size_in_keybuf,
+                              is_mrr_assoc? (uchar**)&range_info_ptr : NULL,
+                              sizeof(uchar*));
+  }
+
+  while ((!know_key_tuple_params || key_buffer->can_write()) && 
+         !(res= h->mrr_funcs.next(h->mrr_iter, &cur_range)))
+  {
+    DBUG_ASSERT(cur_range.range_flag & EQ_RANGE);
+    if (!know_key_tuple_params)
+    {
+      /* This only happens when we've just started filling the buffer */
+      setup_buffer_sizes(&cur_range.start_key);
+      know_key_tuple_params= TRUE;
+      key_buffer->setup_writing(&key_ptr, key_size_in_keybuf,
+                               is_mrr_assoc? (uchar**)&range_info_ptr : NULL,
+                               sizeof(uchar*));
+      DBUG_ASSERT(key_buffer->can_write());
+    }
+    
+    /* Put key, or {key, range_id} pair into the buffer */
+    if (use_key_pointers)
+      key_ptr=(uchar*) &cur_range.start_key.key;
+    else
+      key_ptr=(uchar*) cur_range.start_key.key;
+
+    key_buffer->write();
+  }
+
+  dsmrr_eof= test(res);
+
+  key_buffer->sort((key_buffer->type() == Lifo_buffer::FORWARD)? 
+                     (qsort2_cmp)DsMrr_impl::key_tuple_cmp_reverse : 
+                     (qsort2_cmp)DsMrr_impl::key_tuple_cmp, 
+                   (void*)this);
+  
+  key_buffer->setup_reading(&cur_index_tuple, key_size_in_keybuf,
+                            is_mrr_assoc? (uchar**)&cur_range_info: NULL,
+                            sizeof(void*));
+
+  scanning_key_val_iter= FALSE;
+  index_scan_eof= FALSE; 
+
+  DBUG_VOID_RETURN;
+}
+
+
+/**
+  Take unused space from the key buffer and give it to the rowid buffer
+*/
+
+void DsMrr_impl::reallocate_buffer_space()
+{
+  uchar *unused_start, *unused_end;
+  key_buffer->remove_unused_space(&unused_start, &unused_end);
+  rowid_buffer.grow(unused_start, unused_end);
+}
+
+
+//////////////////////////////////////////////////////////////////////////////
+//////////////////////////////////////////////////////////////////////////////
+bool Key_value_records_iterator::init(DsMrr_impl *dsmrr_arg)
+{
+  int res;
+  dsmrr= dsmrr_arg;
+  handler *file= dsmrr->do_rndpos_scan? dsmrr->h2 : dsmrr->h;
+
+  identical_key_it.init(dsmrr->key_buffer);
+  /* Get the first pair into (cur_index_tuple, cur_range_info) */ 
+  if (identical_key_it.read())
+    return TRUE;
+
+  uchar *key_in_buf= dsmrr->cur_index_tuple;
+
+  last_identical_key_ptr= dsmrr->cur_index_tuple;
+  if (dsmrr->use_key_pointers)
+    dsmrr->cur_index_tuple= *((uchar**)dsmrr->cur_index_tuple);
+  
+  /* Check out how many more identical keys are following */
+  uchar *save_cur_index_tuple= dsmrr->cur_index_tuple;
+  while (!identical_key_it.read())
+  {
+    if (DsMrr_impl::key_tuple_cmp(dsmrr, key_in_buf, dsmrr->cur_index_tuple))
+      break;
+    last_identical_key_ptr= dsmrr->cur_index_tuple;
+  }
+  identical_key_it.init(dsmrr->key_buffer);
+  dsmrr->cur_index_tuple= save_cur_index_tuple;
+  res= file->ha_index_read_map(dsmrr->table->record[0], 
+                               dsmrr->cur_index_tuple, 
+                               dsmrr->key_tuple_map, 
+                               HA_READ_KEY_EXACT);
+
+  if (res)
+  {
+    close();
+    return res; /* Fatal error */
+  }
+  get_next_row= FALSE;
+  return 0;
+}
+
+
+int Key_value_records_iterator::get_next()
+{
+  handler *file= dsmrr->do_rndpos_scan? dsmrr->h2 : dsmrr->h;
+  int res;
+
+  if (get_next_row)
+  {
+    if (dsmrr->index_ranges_unique)
+      return HA_ERR_END_OF_FILE;  /* Max one match */
+
+    if ((res= file->ha_index_next_same(dsmrr->table->record[0], 
+                                       dsmrr->cur_index_tuple, 
+                                       dsmrr->key_tuple_length)))
+    {
+      /* EOF is EOF for iterator, also, any error means EOF on the iterator */
+      return res;
+    }
+    identical_key_it.init(dsmrr->key_buffer);
+    get_next_row= FALSE;
+  }
+
+  identical_key_it.read(); // This gets us next range_id.
+  if (!last_identical_key_ptr || (dsmrr->cur_index_tuple == last_identical_key_ptr))
+  {
+    get_next_row= TRUE;
+  }
+  return 0;
+}
+
+void Key_value_records_iterator::close()
+{
+  while (!dsmrr->key_buffer->read() && 
+         (dsmrr->cur_index_tuple != last_identical_key_ptr)) {}
+}
+
+
+/**
+  DS-MRR/CPK: multi_range_read_next() function
   
-  my_qsort2(rowids_buf, n_rowids, elem_size, (qsort2_cmp)rowid_cmp,
-            (void*)h);
-  rowids_buf_last= rowids_buf_cur;
-  rowids_buf_cur=  rowids_buf;
+  @param range_info  OUT  identifier of range that the returned record belongs to
+  
+  @note
+    This function walks over key buffer and does index reads, i.e. it produces
+    {current_record, range_id} pairs.
+
+    The function has the same call contract like multi_range_read_next()'s.
+
+    We actually iterate over nested sequences:
+    - a disjoint sequence of index ranges
+      - each range has multiple records
+        - each record goes into multiple identical ranges.
+
+  @retval 0                   OK, next record was successfully read
+  @retval HA_ERR_END_OF_FILE  End of records
+  @retval Other               Some other error
+*/
+
+int DsMrr_impl::dsmrr_next_from_index(char **range_info_arg)
+{
+  DBUG_ENTER("DsMrr_impl::dsmrr_next_from_index");
+
+  while (1)
+  {
+    bool have_record= FALSE;
+    if (scanning_key_val_iter)
+    {
+      if (kv_it.get_next())
+      {
+        kv_it.close();
+        scanning_key_val_iter= FALSE;
+      }
+      else
+        have_record= TRUE;
+    }
+    else
+    {
+      while (kv_it.init(this))
+      {
+        if (key_buffer->is_empty())
+        {
+          if (dsmrr_eof)
+          {
+            index_scan_eof= TRUE;
+            DBUG_RETURN(HA_ERR_END_OF_FILE);
+          }
+
+          /*
+            When rowid fetching is used, it controls all buffer refills. When we're
+            on our own, try refilling our buffer.
+          */
+          if (!do_rndpos_scan)
+            dsmrr_fill_key_buffer();
+
+          if (key_buffer->is_empty())
+          {
+            index_scan_eof= TRUE;
+            DBUG_RETURN(HA_ERR_END_OF_FILE);
+          }
+        }
+      }
+      scanning_key_val_iter= TRUE;
+    }
+
+    if (have_record &&
+        (!h->mrr_funcs.skip_index_tuple ||
+         !h->mrr_funcs.skip_index_tuple(h->mrr_iter, *(char**)cur_range_info)) 
+        && 
+        (!h->mrr_funcs.skip_record ||
+         !h->mrr_funcs.skip_record(h->mrr_iter, *(char**)cur_range_info, NULL)))
+    {
+      break;
+    }
+    /* Go get another (record, range_id) combination */
+  } /* while */
+
+  memcpy(range_info_arg, cur_range_info, sizeof(void*));
   DBUG_RETURN(0);
 }
 
 
 /**
-  DS-MRR implementation: multi_range_read_next() function
+  DS-MRR implementation: multi_range_read_next() function.
+
+  Calling convention is like multi_range_read_next() has.
 */
 
 int DsMrr_impl::dsmrr_next(char **range_info)
 {
   int res;
-  uchar *cur_range_info= 0;
-  uchar *rowid;
 
   if (use_default_impl)
     return h->handler::multi_range_read_next(range_info);
+
+  if (!do_rndpos_scan)
+    return dsmrr_next_from_index(range_info);
   
-  do
+  while (last_identical_rowid)
   {
-    if (rowids_buf_cur == rowids_buf_last)
+    /*
+      Current record (the one we've returned in previous call) was obtained
+      from a rowid that matched multiple range_ids. Return this record again,
+      with next matching range_id.
+    */
+    bool bres= rowid_buffer.read();
+    DBUG_ASSERT(!bres);
+
+    if (is_mrr_assoc)
+      memcpy(range_info, rowids_range_id, sizeof(uchar*));
+
+    if (rowid == last_identical_rowid)
+    {
+      last_identical_rowid= NULL; /* reached the last of identical rowids */
+    }
+
+    if (!h2->mrr_funcs.skip_record ||
+        !h2->mrr_funcs.skip_record(h2->mrr_iter, (char *) *range_info, rowid))
+    {
+      return 0;
+    }
+  }
+
+  while (1)
+  {
+    if (rowid_buffer.is_empty())
     {
-      if (dsmrr_eof)
+      if (do_sort_keys)
+      {
+        if (!index_scan_eof) 
+        {
+          /* There are some sorted keys left. Use them to get rowids */
+          if ((res= dsmrr_fill_rowid_buffer()))
+            return res; /* for fatal errors */
+        }
+        while (rowid_buffer.is_empty())
+        {
+          if (dsmrr_eof)
+            return HA_ERR_END_OF_FILE;
+          dsmrr_fill_key_buffer();
+          if ((res= dsmrr_fill_rowid_buffer()))
+            return res;
+        }
+      }
+      else
       {
-        res= HA_ERR_END_OF_FILE;
-        goto end;
+        /* 
+          There is no buffer with sorted keys. If fill_rowid_buffer() haven't
+          reached eof condition before, try refilling the buffer.
+        */
+        if (dsmrr_eof)
+          return HA_ERR_END_OF_FILE;
+
+        if ((res= dsmrr_fill_rowid_buffer()))
+          return res;
       }
-      res= dsmrr_fill_buffer();
-      if (res)
-        goto end;
     }
    
-    /* return eof if there are no rowids in the buffer after re-fill attempt */
-    if (rowids_buf_cur == rowids_buf_last)
-    {
-      res= HA_ERR_END_OF_FILE;
-      goto end;
-    }
-    rowid= rowids_buf_cur;
+    last_identical_rowid= NULL;
+
+    /* Return eof if there are no rowids in the buffer after re-fill attempt */
+    if (rowid_buffer.read())
+      return HA_ERR_END_OF_FILE;
 
     if (is_mrr_assoc)
-      memcpy(&cur_range_info, rowids_buf_cur + h->ref_length, sizeof(uchar**));
+    {
+      memcpy(range_info, rowids_range_id, sizeof(uchar*));
+    }
 
-    rowids_buf_cur += h->ref_length + sizeof(void*) * test(is_mrr_assoc);
     if (h2->mrr_funcs.skip_record &&
-	h2->mrr_funcs.skip_record(h2->mrr_iter, (char *) cur_range_info, rowid))
+	h2->mrr_funcs.skip_record(h2->mrr_iter, *range_info, rowid))
       continue;
+
     res= h->ha_rnd_pos(table->record[0], rowid);
-    break;
-  } while (true);
- 
-  if (is_mrr_assoc)
-  {
-    memcpy(range_info, rowid + h->ref_length, sizeof(void*));
+
+    if (res == HA_ERR_RECORD_DELETED)
+      continue;
+    
+    /* 
+      Check if subsequent buffer elements have the same rowid value as this
+      one. If yes, remember this fact so that we don't make any more rnd_pos()
+      calls with this value.
+    */
+    if (!res)
+    {
+      uchar *cur_rowid= rowid;
+      /* 
+        Note: this implies that SQL layer doesn't touch table->record[0]
+        between calls.
+      */
+      Lifo_buffer_iterator it;
+      it.init(&rowid_buffer);
+      while (!it.read()) // reads to (rowid, ...)
+      {
+        if (h2->cmp_ref(rowid, cur_rowid))
+          break;
+        last_identical_rowid= rowid;
+      }
+    }
+    return 0;
   }
-end:
+
   return res;
 }
 
@@ -582,7 +1123,8 @@
 /**
   DS-MRR implementation: multi_range_read_info() function
 */
-ha_rows DsMrr_impl::dsmrr_info(uint keyno, uint n_ranges, uint rows,
+ha_rows DsMrr_impl::dsmrr_info(uint keyno, uint n_ranges, uint rows, 
+                               uint key_parts,
                                uint *bufsz, uint *flags, COST_VECT *cost)
 {  
   ha_rows res;
@@ -590,8 +1132,8 @@
   uint def_bufsz= *bufsz;
 
   /* Get cost/flags/mem_usage of default MRR implementation */
-  res= h->handler::multi_range_read_info(keyno, n_ranges, rows, &def_bufsz,
-                                         &def_flags, cost);
+  res= h->handler::multi_range_read_info(keyno, n_ranges, rows, key_parts, 
+                                         &def_bufsz, &def_flags, cost);
   DBUG_ASSERT(!res);
 
   if ((*flags & HA_MRR_USE_DEFAULT_IMPL) || 
@@ -683,7 +1225,29 @@
   return FALSE;
 }
 
-/**
+
+/*
+  Check if key/flags allow DS-MRR/CPK strategy to be used
+  
+  @param thd
+  @param keyno      Index that will be used
+  @param  mrr_flags  
+  
+  @retval TRUE   DS-MRR/CPK should be used
+  @retval FALSE  Otherwise
+*/
+
+bool DsMrr_impl::check_cpk_scan(THD *thd, uint keyno, uint mrr_flags)
+{
+  return test((mrr_flags & HA_MRR_SINGLE_POINT) && 
+              !(mrr_flags & HA_MRR_SORTED) && 
+              keyno == table->s->primary_key && 
+              h->primary_key_is_clustered() && 
+              optimizer_flag(thd, OPTIMIZER_SWITCH_MRR_SORT_KEYS));
+}
+
+
+/*
   DS-MRR Internals: Choose between Default MRR implementation and DS-MRR
 
   Make the choice between using Default MRR implementation and DS-MRR.
@@ -706,21 +1270,25 @@
   @retval FALSE  DS-MRR implementation should be used
 */
 
+
 bool DsMrr_impl::choose_mrr_impl(uint keyno, ha_rows rows, uint *flags,
                                  uint *bufsz, COST_VECT *cost)
 {
   COST_VECT dsmrr_cost;
   bool res;
   THD *thd= current_thd;
+
+  bool doing_cpk_scan= check_cpk_scan(thd, keyno, *flags); 
+  bool using_cpk= test(keyno == table->s->primary_key &&
+                       h->primary_key_is_clustered());
   if (thd->variables.optimizer_use_mrr == 2 || *flags & HA_MRR_INDEX_ONLY ||
-      (keyno == table->s->primary_key && h->primary_key_is_clustered()) ||
-       key_uses_partial_cols(table, keyno))
+      (using_cpk && !doing_cpk_scan) || key_uses_partial_cols(table, keyno))
   {
     /* Use the default implementation */
     *flags |= HA_MRR_USE_DEFAULT_IMPL;
     return TRUE;
   }
-  
+
   uint add_len= table->key_info[keyno].key_length + h->ref_length; 
   *bufsz -= add_len;
   if (get_disk_sweep_mrr_cost(keyno, rows, *flags, bufsz, &dsmrr_cost))
@@ -744,6 +1312,10 @@
     *flags &= ~HA_MRR_SORTED;          /* We will return unordered output */
     *cost= dsmrr_cost;
     res= FALSE;
+
+    if ((*flags & HA_MRR_SINGLE_POINT) && 
+         optimizer_flag(thd, OPTIMIZER_SWITCH_MRR_SORT_KEYS))
+      *flags |= HA_MRR_MATERIALIZED_KEYS;
   }
   else
   {
@@ -828,17 +1400,14 @@
 
 /* 
   Get cost of one sort-and-sweep step
-
-  SYNOPSIS
-    get_sort_and_sweep_cost()
-      table       Table being accessed
-      nrows       Number of rows to be sorted and retrieved
-      cost   OUT  The cost
-
-  DESCRIPTION
-    Get cost of these operations:
-     - sort an array of #nrows ROWIDs using qsort
-     - read #nrows records from table in a sweep.
+  
+  It consists of two parts:
+   - sort an array of #nrows ROWIDs using qsort
+   - read #nrows records from table in a sweep.
+
+  @param table       Table being accessed
+  @param nrows       Number of rows to be sorted and retrieved
+  @param cost   OUT  The cost of scan
 */
 
 static 
diff -urN --exclude='.*' 5.3-noc/sql/multi_range_read.h maria-5.3-dsmrr-cpk-r5-noc/sql/multi_range_read.h
--- 5.3-noc/sql/multi_range_read.h	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/multi_range_read.h	2010-10-04 10:48:03.000000000 +0400
@@ -1,49 +1,169 @@
-/*
-  This file contains declarations for 
-   - Disk-Sweep MultiRangeRead (DS-MRR) implementation
+/**
+  @defgroup DS-MRR declarations
+  @{
 */
 
 /**
-  A Disk-Sweep MRR interface implementation
+  A Disk-Sweep implementation of MRR Interface (DS-MRR for short)
+
+  This is a "plugin"(*) for storage engines that allows to
+    1. When doing index scans, read table rows in rowid order;
+    2. when making many index lookups, do them in key order and don't
+       lookup the same key value multiple times;
+    3. Do both #1 and #2, when applicable.
+  These changes are expected to speed up query execution for disk-based 
+  storage engines running io-bound loads and "big" queries (ie. queries that
+  do joins and enumerate lots of records).
+
+  (*) - only conceptually. No dynamic loading or binary compatibility of any
+        kind.
+
+  General scheme of things:
+   
+      SQL Layer code
+       |   |   |
+       v   v   v 
+      -|---|---|---- handler->multi_range_read_XXX() function calls
+       |   |   |
+      _____________________________________
+     / DS-MRR module                       \
+     | (order/de-duplicate lookup keys,    |
+     | scan indexes in key order,          |
+     | order/de-duplicate rowids,          |
+     | retrieve full record reads in rowid |
+     | order)                              |
+     \_____________________________________/
+       |   |   |
+      -|---|---|----- handler->read_range_first()/read_range_next(), 
+       |   |   |      handler->index_read(), handler->rnd_pos() calls.
+       |   |   |
+       v   v   v
+      Storage engine internals
+
+
+  Currently DS-MRR is used by MyISAM, InnoDB/XtraDB and Maria storage engines.
+  Potentially it can be used with any table handler that has disk-based data
+  storage and has better performance when reading data in rowid order.
+*/
+
+#include "sql_lifo_buffer.h"
 
-  This implementation makes range (and, in the future, 'ref') scans to read
-  table rows in disk sweeps. 
+class DsMrr_impl;
+
+/**
+  Iterator over (record, range_id) pairs that match given key value.
   
-  Currently it is used by MyISAM and InnoDB. Potentially it can be used with
-  any table handler that has non-clustered indexes and on-disk rows.
+  We may need to scan multiple (key_val, range_id) pairs with the same 
+  key value. A key value may have multiple matching records, so we'll need to
+  produce a cross-product of sets of matching records and range_id-s.
 */
 
-class DsMrr_impl
+class Key_value_records_iterator
 {
+  /* Scan parameters */
+  DsMrr_impl *dsmrr;
+  Lifo_buffer_iterator identical_key_it;
+  uchar *last_identical_key_ptr;
+  bool get_next_row;
 public:
-  typedef void (handler::*range_check_toggle_func_t)(bool on);
+  bool init(DsMrr_impl *dsmrr);
 
-  DsMrr_impl()
-    : h2(NULL) {};
-  
   /*
-    The "owner" handler object (the one that calls dsmrr_XXX functions.
-    It is used to retrieve full table rows by calling rnd_pos().
+    Get next (key_val, range_id) pair.
   */
-  handler *h;
-  TABLE *table; /* Always equal to h->table */
-private:
-  /* Secondary handler object.  It is used for scanning the index */
-  handler *h2;
+  int get_next();
 
-  /* Buffer to store rowids, or (rowid, range_id) pairs */
-  uchar *rowids_buf;
-  uchar *rowids_buf_cur;   /* Current position when reading/writing */
-  uchar *rowids_buf_last;  /* When reading: end of used buffer space */
-  uchar *rowids_buf_end;   /* End of the buffer */
+  void close();
+};
 
-  bool dsmrr_eof; /* TRUE <=> We have reached EOF when reading index tuples */
 
-  /* TRUE <=> need range association, buffer holds {rowid, range_id} pairs */
-  bool is_mrr_assoc;
+/*
+  DS-MRR implementation for one table. Create/use one object of this class for
+  each ha_{myisam/innobase/etc} object. That object will be further referred to
+  as "the handler"
+
+  DsMrr_impl supports has the following execution strategies:
+
+  - Bypass DS-MRR, pass all calls to default MRR implementation, which is 
+    an MRR-to-non-MRR call converter.
+  - Key-Ordered Retrieval
+  - Rowid-Ordered Retrieval
+
+  DsMrr_impl will use one of the above strategies, or a combination of them, 
+  according to the following diagram:
+
+         (mrr function calls)
+                |
+                +----------------->-----------------+
+                |                                   |
+     ___________v______________      _______________v________________
+    / default: use lookup keys \    / KEY-ORDERED RETRIEVAL:         \
+    | (or ranges) in whatever  |    | sort lookup keys and then make | 
+    | order they are supplied  |    | index lookups in index order   |
+    \__________________________/    \________________________________/
+              | |  |                           |    |
+      +---<---+ |  +--------------->-----------|----+
+      |         |                              |    |
+      |         |              +---------------+    |
+      |   ______v___ ______    |     _______________v_______________
+      |  / default: read   \   |    / ROWID-ORDERED RETRIEVAL:      \
+      |  | table records   |   |    | Before reading table records, |
+      v  | in random order |   v    | sort their rowids and then    |
+      |  \_________________/   |    | read them in rowid order      |
+      |         |              |    \_______________________________/
+      |         |              |                    |
+      |         |              |                    |
+      +-->---+  |  +----<------+-----------<--------+
+             |  |  |                                
+             v  v  v
+      (table records and range_ids)
+
+  The choice of strategy depends on MRR scan properties, table properties
+  (whether we're scanning clustered primary key), and @@optimizer_switch
+  settings.
+  
+  Key-Ordered Retrieval
+  ---------------------
+  The idea is: if MRR scan is essentially a series of lookups on 
+   
+    tbl.key=value1 OR tbl.key=value2 OR ... OR tbl.key=valueN
+  
+  then it makes sense to collect and order the set of lookup values, i.e.
+   
+     sort(value1, value2, .. valueN)
+
+  and then do index lookups in index order. This results in fewer index page
+  fetch operations, and we also can avoid making multiple index lookups for the
+  same value. That is, if value1=valueN we can easily discover that after
+  sorting and make one index lookup for them instead of two.
+
+  Rowid-Ordered Retrieval
+  -----------------------
+  If we do a regular index scan or a series of index lookups, we'll be hitting
+  table records at random. For disk-based engines, this is much slower than 
+  reading the same records in disk order. We assume that disk ordering of
+  rows is the same as ordering of their rowids (which is provided by 
+  handler::cmp_ref())
+  In order to retrieve records in different order, we must separate index
+  scanning and record fetching, that is, MRR scan uses the following steps:
+
+    1. Scan the index (and only index, that is, with HA_EXTRA_KEYREAD on) and 
+        fill a buffer with {rowid, range_id} pairs
+    2. Sort the buffer by rowid value
+    3. for each {rowid, range_id} pair in the buffer
+         get record by rowid and return the {record, range_id} pair
+    4. Repeat the above steps until we've exhausted the list of ranges we're
+       scanning.
+*/
 
-  bool use_default_impl; /* TRUE <=> shortcut all calls to default MRR impl */
+class DsMrr_impl
+{
 public:
+  typedef void (handler::*range_check_toggle_func_t)(bool on);
+
+  DsMrr_impl()
+    : h2(NULL) {};
+  
   void init(handler *h_arg, TABLE *table_arg)
   {
     h= h_arg; 
@@ -52,19 +172,147 @@
   int dsmrr_init(handler *h, RANGE_SEQ_IF *seq_funcs, void *seq_init_param, 
                  uint n_ranges, uint mode, HANDLER_BUFFER *buf);
   void dsmrr_close();
-  int dsmrr_fill_buffer();
   int dsmrr_next(char **range_info);
 
-  ha_rows dsmrr_info(uint keyno, uint n_ranges, uint keys, uint *bufsz,
-                     uint *flags, COST_VECT *cost);
+  ha_rows dsmrr_info(uint keyno, uint n_ranges, uint keys, uint key_parts, 
+                     uint *bufsz, uint *flags, COST_VECT *cost);
 
   ha_rows dsmrr_info_const(uint keyno, RANGE_SEQ_IF *seq, 
                             void *seq_init_param, uint n_ranges, uint *bufsz,
                             uint *flags, COST_VECT *cost);
 private:
+  /*
+    The "owner" handler object (the one that is expected to "own" this object
+    and call its functions).
+  */
+  handler *h;
+  TABLE *table; /* Always equal to h->table */
+
+  /*
+    Secondary handler object. (created when needed, we need it when we need 
+    to run both index scan and rnd_pos() scan at the same time)
+  */
+  handler *h2;
+  
+  /** Properties of current MRR scan **/
+
+  uint keyno; /* index we're running the scan on */
+  bool use_default_impl; /* TRUE <=> shortcut all calls to default MRR impl */
+  /* TRUE <=> need range association, buffers hold {rowid, range_id} pairs */
+  bool is_mrr_assoc;
+  /* TRUE <=> sort the keys before making index lookups */
+  bool do_sort_keys;
+  /* TRUE <=> sort rowids and use rnd_pos() to get and return full records */
+  bool do_rndpos_scan;
+
+  /*
+    (if do_sort_keys==TRUE) don't copy key values, use pointers to them 
+    instead.
+  */
+  bool use_key_pointers;
+
+
+  /* The whole buffer space that we're using */
+  uchar *full_buf;
+  uchar *full_buf_end;
+  
+  /* 
+    When using both rowid and key buffers: the boundary between key and rowid
+    parts of the buffer. This is the "original" value, actual memory ranges 
+    used by key and rowid parts may be different because of dynamic space 
+    reallocation between them.
+  */
+  uchar *rowid_buffer_end;
+ 
+  /** Index scaning and key buffer-related members **/
+
+  /* TRUE <=> We can get at most one index tuple for a lookup key */
+  bool index_ranges_unique;
+
+  /* TRUE<=> we're in a middle of enumerating records for a key range */
+  //bool in_index_range;
+  
+  /*
+    One of the following two is used for key buffer: forward is used when 
+    we only need key buffer, backward is used when we need both key and rowid
+    buffers.
+  */
+  Forward_lifo_buffer forward_key_buf;
+  Backward_lifo_buffer backward_key_buf;
+
+  /* Buffer to store (key, range_id) pairs */
+  Lifo_buffer *key_buffer;
+  
+  /* Index scan state */
+  bool scanning_key_val_iter;
+  /* 
+    TRUE <=> we've got index tuples/rowids for all keys (need this flag because 
+    we may have a situation where we've read everything from the key buffer but 
+    haven't finished with getting index tuples for the last key)
+  */
+  bool index_scan_eof;  
+  Key_value_records_iterator kv_it;
+  
+  /* key_buffer.read() reads to here */
+  uchar *cur_index_tuple;
+
+  /* if in_index_range==TRUE: range_id of the range we're enumerating */
+  char *cur_range_info;
+
+  /* Initially FALSE, becomes TRUE when we've set key_tuple_xxx members */
+  bool know_key_tuple_params;
+  uint         key_tuple_length; /* Length of index lookup tuple, in bytes */
+  key_part_map key_tuple_map;    /* keyparts used in index lookup tuples */
+
+  /*
+    This is 
+      = key_tuple_length   if we copy keys to buffer
+      = sizeof(void*)      if we're using pointers to materialized keys.
+  */
+  uint key_size_in_keybuf;
+  
+  /* = key_size_in_keybuf [ + sizeof(range_assoc_info) ] */
+  uint key_buff_elem_size;
+  
+  /** rnd_pos() scan and rowid buffer-related members **/
+
+  /*
+    Buffer to store (rowid, range_id) pairs, or just rowids if 
+    is_mrr_assoc==FALSE
+  */
+  Forward_lifo_buffer rowid_buffer;
+  
+  /* rowid_buffer.read() will set the following:  */
+  uchar *rowid;
+  uchar *rowids_range_id;
+
+  uchar *last_identical_rowid;
+
+  bool dsmrr_eof; /* TRUE <=> We have reached EOF when reading index tuples */
+  
+  /* = h->ref_length  [ + sizeof(range_assoc_info) ] */
+  uint rowid_buff_elem_size;
+  
   bool choose_mrr_impl(uint keyno, ha_rows rows, uint *flags, uint *bufsz, 
                        COST_VECT *cost);
   bool get_disk_sweep_mrr_cost(uint keynr, ha_rows rows, uint flags, 
                                uint *buffer_size, COST_VECT *cost);
+  bool check_cpk_scan(THD *thd, uint keyno, uint mrr_flags);
+  static int key_tuple_cmp(void* arg, uchar* key1, uchar* key2);
+  static int key_tuple_cmp_reverse(void* arg, uchar* key1, uchar* key2);
+  int dsmrr_fill_rowid_buffer();
+  void dsmrr_fill_key_buffer();
+  int dsmrr_next_from_index(char **range_info);
+
+  void setup_buffer_sizes(key_range *sample_key);
+  void reallocate_buffer_space();
+  
+  static range_seq_t key_buf_seq_init(void *init_param, uint n_ranges, uint flags);
+  static uint key_buf_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
+  friend class Key_value_records_iterator;
 };
 
+/**
+  @} (end of group DS-MRR declarations)
+*/
+
diff -urN --exclude='.*' 5.3-noc/sql/mysqld.cc maria-5.3-dsmrr-cpk-r5-noc/sql/mysqld.cc
--- 5.3-noc/sql/mysqld.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/mysqld.cc	2010-08-14 19:28:23.000000000 +0400
@@ -308,6 +308,7 @@
   "partial_match_rowid_merge",
   "partial_match_table_scan",
   "subquery_cache",
+  "mrr_sort_keys",
 #ifndef DBUG_OFF
   "table_elimination",
 #endif
@@ -329,6 +330,7 @@
   sizeof("partial_match_rowid_merge") - 1,
   sizeof("partial_match_table_scan") - 1,
   sizeof("subquery_cache") - 1,
+  sizeof("mrr_sort_keys") - 1,
 #ifndef DBUG_OFF
   sizeof("table_elimination") - 1,
 #endif
@@ -415,7 +417,8 @@
                                         "semijoin=on,"
                                         "partial_match_rowid_merge=on,"
                                         "partial_match_table_scan=on,"
-                                        "subquery_cache=on"
+                                        "subquery_cache=on,"
+                                        "mrr_sort_keys=on"
 #ifndef DBUG_OFF
                                         ",table_elimination=on";
 #else
diff -urN --exclude='.*' 5.3-noc/sql/mysql_priv.h maria-5.3-dsmrr-cpk-r5-noc/sql/mysql_priv.h
--- 5.3-noc/sql/mysql_priv.h	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/mysql_priv.h	2010-08-14 19:28:23.000000000 +0400
@@ -571,12 +571,13 @@
 #define OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE 512
 #define OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN 1024
 #define OPTIMIZER_SWITCH_SUBQUERY_CACHE (1<<11)
+#define OPTIMIZER_SWITCH_MRR_SORT_KEYS (1<<12)
 
 #ifdef DBUG_OFF
-#  define OPTIMIZER_SWITCH_LAST (1<<12)
-#else
-#  define OPTIMIZER_SWITCH_TABLE_ELIMINATION (1<<12)
 #  define OPTIMIZER_SWITCH_LAST (1<<13)
+#else
+#  define OPTIMIZER_SWITCH_TABLE_ELIMINATION (1<<13)
+#  define OPTIMIZER_SWITCH_LAST (1<<14)
 #endif
 
 #ifdef DBUG_OFF 
@@ -592,7 +593,8 @@
                                     OPTIMIZER_SWITCH_SEMIJOIN | \
                                     OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE|\
                                     OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN|\
-                                    OPTIMIZER_SWITCH_SUBQUERY_CACHE)
+                                    OPTIMIZER_SWITCH_SUBQUERY_CACHE|\
+                                    OPTIMIZER_SWITCH_MRR_SORT_KEYS)
 #else
 #  define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
                                     OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
@@ -606,7 +608,8 @@
                                     OPTIMIZER_SWITCH_SEMIJOIN | \
                                     OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE|\
                                     OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN|\
-                                    OPTIMIZER_SWITCH_SUBQUERY_CACHE)
+                                    OPTIMIZER_SWITCH_SUBQUERY_CACHE|\
+                                    OPTIMIZER_SWITCH_MRR_SORT_KEYS)
 #endif
 
 /*
diff -urN --exclude='.*' 5.3-noc/sql/opt_index_cond_pushdown.cc maria-5.3-dsmrr-cpk-r5-noc/sql/opt_index_cond_pushdown.cc
--- 5.3-noc/sql/opt_index_cond_pushdown.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/opt_index_cond_pushdown.cc	2010-09-21 20:21:11.000000000 +0400
@@ -378,6 +378,7 @@
                                  QT_ORDINARY););
 
         tab->select->cond= tab->select_cond;
+        tab->select->pre_idx_push_select_cond= tab->pre_idx_push_select_cond;
       }
     }
   }
diff -urN --exclude='.*' 5.3-noc/sql/opt_range.cc maria-5.3-dsmrr-cpk-r5-noc/sql/opt_range.cc
--- 5.3-noc/sql/opt_range.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/opt_range.cc	2010-09-21 20:21:11.000000000 +0400
@@ -1119,7 +1119,7 @@
 }
 
 
-SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
+SQL_SELECT::SQL_SELECT() :quick(0),cond(0),pre_idx_push_select_cond(NULL),free_cond(0)
 {
   quick_keys.clear_all(); needed_reg.clear_all();
   my_b_clear(&file);
@@ -8005,6 +8005,7 @@
 
   quick->mrr_buf_size= thd->variables.mrr_buff_size;
   if (table->file->multi_range_read_info(quick->index, 1, (uint)records,
+                                         uint(-1), 
                                          &quick->mrr_buf_size,
                                          &quick->mrr_flags, &cost))
     goto err;
diff -urN --exclude='.*' 5.3-noc/sql/opt_range.h maria-5.3-dsmrr-cpk-r5-noc/sql/opt_range.h
--- 5.3-noc/sql/opt_range.h	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/opt_range.h	2010-09-21 20:21:11.000000000 +0400
@@ -738,6 +738,13 @@
  public:
   QUICK_SELECT_I *quick;	// If quick-select used
   COND		*cond;		// where condition
+
+  /*
+    When using Index Condition Pushdown: condition that we've had before
+    extracting and pushing index condition.
+    In other cases, NULL.
+  */
+  Item *pre_idx_push_select_cond;
   TABLE	*head;
   IO_CACHE file;		// Positions to used records
   ha_rows records;		// Records in use if read from file
diff -urN --exclude='.*' 5.3-noc/sql/sql_join_cache.cc maria-5.3-dsmrr-cpk-r5-noc/sql/sql_join_cache.cc
--- 5.3-noc/sql/sql_join_cache.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/sql_join_cache.cc	2010-08-14 19:28:23.000000000 +0400
@@ -651,6 +651,9 @@
 
   use_emb_key= check_emb_key_usage();
 
+  if (use_emb_key)
+    mrr_mode|= HA_MRR_MATERIALIZED_KEYS;
+
   create_remaining_fields(FALSE);
 
   set_constants();
@@ -2390,8 +2393,8 @@
   */ 
   if (!file->inited)
     file->ha_index_init(join_tab->ref.key, 1);
-  if ((error= file->multi_range_read_init(seq_funcs, (void*) this, ranges,
-					  mrr_mode, &mrr_buff)))
+  if ((error= file->multi_range_read_init(seq_funcs, (void*) this, ranges, 
+                                          mrr_mode, &mrr_buff)))
     rc= error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
   
   return rc;
@@ -2631,6 +2634,8 @@
       data_fields_offset+= copy->length;
   } 
 
+  mrr_mode|= HA_MRR_MATERIALIZED_KEYS;
+
   DBUG_RETURN(rc);
 }
 
diff -urN --exclude='.*' 5.3-noc/sql/sql_lifo_buffer.h maria-5.3-dsmrr-cpk-r5-noc/sql/sql_lifo_buffer.h
--- 5.3-noc/sql/sql_lifo_buffer.h	1970-01-01 03:00:00.000000000 +0300
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/sql_lifo_buffer.h	2010-10-04 10:47:05.000000000 +0400
@@ -0,0 +1,339 @@
+/**
+  @defgroup Bi-directional LIFO buffers used by DS-MRR implementation
+  @{
+*/
+
+class Forward_lifo_buffer;
+class Backward_lifo_buffer;
+
+
+/*
+  A base class for in-memory buffer used by DS-MRR implementation. Common
+  properties:
+  - The buffer is last-in-first-out, i.e. elements that are written last are
+    read first.
+  - The buffer contains fixed-size elements. The elements are either atomic
+    byte sequences or pairs of them.
+  - The buffer resides in the memory provided by the user. It is possible to
+     = dynamically (ie. between write operations) add ajacent memory space to
+       the buffer
+     = dynamically remove unused space from the buffer.
+    The intent of this is to allow to have two buffers on adjacent memory
+    space, one is being read from (and so its space shrinks), while the other 
+    is being written to (and so it needs more and more space).
+
+  There are two concrete classes, Forward_lifo_buffer and Backward_lifo_buffer.
+*/
+
+class Lifo_buffer 
+{
+protected:
+  /**
+    Pointers to data to be written. write() call will assume that 
+    (*write_ptr1) points to size1 bytes of data to be written.
+    If write_ptr2 != NULL then the buffer stores pairs, and (*write_ptr2) 
+    points to size2 bytes of data that form the second component.
+  */
+  uchar **write_ptr1;
+  size_t size1;
+  uchar **write_ptr2;
+  size_t size2;
+
+  /**
+    read() will do reading by storing pointer to read data into *read_ptr1 (if
+    the buffer stores atomic elements), or into {*read_ptr1, *read_ptr2} (if
+    the buffer stores pairs).
+  */
+  uchar **read_ptr1;
+  uchar **read_ptr2;
+
+  uchar *start; /**< points to start of buffer space */
+  uchar *end;   /**< points to just beyond the end of buffer space */
+public:
+
+  enum enum_direction {
+    BACKWARD=-1, /**< buffer is filled/read from bigger to smaller memory addresses */
+    FORWARD=1  /**< buffer is filled/read from smaller to bigger memory addresses */
+  };
+
+  virtual enum_direction type() = 0;
+
+  /* Buffer space control functions */
+
+  /** Let the buffer store data in the given space. */
+  void set_buffer_space(uchar *start_arg, uchar *end_arg) 
+  {
+    start= start_arg;
+    end= end_arg;
+    TRASH(start, end - start);
+    reset();
+  }
+  
+  /** 
+    Specify where write() should get the source data from, as well as source
+    data size.
+  */
+  void setup_writing(uchar **data1, size_t len1, uchar **data2, size_t len2)
+  {
+    write_ptr1= data1;
+    size1= len1;
+    write_ptr2= data2;
+    size2= len2;
+  }
+
+  /** 
+    Specify where read() should store pointers to read data, as well as read
+    data size. The sizes must match those passed to setup_writing().
+  */
+  void setup_reading(uchar **data1, size_t len1, uchar **data2, size_t len2)
+  {
+    read_ptr1= data1;
+    DBUG_ASSERT(len1 == size1);
+    read_ptr2= data2;
+    DBUG_ASSERT(len2 == size2);
+  }
+  
+  bool can_write()
+  {
+    return have_space_for(size1 + (write_ptr2 ? size2 : 0));
+  }
+  virtual void write() = 0;
+
+  bool is_empty() { return used_size() == 0; }
+  virtual bool read() = 0;
+  
+  void sort(qsort2_cmp cmp_func, void *cmp_func_arg)
+  {
+    uint elem_size= size1 + (write_ptr2 ? size2 : 0);
+    uint n_elements= used_size() / elem_size;
+    my_qsort2(used_area(), n_elements, elem_size, cmp_func, cmp_func_arg);
+  }
+
+  virtual void reset() = 0;
+  virtual uchar *end_of_space() = 0;
+protected:
+  virtual bool have_space_for(size_t bytes) = 0;
+  virtual size_t used_size() = 0;
+  
+  /* To be used only by iterator class: */
+  virtual uchar *get_pos()= 0;
+  virtual bool read(uchar **position)= 0;
+  friend class Lifo_buffer_iterator;
+public:
+  virtual void remove_unused_space(uchar **unused_start, uchar **unused_end)=0;
+  virtual uchar *used_area() = 0; 
+  virtual ~Lifo_buffer() {};
+};
+
+
+/**
+  Forward LIFO buffer
+
+  The buffer that is being written to from start to end and read in the
+  reverse.  'pos' points to just beyond the end of used space.
+
+  It is possible to grow/shink the buffer at the end bound
+
+     used space      unused space  
+   *==============*-----------------*
+   ^              ^                 ^
+   |              |                 +--- end
+   |              +---- pos              
+   +--- start           
+*/
+
+class Forward_lifo_buffer: public Lifo_buffer
+{
+  uchar *pos;
+public:
+  enum_direction type() { return FORWARD; }
+  size_t used_size()
+  {
+    return pos - start;
+  }
+  void reset()
+  {
+    pos= start;
+  }
+  uchar *end_of_space() { return pos; }
+  bool have_space_for(size_t bytes)
+  {
+    return (pos + bytes < end);
+  }
+
+  void write()
+  {
+    write_bytes(*write_ptr1, size1);
+    if (write_ptr2)
+      write_bytes(*write_ptr2, size2);
+  }
+  void write_bytes(const uchar *data, size_t bytes)
+  {
+    DBUG_ASSERT(have_space_for(bytes));
+    memcpy(pos, data, bytes);
+    pos += bytes;
+  }
+  bool have_data(uchar *position, size_t bytes)
+  {
+    return ((position - start) >= (ptrdiff_t)bytes);
+  }
+  uchar *read_bytes(uchar **position, size_t bytes)
+  {
+    DBUG_ASSERT(have_data(*position, bytes));
+    *position= (*position) - bytes;
+    return *position;
+  }
+  bool read() { return read(&pos); }
+  bool read(uchar **position)
+  {
+    if (!have_data(*position, size1 + (read_ptr2 ? size2 : 0)))
+      return TRUE;
+    if (read_ptr2)
+      *read_ptr2= read_bytes(position, size2);
+    *read_ptr1= read_bytes(position, size1);
+    return FALSE;
+  }
+  void remove_unused_space(uchar **unused_start, uchar **unused_end)
+  {
+    DBUG_ASSERT(0); /* Don't need this yet */
+  }
+  /**
+    Add more space to the buffer. The caller is responsible that the space
+    being added is adjacent to the end of the buffer.
+
+    @param unused_start Start of space
+    @param unused_end   End of space
+  */
+  void grow(uchar *unused_start, uchar *unused_end)
+  {
+    DBUG_ASSERT(unused_end >= unused_start);
+    DBUG_ASSERT(end == unused_start);
+    TRASH(unused_start, unused_end - unused_start);
+    end= unused_end;
+  }
+  /* Return pointer to start of the memory area that is occupied by the data */
+  uchar *used_area() { return start; }
+  friend class Lifo_buffer_iterator;
+  uchar *get_pos() { return pos; }
+};
+
+
+
+/**
+  Backward LIFO buffer
+
+  The buffer that is being written to from start to end and read in the
+  reverse.  'pos' points to the start of used space.
+
+  It is possible to grow/shink the buffer at the start.
+
+     unused space      used space  
+   *--------------*=================*
+   ^              ^                 ^
+   |              |                 +--- end
+   |              +---- pos              
+   +--- start           
+*/
+class Backward_lifo_buffer: public Lifo_buffer
+{
+  uchar *pos;
+public:
+  enum_direction type() { return BACKWARD; }
+ 
+  size_t used_size()
+  {
+    return end - pos;
+  }
+  void reset()
+  {
+    pos= end;
+  }
+  uchar *end_of_space() { return end; }
+  bool have_space_for(size_t bytes)
+  {
+    return (pos - bytes >= start);
+  }
+  void write()
+  {
+    if (write_ptr2)
+      write_bytes(*write_ptr2, size2);
+    write_bytes(*write_ptr1, size1);
+  }
+  void write_bytes(const uchar *data, size_t bytes)
+  {
+    DBUG_ASSERT(have_space_for(bytes));
+    pos -= bytes;
+    memcpy(pos, data, bytes);
+  }
+  bool read()
+  {
+    return read(&pos);
+  }
+  bool read(uchar **position)
+  {
+    if (!have_data(*position, size1 + (read_ptr2 ? size2 : 0)))
+      return TRUE;
+    *read_ptr1= read_bytes(position, size1);
+    if (read_ptr2)
+      *read_ptr2= read_bytes(position, size2);
+    return FALSE;
+  }
+  bool have_data(uchar *position, size_t bytes)
+  {
+    return ((end - position) >= (ptrdiff_t)bytes);
+  }
+  uchar *read_bytes(uchar **position, size_t bytes)
+  {
+    DBUG_ASSERT(have_data(*position, bytes));
+    uchar *ret= *position;
+    *position= *position + bytes;
+    return ret;
+  }
+  /**
+    Stop using/return the unused part of the space
+    @param unused_start  OUT Start of the unused space
+    @param unused_end    OUT End of the unused space
+  */
+  void remove_unused_space(uchar **unused_start, uchar **unused_end)
+  {
+    *unused_start= start;
+    *unused_end= pos;
+    start= pos;
+  }
+  void grow(uchar *unused_start, uchar *unused_end)
+  {
+    DBUG_ASSERT(0); /* Not used for backward buffers */
+  }
+  /* Return pointer to start of the memory area that is occupied by the data */
+  uchar *used_area() { return pos; }
+  friend class Lifo_buffer_iterator;
+  uchar *get_pos() { return pos; }
+};
+
+
+
+/** Iterator to walk over contents of the buffer without reading it. */
+class Lifo_buffer_iterator
+{
+  uchar *pos;
+  Lifo_buffer *buf;
+public:
+  void init(Lifo_buffer *buf_arg)
+  {
+    buf= buf_arg;
+    pos= buf->get_pos();
+  }
+  /*
+    Read the next value. The calling convention is the same as buf->read()
+    has.
+
+    @retval FALSE - ok
+    @retval TRUE  - EOF, reached the end of the buffer
+  */
+  bool read() 
+  {
+    return buf->read(&pos);
+  }
+};
+
+
diff -urN --exclude='.*' 5.3-noc/sql/sql_select.cc maria-5.3-dsmrr-cpk-r5-noc/sql/sql_select.cc
--- 5.3-noc/sql/sql_select.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/sql/sql_select.cc	2010-09-21 20:21:11.000000000 +0400
@@ -6637,7 +6637,6 @@
   DBUG_ENTER("make_join_select");
   if (select)
   {
-    add_not_null_conds(join);
     table_map used_tables;
     /*
       Step #1: Extract constant condition
@@ -7082,6 +7081,7 @@
       }
 
     }
+    add_not_null_conds(join);
   }
   DBUG_RETURN(0);
 }
@@ -7508,10 +7508,11 @@
   case JT_EQ_REF:
     if (cache_level <= 4)
       return 0;
-    flags= HA_MRR_NO_NULL_ENDPOINTS;
+    flags= HA_MRR_NO_NULL_ENDPOINTS | HA_MRR_SINGLE_POINT;
     if (tab->table->covering_keys.is_set(tab->ref.key))
       flags|= HA_MRR_INDEX_ONLY;
     rows= tab->table->file->multi_range_read_info(tab->ref.key, 10, 20,
+                                                  tab->ref.key_parts,
                                                   &bufsz, &flags, &cost);
     if ((rows != HA_POS_ERROR) && !(flags & HA_MRR_USE_DEFAULT_IMPL) &&
         (!(flags & HA_MRR_NO_ASSOCIATION) || cache_level > 6) &&
diff -urN --exclude='.*' 5.3-noc/storage/maria/ha_maria.cc maria-5.3-dsmrr-cpk-r5-noc/storage/maria/ha_maria.cc
--- 5.3-noc/storage/maria/ha_maria.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/storage/maria/ha_maria.cc	2010-08-14 19:28:23.000000000 +0400
@@ -3503,8 +3503,8 @@
  ***************************************************************************/
 
 int ha_maria::multi_range_read_init(RANGE_SEQ_IF *seq, void *seq_init_param,
-                                     uint n_ranges, uint mode, 
-                                     HANDLER_BUFFER *buf)
+                                    uint n_ranges, uint mode, 
+                                    HANDLER_BUFFER *buf)
 {
   return ds_mrr.dsmrr_init(this, seq, seq_init_param, n_ranges, mode, buf);
 }
@@ -3530,11 +3530,11 @@
 }
 
 ha_rows ha_maria::multi_range_read_info(uint keyno, uint n_ranges, uint keys,
-                                        uint *bufsz, uint *flags, 
-                                        COST_VECT *cost)
+                                       uint key_parts, uint *bufsz, 
+                                       uint *flags, COST_VECT *cost)
 {
   ds_mrr.init(this, table);
-  return ds_mrr.dsmrr_info(keyno, n_ranges, keys, bufsz, flags, cost);
+  return ds_mrr.dsmrr_info(keyno, n_ranges, keys, key_parts, bufsz, flags, cost);
 }
 
 /* MyISAM MRR implementation ends */
diff -urN --exclude='.*' 5.3-noc/storage/maria/ha_maria.h maria-5.3-dsmrr-cpk-r5-noc/storage/maria/ha_maria.h
--- 5.3-noc/storage/maria/ha_maria.h	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/storage/maria/ha_maria.h	2010-08-14 19:28:23.000000000 +0400
@@ -183,7 +183,8 @@
                                       uint n_ranges, uint *bufsz,
                                       uint *flags, COST_VECT *cost);
   ha_rows multi_range_read_info(uint keyno, uint n_ranges, uint keys,
-                                uint *bufsz, uint *flags, COST_VECT *cost);
+                                uint key_parts, uint *bufsz, 
+                                uint *flags, COST_VECT *cost);
   
   /* Index condition pushdown implementation */
   Item *idx_cond_push(uint keyno, Item* idx_cond);
diff -urN --exclude='.*' 5.3-noc/storage/myisam/ha_myisam.cc maria-5.3-dsmrr-cpk-r5-noc/storage/myisam/ha_myisam.cc
--- 5.3-noc/storage/myisam/ha_myisam.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/storage/myisam/ha_myisam.cc	2010-08-14 19:28:23.000000000 +0400
@@ -2206,11 +2206,11 @@
 }
 
 ha_rows ha_myisam::multi_range_read_info(uint keyno, uint n_ranges, uint keys,
-                                         uint *bufsz, uint *flags,
-                                         COST_VECT *cost)
+                                         uint key_parts, uint *bufsz, 
+                                         uint *flags, COST_VECT *cost)
 {
   ds_mrr.init(this, table);
-  return ds_mrr.dsmrr_info(keyno, n_ranges, keys, bufsz, flags, cost);
+  return ds_mrr.dsmrr_info(keyno, n_ranges, keys, key_parts, bufsz, flags, cost);
 }
 
 /* MyISAM MRR implementation ends */
diff -urN --exclude='.*' 5.3-noc/storage/myisam/ha_myisam.h maria-5.3-dsmrr-cpk-r5-noc/storage/myisam/ha_myisam.h
--- 5.3-noc/storage/myisam/ha_myisam.h	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/storage/myisam/ha_myisam.h	2010-08-14 19:28:23.000000000 +0400
@@ -168,7 +168,8 @@
                                       uint n_ranges, uint *bufsz,
                                       uint *flags, COST_VECT *cost);
   ha_rows multi_range_read_info(uint keyno, uint n_ranges, uint keys,
-                                uint *bufsz, uint *flags, COST_VECT *cost);
+                                uint key_parts, uint *bufsz, 
+                                uint *flags, COST_VECT *cost);
   
   /* Index condition pushdown implementation */
   Item *idx_cond_push(uint keyno, Item* idx_cond);
diff -urN --exclude='.*' 5.3-noc/storage/xtradb/handler/ha_innodb.cc maria-5.3-dsmrr-cpk-r5-noc/storage/xtradb/handler/ha_innodb.cc
--- 5.3-noc/storage/xtradb/handler/ha_innodb.cc	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/storage/xtradb/handler/ha_innodb.cc	2010-08-14 19:28:23.000000000 +0400
@@ -11207,7 +11207,8 @@
  */
 
 int ha_innobase::multi_range_read_init(RANGE_SEQ_IF *seq, void *seq_init_param,
-                          uint n_ranges, uint mode, HANDLER_BUFFER *buf)
+                                       uint n_ranges, uint mode, 
+                                       HANDLER_BUFFER *buf)
 {
   return ds_mrr.dsmrr_init(this, seq, seq_init_param, n_ranges, mode, buf);
 }
@@ -11234,12 +11235,13 @@
   return res;
 }
 
-ha_rows ha_innobase::multi_range_read_info(uint keyno, uint n_ranges, 
-                                           uint keys, uint *bufsz, 
+ha_rows ha_innobase::multi_range_read_info(uint keyno, uint n_ranges, uint keys,
+                                           uint key_parts, uint *bufsz, 
                                            uint *flags, COST_VECT *cost)
 {
   ds_mrr.init(this, table);
-  ha_rows res= ds_mrr.dsmrr_info(keyno, n_ranges, keys, bufsz, flags, cost);
+  ha_rows res= ds_mrr.dsmrr_info(keyno, n_ranges, keys, key_parts, bufsz, 
+                                 flags, cost);
   return res;
 }
 
diff -urN --exclude='.*' 5.3-noc/storage/xtradb/handler/ha_innodb.h maria-5.3-dsmrr-cpk-r5-noc/storage/xtradb/handler/ha_innodb.h
--- 5.3-noc/storage/xtradb/handler/ha_innodb.h	2010-08-14 19:29:22.000000000 +0400
+++ maria-5.3-dsmrr-cpk-r5-noc/storage/xtradb/handler/ha_innodb.h	2010-08-14 19:28:23.000000000 +0400
@@ -219,7 +219,8 @@
                                       uint n_ranges, uint *bufsz,
                                       uint *flags, COST_VECT *cost);
   ha_rows multi_range_read_info(uint keyno, uint n_ranges, uint keys,
-                                uint *bufsz, uint *flags, COST_VECT *cost);
+                                uint key_parts, uint *bufsz, 
+                                uint *flags, COST_VECT *cost);
   DsMrr_impl ds_mrr;
 
   Item *idx_cond_push(uint keyno, Item* idx_cond);

Follow ups