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.


mysql-test/r/order_by.result:
  Test case for bug #38745.
mysql-test/t/order_by.test:
  Test case for bug #38745.
sql/item.h:
  Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
              when it should use index
  
  Item::is_outer_field() has been added and overloaded for
  Item_field and Item_ref classes.
sql/item_cmpfunc.cc:
  Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
              when it should use index
  
  Item_equal::update_const() and Item_equal::update_used_tables()
  have been updated to not take into account the constantness
  of outer-joined table items.

2 files changed, 32 insertions, 2 deletions

diff --git a/sql/item.h b/sql/item.h
index 6398e9bffb7..e441a6ff261 100644
--- a/sql/item.h
+++ b/sql/item.h
@@ -1181,6 +1181,10 @@ public:
     collation.set(&my_charset_numeric, DERIVATION_NUMERIC, MY_REPERTOIRE_ASCII);
     fix_char_length(max_char_length_arg);
   }
+  /*
+    Return TRUE if the item points to a column of an outer-joined table.
+  */
+  virtual bool is_outer_field() const { DBUG_ASSERT(fixed); return FALSE; }
 };
 
 
@@ -1694,6 +1698,11 @@ public:
   int fix_outer_field(THD *thd, Field **field, Item **reference);
   virtual Item *update_value_transformer(uchar *select_arg);
   virtual void print(String *str, enum_query_type query_type);
+  bool is_outer_field() const
+  {
+    DBUG_ASSERT(fixed);
+    return field->table->pos_in_table_list->outer_join;
+  }
   Field::geometry_type get_geometry_type() const
   {
     DBUG_ASSERT(field_type() == MYSQL_TYPE_GEOMETRY);
@@ -2507,6 +2516,12 @@ public:
     return (*ref)->get_time(ltime);
   }
   virtual bool basic_const_item() const { return (*ref)->basic_const_item(); }
+  bool is_outer_field() const
+  {
+    DBUG_ASSERT(fixed);
+    DBUG_ASSERT(ref);
+    return (*ref)->is_outer_field();
+  }
 
 };
 
diff --git a/sql/item_cmpfunc.cc b/sql/item_cmpfunc.cc
index 19e8385539f..3c871bc0663 100644
--- a/sql/item_cmpfunc.cc
+++ b/sql/item_cmpfunc.cc
@@ -5466,7 +5466,21 @@ void Item_equal::update_const()
   Item *item;
   while ((item= it++))
   {
-    if (item->const_item())
+    if (item->const_item() &&
+        /*
+          Don't propagate constant status of outer-joined column.
+          Such a constant status here is a result of:
+            a) empty outer-joined table: in this case such a column has a
+               value of NULL; but at the same time other arguments of
+               Item_equal don't have to be NULLs and the value of the whole
+               multiple equivalence expression doesn't have to be NULL or FALSE
+               because of the outer join nature;
+          or
+            b) outer-joined table contains only 1 row: the result of
+               this column is equal to a row field value *or* NULL.
+          Both values are inacceptable as Item_equal constants.
+        */
+        !item->is_outer_field())
     {
       it.remove();
       add(item);
@@ -5505,7 +5519,8 @@ void Item_equal::update_used_tables()
   {
     item->update_used_tables();
     used_tables_cache|= item->used_tables();
-    const_item_cache&= item->const_item();
+    /* see commentary at Item_equal::update_const() */
+    const_item_cache&= item->const_item() && !item->is_outer_field();
   }
 }