Find sub-tree nodes

Question

Find sub-tree nodes

Ian Main

SSC Veteran

Points: 233
More actions
October 8, 2007 at 10:40 pm

#178814

Hi,
I have a tree structure represented by a simple table that references itself:
CREATE TABLE [dbo].[AframeGroup] (
[GroupID] [int] IDENTITY (1, 1) NOT NULL ,
[ParentGroupID] [int] NOT NULL ,
[Name] [varchar] (50) COLLATE SQL_Latin1_General_CP1_CI_AS NOT NULL ,
) ON [PRIMARY]
I need write an SP (or function?) that accepts a parameter of a GroupID and returns a Table of all GroupIDs that are below the GroupID supplied as a parameter.
This is the current Group structure (see below).
If I suppliy 12 as a parameter, I need to get all sub-IDs returned in a table (ie 13, 14, 15, 16, 17, 18, 19).
If I suppliy 6 as a parameter, I need to get all sub-IDs returned in a table (ie 7, 8, 9, 10, 11, 12 13, 14, 15, 16, 17, 18, 19, 20, 21).
----All (ID = 6)
--------Direct Sales (ID = 7)
--------Inbound Calls (ID = 8)
------------QLD (ID = 10)
------------NSW (ID = 11)
------------Melbourne (ID = 12)
----------------Project A (ID = 13)
--------------------General (ID = 14)
--------------------Japanese (ID = 15)
--------------------Trade (ID = 16)
--------------------Outbound (ID = 17)
--------------------Holidays (ID = 18)
----------------Project B (ID = 19)
------------St Kilda Road (ID = 20)
------------Geelong (ID = 21)
FYI: The SP that generated the text above is this SP:
ALTER PROCEDURE apBL_Group_GetSubTreeItems (@RootID int)
AS
BEGIN
DECLARE @GroupID int, @GroupName varchar(30)
SET @GroupName = (SELECT [Name] FROM AframeGroup WHERE GroupID = @RootID)
PRINT REPLICATE('-', @@NESTLEVEL * 4) + @GroupName + ' (ID = ' + CAST(@RootID AS VarChar(20)) + ')'
SET @GroupID = (SELECT MIN(GroupID) FROM AframeGroup WHERE ParentGroupID = @RootID)
WHILE @GroupID IS NOT NULL
BEGIN
EXEC dbo.apBL_Group_GetSubTreeItems @GroupID
SET @GroupID = (SELECT MIN(GroupID) FROM AframeGroup WHERE ParentGroupID = @RootID AND GroupID > @GroupID)
END
END
The problem is how do I store the GroupID during the recursion so that I end up with a table of all the GroupIDs?

Viewing 15 posts - 1 through 15 (of 19 total)

You must be logged in to reply to this topic. Login to reply

ChiragNS One Orange Chip Points: 26137 More actions · Answer 1

Hi

This is what CTE's are there for in sql2005 - recursive querying. check out BOL for details on how to use CTE in case you dont know.

How ever CTE's do have some performance issues if the number records to be returned is large.

"Keep Trying"

Mark Cowne One Orange Chip Points: 26952 More actions · Answer 2

Try this

DECLARE @RootID INT

SET @RootID=12;

WITH CTE AS(

SELECT GroupID,ParentGroupID

FROM AframeGroup

WHERE ParentGroupID=@RootID

UNION ALL

SELECT a.GroupID,a.ParentGroupID

FROM AframeGroup a

INNER JOIN CTE c ON c.GroupID=a.ParentGroupID)

SELECT GroupID

FROM CTE

ORDER BY GroupID

____________________________________________________

Deja View - The strange feeling that somewhere, sometime you've optimised this query before

How to get the best help on a forum

http://www.sqlservercentral.com/articles/Best+Practices/61537

haiao2000 Hall of Fame Points: 3734 More actions · Answer 3

Mark-101232 (10/9/2007)
Try this
DECLARE @RootID INT
SET @RootID=12;
WITH CTE AS(
SELECT GroupID,ParentGroupID
FROM AframeGroup
WHERE ParentGroupID=@RootID
UNION ALL
SELECT a.GroupID,a.ParentGroupID
FROM AframeGroup a
INNER JOIN CTE c ON c.GroupID=a.ParentGroupID)
SELECT GroupID
FROM CTE
ORDER BY GroupID

Eventually I run into performance issue when number records being so large. Could you suggest another method of doing tree drill down?

Thanks!

Eugene Elutin SSC Guru Points: 59322 More actions · Answer 4

I've not checked when OP did post original question...

🙂

_____________________________________________
"The only true wisdom is in knowing you know nothing"
"O skol'ko nam otkrytiy chudnyh prevnosit microsofta duh!":-D
(So many miracle inventions provided by MS to us...)

How to post your question to get the best and quick help[/url]

Sean Lange SSC Guru Points: 286590 More actions · Answer 5

haiao2000 (10/4/2012)
Eventually I run into performance issue when number records being so large. Could you suggest another method of doing tree drill down?
Thanks!

You do realize this thread is 5 years old? You really should just start your own thread.

_______________________________________________________________

Need help? Help us help you.

Read the article at http://www.sqlservercentral.com/articles/Best+Practices/61537/ for best practices on asking questions.

Need to split a string? Try Jeff Modens splitter http://www.sqlservercentral.com/articles/Tally+Table/72993/.

Cross Tabs and Pivots, Part 1 – Converting Rows to Columns - http://www.sqlservercentral.com/articles/T-SQL/63681/
Cross Tabs and Pivots, Part 2 - Dynamic Cross Tabs - http://www.sqlservercentral.com/articles/Crosstab/65048/
Understanding and Using APPLY (Part 1) - http://www.sqlservercentral.com/articles/APPLY/69953/
Understanding and Using APPLY (Part 2) - http://www.sqlservercentral.com/articles/APPLY/69954/

Dwain Camps SSC Guru Points: 86948 More actions · Answer 6

Just goes to show that threads may die off in our memories but they live on forever in the heart of Google! 😛

My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]
My thought question: Have you ever been told that your query runs too fast?

My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.

Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St

Gazareth One Orange Chip Points: 27737 More actions · Answer 7

Old threads don't die, they just get flushed to disk...

haiao2000 Hall of Fame Points: 3734 More actions · Answer 8

Sean Lange (10/4/2012)
haiao2000 (10/4/2012)
Eventually I run into performance issue when number records being so large. Could you suggest another method of doing tree drill down?
Thanks!
You do realize this thread is 5 years old? You really should just start your own thread.

I didn't post an answer didn't I? I could have started new thread, but thought it was just simple question on the same topic. plus it will get populated to top of the list anyway...so why bother

Jeff Moden SSC Guru Points: 1004343 More actions · Answer 9

haiao2000 (10/4/2012)
Mark-101232 (10/9/2007)
Try this
DECLARE @RootID INT
SET @RootID=12;
WITH CTE AS(
SELECT GroupID,ParentGroupID
FROM AframeGroup
WHERE ParentGroupID=@RootID
UNION ALL
SELECT a.GroupID,a.ParentGroupID
FROM AframeGroup a
INNER JOIN CTE c ON c.GroupID=a.ParentGroupID)
SELECT GroupID
FROM CTE
ORDER BY GroupID
Eventually I run into performance issue when number records being so large. Could you suggest another method of doing tree drill down?
Thanks!

Nested Sets. HierarchyID. Materialized path with a level based splitter. 😉

How many nodes do you have in your Hierarchy and how often is it updated?

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

haiao2000 Hall of Fame Points: 3734 More actions · Answer 10

Jeff Moden (10/8/2012)
haiao2000 (10/4/2012)
Mark-101232 (10/9/2007)
Try this
DECLARE @RootID INT
SET @RootID=12;
WITH CTE AS(
SELECT GroupID,ParentGroupID
FROM AframeGroup
WHERE ParentGroupID=@RootID
UNION ALL
SELECT a.GroupID,a.ParentGroupID
FROM AframeGroup a
INNER JOIN CTE c ON c.GroupID=a.ParentGroupID)
SELECT GroupID
FROM CTE
ORDER BY GroupID
Eventually I run into performance issue when number records being so large. Could you suggest another method of doing tree drill down?
Thanks!
Nested Sets. HierarchyID. Materialized path with a level based splitter. 😉
How many nodes do you have in your Hierarchy and how often is it updated?

It gets updated pretty often. #Level of node is unpredictable, it can be any number of levels in the hierarchy. I have look at HierarchyID but it is not something we can be used at this time as not all clients have SQL server 2008. also it doesn't seem we can use Materialized path either as our table is designed a bit funny (which I can't explai myself) here is how it looks:

(ParentID GUID, ChildID GUID, ...), plus non of the parent ID or child ID is Pkey.

Jeff Moden SSC Guru Points: 1004343 More actions · Answer 11

Still missing some information...

1. How often is the hierarchy updated?

2. How many total nodes are in the hierarchy?

It's important because I have an some experience in how to do all of this very quickly. And, yeah... we can avoid 2K8 so long as we can do 2K5 or better.

plus non of the parent ID or child ID is Pkey

Have you got some sample data and a CREATE TABLE example you could provide to make this a bit easier?

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

haiao2000 Hall of Fame Points: 3734 More actions · Answer 12

Jeff Moden (10/8/2012)
Still missing some information...
1. How often is the hierarchy updated? ---anser: It can be very often, daily, weekly
2. How many total nodes are in the hierarchy? -->anser: there can be hundred of nodes depends on clients
It's important because I have an some experience in how to do all of this very quickly. And, yeah... we can avoid 2K8 so long as we can do 2K5 or better.
plus non of the parent ID or child ID is Pkey
Have you got some sample data and a CREATE TABLE example you could provide to make this a bit easier?

Jeff,

Here is some sample data. I am trying to work solution using Materialized Path method, but with the primary key being ID and not objectID, and since objectId is not a Interger, it seems to be a bit challenge.

-ID is defined as BigInt Identity(1,1)

-Duplicated ParentID/ObjectID pair is allowed, just like ID=1 & 2

-One parent can have multiple children

-One children can have multiple parents as well, just like ID: 7 & 8

-MaterializePath is something I added with intention to be used storing calculated marialized path based on ID field

-As I noticed earlier post, using recursive common table expression is too slow for the amount of data we have. This table can contain more than 10 millions or records

WITH TempTreeCTE (ID, ParentID, ObjectID, OtherData, MaterializedPath) AS (

SELECT 1,'B4ED3C39-9626-44B6-93D9-000B37BDA575','95C1A774-C79B-4861-AAB4-09E8070188FB', NEWID(),NULL UNION ALL

SELECT 2,'B4ED3C39-9626-44B6-93D9-000B37BDA575','95C1A774-C79B-4861-AAB4-09E8070188FB', NEWID(),NULL UNION ALL

SELECT 3,'B4ED3C39-9626-44B6-93D9-000B37BDA575','5A116CF5-BD94-46F7-9533-4576D83CC6B0', NEWID(),NULL UNION ALL

SELECT 4,'95C1A774-C79B-4861-AAB4-09E8070188FB','E43FB52B-863D-4D28-95B5-2871CC823721', NEWID(),NULL UNION ALL

SELECT 5,'E43FB52B-863D-4D28-95B5-2871CC823721','3C571CC5-FE52-4453-AFDC-313EBF9CF05F', NEWID(),NULL UNION ALL

SELECT 6,'E43FB52B-863D-4D28-95B5-2871CC823721','68B7C10A-D03E-4F99-9737-6D4CED3B4692', NEWID(),NULL UNION ALL

SELECT 7,'E43FB52B-863D-4D28-95B5-2871CC823721','6Y3435Y9-FE52-4453-AFDC-313EBF9CF05F', NEWID(),NULL UNION ALL

SELECT 8,'D77FB52B-863D-4D28-95B5-2871CC823721','6Y3435Y9-FE52-4453-AFDC-313EBF9CF05F', NEWID(),NULL

) SELECT * FROM TempTreeCTE;

If I can get some help to determine/calculate MaterializedPath value programatically based on the ID field, that would be awsome. Something like created a function that calculates the materialized path, then run the update statement as follow

UPDATE TempTreeCTE

SET MaterializedPath = dbo.MaterializedPath(ID,@ObjectID);

code]

Oop! look like I have been hijacking the original post without knowing it 🙂

Thanks for looking at this.

haiao2000 Hall of Fame Points: 3734 More actions · Answer 13

Look like I figured out the way to calculate Materialized path programatically, the issue I am dealing with now is how to handle objects that have more than one parents.

ALTER FUNCTION dbo.MaterializedPath(

@ID BIGINT

,@ObjectID UNIQUEIDENTIFIER

)

RETURNS VARCHAR(200)

AS

BEGIN

DECLARE @Path VARCHAR(200)

SELECT @Path = '', @ID = ID, @ObjectID=ParentID

FROM TempTreeCTE

WHERE ID=@ID AND ObjectID=@ObjectID;

WHILE @@RowCount > 0

BEGIN

SELECT @Path = ISNULL(RTRIM(CAST(@ID AS VARCHAR(10)))+ ',','') + @Path

SELECT @ID=ID, @ObjectID=ParentID

FROM TempTreeCTE

WHERE ObjectID=@ObjectID

END

RETURN @Path

END;

Jeff Moden SSC Guru Points: 1004343 More actions · Answer 14

haiao2000 (10/9/2012)
the issue I am dealing with now is how to handle objects that have more than one parents.

THAT is the problem here (ie: showstopper). I may have a way around it though. I'll see what I can do tonight after work. Thank you for the sample data. It'll help a lot.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)