How to recursively query in django efficiently?

Question

I have a model, which looks like:

class StaffMember(models.Model):

    id = models.OneToOneField(to=User, unique=True, primary_key=True, related_name='staff_member')
    supervisor = models.ForeignKey(to='self', null=True, blank=True, related_name='team_members')

My current hierarchy of team is designed in such a way that there is let's say an Admin (who is at the top most point of hierarchy). Now, let's say 3 people (A, B, C) report to Admin and each one of A, B and C have their own team reporting to them and so on.

I want to find all the team members (boiling down to the bottom most level of hierarchy), for any employee. My current method to get all the team members of a person is like:

def get_team(self):
    team = [self]
    for c in self.team_members.all():
        team += list(c.get_team())
        if len(team) > 2000:
            break
    return team

I get the team members of a member by:

member = StaffMember.objects.get(pk=72)
team = member.get_team()

But obviously, this leads to a lot of db calls and my API eventually times out. What could be more efficient way to fetch all the members of a team?

Have you tried using the _set method on your foreign key? I've never done it on a recursive model so don't know what the output might look like. You might also try .select_related() and see what you end up with. I think that will give you the necessary output but how efficient is I'm not sure. — Keith Bailey, Sep 15 '16 at 13:23
You should use an efficient way of storing/querying this data, such as https://github.com/django-mptt/django-mptt — Daniel Roseman, Sep 15 '16 at 13:23

score 29 · Answer 1 · answered Oct 08 '16 at 15:09

If you're using a database that supports recursive common table expressions (e.g. PostgreSQL), this is precisely the use-case.

team = StaffMember.objects.raw('''
    WITH RECURSIVE team(id, supervisor) AS (
          SELECT id, supervisor 
          FROM staff_member
          WHERE id = 42
        UNION ALL
          SELECT sm.id, sm.supervisor
          FROM staff_member AS sm, team AS t
          WHERE sm.id = t.supervisor
        )
    SELECT * FROM team
''')

References: Raw SQL queries in Django
Recursive Common Table Expressions in PostgreSQL

score 3 · Answer 2 · answered Oct 08 '16 at 13:19

I found a solution to the problem. The recursive solution takes the node, goes to it's first child and goes deep down till bottom of the hierarchy. Then comes back up again to the second child (if exists), and then again goes down till the bottom. In short, it explores all the nodes one by one and appends all the members in an array. The solution I came up with, fetches the members layer-wise.

member = StaffMember.objects.get(id__id=user_id)

new_list = [member]

new_list = get_final_team(new_list)

def get_final_team(qs):
    team = []
    staffmembers = StaffMember.objects.filter(supervisor__in=qs)

    team += staffmembers 
    if staffmembers:
        interim_team_qs = get_final_team(staffmembers)
        for qs in interim_team_qs:
            team.append(qs)
    else:
        team = [qs]

    return team

The number of db calls this method entails is the number of layers (of hierarchy) that are present beneath the member whose team we want to find out.

You could have let the DB do all the work by writing a simple recursive query as shown by Andrea's answer. In your case, you're issuing multiple queries and appending their results together -- not bad, but why make it so brittle when there's a pure DB-based solution? :-) — ankush981, Sep 20 '21 at 01:41

How to recursively query in django efficiently?

2 Answers2

Linked