search

feincms / django-tree-queries

Adjacency-list trees for Django using recursive common table expressions. Supports PostgreSQL, sqlite, MySQL and MariaDB.
https://django-tree-queries.readthedocs.io/
BSD 3-Clause "New" or "Revised" License
427 stars 27 forks source link

Add support for descending sibling ordering, multi-field sibling ordering, and related field sibling ordering #62

Closed rhomboss closed 7 months ago

rhomboss commented 7 months ago

Addresses #6.

Uses the ROW_NUMBER() window expression to map any ordering criteria onto an ascending set of ordinal integers which can be used to properly order a tree.

Parameters for this new ordering method are generated by get_sibling_order_params() which uses the base Django SQLCompiler to convert a dummy Django queryset object to SQL. This way we are able to rely on Django's backend to generate the extra SQL needed for more complex orderings like ordering by a related field.

This change will also make supporting additional forms of ordering simpler. For example, ordering based on annotations is not currently supported. However, it could be added by having TreeQuerySet override the base annotate() method so that it additionally stores its initial args and kwargs as instance variables which can later be submitted to the dummy queryset used to generate ordering parameters.

rhomboss commented 7 months ago

I'm sorry, but I don't have much insight into how the extra CTE will impact performance. My basic understanding is that you can run into problems when you have too many nested CTEs because it will start to confuse the SQL engine. But one nested CTE is probably not too many.

Additionally, depending on the underlying data having the extra CTE could be more efficient than the standalone. For example #50 , if we were to add a WHERE statement to the __rank_table CTE to filter based on user_id we could increase performance by reducing the overall number of nodes that need to be traversed when constructing the __tree.

matthiask commented 7 months ago

Re. filtering: Ah yes, this is an excellent point. I still have the hope that PostgreSQL will stop treating recursive CTEs as optimization fences at some point in the future. For the time being most trees I have are so small that it's not really a problem anyway.

Also, we could use a materialized view or something for the rank table and even the recursive table in the future if it's a problem. For now I'm going to merge this and upload a new release shortly. Thanks for your great work!