Representing Hierarchies in Relational Databases

Speaker 1: Uh Jacob has a talk, and I can't read with all this light. Um Yeah. I know what I'm doing. Um, relational databases and stuff, so let's give them a hand.

Speaker 2: Uh hello. Okay. Welcome to my talk about representing trees in databases. And many thanks to the organizers to bring DjangoCon Europe to this wonderful location. Um hi, I'm Jacob. Um in 1997 I used Python for the first time and in 2011 um I switched to Django and since then I never looked back and I only use Django for web development. I must admit that I contributed almost nothing to the Django framework itself. Uh instead I'm maintaining a few popular search party Django apps. Um For instance, uh Django Shop, uh that's an e-commerce framework based on Django CMS, uh

Speaker 2: Django Angular On DjangoCon 2014, I gave a talk on how Angular GS plays nice with Django. Django CMS Cascade, that's a full-featured plugin system for Django CMS. Django WebSocket Redis, a WebSocket library for Django written in 2013. before channels uh was available. Um Django admin sortable too, a adds sorting capabilities to list views in the Django admin um Django SAS processor, uh reference for your SAS, your SCSS files directly from uh Django templates and uh Python code.

Speaker 2: In late 2016 on Django under the hood, I inherited together with uh Jacopo and others um uh uh jungle tree beard from the then maintainer Gustavo Picon. And having to maintain that library inspired me to give this talk here. I'm working as a freelance software developer and live in Innsbruck in Austria. So what's our problem and what we do we try to solve? Say we have a grocery store with a bunch of products organized in different categories and subcategories And just as in the virtual world where we use database tables

Speaker 2: and uh model to model products and categories. In Django we use a model entity to describe each category. These model entities then are grouped into a tree. Whenever we have to render a list view of our products belonging to say category meat , we need to know its subcategories. Or When we want to render the breadcrumbs for category turkeys, we need to know their ancestors When building a database model, it turns out that the most obvious solution is not always the best. In this presentation I will show four different solutions to solve this problem.

Speaker 2: Where else do we use hierarchical representations? In content management systems to organize pages and nested content. Hierarchies in corporates for discussion threads, for emulating folders, and many more. So solution one is the adjacent lists. That's the most natural representation of a tree in a database. uh is to have a foreign key pointing to its parent node. Here the numbers in the nodes represent their primary keys. As Django model, it looks like this We add a nullable foreign key pointing onto self.

Speaker 2: This creates a recursive relationship. This statement shows the simplified transition of our Django model into a database schema. And this kind of representation commonly is known as the adjacent list SQL pattern. A common use case is to find all nodes below a given node. In this example, we look for the descendants of the highlighted node. A Python function to get the set its descendants might be implemented such as this. First we create a career set for all immediate children. Then we recursively call that function for over all children in that query set.

Speaker 2: Here the problem is that traversing the tree scales really badly. We need one database query for each depth level. This adds many round trips between the database and our Django application, and we get an iterator instead of a query set. losing all the useful methods on that class. An alternative would be to to to do the recursive join over all the nodes. A SQL statement Um for such a query might look like this. Since we don't know the depths of the tree, building such a statement in a generic way is nearly impossible. and results are grouped by columns rather than by rows, so that's not a very good option.

Speaker 2: Ascending the tree is a bit simpler. Here we look for the ancestor of the highlighted node but we still have to do a recursion on the function get ancestors with four separate queries to the database. Here we also use the chain keyword to build our result set. But again, we return an iterator instead of a query set, losing all the useful methods on the class. Another problem is attribute filtering. Say our nodes are colored and we want to find the red ones. If we change the code to filter by color We would miss out the node with the ID 16.

Speaker 2: Therefore we must do the filtering by the application, and that's this means that we first have to fetch all nodes from the database And afterwards we can apply the filter in Python, but that causes a lot of unnecessary data transfer. Therefore, some engineers have looked for alternative solutions. For instance, the materialized pastry was described by Vadim Tropashko. In uh SQL design patterns and published in 2006. In the materialized pass tree, we encode the position of each note inside a car field. For each depth level we use the word with a fixed step length. The root node starts with A.

Speaker 2: To its first child we append another A, giving a A. For its sibling we use AB. for um its next child uses uh ABA and its sibling A B B and so on This materialized pass is applied to all nodes of the tree. If you have multiple trees, the pass field on the root node of the second tree starts with a B. Therefore we ca can have multiple roots, uh multiple trees uh uh with uh one root each. Here we create a Django model for our node. Instead of a foreign key onto self, we use an index car field named path.

Speaker 2: In that field we store an encoded position of our node inside the tree. By default, Django TreeBeard uses a step length of four with an alphabet of 36 characters. This allows each node to have a maximum of about 1. 6 million immediate children But in the next slides, for simplicity, I use a step length of one with an alphabet of um 26 characters. So here are examples. We want to find all descendants of the highlighted node. The pass field. contains the word AAA. So we look for all nodes starting with that pattern.

Speaker 2: This Python function returns a query set for all the descendants. Here we use the starts with restriction on the query filter This makes use of the database index on the pass field. Therefore we have a fast query to fetch the subtray We also want to exclude the starting node from the query set. And this is a simplified SQL statement. It uses the like clause with the percent sign at the end, therefore the text index works, and the database excess as expected Remember beginning the like clause with a person sign would require a full table scan, but so the database index still works.

Speaker 2: If you create your own tree model, use an alphabet with a consistent sorting order and check the collations of your database. UTF-8 characters in your alphabet are not a good choice because depending on your database settings and language settings they may have different sorting orders. With this short addition to the code, we can return the query set ordered by depth level. We want to traverse the tree from the highlighted node upwards. Again, we use the pass field. Here it's the word AAACA By removing the letters from the end of the

Speaker 2: word, we can build a list of ancestor past values. In our example AAAC AAA, AA and finally our root node A Now it's just a simple lookup to find the ancestor nodes. We just have to check if the path attribute is in that list This time we return the query set ordered by tree level from the button to top. Nested sets tree is another approach for solving our tree problem. It has been described by Joe Chalko in Trees and Hierarchies in SQL for Smarties and published in 2012. The idea between nested sets is to create an envelope over the uh over the tree.

Speaker 2: Each node has two integer fields, left and right. They both follow this rule for each note. Left is smaller than all descendants of the given node, and right is greater than all descendants of a given node. We can draw a graph connecting these numbers together. Then this graph cuts each node twice. The first time while descending and the second time while ascending. Except for leaf nodes, they always have consecutive numbers for the left and right values. Here for instance uh 16 and 17. Using these two numbers, we can traverse the tree in both directions with one single database query. In Django, we add two positive integer fields to our nested sets

Speaker 2: model. Remember, left and right are not foreign keys, but they're indexed. And since these numbers are used a lot in our queries, we add a database index. So we want to find all descendants of the highlighted node. First we take the left and the right value of that node We know that both values for left and right of all descendants lie between those two numbers, between 3 and 22. This simple Python function returns a query set of all descendants. First we construct a a range query.

Speaker 2: This filters out the whole sub subtree of our node. Finally we exclude the node from the query since we are interested only in the subtree. And again, we get the query set as expected. This time, however, unordered by depth. For completeness, this is the simplified SQL statement for that query. We want to find the ancestors of the highlighted node. First we check the left and right values of that node. We know that the left value of all ancestors must be smaller than our node's left value. We also know that the right value of all ancestors must be greater than our node's right value.

Speaker 2: This Python function returns a query set of all ancestors. With these two values, we can narrow down the query using a simple comparison. And again we get the expected query set. For ordering, we could either use the left or right value And here for completeness, check the SQL statement for that query. Simplified SQL statement So adding a node to a uh nested sets tree is a little bit more complicated. Say we want to add a new node just between uh below the high uh below the highlighted node.

Speaker 2: This Python function inserts a child node into our tree. First we filter out the nodes which will be affected by the update. Then we conditionally update the left values depending on their position. The right value is always increased by two. Now that we updated the right part of the tree, we can use the two free values for left and right. The new node now becomes part of the tree. Deleting a node is a similar operation with opposite deltas. Solution 4. Common table expressions have been introduced into the NC SQL

Speaker 2: 99 standard and are now supported by all major databases systems. In MySQL since version 8, in MariahDB since version 10. 2. 2, in SQL Lite since 3. 8. 3, and in Postgres since 8. 4 Common table expressions are used to simplify complex joins and subqueries and to provide a means to query hierarchical data. Here is a working SQL statement. First, we define a virtual table called tree. This SQL finds our starting node and initializes the recursive function. This part recursively fetches the descendants of our starting node.

Speaker 2: The last SQL statement fetches all descendants of the node with ID4, excluding itself. If you have duplicates, remove the all, but this requires extra time for sorting so leave it out by default. Remember, don't put the semicolon after the Wizard recursion class, otherwise our virtual table tree, is not available anymore. With this query, we can use the adjacent list pattern to fetch all descendants with one single query. The tree is still traversed recursively, but this time inside the database, and that's much faster because we have only one round trip from our application to the database. To fetch the ancestors

Speaker 2: of a given starting node, we just have to reverse the condition. To my knowledge, the Django RM currently does not offer any functions to implement common table expressions. So if we want to use this database feature, we have to use raw SQL. Now let's compare the different solutions. The adjacent lists without common table expressions shines for all operations. Except for tree traversals. However, this is the operation we usually use most. It only requires one additional field pointing on uh onto the parent node.

Speaker 2: Therefore we don't have any size limitations If you need multiple routes and sibling ordering , you need extra fields in your database model. The materialized path tree is a good compromise for all operations. The path field has a nice side effect that we don't need any extra fields for multiple routes or sibling ordering. Depending on the alphabet and step lengths, the size of the tree then is naturally limited. Strings and the pass field can become very long. In addition, we have to create a text index. This requires a lot of extra memory. Nested sets pattern is another interesting approach and commonly used. Treat traversals are very fast.

Speaker 2: However, when adding or deleting a node, we must update big parts of the tree. If you get one of the left or right numbers wrong, your complete tree is screwed up. By using common table expressions in adjacent lists, the problem of slow tree traversals is solved. Therefore, in my opinion, this is the best choice and should be used whenever possible. Computing the depths of a node can be integrated into the recursive SQL statement while fetching the tree. So let's uh compare three libraries which are available to solve uh the tree problem

Speaker 2: Django MPT is the most uh well-known library. It implements the nested sets tree pattern uh but identifies itself as as modified pre-order tree traversal. Therefore uh MPTT. Um Django Tribut implements the first three SQL pattern I've shown, the adjacent lists without common table expressions. Materialized paths and nested sets. They all share the same API to manipulate the tree so it's easy to exchange one against the other. And uh Django tree is a newest player of Django uh apps to solve this problem. It's by the way the only one using common table expressions.

Speaker 2: Uh however It declares itself as alpha and only supports Postgres as a database. Therefore, if your app shall be unopinionated to any databases, that's not an option for you. A side note, uh in Django CMS version 3. 1, Django MPTT has been replaced uh by Django Tree Beard. Uh the release notes uh states um Over the years, MPTT has proven not to be fast enough for big tree operations with more than a thousand nodes. Tree corruption because of transactional errors has also been a problem. And further, uh Django TreeBeard should make working with and using Django CMS better, faster

Speaker 2: and reliable. And for instance, uh the other big CMS, Wagtail, and Django Oscar, they both uh use Django Tree Beard to manage their internal uh trees. So what I would like to see in the future, add common table expression support directly into the Django RM. There is an issue, it's uh 28919 uh is a proposal for this, but um it's no uh decisions have uh taken be taken yet And if realized, implement a tree library similar to those three which already exist. And if you're working on a project which requires a modern tree implementation for your Jungle project

Speaker 2: Uh please contact me. Any questions?

Speaker 1: We will take questions in the form of a question at the microphone if anyone has any questions. No one. No questions. Will you take questions later? Oh. Hi

Speaker 2: Russell.

Speaker 3: Um wonder if you could go over the indexing requirements on on the uh those forms of the tree uh again. So uh uh is it just a matter of Text indexing the uh the uh materialized path and yeah and integer indexing the uh the uh right s is that all you need? Okay, and you get All the performance benefits you don't actually need to do anything special on those indexes beyond them doing basic integer, basic string indexing.

Speaker 2: Well if you have a Uh if you have special database requirements maybe, but those libraries they just use the normal uh the normal uh in the indices w which are available.

Speaker 3: Sure, okay.

Speaker 2: So Anybody else?

Speaker 4: Um So in your research did you not find any implementations of a closure table?

Speaker 2: Sorry?

Speaker 4: In your research, did you not find any implementations of a closure table for Django? That's another form of doing trees.

Speaker 2: Um no. That's

Speaker 4: Okay. I was just curious why uh yep.

Speaker 3: Yeah. Okay.

Speaker 2: Uh okay. Because all the libraries I was using was w they uh uh uh uh either used mpt or qbird and I never encountered any requirements for that uh for that Django application. So sorry about that but uh Um

Speaker 5: you mentioned the need of extra memory uh for s uh querying uh with Django Treebert. Uh like the text field that you see that it required a lot of extra memory. Uh can you give us uh an example of size on how much is a lot of memory

Speaker 2: Well you have to consider that um with Django Tree Bird you have a step length of four, uh with um so each depth level has four characters. And if you have a if you have l let's say uh a depth of of of thousand you then you have four thousand characters per node and you have to build an index over those four thousand characters per node. So That may sum up in case you have some size limitations on your database database. It's not really nowadays it's not really really huge, but I just wanted to mention it that uh it could be For instance the uh nested sets uh there the limitations are much smaller because you are

Speaker 2: you have only numbers and uh just integer integer numbers and you built an index over over those integer numbers.

Speaker 5: Okay, thank you.

Speaker 6: Yeah. So here. Uh you mentioned that you replaced Django MPT with Django tree bird in uh in Django CMS, right?

Speaker 2: Uh no I didn't do it. I didn't do it, but uh the developers of Django CMS did it, yes.

Speaker 6: So do you have knowledge which of the algorithms from Django TreeBear they the uh they use as a default

Speaker 2: Uh materialized path.

Speaker 6: So

Speaker 2: so of course

Speaker 6: Okay. Thank you. Uh

Speaker 5: is this working? Okay. Ah, perfect. Um I have a question. Uh is there or why do you limit the alphabet? Because if I think about um if you store a Varcher field And you would store it as UTF 8 for example where you would do this 8 bits per character. If you limit your alphabet, you kind of waste a lot of bits um in uh in that tree path. Why not use a large alphabet that is like complete set of for example UDF8?

Speaker 2: I f first of all I have to say I didn't write any of those libraries. Um I inherited Django Tree Beard uh because uh Gustavo Picon gave up development and uh since we used that in um applications uh for uh for clients and since Django CMS relied on it uh somebody had to take over the um uh the maintenance of of that library I just looked into the code and I saw that uh he was using thirty-six characters. Um I assume it's because of I assume it's because of collation problems uh if you if your databases are configured in different uh uh with different sorting order for alphabets.

Speaker 2: I assume. I don't know.

Speaker 5: Thanks.

Speaker 1: You have time for one more.

Speaker 7: Okay. Um did you do any uh Performance checks that you have some numbers compared to the client-side solutions with the CTE solutions on the database systems?

Speaker 2: Uh no, I didn't do that. I didn't I didn't make any benchmarks on that.

Speaker 1: Okay, let's thank Jacob again.