Backport into MariaDB-5.2 the following:

WL#2474 "Multi Range Read: Change the default MRR implementation to implement new MRR interface"
WL#2475 "Batched range read functions for MyISAM/InnoDb"
        "Index condition pushdown for MyISAM/InnoDB"
Igor's fix from sp1r-igor@olga.mysql.com-20080330055902-07614:
  There could be observed the following problems:
  1. EXPLAIN did not mention pushdown conditions from on expressions in the 
  'extra' column.  As a result if a query had no where conditions pushed 
  down to a table, but had on conditions pushed to this table the 'extra' 
  column in the EXPLAIN for the table missed 'using where'.
  2. Conditions for ref access were not eliminated from on expressions 
  though such conditions were eliminated from the where condition.

1 files changed, 393 insertions, 0 deletions

diff --git a/mysql-test/r/myisam_mrr.result b/mysql-test/r/myisam_mrr.result
new file mode 100644
index 00000000000..f3f89966da2
--- /dev/null
+++ b/mysql-test/r/myisam_mrr.result
@@ -0,0 +1,393 @@
+drop table if exists t1, t2, t3;
+set @read_rnd_buffer_size_save= @@read_rnd_buffer_size;
+set read_rnd_buffer_size=79;
+Warnings:
+Warning	1292	Truncated incorrect read_rnd_buffer_size value: '79'
+select @@read_rnd_buffer_size;
+@@read_rnd_buffer_size
+8228
+create table t1(a int);
+show create table t1;
+Table	Create Table
+t1	CREATE TABLE `t1` (
+  `a` int(11) DEFAULT NULL
+) ENGINE=MyISAM DEFAULT CHARSET=latin1
+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	10	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	21	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 @@read_rnd_buffer_size= @read_rnd_buffer_size_save;
+CREATE TABLE t1 (
+ID int(10) unsigned NOT NULL AUTO_INCREMENT,
+col1 int(10) unsigned DEFAULT NULL,
+key1 int(10) unsigned NOT NULL DEFAULT '0',
+key2 int(10) unsigned DEFAULT NULL,
+text1 text,
+text2 text,
+col2 smallint(6) DEFAULT '100',
+col3 enum('headers','bodyandsubject') NOT NULL DEFAULT 'bodyandsubject',
+col4 tinyint(3) unsigned NOT NULL DEFAULT '0',
+PRIMARY KEY (ID),
+KEY (key1),
+KEY (key2)
+) ENGINE=MyISAM AUTO_INCREMENT=6 DEFAULT CHARSET=utf8;
+INSERT INTO t1 VALUES
+(1,NULL,1130,NULL,'Hello',NULL,100,'bodyandsubject',0),
+(2,NULL,1130,NULL,'bye',NULL,100,'bodyandsubject',0),
+(3,NULL,1130,NULL,'red',NULL,100,'bodyandsubject',0),
+(4,NULL,1130,NULL,'yellow',NULL,100,'bodyandsubject',0),
+(5,NULL,1130,NULL,'blue',NULL,100,'bodyandsubject',0);
+select * FROM t1 WHERE key1=1130 AND col1 IS NULL ORDER BY text1;
+ID	col1	key1	key2	text1	text2	col2	col3	col4
+5	NULL	1130	NULL	blue	NULL	100	bodyandsubject	0
+2	NULL	1130	NULL	bye	NULL	100	bodyandsubject	0
+1	NULL	1130	NULL	Hello	NULL	100	bodyandsubject	0
+3	NULL	1130	NULL	red	NULL	100	bodyandsubject	0
+4	NULL	1130	NULL	yellow	NULL	100	bodyandsubject	0
+drop table t1;
+
+BUG#37851: Crash in test_if_skip_sort_order tab->select is zero
+
+CREATE TABLE t1 (
+pk int(11) NOT NULL AUTO_INCREMENT,
+PRIMARY KEY (pk)
+);
+INSERT INTO t1 VALUES (1);
+CREATE TABLE t2 (
+pk int(11) NOT NULL AUTO_INCREMENT,
+int_key int(11) DEFAULT NULL,
+PRIMARY KEY (pk),
+KEY int_key (int_key)
+);
+INSERT INTO t2 VALUES (1,1),(2,6),(3,0);
+EXPLAIN EXTENDED
+SELECT MIN(t1.pk)
+FROM t1 WHERE EXISTS (
+SELECT t2.pk
+FROM t2
+WHERE t2.int_key IS NULL
+GROUP BY t2.pk
+);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+2	SUBQUERY	t2	ALL	int_key	int_key	5		3	33.33	Using index condition; Using filesort
+Warnings:
+Note	1003	select min(`test`.`t1`.`pk`) AS `MIN(t1.pk)` from `test`.`t1` where 0
+DROP TABLE t1, t2;
+#
+# BUG#42048 Discrepancy between MyISAM and Maria's ICP implementation
+#
+create table t0 (a int);
+insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t1 (a int, b char(20), filler char(200), key(a,b(10)));
+insert into t1 select A.a + 10*(B.a + 10*C.a), 'bbb','filler' from t0 A, t0 B, t0 C;
+update t1 set b=repeat(char(65+a), 20) where a < 25;
+This must show range + using index condition:
+explain select * from t1 where a < 10 and b = repeat(char(65+a), 20);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	a	a	5	NULL	19	Using where
+select * from t1 where a < 10 and b = repeat(char(65+a), 20);
+a	b	filler
+0	AAAAAAAAAAAAAAAAAAAA	filler
+1	BBBBBBBBBBBBBBBBBBBB	filler
+2	CCCCCCCCCCCCCCCCCCCC	filler
+3	DDDDDDDDDDDDDDDDDDDD	filler
+4	EEEEEEEEEEEEEEEEEEEE	filler
+5	FFFFFFFFFFFFFFFFFFFF	filler
+6	GGGGGGGGGGGGGGGGGGGG	filler
+7	HHHHHHHHHHHHHHHHHHHH	filler
+8	IIIIIIIIIIIIIIIIIIII	filler
+9	JJJJJJJJJJJJJJJJJJJJ	filler
+drop table t0,t1;
+#
+# BUG#41136: ORDER BY + range access: EXPLAIN shows "Using MRR" while MRR is actually not used
+#
+create table t0 (a int);
+insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t1 (a int, b int, key(a));
+insert into t1 select A.a + 10 *(B.a + 10*C.a), A.a + 10 *(B.a + 10*C.a) from t0 A, t0 B, t0 C;
+This mustn't show "Using MRR":
+explain select * from t1 where a < 20  order by a;
+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
+drop table t0, t1;