MySQL 8.0 Labs: [Recursive] Common Table Expressions in MySQL (CTEs), Part Three – hierarchies

Here is the third in a series of posts about CTEs, a new feature of MySQL 8.0, available in this Labs release. In the first post we had explored the new SQL syntax, and in the second we had applied it to generating series.

Today we’ll look into the most famous use of recursive CTEs: manipulating hierarchical data. That is, data in SQL tables representing a hierarchy like

  • CEO -> VP -> manager -> employee
  • item -> sub-item -> sub-sub-item
  • parent -> son -> grand-son
  • email or forum thread (question -> reply -> reply to the reply)
  • town -> region -> state

These hierarchies can be arbitrarily deep: that may be a large corporation, or a complex assembly, a numerous family, a heated email debate… From that data, a lot of interesting questions can be answered:

  • Human Resources is trying to spot over- or under-used VPs, they ask: how many employees directly or indirectly reporting to each VP?
  • VP is considering dropping product X from the catalog, she asks: what’s the cost of all items necessary to make the assembly X ?
  • Genealogy: how many people are descendants of Mrs X?
  • MySQL engineers are trying to spot which feature is a recurring problem to users, they ask : what are the topics in the “MySQL help forum” which had more than 20 replies in the last month?

All these questions can be answered by exploring the hierarchical data, accumulating information as we explore it, and presenting summary information to the requester. How to do that in practice, heavily depends on the chosen data model. There are at least two famous data models to represent hierarchies:

  • Adjacency list
  • Nested set

My former colleague Mike Hillyer has a nice explanation of the two models : check them out in paragraphs “Introduction”, “the Adjacency List Model” and “The Nested Set Model” here. It was written at the times of MySQL 4.1 but it still holds.

In his blog Mike has two points:

  • arbitrarily-deep hierarchies are difficult to handle with traditional SQL: either a stored procedure must be written (with WHILE loops and recursive procedure calls, to find  an item, then find its sub-items, then find sub-sub-items of the sub-items), or a maximum depth N must be assumed and then a N-table JOIN can be used.
  • the nested set  model is an easier-to-use alternative.

However, as we will shortly see, the advent of recursive CTEs puts the adjacency list model back on stage.

To prove my point, what I’m going to do now is to go through Mike’s post, review each problem he solved with the nested set model, and show how a recursive CTE makes it possible to solve the same problem with the adjacency list model. I’ll be using the same table data as Mike: table category, with columns category_id, name, parent : every row is a category which has a unique ID, a name, and the ID of its parent category. For example:

“Tube” (ID 3) belongs to parent having ID 2 which is “Televisions”; “Televisions” (ID 2) belongs to parent having ID 1 which is “Electronics”; “Electronics” (ID 1) is the top category as it has no parent (NULL)1.

I really encourage you to check the tree diagram in Mike’s “Introduction” section, it makes it clear how every category relates to each other.

Now, let’s go.

Retrieving a Full Tree

What this does is: start with the top category (which we grab with WHERE parent IS NULL), it is “Electronics”, then find all categories which have it as  parent: that gives us the categories right below “Electronics”, those at “depth 1” in the tree (“Televisions”, “Portable Electronics”). Then iterate: find all categories which have the “depth 1” categories as parent; that gives us the categories at “depth 2”. And so on: at depth 3 there is only “Flash”,  and the recursive SELECT finds nothing at depth 4: so it returns no new rows, and the CTE is done.

You may notice that the query’s result is the same as in Mike’s blog (it better be!), though not in the same order. Mike used ORDER BY node.lft which achieves a so-called depth-first order: you see the children of “Televisions” (“Tube”, …) before the siblings of “Television” (“Portable Electronics”). The order of my result is apparently breadth-first (siblings before children); however, as usual in SQL, if you don’t write ORDER BY, no order is guaranteed. If we want an order, let’s request it:

  • to get breadth-first order: add an integer column “depth”, increment it as you dive deeper, and order by it:

  • to get depth-first order: add a character-string column “path”, extend it as you dive down, and order by it:

I had already mentioned the necessity of CAST here : the type of the path column is determined from the anchor SELECT, and it has to be long enough to fit the path of the deepest leaf in the tree: CAST ensures that.

Finding all the leaf nodes

No change here, the adjacency list model already allowed to do that, no need for CTEs: just find rows which ID is not the parent of another row; a LEFT JOIN or a subquery with a NOT EXISTS or NOT IN predicate can do that; as Mike has given the LEFT JOIN solution I’ll give the subquery one, just for fun:

Retrieving a Single Path

Say, the path of “Flash”: start from “Flash” and go to its parent, then to the parent of its parent, up to the top:

The order of rows is from child to parent; if the opposite order is desired, add a depth and order by it:

Finding the Depth of the Nodes

We want one item, then right under it we want its children indented to the right. So we want depth-first order (children before siblings): a path column is needed. The amount of necessary indentation is easily calculated, by adding a depth column (it would also be possible, instead, to count the number of commas in path and use that as depth):

Depth of a sub-tree

We want to see the sub-tree of a certain category, and to know the depth of every sub-category. Start from the sub-tree’s root and add a depth column. Depth-first order is wanted, so add a path column:

Find the immediate subordinates of a node

Same query as above, but limit the dive to those which have depth=0; no need for a path as they’re all on the same level:

Aggregate functions in a nested set

Adding the same product table as Mike, we want to know how many products a category has; including indirect containment. So we first get categories which directly contain a product, then we join those categories with their parents, to reflect that parents also contain the said product. In the result of the CTE, we have one row per “container and (in)directly contained product”, and we segment that per container, with GROUP BY:

Conclusion

Today with recursive CTEs it is totally possible to answer complicated questions about a hierarchy represented in the adjacency list model: depth, sub-tree, immediate children, breadth-first order, depth-first order…

Does that mean that the nested set model is dead? It is not. If you compare Mike’s queries with mine, his are often shorter. On the other hand, queries to maintain the nested set model in the event of adding/deleting a node, have to be multi-statement ones and must use concurrency control (you can see them in the “Adding new nodes” and “Deleting nodes” section in Mike’s blog). Whereas in the adjacency list model, adding is one short INSERT. The easier insertions, harder reads of that model is easy to explain: in that model, only the direct containment is represented in the table (one row points to its parent). In the nested set model, indirect containment is also represented (with the numeric intervals lft and rgt, any two rows are easily put into relation): in other words, the nested set model puts more information right into the table; it makes reading easier as more information is readily available, and it makes writing harder as more information has to be computed and saved at writing time.

Food for thought…

That was a long blog… it is appropriate to say:

1. SQL authors tend to use the words adjacency list model for such table so I’ll use them too throughout this post, for consistency. But a real adjacency list model would contain one row per node, and in that row, the list of all adjacent nodes – nodes which are directly linked to this node. So, the row of TELEVISIONS would list both its parent ELECTRONICS and its children (TUBE, etc). In our table the row of TELEVISIONS lists only its parent, so our table is actually a collection of edges, it’s in fact using the edge list model. Thanks Peter Brawley for pointing this out. More information here.

5 thoughts on “MySQL 8.0 Labs: [Recursive] Common Table Expressions in MySQL (CTEs), Part Three – hierarchies

  1. “In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.” -https://en.wikipedia.org/wiki/Adjacency_list

    SQL custom diverges from this, using “adjacency list” to refer to what graph theory calls the edge list.

    Seems to me a paper on using CTEs with edge lists in MySQL ought to at least acknowledge this fundamental terminological confusion.

    1. Hello Vasiliy. Thanks for the note, I fixed the link. And, thanks a lot for the translation! I think that for now it’s the last article, but I’ll write some again when MySQL 8.0.1 goes out.

Leave a Reply

Your email address will not be published. Required fields are marked *

Please enter * Time limit is exhausted. Please reload CAPTCHA.