Django ORM Optimization Tips #4 recursive query

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)

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

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])

Result:

Query explanation

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