DEV Community

loading...
Cover image for Django ORM Optimization Tips #4 recursive query

Django ORM Optimization Tips #4 recursive query

shawara profile image Mahmoud Shawara Updated on ・2 min read

Recursive quires is frequently needed when you have a self referencing table

Our example today will be items and categories user wants to get item details with item category path to root category.

Root-Category > Category > Sub-Category > leaf-Category

#models.py
class Category(models.Model):
    name = models.CharField(max_length=127)
    parent = models.ForeignKey('self', null=True)

Enter fullscreen mode Exit fullscreen mode

data example

We need to implement query that get the category path to root:

The naive solution:

def path_to_root_category(category_id):
    if category_id is None:
        return []
    category = Category.objects.get(pk=category_id)
    result = path_to_root_category(category.parent_id)
    result.append(category)
    return result
Enter fullscreen mode Exit fullscreen mode

path_to_root_category(4)
[<Category: root>, <Category: category>, <Category: sub-category>, <Category: leaf-category>]

The cost of this function is 4 queries (number of nodes in the path)
If we have a path of large number of nodes this will be so bad.

The optimized solution:

def path_to_root_category(category_id):
    query = '''
    WITH RECURSIVE parents AS (
        SELECT category.*, 0 AS relative_depth
        FROM category
        WHERE id = %s

        UNION ALL

        SELECT category.*, parents.relative_depth - 1
        FROM category,parents
        WHERE category.id = parents.parent_id
    )
    SELECT id, name, parent_id, relative_depth
    FROM parents
    ORDER BY relative_depth;
    '''
    return Category.objects.raw(query, [category_id])
Enter fullscreen mode Exit fullscreen mode

Result:
Alt Text

Query explanation
SQL query

  1. First find the target category element and make it the first element of the parents set

  2. Follow parent of all categories in parents set and add them to the same set

  3. Finally select all categories in the parents set ordered by their depth

Discussion (0)

Forem Open with the Forem app