Настройка производительности на рекурсивном CTE - PullRequest
Новая
       17

Настройка производительности на рекурсивном CTE

0 голосов
/ 11 октября 2019

У меня есть следующая таблица с образцами данных:

Таблица: tbl_nodes

create table tbl_nodes
(
    nod1 varchar(50),
    nod2 varchar(50)
);

Образцы данных: 

insert into tbl_nodes values('Node1','Node2'); 
insert into tbl_nodes values('Node2','Node4'); 
insert into tbl_nodes values('Node2','Node3'); 
insert into tbl_nodes values('Node2','Node5'); 
insert into tbl_nodes values('Node3','Node5'); 
insert into tbl_nodes values('Node3','Node6'); 
insert into tbl_nodes values('Node6','Node7'); 
insert into tbl_nodes values('Node10','Node11');
insert into tbl_nodes values('Node6','Node8');
insert into tbl_nodes values('Node18','Node19');
insert into tbl_nodes values('Node9','Node10');
insert into tbl_nodes values('Node12','Node13');
insert into tbl_nodes values('Node15','Node16');

ПРИМЕЧАНИЕ : У меня больше, чем 5000 записей в таблице выше.

Ожидаемый результат : 

------------------------------------
Connectivity        
------------------------------------
Node1->Node2->Node3->Node5
Node1->Node2->Node3->Node6->Node7
Node1->Node2->Node3->Node6->Node8
Node1->Node2->Node4
Node1->Node2->Node5
Node9->Node10->Node11

Объяснение Об ожидаемом результате : Я хочу найти соединение между узлами, имеющими более 2 узловНапример, Node1 имеет связь с Node2 и Node2 с 3,4,5 и т. д., как показано в ожидаемом наборе результатов. И хотим отображать каждое соединение до тех пор, пока не будет найден конечный узел, например конечными узлами являются Node4, Node5, Node7, Node8 и Node11.

Я попробовал следующий запрос:

Моя попытка : 

;WITH CTE AS
(
    SELECT  nod1,nod2,
            CAST(nod1 AS VARCHAR(MAX))+'->' AS conn, 
            1 as lvl 
    from tbl_nodes T1
    where EXISTS (select 1 from tbl_nodes T2 where T1.nod2 =T2.nod1) OR 
    EXISTS (select 1 from tbl_nodes T3 WHERE T1.nod1 =T3.nod2)
    UNION ALL
    SELECT C1.nod1,C1.nod2,
           C.conn+CAST(C1.nod1 AS VARCHAR(MAX))+'->',
           c.lvl+1 
    FROM CTE C INNER JOIN tbl_nodes C1 ON  C.nod2 = C1.nod1
    WHERE CHARINDEX(','+C.nod2+',',C.conn)=0 
),cte2 as 
(
    select * , ROW_NUMBER() over (partition by nod1,nod2 order by lvl)as rn From CTE
),cte3 as
(
    select nod1,nod2 ,MAX(LEN(conn)) conn,MAX(rn) rn
    from cte2
    group by nod1,nod2
)
SELECT DISTINCT c2.conn+c3.nod2 AS Connectivity
from cte3 c3
inner join cte2 c2 on c3.rn = c2.rn and c3.nod1 = c2.nod1
where c3.nod2 not in (select nod1 from cte2)

Вышеупомянутый запрос работает нормально, но не может получить результат для записей более чем5000, запрос продолжает выполняться безрезультатно.

Редактировать : я не могу прикрепить текущие данные, поскольку они содержат конфиденциальную информацию, но объясню! У меня есть таблица со столбцами Name1 и Name2, которые я назвал Nod1 и Nod2. Я хочу выяснить отношения между именами, как мы находим связь между узлами здесь в данном примере. Один человек (Name1), возможно, совершил какую-то транзакцию со вторым лицом (Name2), а Name2, возможно, должен будет сделать любое другое лицо. Поэтому мне нужно выяснить связь сделок между людьми. Это так же, как приведенный пример. Я попытался с помощью данного запроса разделить данные: для 100 записей это происходит в течение нескольких секунд, для 500 записей это занимает 1 минуту, а для 5000 записей он продолжает выполняться из-за большего количества перестановок и комбинаций. Проблема в том, что с последним набором данных (5000) мы должны выяснить ссылки.

Ответы [ 2 ]

1 голос
/ 11 октября 2019

Необходимо решить 2 вопроса об этой проблеме:

  1. Удалить пути, которые еще не закончились.
  2. Обнаружить цикл (который вызывает рекурсивный цикл cteбесконечно).

Итак, вот моя собственная версия ответа: 

IF  OBJECT_ID('tempdb..#tbl_nodes') IS NOT NULL
    DROP TABLE  #tbl_nodes;
CREATE TABLE    #tbl_nodes (
                    nod1    VARCHAR(50)
                ,   nod2    VARCHAR(50)
                );

CREATE NONCLUSTERED INDEX #IX_tbl_nodes_1 ON #tbl_nodes (nod1, nod2);
CREATE NONCLUSTERED INDEX #IX_tbl_nodes_2 ON #tbl_nodes (nod2, nod1);

INSERT INTO #tbl_nodes (nod1, nod2)
VALUES  ('Node1','Node2')
    ,   ('Node2','Node4')
    ,   ('Node2','Node3')
    ,   ('Node2','Node5')
    ,   ('Node3','Node5')
    ,   ('Node3','Node6')
    ,   ('Node6','Node7')
    ,   ('Node10','Node11')
    ,   ('Node6','Node8')
    ,   ('Node18','Node19')
    ,   ('Node9','Node10')
    ,   ('Node12','Node13')
    ,   ('Node15','Node16')
    ,   ('Node8', 'Node3')
    ;


WITH cte AS (
    SELECT  parent.nod1, parent.nod2
        ,   [link] = CAST('[' + parent.nod1 + '] -> [' + parent.nod2 + ']' AS VARCHAR(MAX))
        ,   [flag] = f.flag
        ,   [loop] = 0
        ,   [stop] = 0
        ,   [nodes] = 2
    FROM        #tbl_nodes AS parent
    LEFT JOIN   #tbl_nodes AS child
            ON  parent.nod1 = child.nod2
    CROSS APPLY (
        SELECT  _f.flag, [rn] = ROW_NUMBER() OVER(ORDER BY _f.flag ASC)
        FROM    (
            SELECT  [flag] = CAST(1 AS BIT)
            UNION ALL
            SELECT  [flag] = CAST(0 AS BIT)
            FROM    #tbl_nodes AS __f
            WHERE   parent.nod2 = __f.nod1
        ) AS _f
    ) AS f
    WHERE   child.nod2 IS NULL
        AND f.rn = 1
    UNION ALL
    SELECT  parent.nod1, child.nod2
        ,   [link] = CAST(parent.link + ' -> [' + child.nod2 + ']' AS VARCHAR(MAX))
        ,   [flag] = f.flag
        ,   [loop] = l.loop
        ,   [stop] = l.stop
        ,   [nodes] = parent.nodes + 1
    FROM        cte AS parent
    CROSS APPLY (
        SELECT  _child.nod1, _child.nod2, [rn] = ROW_NUMBER() OVER(PARTITION BY _child.nod2 ORDER BY _child.nod2)
        FROM    #tbl_nodes AS _child
        WHERE   parent.nod2 = _child.nod1
    ) AS child
    CROSS APPLY (
        SELECT  _f.flag, [rn] = ROW_NUMBER() OVER(ORDER BY _f.flag ASC)
        FROM    (
            SELECT  [flag] = CAST(1 AS BIT)
            UNION ALL
            SELECT  [flag] = CAST(0 AS BIT)
            FROM    #tbl_nodes AS __f
            WHERE   child.nod2 = __f.nod1
        ) AS _f
    ) AS f
    CROSS APPLY (
        SELECT  [loop] = CASE WHEN (LEN(parent.link + ' -> [' + child.nod2 + ']') - LEN(REPLACE(parent.link + ' -> [' + child.nod2 + ']', '[' + child.nod2 + ']', ''))) / (LEN(child.nod2) + 2) > 1 THEN 1 ELSE 0 END
            ,   [stop] = CASE WHEN (LEN(parent.link) - LEN(REPLACE(parent.link, '[' + parent.nod2 + ']', ''))) / (LEN(parent.nod2) + 2) > 1 THEN 1 ELSE 0 END
    ) AS l
    WHERE   child.rn = 1
        AND f.rn = 1
        AND l.stop = 0
)
SELECT  cte.link, cte.loop
FROM    cte
WHERE   (cte.flag = 1 OR cte.loop = 1)
    AND cte.nodes > 2
ORDER BY cte.nod1
OPTION (MAXRECURSION 0);

Cheers.

Обновлено: по запросу @MAK я обновляю свойОтветьте, чтобы получить пути, которые имеют более 2 узлов.

1 голос
/ 11 октября 2019

Вот упрощенная версия вашего рекурсивного запроса, в котором используется оператор EXISTS: 

WITH cte_nodes AS (
    SELECT CAST(nod1 + '->' + nod2 AS VARCHAR(4000)) AS path, nod2
    FROM tbl_nodes AS root
    WHERE NOT EXISTS (
        -- no parent exists thus represents a root node
        SELECT 1
        FROM tbl_nodes
        WHERE nod2 = root.nod1
    ) AND EXISTS (
        -- at least one child exists thus connected with at least one node
        SELECT 1
        FROM tbl_nodes
        WHERE nod1 = root.nod2
    )
    UNION ALL
    SELECT CAST(prnt.path + '->' + chld.nod2 AS VARCHAR(4000)), chld.nod2
    FROM cte_nodes AS prnt
    JOIN tbl_nodes AS chld ON prnt.nod2 = chld.nod1
)
SELECT path
FROM cte_nodes
WHERE NOT EXISTS (
    -- no child exists thus represents a leaf node
    SELECT 1
    FROM tbl_nodes
    WHERE nod1 = cte_nodes.nod2
)
ORDER BY path
OPTION (MAXRECURSION 100) -- increase this value just enough to get the results
...