[MDEV-17635] Server hangs after the query with recursive CTE Created: 2018-11-07  Updated: 2018-11-08  Resolved: 2018-11-08

Status: Closed
Project: MariaDB Server
Component/s: Optimizer - CTE
Affects Version/s: 10.2, 10.3
Fix Version/s: 10.2.19

Type: Bug Priority: Critical
Reporter: Alice Sherepa Assignee: Igor Babaev
Resolution: Fixed Votes: 0
Labels: None

Issue Links:
Duplicate
duplicates MDEV-17629 Recursive CTE performance Closed

 Description   

Based on the article from https://elephantdolphin.blogspot.com/2018/11/common-table-expressions-shocking.html

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;

The problem is with UNION vs UNION ALL:

MariaDB [test]> WITH RECURSIVE 
    -> x AS (SELECT 0 as k UNION 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 |
+------+------+------+------+
4 rows in set (0.000 sec)
 
################################################ 
 
MariaDB [test]> 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;
 
^CCtrl-C -- query killed. Continuing normally.
ERROR 1317 (70100): Query execution was interrupted

MariaDB [test]> WITH RECURSIVE x(i) AS (
    ->     SELECT CAST(0 AS DECIMAL(13, 10))
    ->      UNION 
    ->     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                                                                                         |
+--------------------------------------------------------------------------------------------------------+
|              ....................................................................................      |
|             .......................................................................................    |
|            .........................................................................................   |
|           ...........................................................................................  |
|         ....................................................,,,,,,,,,................................. |
|        ................................................,,,,,,,,,,,,,,,,,,............................. |
|       ..............................................,,,,,,,,,,,,,,,,,,,,,,,,.......................... |
|      ............................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................ |
|      ..........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...................... |
|     .........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.................... |
|    ........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,................... |
|   .......................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,................. |
|  .......................................,,,,,,,,,,,,,,,,,,,,,,,,--,,,,,,,,,,,,,,,,,,,,................ |
| ......................................,,,,,,,,,,,,,,,,,,,,,,,,,,-+--,,,,,,,,,,,,,,,,,,,............... |
| ....................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----,,,,,,,,,,,,,,,,,,,.............. |
| ...................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,--- -----,,,,,,,,,,,,,,,,,............. |
| .................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---++--++,,,,,,,,,,,,,,,,,,............ |
| ................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----%++---,,,,,,,,,,,,,,,,,............ |
| ..............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+%----,,,,,,,,,,,,,,,,,,........... |
| .............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----- %%+----,,,,,,,,,,,,,,,,,,.......... |
| ...........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---%-+%   ----,,,,,,,,,,,,,,,,,,,......... |
| ..........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---+ +##  %+%---,,,,,,,,,,,,,,,,,,......... |
| ........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----#      # +---,,,,,,,,,,,,,,,,,,........ |
| .......................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-------%       %-----,,,,,,,,,,,,,,,,,........ |
| .....................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---------+         ------,,,,,,,,,,,,,,,,,....... |
| ....................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----------+@       +-----------,,,,,,,,,,,,....... |
| ..................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----@-------++       ++-----------,,,,,,,,,,,,...... |
| .................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,--+@% ---+ +@%%@     %%+@+@%------+-,,,,,,,,,,,...... |
| ................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----  # ++%               % @-----++--,,,,,,,,,,,..... |
| ..............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----+    %                  %%++ %+%@-,,,,,,,,,,,..... |
| .............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+#                       #%    ++-,,,,,,,,,,,,.... |
| ............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,------+                             @---,,,,,,,,,,,,.... |
| ..........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-------++%                             ---,,,,,,,,,,,,.... |
| .........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,--------+ +                             %+---,,,,,,,,,,,,,... |
| ........,,,,,,,,,,,,,,,,,,,,,--------------------@                                +----,,,,,,,,,,,,... |
| .......,,,,,,,,,,,,,,,,,,,,,,- +-----------------+                                 ----,,,,,,,,,,,,... |
| .......,,,,,,,,,,,,,,,,,,,,,--++------+---------+%                                 +++--,,,,,,,,,,,,.. |
| ......,,,,,,,,,,,,,,,,,,,,,,--%+-----++---------                                     #+-,,,,,,,,,,,,.. |
| .....,,,,,,,,,,,,,,,,,,,,,,----#%++--+@ -+-----+%                                     --,,,,,,,,,,,,.. |
| .....,,,,,,,,,,,,,,,,,,,,,,-----+## ++@ + +----%                                    +--,,,,,,,,,,,,,.. |
| ....,,,,,,,,,,,,,,,,,,,,,,------+@  @     @@++++#                                   +--,,,,,,,,,,,,,.. |
| ....,,,,,,,,,,,,,,,,,,,,,-------%           #++%                                      -,,,,,,,,,,,,,.. |
| ...,,,,,,,,,,,,,,,,,,,,,------++%#           %%@                                     %-,,,,,,,,,,,,,,. |
| ...,,,,,,,,,,,,,,,,,,,--------+               %                                     +--,,,,,,,,,,,,,,. |
| ...,,,,,,,,,,,,,,,,,,-----+--++@              #                                      --,,,,,,,,,,,,,,. |
| ..,,,,,,,,,,,,,,,,,-------%+++%                                                    @--,,,,,,,,,,,,,,,. |
| ..,,,,,,,,,,,-------------+ @#@                                                    ---,,,,,,,,,,,,,,,. |
| ..,,,,,,,,,---@--------@-+%                                                       +---,,,,,,,,,,,,,,,. |
| ..,,,,,------- +-++++-+%%%                                                       +----,,,,,,,,,,,,,,,. |
| ..,,,,,,------%--------++%                                                       +----,,,,,,,,,,,,,,,. |
| ..,,,,,,,,,,--+----------++#                                                       ---,,,,,,,,,,,,,,,. |
| ..,,,,,,,,,,,,------------+@@@%                                                    +--,,,,,,,,,,,,,,,. |
| ..,,,,,,,,,,,,,,,,,------- +++%                                                    %--,,,,,,,,,,,,,,,. |
| ...,,,,,,,,,,,,,,,,,,---------+@              @                                      --,,,,,,,,,,,,,,. |
| ...,,,,,,,,,,,,,,,,,,,,------- #              %@                                    +--,,,,,,,,,,,,,,. |
| ...,,,,,,,,,,,,,,,,,,,,,-------++@           %+                                      %-,,,,,,,,,,,,,,. |
| ....,,,,,,,,,,,,,,,,,,,,,-------            %++%                                     %-,,,,,,,,,,,,,.. |
| ....,,,,,,,,,,,,,,,,,,,,,,------+#  %#   #@ ++++                                    +--,,,,,,,,,,,,,.. |
| .....,,,,,,,,,,,,,,,,,,,,,,-----+ %%++% +@+----+                                    +--,,,,,,,,,,,,,.. |
| .....,,,,,,,,,,,,,,,,,,,,,,,---%+++--+#+--------%                                    #--,,,,,,,,,,,,.. |
| ......,,,,,,,,,,,,,,,,,,,,,,--++-----%%---------                                    @#--,,,,,,,,,,,,.. |
| .......,,,,,,,,,,,,,,,,,,,,,---------------------+@                                +-++,,,,,,,,,,,,... |
| ........,,,,,,,,,,,,,,,,,,,,,--------------------+                                 ----,,,,,,,,,,,,... |
| .........,,,,,,,,,,,,,,,,,,,,----,,,-------------                                #+----,,,,,,,,,,,,... |
| ..........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-------+ +                              +---,,,,,,,,,,,,,... |
| ...........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,--------+%#                           #---,,,,,,,,,,,,.... |
| ............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,------+#                        @   @---,,,,,,,,,,,,.... |
| .............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+#                        +    @--,,,,,,,,,,,,.... |
| ..............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---+%   %+@                 %+-+ +++%-,,,,,,,,,,,..... |
| ................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----% %@++              # %  -----++-,,,,,,,,,,,,..... |
| .................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-- ++ ---+ + +%@     %++++++------%-,,,,,,,,,,,...... |
| ...................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---- -------++       +------------,,,,,,,,,,,,...... |
| ....................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----------+%       +--------,,,,,,,,,,,,,,,....... |
| ......................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,--------+#        -----,,,,,,,,,,,,,,,,,,....... |
| .......................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-------+       #----,,,,,,,,,,,,,,,,,,........ |
| .........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----+%      %#---,,,,,,,,,,,,,,,,,,,........ |
| ..........................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---+%+%@  %+%%--,,,,,,,,,,,,,,,,,,......... |
| ............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---+-+%  %----,,,,,,,,,,,,,,,,,,.......... |
| .............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+%@+---,,,,,,,,,,,,,,,,,,,.......... |
| ...............................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----+%----,,,,,,,,,,,,,,,,,,........... |
| ................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-----%+ +--,,,,,,,,,,,,,,,,,............ |
| ..................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,---++----,,,,,,,,,,,,,,,,,............. |
| ...................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,---@-----,,,,,,,,,,,,,,,,,............. |
| .....................................,,,,,,,,,,,,,,,,,,,,,,,,,,,-----,,,,,,,,,,,,,,,,,,,.............. |
|  .....................................,,,,,,,,,,,,,,,,,,,,,,,,,,--%,,,,,,,,,,,,,,,,,,,,............... |
|  .......................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,................. |
|   ........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.................. |
|    ........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,................... |
|     .........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.................... |
|      ..........................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...................... |
|       ............................................,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................ |
|        .............................................,,,,,,,,,,,,,,,,,,,,,,,,.......................... |
|         ................................................,,,,,,,,,,,,,,,,,............................. |
|          .....................................................,,,,.................................... |
|           ...........................................................................................  |
|            .........................................................................................   |
|             ......................................................................................     |
|              ....................................................................................      |
|                .................................................................................       |
|                 ..............................................................................         |
|                   ...........................................................................          |
|                    ........................................................................            |
+--------------------------------------------------------------------------------------------------------+
102 rows in set (0.378 sec)



 Comments   
Comment by Igor Babaev [ 2018-11-08 ]

A fix for this bug was pushed into 10.2

Generated at Thu Feb 08 08:37:57 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.