Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY

            when it should use index

Sometimes the LEFT/RIGHT JOIN with an empty table caused an
unnecessary filesort.

Sample query, where t1.i1 is indexed and t3 is empty:

  SELECT t1.*, t2.* FROM t1 JOIN t2 ON t1.i1 = t2.i2
                       LEFT JOIN t3 ON t2.i2 = t3.i3
    ORDER BY t1.i1 LIMIT 5;

The server erroneously used an item of empty outer-joined
table as a common constant of a Item_equal (multi-equivalence
expression).
By the fix for the bug 16590 the constant status of such
an item has been propagated to st_table::const_key_parts
map bits related to other Item_equal argument-related
key parts (those are obviously not constant in our case).
As far as test_if_skip_sort_order function skips constant
prefixes of testing keys, this caused an ignorance of
available indices, since some prefixes were marked as
constant by mistake.

2 files changed, 53 insertions, 0 deletions

diff --git a/mysql-test/r/order_by.result b/mysql-test/r/order_by.result
index 6827fd0bc76..fa5d8142baf 100644
--- a/mysql-test/r/order_by.result
+++ b/mysql-test/r/order_by.result
@@ -1618,3 +1618,32 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	10	Using join buffer
 DROP TABLE t1, t2;
 End of 5.1 tests
+#
+# Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
+#             when it should use index
+#
+CREATE TABLE t1 (i1 integer NOT NULL PRIMARY KEY);
+CREATE TABLE t2 (i2 integer NOT NULL PRIMARY KEY);
+CREATE TABLE t3 (i3 integer);
+INSERT INTO t1 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (11), (12);
+INSERT INTO t2 SELECT * FROM t1;
+EXPLAIN EXTENDED
+SELECT t1.*, t2.* FROM t1 JOIN t2 ON t1.i1 = t2.i2 
+LEFT JOIN t3 ON t2.i2 = t3.i3
+ORDER BY t1.i1 LIMIT 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t3	system	NULL	NULL	NULL	NULL	0	0.00	const row not found
+1	SIMPLE	t1	index	PRIMARY	PRIMARY	4	NULL	5	240.00	Using index
+1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	4	test.t1.i1	1	100.00	Using index
+Warnings:
+Note	1003	select `test`.`t1`.`i1` AS `i1`,`test`.`t2`.`i2` AS `i2` from `test`.`t1` join `test`.`t2` where (`test`.`t2`.`i2` = `test`.`t1`.`i1`) order by `test`.`t1`.`i1` limit 5
+SELECT t1.*, t2.* FROM t1 JOIN t2 ON t1.i1 = t2.i2 
+LEFT JOIN t3 ON t2.i2 = t3.i3
+ORDER BY t1.i1 LIMIT 5;
+i1	i2
+1	1
+2	2
+3	3
+4	4
+5	5
+DROP TABLE t1, t2, t3;
diff --git a/mysql-test/t/order_by.test b/mysql-test/t/order_by.test
index 36b6015c5d8..2ea169d950d 100644
--- a/mysql-test/t/order_by.test
+++ b/mysql-test/t/order_by.test
@@ -1468,3 +1468,27 @@ SELECT * FROM t1 FORCE INDEX FOR JOIN (a), t2 WHERE t1.a < 2 ORDER BY t1.a;
 DROP TABLE t1, t2;
 
 --echo End of 5.1 tests
+
+
+--echo #
+--echo # Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
+--echo #             when it should use index
+--echo #
+
+CREATE TABLE t1 (i1 integer NOT NULL PRIMARY KEY);
+CREATE TABLE t2 (i2 integer NOT NULL PRIMARY KEY);
+CREATE TABLE t3 (i3 integer);
+
+INSERT INTO t1 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (11), (12);
+INSERT INTO t2 SELECT * FROM t1;
+
+EXPLAIN EXTENDED
+SELECT t1.*, t2.* FROM t1 JOIN t2 ON t1.i1 = t2.i2 
+                     LEFT JOIN t3 ON t2.i2 = t3.i3
+  ORDER BY t1.i1 LIMIT 5;
+
+SELECT t1.*, t2.* FROM t1 JOIN t2 ON t1.i1 = t2.i2 
+                     LEFT JOIN t3 ON t2.i2 = t3.i3
+  ORDER BY t1.i1 LIMIT 5;
+
+DROP TABLE t1, t2, t3;