Fixed the bug mdev-12563.

The bug happened when the specification of a recursive CTE had
no recursive references at the top level of the specification.
In this case the regular processing of derived table references
of the select containing a non-recursive reference to this
recursive CTE misses handling the specification unit.
At the preparation stage any non-recursive reference to a
recursive CTE must be handled after the preparation of the
specification unit for this CTE. So we have to force this
preparation when regular handling of derived tables does not
do it.

6 files changed, 209 insertions, 6 deletions

diff --git a/mysql-test/r/cte_recursive.result b/mysql-test/r/cte_recursive.result
index ff336287129..42ba01e42de 100644
--- a/mysql-test/r/cte_recursive.result
+++ b/mysql-test/r/cte_recursive.result
@@ -2813,3 +2813,65 @@ SELECT c2 FROM t, cte
 COUNT(*)
 4
 DROP TABLE t;
+#
+# mdev-12563: no recursive references on the top level of the CTE spec 
+#  
+CREATE TABLE t (i int);
+INSERT INTO t VALUES (3), (1),(2);
+SET standard_compliant_cte=0;
+WITH RECURSIVE cte(f) AS (
+SELECT i FROM t
+UNION
+SELECT i FROM t WHERE i NOT IN ( SELECT * FROM cte )
+) SELECT * FROM cte;
+f
+3
+1
+2
+WITH RECURSIVE cte(f) AS (
+SELECT i FROM t
+UNION
+SELECT i FROM t WHERE i NOT IN ( SELECT * FROM cte WHERE i < 2 )
+UNION
+SELECT i FROM t WHERE i NOT IN ( SELECT * FROM cte WHERE i > 2 )
+) SELECT * FROM cte;
+f
+3
+1
+2
+WITH RECURSIVE cte(f) AS (
+SELECT i FROM t
+UNION
+SELECT i FROM t
+WHERE i NOT IN ( SELECT * FROM cte WHERE i < 2
+UNION
+SELECT * FROM cte WHERE i > 2)
+) SELECT * FROM cte;
+f
+3
+1
+2
+WITH RECURSIVE cte(f) AS (
+SELECT i FROM t
+UNION
+SELECT i FROM t 
+WHERE i NOT IN ( SELECT * FROM t
+WHERE i IN ( SELECT * FROM cte ) GROUP BY i )
+) SELECT * FROM cte;
+f
+3
+1
+2
+WITH RECURSIVE cte(f) AS (
+SELECT i FROM t
+UNION
+SELECT i FROM t WHERE i NOT IN ( SELECT * FROM cte )
+UNION 
+SELECT * FROM cte WHERE f > 2
+) SELECT * FROM cte;
+f
+3
+1
+2
+set standard_compliant_cte=default;
+DROP TABLE t;
diff --git a/mysql-test/t/cte_recursive.test b/mysql-test/t/cte_recursive.test
index ea825036728..5701ee896cb 100644
--- a/mysql-test/t/cte_recursive.test
+++ b/mysql-test/t/cte_recursive.test
@@ -1876,3 +1876,55 @@ eval $q2;
 
 DROP TABLE t;
 
+--echo #
+--echo # mdev-12563: no recursive references on the top level of the CTE spec 
+--echo #  
+
+CREATE TABLE t (i int);
+INSERT INTO t VALUES (3), (1),(2);
+ 
+SET standard_compliant_cte=0;
+ 
+WITH RECURSIVE cte(f) AS (
+  SELECT i FROM t
+  UNION
+  SELECT i FROM t WHERE i NOT IN ( SELECT * FROM cte )
+) SELECT * FROM cte;           
+
+WITH RECURSIVE cte(f) AS (
+  SELECT i FROM t
+  UNION
+  SELECT i FROM t WHERE i NOT IN ( SELECT * FROM cte WHERE i < 2 )
+  UNION
+  SELECT i FROM t WHERE i NOT IN ( SELECT * FROM cte WHERE i > 2 )
+) SELECT * FROM cte;
+           
+WITH RECURSIVE cte(f) AS (
+  SELECT i FROM t
+  UNION
+  SELECT i FROM t
+    WHERE i NOT IN ( SELECT * FROM cte WHERE i < 2
+                     UNION
+                     SELECT * FROM cte WHERE i > 2)
+) SELECT * FROM cte;           
+
+WITH RECURSIVE cte(f) AS (
+  SELECT i FROM t
+  UNION
+  SELECT i FROM t 
+    WHERE i NOT IN ( SELECT * FROM t
+                       WHERE i IN ( SELECT * FROM cte ) GROUP BY i )
+) SELECT * FROM cte;           
+
+WITH RECURSIVE cte(f) AS (
+  SELECT i FROM t
+  UNION
+  SELECT i FROM t WHERE i NOT IN ( SELECT * FROM cte )
+  UNION 
+  SELECT * FROM cte WHERE f > 2
+) SELECT * FROM cte;           
+
+set standard_compliant_cte=default;
+
+DROP TABLE t;
+
diff --git a/sql/sql_cte.cc b/sql/sql_cte.cc
index 62b27d05e9b..1b14c5b68b7 100644
--- a/sql/sql_cte.cc
+++ b/sql/sql_cte.cc
@@ -141,7 +141,7 @@ bool With_clause::check_dependencies()
 
   /*
     Mark those elements where tables are defined with direct or indirect
-   make recursion.
+    recursion.
   */ 
   for (With_element *with_elem= with_list.first;
        with_elem;
@@ -342,6 +342,8 @@ void With_element::check_dependencies_in_select(st_select_lex *sl,
       tbl->with_internal_reference_map= get_elem_map();
       if (in_subq)
         sq_dep_map|= tbl->with->get_elem_map();
+      else
+        top_level_dep_map|= tbl->with->get_elem_map();
     }
   }
   /* Now look for the dependencies in the subqueries of sl */
@@ -353,6 +355,53 @@ void With_element::check_dependencies_in_select(st_select_lex *sl,
 
 /**
   @brief
+    Find a recursive reference to this with element in subqueries of a select
+ 
+  @param  sel      The select in whose subqueries the reference
+                   to be looked for
+
+  @details
+    The function looks for a recursive reference to this with element in
+    subqueries of select sl. When the first such reference is found
+    it is returned as the result.
+    The function assumes that the identification of all CTE references
+    has been performed earlier.
+
+  @retval
+    Pointer to the found recursive reference if the search succeeded
+    NULL - otherwise 
+*/
+
+TABLE_LIST *With_element::find_first_sq_rec_ref_in_select(st_select_lex *sel)
+{
+  TABLE_LIST *rec_ref= NULL;
+  st_select_lex_unit *inner_unit= sel->first_inner_unit();
+  for (; inner_unit; inner_unit= inner_unit->next_unit())
+  {
+    st_select_lex *sl= inner_unit->first_select();
+    for (; sl; sl= sl->next_select())
+    {
+      for (TABLE_LIST *tbl= sl->table_list.first; tbl; tbl= tbl->next_local)
+      {
+        if (tbl->derived || tbl->nested_join)
+          continue;
+        if (tbl->with && tbl->with->owner== this->owner &&
+            (tbl->with_internal_reference_map & mutually_recursive))
+	{
+	  rec_ref= tbl;
+          return rec_ref;
+        }
+      }
+      if ((rec_ref= find_first_sq_rec_ref_in_select(sl)))
+        return rec_ref;
+    } 
+  }
+  return 0;
+}
+
+
+/**
+  @brief
     Find the dependencies of this element on its siblings in a unit
  
   @param  unit     The unit where to look for the dependencies
@@ -602,6 +651,10 @@ void With_clause::move_anchors_ahead()
   @details
     If the specification of this with element contains anchors the method
     moves them at the very beginning of the specification.
+    Additionally for the other selects of the specification if none of them
+    contains a recursive reference to this with element or a mutually recursive
+    one the method looks for the first such reference in the first recursive 
+    select and set a pointer to it in this->sq_rec_ref.   
 */
 
 void With_element::move_anchors_ahead()
@@ -618,6 +671,11 @@ void With_element::move_anchors_ahead()
       sl->move_node(new_pos);
       new_pos= sl->next_select();
     }
+    else if (!sq_rec_ref && no_rec_ref_on_top_level())
+    {
+      sq_rec_ref= find_first_sq_rec_ref_in_select(sl);
+      DBUG_ASSERT(sq_rec_ref != NULL);
+    }
     last_sl= sl;
   }
   if (spec->union_distinct)
diff --git a/sql/sql_cte.h b/sql/sql_cte.h
index 1cb77af8099..64b2f1cb1c8 100644
--- a/sql/sql_cte.h
+++ b/sql/sql_cte.h
@@ -46,6 +46,16 @@ private:
   /* Dependency map of with elements mutually recursive with this with element */
   table_map mutually_recursive;
   /* 
+    Dependency map built only for the top level references i.e. for those that
+    are encountered in from lists of the selects of the specification unit
+  */ 
+  table_map top_level_dep_map;
+  /*
+    Points to a recursive reference in subqueries.
+    Used only for specifications without recursive references on the top level.
+  */
+  TABLE_LIST *sq_rec_ref;
+  /* 
     The next with element from the circular chain of the with elements
     mutually recursive with this with element. 
     (If This element is simply recursive than next_mutually_recursive contains
@@ -118,7 +128,7 @@ public:
     stage and is used at the execution stage.
   */
   select_union_recursive *rec_result;
- 
+
   /* List of Item_subselects containing recursive references to this CTE */
   SQL_I_List<Item_subselect> sq_with_rec_ref; 
 
@@ -127,6 +137,7 @@ public:
                st_select_lex_unit *unit)
     : next(NULL), base_dep_map(0), derived_dep_map(0),
       sq_dep_map(0), work_dep_map(0), mutually_recursive(0),
+      top_level_dep_map(0), sq_rec_ref(NULL),
       next_mutually_recursive(NULL), references(0), 
       query_name(name), column_list(list), spec(unit),
       is_recursive(false), with_anchor(false),
@@ -154,6 +165,8 @@ public:
   bool check_dependency_on(With_element *with_elem)
   { return base_dep_map & with_elem->get_elem_map(); }
 
+  TABLE_LIST *find_first_sq_rec_ref_in_select(st_select_lex *sel);
+
   bool set_unparsed_spec(THD *thd, char *spec_start, char *spec_end);
 
   st_select_lex_unit *clone_parsed_spec(THD *thd, TABLE_LIST *with_table);
@@ -177,11 +190,16 @@ public:
   bool contains_sq_with_recursive_reference()
   { return sq_dep_map & mutually_recursive; }
 
+  bool no_rec_ref_on_top_level()
+  { return !(top_level_dep_map & mutually_recursive); }
+
   table_map get_mutually_recursive() { return mutually_recursive; }
 
   With_element *get_next_mutually_recursive()
   { return next_mutually_recursive; }
 
+  TABLE_LIST *get_sq_rec_ref() { return sq_rec_ref; }
+
   bool is_anchor(st_select_lex *sel);
 
   void move_anchors_ahead(); 
diff --git a/sql/sql_derived.cc b/sql/sql_derived.cc
index 916f7057607..8f0410b4284 100644
--- a/sql/sql_derived.cc
+++ b/sql/sql_derived.cc
@@ -646,6 +646,23 @@ bool mysql_derived_prepare(THD *thd, LEX *lex, TABLE_LIST *derived)
 
   SELECT_LEX *first_select= unit->first_select();
 
+  if (derived->is_recursive_with_table() &&
+      !derived->is_with_table_recursive_reference() &&
+      !derived->with->rec_result && derived->with->get_sq_rec_ref())
+  {
+    /*
+      This is a non-recursive reference to a recursive CTE whose
+      specification unit has not been prepared at the regular processing of
+      derived table references. This can happen  only in the case when
+      the specification unit has no recursive references at the top level. 
+      Force the preparation of the specification unit. Use a recursive
+      table reference from a subquery for this.
+    */
+    DBUG_ASSERT(derived->with->get_sq_rec_ref());
+    if (mysql_derived_prepare(lex->thd, lex, derived->with->get_sq_rec_ref()))
+      DBUG_RETURN(TRUE);
+  }
+
   if (unit->prepared && derived->is_recursive_with_table() &&
       !derived->table)
   {
diff --git a/sql/sql_derived.h b/sql/sql_derived.h
index c451e423032..f098cf39083 100644
--- a/sql/sql_derived.h
+++ b/sql/sql_derived.h
@@ -39,10 +39,6 @@ bool mysql_derived_cleanup(THD *thd, LEX *lex, TABLE_LIST *derived);
 
 Item *delete_not_needed_parts(THD *thd, Item *cond);
 
-#if 0
-bool pushdown_cond_for_derived(THD *thd, Item **cond, TABLE_LIST *derived);
-#else
 bool pushdown_cond_for_derived(THD *thd, Item *cond, TABLE_LIST *derived);
-#endif
 
 #endif /* SQL_DERIVED_INCLUDED */