Sorting Closure Table Hierarchical Data Structure

Question

You can think this question as follow-up for that one: Sorting a subtree in a closure table hierarchical-data structure

Let's consider the modified example (with a new row called rating in category table):

--
-- Table `category`
--

CREATE TABLE IF NOT EXISTS `category` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) COLLATE utf8_czech_ci NOT NULL,
  `rating` int(11) NOT NULL,
  `active` tinyint(1) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;


INSERT INTO `category` (`id`, `name`, `rating`, `active`) VALUES
(1, 'Cat 1', 0, 1),
(2, 'Cat 2', 0, 1),
(3, 'Cat  1.1', 0, 1),
(4, 'Cat  1.1.1', 2, 1),
(5, 'Cat 2.1', 0, 1),
(6, 'Cat 1.2', 2, 1),
(7, 'Cat 1.1.2', 3, 1);

--
-- Table `category_closure`
--

CREATE TABLE IF NOT EXISTS `category_closure` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `ancestor` int(11) DEFAULT NULL,
  `descendant` int(11) DEFAULT NULL,
  `depth` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `fk_category_closure_ancestor_category_id` (`ancestor`),
  KEY `fk_category_closure_descendant_category_id` (`descendant`)
) ENGINE=InnoDB;

INSERT INTO `category_closure` (`id`, `ancestor`, `descendant`, `depth`) VALUES
(1, 1, 1, 0),
(2, 2, 2, 0),
(3, 3, 3, 0),
(4, 1, 3, 1),
(5, 4, 4, 0),
(7, 3, 4, 1),
(8, 1, 4, 2),
(10, 6, 6, 0),
(11, 1, 6, 1),
(12, 7, 7, 0),
(13, 3, 7, 1),
(14, 1, 7, 2),
(16, 5, 5, 0),
(17, 2, 5, 1);

Thanks to Bill Karwin, i am able to sort my data based on numeric order of id's with following query:

SELECT c2.*, cc2.ancestor AS `_parent`,
  GROUP_CONCAT(breadcrumb.ancestor ORDER BY breadcrumb.depth DESC) AS breadcrumbs
FROM category AS c1
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id)
JOIN category AS c2 ON (cc1.descendant = c2.id)
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1)
JOIN category_closure AS breadcrumb ON (cc1.descendant = breadcrumb.descendant)
WHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1
GROUP BY cc1.descendant
ORDER BY breadcrumbs;

+----+------------+--------+---------+-------------+
| id | name       | active | _parent | breadcrumbs |
+----+------------+--------+---------+-------------+
|  1 | Cat 1      |      1 |    NULL | 1           | Rating: 0
|  3 | Cat 1.1    |      1 |       1 | 1,3         | Rating: 0
|  4 | Cat 1.1.1  |      1 |       3 | 1,3,4       | Rating: 2
|  7 | Cat 1.1.2  |      1 |       3 | 1,3,7       | Rating: 3
|  6 | Cat 1.2    |      1 |       1 | 1,6         | Rating: 2
+----+------------+--------+---------+-------------+

So far so good, now i want to sort this results using rating row from category table. It should be like this:

+----+------------+--------+---------+-------------+
| id | name       | active | _parent | breadcrumbs |
+----+------------+--------+---------+-------------+
|  1 | Cat 1      |      1 |    NULL | 1           | Rating: 0
|  6 | Cat 1.2    |      1 |       1 | 1,6         | **Rating: 2**
|  3 | Cat 1.1    |      1 |       1 | 1,3         | Rating: 0
|  7 | Cat 1.1.2  |      1 |       3 | 1,3,7       | **Rating: 3**
|  4 | Cat 1.1.1  |      1 |       3 | 1,3,4       | **Rating: 2**
+----+------------+--------+---------+-------------+

So all data should have both breadcrumbs ASC and rating DESC order without breaking the hierarchy. Is this possible with one query? Is this even possible?

Thanks.

UPDATE:

Here is what i've tried so far based on Bill's answer's second part:

SELECT c2.*, cc2.ancestor AS `_parent`,
  GROUP_CONCAT(c2.rating ORDER BY breadcrumb.depth DESC) AS breadcrumbs
FROM category AS c1
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id)
JOIN category AS c2 ON (cc1.descendant = c2.id)
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1)
JOIN category_closure AS breadcrumb ON (cc1.descendant = breadcrumb.descendant)
WHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1
GROUP BY cc1.descendant
ORDER BY breadcrumbs;

+----+------------+--------+---------+-------------+
| id | name       | active | _parent | breadcrumbs |
+----+------------+--------+---------+-------------+
|  7 | Cat 1.1.2  |      1 |       3 | 3,3,3       | **Rating: 3**
|  6 | Cat 1.2    |      1 |       1 | 2,2         | **Rating: 2**
|  4 | Cat 1.1.1  |      1 |       3 | 2,2,2       | **Rating: 2**
|  1 | Cat 1      |      1 |    NULL | 0           | Rating: 0
|  3 | Cat 1.1    |      1 |       1 | 0,0         | Rating: 0
+----+------------+--------+---------+-------------+

Also please be mind that rating values can be SIGNED (negative) as well.

POSSIBLE ANSWER:

Not working with 2 roots, check the comments.

SELECT c2.*, cc2.ancestor AS `_parent`,
  GROUP_CONCAT(999-c3.rating ORDER BY breadcrumb.depth DESC) AS breadcrumbs
FROM category AS c1
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id)
JOIN category AS c2 ON (cc1.descendant = c2.id)
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1)
JOIN category_closure AS breadcrumb ON (cc1.descendant = breadcrumb.descendant)
JOIN category AS c3 ON (breadcrumb.ancestor = c3.id)
WHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1
GROUP BY cc1.descendant
ORDER BY breadcrumbs;

Bill actually covered this in the second part of his answer. His `category_closure_order` is your `category` and his `sibling_order` is your `rating`, or more precisely `999-rating`, as you want to decrement. — Solarflare, Jul 17 '18 at 06:53
Thanks for your kind attention Solarflare, i've updated my question. — oezby, Jul 17 '18 at 11:25
You didn't add the required join. You literally just have to do a 1:1 replace of `category_closure_order` by `category` and `o.sibling_order` by `999-o.rating` in Bills (2nd part of his) answer — Solarflare, Jul 17 '18 at 11:36
Addon to your edit: if you have negative ratings, you have to adjust 999 to something different (Maybe `500-o.rating`, depending on your range - you have to ensure that you have the same length for all entries). As to your result: it doesn't seem to be ordered at all, are you sure that this is the result you are getting? If I run this in [sql fiddle](http://sqlfiddle.com/#!9/96c3e5e/11) it gives the expected result (apart from the reverse order of the rankings, as there is no `500-` yet) — Solarflare, Jul 17 '18 at 11:39
You were right, results was wrong. I've noticed a typo and i am so sorry for that. I've updated my question again and that `999-o.rating` trick saved the day! Please check my answer and if everything seems okay, guide me to give you some reputations. — oezby, Jul 17 '18 at 11:59
Addition: this approach is not working with two roots. Check the [fiddle](http://sqlfiddle.com/#!9/96c3e5e/15). — oezby, Jul 17 '18 at 20:43

IVO GELOV · Accepted Answer · 2018-07-18T11:22:36.020

0

EDIT - updated the sorting argument

I believe that this is the query that you need/want. Since you have no PARENT_ID column in the category table I first get all root items from the closure and then find all of their children, ordering by a modified breadcrumb in which the last item is not the ID of the current leaf but its rating instead. So you get reverse sorting by rating while still keeping the hierarchy levels.

SELECT category.id,name,rating,
  (SELECT GROUP_CONCAT(CONCAT(LPAD(1000 - rating, 5, "0"), "#", ancestor) ORDER BY depth DESC) 
    FROM category_closure LEFT JOIN category AS cat ON ancestor = cat.id WHERE descendant = category.id
  ) AS sorting
FROM category_closure
LEFT JOIN category ON descendant = category.id
WHERE ancestor IN
  (SELECT ancestor FROM category_closure AS c1 
   WHERE depth = 0 
     AND NOT EXISTS(SELECT 1 FROM category_closure AS c2 
       WHERE c2.descendant = c1.descendant AND depth > 0)
  )
ORDER BY sorting

edited Jul 18 '18 at 11:22

answered Jul 17 '18 at 12:57

IVO GELOV

13,496
1
17
26

This is a completely different and wise approach. I will give it a shot for sure. As i see u selected only the root element in SELECT 1 but what if I want to select multiple root elements, merge and order them all together? I could do this in Bil's query with WHERE c1.id IN (:array) right? Your approach seems more like for one root element i believe. – oezby Jul 17 '18 at 17:03
The sub-query which uses `c1` and `c2` is fetching all categories which are not already a child of another category - I believe there can be more than 1. This sub-query is only needed because you do not have a PARENT_ID column in the `category` table so I can filter by `PARENT_ID IS NULL`. If you want to start from a specific group of nodes and continue below them - you simply have to list their IDs inside the IN predicate, replacing this sub-query. – IVO GELOV Jul 17 '18 at 17:36
Please check the [sql fiddle](http://sqlfiddle.com/#!9/dc8a7c/1/0) Cat 2 with rating 2 and its childs are not moving on top of the hierarchy. – oezby Jul 17 '18 at 18:37
Okay, I updated to sorting argument and I believe this is what you wanted to achieve. You have to replace the constant 1000 with the maximum positive rating you expect to have. We sort by rating first but then follow the breadcrumb. – IVO GELOV Jul 18 '18 at 11:24
You solved my question as i asked like a boss! Thank you so much. Since you build this query, i've one last question for you as a favor just to make things much clear (of course you don't have to answer). What if i wanted to order root elements in `id DESC` order with their children (Cat 2 [rating:0] and its children - Cat 1 [rating:0] and its children) without breaking the rating orders? How would you modify this query? You could think this is a bit off-question but i am asking you this because i am eager to learn from you. – oezby Jul 18 '18 at 13:34
You can append the ID at the end - so that if two children have the same rating and the same parent they will be sorted according to their ID. However, in order to sort DESC by ID you have to alter them - like `CONCAT(LPAD(1000 - rating, 5, "0"), "#", ancestor,"#",LPAD(1e9 - descendant,10,"0"))` I do not think it is wise to sort by ID - perhaps by name ? But it is your call. – IVO GELOV Jul 18 '18 at 13:52
Textarea placeholder saying that avoid "thanks" in comments but i couldn't help myself to thank you for your efforts, my friend. Thanks again. – oezby Jul 18 '18 at 14:17
Well, you could also upvote the answer as well :))) All the best and such! – IVO GELOV Jul 18 '18 at 14:19
I need 5 more reputations for that. As soon as i get 15, i am going to upvote all of your useful answers :) – oezby Jul 18 '18 at 14:33

Sorting Closure Table Hierarchical Data Structure

1 Answers1

EDIT - updated the sorting argument