эффективная функция для получения набора запросов предков набора запросов mptt

Есть ли у кого-нибудь эффективный алгоритм для получения всех предков набора запросов mptt? Лучшее, что я мог придумать, это что-то вроде этого:

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

У этого подхода есть две проблемы:

  1. Не работает, если есть ветки, которые не расположены рядом (т.е. на самом деле не работает).
  2. Это очень неэффективно, потому что в конечном запросе у него есть number_of_trees*number_of_levels предложений, которые могут очень быстро стать очень большими.

Я открыт для кеширования предков где-нибудь еще, но я не могу придумать способ сделать это эффективно. Я подумал о том, чтобы добавить поле со списком идентификаторов предков, разделенных запятыми, а затем сделать GROUP_CONCAT (я в MySQL) внутри дополнительного, но я думаю, что это может стать огромным / медленным.


python django hierarchical-data django-mptt mptt
person Bacon    schedule 24.06.2011    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Как насчет:

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

Это все еще предложения len (queryset). Вы могли бы немного уменьшить количество предложений, выполнив предпроцессный проход, который удаляет объекты, которые являются предками других объектов в наборе запросов, например:

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)

Хотя приведенный выше фрагмент является только примером, вы, вероятно, захотите использовать BST, если ваш набор запросов содержит значительное количество объектов.

Однако вам нужно будет проверить, приводит ли это к увеличению скорости по сравнению с большим запросом к БД.

person Michał Modzelewski    schedule 30.06.2011
comment
Проблема с этим подходом заключается в том, что необходимо сделать запрос для каждого объекта. obj.get_ancestors() выполняет запрос, не так ли? Таким образом, вы получите запрос len (qs) + 1 без оптимизации. - person Bacon; 04.07.2011
comment
@bacon нет, obj.get_ancestors () возвращает объект QuerySet, который лениво вычисляется. QuerySets объединяются вместе в цикле - в этом случае предложения where будут объединены по ИЛИ - а затем выполняются только позже, когда вы пытаетесь получить доступ к значениям. Будет выполнено только два запроса: один для исходного QuerySet, а второй - для получения всех предков. - person Michał Modzelewski; 04.07.2011
comment
Ааа - извините, хороший звонок. Значит, ваш будет примерно таким же, как у @ Cesar? - person Bacon; 05.07.2011
comment
Однако вы можете исключить этот лишний запрос с помощью .select_related. - person Bacon; 05.07.2011
comment
Я никогда не изучал, как django обрабатывает select_related в модели, связанной с самим собой полем ForeignKey. Это вполне может вызвать бесконечный цикл, если не используется ограничение глубины. Но в данном случае это не нужно. node.parent_id эквивалентен node.parent.pk без дополнительного запроса, как описано в django docs. Запрос с select_related, скорее всего, вернет больше столбцов, поэтому он будет менее эффективным. - person Michał Modzelewski; 05.07.2011

arrow_upward
6
arrow_downward

Однажды мне пришлось написать подобный алгоритм. У меня было представление, отображающее дерево MPTT, это было очень большое дерево, поэтому я не мог загрузить все его данные в шаблон HTML. Поэтому я отображал только корневые узлы в начальной загрузке и использовал Ajax для загрузки других узлов.

Это работало хорошо, пока мой начальник не попросил меня реализовать опцию «поиска». Поиск должен был просмотреть все узлы и взорвать дерево, если оно обнаружило совпадение. Мне потребовалось время, чтобы понять это, но я наконец понял. Вот решение, которое придумал:

from django.db.models import Q

def get_parents(self, qs):
    tree_list = {}
    query = Q()
    for node in qs:
        if node.tree_id not in tree_list:
            tree_list[node.tree_id] = []

        parent =  node.parent.pk if node.parent is not None else None,

        if parent not in tree_list[node.tree_id]:
            tree_list[node.tree_id].append(parent)

            query |= Q(lft__lt=node.lft, rght__gt=node.rght, tree_id=node.tree_id)

    return YourModel.objects.filter(query)

Для выполнения требуется только два запроса: начальный qs, переданный в качестве аргумента, и последний набор запросов, возвращаемый функцией. tree_list - это словарь, в котором хранятся узлы, которые уже были добавлены в набор запросов, это оптимизация, и для работы алгоритма нет необходимости. Но поскольку я работал с относительно большим деревом, мне пришлось включить его.

Думаю, вы могли бы превратить этот метод в менеджер и сделать его более универсальным, т.е. заставить его работать для любой модели MPTT, а не только YourModel

person Cesar Canassa    schedule 03.07.2011
comment
Очень умно - я закончил тем, что добавил в свою модель mptt текстовое поле под названием ancestor_ids, в котором есть список идентификаторов, разделенных запятыми - тогда это просто вопрос: queryset_ancestor_ids = set([]); for a in queryset.values_list('ancestor_ids', flat=True): if a: queryset_ancestor_ids.update(a.split(",")); return SegmentNode.objects.filter(pk__in=queryset_ancestor_ids) Я проведу сравнительный анализ, чтобы увидеть, что быстрее . - person Bacon; 04.07.2011