Recursion with a Twist

Question

Recursion with a Twist

Forum Etiquette: How to post Reporting Services problems

[/url]

Forum Etiquette: How to post data/code on a forum to get the best help - by Jeff Moden
[/url]

How to Post Performance Problems - by Gail Shaw
[/url]

Jeff Moden SSC Guru Points: 1004362 More actions · Answer 1

Evil Kraig F (11/28/2012)
This is NOT pretty, but it IS functional.
--am trying to write a query against a table of invoices, returning all relevant rows for a particular InvoiceId. Heres some sample data:
--Create temp table to hold the dummy data
if object_id('tempdb..#IDs') is not null
drop table #IDs
if object_id('tempdb..#TempStore') is not null
drop table #TempStore
create table #IDs (
InvoiceId int not null
,BookingId int not null
) on [PRIMARY]
go
alter table #IDs add constraint PK_IDs primary key clustered (
InvoiceId
,BookingId
)
with (
STATISTICS_NORECOMPUTE = off
,IGNORE_DUP_KEY = off
,ALLOW_ROW_LOCKS = on
,ALLOW_PAGE_LOCKS = on
) on [PRIMARY]
go
insert #IDs ( InvoiceId, BookingId)
select * from (values (1,9), (1,10), (1,11), (2,11), (3,11), (3,12), (3,13), (4,14), (5,14)) data(InvoiceId,BookingId)
select * from #IDs
DECLARE @InvoiceID INT,
@Rowcount INT
SELECT @InvoiceID = 1,
@Rowcount = 1
CREATE TABLE #TempStore
(InvoiceID INT, BookingID INT)
INSERT INTO #TempStore
SELECT
InvoiceID, BookingID
FROM
#IDs
WHERE
InvoiceID = @InvoiceID
-- Set this here, might as well not hit the loop if no records to work from.
SELECT @Rowcount = @@ROWCOUNT
WHILE @Rowcount <> 0
BEGIN
INSERT INTO #TempStore
SELECT
ids2.InvoiceID, ids2.BookingID
FROM
#IDs
JOIN
(SELECT DISTINCT BookingID FROM #TempStore) AS drv
ON#IDs.BookingID = drv.BookingID
JOIN
#IDs AS ids2
ON#IDs.InvoiceID = ids2.InvoiceID
WHERE
#IDs.InvoiceID NOT IN(SELECT DISTINCT InvoiceID FROM #TempStore)
SET @Rowcount = @@ROWCOUNT
END
SELECT * FROM #TempStore

It might not be pretty but it appears to be the fastest... and I can't beat it. Nicely done, Craig!

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

Paul White SSC Guru Points: 150467 More actions · Answer 2

-- removed --

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Jeff Moden SSC Guru Points: 1004362 More actions · Answer 3

SQL Kiwi (12/1/2012)
The set-based iteration (WHILE loop) solution may well be best here, but the following is a recursive CTE solution that appears to work correctly:

All "seeks", too! Nicely done.

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

mister.magoo SSC-Forever Points: 47174 More actions · Answer 4

SQL Kiwi (12/1/2012)
The set-based iteration (WHILE loop) solution may well be best here, but the following is a recursive CTE solution that appears to work correctly:

Hi Paul,

I think there is a problem with duplicates...although this test data may not be valid.

Try it with this sample data:

INSERT INTO #IDs

(

InvoiceId,

BookingId

)

VALUES

(1,1),

(1,2),

(2,1),

(2,2);

You get this:

MM

select geometry::STGeomFromWKB(0x0106000000020000000103000000010000000B0000001000000000000840000000000000003DD8CCCCCCCCCC0840000000000000003DD8CCCCCCCCCC08408014AE47E17AFC3F040000000000104000CDCCCCCCCCEC3F9C999999999913408014AE47E17AFC3F9C99999999991340000000000000003D0000000000001440000000000000003D000000000000144000000000000000400400000000001040000000000000F03F100000000000084000000000000000401000000000000840000000000000003D0103000000010000000B000000000000000000143D000000000000003D009E99999999B93F000000000000003D009E99999999B93F8014AE47E17AFC3F400000000000F03F00CDCCCCCCCCEC3FA06666666666FE3F8014AE47E17AFC3FA06666666666FE3F000000000000003D1800000000000040000000000000003D18000000000000400000000000000040400000000000F03F000000000000F03F000000000000143D0000000000000040000000000000143D000000000000003D, 0);

mister.magoo SSC-Forever Points: 47174 More actions · Answer 5

As is becoming a habit, I would like to offer up my Identity Hack - rCTE replacement...

It performs quite nicely and doesn't suffer from the dupes problem I have seen in some others - I think...

---- Create a temp table to hold the results

---- include an identity column to keep track of the recursion

---- include a computed column to keep track of whether we are

---- looking for InvoiceId or BookingId, which flips every other

---- loop, so first we look for BookingId, then InvoiceId

IF OBJECT_ID('tempdb..#idhack') IS NULL

BEGIN

CREATE TABLE #idhack(

Depth INT IDENTITY(1,1) NOT NULL,

InvoiceId INT NOT NULL,

BookingId INT NOT NULL,

InvOrBook AS (Depth & 1) PERSISTED -- Flips every other row.

);

CREATE UNIQUE CLUSTERED INDEX ix_bid ON #idhack(BookingId,InvoiceId);

CREATE UNIQUE INDEX ix_invid ON #idhack(InvoiceId,BookingId) include (InvOrBook);

END

DECLARE

@InvoiceID INTEGER = 3;

-- Enable identity insert so we can insert our own values and have duplicates.

SET IDENTITY_INSERT #idhack ON;

-- put the first invoice into the results

INSERT #idhack(Depth, InvoiceId, BookingId)

SELECT 1, ids.InvoiceId, ids.BookingId

FROM #IDS AS ids

WHERE ids.InvoiceId = @InvoiceID;

-- recurse down looking for more invoices / bookings

-- use SCOPE_IDENTITY to tell us which level we are on.

WHILE @@ROWCOUNT>0

INSERT #idhack(Depth, InvoiceId, BookingId)

SELECT idh.Depth+1, ids.InvoiceId, ids.BookingId

FROM #IDS AS ids

JOIN #idhack idh

ON (InvOrBook = 1 AND ids.BookingId = idh.BookingId)

OR (InvOrBook = 0 AND ids.InvoiceId = idh.InvoiceId)

WHERE idh.Depth = SCOPE_IDENTITY()

AND NOT EXISTS (

SELECT 1

FROM #idhack idh2

WHERE idh2.InvoiceId = ids.InvoiceId

AND idh2.BookingId = ids.BookingId

);

-- turn off identity insert

SET IDENTITY_INSERT #idhack OFF;

-- and select the results

SELECT InvoiceId, BookingId

FROM #idhack;

MM

select geometry::STGeomFromWKB(0x0106000000020000000103000000010000000B0000001000000000000840000000000000003DD8CCCCCCCCCC0840000000000000003DD8CCCCCCCCCC08408014AE47E17AFC3F040000000000104000CDCCCCCCCCEC3F9C999999999913408014AE47E17AFC3F9C99999999991340000000000000003D0000000000001440000000000000003D000000000000144000000000000000400400000000001040000000000000F03F100000000000084000000000000000401000000000000840000000000000003D0103000000010000000B000000000000000000143D000000000000003D009E99999999B93F000000000000003D009E99999999B93F8014AE47E17AFC3F400000000000F03F00CDCCCCCCCCEC3FA06666666666FE3F8014AE47E17AFC3FA06666666666FE3F000000000000003D1800000000000040000000000000003D18000000000000400000000000000040400000000000F03F000000000000F03F000000000000143D0000000000000040000000000000143D000000000000003D, 0);

Paul White SSC Guru Points: 150467 More actions · Answer 6

mister.magoo (12/2/2012)
I think there is a problem with duplicates...although this test data may not be valid.

I found another issue with the recursive CTE solution, so I have removed it for the time being.

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi