Re: 50% performance regression with maria-5.3-dsmrr-cpk
Test case:

--source include/have_innodb.inc

SET SESSION join_cache_level=8;

CREATE TABLE `D` (
`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,
PRIMARY KEY (`pk`),
KEY `col_int_key` (`col_int_key`),
KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`)
) ENGINE=InnoDB AUTO_INCREMENT=101 DEFAULT CHARSET=latin1;
INSERT INTO `D` VALUES (1,6,NULL,'r');
INSERT INTO `D` VALUES (2,8,0,'c');
INSERT INTO `D` VALUES (3,6,0,'o');
INSERT INTO `D` VALUES (4,6,7,'c');
INSERT INTO `D` VALUES (5,3,8,'d');
INSERT INTO `D` VALUES (6,9,4,'v');
INSERT INTO `D` VALUES (7,2,6,'m');
INSERT INTO `D` VALUES (8,1,5,'j');
INSERT INTO `D` VALUES (9,8,NULL,'f');
INSERT INTO `D` VALUES (10,0,NULL,'n');
INSERT INTO `D` VALUES (11,9,8,'z');
INSERT INTO `D` VALUES (12,8,8,'h');
INSERT INTO `D` VALUES (13,NULL,8,'q');
INSERT INTO `D` VALUES (14,0,1,'w');
INSERT INTO `D` VALUES (15,5,1,'z');
INSERT INTO `D` VALUES (16,1,5,'j');
INSERT INTO `D` VALUES (17,1,2,'a');
INSERT INTO `D` VALUES (18,6,7,'m');
INSERT INTO `D` VALUES (19,6,6,'n');
INSERT INTO `D` VALUES (20,1,4,'e');
INSERT INTO `D` VALUES (21,8,7,'u');
INSERT INTO `D` VALUES (22,1,0,'s');
INSERT INTO `D` VALUES (23,0,9,'u');
INSERT INTO `D` VALUES (24,4,3,'r');
INSERT INTO `D` VALUES (25,9,5,'g');
INSERT INTO `D` VALUES (26,8,1,'o');
INSERT INTO `D` VALUES (27,5,1,'w');
INSERT INTO `D` VALUES (28,9,5,'b');
INSERT INTO `D` VALUES (29,5,9,NULL);
INSERT INTO `D` VALUES (30,NULL,2,'y');
INSERT INTO `D` VALUES (31,NULL,5,'y');
INSERT INTO `D` VALUES (32,105,248,'u');
INSERT INTO `D` VALUES (33,0,0,'p');
INSERT INTO `D` VALUES (34,3,8,'s');
INSERT INTO `D` VALUES (35,1,1,'e');
INSERT INTO `D` VALUES (36,75,255,'d');
INSERT INTO `D` VALUES (37,9,9,'d');
INSERT INTO `D` VALUES (38,7,9,'c');
INSERT INTO `D` VALUES (39,NULL,3,'b');
INSERT INTO `D` VALUES (40,NULL,9,'t');
INSERT INTO `D` VALUES (41,4,6,NULL);
INSERT INTO `D` VALUES (42,0,4,'y');
INSERT INTO `D` VALUES (43,204,60,'c');
INSERT INTO `D` VALUES (44,0,7,'d');
INSERT INTO `D` VALUES (45,9,1,'x');
INSERT INTO `D` VALUES (46,8,6,'p');
INSERT INTO `D` VALUES (47,7,4,'e');
INSERT INTO `D` VALUES (48,8,NULL,'g');
INSERT INTO `D` VALUES (49,NULL,8,'x');
INSERT INTO `D` VALUES (50,6,0,'s');
INSERT INTO `D` VALUES (51,5,8,'e');
INSERT INTO `D` VALUES (52,2,151,'l');
INSERT INTO `D` VALUES (53,3,7,'p');
INSERT INTO `D` VALUES (54,7,6,'h');
INSERT INTO `D` VALUES (55,NULL,NULL,'m');
INSERT INTO `D` VALUES (56,145,23,'n');
INSERT INTO `D` VALUES (57,0,2,'v');
INSERT INTO `D` VALUES (58,1,4,'b');
INSERT INTO `D` VALUES (59,7,NULL,'x');
INSERT INTO `D` VALUES (60,3,NULL,'r');
INSERT INTO `D` VALUES (61,NULL,77,'t');
INSERT INTO `D` VALUES (62,2,NULL,'w');
INSERT INTO `D` VALUES (63,2,NULL,'w');
INSERT INTO `D` VALUES (64,2,7,'k');
INSERT INTO `D` VALUES (65,8,1,'a');
INSERT INTO `D` VALUES (66,6,9,'t');
INSERT INTO `D` VALUES (67,1,6,'z');
INSERT INTO `D` VALUES (68,NULL,2,'e');
INSERT INTO `D` VALUES (69,1,3,'q');
INSERT INTO `D` VALUES (70,0,0,'e');
INSERT INTO `D` VALUES (71,4,NULL,'v');
INSERT INTO `D` VALUES (72,1,6,'d');
INSERT INTO `D` VALUES (73,1,3,'u');
INSERT INTO `D` VALUES (74,27,195,'o');
INSERT INTO `D` VALUES (75,4,5,'b');
INSERT INTO `D` VALUES (76,6,2,'c');
INSERT INTO `D` VALUES (77,2,7,'q');
INSERT INTO `D` VALUES (78,248,25,NULL);
INSERT INTO `D` VALUES (79,NULL,NULL,'h');
INSERT INTO `D` VALUES (80,9,0,'d');
INSERT INTO `D` VALUES (81,75,98,'w');
INSERT INTO `D` VALUES (82,2,6,'m');
INSERT INTO `D` VALUES (83,9,5,'i');
INSERT INTO `D` VALUES (84,4,0,'w');
INSERT INTO `D` VALUES (85,0,3,'f');
INSERT INTO `D` VALUES (86,0,1,'k');
INSERT INTO `D` VALUES (87,1,1,'v');
INSERT INTO `D` VALUES (88,119,147,'c');
INSERT INTO `D` VALUES (89,1,3,'y');
INSERT INTO `D` VALUES (90,7,3,'h');
INSERT INTO `D` VALUES (91,2,NULL,NULL);
INSERT INTO `D` VALUES (92,7,2,'t');
INSERT INTO `D` VALUES (93,2,1,'l');
INSERT INTO `D` VALUES (94,6,8,'a');
INSERT INTO `D` VALUES (95,4,8,'r');
INSERT INTO `D` VALUES (96,5,8,'s');
INSERT INTO `D` VALUES (97,7,0,'z');
INSERT INTO `D` VALUES (98,1,1,'j');
INSERT INTO `D` VALUES (99,7,8,'c');
INSERT INTO `D` VALUES (100,2,5,'f');

SELECT table1 .`col_int_nokey`
FROM D table1 STRAIGHT_JOIN ( D JOIN ( D table3 STRAIGHT_JOIN D table4 ON table4 .`pk` = table3 .`col_varchar_key` ) ON table4 .`pk` ) ON table4 .`col_varchar_key` ;

With mrr_sort_keys=off , this query crashes with LP bug #628785

Re: 50% performance regression with maria-5.3-dsmrr-cpk
I failed to reproduce this bug with the latest 5.3 tree

I got with a debug build:

MariaDB [test]> set join_cache_level=8;
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> set optimizer_switch='mrr=on';
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> SELECT table1 .`col_int_nokey` FROM D table1 STRAIGHT_JOIN ( D JOIN ( D table3 STRAIGHT_JOIN D table4 ON table4 .`pk` = table3 .`col_varchar_key` ) ON table4 .`pk` ) ON table4 .`col_varchar_key`;
Empty set (7.94 sec)

and

MariaDB [test]> set join_cache_level=8;
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> set optimizer_switch='mrr=on,mrr_sort_keys=on';
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> SELECT table1 .`col_int_nokey` FROM D table1 STRAIGHT_JOIN ( D JOIN ( D table3 STRAIGHT_JOIN D table4 ON table4 .`pk` = table3 .`col_varchar_key` ) ON table4 .`pk` ) ON table4 .`col_varchar_key`;
Empty set (1.62 sec)

Launchpad bug id: 629493