CTE Recursion - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2008 Forums

Transact-SQL (2008)

CTE Recursion

Author

Topic

soaphope
Starting Member

13 Posts

Posted - 2011-02-22 : 23:12:23

Below is a query that recursively replaces tokens with replacement values using a recursive CTE, along with the results. As you can see from the results, the server is calculating a lot of result combinations that are not useful. Can someone shed some light on how the recursion is working and how to streamline it?

Query:


DECLARE @block varchar(1000)

SELECT @block = '$a $b $c $r'
;
WITH T AS
(
 SELECT '$a' as ckey, 'a_value' as cval UNION ALL
 SELECT '$b', 'b_value'    UNION ALL
 SELECT '$c', 'c_value'    UNION ALL
 SELECT '$r', 'recurse_$a'  
)
,
CTE_Rec  
AS  
( 
 SELECT TOP 1 REPLACE(@block, ckey, cval) rec
 FROM T
 WHERE PATINDEX('%' + ckey + '%',@block) > 0
 
 UNION ALL
 SELECT replace(rec, ckey, cval) 
 FROM CTE_Rec CROSS JOIN T
 WHERE PATINDEX('%' + ckey + '%',rec) > 0
)

SELECT * FROM CTE_Rec

Results:

a_value $b $c $r
a_value b_value $c $r
a_value $b c_value $r
a_value $b $c recurse_$a
a_value $b $c recurse_a_value
a_value b_value $c recurse_$a
a_value $b c_value recurse_$a
a_value $b c_value recurse_a_value
a_value b_value c_value recurse_$a
a_value b_value c_value recurse_a_value
a_value b_value c_value recurse_a_value
a_value b_value $c recurse_a_value
a_value b_value c_value recurse_$a
a_value b_value c_value recurse_a_value
a_value b_value c_value recurse_a_value
a_value b_value $c recurse_a_value
a_value $b c_value recurse_a_value
a_value b_value c_value recurse_a_value
a_value b_value c_value recurse_a_value
a_value b_value c_value $r
a_value $b c_value recurse_$a
a_value $b c_value recurse_a_value
a_value b_value c_value recurse_$a
a_value b_value c_value recurse_a_value
a_value b_value c_value recurse_a_value
a_value b_value c_value recurse_$a
a_value b_value c_value recurse_a_value
a_value b_value c_value $r
a_value b_value $c recurse_$a
a_value b_value $c recurse_a_value
a_value b_value c_value recurse_$a
a_value b_value c_value recurse_a_value
a_value b_value c_value recurse_a_value
a_value b_value c_value recurse_$a
a_value b_value c_value recurse_a_value

What I expected was this:

a_value $b $c $r
a_value b_value $c $r
a_value b_value c_value $r
a_value b_value c_value recurse_$a
a_value b_value c_value recurse_a_value

Thanks for any assistance. (Also thank you to malpashaa for helping me understand CTEs enough to even get this far.)

Salah Boukadoum
Founder, Soap Hope
Where 100% of profits go to lift women from poverty - http://soaphope.com

soaphope
Starting Member

13 Posts

Posted - 2011-02-23 : 10:50:48

When I change the CTE to this I can see the recursion and it removes some of the "extra" processing, but it's still overkill on the number of combinations that are being calculated.



DECLARE @block varchar(1000)

SELECT @block = '$a $b $c $r'
;
WITH T AS
(
 SELECT '$a' as ckey, 'a_value' as cval UNION ALL
 SELECT '$b', 'b_value'    UNION ALL
 SELECT '$c', 'c_value'    UNION ALL
 SELECT '$r', 'recurse_$a'  
)
,
CTE_Rec  
AS  
( 
 SELECT @block rec,
 CAST (1 as BIGINT) n_rec
  
 UNION ALL
 
 SELECT CAST (replace(rec, ckey, cval) AS varchar(1000)),
 ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
 FROM CTE_Rec CROSS JOIN T 
 WHERE PATINDEX('%' + ckey + '%',rec) > 0 AND n_rec = 1
)

SELECT * FROM CTE_Rec

Results:

$a $b $c $r 1
a_value $b $c $r 1
$a b_value $c $r 2
$a $b c_value $r 3
$a $b $c recurse_$a 4
a_value b_value $c $r 1
a_value $b c_value $r 2
a_value $b $c recurse_$a 3
a_value b_value c_value $r 1
a_value b_value $c recurse_$a 2
a_value b_value c_value recurse_$a 1
a_value b_value c_value recurse_a_value 1

soaphope
Starting Member

13 Posts

Posted - 2011-02-23 : 18:20:41

Maybe this is a step in the right direction. But it only works when ALL the items being searched for are in the block to search. If any item in the search table is not found in the block, the recursion stops and the result is incomplete. I'm hoping someone can get me past that hurdle.

[CODE]
DECLARE @block varchar(1000)

SELECT @block = '$a $b $c $r $z'
;
WITH T (ckey,cval) AS
(
SELECT '$a', 'a_value' UNION ALL
SELECT '$b', 'b_value' UNION ALL
SELECT '$c', 'c_value' UNION ALL
SELECT '$r', 'ra_recurse_$a' UNION ALL
SELECT '$z', 'zr_recurse_$r'
)
,
TN (ckey, cval, row, ct) AS (
SELECT ckey,
cval,
ROW_NUMBER() OVER (ORDER BY (SELECT NULL)),
COUNT(ckey) OVER (PARTITION BY (SELECT NULL))
FROM T
)
,
CTE_Replace (result,level)
AS
(
SELECT @block,
1
UNION ALL
SELECT CAST (replace(result, ckey, cval) AS varchar(1000)),
level+1
FROM CTE_Replace CROSS JOIN TN
WHERE PATINDEX('%' + ckey + '%',result) > 0 AND ((level = row) OR (level > ct))
)

SELECT * FROM CTE_Replace
[/CODE]

Results:

$a $b $c $r $z 1
a_value $b $c $r $z 2
a_value b_value $c $r $z 3
a_value b_value c_value $r $z 4
a_value b_value c_value ra_recurse_$a $z 5
a_value b_value c_value ra_recurse_$a zr_recurse_$r 6
a_value b_value c_value ra_recurse_a_value zr_recurse_$r 7
a_value b_value c_value ra_recurse_$a zr_recurse_ra_recurse_$a 7
a_value b_value c_value ra_recurse_a_value zr_recurse_ra_recurse_a_value 8
a_value b_value c_value ra_recurse_a_value zr_recurse_ra_recurse_$a 8
a_value b_value c_value ra_recurse_a_value zr_recurse_ra_recurse_a_value 9

But change say "$b" to "$x" and the recursion stops at that point.

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources