[MDEV-22068] Recursive CTE hangs - Mandelbrot set calculation Created: 2020-03-28  Updated: 2023-12-05

Status: Stalled
Project: MariaDB Server
Component/s: Optimizer - CTE
Affects Version/s: 10.4.12, 10.2, 10.3, 10.4, 10.5
Fix Version/s: 10.4, 10.5

Type: Bug Priority: Major
Reporter: Karl Levik Assignee: Igor Babaev
Resolution: Unresolved Votes: 0
Labels: Compatibility

Attachments: Text File mandelbrot_m2_sqlite.txt    

 Description   

I was inspired by this tutorial for SQLite to try the same thing for MariaDB - skip ahead to the "Outlandish Recursive Query Examples" section:
https://infoshri.com/latest-news/the-mandelbrot-set-in-sql/

So I re-wrote the query slightly, just changing the min function to be least so it will run in MariaDB:

WITH RECURSIVE
 
  xaxis(x) AS (VALUES(-2.0) UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2),
 
  yaxis(y) AS (VALUES(-1.0) UNION ALL SELECT y+0.1 FROM yaxis WHERE y<1.0),
 
  m(iter, cx, cy, x, y) AS (
 
    SELECT 0, x, y, 0.0, 0.0 FROM xaxis, yaxis
 
    UNION ALL
 
    SELECT iter+1, cx, cy, x*x-y*y + cx, 2.0*x*y + cy FROM m 
     WHERE (x*x + y*y) < 4.0 AND iter<28
 
  ),
 
  m2(iter, cx, cy) AS (
 
    SELECT max(iter), cx, cy FROM m GROUP BY cx, cy
 
  ),
 
  a(t) AS (
 
    SELECT group_concat( substr(' .+*#', 1+least(iter/7,4), 1), '') 
    FROM m2 GROUP BY cy
 
  )
 
SELECT group_concat(rtrim(t),x'0a') FROM a;

The query seems to run forever without completing.

I've also tested the query with the most recent MySQL version - 8.0.19, just changing the VALUES to VALUES ROW and setting @@cte_max_recursion_depth to a big number in the query above. The query doesn't seem to complete there either.

 Comments   
Comment by Elena Stepanova [ 2020-03-29 ]

This is already different:

WITH RECURSIVE xaxis(x) AS (SELECT -2.0 UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2) SELECT * FROM xaxis

SQLite (SQL.js) from SQL Fiddle:

SQLite

 
WITH RECURSIVE xaxis(x) AS (SELECT -2.0 UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2) SELECT * FROM xaxis
 
 
 
x
 
-2
 
-1.95
 
-1.9
 
-1.8499999999999999
 
-1.7999999999999998
 
-1.7499999999999998
 
-1.6999999999999997
 
-1.6499999999999997
 
-1.5999999999999996
 
-1.5499999999999996
 
-1.4999999999999996
 
-1.4499999999999995
 
-1.3999999999999995
 
-1.3499999999999994
 
-1.2999999999999994
 
-1.2499999999999993
 
-1.1999999999999993
 
-1.1499999999999992
 
-1.0999999999999992
 
-1.0499999999999992
 
-0.9999999999999991
 
-0.9499999999999991
 
-0.899999999999999
 
-0.849999999999999
 
-0.7999999999999989
 
-0.7499999999999989
 
-0.6999999999999988
 
-0.6499999999999988
 
-0.5999999999999988
 
-0.5499999999999987
 
-0.4999999999999987
 
-0.44999999999999873
 
-0.39999999999999875
 
-0.34999999999999876
 
-0.29999999999999877
 
-0.24999999999999878
 
-0.1999999999999988
 
-0.1499999999999988
 
-0.0999999999999988
 
-0.049999999999998795
 
1.2073675392798577e-15
 
0.05000000000000121
 
0.10000000000000121
 
0.15000000000000122
 
0.20000000000000123
 
0.2500000000000012
 
0.3000000000000012
 
0.3500000000000012
 
0.4000000000000012
 
0.4500000000000012
 
0.5000000000000012
 
0.5500000000000013
 
0.6000000000000013
 
0.6500000000000014
 
0.7000000000000014
 
0.7500000000000014
 
0.8000000000000015
 
0.8500000000000015
 
0.9000000000000016
 
0.9500000000000016
 
1.0000000000000016
 
1.0500000000000016
 
1.1000000000000016
 
1.1500000000000017
 
1.2000000000000017

MariaDB:

MariaDB

 
set max_recursive_iterations = 100;
 
WITH RECURSIVE xaxis(x) AS (SELECT -2.0 UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2) SELECT * FROM xaxis;
 
 
 
+------+
 
| x    |
 
+------+
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
| -2.0 |
 
+------+

With UNION instead of UNION ALL SQLite result doesn't change, while MariaDB returns a single row instead:

MariaDB [(none)]> WITH RECURSIVE xaxis(x) AS (SELECT -2.0 UNION SELECT x+0.05 FROM xaxis WHERE x<1.2) SELECT * FROM xaxis;
 
+------+
 
| x    |
 
+------+
 
| -2.0 |
 
+------+
 
1 row in set (0.003 sec)

Comment by Igor Babaev [ 2020-03-30 ]

The above behavior is due to the fact that the type of the recursive table xaxis is determined by the type of of its non-recursive part that is SELECT -2.0.
We can see from the following

MariaDB [test]> create table t0 as select -2.0;
 
Query OK, 1 row affected (0.02 sec)
 
Records: 1  Duplicates: 0  Warnings: 0
 
 
 
MariaDB [test]> show create table t0;
 
+-------+-------------------------------------------------------------------------------------------+
 
| Table | Create Table                                                                              |
 
+-------+-------------------------------------------------------------------------------------------+
 
| t0    | CREATE TABLE `t0` (
 
  `-2.0` decimal(2,1) NOT NULL
 
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
 
+-------+-------------------------------------------------------------------------------------------+

that this type is decimal(2,1) .
Yet the type of SELECT -2.00 is decimal(3,2) and for 

WITH RECURSIVE xaxis(x) AS (SELECT -2.00 UNION ALL SELECT x+0.05 FROM xaxis WHERE  x<1.2) SELECT * FROM xaxis;

we have

MariaDB [test]> WITH RECURSIVE xaxis(x) AS (SELECT -2.00 UNION ALL SELECT x+0.05 FROM xaxis WHERE  x<1.2) SELECT * FROM xaxis;
 
+-------+
 
| x     |
 
+-------+
 
| -2.00 |
 
| -1.95 |
 
| -1.90 |
 
| -1.85 |
 
| -1.80 |
 
| -1.75 |
 
| -1.70 |
 
| -1.65 |
 
| -1.60 |
 
| -1.55 |
 
| -1.50 |
 
| -1.45 |
 
| -1.40 |
 
| -1.35 |
 
| -1.30 |
 
| -1.25 |
 
| -1.20 |
 
| -1.15 |
 
| -1.10 |
 
| -1.05 |
 
| -1.00 |
 
| -0.95 |
 
| -0.90 |
 
| -0.85 |
 
| -0.80 |
 
| -0.75 |
 
| -0.70 |
 
| -0.65 |
 
| -0.60 |
 
| -0.55 |
 
| -0.50 |
 
| -0.45 |
 
| -0.40 |
 
| -0.35 |
 
| -0.30 |
 
| -0.25 |
 
| -0.20 |
 
| -0.15 |
 
| -0.10 |
 
| -0.05 |
 
|  0.00 |
 
|  0.05 |
 
|  0.10 |
 
|  0.15 |
 
|  0.20 |
 
|  0.25 |
 
|  0.30 |
 
|  0.35 |
 
|  0.40 |
 
|  0.45 |
 
|  0.50 |
 
|  0.55 |
 
|  0.60 |
 
|  0.65 |
 
|  0.70 |
 
|  0.75 |
 
|  0.80 |
 
|  0.85 |
 
|  0.90 |
 
|  0.95 |
 
|  1.00 |
 
|  1.05 |
 
|  1.10 |
 
|  1.15 |
 
|  1.20 |
 
+-------+

Comment by Igor Babaev [ 2020-03-30 ]

Karl,

Still I don't have a proper picture for table a.
Could you please provide me with the contents of m2 that you get with SQLite?

Comment by Karl Levik [ 2020-04-02 ]

I actually hadn't tested this with SQLite, but now that you ask, I'm happy to help. I assume you want the output of:

WITH RECURSIVE
 
  xaxis(x) AS (VALUES(-2.0) UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2),
 
  yaxis(y) AS (VALUES(-1.0) UNION ALL SELECT y+0.1 FROM yaxis WHERE y<1.0),
 
  m(iter, cx, cy, x, y) AS (
 
    SELECT 0, x, y, 0.0, 0.0 FROM xaxis, yaxis
 
    UNION ALL
 
    SELECT iter+1, cx, cy, x*x-y*y + cx, 2.0*x*y + cy FROM m 
     WHERE (x*x + y*y) < 4.0 AND iter<28
 
  ),
 
  m2(iter, cx, cy) AS (
 
    SELECT max(iter), cx, cy FROM m GROUP BY cx, cy
 
  )
 
SELECT * FROM m2;

I have attached the output in a file named 'mandelbrot_m2_sqlite.txt'.

Comment by Igor Babaev [ 2020-04-03 ]

Karl,
how do you get this record in the result set
2|1.2|1.1
if yaxis AS (VALUES(-1.0) UNION ALL SELECT y+0.1 FROM yaxis WHERE y<1.0) ?
Looking at the above definition I would conclude that cy <= 1.0.

Comment by Karl Levik [ 2020-05-08 ]

Hi Igor,

I can only guess the cy numbers that are >= 1.0 in the output indicate a bug in sqlite? So that means sqlite creates a few extra results, but at least it succeeds in producing a result set.

Comment by Julien Fritsch [ 2023-12-05 ]

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.

Comment by JiraAutomate [ 2023-12-05 ]

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.

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