Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase ««1234»»»

Recursion with a Twist Expand / Collapse
Author
Message
Posted Wednesday, November 28, 2012 3:27 PM


SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Friday, September 19, 2014 5:16 AM
Points: 887, Visits: 1,774
Alan.B (11/28/2012)
Evil Kraig F (11/28/2012)
This is NOT pretty, but it IS functional.


I am trying to understand why went with a loop vs a set-based approach. I posted a more set based method earlier that gets the same results notably faster. I am not trying to be confrontational, I'm just trying to understand your approach or what I did wrong.



@Alan.b If i look at your method correctly it misses InvoiceID 3.

@Kraig your right about the issues with my method that you cant go both directions up the tree which i had forgotten about. (dont work with hierarchies much)


EDIT: i sat to long to hit the post button so struck what was said before the post.



For faster help in answering any problems Please read How to post data/code on a forum to get the best help - Jeff Moden for the best way to ask your question.

For performance Issues see how we like them posted here: How to Post Performance Problems - Gail Shaw

Need to Split some strings? Jeff Moden's DelimitedSplit8K
Jeff Moden's Cross tab and Pivots Part 1
Jeff Moden's Cross tab and Pivots Part 2

Jeremy Oursler
Post #1390169
Posted Thursday, November 29, 2012 12:12 AM
SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Sunday, September 14, 2014 12:30 AM
Points: 253, Visits: 540
how about this one
SET @InvoiceID = 1;WITH rCTE AS
(
SELECT InvoiceID, BookingID, 1 AS HierarchyLevel
FROM #IDs
WHERE InvoiceID = @InvoiceID
UNION ALL
SELECT IDs.InvoiceID, ids2.BookingID, rCTE.HierarchyLevel + 1 AS HierarchyLevel
FROM rCTE
JOIN #IDs ids
ON IDs.BookingID = rCTE.BookingID AND
ids.InvoiceId <> rcte.InvoiceID
INNER JOIN #IDs ids2
ON ids2.InvoiceId = ids.InvoiceID
WHERE rCTE.InvoiceID<ids2.InvoiceId
)
select * from Rcte





Every rule in a world of bits and bytes, can be bend or eventually be broken
MyBlog About Common dialog control
A Visualizer for viewing SqlCommand object script
Post #1390309
Posted Thursday, November 29, 2012 1:16 AM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: 2 days ago @ 12:18 PM
Points: 5,438, Visits: 7,606
thava (11/29/2012)
how about this one


It can't go backwards from 3 to get back to 1 because of the limitor to reduce duplication and endless recursion. It's similar to the issue above in the hierarchy model. You need to be able to go after either InvoiceID 3 or InvoiceID 1 and get the same result list.



- Craig Farrell

Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.

For better assistance in answering your questions | Forum Netiquette
For index/tuning help, follow these directions. |Tally Tables

Twitter: @AnyWayDBA
Post #1390332
Posted Thursday, November 29, 2012 1:56 AM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Yesterday @ 4:18 AM
Points: 5,245, Visits: 12,161
First of all, thanks to everyone who has taken the time to think about this problem and contribute. I spent over an hour blowing recursion limits left, right and centre yesterday without getting anywhere close, so I appreciate the input.

I was excited to see Alan's solution working perfectly with my data, only to test it out using Craig's alternative (and valid) data and see it not work quite so well ...

It remains a problem for us here, which for the moment we are dealing with by hard-coding multiple recursion levels. But we have examples where the actual number of recursions needed to scrape all the details together is greater than what we have coded. So any further input is most welcome.

Thanks
Phil



Help us to help you. For better, quicker and more-focused answers to your questions, consider following the advice in this link.

When you ask a question (and please do ask a question: "My T-SQL does not work" just doesn't cut it), please provide enough information for us to understand its context.
Post #1390347
Posted Thursday, November 29, 2012 2:02 AM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Yesterday @ 4:18 AM
Points: 5,245, Visits: 12,161
I wrote the above response before trying Craig's solution, which certainly does the business - thanks! Maybe this is one instance where a loop is the best solution. I'll leave it a while longer (no pun intended) before I implement it, to see whether anyone comes up with a set-based solution.


Help us to help you. For better, quicker and more-focused answers to your questions, consider following the advice in this link.

When you ask a question (and please do ask a question: "My T-SQL does not work" just doesn't cut it), please provide enough information for us to understand its context.
Post #1390350
Posted Thursday, November 29, 2012 11:48 AM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: 2 days ago @ 12:18 PM
Points: 5,438, Visits: 7,606
Phil Parkin (11/29/2012)
I wrote the above response before trying Craig's solution, which certainly does the business - thanks! Maybe this is one instance where a loop is the best solution. I'll leave it a while longer (no pun intended) before I implement it, to see whether anyone comes up with a set-based solution.


I poked at it a bit more yesterday and while I can make that process look cleaner (it's a bit disorganized) it's the best solution I have available without digging into indexes and possible shortcuts for some of the sub-data, like the BookingID list. The killer is in the self-referencing bookingIDs and the bi-directional hierarchy, where you're going both 'up and down' the chain simultaneously.

Glad to help, though.



- Craig Farrell

Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.

For better assistance in answering your questions | Forum Netiquette
For index/tuning help, follow these directions. |Tally Tables

Twitter: @AnyWayDBA
Post #1390750
Posted Thursday, November 29, 2012 6:58 PM
Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Wednesday, November 19, 2014 2:45 PM
Points: 1,080, Visits: 3,170
Hi

The following recursive option might work. It walks up and down from the queried invoice and joins the results.
DECLARE @invoiceID int = 3

;with rListUp as (
select a.invoiceid invoiceid, a.invoiceid currentid, a.bookingid, b.invoiceid nextinvoiceid
from #IDs a
CROSS APPLY (SELECT invoiceid, bookingid FROM #IDs m WHERE m.bookingid = a.bookingid ) b
where b.invoiceid > a.invoiceid
union all
select a.invoiceid, a.nextinvoiceid, a.bookingid, c.invoiceid
from rListUp a
CROSS APPLY (SELECT l.invoiceid, l.bookingid FROM #IDs l WHERE l.invoiceID = a.nextinvoiceid) b
CROSS APPLY (SELECT m.invoiceid, m.bookingid FROM #IDs m WHERE m.bookingid = b.bookingid and m.invoiceid > a.nextinvoiceid ) c
),
rListDown as (
select a.invoiceid invoiceid, a.invoiceid currentid, a.bookingid, b.invoiceid nextinvoiceid
from #IDs a
CROSS APPLY (SELECT invoiceid, bookingid FROM #IDs m WHERE m.bookingid = a.bookingid ) b
where b.invoiceid < a.invoiceid
union all
select a.invoiceid, a.nextinvoiceid, a.bookingid, c.invoiceid
from rListDown a
CROSS APPLY (SELECT l.invoiceid, l.bookingid FROM #IDs l WHERE l.invoiceID = a.nextinvoiceid) b
CROSS APPLY (SELECT m.invoiceid, m.bookingid FROM #IDs m WHERE m.bookingid = b.bookingid and m.invoiceid < a.nextinvoiceid ) c
),
rList AS (
SELECT invoiceid, nextinvoiceid FROM rListUp
UNION
SELECT invoiceid, nextinvoiceid FROM rListDown
)
select invoiceid, bookingid
from #IDs
where invoiceid in (
select nextinvoiceid from rlist where invoiceID = @InvoiceID
union
select @InvoiceID
)

It could probably be prettied up a bit more and there is still a chance that recursion limits will get hit if there is a long change of invoice/bookings


Post #1390944
Posted Thursday, November 29, 2012 11:23 PM


Hall of Fame

Hall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of Fame

Group: General Forum Members
Last Login: Thursday, November 20, 2014 7:58 PM
Points: 3,422, Visits: 5,366
mickyT (11/29/2012)
dwain.c (11/29/2012)
To all who participated in this thread:

You may wish to review this new article:
http://www.sqlservercentral.com/articles/String+Manipulation/94365/

It provides a good utility function for solving this case and many other similar ones. Thanks to the OP for being the inspiration for the article!

Thanks Dwain

I've already had a look at it and I am going to have a really good read through it soon. Even though I haven't had a chance to dig into the functionality and digest it properly I was impressed with the methods you came up with. Great article


Thanks for noticing and reading it, and the praise!

By all means leave some comments in the discussion thread and don't forget to rate the article!



My mantra: No loops! No CURSORs! No RBAR! Hoo-uh!

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?
Since random numbers are too important to be left to chance, let's generate some!
Learn to understand recursive CTEs by example.
Splitting strings based on patterns can be fast!
Post #1391042
Posted Thursday, November 29, 2012 11:25 PM


Hall of Fame

Hall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of Fame

Group: General Forum Members
Last Login: Thursday, November 20, 2014 7:58 PM
Points: 3,422, Visits: 5,366
Hi Phil - allow me to propose something for you.

DECLARE @RowCount INT
DECLARE @IDs TABLE
(InvoiceId int not null
,BookingId int not null)

INSERT INTO @IDs
SELECT InvoiceID, BookingID
FROM #IDs
WHERE InvoiceID = 1
SET @RowCount = @@ROWCOUNT

WHILE @RowCount <> 0
BEGIN
INSERT INTO @IDs
SELECT a.InvoiceID, a.BookingID
FROM #IDs a
INNER JOIN @IDs b ON a.BookingID = b.BookingID
UNION ALL
SELECT a.InvoiceID, a.BookingID
FROM #IDs a
INNER JOIN @IDs b ON a.InvoiceID = b.InvoiceID
EXCEPT
SELECT a.InvoiceID, a.BookingID
FROM @IDs a
SET @RowCount = @@ROWCOUNT
END

SELECT * FROM @IDs


I think this resolves the original and the alternate data setup (from Kraig?) properly. As it turns out, I recently solved an problem quite similar to this and this solution has its basis in that.

Not to disappoint you Alan (as this uses a loop), it is at least a set-based loop and in the similar problem I solved any attempt at a recursive solution did not perform nearly as well. I have not done that testing here so I can't say for sure whether it will be faster or not.

The other advantage to this approach is that it eliminates feedback loops which will completely disintegrate any effort to use a rCTE.

Let me know of any cases it doesn't resolve. It is possible that another UNION ALL amidst the loop will take care of it.



My mantra: No loops! No CURSORs! No RBAR! Hoo-uh!

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?
Since random numbers are too important to be left to chance, let's generate some!
Learn to understand recursive CTEs by example.
Splitting strings based on patterns can be fast!
Post #1391044
Posted Thursday, November 29, 2012 11:27 PM


Hall of Fame

Hall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of Fame

Group: General Forum Members
Last Login: Thursday, November 20, 2014 7:58 PM
Points: 3,422, Visits: 5,366
Post deleted - SSC hung and posted this one to the wrong thread.




My mantra: No loops! No CURSORs! No RBAR! Hoo-uh!

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?
Since random numbers are too important to be left to chance, let's generate some!
Learn to understand recursive CTEs by example.
Splitting strings based on patterns can be fast!
Post #1391050
« Prev Topic | Next Topic »

Add to briefcase ««1234»»»

Permissions Expand / Collapse