Replace django-mptt

[jeremystretch]

Proposed Changes

Replace usage of django-mptt in NetBox with one of the alternatives listed below:

django-tree-queries

django-tree-queries employs recursive common table expressions (CTE). It was originally proposed in #6587.

django-treebeard

django-treebeard offers several tree implementations, one of which (nested sets) is roughly analogous to django-mptt's implementation.

PotsgreSQL ltree

PostgreSQL's ltree module offers another potential solution. It is employed by django-ltree, however that library appears to no longer be maintained.

Justification

django-mptt is no longer maintained. Additionally, this presents an opportunity to adopt a recursive nesting solution that may prove to be more performant and/or scalable than MPTT. This idea was originally raised in #11421.

[arthanson]

Looked more into replacing MPTT. The issue to cache the number of component types (#6347) I think might remove the need for add_related_count from MPTT which none of the other tree queries support and would be a bit of a pain to implement for CTE. If we don't need add_related_count, this makes it much easier to use any of the tree systems.

1. postgres ltree does need a postgres extension, which can be added via a migration, but it is an extension. If this is not acceptable then we can rule it out. django-ltree also looks like it isn't actively maintained, but is just a thin wrapper around the postgres stuff.
2. django-tree-queries and django-treebeard are both well maintained, treebeard has more stars but is much older.
3. leaning towards django-tree-queries as it is much lighter codebase and doesn't have three different tree structures to complicate the codebase. Otherwise the materialized path in treebeard looks like the best option.

Also, The author of django-tree-queries has a very good post at (https://406.ch/writing/django-tree-queries/) outlining the reasoning behind creating it and how it compares and the issues he had with the other tree libraries.

[DanSheps]

IMO, CTE seems to be the way to go. The lighter code being a big draw. It is somewhat newer but like mentioned is still actively maintained.

[arthanson]

Did a test implementation and now moving more towards treebeard. the issue with django-tree-queries came down to replacing add_related_count as everything else was very straight-forward.

add_related_count is basically doing a count on a subquery, the subquery being the tree of child elements. I.E. to get Regions (which is a tree) with a count of sites, you do an annotation of the count of the select of sites.regions filtering for the tree of the region.

The issue is the tree fields to filter on are not in the database as they are dynamically created by the CTE query, but django-tree-queries doesn't have any way to add these to a subquery. It could be done by either patching django-tree-queries to add this support, or by just doing RAW SQL to do the count in the subquery.

After discussion with Jeremy, would want to avoid the RAW sql if at all possible so looking at treebeard, since that has the tree fields in the database the implementation of add_related_count would be much more straightforward.

For treebeard looking at the materialized-path as that seems to have the best tradeoffs between the implementations.

[jeremystretch]

Blocked by #12759