django-mptt get_descendants for a list of nodes

Question

I am trying to get all descendants(include_self=True) not for one Node, but for a list (a QuerySet) of Nodes. This should be one SQL query.

Example (that actually is not working:)

some_nodes = Node.objects.filter( ...some_condition... ) 
some_nodes.get_descendants(include_self=True) #hopefully I would like 
to have all possible Nodes starting from every node of "some_nodes" 

The only idea I have right now is to iterate through some_nodes and run get_descendants() for every node - but this is terrible solution (plenty of SQL queries).

If there is no clean way to do it via Django ORM can you provide me a custom SQL to run instead? Here you can make assumption that I have a list of Node's pk.

EDIT: If that could help - all of my "some_nodes" are placed in the same parent directory and have the same "level" in the tree.

Iz

Answer 1

Great thanks to Craig de Stigter answered my question on django-mptt-dev group, in case anybody need it I am kindly reposting his solution from http://groups.google.com/group/django-mptt-dev/browse_thread/thread/637c8b2fe816304d

   from django.db.models import Q 
   import operator 
   def get_queryset_descendants(nodes, include_self=False): 
       if not nodes: 
           return Node.tree.none() 
       filters = [] 
       for n in nodes: 
           lft, rght = n.lft, n.rght 
           if include_self: 
               lft -=1 
               rght += 1 
           filters.append(Q(tree_id=n.tree_id, lft__gt=lft, rght__lt=rght)) 
       q = reduce(operator.or_, filters) 
       return Node.tree.filter(q) 

Example Node tree:

T1 
---T1.1 
---T1.2 
T2 
T3 
---T3.3 
------T3.3.3 

Example usage:

   >> some_nodes = [<Node: T1>, <Node: T2>, <Node: T3>]  # QureySet
   >> print get_queryset_descendants(some_nodes)
   [<Node: T1.1>, <Node: T1.2>, <Node: T3.3>, <Node: T3.3.3>] 
   >> print get_queryset_descendants(some_nodes, include_self=True)
   [<Node: T1>, <Node: T1.1>, <Node: T1.2>, <Node: T2>, <Node: T3>, <Node: T3.3>, <Node: T3.3.3>] 

Iz

This is great! I think it should Node.objects instead of Node.tree though – Repartition

Actually this is now built into the manager. See my alternate answer. – Repartition

Answer 2

Later versions of mptt already have this function built into the object manager. So the solution to this is just as follows:

Node.objects.get_queryset_descendants(my_queryset, include_self=False)

Repartition

Answer 3

Django mptt uses the modified pre-order tree traversal method as described in the MySQL Managing Hierarchical Data document.

It has the following query for returning all nodes in a tree below a certain node:

SELECT node.name
FROM nested_category AS node, nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
    AND parent.name = 'ELECTRONICS'
ORDER BY node.lft;

The secret is the parent.lft and parent.rgt numbers, all children will have a node.lft value between the two.

Obviously that example presupposes only one parent and that you need to use the parent name to find the parent. As you have the parent node data already you can do something like the following:

SELECT node.id
FROM node_table
WHERE node.lft BETWEEN parent[0].lft AND parent[0].rgt
    OR node.lft BETWEEN parent[1].lft AND parent[1].rgt

I'll leave it as an exercise for you as to how to generate a seperate BETWEEN clause for each parent node (hint, " AND ".join)

Alternatively you can use a the range generator on each parent to obtain all the values between each parent's lft and rgt values inclusive. That then lets you use a giant IN statement rather than lots of BETWEEN clauses.

Combine either of the above with a RawQueryset and you will get the models back.

Insular

Hmm, I've just realised I might use this myself for the related problem of extracting the parents for a large number of trees which is also massively slow at present due to a massive number of query calls that are generated – Insular

This is not very precise answer to what I asked: no tree_id in this statement! Therefore the idea is correct to select nodes between lft and right. – Iz