Storing read optimized Tree in a Database
Introduction
Have you ever tried putting a Tree (a Parent-Child hierarchical structure) into a Database Table? What seems to be a trivial thing from an implementation point of view can sometimes turn into a real performance nightmare when a large number of requests continuously try to read different portions/branches of the Tree.
Example Use Case
Let's say we have an e-commerce solution with a multi-level Product Catalog. One of the most basic requirements would be that if a Customer browses one of the Categories, he should be presented with Products from that Category and from its Subcategories (regardless of their depth in the hierarchy).
If I browse for Phones, I should be presented with all the Phones of all the brands. I can then decide to browse a Sub-category of Phones - for example iPhones or Samsungs.
The same use case will apply to any Taxonomy based systems that need to fetch Items related to entire Branches of Trees, not only from single Nodes. It is based on an assumption that reading parts of the Tree will occur orders of magnitude more often than actually modifying the Tree's structure. In a typical use case an Internet Store is browsed way more often than it's Catalogue is modified in any way. So number of GET requests will typically outweigh the number of POST/PUT/DELETE requests by a significant factor.
Sometimes a kiss is not enough
Any developer tasked with implementing the above requirement would try to kiss (keep it simple, stupid) it at fist. A typical, naive implementation would entail putting a parent_id Foreign Key on our Tree Node Class/Table. Its super easy and very intuitive. But is it fast enough? What if our store becomes a hit with hundreds of thousands requests per day? Or what if we just want to ensure that we use the best engineering methods to fulfill this requirement?
Reading vs Writing performance dilemma
If there is any universal law in software engineering, it is that if something is easy/fast to write, it will be hard/slow to read. And if something is easy/fast to read, it will be hard/slow to write. Take a look at LinkedList vs ArrayList - those 2 implementations of Java's List interface are a perfect example of what I'm trying to show. LinkedList is fast to write, because adding a new Item requires only to alter the 2 neighbor's references to the next/previous item - we have an O(1) complexity there. The penalty for this is a slow random access reading speed - if you want to get to Item with index N, you will have to traverse the List from 0 to N-1 to get to it - O(n) complexity. ArrayLists offer completely opposite experience - reading is fast because you have an O(1) coming from the backing Array, but inserting something into an ArrayList is penalized with an O(n) complexity due to the need of modifying that same Array.
As you already know, our naive parent_id implementation will fall into the "easy to write, hard to read" category. Why? Well because it is really easy to insert a new Node into such Tree - you just set the parent_id value and you're done. However, reading a Tree Branch will require us to use Recursion, to get to each nested Branch of the Tree. We will need to recursively execute an SQL Query similar to this one:
select cat_id from categories where cat_parent_id = :parent_id
and gather the category IDs into some sort of Collection, that we will use to fetch the Products, that in turn belong to all the Subcategories of the chosen Parent Category:
select * from products where cat_id in (:gathered_category_ids)
OK, so what is the complexity of this? Well, it depends on how many sub-branches are in the requested Branch and how many nested levels are there (how deep is it). Generally the complexity for a Recursion is O(b^d) where b is a 'branching factor' and d is a 'depth of tree', so it will strongly depend on the size and depth of our Tree. In general though we can see that the ease of inserting a new Node into a Tree is heavily penalized with an exponential complexity of performing read operations on it.
Cache?
There's an old saying that if you have a problem and you decide to solve it by using cache, you now have two problems. While it may be an exaggeration, caching doesn't seem to be a good solution here. Different users may want to access different parts of the Tree so you'd have to cache every single Node along with its Children and then track those cached values to invalidate them if any of the Children of that Node are modified. I wouldn't exactly call it a clean solution.
Going Native?
One possible solution is to use native features of our Database. Many Databases offer support for Recursive Queries or Common Table Expressions (CTEs). While using such features will surely be faster than recursive execution of SQL statements from an external application, the recursive nature of the solution will remain there, just hidden from our sight by the Database. Below you can find couple of examples:
- Oracle's recursive queries:
select p.* from product p inner join categories c on p.cat_id = c.cat_id connect by prior c.cat_id = c.cat_parent_id where c.cat_parent_id = :parent_id
- MS SQL Server's Recursive CTEs:
WITH Products as ( SELECT p.* FROM product p WHERE p.parent_id is null UNION ALL SELECT p1.* FROM product p1 INNER JOIN Products Ps ON Ps.parent_id = p1.parent_id ) SELECT * From Products
The above solutions will also share the common issues of using native database features - they will be hard to test automatically (using an in-memory DB will require us to provide multiple implementations) and to maintain.
The Solution
OK, so is there any way that we can reverse the complexities in here? Is the an algorithm that allows for fast Tree traversal/reading? Even at the cost of elevated Tree structure modification complexity? Yes, it is called a Nested Set Model which is an algorithm of storing a read-optimized Trees in the Database Tables. For further reference, we will use a variation of the Nested Set that utilizes Depth Column, described at the end of the linked Wikipedia article.
So, how does it work? The theory is super simple, but its practical implementation can get pretty complicated - especially in the area of Tree modification operations (inserting, moving, deleting Nodes). Fortunately it just so happens that I've created an (actively maintained) Open Source Java library - NestedJ - that takes care of all the implementation details. Having that said, it would be a bad practice to just use it as a black box and not know, what is happening inside, so moving on to the inner workings of a Nested Set based Tree, take a look at this thing:
D:1 1 A 18
/ \
/ \
/ \
D:2 2 B 7 8 C 17
/ \ _______
/\ /\ \
D:3 / \ / \ 15 I 16
/ \ / \
/ 5 E 6 9 F 10 \
3 D 4 11 G 14
\
\
D:4 12 H 13
Wow. That seems not so simple after all, right? It actually is, let me explain:
- the above diagram depicts a Tree of letter-based Nodes from A to H
- each Node has 3 numeric values attached to it:
- left (for Node 'A' it is equal to 1)
- right (for Node 'A' it is equal to 18)
- depth (for Node 'A' it is equal to 1)
The 2 fundamental questions that pop into mind are:
- how did we come up with these numbers?
- depth should be pretty self-explanatory. It is the current depth of the Tree. Assuming that the Root Node has depth with value equal to 1, its Children will have depth equal to 2 and their Children will have depth equal to 3.
- left and right are more tricky, but this short animation should help. The numbers are 'wrapping' the entire tree starting from first Root's left side and ending on the last Root's right side.
- how do these numbers help us with reading this Tree in an optimized way?
- A very useful regularity can be observed - any Child node has the left value greater and the right value smaller than the corresponding values of their Parent
- For Example all Children of Node C (regardless of depth) have left value greater than 8 and right value smaller than 17
- This can be easily translated to an SQL clause that will fetch all Children of Node C (again, regardless of depth) in one go:
select * from tree_table where tree_left >= 8 and tree_right <= 17
- Assuming that the Table is properly indexed, the above statement will have O(log2(n)) complexity, which is orders of magnitude better than a traditional, recursive approach.
- Additionally, Nested Set is a sorted structure that maintains fixed order of the nodes, so you can order the result by the ascending left value, getting a pre-sorted result:
select * from tree_table where tree_left >= 8 and tree_right <= 17 order by tree_left asc
The relations between left, right and depth columns can be used in many interesting ways that are covered in more detail in the NestedJ's Readme file. The important thing is that once you see the regularity and pattern of numbering the Nodes, you can perform all sorts of optimized and fast read operations on your Tree.
Of course, the penalty of using Nested Set Model will be an increased complexity of modifying the Tree structure. Fortunately NestedJ has been written in a way that utilizes the full SIMD (single instruction - multiple data) power of SQL, so every Tree modification will execute the same, small number of SQL queries, regardless of the Nodes count.
It also uses the traditional parent_id column to make sure, that the Nested Set Model can be rebuilt from ground up (it has a rebuild feature implemented) in case of any data corruption (resulting from a manual SQL DML execution for example).
Conclusion
As you can see, storing a read-optimized Tree structure inside a Database Table is a non-trivial thing. It's always good to know all the options and consequences behind using them. For some this may seem like an overkill or too much complexity. For others this may turn out to be a viable solution that will solve their performance problems with repeated reading of nested structures from the Database. Hope that, regardless of which group you represent, you have at least found this article informative. Thanks!
Gosh, your awesome, hope we get to describe to your news letter soon.
ReplyDelete