Many files:

  After review fixes for Item_equal.


sql/item.cc:
  After review fixes for Item_equal.
sql/item.h:
  After review fixes for Item_equal.
sql/item_cmpfunc.cc:
  After review fixes for Item_equal.
sql/item_cmpfunc.h:
  After review fixes for Item_equal.
sql/item_func.h:
  After review fixes for Item_equal.
sql/item_func.cc:
  After review fixes for Item_equal.
sql/item_row.cc:
  After review fixes for Item_equal.
sql/item_row.h:
  After review fixes for Item_equal.
sql/item_strfunc.h:
  After review fixes for Item_equal.
sql/opt_range.cc:
  After review fixes for Item_equal.
sql/sql_list.h:
  After review fixes for Item_equal.
sql/sql_select.cc:
  After review fixes for Item_equal.
mysql-test/r/select.result:
  After review fixes for Item_equal.
mysql-test/r/subselect.result:
  After review fixes for Item_equal.

1 files changed, 87 insertions, 8 deletions

diff --git a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h
index 9d567bbc01b..d7cd0d93588 100644
--- a/sql/item_cmpfunc.h
+++ b/sql/item_cmpfunc.h
@@ -20,6 +20,9 @@
 #ifdef __GNUC__
 #pragma interface			/* gcc class implementation */
 #endif
+#ifdef __GNUC__
+template class List_iterator_fast<Item_field>;
+#endif
 
 extern Item_result item_cmp_type(Item_result a,Item_result b);
 class Item_bool_func2;
@@ -27,6 +30,8 @@ class Arg_comparator;
 
 typedef int (Arg_comparator::*arg_cmp_func)();
 
+typedef int (*Item_field_cmpfunc)(Item_field *f1, Item_field *f2, void *arg); 
+
 class Arg_comparator: public Sql_alloc
 {
   Item **a, **b;
@@ -890,6 +895,7 @@ public:
     :Item_bool_func(), list(nlist), abort_on_null(0) {}
   ~Item_cond() { list.delete_elements(); }
   bool add(Item *item) { return list.push_back(item); }
+  void add_at_head(List<Item> *nlist) { list.prepand(nlist); }
   bool fix_fields(THD *, struct st_table_list *, Item **ref);
 
   enum Type type() const { return COND_ITEM; }
@@ -902,11 +908,75 @@ public:
   void top_level_item() { abort_on_null=1; }
   void copy_andor_arguments(THD *thd, Item_cond *item);
   bool walk(Item_processor processor, byte *arg);
-  Item *traverse(Item_calculator calculator, byte *arg);
+  Item *transform(Item_transformer transformer, byte *arg);
   void neg_arguments();
 };
 
 
+/*
+  The class Item_equal is used to represent conjuctions of equality
+  predicates of the form field1 = field2, and field=const in where
+  conditions and on expressions.
+ 
+  All equality predicates of the form field1=field2 contained in a 
+  conjuction are substituted for a sequence of items of this class.
+  An item of this class Item_equal(f1,f2,...fk) respresents a
+  multiple equality f1=f2=...=fk.
+
+  If a conjuction contains predicates f1=f2 and f2=f3, a new item of
+  this class is created Item_equal(f1,f2,f3) representing the multiple
+  equality f1=f2=f3 that substitutes the above equality predicates in
+  the conjuction.
+  A conjuction of the predicates f2=f1 and f3=f1 and f3=f2 will be
+  substituted for the item representing the same multiple equality
+  f1=f2=f3.
+  An item Item_equal(f1,f2) can appear instead of a conjuction of 
+  f2=f1 and f1=f2, or instead of just the predicate f1=f2.
+
+  An item of the class Item_equal inherites equalities from outer 
+  conjunctive levels.
+
+  Suppose we have a where condition of the following form:
+  WHERE f1=f2 AND f3=f4 AND f3=f5 AND ... AND (...OR (f1=f3 AND ...)).
+  In this case:
+    f1=f2 will be substituted for Item_equal(f1,f2);
+    f3=f4 and f3=f5  will be substituted for Item_equal(f3,f4,f5);
+    f1=f3 will be substituted for Item_equal(f1,f2,f3,f4,f5);
+
+  An object of the class Item_equal can contain an optional constant
+  item c. Thenit represents a multiple equality of the form 
+  c=f1=...=fk.
+
+  Objects of the class Item_equal are used for the following:
+
+  1. An object Item_equal(t1.f1,...,tk.fk) allows us to consider any
+  pair of tables ti and tj as joined by an equi-condition.
+  Thus it provide us with additional access paths from table to table.
+
+  2. An object Item_equal(t1.f1,...,tk.fk) is applied to deduce new
+  SARGable predicates:
+    f1=...=fk AND P(fi) => f1=...=fk AND P(fi) AND P(fj).
+  It also can give us additional index scans and can allow us to
+  improve selectivity estimates.
+
+  3. An object Item_equal(t1.f1,...,tk.fk) is used to optimize the 
+  selected execution plan for the query: if table ti is accessed 
+  before the table tj then in any predicate P in the where condition
+  the occurence of tj.fj is substituted for ti.fi. This can allow
+  an evaluation of the predicate at an earlier step.
+
+  When feature 1 is supported they say that join transitive closure 
+  is employed.
+  When feature 2 is supported they say that search argument transitive
+  closure is employed.
+  Both features are usually supported by preprocessing original query and
+  adding additional predicates.
+  We do not just add predicates, we rather dynamically replace some
+  predicates that can not be used to access tables in the investigated
+  plan for those, obtained by substitution of some fields for equal fields,
+  that can be used.     
+*/
+
 class Item_equal: public Item_bool_func
 {
   List<Item_field> fields; /* list of equal field items                    */
@@ -924,7 +994,7 @@ public:
   inline Item* get_const() { return const_item; }
   void add(Item *c);
   void add(Item_field *f);
-  bool is_false() { return cond_false; }
+  uint members();
   bool contains(Field *field);
   Item_field* get_first() { return fields.head(); }
   void merge(Item_equal *item);
@@ -932,22 +1002,29 @@ public:
   longlong val_int(); 
   const char *func_name() const { return "multiple equal"; }
   optimize_type select_optimize() const { return OPTIMIZE_EQUAL; }
-  void sort(void *table_join_idx);
+  void sort(Item_field_cmpfunc cmp, void *arg);
   friend class Item_equal_iterator;
   void fix_length_and_dec();
   bool fix_fields(THD *thd, TABLE_LIST *tables, Item **ref);
   void update_used_tables();
   bool walk(Item_processor processor, byte *arg);
-  Item *traverse(Item_calculator calculator, byte *arg);
+  Item *transform(Item_transformer transformer, byte *arg);
   void print(String *str);
 }; 
 
 class COND_EQUAL
 {
 public:
-  COND_EQUAL *parent_level;
-  List<Item_equal> current_level;
-  COND_EQUAL() { parent_level= 0; }
+  uint max_members;               /* max number of members the current level
+                                     list and all lower level lists */ 
+  COND_EQUAL *upper_levels;       /* multiple equalities of upper and levels */
+  List<Item_equal> current_level; /* list of multiple equalities of 
+                                     the current and level           */
+  COND_EQUAL()
+  { 
+    max_members= 0;
+    upper_levels= 0;
+  }
 };
 
 
@@ -971,7 +1048,9 @@ public:
 class Item_cond_and :public Item_cond
 {
 public:
-  COND_EQUAL cond_equal;  
+  COND_EQUAL cond_equal;  /* contains list of Item_equal objects for 
+                             the current and level and reference
+                             to multiple equalities of upper and levels */  
   Item_cond_and() :Item_cond() {}
   Item_cond_and(Item *i1,Item *i2) :Item_cond(i1,i2) {}
   Item_cond_and(THD *thd, Item_cond_and &item) :Item_cond(thd, item) {}