2

Есть таблица с деревом (id, parent)

Нужно написать запрос, который вернет для каждого узла все дочерние узлы и дочерние узлы всех дочерних узлов (рекурсивно), а так же столбец с уровнем в дереве текущего узла и столбец с уровнем в дереве дочернего узла. Я написал запрос, но он виснет. Конкретно виснет (выполняется очень долго и я не могу его отменить). При этом ошибки с достижением уровня рекурсии 100 не вылетает. То есть, я так понял, рекурсия не уходит в глубину, но выполнение одной итерации уходит в бесконечность.

WITH 
Tree(Id,Parent,Level) AS (
  SELECT
    Node_Id
    ,0
    ,0
  FROM CatalogOKPD WHERE Node_Parent_Id = 0
  UNION ALL
  SELECT
    okpd.Node_Id
    ,okpd.Node_Parent_Id
    ,t.Level+1
  FROM CatalogOKPD okpd
  JOIN Tree t ON t.Id = okpd.Node_Parent_Id)
,FullTree(Id,Child,Level,ChildLevel) AS (
  SELECT 
    t1.Id
    ,t2.Id
    ,t1.Level
    ,t2.Level
  FROM Tree t1
  JOIN Tree t2 ON t1.Id=t2.Parent
  UNION ALL
  SELECT
    ft.Id
    ,t.Id
    ,ft.Level
    ,t.Level
  FROM Tree t
  JOIN FullTree ft ON t.Parent = ft.Child
)
SELECT * FROM FullTree

В итоге из таблицы с такими данными

id  parent
--- -------
1   0
2   1
3   1
4   0
5   4
6   4
7   6
8   7

я хочу получить ответ

id          child       level       childlevel
----------- ----------- ----------- -----------
1           2           0           1
1           3           0           1
4           5           0           1
4           6           0           1
4           7           0           2
4           8           0           3
6           7           1           2
6           8           1           3
7           8           2           3

UPD:

поправил запрос, проверил на малом количестве данных, все норм. А вот на реальной таблице с 70000 записями запрос выполняется нереально долго. Так что его нужно оптимизировать (или переписать иначе)

6
  • Я не понял как по входным данным добраться до записей с id 6, 7, 8 потому как от заданного вами корня (с parent=0) нет никакого пути до них. И не ясно что такое childLevel, обычно уровень дочернего элемента на 1 больше, чем у родителя.
    – Mike
    27 окт 2016 в 9:17
  • @Mike, вы невнимательно прочитали. "все дочерние узлы и дочерние узлы всех дочерних узлов (рекурсивно)" означает, что для узла с id = 4 нужно вернуть не только узлы 5 и 6, но и их дочерние узлы и узлы их дочерних узлов, короче все поддерево
    – iRumba
    27 окт 2016 в 9:23
  • Вот, теперь с записью 4/6 в входных данных стало лучше
    – Mike
    27 окт 2016 в 9:26
  • @Mike, замечание было отчасти в тему. Я в начальном наборе данных забыл указать узел 6 / 4. Исправил
    – iRumba
    27 окт 2016 в 9:26
  • @Mike, смотрите обновление
    – iRumba
    27 окт 2016 в 9:57

2 ответа 2

2
WITH 
Nums(N) AS (select 0 union select 1),
Tree(id,Child,Level,ChildLevel,old_n) AS (
  SELECT Node_Id, Node_Id, 0, 0, 1
    FROM CatalogOKPD WHERE Node_Parent_Id = 0
 UNION ALL
  SELECT case when N=0 then t.id else okpd.Node_Id end,
         okpd.Node_Id, t.Level+N,
         t.ChildLevel+1, N
    FROM Tree t, CatalogOKPD okpd, Nums N
   WHERE t.Child = okpd.Node_Parent_Id and (old_n=1 or N=0)
)
  select id, Child, Level, ChildLevel
    from Tree
   where old_n=0
   order by Level, id, ChildLevel

Идея в том, что на каждом уровне рекурсии мы раздваиваем пришедшую на вход запись, одна из них идет дальше от того же корня, что пришедшая. А вторая запись становится новым корнем. Раздваиваются только те записи, которые на предыдущем уровне стали корневыми (old_n=1).

UPD Как работает ...

Для примера возьмем только одну ветку данных, от записи 4/0:

id=4, child=4, old_n=0, N=1 Затравочная запись выбрана первой частью
                            она поступает на вход рекурсивной части как Tree ...
                            Тут по parent=child к ней приклеены 2 записи (5, 6)
                            old_n на входе равен 1 - значит по условию (old_n=1 or N=0)
                            для каждой из них будут взяты 2 записи Nums, что даст 4 записи:
id=4, child=5, old_n=0, N=0 В old_n перешел номер 0 из Nums
id=5, child=5, old_n=1, N=1 Т.к. N=1 в качестве id был взят child, что дало новый корень (5)
id=4, child=6, old_n=0, N=0
id=6, child=6, old_n=1, N=1 тут все аналогично
                            На следующем уровне рекурсии для записи 5 потомков нет, значит
                            она уже ничего не породит. Следим за 6
id=4, child=7, old_n=0, N=0 По условию (old_n=1 or N=0) взята только 1 запись из Nums N=0
                            child взят из следующей дочерней записи
id=6, child=7, old_n=1, N=0 т.к. old_n=1 то берется 2 записи Nums (0,1)
                            у данной N=0, поэтому корень сохранился id=4
id=7, child=7, old_n=1, N=1 N=1 поэтому корень 6 заменен на 7
                            И аналогично следующий уровень рекурсии
id=4, child=8, old_n=0, N=0
id=6, child=8, old_n=0, N=0
id=7, child=8, old_n=1, N=0
id=8, child=8, old_n=1, N=1 Затравка для следующего уровня, если бы он был

Итоговый запрос берет все записи с N=0 из примера выше, он в выборке находится в поле old_n. Записи с N=1 используются только внутри рекурсии для порождения новых ветвей дерева.

7
  • Опишите пожалуйста по шагам на основе предложенных в запросе данных, как это работает... а то у меня крыша едет от вашего запроса. Он работает, но я не пойму как! (
    – iRumba
    28 окт 2016 в 10:34
  • @iRumba Ok, чуть позже, довольно тяжело сформулировать ... себе вчера полчаса доказывал, что нет подводных камней, после того как заработало :)
    – Mike
    28 окт 2016 в 10:40
  • @iRumba В общем я написал как себя записи ведут, не знаю, прояснит это что то или еще более запутает ...
    – Mike
    28 окт 2016 в 12:05
  • Магия, как она есть )))
    – iRumba
    31 окт 2016 в 2:22
  • Какая то ерунда. Запрос то выполняется несколько секунд, то несколько минут с одними и теми же данными
    – iRumba
    31 окт 2016 в 5:14
2

Таблица, данные и доп. индекс:

create table tree
(
    ID int not NULL primary key,
    ParentID int NULL foreign key references tree (ID)
);

insert into tree (ID, ParentID) values
    (1, NULL),
        (2, 1), (3, 1),
    (4, NULL),
        (5, 4),
        (6, 4),
            (7, 6),
                (8, 7);

create index IX_tree_ParentID on tree (ParentID) include (ID);

Представление для полного дерева:

create view treeView
as
    with cte(ID, ParentID, Level)
    as
    (
        select t.ID, t.ParentID, 0
        from tree t
        where ParentID is NULL
        union all
        select t.ID, t.ParentID, cte.Level + 1
        from tree t
            join cte on cte.ID = t.ParentID
    )
    select ID, ParentID, Level
    from cte
GO

Функция для дочерних узлов (исключая узел-параметр)

create function treeItemDescendants2
(
    @itemID int
)
returns table
as return
    with cte(ID, ParentID, Level)
    as
    (
        select t.ID, t.ParentID, 1
        from tree t
        where ParentID = @itemID
        union all
        select t.ID, t.ParentID, cte.Level + 1
        from tree t
            join cte on cte.ID = t.ParentID
    )
    select ID, ParentID, Level
    from cte
GO

Собственно сам запрос:

select t.ID, d.ID as Child, t.Level, d.Level as ChildLevel
from treeView t
    cross apply treeItemDescendants2(t.ID) d;

Результат:

ID          Child       Level       ChildLevel
----------- ----------- ----------- -----------
1           2           0           1
1           3           0           1
4           5           0           1
4           6           0           1
4           7           0           2
4           8           0           3
6           7           1           1
6           8           1           2
7           8           2           1

P.S.
на 70+ тыс. записей у меня запрос отрабатывал за ~4 секунды. Если Level хранить в таблице столбцом, а не вычислять в treeView (оно тогда не нужно), то за 2.4 сек (результирующая выборка на моих данных получалась около 400 тыс. строк).

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.