[MDEV-16086] Recursive CTE Hangs Created: 2018-05-03  Updated: 2018-05-09  Resolved: 2018-05-09

Status: Closed
Project: MariaDB Server
Component/s: Optimizer - CTE
Affects Version/s: 10.2.14
Fix Version/s: 10.2.15

Type: Bug Priority: Critical
Reporter: Bryce Lowe Assignee: Igor Babaev
Resolution: Duplicate Votes: 0
Labels: None
Environment:

CentOS VMware virtual machine running MariaDB 10.2.14
Windows 10 physical machine running MariaDB 10.2.9


 Description   

I am attempting to use the recursive common table expressions to explode a bill of materials, however I am running into a problem where the MariaDB server hangs and eventually fills up the disk if left unchecked, even though there are not any circular references in this expression.

See the following example:

1. Table to hold the bom

DROP TABLE IF EXISTS bomtest;
 
CREATE TABLE bomtest (
 
	`Id` int(11) not null AUTO_INCREMENT,
 
    `Parent` varchar(15) not null,
 
    `Child` varchar(15) not null,
 
    PRIMARY KEY (`Id`)
 
) ENGINE = InnoDB;

2. Add some dummy entries that represent a part/child product structure

INSERT INTO bomtest (Parent, Child)
 
VALUES
 
('123', '456'),
 
('456', '789'),
 
('321', '654'),
 
('654', '987');

3. Attempt to run a recursive common table expression with a path using cast to avoid data truncation. In this query the Path column is created as TEXT because of the CAST to CHAR(513), it never seems to complete and eventually fills the disk.

WITH RECURSIVE cte AS (
 
	SELECT b.Parent, b.Child, CAST(CONCAT(b.Child,',') AS CHAR(513)) Path FROM bomtest b LEFT OUTER JOIN bomtest bc ON b.Child = bc.Parent WHERE bc.Id IS NULL
 
    UNION ALL
 
    SELECT c.Parent, c.Child, CONCAT(p.Path,c.Child,',') Path FROM bomtest c INNER JOIN cte p ON c.Child = p.Parent
 
)
 
SELECT * FROM cte ORDER BY Path;

4. Attempt to run a recursive common table expression with a path using cast to avoid data truncation. This query the Path column is created as VARCHAR(512) because of the CAST to CHAR(512) and DOES complete.

WITH RECURSIVE cte AS (
 
	SELECT b.Parent, b.Child, CAST(CONCAT(b.Child,',') AS CHAR(512)) Path FROM bomtest b LEFT OUTER JOIN bomtest bc ON b.Child = bc.Parent WHERE bc.Id IS NULL
 
    UNION ALL
 
    SELECT c.Parent, c.Child, CONCAT(p.Path,c.Child,',') Path FROM bomtest c INNER JOIN cte p ON c.Child = p.Parent
 
)
 
SELECT * FROM cte ORDER BY Path;

In this particular example the query just continues executing, even though there aren't any circular references. As I mention in the reproduction steps, I believe I have narrowed down part of the issue to the datatype that the Path column eventually becomes. When you CAST the path to anything over CHAR(512) the column type switches from VARCHAR to TEXT, once that happens the never completes. However if you cast to CHAR(512) and below you get the expected result and the Path column is VARCHAR.

In my particular use case, the column must be text as the path gets very long and is key to not only detecting circular references, but also drawing the indented version of the bill of materials.

 Comments   
Comment by Alice Sherepa [ 2018-05-07 ]

Thanks for the report, reproducible as described on 10.2-10.3
Problems here are:

1) datatype CHAR(M), the range of M is 0 to 255. (https://mariadb.com/kb/en/library/char/), then why CHAR(512) works

2) casting to CHAR(513), result type is text, while for CHAR(512) it is varchar(512) (MariaDB 5.5 - 10.3)
(affects Mysql too, according to https://stackoverflow.com/questions/49539606/mysql-view-column-stays-text-despite-using-cast-convert-to-char)

MariaDB [test2]> CREATE view v1(f1) as select cast('sometext' as char(513));
 
Query OK, 0 rows affected (0.477 sec)
 
 
 
MariaDB [test2]> show columns from v1;
 
+-------+------+------+-----+---------+-------+
 
| Field | Type | Null | Key | Default | Extra |
 
+-------+------+------+-----+---------+-------+
 
| f1    | text | YES  |     | NULL    |       |
 
+-------+------+------+-----+---------+-------+
 
1 row in set (0.002 sec)
 
 
 
MariaDB [test2]> CREATE view v2(f1) as select cast('sometext' as char(512));
 
Query OK, 0 rows affected (0.271 sec)
 
 
 
MariaDB [test2]> show columns from v2;
 
+-------+--------------+------+-----+---------+-------+
 
| Field | Type         | Null | Key | Default | Extra |
 
+-------+--------------+------+-----+---------+-------+
 
| f1    | varchar(512) | YES  |     | NULL    |       |
 
+-------+--------------+------+-----+---------+-------+
 
1 row in set (0.002 sec)

3) Query with recursive CTE hangs due to truncating of types.
If columns `Parent` and `Child` are defined as VARCHAR(513) or text, then query returns correct results.

DROP TABLE IF EXISTS bomtest;
 
CREATE TABLE bomtest (
 
	`Id` int(11) not null AUTO_INCREMENT,
 
    `Parent` VARCHAR(513) not null,
 
    `Child` VARCHAR(513) not null,
 
    PRIMARY KEY (`Id`)
 
) ENGINE = InnoDB;
 
 
 
INSERT INTO bomtest (Parent, Child) VALUES ('123', '456'),('456', '789'),('321', '654'),('654', '987');
 
 
 
WITH RECURSIVE cte AS
 
  ( SELECT b.Parent,
 
           b.Child,
 
           CAST(CONCAT(b.Child,',') AS CHAR(513)) Path
 
   FROM bomtest b
 
   LEFT OUTER JOIN bomtest bc ON b.Child = bc.Parent
 
   WHERE bc.Id IS NULL
 
   UNION ALL SELECT c.Parent,
 
                    c.Child,
 
                    CONCAT(p.Path,c.Child,',') Path
 
   FROM bomtest c
 
   INNER JOIN cte p ON c.Child = p.Parent)
 
SELECT *
 
FROM cte
 
ORDER BY Path;


+--------+-------+----------+
 
| Parent | Child | Path     |
 
+--------+-------+----------+
 
| 456    | 789   | 789,     |
 
| 123    | 456   | 789,456, |
 
| 654    | 987   | 987,     |
 
| 321    | 654   | 987,654, |
 
+--------+-------+----------+
 
4 rows in set (0.261 sec)

Comment by Igor Babaev [ 2018-05-07 ]

This bug cannot be reproduced on the current 10.2 development tree because it was actually fixed by the patch for MDEV-15575. The patch will appear in the 10.2.15 release. Yet I'm adding the test case for this bug.

Comment by Igor Babaev [ 2018-05-09 ]

This bug was fixed by the patch for MDEV-15575.
Added the test case reported for MDEV-16086.

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