Search code examples
sqloracle-databasemariadbhierarchical-dataansi-sql

CONNECT BY with NOCYCLE ( oracle ) hierarhical query in MariaDB with simple sql code

A hierarchical query with own nocycle solution will be presented. Improvement needed.

A tree with or without loops (Oidipus) is assumed. Table:

CREATE TABLE `person` (
  `ID` varchar(10) NOT NULL,
  `PARENT` varchar(10) NOT NULL,
  `TYPE` varchar(10) NOT NULL,
  `NAME` varchar(50) NOT NULL
)

Fields TYPE and NAME have no importance.Connection is realized with the ID of another person in field PARENT.

  1. Find Parents:
WITH recursive Parents(ID, SUMID, TYPE, PARENT, LEVEL) AS (
  SELECT ID, Concat(ID,"Z","                  ...") AS SUMID, TYPE, PARENT, 0 AS LEVEL FROM `person` WHERE ID = '1000000005'
  UNION ALL
  SELECT m.ID, CONCAT(m.ID,"Z",SUMID) AS SUMID , m.TYPE, m.PARENT, LEVEL + 1 FROM `person` as m INNER JOIN Parents t on m.ID = t.PARENT
  WHERE LEVEL < 6
  AND INSTR ( SUMID, m.ID) < 1
)
SELECT * FROM Parents;

An extra Column SUMID (concatenated "numeric" IDs, separator="Z") will be used for checking NOCCYCLE (see Oracle keyword). (Oidipus appears only one times in field ID). Works fine, but SUMID initial content should be coded as MAXLEVEL times 10 "String".

What only partially works:

  1. Find all Children
WITH recursive Children(ID, SUMID, TYPE, PARENT, LEVEL) AS (
  SELECT ID, Concat(ID,"Z","                  ...") AS SUMID, TYPE, PARENT, 0 AS LEVEL FROM `person` WHERE ID = '1000000002'
  UNION ALL
  SELECT m.ID, CONCAT(m.ID,"Z",SUMID) AS SUMID , m.TYPE, m.PARENT, LEVEL + 1 FROM `person` as m INNER JOIN Children t on m.PARENT = t.ID
  WHERE LEVEL < 6
  AND INSTR ( SUMID, m.ID) < 1
)
SELECT * FROM Children;

When someone has 5 children and 5*5 = 25 grandchildren, etc., then SUMID could not be long enough. Furthermore, the script for all children is very slow and weak in performance. How could you implement "Find all children" in simple MySQL?

I tried to implement a hierarchical query for a tree rekordstructure. The query "Find Children" is slow and iefficient. Ia am hoping for improvement suggestions.

INSERT INTO `person` (`ID`, `PARENT`, `TYPE`, `NAME`) VALUES
('1000000001', '1000000001', 'A', 'first'),
('1000000002', '1000000004', 'B', 'second'),
('1000000003', '1000000002', 'C', 'third'),
('1000000004', '1000000002', 'C', 'fourth'),
('1000000005', '1000000004', 'C', 'fifth'),
('1000000006', '1000000002', 'C', '6th'),
('1000000007', '1000000002', 'C', '7th'),
('1000000008', '1000000002', 'C', '8th'),
('1000000009', '1000000002', 'C', '9th'),
('1000000010', '1000000005', 'D', '10th'),
('1000000011', '1000000005', 'D', '11th'),
('1000000012', '1000000005', 'D', '12nd'),
('1000000013', '1000000005', 'D', '13rd');

Result:

MariaDB [devmysql]> WITH recursive Children(ID, SUMID, TYPE, PARENT, LEVEL) AS (
    ->   SELECT ID, Concat(ID,"Z","                  ") AS SUMID, TYPE, PARENT, 0 AS LEVEL FROM `person` WHERE ID = '1000000002'
    ->   UNION ALL
    ->   SELECT m.ID, CONCAT(m.ID,"Z",SUMID) AS SUMID , m.TYPE, m.PARENT, LEVEL + 1 FROM `person` as m INNER JOIN Children t on m.PARENT = t.ID
    ->   WHERE LEVEL < 6
    ->   AND INSTR ( SUMID, m.ID) < 1
    -> )
    -> SELECT * FROM Children;
+------------+-------------------------------+------+------------+-------+
| ID         | SUMID                         | TYPE | PARENT     | LEVEL |
+------------+-------------------------------+------+------------+-------+
| 1000000002 | 1000000002Z                   | B    | 1000000004 |     0 |
| 1000000003 | 1000000003Z1000000002Z        | C    | 1000000002 |     1 |
| 1000000004 | 1000000004Z1000000002Z        | C    | 1000000002 |     1 |
| 1000000006 | 1000000006Z1000000002Z        | C    | 1000000002 |     1 |
| 1000000007 | 1000000007Z1000000002Z        | C    | 1000000002 |     1 |
| 1000000008 | 1000000008Z1000000002Z        | C    | 1000000002 |     1 |
| 1000000009 | 1000000009Z1000000002Z        | C    | 1000000002 |     1 |
| 1000000005 | 1000000005Z1000000004Z1000000 | C    | 1000000004 |     2 |
| 1000000010 | 1000000010Z1000000005Z1000000 | D    | 1000000005 |     3 |
| 1000000011 | 1000000011Z1000000005Z1000000 | D    | 1000000005 |     3 |
| 1000000012 | 1000000012Z1000000005Z1000000 | D    | 1000000005 |     3 |
| 1000000013 | 1000000013Z1000000005Z1000000 | D    | 1000000005 |     3 |
+------------+-------------------------------+------+------------+-------+
12 rows in set, 11 warnings (0.004 sec)

The Oracle equivalent looks like that (see below) :
Hint
In oracle

  • UNION ALL is compulsory otherwise ORA-32040: recursive WITH clause must use a UNION ALL operation
  • a Parameterlist is compulsory otherwise ORA-32039: recursive WITH clause must have column alias list
  • recursive ommitted otherwise systax error
  • LEVEL is a keyword in ORACLE, i.e. use LEV instead
WITH Children (ID, SUMID, LEVEL) 
AS
(
  SELECT
    m.ID,
    ',' || CAST(m.ID AS VARCHAR(120) || ','  AS SUMID,
    0 AS LEV
  FROM
    person  AS m
  WHERE
    ID = '1000000002'
  UNION ALL
  SELECT
    m.ID,
    t.SUMID || m.ID || ','  AS SUMID,
    LEV + 1 AS LEV
  FROM
    person AS m
  INNER JOIN
    Children AS t
      ON m.PARENT = t.ID
  WHERE
      t.LEV < 10
    AND INSTR(t.SUMID, CONCAT(',', m.ID, ',')) < 1
)
SELECT * FROM Children;

Query has delivered ca. 60000 records in 600 msecs.
Query has been tested against his connect by oracle counterpart with MINUS in both directions:

select ID
FROM person 
  START WITH ID = '1000000002'
  CONNECT BY NOCYCLE PRIOR ID = PARENT
MINUS
SELECT ID FROM (
WITH Children (ID, SUMID, LEVEL) 
AS
(
  SELECT
    m.ID,
    ',' || CAST(m.ID AS VARCHAR(120) || ','  AS SUMID,
    0 AS LEV
  FROM
    person  AS m
  WHERE
    ID = '1000000002'
  UNION ALL
  SELECT
    m.ID,
    t.SUMID || m.ID || ','  AS SUMID,
    LEV + 1 AS LEV
  FROM
    person AS m
  INNER JOIN
    Children AS t
      ON m.PARENT = t.ID
  WHERE
      t.LEV < 10
    AND INSTR(t.SUMID, CONCAT(',', m.ID, ',')) < 1
)
SELECT * FROM Children);

Does not deliver any record.
Query was successfully tested in ORACLE in 1 sec. As for me Unbelievable quick.
"Na ja," Connect by can automatically deliver some more features:

  • CONNECT_BY_ISCYCLE
  • CONNECT_BY_ISLEAF
  • LEVEL
    [see: oracle docs][1]https://docs.oracle.com/cd/B12037_01/server.101/b10759/pseudocolumns001.htm#i1009434]
Solution

  • As long as you don't need to output the LEVEL and the SUMID, you can use UNION instead of UNION ALL to prevent loops being evaluated.

    CREATE TABLE `person` (
  `ID` varchar(10) NOT NULL,
  `PARENT` varchar(10) NOT NULL,
  `TYPE` varchar(10) NOT NULL,
  `NAME` varchar(50) NOT NULL
)

    INSERT INTO `person` (`ID`, `PARENT`, `TYPE`, `NAME`) VALUES
('1000000001', '1000000001', 'A', 'first'),
('1000000002', '1000000004', 'B', 'second'),
('1000000003', '1000000002', 'C', 'third'),
('1000000004', '1000000002', 'C', 'fourth'),
('1000000005', '1000000004', 'C', 'fifth'),
('1000000006', '1000000002', 'C', '6th'),
('1000000007', '1000000002', 'C', '7th'),
('1000000008', '1000000002', 'C', '8th'),
('1000000009', '1000000002', 'C', '9th'),
('1000000010', '1000000005', 'D', '10th'),
('1000000011', '1000000005', 'D', '11th'),
('1000000012', '1000000005', 'D', '12nd'),
('1000000013', '1000000005', 'D', '13rd')
;

    Records: 13  Duplicates: 0  Warnings: 0

    WITH
  RECURSIVE
    Children
AS
(
  SELECT * FROM `person` WHERE ID = '1000000002'
  UNION
  SELECT m.* FROM `person` as m INNER JOIN Children t on m.PARENT = t.ID
)
SELECT * FROM Children
    ID PARENT TYPE NAME
    1000000002 1000000004 B second
    1000000003 1000000002 C third
    1000000004 1000000002 C fourth
    1000000006 1000000002 C 6th
    1000000007 1000000002 C 7th
    1000000008 1000000002 C 8th
    1000000009 1000000002 C 9th
    1000000005 1000000004 C fifth
    1000000010 1000000005 D 10th
    1000000011 1000000005 D 11th
    1000000012 1000000005 D 12nd
    1000000013 1000000005 D 13rd

    fiddle