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 :(

Answer 1

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.

Answer 2

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.

Answer 3

**

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 !