Geek Answers Handbook

Nested set query to retrieve all the ancestors of each node

I have a MySQL query that I thought works fine to get all the ancestors of each node, starting from the top node, right up to its immediate node. However, when I added level 5 to the nested set, it broke.

The following are examples of tables, queries, and SQL scripts:

Four levels of nested dialing:

CREATE TABLE Tree (title varchar(20) PRIMARY KEY, `tree` int, `left` int, `right` int); INSERT Tree VALUES ("Food", 1, 1, 18), ('Fruit', 1, 2, 11), ('Red', 1, 3, 6), ('Cherry', 1, 4, 5), ('Yellow', 1, 7, 10), ('Banana', 1, 8, 9), ('Meat', 1, 12, 17), ('Beef', 1, 13, 14), ('Pork', 1, 15, 16);

Request:

 SELECT t0.title node ,(SELECT GROUP_CONCAT(t2.title) FROM Tree t2 WHERE t2.left<t0.left AND t2.right>t0.right ORDER BY t2.left) ancestors FROM Tree t0 GROUP BY t0.title;

The returned result for node Banana is Food,Fruit,Yellow - Perfect. You can see it here SQL Fiddle - Level 4

When I run the same query in a table below level 5, nodes of the fifth level are returned in the wrong order:

 CREATE TABLE Tree (title varchar(20) PRIMARY KEY, `tree` int, `left` int, `right` int); INSERT Tree VALUES ("Food", 1, 1, 24), ('Fruit', 1, 2, 13), ('Red', 1, 3, 8), ('Cherry', 1, 4, 7), ('Cherry_pie', 1, 5, 6), ('Yellow', 1, 9, 12), ('Banana', 1, 10, 11), ('Meat', 1, 14, 23), ('Beef', 1, 15, 16), ('Pork', 1, 17, 22), ('Bacon', 1, 18, 21), ('Bacon_Sandwich', 1, 19, 20);

The return result for Bacon_Sandwich is Bacon,Food,Meat,Pork , which is not correct, it should be Food,Meat,Pork,Bacon . You can see it here SQL Fiddle - 5 levels

I am not sure what is happening because I am not well versed in subqueries. Can anyone shed some light on this?

EDIT AFTER RESEARCH:

Wow !! It seems like writing all this, and reading the order with GROUP_CONCAT gave me some inspiration.

Adding ORDER BY to the actual GROUP_CONCAT function and removing it from the end of the subquery solved the problem. Now I get Food,Meat,Pork,Bacon for node Bacon_Sandwich

 SELECT t0.title node ,(SELECT GROUP_CONCAT(t2.title ORDER BY t2.left) FROM Tree t2 WHERE t2.left<t0.left AND t2.right>t0.right ) ancestors FROM Tree t0 GROUP BY t0.title;

I still don’t know why. If ORDER BY at the end of a subquery works for 4 levels, but not for 5?!?!

If someone can explain what the problem is and why moving ORDER BY corrects it, I would be very grateful.

+6
source share
2 answers

First of all, it's important to understand that you have an implicit GROUP BY

If you use a group function in a statement that does not contain a GROUP BY clause, it is equivalent to grouping by all lines.

To make the point clearer, I will leave the subqueries and reduce the problem to a banana. A banana is a lot [10, 11]. The correct sorted ancestors are as follows:

 SELECT "banana" as node, GROUP_CONCAT(title ORDER by `left`) FROM Tree WHERE `left` < 10 AND `right` > 11 GROUP BY node;

ORDER BY must be in GROUP_CONCAT() , as you want the aggregation function to be sorted. ORDER BY external sorts by aggregated results (i.e., the result of GROUP_CONCAT() ). The fact that he worked up to level 4 is just luck. ORDER BY does not affect aggregate function. You will get the same results with or without ORDER BY :

 SELECT GROUP_CONCAT(title) FROM Tree WHERE `left` < 10 AND `right` > 11 /* ORDER BY `left` */

This may help to understand what SELECT GROUP_CONCAT(title ORDER BY left) FROM Tree WHERE … ORDER BY left does:

  • Get a selection ( WHERE ), which results in three lines in undefined order:

      ("Food")
 ("Yellow")
 ("Fruit")

  • Match the result in one line (implicit GROUP BY ) to be able to use the aggregate function:

      (("Food", "Yellow", "Fruit"))

  • Omit the aggregate function ( GROUP_CONCAT(title, ORDER BY link) ). That is, sort by reference and then combine:

      ("Food, Fruit, Yellow")

  • And now, finally, it sorts this result ( ORDER BY ). Since this is only one line, sorting does not change anything.

      ("Food, Fruit, Yellow")
+5
source

You can get the result using JOIN or SUB-QUERY .

Using JOIN:

 SELECT t0.title node, GROUP_CONCAT(t2.title ORDER BY t2.left) ancestors FROM Tree t0 LEFT JOIN Tree t2 ON t2.left < t0.left AND t2.right > t0.right GROUP BY t0.title;

Mark SQL FIDDLE DEMO

Using SUB-QUERY:

 SELECT t0.title node, (SELECT GROUP_CONCAT(t2.title ORDER BY t2.left) FROM Tree t2 WHERE t2.left<t0.left AND t2.right>t0.right) ancestors FROM Tree t0 GROUP BY t0.title;

Mark SQL FIDDLE DEMO

OUTPUT

 | NODE | ANCESTORS | |----------------|-----------------------| | Bacon | Food,Meat,Pork | | Bacon_Sandwich | Food,Meat,Pork,Bacon | | Banana | Food,Fruit,Yellow | | Beef | Food,Meat | | Cherry | Food,Fruit,Red | | Cherry_pie | Food,Fruit,Red,Cherry | | Food | (null) | | Fruit | Food | | Meat | Food | | Pork | Food,Meat | | Red | Food,Fruit | | Yellow | Food,Fruit |

In your extra query, you used ORDER BY after WHERE , which will not affect the output. By default, the GROUP_CONCAT () function will order the output row in ascending column value. He will not consider the explicit ORDER BY clause.

If you check your output of the first query, which returns the data in ascending order of the title column. Thus, the return result for node Banana is Food,Fruit,Yellow .

But in your second result for Bacon_Sandwich there is Bacon,Food,Meat,Pork , because in ascending order Bacon comes first than Food .

If you want to order the result based on the left column, you must specify ORDER BY inside the GROUP_CONCAT() function, as described above. Check out my both questions.

I prefer to use JOIN instead of SUB-QUERY for better performance.

+2
source

More articles:


All Articles