Recursive CTEs
This is something that a lot of people have blogged about, but since it cropped up again recently in a discussion I was having about part of a project I thought it’d be worthwhile writing something myself.
SQL Server doesn’t like looping.
We all know this. We all know that includes cursors and while loops, but what seems to be forgotton is that a recursive common table expression is also a loop. A requirement came up for a developer to find all of the directory numbers that were stored in a table including those that were “missing” from the table (think sequence). Let’s create some sample data to illustrate the problem.
DROP TABLE IF EXISTS [testEnvironment];
CREATE TABLE [testEnvironment]
(
[ID] INT IDENTITY(1, 1),
[DIRECTORY_NUMBER] VARCHAR(50) NULL
);
CREATE CLUSTERED INDEX [cl_ID_testEnvironment] ON [testEnvironment] ([ID] ASC);
CREATE NONCLUSTERED INDEX [nc_DIRECTORY_NUMBER_testEnvironment] ON [testEnvironment] ([DIRECTORY_NUMBER] ASC);
INSERT INTO [testEnvironment]
( [DIRECTORY_NUMBER]
)
SELECT DISTINCT
[a].[randomBigInt]
FROM ( SELECT TOP 1000000
( ABS(CHECKSUM(NEWID())) % 1000000 ) + 1 AS [randomBigInt]
FROM [master].[sys].[syscolumns] [sc1]
CROSS JOIN [master].[sys].[syscolumns] [sc2]
CROSS JOIN [master].[sys].[syscolumns] [sc3]
) [a];
Being a good developer, they decided to avoid a cursor or a while loop to solve this and instead chose a recursive common table expression. Initially, the design was like this: -
-- THESE ARE PARAMETERS PASSED IN TO A REPORT
DECLARE @initial AS BIGINT = 3500,
@final AS BIGINT = 4500;
DECLARE @TEMP TABLE
(
[ID] INT IDENTITY(1, 1),
[DIRECTORY_NUMBER] VARCHAR(50),
[IP_DESCRIPTION] VARCHAR(11)
);
INSERT INTO @TEMP
( [DIRECTORY_NUMBER],
[IP_DESCRIPTION]
)
SELECT [DIRECTORY_NUMBER],
'Assigned'
FROM [testEnvironment]
WHERE ( [DIRECTORY_NUMBER] >= @initial
AND [DIRECTORY_NUMBER] < @final
);
WITH [cte_n]
AS ( SELECT @initial AS [DIRECTORY_NUMBER]
UNION ALL
SELECT [cte_n].[DIRECTORY_NUMBER] + 1
FROM [cte_n]
WHERE [cte_n].[DIRECTORY_NUMBER] + 1 < @final
)
INSERT INTO @TEMP
( [DIRECTORY_NUMBER],
[IP_DESCRIPTION]
)
SELECT [cte].[DIRECTORY_NUMBER], 'Un-Assigned'
FROM [cte_n] [cte]
WHERE NOT EXISTS ( SELECT *
FROM @TEMP [X]
WHERE [X].[DIRECTORY_NUMBER] = [cte].[DIRECTORY_NUMBER] )
OPTION ( MAXRECURSION 0 );
SELECT *
FROM @TEMP
ORDER BY [DIRECTORY_NUMBER];
Running this over a thousand rows, as in the example above, worked fine. The report was created and the developer started testing. As a load test, he decided to see what would happen if someone were to request a hundred thousand rows out of the report. This caused the report to take longer than the timeout settings to return (in fact, it took longer than an hour!) and is where my advice was sought.
I suggested that since we are looking at sequential numbers, we could just create a numbers table or a cascading common table expression that generates a numbers work table in memory. Below is an example of the cascading common table expression: -
-- THESE ARE PARAMETERS PASSED IN TO A REPORT
DECLARE @initial AS BIGINT = 3500,
@final AS BIGINT = 135000;
WITH [cte_n10] ( [N] )
AS ( SELECT 1
FROM ( VALUES ( 1), ( 1), ( 1), ( 1), ( 1), ( 1), ( 1), ( 1), ( 1), ( 1) ) [a] ( [n] )
),
[cte_n100] ( [N] )
AS ( SELECT 1
FROM [cte_n10] [a]
CROSS JOIN [cte_n10] [b]
),
[cte_n10000] ( [N] )
AS ( SELECT 1
FROM [cte_n100] [a]
CROSS JOIN [cte_n100] [b]
),
[cte_n1000000] ( [N] )
AS ( SELECT 1
FROM [cte_n100] [a]
CROSS JOIN [cte_n10000] [b]
),
[cte_RN] ( [N] )
AS ( SELECT 0
UNION ALL
SELECT TOP ( @final - @initial )
ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL
) )
FROM [cte_n1000000]
),
[cte_n] ( [DIRECTORY_NUMBER] )
AS ( SELECT @initial + [cte_RN].[N]
FROM [cte_RN]
WHERE @initial + [cte_RN].[N] <= @final
)
SELECT [cte].[DIRECTORY_NUMBER],
CASE WHEN [te].[DIRECTORY_NUMBER] IS NOT NULL THEN 'Assigned'
ELSE 'Un-Assigned'
END AS [IP_DESCRIPTION]
FROM [cte_n] [cte]
LEFT OUTER JOIN [testEnvironment] [te] ON [cte].[DIRECTORY_NUMBER] = [te].[DIRECTORY_NUMBER]
ORDER BY [cte].[DIRECTORY_NUMBER];
This takes advantage of a few cartesian joins to generate a set of numbers, followed by a window function and a top to limit the overall result-set. When we’re looking at few numbers, the cascading common table expression will only expand the parts of the query it actually needs (so for 10 rows, it’ll look at cte_n10, cte_RN and cte_n).
Let’s create a quick performance test to see what happens over a few different rows.
SET NOCOUNT ON;
DECLARE @TABLE AS TABLE
(
[Initial] BIGINT,
[Final] BIGINT
);
INSERT INTO @TABLE
( [Initial], [Final] )
VALUES ( 3500, 4500 ),
( 500, 10498 ),
( 673, 114980 );
DECLARE @Duration CHAR(12),
@StartTime DATETIME,
@Size INT;
DECLARE @initial AS BIGINT,
@final AS BIGINT;
WHILE EXISTS ( SELECT 1
FROM @TABLE )
BEGIN
SELECT TOP 1
@initial = [Initial],
@final = [Final]
FROM @TABLE
ORDER BY [Final] - [Initial];
SET @Size = @final - @initial;
DROP TABLE IF EXISTS #resultsHolder1;
SELECT @StartTime = GETDATE();
WITH [cte_n10] ( [N] )
AS ( SELECT 1
FROM ( VALUES ( 1), ( 1), ( 1), ( 1), ( 1), ( 1), ( 1), ( 1), ( 1), ( 1) ) [a] ( [n] )
),
[cte_n100] ( [N] )
AS ( SELECT 1
FROM [cte_n10] [a]
CROSS JOIN [cte_n10] [b]
),
[cte_n10000] ( [N] )
AS ( SELECT 1
FROM [cte_n100] [a]
CROSS JOIN [cte_n100] [b]
),
[cte_n1000000] ( [N] )
AS ( SELECT 1
FROM [cte_n100] [a]
CROSS JOIN [cte_n10000] [b]
),
[cte_RN] ( [N] )
AS ( SELECT 0
UNION ALL
SELECT TOP ( @final - @initial )
ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL
) )
FROM [cte_n1000000]
),
[cte_n] ( [DIRECTORY_NUMBER] )
AS ( SELECT @initial + [cte_RN].[N]
FROM [cte_RN]
WHERE @initial + [cte_RN].[N] <= @final
)
SELECT [cte].[DIRECTORY_NUMBER],
CASE WHEN [te].[DIRECTORY_NUMBER] IS NOT NULL THEN 'Assigned'
ELSE 'Un-Assigned'
END AS [IP_DESCRIPTION]
INTO [#resultsHolder1]
FROM [cte_n] [cte]
LEFT OUTER JOIN [testEnvironment] [te] ON [cte].[DIRECTORY_NUMBER] = [te].[DIRECTORY_NUMBER]
ORDER BY [cte].[DIRECTORY_NUMBER];
SELECT @Duration = CONVERT(CHAR(12), GETDATE() - @StartTime, 114);
RAISERROR('New Query Duration: %s over %d rows',0,1,@Duration,@Size) WITH NOWAIT;
DROP TABLE IF EXISTS #resultsHolder2
SELECT @StartTime = GETDATE();
DECLARE @TEMP TABLE
(
[ID] INT IDENTITY(1, 1),
[DIRECTORY_NUMBER] VARCHAR(50),
[IP_DESCRIPTION] VARCHAR(11)
);
INSERT INTO @TEMP
( [DIRECTORY_NUMBER],
[IP_DESCRIPTION]
)
SELECT [DIRECTORY_NUMBER],
'Assigned'
FROM [testEnvironment]
WHERE ( [DIRECTORY_NUMBER] >= @initial
AND [DIRECTORY_NUMBER] < @final
);
WITH [cte_n]
AS ( SELECT @initial AS [DIRECTORY_NUMBER]
UNION ALL
SELECT [cte_n].[DIRECTORY_NUMBER] + 1
FROM [cte_n]
WHERE [cte_n].[DIRECTORY_NUMBER] + 1 < @final
)
INSERT INTO @TEMP
( [DIRECTORY_NUMBER],
[IP_DESCRIPTION]
)
SELECT [cte].[DIRECTORY_NUMBER],
'Un-Assigned'
FROM [cte_n] [cte]
WHERE NOT EXISTS ( SELECT *
FROM @TEMP [X]
WHERE [X].[DIRECTORY_NUMBER] = [cte].[DIRECTORY_NUMBER] )
OPTION ( MAXRECURSION 0 );
SELECT [DIRECTORY_NUMBER],
[IP_DESCRIPTION]
INTO [#resultsHolder2]
FROM @TEMP
ORDER BY [DIRECTORY_NUMBER];
SELECT @Duration = CONVERT(CHAR(12), GETDATE() - @StartTime, 114);
RAISERROR('Initial Query Duration: %s over %d rows',0,1,@Duration,@Size) WITH NOWAIT;
DELETE FROM @TABLE
WHERE [Initial] = @initial
AND [Final] = @final;
END;
I inserted the result-set in to temporary tables to take the display time out of the equation. If you look at the messages tab, you will have something like looks like this: -
New Query Duration: 00:00:00:087 over 1000 rows
Initial Query Duration: 00:00:00:167 over 1000 rows
New Query Duration: 00:00:00:087 over 9998 rows
Initial Query Duration: 00:00:07:440 over 9998 rows
New Query Duration: 00:00:00:443 over 114307 rows
Note, I killed the query after 5 minutes, at which point the initial query had still not managed to return for 114,307 rows. Even without that part of the execution to compare with, we’re left with a fairly large improvement: -
| Rows | Initial Query Duration | New Query Duration |
|---|---|---|
| 1000 | 0.167 | 0.087 |
| 9998 | 7.440 | 0.087 |
| 114307 | 05:00.000 (killed query) | 0.443 |
That’s an improvement with no indexes and no major design change.
Share on: