Fix UNION

New faster list iterators
Change list code to be simpler and faster
Optimize count(distinct)
New error messages for UNION
Make create_tmp_table more general to be usable by UNION


Docs/manual.texi:
  Changelog
include/mysqld_error.h:
  Add new error messages needed for UNION
mysql-test/r/union.result:
  New tests for UNION
mysql-test/t/analyse.test:
  Add missing drop table
mysql-test/t/union.test:
  new tests for UNION
sql/Makefile.am:
  Change name of sql_unions.cc to sql_union.cc
sql/item.cc:
  Use List_iterator_fast
sql/item_cmpfunc.cc:
  Use List_iterator_fast
sql/item_func.cc:
  Use List_iterator_fast
sql/item_sum.cc:
  Use List_iterator_fast
  Optimize count(distinct)
  Cleanup of indentation and comments
sql/item_sum.h:
  Optimize count(distinct)
sql/key.cc:
  Use List_iterator_fast
sql/mysql_priv.h:
  Add new option bits
sql/opt_sum.cc:
  Use List_iterator_fast
sql/share/Makefile.am:
  Add 'fix_errors' label
sql/share/czech/errmsg.txt:
  Add new error messages needed for UNION
sql/share/danish/errmsg.txt:
  Add new error messages needed for UNION
sql/share/dutch/errmsg.txt:
  Add new error messages needed for UNION
sql/share/english/errmsg.txt:
  Add new error messages needed for UNION
sql/share/estonian/errmsg.txt:
  Add new error messages needed for UNION
sql/share/french/errmsg.txt:
  Add new error messages needed for UNION
sql/share/german/errmsg.txt:
  Add new error messages needed for UNION
sql/share/greek/errmsg.txt:
  Add new error messages needed for UNION
sql/share/hungarian/errmsg.txt:
  Add new error messages needed for UNION
sql/share/italian/errmsg.txt:
  Add new error messages needed for UNION
sql/share/japanese/errmsg.txt:
  Add new error messages needed for UNION
sql/share/korean/errmsg.txt:
  Add new error messages needed for UNION
sql/share/norwegian-ny/errmsg.txt:
  Add new error messages needed for UNION
sql/share/norwegian/errmsg.txt:
  Add new error messages needed for UNION
sql/share/polish/errmsg.txt:
  Add new error messages needed for UNION
sql/share/portuguese/errmsg.txt:
  Add new error messages needed for UNION
sql/share/romanian/errmsg.txt:
  Add new error messages needed for UNION
sql/share/russian/errmsg.txt:
  Add new error messages needed for UNION
sql/share/slovak/errmsg.txt:
  Add new error messages needed for UNION
sql/share/spanish/errmsg.txt:
  Add new error messages needed for UNION
sql/share/swedish/errmsg.txt:
  Add new error messages needed for UNION
sql/sql_analyse.cc:
  Use List_iterator_fast
sql/sql_base.cc:
  Use List_iterator_fast
  Add new argument to setup_fields
sql/sql_class.cc:
  Use List_iterator_fast
sql/sql_class.h:
  Create new class for UNION
sql/sql_handler.cc:
  Use List_iterator_fast
sql/sql_insert.cc:
  Use List_iterator_fast
sql/sql_lex.h:
  Cleanup
sql/sql_list.cc:
  Faster iteration of lists
sql/sql_list.h:
  Faster iterations of lists
sql/sql_load.cc:
  Use List_iterator_fast
sql/sql_parse.cc:
  Fix UNION code
sql/sql_select.cc:
  Use List_iterator_fast
  Make create_tmp_table more general to be usable by UNION
sql/sql_select.h:
  Changes to speed up copy_fields()
sql/sql_show.cc:
  Use List_iterator_fast
sql/sql_table.cc:
  Use List_iterator_fast
sql/sql_union.cc:
  Fix UNION code
sql/sql_update.cc:
  Use List_iterator_fast
sql/sql_yacc.yy:
  Fix UNION code

1 files changed, 60 insertions, 28 deletions

diff --git a/sql/sql_list.h b/sql/sql_list.h
index b86250f70b6..1486502148f 100644
--- a/sql/sql_list.h
+++ b/sql/sql_list.h
@@ -34,25 +34,40 @@ public:
 /*
 ** basic single linked list
 ** Used for item and item_buffs.
+** All list ends with a pointer to the 'end_of_list' element, which
+** data pointer is a null pointer and the next pointer points to itself.
+** This makes it very fast to traverse lists as we don't have to
+** test for a specialend condition for list that can't contain a null
+** pointer.
 */
 
+class list_node :public Sql_alloc
+{
+public:
+  list_node *next;
+  void *info;
+  list_node(void *info_par,list_node *next_par)
+    :next(next_par),info(info_par)
+    {}
+  list_node()					/* For end_of_list */
+    {
+      info=0;
+      next= this;
+    }
+  friend class base_list;
+  friend class base_list_iterator;
+};
+
+extern list_node end_of_list;
+
 class base_list :public Sql_alloc {
 protected:
-  class list_node :public Sql_alloc
-  {
-  public:
-    list_node *next;
-    void *info;
-    list_node(void *info_par,list_node *next_par) : next(next_par),info(info_par) {}
-    friend class base_list;
-    friend class base_list_iterator;
-  };
   list_node *first,**last;
 
 public:
   uint elements;
 
-  inline void empty() { elements=0; first=0; last=&first;}
+  inline void empty() { elements=0; first= &end_of_list; last=&first;}
   inline base_list() { empty(); }
   inline base_list(const base_list &tmp) :Sql_alloc()
   {
@@ -62,7 +77,7 @@ public:
   }
   inline bool push_back(void *info)
   {
-    if (((*last)=new list_node(info,0)))
+    if (((*last)=new list_node(info, &end_of_list)))
     {
       last= &(*last)->next;
       elements++;
@@ -75,7 +90,7 @@ public:
     list_node *node=new list_node(info,first);
     if (node)
     {
-      if (!first)
+      if (last == &first)
 	last= &node->next;
       first=node;
       elements++;
@@ -89,22 +104,21 @@ public:
     delete *prev;
     *prev=node;
     if (!--elements)
-    {
       last= &first;
-      first=0;
-    }
   }
   inline void *pop(void)
   {
-    if (!first) return 0;
+    if (first == &end_of_list) return 0;
     list_node *tmp=first;
     first=first->next;
     if (!--elements)
       last= &first;
     return tmp->info;
   }
-  inline void *head() { return first ? first->info : 0; }
-  inline void **head_ref() { return first ? &first->info : 0; }
+  inline void *head() { return first->info; }
+  inline void **head_ref() { return first != &end_of_list ? &first->info : 0; }
+  inline bool is_empty() { return first == &end_of_list ; }
+  inline list_node *last_ref() { return &end_of_list; }
   friend class base_list_iterator;
 
 protected:
@@ -122,7 +136,7 @@ protected:
 class base_list_iterator
 {
   base_list *list;
-  base_list::list_node **el,**prev,*current;
+  list_node **el,**prev,*current;
 public:
   base_list_iterator(base_list &list_par) :list(&list_par),el(&list_par.first),
     prev(0),current(0)
@@ -130,16 +144,22 @@ public:
   inline void *next(void)
   {
     prev=el;
-    if (!(current= *el))
-      return 0;
+    current= *el;
     el= &current->next;
     return current->info;
   }
+  inline void *next_fast(void)
+  {
+    list_node *tmp;
+    tmp= *el;
+    el= &tmp->next;
+    return tmp->info;
+  }
   inline void rewind(void)
   {
     el= &list->first;
   }
-  void *replace(void *element)
+  inline void *replace(void *element)
   {						// Return old element
     void *tmp=current->info;
     current->info=element;
@@ -148,7 +168,7 @@ public:
   void *replace(base_list &new_list)
   {
     void *ret_value=current->info;
-    if (new_list.first)
+    if (!new_list.is_empty())
     {
       *new_list.last=current->next;
       current->info=new_list.first->info;
@@ -175,7 +195,7 @@ public:
   }
   inline bool is_last(void)
   {
-    return *el == 0;
+    return el == &list->last_ref()->next;
   }
 };
 
@@ -193,7 +213,7 @@ public:
   void delete_elements(void)
   {
     list_node *element,*next;
-    for (element=first; element ; element=next)
+    for (element=first; element != &end_of_list; element=next)
     {
       next=element->next;
       delete (T*) element->info;
@@ -208,13 +228,25 @@ template <class T> class List_iterator :public base_list_iterator
 public:
   List_iterator(List<T> &a) : base_list_iterator(a) {}
   inline T* operator++(int) { return (T*) base_list_iterator::next(); }
-  inline void rewind(void)  { base_list_iterator::rewind(); }
   inline T *replace(T *a)   { return (T*) base_list_iterator::replace(a); }
   inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
-  inline void remove(void)  { base_list_iterator::remove(); }
   inline void after(T *a)   { base_list_iterator::after(a); }
   inline T** ref(void)	    { return (T**) base_list_iterator::ref(); }
-  inline bool is_last(void) { return base_list_iterator::is_last(); }
+};
+
+template <class T> class List_iterator_fast :public base_list_iterator
+{
+protected:
+  inline T *replace(T *a)   { return (T*) 0; }
+  inline T *replace(List<T> &a) { return (T*) 0; }
+  inline void remove(void)  { }
+  inline void after(T *a)   { }
+  inline T** ref(void)	    { return (T**) 0; }
+
+public:
+  List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
+  inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
+  inline void rewind(void)  { base_list_iterator::rewind(); }
 };