Fixed LP bug #698882.

Made sure that the optimal fields are used by TABLE_REF objects
when building index access keys to joined tables.
Fixed a bug in the template function that sorts the elements of
a list using the bubble sort algorithm. The bug caused poor
performance of the function. Also added an optimization that
skips comparison with the most heavy elements that has been 
already properly placed in the list.
Made the comparison of the fields belonging to the same Item_equal
more granular: fields belonging to the same table are also ordered
according to some rules.

1 files changed, 103 insertions, 1 deletions

diff --git a/mysql-test/r/select_pkeycache.result b/mysql-test/r/select_pkeycache.result
index 6d3a3717c67..303b3f065fb 100644
--- a/mysql-test/r/select_pkeycache.result
+++ b/mysql-test/r/select_pkeycache.result
@@ -4383,7 +4383,7 @@ EXPLAIN EXTENDED SELECT a, b FROM t1 WHERE a > 1 AND b = a LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	SIMPLE	t1	range	PRIMARY	PRIMARY	4	NULL	3	100.00	Using index condition; Using where; Using MRR
 Warnings:
-Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` where ((`test`.`t1`.`a` = `test`.`t1`.`b`) and (`test`.`t1`.`a` > 1)) limit 2
+Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` where ((`test`.`t1`.`b` = `test`.`t1`.`a`) and (`test`.`t1`.`a` > 1)) limit 2
 DROP TABLE t1;
 #
 # Bug#47019: Assertion failed: 0, file .\rt_mbr.c, line 138 when 
@@ -4796,4 +4796,106 @@ SELECT 1 FROM t1 ORDER BY a COLLATE latin1_german2_ci;
 1
 1
 DROP TABLE t1;
+#
+# Bug #698882: best equality substitution not applied to ref 
+#
+CREATE TABLE t1 (a1 int NOT NULL, b1 char(10), INDEX idx (a1));
+CREATE TABLE t2 (a2 int NOT NULL, b2 char(10), INDEX idx (a2));
+CREATE TABLE t3 (a3 int NOT NULL, b3 char(10), INDEX idx (a3));
+INSERT INTO t1 VALUES (2,'xx'), (1,'xxx'),  (11,'xxxxxxx');
+INSERT INTO t2 VALUES
+(7,'yyyy'), (2,'y'), (3,'yyy'), (1,'yy'), (1,'yyyyy'),
+(3,'yy'),  (1,'y'), (4,'yyy'), (7,'y'),  (4,'yyyyy'), (7,'yyy'),
+(7,'yyyy'), (2,'yy'),  (3,'yyy'), (1,'yyyyyyyy'), (1,'yyyyy'),
+(3,'yy'), (1,'yyy'), (4,'yyy'), (7,'y'), (4,'yyyyy'), (7,'yyy');
+INSERT INTO t3 VALUES
+(9,'zzzzzzz'), (2,'zzzzz'), (1,'z'), (9,'zz'), (1,'zz'), (5,'zzzzzzz'),
+(4,'zz'), (3,'z'), (5,'zzzzzz'), (3,'zz'), (4,'zzzz'), (3,'z'),
+(9,'zzzzzzzz'), (2,'zz'), (1,'zz'), (9,'zzz'), (1,'zzz'), (5,'zzzzzzzz'),
+(4,'zzz'), (3,'zz'), (5,'zzzzzzz'), (3,'zzz'), (4,'zzzzz'), (3,'zz'),
+(9,'zzzzzz'), (2,'zzzz'), (1,'zzz'), (9,'z'), (1,'z'), (5,'zzzzzz'),
+(4,'z'), (3,'zzz'), (5,'zzzzz'), (3,'z'), (4,'zzz'), (3,'zzzz'),
+(9,'zzzzz'), (2,'zzz'), (1,'zzzz'), (9,'zzz'), (1,'zzzz'), (5,'zzzzz'),
+(4,'zzz'), (3,'zzzz'), (5,'zzzz'), (3,'zzz'), (4,'zz'), (3,'zzzzz');
+SET SESSION optimizer_switch='index_condition_pushdown=off';
+EXPLAIN SELECT * from t1,t2,t3 WHERE t3.a3=t1.a1 AND t2.a2=t1.a1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	idx	NULL	NULL	NULL	3	
+1	SIMPLE	t2	ref	idx	idx	4	test.t1.a1	2	
+1	SIMPLE	t3	ref	idx	idx	4	test.t1.a1	5	
+EXPLAIN SELECT * FROM t1,t2,t3 WHERE t2.a2=t1.a1 AND t3.a3=t1.a1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	idx	NULL	NULL	NULL	3	
+1	SIMPLE	t2	ref	idx	idx	4	test.t1.a1	2	
+1	SIMPLE	t3	ref	idx	idx	4	test.t1.a1	5	
+EXPLAIN SELECT * FROM t1,t2,t3 WHERE t2.a2=t1.a1 AND t3.a3=t2.a2;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	idx	NULL	NULL	NULL	3	
+1	SIMPLE	t2	ref	idx	idx	4	test.t1.a1	2	
+1	SIMPLE	t3	ref	idx	idx	4	test.t1.a1	5	
+SELECT * from t1,t2,t3
+WHERE t3.a3=t1.a1 AND t2.a2=t1.a1 AND
+LENGTH(CONCAT(CONCAT(t1.b1,t2.b2),t3.b3)) <= 7;
+a1	b1	a2	b2	a3	b3
+2	xx	2	y	2	zz
+2	xx	2	y	2	zzzz
+2	xx	2	y	2	zzz
+2	xx	2	yy	2	zz
+2	xx	2	yy	2	zzz
+1	xxx	1	yy	1	z
+1	xxx	1	yy	1	zz
+1	xxx	1	yy	1	zz
+1	xxx	1	yy	1	z
+1	xxx	1	y	1	z
+1	xxx	1	y	1	zz
+1	xxx	1	y	1	zz
+1	xxx	1	y	1	zzz
+1	xxx	1	y	1	zzz
+1	xxx	1	y	1	z
+1	xxx	1	yyy	1	z
+1	xxx	1	yyy	1	z
+SELECT * FROM t1,t2,t3
+WHERE t2.a2=t1.a1 AND t3.a3=t1.a1 AND 
+LENGTH(CONCAT(CONCAT(t1.b1,t2.b2),t3.b3)) <= 7;
+a1	b1	a2	b2	a3	b3
+2	xx	2	y	2	zz
+2	xx	2	y	2	zzzz
+2	xx	2	y	2	zzz
+2	xx	2	yy	2	zz
+2	xx	2	yy	2	zzz
+1	xxx	1	yy	1	z
+1	xxx	1	yy	1	zz
+1	xxx	1	yy	1	zz
+1	xxx	1	yy	1	z
+1	xxx	1	y	1	z
+1	xxx	1	y	1	zz
+1	xxx	1	y	1	zz
+1	xxx	1	y	1	zzz
+1	xxx	1	y	1	zzz
+1	xxx	1	y	1	z
+1	xxx	1	yyy	1	z
+1	xxx	1	yyy	1	z
+SELECT * FROM t1,t2,t3
+WHERE t2.a2=t1.a1 AND t3.a3=t2.a2 AND
+LENGTH(CONCAT(CONCAT(t1.b1,t2.b2),t3.b3)) <= 7;
+a1	b1	a2	b2	a3	b3
+2	xx	2	y	2	zz
+2	xx	2	y	2	zzzz
+2	xx	2	y	2	zzz
+2	xx	2	yy	2	zz
+2	xx	2	yy	2	zzz
+1	xxx	1	yy	1	z
+1	xxx	1	yy	1	zz
+1	xxx	1	yy	1	zz
+1	xxx	1	yy	1	z
+1	xxx	1	y	1	z
+1	xxx	1	y	1	zz
+1	xxx	1	y	1	zz
+1	xxx	1	y	1	zzz
+1	xxx	1	y	1	zzz
+1	xxx	1	y	1	z
+1	xxx	1	yyy	1	z
+1	xxx	1	yyy	1	z
+SET SESSION optimizer_switch=DEFAULT;
+DROP TABLE t1,t2,t3;
 End of 5.1 tests