django-tree-queries

CI Status

Query Django model trees using adjacency lists and recursive common table expressions. Supports PostgreSQL, sqlite3 (3.8.3 or higher) and MariaDB (10.2.2 or higher) and MySQL (8.0 or higher, if running without ONLY_FULL_GROUP_BY).

Supports Django 3.2 or better, Python 3.8 or better. See the GitHub actions build for more details.

Features and limitations

  • Supports only integer and UUID primary keys (for now).

  • Allows specifying ordering among siblings.

  • Uses the correct definition of depth, where root nodes have a depth of zero.

  • The parent foreign key must be named "parent" at the moment (but why would you want to name it differently?)

  • The fields added by the common table expression always are tree_depth, tree_path and tree_ordering. The names cannot be changed. tree_depth is an integer, tree_path an array of primary keys and tree_ordering an array of values used for ordering nodes within their siblings. Note that the contents of the tree_path and tree_ordering are subject to change. You shouldn’t rely on their contents.

  • Besides adding the fields mentioned above the package only adds queryset methods for ordering siblings and filtering ancestors and descendants. Other features may be useful, but will not be added to the package just because it’s possible to do so.

  • Little code, and relatively simple when compared to other tree management solutions for Django. No redundant values so the only way to end up with corrupt data is by introducing a loop in the tree structure (making it a graph). The TreeNode abstract model class has some protection against this.

  • Supports only trees with max. 50 levels on MySQL/MariaDB, since those databases do not support arrays and require us to provide a maximum length for the tree_path and tree_ordering upfront.

Here’s a blog post offering some additional insight (hopefully) into the reasons for django-tree-queries’ existence.

Usage

  • Install django-tree-queries using pip.

  • Extend tree_queries.models.TreeNode or build your own queryset and/or manager using tree_queries.query.TreeQuerySet. The TreeNode abstract model already contains a parent foreign key for your convenience and also uses model validation to protect against loops.

  • Call the with_tree_fields() queryset method if you require the additional fields respectively the CTE.

  • Call the order_siblings_by("field_name") queryset method if you want to order tree siblings by a specific model field. Note that Django’s standard order_by() method isn’t supported – nodes are returned according to the depth-first search algorithm.

  • Create a manager using TreeQuerySet.as_manager(with_tree_fields=True) if you want to add tree fields to queries by default.

  • Until documentation is more complete I’ll have to refer you to the test suite for additional instructions and usage examples, or check the recipes below.

Recipes

Basic models

The following two examples both extend the TreeNode which offers a few agreeable utilities and a model validation method that prevents loops in the tree structure. The common table expression could be hardened against such loops but this would involve a performance hit which we don’t want – this is a documented limitation (non-goal) of the library after all.

Basic tree node

from tree_queries.models import TreeNode

class Node(TreeNode):
    name = models.CharField(max_length=100)

Tree node with ordering among siblings

Nodes with the same parent may be ordered among themselves. The default is to order siblings by their primary key but that’s not always very useful.

from tree_queries.models import TreeNode

class Node(TreeNode):
    name = models.CharField(max_length=100)
    position = models.PositiveIntegerField(default=0)

    class Meta:
        ordering = ["position"]

Add custom methods to queryset

from tree_queries.models import TreeNode
from tree_queries.query import TreeQuerySet

class NodeQuerySet(TreeQuerySet):
    def active(self):
        return self.filter(is_active=True)

class Node(TreeNode):
    is_active = models.BooleanField(default=True)

    objects = NodeQuerySet.as_manager()

Querying the tree

All examples assume the Node class from above.

Basic usage

# Basic usage, disregards the tree structure completely.
nodes = Node.objects.all()

# Fetch nodes in depth-first search order. All nodes will have the
# tree_path, tree_ordering and tree_depth attributes.
nodes = Node.objects.with_tree_fields()

# Fetch any node.
node = Node.objects.order_by("?").first()

# Fetch direct children and include tree fields. (The parent ForeignKey
# specifies related_name="children")
children = node.children.with_tree_fields()

# Fetch all ancestors starting from the root.
ancestors = node.ancestors()

# Fetch all ancestors including self, starting from the root.
ancestors_including_self = node.ancestors(include_self=True)

# Fetch all ancestors starting with the node itself.
ancestry = node.ancestors(include_self=True).reverse()

# Fetch all descendants in depth-first search order, including self.
descendants = node.descendants(include_self=True)

# Temporarily override the ordering by siblings.
nodes = Node.objects.order_siblings_by("id")

Note that the tree queryset doesn’t support all types of queries Django supports. For example, updating all descendants directly isn’t supported. The reason for that is that the recursive CTE isn’t added to the UPDATE query correctly. Workarounds often include moving the tree query into a subquery:

# Doesn't work:
node.descendants().update(is_active=False)

# Use this workaround instead:
Node.objects.filter(pk__in=node.descendants()).update(is_active=False)

Filter by depth

If you only want nodes from the top two levels:

nodes = Node.objects.with_tree_fields().extra(
    where=["__tree.tree_depth <= %s"],
    params=[1],
)

Aggregating ancestor fields

It may be useful to aggregate fields from ancestor nodes, e.g. to collect parts of a path or something similar.

nodes = Node.objects.with_tree_fields().tree_fields(
    tree_names="name",
)

All nodes will now have a tree_names attribute containing a list of all ancestors’ names, including the node itself.

Form fields

django-tree-queries ships a model field and some form fields which augment the default foreign key field and the choice fields with a version where the tree structure is visualized using dashes etc. Those fields are tree_queries.fields.TreeNodeForeignKey, tree_queries.forms.TreeNodeChoiceField, tree_queries.forms.TreeNodeMultipleChoiceField.

Templates

django-tree-queries doesn’t include any utilities to help rendering trees in templates at this time. django-tree-query-template exists and includes a version of the django-mptt tree_info filter. Feel free to check it out.

Change log

Next version

  • Added Django 5.1 to the testsuite.

  • Added tests showing that .descendants().update(...) doesn’t work, but .filter(pk__in=....descendants()).update(...) does.

0.19 (2024-04-25)

  • Reimplemented the rank table construction using a real queryset; this enables support for pre-filtering the tree queryset using .tree_filter() and .tree_exclude(). Thanks rhomboss!

  • Added a .tree_fields() method to allow adding additional columns to the tree queryset, allowing collecting ancestors fields directly when running the initial query. For example, .tree_fields(tree_names="name") will collect all name fields in a tree_fields array on the model instances. For now the code only supports string fields and integer fields.

0.18 (2024-04-03)

  • Fixed broken SQL which was generated when using a tree query with EXISTS() subqueries.

0.17 (2024-03-26)

  • Preserved the tree ordering even when using .values() or .values_list(). Thanks Glenn Matthews!

  • Added support for descending sibling ordering, multi-field sibling ordering, and related field sibling ordering. Thanks rhomboss!

0.16 (2023-11-29)

  • Added Python 3.12, Django 5.0.

  • Fixed a problem where .values() would return an incorrect mapping. Thanks Glenn Matthews!

  • Started running tests periodically to catch bugs earlier.

0.15 (2023-06-19)

  • Switched to ruff and hatchling.

  • Dropped Django 4.0.

  • Added Python 3.11.

  • Added a .without_tree_fields() method which calls .with_tree_fields(False) in a way which doesn’t trigger the flake8 boolean trap linter.

0.14 (2023-01-30)

  • Changed the behavior around sibling ordering to warn if using Meta.ordering where ordering contains more than one field.

  • Added Django 4.2a1 to the CI.

  • Django 5.0 will require Python 3.10 or better, pruned the CI jobs list.

  • Added quoting to the field name for the ordering between siblings so that fields named order can be used. Thanks Tao Bojlén!

  • Narrowed exception catching when determining whether the ordering field is an integer field or not. Thanks Tao Bojlén.

0.13 (2022-12-08)

  • Made it possible to use tree queries with multiple table inheritance. Thanks Olivier Dalang for the testcases and the initial implementation!

0.12 (2022-11-30)

  • Removed compatibility with Django < 3.2, Python < 3.8.

  • Added Django 4.1 to the CI.

  • Fixed .with_tree_fields().explain() on some databases. Thanks Bryan Culver!

0.11 (2022-06-10)

  • Fixed a crash when running .with_tree_fields().distinct().count() by 1. avoiding to select tree fields in distinct subqueries and 2. trusting the testsuite.

0.10 (2022-06-07)

  • Fixed ordering by string fields to actually work correctly in the presence of values of varying length.

0.9 (2022-04-01)

  • Added TreeQuerySet.order_siblings_by which allows specifying an ordering for siblings per-query.

0.8 (2022-03-09)

  • Added pre-commit configuration to automatically remove some old-ish code patterns.

  • Fixed a compatibility problem with the upcoming Django 4.1.

0.7 (2021-10-31)

  • Added a test with a tree node having a UUID as its primary key.

0.6 (2021-07-21)

  • Fixed TreeQuerySet.ancestors to support primary keys not named id.

  • Changed the tree compiler to only post-process its own database results.

  • Added **kwargs-passing to TreeQuery.get_compiler for compatibility with Django 4.0.

0.5 (2021-05-12)

  • Added support for adding tree fields to queries by default. Create a manager using TreeQuerySet.as_manager(with_tree_fields=True).

  • Ensured the availability of the with_tree_fields configuration also on subclassed managers, e.g. those used for traversing reverse relations.

  • Dropped compatibility with Django 1.8 to avoid adding workarounds to the testsuite.

  • Made it possible to use django-tree-queries in more situations involving JOINs. Thanks Safa Alfulaij for the contribution!

0.4 (2020-09-13)

  • Fixed a grave bug where a position of 110 would be sorted before 20 for obvious reasons.

  • Added a custom TreeNodeForeignKey.deconstruct method to avoid migrations because of changing field types.

  • Removed one case of unnecessary fumbling in Query’s internals making things needlessly harder than they need to be. Made django-tree-queries compatible with Django’s master branch.

  • Removed Python 3.4 from the Travis CI job list.

  • Dropped the conversion of primary keys to text on PostgreSQL. It’s a documented constraint that django-tree-queries only supports integer primary keys, therefore the conversion wasn’t necessary at all.

  • Reverted to using integer arrays on PostgreSQL for ordering if possible instead of always converting everything to padded strings.

0.3 (2018-11-15)

  • Added a label_from_instance override to the form fields.

  • Removed the limitation that nodes can only be ordered using an integer field within their siblings.

  • Changed the representation of tree_path and tree_ordering used on MySQL/MariaDB and sqlite3. Also made it clear that the representation isn’t part of the public interface of this package.

0.2 (2018-10-04)

  • Added an optional argument to TreeQuerySet.with_tree_fields() to allow reverting to a standard queryset (without tree fields).

  • Added tree_queries.fields.TreeNodeForeignKey, tree_queries.forms.TreeNodeChoiceField and tree_queries.forms.TreeNodeMultipleChoiceField with node depth visualization.

  • Dropped Python 3.4 from the CI.

0.1 (2018-07-30)

  • Initial release!