MDEV-17635 Server hangs after the query with recursive CTE

This bug in the code of the function With_element::check_unrestricted_recursive()
could force a recursive CTE to be executed in a non-standard compliant mode
in which recursive UNION ALL could lead to an infinite execution. This
problem could occur only in the case when this CTE was used by another
recursive CTE at least twice.

3 files changed, 215 insertions, 1 deletions

diff --git a/mysql-test/r/cte_recursive.result b/mysql-test/r/cte_recursive.result
index de23d54694e..78530261efc 100644
--- a/mysql-test/r/cte_recursive.result
+++ b/mysql-test/r/cte_recursive.result
@@ -3441,3 +3441,162 @@ expired_date	purchase_date	quantity	p_id	purchase_processed	unresolved
 2014-11-08	NULL	0	2	5	1
 2014-11-08	2014-11-03	1	2	4	0
 DROP TABLE purchases, expired;
+#
+# MDEV-17635: Two recursive CTEs, the second using the first
+#
+WITH RECURSIVE
+x AS (SELECT 0 as k UNION ALL SELECT k + 1 FROM x WHERE k < 1),
+z AS
+( SELECT  k1 AS cx, k2 AS cy, k1, k2
+FROM (SELECT k  AS k1 FROM x) x1 JOIN (SELECT k  AS k2 FROM x) y1
+UNION
+SELECT 1,1,1,1 FROM z)
+SELECT * FROM z;
+cx	cy	k1	k2
+0	0	0	0
+1	0	1	0
+0	1	0	1
+1	1	1	1
+# https://wiki.postgresql.org/wiki/Mandelbrot_set:
+WITH RECURSIVE x(i) AS (
+SELECT CAST(0 AS DECIMAL(13, 10))
+UNION ALL
+SELECT i + 1
+FROM x
+WHERE i < 101
+),
+Z(Ix, Iy, Cx, Cy, X, Y, I) AS (
+SELECT Ix, Iy, X, Y, X, Y, 0
+FROM (SELECT CAST(-2.2 + 0.031 * i AS DECIMAL(13, 10)) AS X,
+i AS Ix FROM x) AS xgen
+CROSS JOIN (
+SELECT CAST(-1.5 + 0.031 * i AS DECIMAL(13, 10)) AS Y,
+i AS iY FROM x
+) AS ygen
+UNION ALL
+SELECT Ix, Iy, Cx, Cy,
+CAST(X * X - Y * Y + Cx AS DECIMAL(13, 10)) AS X,
+CAST(Y * X * 2 + Cy AS DECIMAL(13, 10)), I + 1
+FROM Z
+WHERE X * X + Y * Y < 16.0
+AND I < 27
+),
+Zt (Ix, Iy, I) AS (
+SELECT Ix, Iy, MAX(I) AS I
+FROM Z
+GROUP BY Iy, Ix
+ORDER BY Iy, Ix
+)
+SELECT GROUP_CONCAT(
+SUBSTRING(
+' .,,,-----++++%%%%@@@@#### ',
+GREATEST(I, 1),
+1
+) ORDER BY Ix SEPARATOR ''
+       ) AS 'Mandelbrot Set'
+  FROM Zt
+GROUP BY Iy
+ORDER BY Iy;
+Mandelbrot Set
+             ....................................................................................     
+            .......................................................................................   
+           .........................................................................................  
+          ........................................................................................... 
+        ....................................................,,,,,,,,,.................................
+       ................................................,,,,,,,,,,,,,,,,,,.............................
+      ..............................................,,,,,,,,,,,,,,,,,,,,,,,,..........................
+     ............................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................
+     ..........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,......................
+    .........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....................
+   ........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...................
+  .......................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.................
+ .......................................,,,,,,,,,,,,,,,,,,,,,,,,--,,,,,,,,,,,,,,,,,,,,................
+......................................,,,,,,,,,,,,,,,,,,,,,,,,,,-+--,,,,,,,,,,,,,,,,,,,...............
+....................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----,,,,,,,,,,,,,,,,,,,..............
+...................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,--- -----,,,,,,,,,,,,,,,,,.............
+.................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---++--++,,,,,,,,,,,,,,,,,,............
+................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----%++---,,,,,,,,,,,,,,,,,............
+..............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+%----,,,,,,,,,,,,,,,,,,...........
+.............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----- %%+----,,,,,,,,,,,,,,,,,,..........
+...........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---%-+%   ----,,,,,,,,,,,,,,,,,,,.........
+..........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---+ +##  %+%---,,,,,,,,,,,,,,,,,,.........
+........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----#      # +---,,,,,,,,,,,,,,,,,,........
+.......................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-------%       %-----,,,,,,,,,,,,,,,,,........
+.....................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---------+         ------,,,,,,,,,,,,,,,,,.......
+....................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----------+@       +-----------,,,,,,,,,,,,.......
+..................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----@-------++       ++-----------,,,,,,,,,,,,......
+.................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,--+@% ---+ +@%%@     %%+@+@%------+-,,,,,,,,,,,......
+................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----  # ++%               % @-----++--,,,,,,,,,,,.....
+..............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----+    %                  %%++ %+%@-,,,,,,,,,,,.....
+.............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+#                       #%    ++-,,,,,,,,,,,,....
+............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,------+                             @---,,,,,,,,,,,,....
+..........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-------++%                             ---,,,,,,,,,,,,....
+.........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,--------+ +                             %+---,,,,,,,,,,,,,...
+........,,,,,,,,,,,,,,,,,,,,,--------------------@                                +----,,,,,,,,,,,,...
+.......,,,,,,,,,,,,,,,,,,,,,,- +-----------------+                                 ----,,,,,,,,,,,,...
+.......,,,,,,,,,,,,,,,,,,,,,--++------+---------+%                                 +++--,,,,,,,,,,,,..
+......,,,,,,,,,,,,,,,,,,,,,,--%+-----++---------                                     #+-,,,,,,,,,,,,..
+.....,,,,,,,,,,,,,,,,,,,,,,----#%++--+@ -+-----+%                                     --,,,,,,,,,,,,..
+.....,,,,,,,,,,,,,,,,,,,,,,-----+## ++@ + +----%                                    +--,,,,,,,,,,,,,..
+....,,,,,,,,,,,,,,,,,,,,,,------+@  @     @@++++#                                   +--,,,,,,,,,,,,,..
+....,,,,,,,,,,,,,,,,,,,,,-------%           #++%                                      -,,,,,,,,,,,,,..
+...,,,,,,,,,,,,,,,,,,,,,------++%#           %%@                                     %-,,,,,,,,,,,,,,.
+...,,,,,,,,,,,,,,,,,,,--------+               %                                     +--,,,,,,,,,,,,,,.
+...,,,,,,,,,,,,,,,,,,-----+--++@              #                                      --,,,,,,,,,,,,,,.
+..,,,,,,,,,,,,,,,,,-------%+++%                                                    @--,,,,,,,,,,,,,,,.
+..,,,,,,,,,,,-------------+ @#@                                                    ---,,,,,,,,,,,,,,,.
+..,,,,,,,,,---@--------@-+%                                                       +---,,,,,,,,,,,,,,,.
+..,,,,,------- +-++++-+%%%                                                       +----,,,,,,,,,,,,,,,.
+..,,,,,,------%--------++%                                                       +----,,,,,,,,,,,,,,,.
+..,,,,,,,,,,--+----------++#                                                       ---,,,,,,,,,,,,,,,.
+..,,,,,,,,,,,,------------+@@@%                                                    +--,,,,,,,,,,,,,,,.
+..,,,,,,,,,,,,,,,,,------- +++%                                                    %--,,,,,,,,,,,,,,,.
+...,,,,,,,,,,,,,,,,,,---------+@              @                                      --,,,,,,,,,,,,,,.
+...,,,,,,,,,,,,,,,,,,,,------- #              %@                                    +--,,,,,,,,,,,,,,.
+...,,,,,,,,,,,,,,,,,,,,,-------++@           %+                                      %-,,,,,,,,,,,,,,.
+....,,,,,,,,,,,,,,,,,,,,,-------            %++%                                     %-,,,,,,,,,,,,,..
+....,,,,,,,,,,,,,,,,,,,,,,------+#  %#   #@ ++++                                    +--,,,,,,,,,,,,,..
+.....,,,,,,,,,,,,,,,,,,,,,,-----+ %%++% +@+----+                                    +--,,,,,,,,,,,,,..
+.....,,,,,,,,,,,,,,,,,,,,,,,---%+++--+#+--------%                                    #--,,,,,,,,,,,,..
+......,,,,,,,,,,,,,,,,,,,,,,--++-----%%---------                                    @#--,,,,,,,,,,,,..
+.......,,,,,,,,,,,,,,,,,,,,,---------------------+@                                +-++,,,,,,,,,,,,...
+........,,,,,,,,,,,,,,,,,,,,,--------------------+                                 ----,,,,,,,,,,,,...
+.........,,,,,,,,,,,,,,,,,,,,----,,,-------------                                #+----,,,,,,,,,,,,...
+..........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-------+ +                              +---,,,,,,,,,,,,,...
+...........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,--------+%#                           #---,,,,,,,,,,,,....
+............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,------+#                        @   @---,,,,,,,,,,,,....
+.............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+#                        +    @--,,,,,,,,,,,,....
+..............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---+%   %+@                 %+-+ +++%-,,,,,,,,,,,.....
+................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----% %@++              # %  -----++-,,,,,,,,,,,,.....
+.................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-- ++ ---+ + +%@     %++++++------%-,,,,,,,,,,,......
+...................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---- -------++       +------------,,,,,,,,,,,,......
+....................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----------+%       +--------,,,,,,,,,,,,,,,.......
+......................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,--------+#        -----,,,,,,,,,,,,,,,,,,.......
+.......................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-------+       #----,,,,,,,,,,,,,,,,,,........
+.........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----+%      %#---,,,,,,,,,,,,,,,,,,,........
+..........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---+%+%@  %+%%--,,,,,,,,,,,,,,,,,,.........
+............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---+-+%  %----,,,,,,,,,,,,,,,,,,..........
+.............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+%@+---,,,,,,,,,,,,,,,,,,,..........
+...............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+%----,,,,,,,,,,,,,,,,,,...........
+................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----%+ +--,,,,,,,,,,,,,,,,,............
+..................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---++----,,,,,,,,,,,,,,,,,.............
+...................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,---@-----,,,,,,,,,,,,,,,,,.............
+.....................................,,,,,,,,,,,,,,,,,,,,,,,,,,,-----,,,,,,,,,,,,,,,,,,,..............
+ .....................................,,,,,,,,,,,,,,,,,,,,,,,,,,--%,,,,,,,,,,,,,,,,,,,,...............
+ .......................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.................
+  ........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..................
+   ........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...................
+    .........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....................
+     ..........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,......................
+      ............................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................
+       .............................................,,,,,,,,,,,,,,,,,,,,,,,,..........................
+        ................................................,,,,,,,,,,,,,,,,,.............................
+         .....................................................,,,,....................................
+          ........................................................................................... 
+           .........................................................................................  
+            ......................................................................................    
+             ....................................................................................     
+               .................................................................................      
+                ..............................................................................        
+                  ...........................................................................         
+                   ........................................................................           
diff --git a/mysql-test/t/cte_recursive.test b/mysql-test/t/cte_recursive.test
index acaf95beda7..3c5bc62ae1a 100644
--- a/mysql-test/t/cte_recursive.test
+++ b/mysql-test/t/cte_recursive.test
@@ -2440,3 +2440,58 @@ WITH RECURSIVE expired_map AS (
 SELECT  * FROM expired_map;
 
 DROP TABLE purchases, expired;
+
+--echo #
+--echo # MDEV-17635: Two recursive CTEs, the second using the first
+--echo #
+
+WITH RECURSIVE
+x AS (SELECT 0 as k UNION ALL SELECT k + 1 FROM x WHERE k < 1),
+z AS
+  ( SELECT  k1 AS cx, k2 AS cy, k1, k2
+      FROM (SELECT k  AS k1 FROM x) x1 JOIN (SELECT k  AS k2 FROM x) y1
+    UNION
+    SELECT 1,1,1,1 FROM z)
+SELECT * FROM z;
+
+--echo # https://wiki.postgresql.org/wiki/Mandelbrot_set:
+
+WITH RECURSIVE x(i) AS (
+    SELECT CAST(0 AS DECIMAL(13, 10))
+     UNION ALL
+    SELECT i + 1
+      FROM x
+     WHERE i < 101
+),
+Z(Ix, Iy, Cx, Cy, X, Y, I) AS (
+    SELECT Ix, Iy, X, Y, X, Y, 0
+      FROM (SELECT CAST(-2.2 + 0.031 * i AS DECIMAL(13, 10)) AS X,
+                  i AS Ix FROM x) AS xgen
+           CROSS JOIN (
+               SELECT CAST(-1.5 + 0.031 * i AS DECIMAL(13, 10)) AS Y,
+                      i AS iY FROM x
+           ) AS ygen
+    UNION ALL
+    SELECT Ix, Iy, Cx, Cy,
+           CAST(X * X - Y * Y + Cx AS DECIMAL(13, 10)) AS X,
+           CAST(Y * X * 2 + Cy AS DECIMAL(13, 10)), I + 1
+      FROM Z
+     WHERE X * X + Y * Y < 16.0
+           AND I < 27
+),
+Zt (Ix, Iy, I) AS (
+    SELECT Ix, Iy, MAX(I) AS I
+      FROM Z
+     GROUP BY Iy, Ix
+     ORDER BY Iy, Ix
+)
+SELECT GROUP_CONCAT(
+           SUBSTRING(
+               ' .,,,-----++++%%%%@@@@#### ',
+               GREATEST(I, 1),
+               1
+           ) ORDER BY Ix SEPARATOR ''
+       ) AS 'Mandelbrot Set'
+  FROM Zt
+GROUP BY Iy
+ORDER BY Iy;
diff --git a/sql/sql_cte.cc b/sql/sql_cte.cc
index 5a590bfea93..5d4c2b20872 100644
--- a/sql/sql_cte.cc
+++ b/sql/sql_cte.cc
@@ -1263,7 +1263,7 @@ bool With_element::check_unrestricted_recursive(st_select_lex *sel,
       With_element *with_elem= unit->with_element;
       if (encountered & with_elem->get_elem_map())
         unrestricted|= with_elem->mutually_recursive;
-      else
+      else if (with_elem ==this)
         encountered|= with_elem->get_elem_map();
     }
   }