Sorting a subtree in a closure table hierarchical-data structure
This question comes up frequently not only for Closure Table but also for other methods of storing hierarchical data. It's not easy in any of the designs.
The solution I've come up with for Closure Table involves one additional join. Every node in the tree joins to the chain of its ancestors, like a "breadcrumbs" type query. Then use GROUP_CONCAT() to collapse the breadcrumbs into a comma-separated string, sorting the id numbers by depth in the tree. Now you have a string by which you can sort.
SELECT c2.*, cc2.ancestor AS `_parent`, GROUP_CONCAT(breadcrumb.ancestor ORDER BY breadcrumb.depth DESC) AS breadcrumbsFROM category AS c1JOIN 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 = 1GROUP BY cc1.descendantORDER BY breadcrumbs;+----+------------+--------+---------+-------------+| id | name | active | _parent | breadcrumbs |+----+------------+--------+---------+-------------+| 1 | Cat 1 | 1 | NULL | 1 || 3 | Cat 1.1 | 1 | 1 | 1,3 || 4 | Cat 1.1.1 | 1 | 3 | 1,3,4 || 7 | Cat 1.1.2 | 1 | 3 | 1,3,7 || 6 | Cat 1.2 | 1 | 1 | 1,6 |+----+------------+--------+---------+-------------+Caveats:
- The id values should have uniform length, because sorting "1,3" and "1,6" and "1,327" might not give the order you intend. But sorting "001,003" and "001,006" and "001,327" would. So you either need to start your id values at 1000000+, or else use
ZEROFILLfor ancestor and descendant in the category_closure table. - In this solution the display order depends on the numeric order of category id's. That numeric order of id values may not represent the order you want to display the tree. Or you may want the freedom to change the display order irrespective of the numeric id values. Or you may want the same category data to appear in more than one tree, each with different display order.
If you need more freedom, you need to store the sort-order values separately from the id's, and the solution gets even more complex. But in most projects, it's acceptable to use a short-cut, giving the category id's double-duty as the tree display order.
Re your comment:
Yes, you could store "sibling sort order" as another column in the closure table, then use that value instead of ancestor to build the breadcrumbs string. But if you do that, you end up with a lot of data redundancy. That is, a given ancestor is stored on multiple rows, one for each path descending from it. So you have to store the same value for sibling sort order on all of those rows, which creates the risk of an anomaly.
The alternative would be to create another table, with only one row per distinct ancestor in the tree, and join to that table to get the sibling order.
CREATE TABLE category_closure_order ( ancestor INT PRIMARY KEY, sibling_order SMALLINT UNSIGNED NOT NULL DEFAULT 1);SELECT c2.*, cc2.ancestor AS `_parent`, GROUP_CONCAT(o.sibling_order ORDER BY breadcrumb.depth DESC) AS breadcrumbsFROM category AS c1JOIN 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_closure_order AS o ON breadcrumb.ancestor = o.ancestorWHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1GROUP BY cc1.descendantORDER BY breadcrumbs;+----+------------+--------+---------+-------------+| id | name | active | _parent | breadcrumbs |+----+------------+--------+---------+-------------+| 1 | Cat 1 | 1 | NULL | 1 || 3 | Cat 1.1 | 1 | 1 | 1,1 || 4 | Cat 1.1.1 | 1 | 3 | 1,1,1 || 7 | Cat 1.1.2 | 1 | 3 | 1,1,2 || 6 | Cat 1.2 | 1 | 1 | 1,2 |+----+------------+--------+---------+-------------+