ORDER BY with hierarchical data

Hi,

I have a question regarding sorting and ordering of hierarchical data
following this tutorial: http://dev.mysql.com/tech-resources/...ical-data.html.

When using the Modified Pre-order Tree Traversal algorithm, is there a
way to have MySQL sort the names, but retaining the tree order?

When looking at this query:

SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

Everything is ordered by node.lft, which contains unique values along
the whole column. This means adding another ordering by node.name will
have no effect.

Additionally, When putting everything into a result table to order on
that, we loose the relationship between the nodes.
SELECT * FROM (
SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft) AS t3
ORDER BY t3.name

Is there a way out of this problem?

Thanks

On Fri, 01 Feb 2008 15:28:37 +0100, <pieter.thoma@gmail.com> wrote:

> Hi,
>
> I have a question regarding sorting and ordering of hierarchical data
> following this tutorial:
> http://dev.mysql.com/tech-resources/...ical-data.html.
>
> When using the Modified Pre-order Tree Traversal algorithm, is there a
> way to have MySQL sort the names, but retaining the tree order?
>
> When looking at this query:
>
> SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
> FROM nested_category AS node,
> nested_category AS parent
> WHERE node.lft BETWEEN parent.lft AND parent.rgt
> GROUP BY node.name
> ORDER BY node.lft;
>
> Everything is ordered by node.lft, which contains unique values along
> the whole column. This means adding another ordering by node.name will
> have no effect.
>
> Additionally, When putting everything into a result table to order on
> that, we loose the relationship between the nodes.
> SELECT * FROM (
> SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
> FROM nested_category AS node,
> nested_category AS parent
> WHERE node.lft BETWEEN parent.lft AND parent.rgt
> GROUP BY node.name
> ORDER BY node.lft) AS t3
> ORDER BY t3.name
>
> Is there a way out of this problem?

What is it exactly that you want? Siblings ordered by name, with tree
'retention'? This could be a hack that does it, not 100% reliable though
(I like explicit joins, they are more clear to me):

SELECT CONCAT( REPEAT(' ', COUNT(parent.name)-1), node.name) AS name,
GROUP_CONCAT(parent.name ORDER BY parent.lft SEPARATOR '~') as 'path',
node.lft
FROM nested_category AS node
LEFT JOIN nested_category AS parent
ON node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY path,node.name;

'~' is chosen because of it's high ascii value. In case of unicode /
higher characters, this could potentially break. If the
possibilities/character set for node.name is limited, this will work
though.
+-----------------------+----------------------------------------------------+-----+
| name |
path | lft |
+-----------------------+----------------------------------------------------+-----+
| ELECTRONICS |
ELECTRONICS | 1 |
| PORTABLE ELECTRONICS | ELECTRONICS~PORTABLE
ELECTRONICS | 10 |
| 2 WAY RADIOS | ELECTRONICS~PORTABLE ELECTRONICS~2 WAY
RADIOS | 17 |
| CD PLAYERS | ELECTRONICS~PORTABLE ELECTRONICS~CD
PLAYERS | 15 |
| MP3 PLAYERS | ELECTRONICS~PORTABLE ELECTRONICS~MP3
PLAYERS | 11 |
| FLASH | ELECTRONICS~PORTABLE ELECTRONICS~MP3
PLAYERS~FLASH | 12 |
| TELEVISIONS |
ELECTRONICS~TELEVISIONS | 2 |
| LCD |
ELECTRONICS~TELEVISIONS~LCD | 5 |
| PLASMA |
ELECTRONICS~TELEVISIONS~PLASMA | 7 |
| TUBE |
ELECTRONICS~TELEVISIONS~TUBE | 3 |
+-----------------------+----------------------------------------------------+-----+
--
Rik Wasmus