Patch for Bug#13805127: Stored program cache produces wrong result in same THD.

Background:

  - as described in MySQL Internals Prepared Stored
    (http://forge.mysql.com/wiki/MySQL_Internals_Prepared_Stored),
    the Optimizer sometimes does destructive changes to the parsed
    LEX-object (Item-tree), which makes it impossible to re-use
    that tree for PS/SP re-execution.

  - in order to be able to re-use the Item-tree, the destructive
    changes are remembered and rolled back after the statement execution.

The problem, discovered by this bug, was that the objects representing
GROUP-BY clause did not restored after query execution. So, the GROUP-BY
part of the statement could not be properly re-initialized for re-execution
after destructive changes.

Those objects do not take part in the Item-tree, so they can not be saved
using the approach for Item-tree.

The fix is as follows:

  - introduce a new array in st_select_lex to store the original
    ORDER pointers, representing the GROUP-BY clause;

  - Initialize this array in fix_prepare_information().

  - restore the list of GROUP-BY items in reinit_stmt_before_use().

4 files changed, 220 insertions, 2 deletions

diff --git a/sql/mem_root_array.h b/sql/mem_root_array.h
new file mode 100644
index 00000000000..5ce4dcb584d
--- /dev/null
+++ b/sql/mem_root_array.h
@@ -0,0 +1,175 @@
+/* Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+
+#ifndef MEM_ROOT_ARRAY_INCLUDED
+#define MEM_ROOT_ARRAY_INCLUDED
+
+#include <my_alloc.h>
+
+/**
+   A typesafe replacement for DYNAMIC_ARRAY.
+   We use MEM_ROOT for allocating storage, rather than the C++ heap.
+   The interface is chosen to be similar to std::vector.
+
+   @remark
+   Unlike DYNAMIC_ARRAY, elements are properly copied
+   (rather than memcpy()d) if the underlying array needs to be expanded.
+
+   @remark
+   Depending on has_trivial_destructor, we destroy objects which are
+   removed from the array (including when the array object itself is destroyed).
+
+   @remark
+   Note that MEM_ROOT has no facility for reusing free space,
+   so don't use this if multiple re-expansions are likely to happen.
+
+   @param Element_type The type of the elements of the container.
+          Elements must be copyable.
+   @param has_trivial_destructor If true, we don't destroy elements.
+          We could have used type traits to determine this.
+          __has_trivial_destructor is supported by some (but not all)
+          compilers we use.
+*/
+template<typename Element_type, bool has_trivial_destructor>
+class Mem_root_array
+{
+public:
+  Mem_root_array(MEM_ROOT *root)
+    : m_root(root), m_array(NULL), m_size(0), m_capacity(0)
+  {
+    DBUG_ASSERT(m_root != NULL);
+  }
+
+  ~Mem_root_array()
+  {
+    clear();
+  }
+
+  Element_type &at(size_t n)
+  {
+    DBUG_ASSERT(n < size());
+    return m_array[n];
+  }
+
+  const Element_type &at(size_t n) const
+  {
+    DBUG_ASSERT(n < size());
+    return m_array[n];
+  }
+
+  // Returns a pointer to the first element in the array.
+  Element_type *begin() { return &m_array[0]; }
+
+  // Returns a pointer to the past-the-end element in the array.
+  Element_type *end() { return &m_array[size()]; }
+
+  // Erases all of the elements. 
+  void clear()
+  {
+    if (!empty())
+      chop(0);
+  }
+
+  /*
+    Chops the tail off the array, erasing all tail elements.
+    @param pos Index of first element to erase.
+  */
+  void chop(const size_t pos)
+  {
+    DBUG_ASSERT(pos < m_size);
+    if (!has_trivial_destructor)
+    {
+      for (size_t ix= pos; ix < m_size; ++ix)
+      {
+        Element_type *p= &m_array[ix];
+        p->~Element_type();              // Destroy discarded element.
+      }
+    }
+    m_size= pos;
+  }
+
+  /*
+    Reserves space for array elements.
+    Copies over existing elements, in case we are re-expanding the array.
+
+    @param  n number of elements.
+    @retval true if out-of-memory, false otherwise.
+  */
+  bool reserve(size_t n)
+  {
+    if (n <= m_capacity)
+      return false;
+
+    void *mem= alloc_root(m_root, n * element_size());
+    if (!mem)
+      return true;
+    Element_type *array= static_cast<Element_type*>(mem);
+
+    // Copy all the existing elements into the new array.
+    for (size_t ix= 0; ix < m_size; ++ix)
+    {
+      Element_type *new_p= &array[ix];
+      Element_type *old_p= &m_array[ix];
+      new (new_p) Element_type(*old_p);         // Copy into new location.
+      if (!has_trivial_destructor)
+        old_p->~Element_type();                 // Destroy the old element.
+    }
+
+    // Forget the old array.
+    m_array= array;
+    m_capacity= n;
+    return false;
+  }
+
+  /*
+    Adds a new element at the end of the array, after its current last
+    element. The content of this new element is initialized to a copy of
+    the input argument.
+
+    @param  element Object to copy.
+    @retval true if out-of-memory, false otherwise.
+  */
+  bool push_back(const Element_type &element)
+  {
+    const size_t min_capacity= 20;
+    const size_t expansion_factor= 2;
+    if (0 == m_capacity && reserve(min_capacity))
+      return true;
+    if (m_size == m_capacity && reserve(m_capacity * expansion_factor))
+      return true;
+    Element_type *p= &m_array[m_size++];
+    new (p) Element_type(element);
+    return false;
+  }
+
+  size_t capacity()     const { return m_capacity; }
+  size_t element_size() const { return sizeof(Element_type); }
+  bool   empty()        const { return size() == 0; }
+  size_t size()         const { return m_size; }
+
+private:
+  MEM_ROOT *const m_root;
+  Element_type   *m_array;
+  size_t          m_size;
+  size_t          m_capacity;
+
+  // Not (yet) implemented.
+  Mem_root_array(const Mem_root_array&);
+  Mem_root_array &operator=(const Mem_root_array&);
+};
+
+
+#endif  // MEM_ROOT_ARRAY_INCLUDED
diff --git a/sql/sql_lex.cc b/sql/sql_lex.cc
index 4637b1b1371..4692d1154a2 100644
--- a/sql/sql_lex.cc
+++ b/sql/sql_lex.cc
@@ -389,6 +389,8 @@ void lex_start(THD *thd)
   lex->select_lex.sql_cache= SELECT_LEX::SQL_CACHE_UNSPECIFIED;
   lex->select_lex.init_order();
   lex->select_lex.group_list.empty();
+  if (lex->select_lex.group_list_ptrs)
+    lex->select_lex.group_list_ptrs->clear();
   lex->describe= 0;
   lex->subqueries= FALSE;
   lex->context_analysis_only= 0;
@@ -1773,6 +1775,8 @@ void st_select_lex::init_select()
 {
   st_select_lex_node::init_select();
   group_list.empty();
+  if (group_list_ptrs)
+    group_list_ptrs->clear();
   type= db= 0;
   having= 0;
   table_join_options= 0;
@@ -3100,6 +3104,8 @@ static void fix_prepare_info_in_table_list(THD *thd, TABLE_LIST *tbl)
     The passed WHERE and HAVING are to be saved for the future executions.
     This function saves it, and returns a copy which can be thrashed during
     this execution of the statement. By saving/thrashing here we mean only
+    We also save the chain of ORDER::next in group_list, in case
+    the list is modified by remove_const().
     AND/OR trees.
     The function also calls fix_prepare_info_in_table_list that saves all
     ON expressions.    
@@ -3111,6 +3117,19 @@ void st_select_lex::fix_prepare_information(THD *thd, Item **conds,
   if (!thd->stmt_arena->is_conventional() && first_execution)
   {
     first_execution= 0;
+    if (group_list.first)
+    {
+      if (!group_list_ptrs)
+      {
+        void *mem= thd->stmt_arena->alloc(sizeof(Group_list_ptrs));
+        group_list_ptrs= new (mem) Group_list_ptrs(thd->stmt_arena->mem_root);
+      }
+      group_list_ptrs->reserve(group_list.elements);
+      for (ORDER *order= group_list.first; order; order= order->next)
+      {
+        group_list_ptrs->push_back(order);
+      }
+    }
     if (*conds)
     {
       prep_where= *conds;
@@ -3362,3 +3381,7 @@ void binlog_unsafe_map_init()
      BINLOG_DIRECT_OFF & TRX_CACHE_NOT_EMPTY);
 }
 #endif
+
+#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
+template class Mem_root_array<ORDER*, true>;
+#endif
diff --git a/sql/sql_lex.h b/sql/sql_lex.h
index c89057a4f75..6d004d0fa24 100644
--- a/sql/sql_lex.h
+++ b/sql/sql_lex.h
@@ -24,6 +24,7 @@
 #include "sql_trigger.h"
 #include "item.h"               /* From item_subselect.h: subselect_union_engine */
 #include "thr_lock.h"                  /* thr_lock_type, TL_UNLOCK */
+#include "mem_root_array.h"
 
 /* YACC and LEX Definitions */
 
@@ -258,6 +259,7 @@ enum enum_drop_mode
 #define TL_OPTION_ALIAS         8
 
 typedef List<Item> List_item;
+typedef Mem_root_array<ORDER*, true> Group_list_ptrs;
 
 /* SERVERS CACHE CHANGES */
 typedef struct st_lex_server_options
@@ -693,7 +695,16 @@ public:
   enum olap_type olap;
   /* FROM clause - points to the beginning of the TABLE_LIST::next_local list. */
   SQL_I_List<TABLE_LIST>  table_list;
-  SQL_I_List<ORDER>       group_list; /* GROUP BY clause. */
+
+  /*
+    GROUP BY clause.
+    This list may be mutated during optimization (by remove_const()),
+    so for prepared statements, we keep a copy of the ORDER.next pointers in
+    group_list_ptrs, and re-establish the original list before each execution.
+  */
+  SQL_I_List<ORDER>       group_list;
+  Group_list_ptrs        *group_list_ptrs;
+
   List<Item>          item_list;  /* list of fields & expressions */
   List<String>        interval_list;
   bool	              is_item_list_lookup;
@@ -870,7 +881,8 @@ public:
   bool test_limit();
 
   friend void lex_start(THD *thd);
-  st_select_lex() : n_sum_items(0), n_child_sum_items(0) {}
+  st_select_lex() : group_list_ptrs(NULL), n_sum_items(0), n_child_sum_items(0)
+  {}
   void make_empty_select()
   {
     init_query();
diff --git a/sql/sql_prepare.cc b/sql/sql_prepare.cc
index 8390594c2eb..d0bfecebc82 100644
--- a/sql/sql_prepare.cc
+++ b/sql/sql_prepare.cc
@@ -2422,6 +2422,14 @@ void reinit_stmt_before_use(THD *thd, LEX *lex)
       DBUG_ASSERT(sl->join == 0);
       ORDER *order;
       /* Fix GROUP list */
+      if (sl->group_list_ptrs && sl->group_list_ptrs->size() > 0)
+      {
+        for (uint ix= 0; ix < sl->group_list_ptrs->size() - 1; ++ix)
+        {
+          order= sl->group_list_ptrs->at(ix);
+          order->next= sl->group_list_ptrs->at(ix+1);
+        }
+      }
       for (order= sl->group_list.first; order; order= order->next)
         order->item= &order->item_ptr;
       /* Fix ORDER list */