Recurstive query parent child speed

Question

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?

Answer 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