Django PostgreSQL – Efficiently fetch recursive category structure

Question

I have a model which looks like this:

class Category(models.Model):
    name = models.CharField(max_length=50)
    slug = models.SlugField()
    parent = models.ForeignKey(
        'categories.Category',
        null=True,
        blank=True,
        on_delete=models.CASCADE,
        related_name='categories'
    )

basically, in the parent field, it references itself. If a parent is set to None, it's the root category.

I use it to build a hierarchy of categories.

What would be the most efficient way to:

1. fetch all the objects through the hierarchy
2. display them in a template?

For some reason, select_related does not seem to lead to performance improvements here.

I also found this: How to recursively query in django efficiently?

But had a really hard time applying it to my example, because I still don't really understand what's going on. This was my result:

    WITH RECURSIVE hierarchy(slug, parent_id) AS (
        SELECT slug, parent_id 
        FROM categories_category
        WHERE parent_id = '18000'

        UNION ALL

        SELECT sm.slug, sm.parent_id
        FROM categories_category AS sm, hierarchy AS h
        WHERE sm.parent_id = h.slug
        )
    SELECT * FROM hierarchy

Would appreciate any help.

Thanks!

Answer 1

One possible solution can be using https://django-mptt.readthedocs.io/en/latest/overview.html#what-is-django-mptt

MPTT is a technique for storing hierarchical data in a database. The aim is to make retrieval operations very efficient. The trade-off for this efficiency is that performing inserts and moving items around the tree is more involved, as there’s some extra work required to keep the tree structure in a good state at all times.

from django.db import models
from mptt.models import MPTTModel, TreeForeignKey

class Category(MPTTModel):
    name = models.CharField(max_length=50)
    slug = models.SlugField()
    parent = TreeForeignKey(
        'self',
        null=True,
        blank=True,
        on_delete=models.CASCADE,
        related_name='children'
    )

    class MPTTMeta:
        order_insertion_by = ['name']

You can use the django-mptt template tag as this:

{% load mptt_tags %}
<ul>
    {% recursetree categories %}
        <li>
            {{ node.name }}
            {% if not node.is_leaf_node %}
                <ul class="children">
                    {{ children }}
                </ul>
            {% endif %}
        </li>
    {% endrecursetree %}
</ul>

There is a tutorial and more information in the library docs.

Answer 2

I had the same problem and ended up creating the following function that hits the database once, then sorts out the heirarchy and returns a dict:

def get_category_tree():
    categories = Category.objects.order_by('name')
    itemtree = {}
    # Add 'children' attribute to each category; populate dict
    for category in categories:
        category.children = {}
        itemtree[category.pk] = category
    # Add categories to 'children'
    for key,value in itemtree.items():
        if value.parent_id:
            itemtree[value.parent_id].children[key] = value
    # Return top-level items
    return {k:v for k,v in itemtree.items() if not v.parent_id}

Each value of the returned dict is a top-level Category object which has a children attribute.

You can render it in the template by looping through the dict values. The following example will handle three levels of heirarchy:

<ul>
{% for level1 in category_tree.values %}
    <li>
        {{ level1.name }}
        {% if level1.children %}
        <ul>
            {for level2 in level1.children.values %}
            <li>{{ level2.name }}
                {% if level2.children %}
                <ul>
                    {for level3 in level2.children.values %}
                    <li>{{ level3.name }}</li>
                    {% endfor %}
                </ul>
                {% endif %}
            </li>
            {% endfor %}
        </ul>
        {% endif %}
    </li>
{% endfor %}
</ul>

If you need to render many levels of the heirarchy, you could consider using template recursion. Have a read of the following question and answers to determine if that might be suitable: Represent a tree of objects in Django template