MySQL Order By Hierarchy

Question

I asked this question previously but this was for a two-layer tree and the solution I was given worked perfectly.

I now have a multi level tree (up to 3, but lets assume there could be more in the future.

My code currently looks like this:

SELECT * FROM fin_document AS finl

LEFT OUTER JOIN fin_document AS finl2
ON finl2.id = finl.parent_line_id

ORDER BY
CASE WHEN finl2.ordinal IS NULL THEN finl.ordinal
ELSE concat(finl2.ordinal,'-',finl.ordinal) END

Lets assume a similar tree as before:

(id)  (Item)    (#)  (parent_line_id)
1234 - Car    -  1 -  null
0000 - Boat   -  2 -  null
2222 - House  -  4 -  null
6545 - Bike   -  5 -  null
6547 - Wheels -  0 -  1234
4442 - Bed    -  1 -  2222
1474 - Sink   -  0 -  2222
9456 - Tires  -  0 -  6547                  *New item, child of wheels
8975 - L.Nuts -  1 -  6547                  *New item, child of wheels

oh and the # column is "ordinal"

So how would I get this to sort proper with more than one parent?

The proper sort should look like:

(id)  (Item)    (#)  (parent_line_id)
1234 - Car    -  1 -  null
6547 - Wheels -  0 -  1234
9456 - Tires  -  0 -  6547
8975 - L.Nuts -  1 -  6547 
0000 - Boat   -  2 -  null
2222 - House  -  4 -  null
1474 - Sink   -  0 -  2222
4442 - Bed    -  1 -  2222
6545 - Bike   -  5 -  null

Note: I cannot alter the tables whatsoever. I am only able to pull data from the tables, as the tables are managed by another company, who's software we use. I'm aware that they will get more and more complex if there are more children, but I do not think there will be more than 3-4 children for what my company will be using this for. Unfortunately, due to this complexity, this is why I had to return here and ask again :(

This will be a restructure, so I am putting this in as a comment instead of an answer. The adjacency list model is rather inflexible and get more complex as the size grows. A better option (not the best) would be to use a nested set model described [here](http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/). The best option, is to use a graph for your structure and a rdbms for the data, but that is another subject. — Jacob Lambert, Jun 10 '15 at 23:02
I'm assuming you mean the structure of the original tables. I forgot to mention this time but I cannot alter the tables whatsoever. I am only able to pull data from the tables, as the tables are managed by another company, who's software we use. Thanks for reminding me about this. — user3669901, Jun 10 '15 at 23:04

score 1 · Answer 1 · answered Jun 11 '15 at 00:50

Hopefully you aren't looking for something that is going to work with N deep hierarchy without modification.

This should be fairly trivial to extend, however.

SELECT id,
    item,
    o,
    parent_line_id
FROM (
    SELECT *,
        1 AS parentage,
        o AS rank
    FROM table1
    WHERE parent_line_id IS NULL

    UNION ALL

    SELECT t2.id,
        t1.item,
        t1.o,
        t1.parent_line_id,
        2 AS parentage,
        t2.o AS rank
    FROM table1 t1
    INNER JOIN table1 t2 ON t1.parent_line_id = t2.id
        AND t2.parent_line_id IS NULL

    UNION ALL

    SELECT t3.id,
        t1.item,
        t1.o,
        t1.parent_line_id,
        3 AS parentage,
        t3.o AS rank
    FROM table1 t1
    INNER JOIN table1 t2 ON t1.parent_line_id = t2.id
        AND t2.parent_line_id IS NOT NULL
    INNER JOIN table1 t3 ON t2.parent_line_id = t3.id
    ) q
ORDER BY rank ASC,
    parentage ASC,
    o ASC;

demo here

The basic premise is we identify all the parentless items, and give them a parentage of 1.

We then identify their children, give them a parentage of 2, and their children get a parentage of 3.

All of them inherit the first parents ordinal for sorting purposes, then.

There are probably other ways to do this, i'm probably even going to look for them, but in the mean time - this works.

Well... it kind of works. I tried it out in a test table I made and it puts some things in the right order, but for some reason its moving and removing items and such. For example, the parent rows are correct, as in id, name, ordinal, parent_id are all the same as they should be. However, the child elements are all jumbled- the Name replaced the parent_id, the id became the parent_id of the top-most parent (including the grand children), and the Name became the parent_id as well... The grand children are out of order too. I honestly have no clue what is going on here in your code either. — user3669901, Jun 11 '15 at 17:12
@user3669901 can you please update the demo i posted, with the data you have that gives incorrect output? — pala_, Jun 12 '15 at 06:51
@user3669901 sqlfiddle can occasionally be unreliable - looks to still be down at the moment :/ — pala_, Jun 16 '15 at 00:00

score 0 · Answer 2 · edited May 23 '17 at 11:58

0

Here's a dirty trick to handle arbitrary depth:

SELECT a.k, b.*
FROM (
    SELECT a.id, a.k
    FROM (
        SELECT CONCAT(LEFT(
               (@c := @previous_id <> b.id OR @previous_id IS NULL)
               & (@id := IF( @c, b.id, (SELECT parent_line_id FROM fin_document WHERE id = @id)))
               & (@num := LPAD(IF( @c, b.num, (SELECT num FROM fin_document WHERE id = @id)), 5, ' '))
               & (@key := IF( @c, @num, CONCAT(@num, '', @key) ))
               & (@previous_id := b.id),0),@key) k,
               b.id
        FROM fin_document a
        STRAIGHT_JOIN ( SELECT @previous_id := NULL, id, num FROM fin_document ) b ) a
            WHERE k IS NOT NULL
    ORDER BY id, LENGTH(k) DESC) a
JOIN fin_document b ON a.id = b.id
GROUP BY a.id
ORDER BY k;

fiddle (not sure why column k is not displayed correctly. column k represents the sorting key, and is built up with similar format as your original query) Also, it takes exponential execution time. So it may not be what you want.

edited May 23 '17 at 11:58

Community

1
1

answered Jun 11 '15 at 02:10

Fabricator

12,722
2
27
40

Mysql doesn't necessarily evaluate select fields left to right, so there is no guarantee the variables are evaluated in the order you hope they are. This could very well return different results across different versions or installations. – pala_ Jun 11 '15 at 14:19
@pala_, wow thanks. i didn't know about the undefined execution order. i merged them into one field. do you think it works now? – Fabricator Jun 11 '15 at 18:07
It might do - I generally try and force the order by putting all the variable action inside ugly nested conditional statements. – pala_ Jun 12 '15 at 06:51

score 0 · Answer 3 · answered Aug 24 '20 at 14:53

**

Adjacency list (Hierarchy) - Level based sorting/order

**

For anyone searching, If you have an Adjacency list ID->Parent structure, you can actually maintain a LEVEL BASED SORTING by using the Path enumeration model :)

In the Data table you would have the parent and a sort value column

And in order to generate the hierarchy with the correct sorting i use the following CTE:

CTE_Topic_Details AS
(
SELECT Topic_id, CONVERT(Topic_id, CHAR(100)) as path, Topic_name as TopFullN,CONVERT(Topic_sort, CHAR(100)) as SortGPS
FROM topic
WHERE Topic_Topic_id IS NULL
UNION ALL
SELECT e.Topic_id, CONCAT(d.path, ".", CONVERT(e.Topic_id, CHAR(20))),  CONCAT(d.TopFullN, ">", e.Topic_name), CONCAT(d.SortGPS, ".", CONVERT(e.Topic_sort, CHAR(20)))
FROM topic e
JOIN CTE_Topic_Details d ON e.Topic_Topic_id = d.Topic_id
)

Nice, isn't it !

MySQL Order By Hierarchy

3 Answers3

Adjacency list (Hierarchy) - Level based sorting/order