Need help/advice in improving pruning an adjacency tree

  • I have a test database which contains a TestQueue table that tests are fetched from and executed on various machines in my lab environment. One feature of the TestQueue, is that users are able to create "Execution Plans". These plans basically define future executions of the same test depending on the status of the current execution. The execution plans are implemented simply through an adjacency tree.

    My problem comes from when I want to prune the tree of unnecessary nodes as the test travels through it's execution plan. I am currently handling this through two stored procedures, one of which is recursive. The result is that I experience lots of locks which cause more timeouts than are acceptable.

    From the table and stored procedures below, can anyone tell me if I am doing anything inherently wrong, and perhaps suggest ways that I can improve this?

    The my current usage model is that whenever a test finishes, I remove it from the TestQueue by calling DeleteQueuedTest and passing in it's ID, and it's RunStatus (Pass, Fail, Error). DeleteQueuedTest then calls the recursive procedure to prune the tree.

    Thanks,

    Justin

    -- I stripped out all unnecessary columns and am only showing those referenced by the stored procs

    CREATE TABLE [dbo].[TestQueue](

    [TestQueueID] [int] IDENTITY(1,1) NOT NULL,

    [ExecutionParentID] [int] NULL,

    [ExecutionCondition] [varchar](10) COLLATE SQL_Latin1_General_CP1_CI_AS NULL,

    CONSTRAINT [PK_TestQueue] PRIMARY KEY CLUSTERED

    (

    [TestQueueID] ASC

    )WITH (IGNORE_DUP_KEY = OFF) ON [PRIMARY]

    ) ON [PRIMARY]

    CREATE PROCEDURE [dbo].[DeleteQueuedTest]

    (

    @TestQueueID INT = NULL,

    @KeepCondition VARCHAR(10) = NULL

    )

    AS

    SET NOCOUNT ON

    BEGIN

    BEGIN TRAN

    -- start by recursively deleteing any queue sub tree nodes that this queue node may be the root of

    EXEC [dbo].[DeleteQueueTree] @TestQueueID = @TestQueueID, @KeepCondition = @KeepCondition;

    -- reset the parent id of any child nodes which had the keep condition so that they become executable root nodes

    UPDATE TestQueue

    SET ExecutionParentID = NULL

    WHERE ExecutionParentID = @TestQueueID AND ExecutionCondition LIKE @KeepCondition

    IF @@ERROR = 0

    COMMIT TRAN

    ELSE

    ROLLBACK TRAN

    END

    CREATE PROCEDURE [dbo].[DeleteQueueTree]

    (

    @TestQueueID INT = NULL,

    @KeepCondition VARCHAR(10) = NULL

    )

    AS

    SET NOCOUNT ON

    BEGIN

    DECLARE @ChildQueueID INT

    -- recursively drill down to the leaf nodes and delete them first

    IF @KeepCondition IS NULL

    BEGIN

    WHILE EXISTS (SELECT TestQueueID FROM TestQueue WHERE ExecutionParentID = @TestQueueID)

    BEGIN

    SELECT TOP 1 @ChildQueueID = TestQueueID FROM TestQueue WHERE ExecutionParentID = @TestQueueID

    -- keep condition must be null in the recursive case.

    -- this will ensure that all children of this node are deleted.

    EXEC [dbo].[DeleteQueueTree] @TestQueueID = @ChildQueueID, @KeepCondition = NULL;

    End

    END

    ELSE

    BEGIN

    WHILE EXISTS (SELECT TestQueueID FROM TestQueue WHERE ExecutionParentID = @TestQueueID AND (ExecutionCondition NOT LIKE @KeepCondition OR ExecutionCondition IS NULL))

    BEGIN

    SELECT TOP 1 @ChildQueueID = TestQueueID FROM TestQueue where ExecutionParentID = @TestQueueID AND (ExecutionCondition NOT LIKE @KeepCondition OR ExecutionCondition IS NULL)

    -- keep condition must be null in the recursive case.

    -- this will ensure that all children of this node are deleted.

    EXEC [dbo].[DeleteQueueTree] @TestQueueID = @ChildQueueID, @KeepCondition = NULL;

    END

    END

    -- remove TestQueue record

    DELETE FROM TestQueue WHERE TestQueueID = @TestQueueID

    END

  • Recursion of stored procedures is always a bad Idea.

    You should use a CTE (or any other method you feel comfortable with) to determine which IDs you need deleted and then issue a single DELETE statement.

    Hope it helps.


    * Noel

  • Thanks Noel for the suggestion to use a CTP. I ended up modifying just my recursive stored procedure and this is what I came up with.

    ALTER PROCEDURE [dbo].[DeleteQueueTree]

    (

    @TestQueueID INT = NULL,

    @KeepCondition VARCHAR(10) = NULL

    )

    AS

    SET NOCOUNT ON

    BEGIN

    WITH ChildExecutionPlanIDs AS (

    -- Get all level 1 child nodes which

    -- do not match the execution condition

    SELECT TestQueueID

    FROM TestQueue

    WHERE ExecutionParentID = @TestQueueID AND

    (ExecutionCondition NOT LIKE COALESCE(@KeepCondition, '') OR ExecutionCondition IS NULL)

    UNION ALL

    -- Get all level 2+ child nodes whose parents

    -- were retrieved in the above query

    SELECT TQ.TestQueueID

    FROM TestQueue TQ INNER JOIN

    ChildExecutionPlanIDs EPID ON TQ.ExecutionParentID = EPID.TestQueueID

    )

    -- remove TestQueue record

    DELETE FROM TestQueue

    WHERE TestQueueID IN (SELECT EPID.TestQueueID FROM ExecutionPlanIDs EPID) OR TestQueueID = @TestQueueID

    END

    So far it looks good, but I am still testing it out and trying to collect performance data. If you have any other suggestions, please let me know.

    Thanks again,

    -Justin

  • Just a thought. You still have to do the second step where you update the rows that matched the keep condition. Read up on the MERGE statement (it's new) and you can take care of the DELETEs and UPDATEs in a single pass using your recursive CTE.

    __________________________________________________

    Against stupidity the gods themselves contend in vain. -- Friedrich Schiller
    Stop, children, what's that sound? Everybody look what's going down. -- Stephen Stills

Viewing 4 posts - 1 through 3 (of 3 total)

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