Merge for Item_equal.

BitKeeper/etc/ignore:
  auto-union
mysql-test/r/bdb.result:
  Auto merged
mysql-test/r/func_group.result:
  Auto merged
mysql-test/r/innodb.result:
  Auto merged
mysql-test/r/heap_btree.result:
  Auto merged
mysql-test/r/select.result:
  Auto merged
mysql-test/r/user_var.result:
  Auto merged
mysql-test/t/range.test:
  Auto merged
sql/item_func.cc:
  Auto merged
sql/item_func.h:
  Auto merged
sql/item_row.cc:
  Auto merged
sql/item_strfunc.h:
  Auto merged
sql/opt_sum.cc:
  Auto merged
sql/sql_list.h:
  Auto merged
mysql-test/r/func_test.result:
  Post-automerge resolution of conflicts
mysql-test/r/index_merge.result:
  Post-automerge resolution of conflicts
mysql-test/r/join_outer.result:
  Post-automerge resolution of conflicts
mysql-test/r/range.result:
  Post-automerge resolution of conflicts
mysql-test/r/subselect.result:
  Post-automerge resolution of conflicts
sql/item.cc:
  Post-automerge resolution of conflicts
sql/item.h:
  Post-automerge resolution of conflicts
sql/item_cmpfunc.cc:
  Post-automerge resolution of conflicts
sql/item_cmpfunc.h:
  Post-automerge resolution of conflicts
sql/opt_range.cc:
  Post-automerge resolution of conflicts
sql/sql_select.cc:
  Post-automerge resolution of conflicts
sql/sql_select.h:
  Post-automerge resolution of conflicts

1 files changed, 144 insertions, 0 deletions

diff --git a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h
index e7bef18e629..a8382df20f5 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;
@@ -957,6 +962,7 @@ public:
   Item_cond(List<Item> &nlist)
     :Item_bool_func(), list(nlist), abort_on_null(0) {}
   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; }
@@ -969,13 +975,151 @@ 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 *transform(Item_transformer transformer, byte *arg);
   void neg_arguments(THD *thd);
 };
 
 
+/*
+  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                    */
+  Item *const_item;        /* optional constant item equal to fields items */
+  cmp_item *eval_item;
+  bool cond_false;
+  DTCollation cmp_collation;
+public:
+  inline Item_equal()
+    : Item_bool_func(), const_item(0), eval_item(0), cond_false(0)
+  { const_item_cache=0 ;}
+  Item_equal(Item_field *f1, Item_field *f2);
+  Item_equal(Item *c, Item_field *f);
+  Item_equal(Item_equal *item_equal);
+  inline Item* get_const() { return const_item; }
+  void add(Item *c);
+  void add(Item_field *f);
+  uint members();
+  bool contains(Field *field);
+  Item_field* get_first() { return fields.head(); }
+  void merge(Item_equal *item);
+  enum Functype functype() const { return MULT_EQUAL_FUNC; }
+  longlong val_int(); 
+  const char *func_name() const { return "multiple equal"; }
+  optimize_type select_optimize() const { return OPTIMIZE_EQUAL; }
+  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 *transform(Item_transformer transformer, byte *arg);
+  void print(String *str);
+  CHARSET_INFO *compare_collation() 
+  { return fields.head()->collation.collation; }
+}; 
+
+class COND_EQUAL
+{
+public:
+  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;
+  }
+};
+
+
+class Item_equal_iterator :List_iterator_fast<Item_field>
+{
+public:
+  inline Item_equal_iterator(Item_equal &item_equal) 
+    :List_iterator_fast<Item_field> (item_equal.fields)
+  {}
+  inline Item_field* operator++(int)
+  { 
+    Item_field *item= (*(List_iterator_fast<Item_field> *) this)++;
+    return  item;
+  }
+  inline void rewind(void) 
+  { 
+    List_iterator_fast<Item_field>::rewind();
+  }
+};
+
 class Item_cond_and :public Item_cond
 {
 public:
+  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) {}