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.

6 files changed, 114 insertions, 25 deletions

diff --git a/sql/item.cc b/sql/item.cc
index 310e6994c7d..122688198b9 100644
--- a/sql/item.cc
+++ b/sql/item.cc
@@ -4814,7 +4814,8 @@ bool Item_field::set_no_const_sub(uchar *arg)
   Replace an Item_field for an equal Item_field that evaluated earlier
   (if any).
 
-  The function returns a pointer to an item that is taken from
+  If this->item_equal points to some item and coincides with arg then
+  the function returns a pointer to an item that is taken from
   the very beginning of the item_equal list which the Item_field
   object refers to (belongs to) unless item_equal contains  a constant
   item. In this case the function returns this constant item, 
@@ -4822,7 +4823,7 @@ bool Item_field::set_no_const_sub(uchar *arg)
   If the Item_field object does not refer any Item_equal object
   'this' is returned .
 
-  @param arg   a dummy parameter, is not used here
+  @param arg   NULL or points to so some item of the Item_equal type  
 
 
   @note
@@ -4837,7 +4838,7 @@ bool Item_field::set_no_const_sub(uchar *arg)
 
 Item *Item_field::replace_equal_field(uchar *arg)
 {
-  if (item_equal)
+  if (item_equal && item_equal == (Item_equal *) arg)
   {
     Item *const_item= item_equal->get_const();
     if (const_item)
@@ -4848,7 +4849,7 @@ Item *Item_field::replace_equal_field(uchar *arg)
       return const_item;
     }
     Item_field *subst= item_equal->get_first(this);
-    if (subst && field->table != subst->field->table && !field->eq(subst->field))
+    if (subst && !field->eq(subst->field))
       return subst;
   }
   return this;
diff --git a/sql/item_cmpfunc.cc b/sql/item_cmpfunc.cc
index 0b89adb75e8..32641a7ea3b 100644
--- a/sql/item_cmpfunc.cc
+++ b/sql/item_cmpfunc.cc
@@ -5521,6 +5521,7 @@ Item_equal::Item_equal(Item_field *f1, Item_field *f2)
   const_item_cache= 0;
   fields.push_back(f1);
   fields.push_back(f2);
+  f1->item_equal= f2->item_equal= this;
 }
 
 Item_equal::Item_equal(Item *c, Item_field *f)
@@ -5598,6 +5599,7 @@ void Item_equal::add(Item *c)
 void Item_equal::add(Item_field *f)
 {
   fields.push_back(f);
+  f->item_equal= this;
 }
 
 uint Item_equal::members()
@@ -5668,7 +5670,7 @@ void Item_equal::merge(Item_equal *item)
   If cmp(item_field1,item_field2,arg)<0 than item_field1 must be
   placed after item_fiel2.
 
-  The function sorts field items by the exchange sort algorithm.
+  The function sorts field items by the bubble sort algorithm.
   The list of field items is looked through and whenever two neighboring
   members follow in a wrong order they are swapped. This is performed
   again and again until we get all members in a right order.
@@ -5679,7 +5681,7 @@ void Item_equal::merge(Item_equal *item)
 
 void Item_equal::sort(Item_field_cmpfunc compare, void *arg)
 {
-  exchange_sort<Item_field>(&fields, compare, arg);
+  bubble_sort<Item_field>(&fields, compare, arg);
 }
 
 
diff --git a/sql/opt_table_elimination.cc b/sql/opt_table_elimination.cc
index be1471b7e2c..7497395d628 100644
--- a/sql/opt_table_elimination.cc
+++ b/sql/opt_table_elimination.cc
@@ -1232,7 +1232,7 @@ void build_eq_mods_for_cond(Dep_analysis_context *ctx,
     if (fvl->elements)
     {
       
-      exchange_sort<Dep_value_field>(fvl, compare_field_values, NULL);
+      bubble_sort<Dep_value_field>(fvl, compare_field_values, NULL);
       add_module_expr(ctx, eq_mod, *and_level, NULL, bound_item, fvl);
     }
     break;
diff --git a/sql/sql_list.h b/sql/sql_list.h
index 76b3145f24d..2dade14f211 100644
--- a/sql/sql_list.h
+++ b/sql/sql_list.h
@@ -515,36 +515,40 @@ public:
 
 
 /*
-  Exchange sort algorithm for List<T>.
+  Bubble sort algorithm for List<T>.
+  This sort function is supposed to be used only for very short list.
+  Currently it is used for the lists of Item_equal objects and
+  for some lists in the table elimination algorithms. In both
+  cases the sorted lists are very short.
 */
+
 template <class T> 
-inline void exchange_sort(List<T> *list_to_sort,
-                          int (*sort_func)(T *a, T *b, void *arg), void *arg)
+inline void bubble_sort(List<T> *list_to_sort,
+                        int (*sort_func)(T *a, T *b, void *arg), void *arg)
 {
   bool swap;
+  T **ref1= 0;
+  T **ref2= 0;
   List_iterator<T> it(*list_to_sort);
   do
   {
+    T **last_ref= ref1;
     T *item1= it++;
-    T **ref1= it.ref();
+    ref1= it.ref();
     T *item2;
 
     swap= FALSE;
-    while ((item2= it++))
+    while ((item2= it++) && (ref2= it.ref()) != last_ref)
     {
-      T **ref2= it.ref();
       if (sort_func(item1, item2, arg) < 0)
       {
-        T *item= *ref1;
-        *ref1= *ref2;
-        *ref2= item;
+        *ref1= item2;
+        *ref2= item1;
         swap= TRUE;
       }
       else
-      {
         item1= item2;
-        ref1= ref2;
-      }
+      ref1= ref2;
     }
     it.rewind();
   } while (swap);
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index c0360828f3c..b164daee8d8 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -1036,7 +1036,7 @@ JOIN::optimize()
   }
 
   /*
-    Permorm the the optimization on fields evaluation mentioned above
+    Perform the optimization on fields evaluation mentioned above
     for all on expressions.
   */ 
   for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
@@ -1048,8 +1048,38 @@ JOIN::optimize()
                                                          map2table);
       (*tab->on_expr_ref)->update_used_tables();
     }
+
+    
   }
 
+  /*
+    Perform the optimization on fields evaliation mentioned above
+    for all used ref items.
+  */
+  for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables; tab++)
+  {
+    for (uint i=0; i < tab->ref.key_parts; i++)
+    {
+      
+      Item **ref_item_ptr= tab->ref.items+i;
+      Item *ref_item= *ref_item_ptr;
+      COND_EQUAL *equals= tab->first_inner ? tab->first_inner->cond_equal : 
+	                                     cond_equal;
+      ref_item= substitute_for_best_equal_field(ref_item, equals, map2table);
+      ref_item->update_used_tables();
+      if (*ref_item_ptr != ref_item)
+      {
+        *ref_item_ptr= ref_item;
+        Item *item= ref_item->real_item();
+        if (item->type() == Item::FIELD_ITEM)
+        {
+          store_key_field *key_copy= (store_key_field *) tab->ref.key_copy[i];
+          key_copy->change_source_field((Item_field *) item);
+        }
+      }
+    }
+  }   
+
   if (conds && const_table_map != found_const_table_map &&
       (select_options & SELECT_DESCRIBE))
   {
@@ -9508,10 +9538,14 @@ static COND *build_equal_items(THD *thd, COND *cond,
 /**
   Compare field items by table order in the execution plan.
 
+    If field1 and field2 belong to different tables then
     field1 considered as better than field2 if the table containing
     field1 is accessed earlier than the table containing field2.   
     The function finds out what of two fields is better according
     this criteria.
+    If field1 and field2 belong to the same table then the result
+    of comparison depends on whether the fields are parts of
+    the key that are used to access this table.  
 
   @param field1          first field item to compare
   @param field2          second field item to compare
@@ -9526,8 +9560,8 @@ static COND *build_equal_items(THD *thd, COND *cond,
 */
 
 static int compare_fields_by_table_order(Item_field *field1,
-                                  Item_field *field2,
-                                  void *table_join_idx)
+                                         Item_field *field2,
+                                         void *table_join_idx)
 {
   int cmp= 0;
   bool outer_ref= 0;
@@ -9536,7 +9570,7 @@ static int compare_fields_by_table_order(Item_field *field1,
     outer_ref= 1;
     cmp= -1;
   }
-  if (field2->used_tables() & OUTER_REF_TABLE_BIT)
+  if (field1->used_tables() & OUTER_REF_TABLE_BIT)
   {
     outer_ref= 1;
     cmp++;
@@ -9545,6 +9579,42 @@ static int compare_fields_by_table_order(Item_field *field1,
     return cmp;
   JOIN_TAB **idx= (JOIN_TAB **) table_join_idx;
   cmp= idx[field2->field->table->tablenr]-idx[field1->field->table->tablenr];
+  if (!cmp)
+  {
+    JOIN_TAB *tab= idx[field1->field->table->tablenr];
+    uint keyno= MAX_KEY;
+    if (tab->ref.key_parts)
+      keyno= tab->ref.key;
+    else if (tab->select && tab->select->quick)
+       keyno = tab->select->quick->index;
+    if (keyno != MAX_KEY)
+    {
+      if (field2->field->part_of_key.is_set(keyno))
+        cmp= -1;
+      if (field1->field->part_of_key.is_set(keyno))
+        cmp++;
+      if (!cmp)
+      {
+        KEY *key_info= tab->table->key_info + keyno;
+        for (uint i= 0; i < key_info->key_parts; i++)
+	{
+          Field *fld= key_info->key_part[i].field;
+          if (fld->eq(field2->field))
+	  {
+	    cmp= -1;
+            break;
+          }
+          if (fld->eq(field1->field))
+	  {
+	    cmp= 1;
+            break;
+          }
+        }
+      }              
+    }              
+    else   
+      cmp= field2->field->field_index-field1->field->field_index;
+  }
   return cmp < 0 ? -1 : (cmp ? 1 : 0);
 }
 
@@ -9833,8 +9903,14 @@ static COND* substitute_for_best_equal_field(COND *cond,
     cond= eliminate_item_equal(0, cond_equal, item_equal);
     return cond ? cond : org_cond;
   }
-  else
-    cond->transform(&Item::replace_equal_field, 0);
+  else if (cond_equal)
+  {
+    List_iterator_fast<Item_equal> it(cond_equal->current_level);
+    while((item_equal= it++))
+    {
+      cond= cond->transform(&Item::replace_equal_field, (uchar *) item_equal);
+    }
+  }
   return cond;
 }
 
diff --git a/sql/sql_select.h b/sql/sql_select.h
index ecc19f763fa..8f0feb0e766 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -1071,6 +1071,12 @@ class store_key_field: public store_key
   }
   const char *name() const { return field_name; }
 
+  void change_source_field(Item_field *fld_item)
+  {
+    copy_field.set(to_field, fld_item->field, 0);
+    field_name= fld_item->full_name();
+  }
+
  protected: 
   enum store_key_result copy_inner()
   {