Django MPTT is no longer maintained - Migrate Existing Models to django-tree-queries

[lampwins]

Proposed Changes

The django-mptt project is no longer maintained so we need to find a new pattern for our tree use cases (Regions, rack groups, etc). I think we should revisit these use cases related to storage and access patterns to see if we really need the complexity of the MPTT structure, to begin with.

Justification

The django-mptt project is no longer maintained and as a core dependency, we need to find an alternative path.

TODO

Migrate

• RackGroup
• TenantGroup
• InventoryItem

Footnote: Region is an MPTT model but should be collapsed into Location sometime in this release and either this issue or that one can be the one to "turn the lights off" on MPTT (See: #2517)

[jathanism]

Sounds like we really need to review for what, exactly, we're using MPTT, and how we can centralize the pattern. We already attacked this to some degree w/ the network model overhaul to decouple form Postgres using the MPTT pattern, but we could go deeper and make it more efficient by establishing some kind of base "tree" model that uses an adjacency list (self-referential foreign key) to a parent, and then have all the tree methods (get_ancestors, get_children, root, parent, etc.).

[glennmatthews]

Requirements

The main requirements, as I understand them are:

1. Reasonably efficient iteration over ancestors (get_ancestors())
   • nautobot/dcim/templates/dcim/site.html and others - for region in object.region.get_ancestors etc.
2. Reasonably efficient iteration over children and/or descendants (get_children(), get_descendants())
   • nautobot.dcim.signals.handle_rackgroup_site_change - recursively setting the Site of all child RackGroups when a parent RackGroup changes Site
3. Reasonably efficient tree membership queries (closely related to the previous two requirements)
   • TreeNodeMultipleChoiceFilter - "get me all Sites that belong to Region ABC or any of its descendants"
   • ConfigContextModelQuerySet - "get me all ConfigContexts that are assigned to Region XYZ or any of its ancestors"
4. Reasonably efficient QuerySet annotation such as add_related_count
   • RegionListView - "How many Sites belong to each of the following Regions or any of their descendants"
   • RackGroupListView - "How many Racks belong to each of the following RackGroups or any of their descendants"
5. Reasonably efficient insertion of leaf nodes (adding a new Region, RackGroup, TenantGroup, etc.)
6. Reasonably efficient relocation of subtrees (changing the parent of a Region, etc.)
7. Reasonably efficient hard-coded ordering of sibling nodes (e.g. sibling Regions are always ordered by name), as opposed to un-ordered trees
8. Reasonably efficient tree traversal as QuerySet, respecting sibling ordering (e.g., depth-first ordering of Region QuerySet in order to render it into a hierarchical table)
9. Reasonably efficient handling of wide trees (hundreds or thousands of sibling nodes under a given parent)
10. Reasonably simple and foolproof API, easily usable with DRF, GraphQL, etc.
11. Support for UUID PKs
12. Compatibility with latest Django and Python versions / ongoing maintenance and support

Non-requirements

1. Efficient arbitrary tree traversal (e.g. breadth-first search)
2. Efficient user-selected ordering of sibling nodes (e.g. re-sorting or changing traversal order on the fly, as opposed to influencing order indirectly by changing the value of name or other field that is hard-coded for sorting) - see also Tree model tables should sort sensibly or not be sortable at all #1854
3. Efficient deeply nested trees
   • Perhaps for IPAddress/Prefix models, where an IPv6 address could theoretically have 127 ancestor Prefixes
   • For Region/Location/RackGroup/TenantGroup, a tree depth of less than 10 would be typical and even 20 would be a rare exception
4. Insertion of nodes at a specified position relative to their siblings (e.g. direct control over sibling order)

Comparison of approaches

Based on my limited research and understanding to date.

Requirement	django-mptt	django-treebeard	django-tree-queries	naive adjacency-list
1. efficient get_ancestors	✅	✅	✅	❌
2. efficient get_children, get_descendants	✅	✅	✅	❌
3. efficient tree membership queries	✅	✅	✅	❌
4. add_related_count	✅	❌	❌ feincms/django-tree-queries#21	❌
5. efficient leaf insertion	✅	✅	✅	✅
6. efficient subtree relocation	✅	✅	✅	✅
7. efficient sibling ordering	✅	✅	✅	❓
8. DFS queryset	✅	✅	✅	❌
9. wide trees	✅	✅	✅	✅
10. simple foolproof API	✅	❌	✅	✅
11. UUID PKs	✅	✅	✅	✅
12. compatibility, maintenance	❌	❓last release 2/2021	✅	✅

[jathanism]

Naive implementation thoughts

Items 1 -3

I believe that this is not as scary as it might sound at first. I know, I invoke this a lot and when it comes to comparing networks to other types of trees there are some built-in assumptions, but generally when it comes to MPTT you have the triangulation of left, right, and node.

Therefore all of the ancestors/descendants/membership queries shouldn't ever be all that expensive, because you will always have the 3-tuple (left, right, node) of the source object at query time.

Item 4

Seeing as this is just an optional annotation, this should also be pretty simple to do.

Item 8

This is going to vary based on how ordering is determined to be done. Obviously, again, with networks it's implied they will be numerical, but as you had hinted if it's done by name or slug, that is actually quite efficient, but not necessarily deterministic. But certainly could be done in respect to the 3-tuple for tree position.

[glennmatthews]

A feature we don't have or use at present is an efficient way to annotate a queryset with the tree path (ordered list of ancestors) of each node in the queryset (versus individually annotating each instance with something like get_ancestors()). To the best of my current understanding this would possibly be feasible with a materialized-path tree library such as one of the options provide by django-treebeard.

This would be useful for features like:

• Querying all parents of a nested object in GraphQL #1963
• Add information/filter about rack group in/with rack selector widget everywhere #629
• Expose IP Addresses within a prefix via GraphQL interface #842
• Tree model tables should sort sensibly or not be sortable at all #1854

Perhaps django-tree-queries could add something like https://stevestedman.com/2012/02/generating-a-tree-path-with-a-cte/ as well?

[glennmatthews]

Another useful feature I've identified a potential need/benefit for is the ability to select a subtree and/or set of nodes based on ancestor properties - e.g. "get me all of the Locations who have an ancestor of type Campus", "get me the subtrees of Locations descended from Location ABC or Location XYZ", "get me the subtrees of Locations descended from a Location that is linked to Site PDQ".

• django-mptt has this with queryset.get_ancestors() and queryset.get_descendants()
• django-treebeard does not appear to (Feature request: queryset.get_ancestors() django-treebeard/django-treebeard#98 appears to have been closed incorrectly)
• django-tree-queries does not appear to