MDEV-8989: ORDER BY optimizer ignores equality propagation

Variant #4 of the fix.

Make ORDER BY optimization functions take into account multiple
equalities. This is done in several places:
- remove_const() checks whether we can sort the first table in the
  join, or we need to put rows into temp.table and then sort.
- test_if_order_by_key() checks whether there are indexes that
  can be used to produce the required ordering
- make_unireg_sortorder() constructs sort criteria for filesort.

13 files changed, 414 insertions, 21 deletions

diff --git a/mysql-test/r/compress.result b/mysql-test/r/compress.result
index 83b50351ba9..f61080d8a77 100644
--- a/mysql-test/r/compress.result
+++ b/mysql-test/r/compress.result
@@ -607,7 +607,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.fld1	1	Using where; Using index
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using filesort
 1	SIMPLE	t3	ref	period	period	4	test.t1.period	4181	
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period limit 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
diff --git a/mysql-test/r/order_by.result b/mysql-test/r/order_by.result
index a015819e480..3e4a2ce3643 100644
--- a/mysql-test/r/order_by.result
+++ b/mysql-test/r/order_by.result
@@ -2987,3 +2987,144 @@ EXPLAIN SELECT id1 FROM t2 WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ref	id_23_date,id_234_date	id_23_date	2	const,const	3	Using where
 drop table t1,t2;
+#
+# MDEV-8989: ORDER BY optimizer ignores equality propagation
+#
+create table t0(a int);
+insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t1(a int);
+insert into t1 select A.a + B.a* 10 + C.a * 100 from t0 A, t0 B, t0 C;
+create table t2 (
+pk int primary key, 
+a int, b int, 
+filler char(200), 
+key(a)
+);
+insert into t2 select a, 1000-a, 1000-a, repeat('abc-',50) from t1 where a<200 limit 200;
+create table t3 (
+pk int primary key, 
+a int, b int, 
+filler char(200), 
+key(a)
+);
+insert into t3 select a,      1000-a, 1000-a, repeat('abc-',50) from t1;
+insert into t3 select a+1000, 1000+a, 1000+a, repeat('abc-',50) from t1;
+# The optimizer produces an order of 't2,t3' for this join
+#
+# Case #1 (from the bug report): 
+#  Q1 can take advantage of t2.a to resolve ORDER BY limit w/o sorting
+explain
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t2.a limit 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	index	a	a	5	NULL	5	Using where
+1	SIMPLE	t3	ref	a	a	5	test.t2.a	1	
+# 
+# This is Q2 which used to have "Using temporary; using filesort" but
+#   has the same query plan as Q1:
+# 
+explain
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t3.a limit 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	index	a	a	5	NULL	5	Using where
+1	SIMPLE	t3	ref	a	a	5	test.t2.a	1	
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t2.a limit 5;
+pk	a	b	pk	a	b
+199	801	801	199	801	801
+198	802	802	198	802	802
+197	803	803	197	803	803
+196	804	804	196	804	804
+195	805	805	195	805	805
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t3.a limit 5;
+pk	a	b	pk	a	b
+199	801	801	199	801	801
+198	802	802	198	802	802
+197	803	803	197	803	803
+196	804	804	196	804	804
+195	805	805	195	805	805
+# 
+# Case #2: here, only "Using temporary" is removed. "Using filesort" remains.
+# 
+explain
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t2.a limit 25;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	a	NULL	NULL	NULL	200	Using where; Using filesort
+1	SIMPLE	t3	ref	a	a	5	test.t2.a	1	
+explain
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t3.a limit 25;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	a	NULL	NULL	NULL	200	Using where; Using filesort
+1	SIMPLE	t3	ref	a	a	5	test.t2.a	1	
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t2.a limit 25;
+pk	a	b	pk	a	b
+199	801	801	199	801	801
+198	802	802	198	802	802
+197	803	803	197	803	803
+196	804	804	196	804	804
+195	805	805	195	805	805
+194	806	806	194	806	806
+193	807	807	193	807	807
+192	808	808	192	808	808
+191	809	809	191	809	809
+190	810	810	190	810	810
+189	811	811	189	811	811
+188	812	812	188	812	812
+187	813	813	187	813	813
+186	814	814	186	814	814
+185	815	815	185	815	815
+184	816	816	184	816	816
+183	817	817	183	817	817
+182	818	818	182	818	818
+181	819	819	181	819	819
+180	820	820	180	820	820
+179	821	821	179	821	821
+178	822	822	178	822	822
+177	823	823	177	823	823
+176	824	824	176	824	824
+175	825	825	175	825	825
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t3.a limit 25;
+pk	a	b	pk	a	b
+199	801	801	199	801	801
+198	802	802	198	802	802
+197	803	803	197	803	803
+196	804	804	196	804	804
+195	805	805	195	805	805
+194	806	806	194	806	806
+193	807	807	193	807	807
+192	808	808	192	808	808
+191	809	809	191	809	809
+190	810	810	190	810	810
+189	811	811	189	811	811
+188	812	812	188	812	812
+187	813	813	187	813	813
+186	814	814	186	814	814
+185	815	815	185	815	815
+184	816	816	184	816	816
+183	817	817	183	817	817
+182	818	818	182	818	818
+181	819	819	181	819	819
+180	820	820	180	820	820
+179	821	821	179	821	821
+178	822	822	178	822	822
+177	823	823	177	823	823
+176	824	824	176	824	824
+175	825	825	175	825	825
+#
+# Case #3: single table access (the code that decides whether we need
+#          "Using temporary" is not invoked)
+#
+explain select * from t3 where b=a order by a limit 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t3	index	NULL	a	5	NULL	10	Using where
+# This must not use filesort. The query plan should be like the query above:
+explain select * from t3 where b=a order by b limit 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t3	index	NULL	a	5	NULL	10	Using where
+drop table t0,t1,t2,t3;
diff --git a/mysql-test/r/pool_of_threads.result b/mysql-test/r/pool_of_threads.result
index 9611d7ff43b..ab2ba2eab35 100644
--- a/mysql-test/r/pool_of_threads.result
+++ b/mysql-test/r/pool_of_threads.result
@@ -603,7 +603,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.fld1	1	Using where; Using index
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using filesort
 1	SIMPLE	t3	ref	period	period	4	test.t1.period	4181	
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period limit 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
diff --git a/mysql-test/r/select.result b/mysql-test/r/select.result
index 9dbf6e0c46b..9c4429caaf5 100644
--- a/mysql-test/r/select.result
+++ b/mysql-test/r/select.result
@@ -606,7 +606,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.fld1	1	Using where; Using index
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using filesort
 1	SIMPLE	t3	ref	period	period	4	test.t1.period	4181	
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period limit 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
diff --git a/mysql-test/r/select_pkeycache.result b/mysql-test/r/select_pkeycache.result
index 9dbf6e0c46b..9c4429caaf5 100644
--- a/mysql-test/r/select_pkeycache.result
+++ b/mysql-test/r/select_pkeycache.result
@@ -606,7 +606,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.fld1	1	Using where; Using index
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using filesort
 1	SIMPLE	t3	ref	period	period	4	test.t1.period	4181	
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period limit 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
diff --git a/mysql-test/r/ssl.result b/mysql-test/r/ssl.result
index 57427a228eb..a8c7358dd90 100644
--- a/mysql-test/r/ssl.result
+++ b/mysql-test/r/ssl.result
@@ -610,7 +610,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.fld1	1	Using where; Using index
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using filesort
 1	SIMPLE	t3	ref	period	period	4	test.t1.period	4181	
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period limit 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
diff --git a/mysql-test/r/ssl_compress.result b/mysql-test/r/ssl_compress.result
index 31f484ab58c..10f3ef729cd 100644
--- a/mysql-test/r/ssl_compress.result
+++ b/mysql-test/r/ssl_compress.result
@@ -607,7 +607,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.fld1	1	Using where; Using index
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	period	NULL	NULL	NULL	41810	Using filesort
 1	SIMPLE	t3	ref	period	period	4	test.t1.period	4181	
 explain select * from t3 as t1,t3 where t1.period=t3.period order by t3.period limit 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
diff --git a/mysql-test/t/order_by.test b/mysql-test/t/order_by.test
index bdd6f3b825f..7f53f994721 100644
--- a/mysql-test/t/order_by.test
+++ b/mysql-test/t/order_by.test
@@ -1997,3 +1997,81 @@ EXPLAIN SELECT id1 FROM t2 WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4;
 
 drop table t1,t2;
 
+--echo #
+--echo # MDEV-8989: ORDER BY optimizer ignores equality propagation
+--echo #
+create table t0(a int);
+insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+
+create table t1(a int);
+insert into t1 select A.a + B.a* 10 + C.a * 100 from t0 A, t0 B, t0 C;
+
+create table t2 (
+  pk int primary key, 
+  a int, b int, 
+  filler char(200), 
+  key(a)
+);
+insert into t2 select a, 1000-a, 1000-a, repeat('abc-',50) from t1 where a<200 limit 200;
+
+create table t3 (
+  pk int primary key, 
+  a int, b int, 
+  filler char(200), 
+  key(a)
+);
+insert into t3 select a,      1000-a, 1000-a, repeat('abc-',50) from t1;
+insert into t3 select a+1000, 1000+a, 1000+a, repeat('abc-',50) from t1;
+
+--echo # The optimizer produces an order of 't2,t3' for this join
+--echo #
+--echo # Case #1 (from the bug report): 
+--echo #  Q1 can take advantage of t2.a to resolve ORDER BY limit w/o sorting
+explain
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t2.a limit 5;
+
+--echo # 
+--echo # This is Q2 which used to have "Using temporary; using filesort" but
+--echo #   has the same query plan as Q1:
+--echo # 
+explain
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t3.a limit 5; 
+
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t2.a limit 5;
+
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t3.a limit 5;
+
+
+--echo # 
+--echo # Case #2: here, only "Using temporary" is removed. "Using filesort" remains.
+--echo # 
+explain
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t2.a limit 25;
+
+explain
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t3.a limit 25; 
+
+
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t2.a limit 25;
+
+
+select t2.pk,t2.a,t2.b,t3.pk,t3.a,t3.b 
+from t2, t3 where t2.a=t3.a order by t3.a limit 25; 
+
+--echo #
+--echo # Case #3: single table access (the code that decides whether we need
+--echo #          "Using temporary" is not invoked)
+--echo #
+explain select * from t3 where b=a order by a limit 10;
+
+--echo # This must not use filesort. The query plan should be like the query above:
+explain select * from t3 where b=a order by b limit 10;
+drop table t0,t1,t2,t3;
+
diff --git a/sql/sql_delete.cc b/sql/sql_delete.cc
index f49a053918b..e077073c2df 100644
--- a/sql/sql_delete.cc
+++ b/sql/sql_delete.cc
@@ -499,7 +499,7 @@ bool mysql_delete(THD *thd, TABLE_LIST *table_list, COND *conds,
       Filesort_tracker *fs_tracker= 
         thd->lex->explain->get_upd_del_plan()->filesort_tracker;
 
-      if (!(sortorder= make_unireg_sortorder(thd, order, &length, NULL)) ||
+      if (!(sortorder= make_unireg_sortorder(thd, NULL, 0, order, &length, NULL)) ||
 	  (table->sort.found_records= filesort(thd, table, sortorder, length,
                                                select, HA_POS_ERROR,
                                                true,
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index f59a1591296..a278183d5fd 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -12327,7 +12327,53 @@ remove_const(JOIN *join,ORDER *first_order, COND *cond,
 	    DBUG_PRINT("info",("removing: %s", order->item[0]->full_name()));
 	    continue;
 	  }
-	  *simple_order=0;			// Must do a temp table to sort
+          /*
+            UseMultipleEqualitiesToRemoveTempTable:
+            Can use multiple-equalities here to check that ORDER BY columns
+            can be used without tmp. table.
+          */
+          bool can_subst_to_first_table= false;
+          if (first_is_base_table &&
+              order->item[0]->real_item()->type() == Item::FIELD_ITEM &&
+              join->cond_equal)
+          {
+            table_map first_table_bit=
+              join->join_tab[join->const_tables].table->map;
+
+            Item *item= order->item[0];
+
+            /* 
+              We are using Context_identity below. This means only do
+              substitution when equality means
+            */
+            Item *res= item->propagate_equal_fields(join->thd,
+                                                    Value_source::
+                                                    Context_identity(),
+                                                    join->cond_equal);
+            if (res != item)
+            {
+              /* Substituted to a constant */
+              can_subst_to_first_table= true;
+            }
+            else
+            {
+              Item_equal *item_eq= item->get_item_equal();
+              if (item_eq)
+              {
+                Item *first= item_eq->get_first(NO_PARTICULAR_TAB, NULL);
+                if (first->const_item() || first->used_tables() ==
+                                           first_table_bit)
+                {
+                  can_subst_to_first_table= true;
+                }
+              }
+            }
+          }
+
+          if (!can_subst_to_first_table)
+          {
+            *simple_order=0;			// Must do a temp table to sort
+          }
 	}
       }
     }
@@ -20327,6 +20373,8 @@ part_of_refkey(TABLE *table,Field *field)
 /**
   Test if one can use the key to resolve ORDER BY.
 
+  @param join                  if not NULL, can use the join's top-level
+                               multiple-equalities.
   @param order                 Sort order
   @param table                 Table to sort
   @param idx                   Index to check
@@ -20349,7 +20397,8 @@ part_of_refkey(TABLE *table,Field *field)
     -1   Reverse key can be used
 */
 
-static int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
+static int test_if_order_by_key(JOIN *join,
+                                ORDER *order, TABLE *table, uint idx,
 				uint *used_key_parts= NULL)
 {
   KEY_PART_INFO *key_part,*key_part_end;
@@ -20372,7 +20421,8 @@ static int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
 
   for (; order ; order=order->next, const_key_parts>>=1)
   {
-    Field *field=((Item_field*) (*order->item)->real_item())->field;
+    Item_field *item_field= ((Item_field*) (*order->item)->real_item());
+    Field *field= item_field->field;
     int flag;
 
     /*
@@ -20414,6 +20464,17 @@ static int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
       DBUG_RETURN(0);
     }
 
+    if (key_part->field != field)
+    {
+      /*
+        Check if there is a multiple equality that allows to infer that field
+        and key_part->field are equal 
+        (see also: compute_part_of_sort_key_for_equals)
+      */
+      if (item_field->item_equal && 
+          item_field->item_equal->contains(key_part->field))
+        field= key_part->field;
+    }
     if (key_part->field != field || !field->part_of_sortkey.is_set(idx))
       DBUG_RETURN(0);
 
@@ -20541,7 +20602,7 @@ test_if_subkey(ORDER *order, TABLE *table, uint ref, uint ref_key_parts,
 	table->key_info[nr].user_defined_key_parts >= ref_key_parts &&
 	is_subkey(table->key_info[nr].key_part, ref_key_part,
 		  ref_key_part_end) &&
-	test_if_order_by_key(order, table, nr))
+	test_if_order_by_key(NULL, order, table, nr))
     {
       min_length= table->key_info[nr].key_length;
       best= nr;
@@ -20680,6 +20741,68 @@ find_field_in_item_list (Field *field, void *data)
 }
 
 
+/*
+  Fill *col_keys with a union of Field::part_of_sortkey of all fields
+  that belong to 'table' and are equal to 'item_field'.
+*/
+
+void compute_part_of_sort_key_for_equals(JOIN *join, TABLE *table,
+                                         Item_field *item_field,
+                                         key_map *col_keys)
+{
+  col_keys->clear_all();
+  col_keys->merge(item_field->field->part_of_sortkey);
+
+  Item_equal *item_eq= NULL;
+
+  if (item_field->item_equal)
+  {
+    /* 
+      The item_field is from ORDER structure, but it already has an item_equal
+      pointer set (UseMultipleEqualitiesToRemoveTempTable code have set it)
+    */
+    item_eq= item_field->item_equal;
+  }
+  else
+  {
+    /* 
+      Walk through join's muliple equalities and find the one that contains
+      item_field.
+    */
+    if (!join->cond_equal)
+      return;
+    table_map needed_tbl_map= item_field->used_tables() | table->map;
+    List_iterator<Item_equal> li(join->cond_equal->current_level);
+    Item_equal *cur_item_eq;
+    while ((cur_item_eq= li++))
+    {
+      if ((cur_item_eq->used_tables() & needed_tbl_map) &&
+          cur_item_eq->contains(item_field->field))
+      {
+        item_eq= cur_item_eq;
+        item_field->item_equal= item_eq; // Save the pointer to our Item_equal.
+        break;
+      }
+    }
+  }
+  
+  if (item_eq)
+  {
+    Item_equal_fields_iterator it(*item_eq);
+    Item *item;
+    /* Loop through other members that belong to table table */
+    while ((item= it++))
+    {
+      if (item->type() == Item::FIELD_ITEM &&
+          ((Item_field*)item)->field->table == table)
+      {
+        col_keys->merge(((Item_field*)item)->field->part_of_sortkey);
+      }
+    }
+  }
+}
+
+
 /**
   Test if we can skip the ORDER BY by using an index.
 
@@ -20736,7 +20859,27 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
       usable_keys.clear_all();
       DBUG_RETURN(0);
     }
-    usable_keys.intersect(((Item_field*) item)->field->part_of_sortkey);
+
+    /*
+      Take multiple-equalities into account. Suppose we have
+        ORDER BY col1, col10
+      and there are
+         multiple-equal(col1, col2, col3),
+         multiple-equal(col10, col11).
+
+      Then, 
+      - when item=col1, we find the set of indexes that cover one of {col1,
+        col2, col3}
+      - when item=col10, we find the set of indexes that cover one of {col10,
+        col11}
+
+      And we compute an intersection of these sets to find set of indexes that
+      cover all ORDER BY components.
+    */
+    key_map col_keys;
+    compute_part_of_sort_key_for_equals(tab->join, table, (Item_field*)item,
+                                        &col_keys);
+    usable_keys.intersect(col_keys);
     if (usable_keys.is_clear_all())
       goto use_filesort;                        // No usable keys
   }
@@ -20894,7 +21037,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
     }
     /* Check if we get the rows in requested sorted order by using the key */
     if (usable_keys.is_set(ref_key) &&
-        (order_direction= test_if_order_by_key(order,table,ref_key,
+        (order_direction= test_if_order_by_key(tab->join, order,table,ref_key,
 					       &used_key_parts)))
       goto check_reverse_order;
   }
@@ -21274,8 +21417,11 @@ create_sort_index(THD *thd, JOIN *join, ORDER *order,
   for (ORDER *ord= join->order; ord; ord= ord->next)
     length++;
   if (!(join->sortorder= 
-        make_unireg_sortorder(thd, order, &length, join->sortorder)))
+        make_unireg_sortorder(thd, join, tab->table->map, order, &length,
+                              join->sortorder)))
+  {
     goto err;				/* purecov: inspected */
+  }
 
   table->sort.io_cache=(IO_CACHE*) my_malloc(sizeof(IO_CACHE),
                                              MYF(MY_WME | MY_ZEROFILL|
@@ -21693,7 +21839,9 @@ err:
 }
 
 
-SORT_FIELD *make_unireg_sortorder(THD *thd, ORDER *order, uint *length,
+SORT_FIELD *make_unireg_sortorder(THD *thd, JOIN *join,
+                                  table_map first_table_bit,
+                                  ORDER *order, uint *length,
                                   SORT_FIELD *sortorder)
 {
   uint count;
@@ -21713,7 +21861,30 @@ SORT_FIELD *make_unireg_sortorder(THD *thd, ORDER *order, uint *length,
 
   for (;order;order=order->next,pos++)
   {
-    Item *const item= order->item[0], *const real_item= item->real_item();
+    Item *first= order->item[0];
+    /*
+      It is possible that the query plan is to read table t1, while the
+      sort criteria actually has "ORDER BY t2.col" and the WHERE clause has 
+      a multi-equality(t1.col, t2.col, ...).  
+      The optimizer detects such cases (grep for
+      UseMultipleEqualitiesToRemoveTempTable to see where), but doesn't 
+      perform equality substitution in the order->item. We need to do the
+      substitution here ourselves.
+    */
+    table_map item_map= first->used_tables();
+    if (join && (item_map & ~join->const_table_map) &&
+        !(item_map & first_table_bit) && join->cond_equal &&
+         first->get_item_equal())
+    {
+      /*
+        Ok, this is the case descibed just above. Get the first element of the
+        multi-equality.
+      */
+      Item_equal *item_eq= first->get_item_equal();
+      first= item_eq->get_first(NO_PARTICULAR_TAB, NULL);
+    }
+
+    Item *const item= first, *const real_item= item->real_item();
     pos->field= 0; pos->item= 0;
     if (real_item->type() == Item::FIELD_ITEM)
     {
@@ -25581,7 +25752,8 @@ test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
     uint used_key_parts= 0;
 
     if (keys.is_set(nr) &&
-        (direction= test_if_order_by_key(order, table, nr, &used_key_parts)))
+        (direction= test_if_order_by_key(join, order, table, nr,
+                                         &used_key_parts)))
     {
       /*
         At this point we are sure that ref_key is a non-ordering
@@ -25824,7 +25996,7 @@ uint get_index_for_order(ORDER *order, TABLE *table, SQL_SELECT *select,
     }
 
     uint used_key_parts;
-    switch (test_if_order_by_key(order, table, select->quick->index,
+    switch (test_if_order_by_key(NULL, order, table, select->quick->index,
                                  &used_key_parts)) {
     case 1: // desired order
       *need_sort= FALSE; 
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 3a0baf03c26..89ee63e87b0 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -1821,7 +1821,9 @@ bool error_if_full_join(JOIN *join);
 int report_error(TABLE *table, int error);
 int safe_index_read(JOIN_TAB *tab);
 int get_quick_record(SQL_SELECT *select);
-SORT_FIELD * make_unireg_sortorder(THD *thd, ORDER *order, uint *length,
+SORT_FIELD *make_unireg_sortorder(THD *thd, JOIN *join,
+                                  table_map first_table_map,
+                                  ORDER *order, uint *length,
                                   SORT_FIELD *sortorder);
 int setup_order(THD *thd, Item **ref_pointer_array, TABLE_LIST *tables,
 		List<Item> &fields, List <Item> &all_fields, ORDER *order);
diff --git a/sql/sql_table.cc b/sql/sql_table.cc
index 337fb06d4e4..dae3b7ad827 100644
--- a/sql/sql_table.cc
+++ b/sql/sql_table.cc
@@ -9472,7 +9472,7 @@ copy_data_between_tables(THD *thd, TABLE *from, TABLE *to,
       if (thd->lex->select_lex.setup_ref_array(thd, order_num) ||
           setup_order(thd, thd->lex->select_lex.ref_pointer_array,
                       &tables, fields, all_fields, order) ||
-          !(sortorder= make_unireg_sortorder(thd, order, &length, NULL)) ||
+          !(sortorder= make_unireg_sortorder(thd, NULL, 0, order, &length, NULL)) ||
           (from->sort.found_records= filesort(thd, from, sortorder, length,
                                               NULL, HA_POS_ERROR,
                                               true,
diff --git a/sql/sql_update.cc b/sql/sql_update.cc
index 3c0827bb164..4221025da28 100644
--- a/sql/sql_update.cc
+++ b/sql/sql_update.cc
@@ -567,7 +567,7 @@ int mysql_update(THD *thd,
       Filesort_tracker *fs_tracker= 
         thd->lex->explain->get_upd_del_plan()->filesort_tracker;
 
-      if (!(sortorder=make_unireg_sortorder(thd, order, &length, NULL)) ||
+      if (!(sortorder=make_unireg_sortorder(thd, NULL, 0, order, &length, NULL)) ||
           (table->sort.found_records= filesort(thd, table, sortorder, length,
                                                select, limit,
                                                true,