Find sub-tree nodes

  • 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?

  • 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"

  • 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
  • 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!

  • 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]

  • 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/

  • 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

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

  • 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

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

  • 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.

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

  • 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.

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

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

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

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