How to do MySQL Looped Join which tests if results are complete?

Question

Situation:
I have a mysql table of directories. Each directory has a parent directory (stored as parentID), up to the point where the root directory has a parentID of 0.

E.g.:

rowID: 1, name: Dir1,    parentID: 0 (root directory)
rowID: 2, name: Dir2,    parentID: 0 (root directory)
rowID: 3, name: Subdir1, parentID: 1 (lives in "Dir1")
rowID: 4, name: Subdir2, parentID: 1 (lives in "Dir1")
rowID: 5, name: Subdir3, parentID: 3 (lives in "Subdir1", which in turn lives in "Dir1")
rowID: 6, name: Subdir4, parentID: 5 (lives in "Subdir3", which lives in "Subdir1", which lives in "Dir1")

So here there is a 3 directory depth structure.

I need to build a statement which joins any directory to its parent and continues to do so until the last directory joined has a parentID of 0 (i.e. found the root directory). You can think of it as if, given any directory, you can find the breadcrumb back to the parent.

I figure that this may require some MySQL looping but for the life of me, I can't get any of the web examples to work. I can't even get some of the examples to run as they seem to have some sort of syntax errors in them. Can anyone help me get started?

I can accept any result format that's easiest and gives best performance to get this done. Either a simple array of row numbers in correct order (e.g. 5, 3, 1, 0, indicating the steps to get to ID of 0), or a full table (best) which will be an ordered list of rows that achieve this, e.g.

rowID: 5, name: Subdir3, parentID: 2;
rowID: 3, name: Subdir1, parentID: 1;
rowId: 1, name: Dir1,    parentID: 0;

Help much appreciated!

score 0 · Answer 1 · answered Aug 27 '12 at 12:12

0

Well, It could be you did not find a good web example, because you did use the wrong search-term. The problem described fits perfectly into oracles CONNECT BY PRIOR statement and by googling for mysql-equivalents to this statement you find http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/ quite fast.

Because its not that easy (and I dont have a mysql-db to rape here) to write this stuff, just have a glance at the good examples given (you can even do that without deployed functions via http://explainextended.com/2009/07/20/hierarchical-data-in-mysql-parents-and-children-in-one-query/.

If you still dont get the hang of those, I might be able to help at home.

answered Aug 27 '12 at 12:12

Najzero

3,164
18
18

Thanks Najzero for clearing this up. Clearly I was thinking of the wrong terms to search for. I did manage to get the parent hiearchical query working fine, but I don't seem to be able to get the child one going. I tried the statement they gave but there's no code for the function declared (second link). I tried plugging in the function from the first link but it's also got an error around line 5, where it declares the variables. Am I doing something totally wrong? Sorry for the potentially silly question. I'm familiar with simple mysql queries but this is far beyond my scope. Thanks. – Dave S Aug 30 '12 at 14:22
Also, would you have any idea of the performance of rather complex queries like this? – Dave S Aug 30 '12 at 14:27
Since I am enjoying my time at work now, I will try to recreate your task with the simple table structure described above this afternoon at home so you can catch the idea (if I am able to solve it anyway, its still complicated and I got the attention span of a goldfish). For your performance questsion, it is rather bad - because solving those hirarchical levels up, always requires some form of nested queries or another (the deeper the level, the worse it will become) but still faster than some summing functions on huge data amounts. – Najzero Aug 31 '12 at 05:49
Ok, so after more investigation and testing I'm satisfied that performance in downstream hiearchical query (finding children) is best approached using php/mysql combo instead of the one hit. But just wanted to ask for your opinion on the reverse? What's it like for upstream (finding parents)? This is the query i'm using (next comment), is it recommended and is it ok for performance? – Dave S Sep 04 '12 at 10:35
Actually it's the same as the one you gave in your first answer. – Dave S Sep 04 '12 at 10:42

Najzero · Answer 2 · 2012-08-31T15:32:46.677

Alright, found the time to actually deploy a simple database with a similar structure as described.

The table is the following:

CREATE TABLE `t_hierarchy` (
    `rowID` INT(11) NULL DEFAULT NULL,
    `name` VARCHAR(50) NULL DEFAULT NULL COLLATE 'latin1_general_ci',
    `parentID` INT(11) NULL DEFAULT NULL
);

I basicly inserted the exact same stuff as you have given above but used NULL values instead of 0 for root/no parent

What I've done is the quite cryptic example from http://explainextended.com/2009/07/20/hierarchical-data-in-mysql-parents-and-children-in-one-query/ . and just corrected the column names to fit mine.

Since this only generates you a recursive hierarchy, I just added a stupid join into the example ( ad.rowID = qi.id ):

 SELECT  qi.id, qi.parent, ad.rowId, ad.name, level
FROM    (
        SELECT  @r AS id,
                (
                SELECT  @r := parentID
                FROM    t_hierarchy
                WHERE   rowID = id
                ) AS parent,
                @l := @l + 1 AS level
        FROM    (
                SELECT  @r := 5, -- change this 5 to the directory ID you want to resolve
                        @l := 0,
                        @cl := 0
                ) vars,
                t_hierarchy h
        WHERE   @r <> 0
        ORDER BY
                level DESC
        ) qi, t_hierarchy ad
        WHERE ad.rowID = qi.id

And this generates the follwoing (desired) output:

id parent rowId name level

1 NULL 1 Dir1 3

3 1 3 Subdir1 2

5 3 5 Subdir3 1

Level is a helper column which tells you how "deep" it had to resolve to reach this. All you will have to do is change the "5" next to @r := to the directory ID from where you wanna iterate down.

If you want to switch the direction (from up to down) simply sort by level column ([...] WHERE ad.rowID = qi.id ORDER BY level ASC )

Hope this helps you out.

Edit: qi.id and ad.rowID are duplicates, just remove one of them ;-)... damn I hate that hierarchy stuff

Thank you so much! I think I got it to work...only I then did some more asking around and apparently the performance is potentially dangerously bad. If, say, the mysql data changes half way through an iteration it will cause some nasty errors. I may have to just use php to loop it through it seems, and restrict the depth to something sensible so that it doesn't error and hang. Would you say the same about the performance on this sort of super-query? — Dave S, Sep 01 '12 at 12:58
yes, this kind of retrival is always bad. You could always lay the "tree" structure into a text column like it would be in an normal OS ( /dir1/subdir1/subdir5 ) and then extract your required information via PHP... would be faster for sure. — Najzero, Sep 01 '12 at 13:16
I might have to go with the php solution for performance. I always thought that having a bigger query was better than going back and forth between database and script, but seems like this is no longer the case. Thanks so much for your help. — Dave S, Sep 02 '12 at 03:30

How to do MySQL Looped Join which tests if results are complete?

2 Answers2

Linked