Creating efficient database queries for hierarchical models (django)

Question

Consider this (django) model:

class Source(models.Model):
   # Some other fields
   type = models.ForeignKey('Type')

class Type(models.Model):
    # Some other fields
    parent = models.ForeignKey('self')

This model has a foreign key to itself, thus creating a hierarchy.

Let's say we have the following hierarchy:

Website
    Blog
    News    
    Social Network
    Q&A
    Forum
Radio
    Government radio
    Pirate radio
    Commercial radio
    Internet radio

How do I efficiently query so that if I select Source by Type, I also retrieve Sources which have a Type that is a child of the given type?

I have tried traversing through the whole tree, but that isn't very efficient obviously.

Another option would be to use a ManyToManyField and automatically attach parent Types by overriding the save() method. For example, if 'blog' is selected, a record for 'website' is also created. But this seems overkill to me.

Answer 1

django-mptt or django-treebeard are great helpers for hierarchical data. They both add extra metadata to your model to allow efficient queries.

if you choose to use django-treebeard your model could look something like this:

from django.db import models
from treebeard.mp_tree import MP_Node

class Source(models.Model):
    # Some other fields
    type = models.ForeignKey('Type')

class Type(MP_Node):
    # Some other fields
    name = models.CharField(max_length=100)

    # parent gets added automatically by treebeard
    # parent = models.ForeignKey('self', blank=True, null=True)

and could be queried like this:

# get all Sources of Type type and descendants of type
type = Type.objects.get(name='Radio')
Source.objects.filter(type__in=type.get_descendants())

see https://django-treebeard.readthedocs.io/en/latest/api.html for more possible queries

Answer 2

Such a structure can easily be retrieved using a recursive common table expression.

An example is e.g. here: http://www.postgresql.org/docs/current/static/queries-with.html

Answer 3

How do I efficiently query so that if I select Source by Type, I also retrieve Sources which have a Type that is a child of the given type?

For the example given, it is fairly easy to setup a query because no recursive calls need to be made, and your "hierarchy" is only one level deep:

class Source(models.Model):
   # Some other fields
   type = models.ForeignKey('Type')

class Type(models.Model):
    # Some other fields
    name = models.CharField(max_length=100)
    parent = models.ForeignKey('self', blank=True, null=True)

#We want all sources under in the type = Radio tree
type = Type.objects.get(name='Radio')
qs = Source.objects.filter(type__parent=type)

#We want all sources that are `Forum` typed
type = Type.objects.get(name='Forum')
qs = Source.objects.filter(type=type)

This is assuming that Source is always related to a "child" type and not to the "parent."

If sources can also be related to the "parent" types, you can use Q for complex queries:

>>> from django.db.models import Q
>>> type = Type.objects.get(name='Radio')
>>> qs = Source.objects.filter(Q(type=type)|Q(type_parent=type))
>>> #if Radio type id = 2
>>> print qs.query
SELECT `app_source`.`id`, `app_source`.`type_id` FROM `app_source` INNER JOIN `app_type` ON  (`app_source`.`type_id` = `app_type`.`id`) WHERE (`app_source`.`type_id` = 2  OR `app_type`.`parent_id` = 2 )
>>> 

If you have a truly hierarchical trees in your tables, this method is much less usable, and you should seek out another solution.