none
Рекурсия в SQL RRS feed

  • Вопрос

  • Есть таблица с полями id и parent_id, записи связаны между собой очередью как родитель-потомок.

    Подскажите, пожалуйста, как зная id записи (причем это id может быть любого потомка) получить полное дерево своего родства, начиная от родителя и до последнего потомка?

    10 октября 2013 г. 14:15

Ответы

  • Решил проблему сам, возможно кому-то пригодится (где id => DocID, parent_id => ParentDocID).

    WITH ParSel(DocID, ParentDocID, StartDate, ChangeDate) AS
    (
     select DocID, ParentDocID, StartDate, ChangeDate 
      From documents where DocID = @Docid 
     union all
     select b.DocID, b.ParentDocID, b.StartDate, b.ChangeDate 
         From ParSel a, documents b 
                where a.ParentDocID = b.DocID
    ), ParSel1(DocID, ParentDocID, StartDate, ChangeDate) AS
    (
     select DocID, ParentDocID, StartDate, ChangeDate 
      From documents where DocID = @Docid 
     union all
     select b.DocID, b.ParentDocID, b.StartDate, b.ChangeDate 
         From ParSel1 a, documents b
                where b.ParentDocID = a.DocID
               
    )select DocID, ParentDocID, StartDate, ChangeDate from ParSel 
    union  
    select DocID, ParentDocID, StartDate, ChangeDate from ParSel1
    Код по любому @Docid в цепочке находит всю цепочку целиком


    10 октября 2013 г. 17:59

Все ответы

  • Решил проблему сам, возможно кому-то пригодится (где id => DocID, parent_id => ParentDocID).

    WITH ParSel(DocID, ParentDocID, StartDate, ChangeDate) AS
    (
     select DocID, ParentDocID, StartDate, ChangeDate 
      From documents where DocID = @Docid 
     union all
     select b.DocID, b.ParentDocID, b.StartDate, b.ChangeDate 
         From ParSel a, documents b 
                where a.ParentDocID = b.DocID
    ), ParSel1(DocID, ParentDocID, StartDate, ChangeDate) AS
    (
     select DocID, ParentDocID, StartDate, ChangeDate 
      From documents where DocID = @Docid 
     union all
     select b.DocID, b.ParentDocID, b.StartDate, b.ChangeDate 
         From ParSel1 a, documents b
                where b.ParentDocID = a.DocID
               
    )select DocID, ParentDocID, StartDate, ChangeDate from ParSel 
    union  
    select DocID, ParentDocID, StartDate, ChangeDate from ParSel1
    Код по любому @Docid в цепочке находит всю цепочку целиком


    10 октября 2013 г. 17:59
  • Отлично, что вы решили вопрос самостоятельно.

    Теперь уточнения: у вас просто список, а не дерево? Если список, то всё практически ок, а если дерево, то написано неправильно.
    UNION в конце вы впихнули ради фильтрации удвоения стартового элемента? Подобные фокусы часто катастрофически гробят производительность. В рамках учебной задачки оно покатит, но при использовании этого куска кода внутри больших запросов есть шансы получить проблем. 

    Категорически неправильным является запихивание в union (group by, distinct) того, что можно туда не засовывать. Случается, что это бывает эффективно, но, как правило, всё ровно наоборот. И это ОЧЕНЬ распространённая ошибка. У вас есть уникальный ID документа. Этого достаточно для фильтрации, раз уж вы её хотите. Т.е. вы должны переписать ParSel блоки на возвращение только двух первых колонок, в union оставить только DocID, а прочие поля получать джойном итогового результата на documents по DocID.


    • Изменено Roman Sergeev 11 октября 2013 г. 14:47
    11 октября 2013 г. 6:54
  • Да у меня просто список. При этом ParSel - получает список всех документов после переданного @Docid, а ParSel1 - все документы до @Docid. Последний union просто объединяет эти два списка в один, чтобы получить все документы. Следовательно если надо только часть (до или после) заявленного @Docid, то можно одну из рекурсий убрать. На счет лишних полей в ParSel, конечно согласен их можно убрать и получить все на последнем шаге (за указание на это спасибо).

    понимаю, что union не очень изящное решение, однако пока проблем с производительностью не замечено, да и вызываться этот код будет крайне редко.

    Если Вы предложите более лаконичное решение, то буду признателен.

    11 октября 2013 г. 8:55
  • Лаконичность не должна являться самоцелью. :) 

    11 октября 2013 г. 15:09
  • При большом объёме данных, и высокой динамике обращений Ваша конструкция не очень оптимальна.

    Для таких задач(прямой и обратной рекурсии) я использую функции вида:

    create function ft_tree(@id int)
    returns @tab table (id int, parent_id int)
    as
    begin
    	insert into @tab select id,parent_id from tabname
    	while (select count(*) from tablename where parent_id in (select id from tablename) and id not in (select id from tablename) )>0
    	  insert into @tab select id,parent_id from tabname where parent_id in (select id from tablename) and id not in (select id from tablename)
      return
    end
    Клиент получает результирующую выборку максимально быстро. Функция падает в кеш. 

    • Предложено в качестве ответа Surushkin Ilya 26 октября 2013 г. 17:00
    19 октября 2013 г. 17:18
  • А как обстоят дела с индексом по результирующей таблице? если потом делать выборки по id?

    21 октября 2013 г. 17:41
  • Легко, табличные переменные имеют все свойства таблицы, кроме того переменная приоритетно в памяти.

    Производительность максимальна.  У меня реально работает едино-моментно 100к-200к записей и ~100 пользователей , тесты ставил 10000к, но проблема есть когда физической памяти сервака(32гб) не хватает но добился этого после 1500 потоков...

    21 октября 2013 г. 19:56
  • Вы передаете в функцию @id, а выборку никак не ограничиваете...

    22 октября 2013 г. 13:08
  • Так,  я Вам просто пример привёл (проиллюстрировать подход).

    Можно ограничения вводить внутри функции или снаружи всё зависит от специфики задачи.

    Скорость работы Вы можете проверить на своих данных... Важно,  что бы в базовой таблице существовали индексы по id и parent_id всё.

    22 октября 2013 г. 13:21