[MDEV-11259] Recursive CTE crashes or gets "table full" errors Created: 2016-11-09  Updated: 2016-11-17  Resolved: 2016-11-17

Status: Closed
Project: MariaDB Server
Component/s: Optimizer - CTE
Affects Version/s: 10.2.2
Fix Version/s: 10.2.3

Type: Bug Priority: Major
Reporter: richardeaxon Assignee: Igor Babaev
Resolution: Fixed Votes: 0
Labels: None
Environment:

Centos 7


 Description   

Using the following simple table and dataset from the extensive CTE examples here: https://inviqa.com/blog/graphs-database-sql-meets-social-network

DROP TABLE IF EXISTS `edges`;
 
CREATE TABLE `edges` (
 
  `a` int(10) unsigned NOT NULL,
 
  `b` int(10) unsigned NOT NULL,
 
  PRIMARY KEY (`a`,`b`),
 
  KEY `b` (`b`)
 
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
 
 
 
INSERT INTO `edges` VALUES (1,3),(2,1),(2,4),(3,4),(3,5),(3,6),(4,7),(5,1),(5,6),(6,1);
 
 
 
DROP TABLE IF EXISTS `edges2`;
 
CREATE VIEW edges2 (a, b) AS SELECT a, b FROM edges   UNION ALL   SELECT b, a FROM edges;

When trying any of the examples the server either crashes hard, or the query runs but aborts with ERROR 1114 (HY000): The table '/tmp/#sql_4b24_1' is full.

Some of the queries I ran are:

Causes a "table full":

WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
 
( SELECT a, b, 1 AS distance,
 
    a || '.' || b || '.' AS path_string
 
  FROM edges
 
 
  UNION ALL
 
 
  SELECT tc.a, e.b, tc.distance + 1,
 
  tc.path_string || e.b || '.' AS path_string
 
  FROM edges AS e
 
    JOIN transitive_closure AS tc
 
      ON e.a = tc.b
 
  WHERE tc.path_string NOT LIKE '%' || e.b || '.%'
 
)
 
SELECT * FROM transitive_closure
 
ORDER BY a, b, distance;


WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
 
( SELECT a, b, 1 AS distance,
 
         a || '.' || b || '.' AS path_string
 
  FROM edges
 
 WHERE a = 1 -- source
 
 
  UNION ALL
 
 
  SELECT tc.a, e.b, tc.distance + 1,
 
         tc.path_string || e.b || '.' AS path_string
 
  FROM edges AS e
 
  JOIN transitive_closure AS tc ON e.a = tc.b
 
 WHERE tc.path_string NOT LIKE '%' || e.b || '.%'
 
)
 
  SELECT * FROM transitive_closure
 
   WHERE b=6 -- destination
 
ORDER BY a, b, distance;

Causes a hard server crash (suspect due to CTE against view):

WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
 
( SELECT  a, b, 1 AS distance,
 
          a || '.' || b || '.' AS path_string
 
  FROM edges2
 
 
  UNION ALL
 
 
  SELECT tc.a, e.b, tc.distance + 1,
 
  tc.path_string || e.b || '.' AS path_string
 
  FROM edges2 AS e
 
    JOIN transitive_closure AS tc ON e.a = tc.b
 
  WHERE tc.path_string NOT LIKE '%' || e.b || '.%'
 
)
 
SELECT * FROM transitive_closure
 
ORDER BY a, b, distance;


WITH RECURSIVE transitive_closure(a, b, distance, path_string)
 
AS
 
( SELECT a, b, 1 AS distance,
 
         a || '.' || b || '.' AS path_string
 
  FROM edges2
 
 
  UNION ALL
 
 
  SELECT tc.a, e.b, tc.distance + 1,
 
         tc.path_string || e.b || '.' AS path_string
 
  FROM edges2 AS e
 
  JOIN transitive_closure AS tc ON e.a = tc.b
 
 WHERE tc.path_string NOT LIKE '%' || e.b || '.%'
 
)
 
SELECT a, b, min(distance) AS dist FROM transitive_closure
 
--WHERE a = 1 AND b=6
 
GROUP BY a, b
 
ORDER BY a, dist, b;

I expect all the queries to behave as per the examples given in the article.

 Comments   
Comment by Elena Stepanova [ 2016-11-12 ]

Thanks for the report and test case.

The crashes were fixed in scope of MDEV-10899.
So, all four queries from the description currently fail with ER_RECORD_FILE_FULL.
In PostgreSQL, all of them work, and they don't return so many rows (maximum is 300).

Comment by Igor Babaev [ 2016-11-12 ]

The problem is that MySQL/MariaDB does not take the operator '||' as the concatenation operator.
Rather they take it as a logical operator equivalent to OR.
Compare:

MariaDB [test]> SELECT a, b, 1 AS distance,
 
    ->     a || '.' || b || '.' AS path_string
 
    ->   FROM edges;
 
+---+---+----------+-------------+
 
| a | b | distance | path_string |
 
+---+---+----------+-------------+
 
| 1 | 3 |        1 |           1 |
 
| 2 | 1 |        1 |           1 |
 
| 2 | 4 |        1 |           1 |
 
| 3 | 4 |        1 |           1 |
 
| 3 | 5 |        1 |           1 |
 
| 3 | 6 |        1 |           1 |
 
| 4 | 7 |        1 |           1 |
 
| 5 | 1 |        1 |           1 |
 
| 5 | 6 |        1 |           1 |
 
| 6 | 1 |        1 |           1 |
 
+---+---+----------+-------------+
 
10 rows in set, 2 warnings (0.00 sec)
 
 
 
MariaDB [test]> show warnings;
 
+---------+------+----------------------------------------+
 
| Level   | Code | Message                                |
 
+---------+------+----------------------------------------+
 
| Warning | 1292 | Truncated incorrect INTEGER value: '.' |
 
| Warning | 1292 | Truncated incorrect INTEGER value: '.' |
 
+---------+------+----------------------------------------+
 
2 rows in set (0.00 sec)

and

MariaDB [test]> SELECT a, b, 1 AS distance, concat(a,'.',b,'.') AS path_string   FROM edges;
 
+---+---+----------+-------------+
 
| a | b | distance | path_string |
 
+---+---+----------+-------------+
 
| 1 | 3 |        1 | 1.3.        |
 
| 2 | 1 |        1 | 2.1.        |
 
| 2 | 4 |        1 | 2.4.        |
 
| 3 | 4 |        1 | 3.4.        |
 
| 3 | 5 |        1 | 3.5.        |
 
| 3 | 6 |        1 | 3.6.        |
 
| 4 | 7 |        1 | 4.7.        |
 
| 5 | 1 |        1 | 5.1.        |
 
| 5 | 6 |        1 | 5.6.        |
 
| 6 | 1 |        1 | 6.1.        |
 
+---+---+----------+-------------+
 
10 rows in set (0.00 sec)

Yes, MySQL/MariaDB does not follow SQL standard here, but this is a different problem.

Comment by richardeaxon [ 2016-11-13 ]

Reworking query 1 & 2 as follows gives the expected result. As the crash caused by query 3 & 4 has been resolved under another ticket, this ticket can be closed. Thanks.

WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
 
( SELECT a, b, 1 AS distance,
 
    concat(a, '.', b, '.') AS path_string
 
  FROM edges
 
 
  UNION ALL
 
 
  SELECT tc.a, e.b, tc.distance + 1,
 
  concat(tc.path_string, e.b, '.') AS path_string
 
  FROM edges AS e
 
    JOIN transitive_closure AS tc
 
      ON e.a = tc.b
 
  WHERE tc.path_string NOT LIKE concat('%', e.b, '.%')
 
)
 
SELECT * FROM transitive_closure
 
ORDER BY a, b, distance;
 



WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
 
( SELECT a, b, 1 AS distance,
 
         concat(a, '.', b, '.') AS path_string
 
  FROM edges
 
 WHERE a = 1 -- source
 
 
  UNION ALL
 
 
  SELECT tc.a, e.b, tc.distance + 1,
 
         concat(tc.path_string, e.b,'.') AS path_string
 
  FROM edges AS e
 
  JOIN transitive_closure AS tc ON e.a = tc.b
 
 WHERE tc.path_string NOT LIKE concat('%',e.b,'.%')
 
)
 
  SELECT * FROM transitive_closure
 
   WHERE b=6 -- destination
 
ORDER BY a, b, distance;

Comment by Igor Babaev [ 2016-11-17 ]

The test case from this mdev was added into cte_recursive.test

Generated at Thu Feb 08 07:48:33 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.