有效的功能来检索mptt查询的祖先的查询 [英] efficient function to retrieve a queryset of ancestors of an mptt queryset

问题描述

有没有人有一个有效的算法来检索mptt查询的所有祖先？到目前为止，我能想到的最好的是这样的：

  def qs_ancestors（queryset）：
 if isinstance（查询队列，EmptyQuerySet）：
返回查询
 queryset_aggs = queryset.values_list（'tree_id'，'level'）。注释（max_lft = Max（'lft'），min_rght = Min（'rght'）） 
 new_queryset = queryset.none（）
 for tree_id，level，max_lft，min_rght in queryset_aggs：
 ancestors = MyModel.objects.filter（
 tree_id = tree_id，
 level__lt = level，
 lft__lte = max_lft，
 rght__gte = min_rght，
）
 new_queryset =祖先| new_queryset 
 return new_queryset 
  

这种方法有两个问题：

1. 如果有不相邻的分支（即它没有真正工作），则失败


2. 它是非常低效的，因为它最终在最终查询中具有 number_of_trees * number_of_levels 子句，可以非常快速地获得非常大的

我可以在其他地方缓存祖先，但我不能想到有效的方法。我考虑用一个逗号分隔的祖先列表的列表添加一个字段，然后在一个额外的内部执行一个 GROUP_CONCAT （我在MySQL中），但我认为可能会变得很大/慢

解决方案

如何：

  def qs_ancestors（queryset）：
 if isinstance（queryset，EmptyQuerySet）：
 return queryset 
 new_queryset = queryset.none（）
对于obj在查询中：
 new_queryset = new_queryset | obj.get_ancestors（）
 return new_queryset 
  

它仍然是len（queryset）子句。您可以通过执行预处理通行来减少子句数量，从而删除作为查询器中其他对象的祖先的对象，如下所示：

  min_obj_set = [] 
对于obj在queryset.order_by（'tree_id'，'-level'）：
 for obj2 in min_obj_set：
 if obj.is_ancestor_of（obj2） ：
 break 
 else：
 min_obj_set.append（obj）
  

尽管上面的代码片段只是一个例子，但如果您的查询包含大量的对象，您可能需要使用BST。

您必须测试但是，如果这个增加速度与较大的数据库查询相关。

Does anybody have an efficient algorithm to retrieve all ancestors of an mptt queryset? The best I could think of so far is something like this:

def qs_ancestors(queryset):
    if isinstance(queryset, EmptyQuerySet):
        return queryset
    queryset_aggs = queryset.values_list('tree_id', 'level').annotate(max_lft=Max('lft'), min_rght=Min('rght'))
    new_queryset = queryset.none()
    for tree_id, level, max_lft, min_rght in queryset_aggs:
        ancestors = MyModel.objects.filter(
           tree_id=tree_id,
           level__lt=level, 
           lft__lte=max_lft,
           rght__gte=min_rght,
        )
        new_queryset = ancestors | new_queryset
    return new_queryset

There are two problems with this approach:

1. It fails if there are branches that aren't next to each other (ie it doesn't really work)
2. It is highly inefficient because it ends up have number_of_trees*number_of_levels clauses in the final query, which can get very large very fast

I am open to caching the ancestors somewhere else, but I cannot think of a way to do efficiently. I considered adding a field with a comma separated list of ancestor's ids and then doing a GROUP_CONCAT (I am in MySQL) inside an extra, but I think that could get huge/slow.

解决方案

How about:

def qs_ancestors(queryset):
    if isinstance(queryset, EmptyQuerySet):
        return queryset
    new_queryset = queryset.none()
    for obj in queryset:
        new_queryset = new_queryset | obj.get_ancestors()
return new_queryset

It's still len(queryset) clauses. You could potentially reduce the number of clauses a bit by doing a preprocess pass that removes objects that are ancestors of other objects in the queryset, something like:

min_obj_set = []
for obj in queryset.order_by('tree_id', '-level'):
    for obj2 in min_obj_set:
        if obj.is_ancestor_of(obj2):
            break
    else:
        min_obj_set.append(obj)

Although the above snippet is only an example, you'll probably want to use a BST if your querset contains a significant amount of objects.

You'll have to test if this yeilds an increase in speed vs. the larger DB query, though.

这篇关于有效的功能来检索mptt查询的祖先的查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！