There is a table with a tree (id, parent)

You need to write a query that returns for each node all child nodes and child nodes of all child nodes (recursively), as well as a column with a level in the tree of the current node and a column with a level in the tree of the child node. I wrote a request, but it hangs. It specifically hangs (it takes a very long time and I can not cancel it). In this case, errors with the achievement of the level of recursion 100 does not crash. That is, as I understand it, recursion does not go deep, but the execution of one iteration goes to infinity.

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

As a result, from a table with such data

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

I want to get an answer

 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:

corrected the request, checked on a small amount of data, all the rules. But on a real table with 70,000 entries, the request is unrealistically long. So it needs to be optimized (or rewritten otherwise)

  • I did not understand how to get to the records with id 6, 7, 8 from the input data because there is no way from the root you specified (with parent = 0). And it is not clear what childLevel is, usually the child level is 1 more than the parent. - Mike
  • @Mike, you read it inattentively. "all child nodes and child nodes of all child nodes (recursively)" means that for a node with id = 4, you need to return not only nodes 5 and 6, but also their child nodes and nodes of their child nodes, in short, the entire subtree - iRumba
  • Here, now with the 4/6 record in the input data is better - Mike
  • @Mike, the remark was kind of the topic. I forgot to specify the node 6/4 in the initial data set. I fixed it - iRumba
  • @Mike, see update - iRumba

2 answers 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

The idea is that at every level of recursion we split the entry that came in, one of which goes further from the same root as the one that came in. And the second entry becomes the new root. Only those records that become root at the previous level ( old_n=1 ) are old_n=1 .

UPD How it works ...

For example, let's take only one data branch, from the 4/0 record:

 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 Затравка для следующего уровня, если бы он был

The final query takes all the records with N = 0 from the example above; it is in the sample in the old_n field. Entries with N = 1 are used only inside recursion to generate new branches of the tree.

  • Please describe in steps on the basis of the data proposed in the request, how it works ... otherwise my roof is coming from your request. It works, but I do not understand how! ( - iRumba
  • @iRumba Ok, a little later, it’s pretty hard to articulate ... half an hour yesterday I argued that there were no pitfalls after it worked :) - Mike
  • @iRumba In general, I wrote how the recordings behave, I don’t know, it will clarify something or even more confuse ... - Mike
  • Magic as it is))) - iRumba
  • What is nonsense. The request is executed a few seconds, then a few minutes with the same data - iRumba

Table, data and add. index:

 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);

View for full wood:

 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

Function for child nodes (excluding parameter node)

 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

Actually the request itself:

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

Result:

 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

PS
for 70+ thousand records, my request was processed in ~ 4 seconds. If Level stored in a table as a column, and not calculated in a treeView (then it is not needed), then in 2.4 seconds (the resulting sample on my data was obtained about 400 thousand lines).