Recently we had a report from a customer about very slow loading time of his store. We investigated the problem and found that it is caused by GetChildCategoryIds method, which could be found at CatalogController. It is a recursive method that builds List of ids for all child categories of a certain parent category.
In the case of our customer he had more that 1300 categories and some of his parent categories had more than 380 child categories distributed in multiple levels. Due to the recursive nature of the GetChildCategoryIds method and the multiple levels of categories, the heavy GetAllCategoriesByParentCategoryId (used by GetChildCategoryIds) is called tremendous amount of times, also the calls to the database were exponential. Although both methods have caching you could figure that the initial load was taking too long.
We have solved this problem for our products using only one call to the database and the Tree data structure for performance and we would like to share it with the nopCommerce community.
The main idea is to load all categories from the database in the memory (caching them) as a key-value pair (child, parent) and build a tree of them.
The tree is nothing special, just a regular one with Add, Search, GetAllSubNodes methods.
Search method takes a value and uses standard BFS (Breadth first search) to find it.
We decided to use iteration instead of recursion, so we used a regular queue.
procedure Search(G,v) is
let Q be a queue
Q.enqueue(v)
label v as discovered
while Q is not empty
w ← Q.dequeue()
if w is labeled as discovered
return w
else
for all childNodes of w do
Q.enqueue(childNode)
Add method takes two parameters - childCategory and parentCategory. The method considers three cases:
1. When the parent category is already in the tree and the child category is not:
In this case we just create a new child node and attach it to the parent node.
let newChildNode be a TreeNode
newChildNode.ParentNode = parentNode
push newChildNode into parentNode.ChildNodes
2. When the parent category is not in the tree but the child category is:
In this case we create a new parent node for our child node and attach it to the current parent of our child node, then we attach the child node to the new parent node.
let newParentNode be a TreeNode
newParentNode.ParentNode = parentNode of childNode
childNode.ParentNode = newParentNode
push newChildNode into parentNode.ChildNodes
3. When neither one are in the tree
In this case we create two new tree nodes (for parent and for child category), attach the nodes to each other and attach the parent node to the tree root.
let newParentNode be a TreeNode
let newChildNode be a TreeNode
newChildNode.ParentNode = newParentNode
push newChildNode into newParentNode
push newParentNode into root.ChildNodes
GetAllSubNodes method takes a value to search for, finds the TreeNode with this value and returns List of all his child tree nodes (something like a subtree, but instead in tree in list). The method uses DFS (Depth First Search) to traverse the nodes from the node with the provided value and build the list.
The pseudocode for the DFS is pretty much the same as the BFS but instead of queue a stack is used.
Then we use the Tree in a helper method that accepts the parent categoryId and returns all of its child categories using the GetAllSubNodes method.
We use this helper method to replace the GetChildCategoryIds method in all our products.
Also, we replace it in the entire nopCommerce and tested this with our clients database. From 40 seconds the initial load dropped to 4 seconds.
If Andrei decides it is good idea we are ready to contribute this to nopCommerce and make it native to the platform. We are using this in production for several months and we didn't have any problems.
Regards,
Nop-Templates Team
