0

Recursive queries to find the tree-structure (parent-child) in a table are commonly found here, however most have the problem that the childID must be higher than the parentID.

A possible solution for this is using a query like (given parent X, find all children)

SELECT * FROM (
    SELECT @pv:=(
        SELECT GROUP_CONCAT( child_id SEPARATOR "," ) FROM link_parent_child WHERE FIND_IN_SET( parent_id, @pv )
        ) AS lv FROM link_parent_child
        JOIN
        (SELECT @pv:=$parentStartID$) tmp
    ) a
WHERE lv IS NOT NULL

OR Given child X, find all parents

SELECT * FROM (
    SELECT @pv:=(
        SELECT parent_id FROM link_parent_child WHERE child_id = @pv
        ) AS lv FROM link_parent_child
        JOIN
        (SELECT @pv:=$ChildStartID$) tmp
    ) a
WHERE lv IS NOT NULL

However, with a table of over 500k records, this is somewhat slow... (understatement)

CREATE TABLE `link_parent_child` (
    `parent_id` int(11) NOT NULL,
    `child_id` int(11) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_520_ci;
ALTER TABLE `link_parent_child`
    ADD PRIMARY KEY (`child_id`,`parent_id`);
    ADD KEY `child_id` (`child_id`),
    ADD KEY `parent_id` (`parent_id`),
    ADD KEY `parent_id_2` (`parent_id`,`child_id`);

even with indexes set, and only 10k records, the query takes more than 80 seconds to run.

So, this query (correct me if I'm wrong) is so slow because the inner part returns NULL for almost all rows, which (i guess) are stored in a temp table and filtered out by the outer part of the query. I guess that the query would speed-up if the NULL's are filtered out earlier, but is that possible?

My tree's have a dynamic length, but mostly not deeper than 3-10 layers. Should I take my losses and solve this programmatically, or is there a method to speed this up?

  • 1
    What version are you running? 8.0.2 and MariaDB 10.2 have CTEs. – Rick James May 18 '17 at 4:41
  • I'm running windows 10 :P with MySQL 5.7.13. Could you elaborate what CTEs are? I guess I'll have to find mysqlf a good tutorian on getting MariaDB to work. I downloaded 10.1 earlier, but did not bother got get it working. – Jeffrey May 18 '17 at 17:58
  • CTEs are hot off the press (10.2); I have not yet found much MariaDB-specific documentation on them. – Rick James May 23 '17 at 17:35
1

Well, with the help of Rick James' remark I managed to find the answer. I installed MariaDB 10.2.5 (10.2.2 or higher required) and imported all MySQL data files by just copying the files in the Data dir to the MariaDB Data dir, and running mysql_update on the MariaDB database.

WITH RECURSIVE tree (parent_id) AS (
    SELECT parent_id FROM link_parent_child WHERE child_id = $ChildStartID$

    UNION ALL

    SELECT c.parent_id FROM link_parent_child lpc
    JOIN tree t ON t.parent_id = lpc.child_id
)
SELECT parent_id FROM tree

It really is that simpel :|

What are CTEs

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.