Generating n-Tuples with SQL

  • Dwain Camps

    SSC Guru

    Points: 86873

    Comments posted to this topic are about the item Generating n-Tuples with SQL


    My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]

    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?[/url]
    Since random numbers are too important to be left to chance, let's generate some![/url]
    Learn to understand recursive CTEs by example.[/url]
    [url url=http://www.sqlservercentral.com/articles/St

  • Paul White

    SSC Guru

    Points: 150341

  • Dwain Camps

    SSC Guru

    Points: 86873

    SQL Kiwi (5/16/2012)


    Craig Freedman has a couple of great posts covering how recursive CTEs work:

    http://blogs.msdn.com/b/craigfr/archive/2007/10/25/recursive-ctes.aspx

    http://blogs.msdn.com/b/craigfr/archive/2007/11/07/recursive-ctes-continued.aspx

    Thanks. I'm always looking to expand my knowledge in this area.

    BTW. Someone recently linked me to (I believe it was) your article on the recursive CTE version of a really fast DISTINCT. Great job there!


    My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]

    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?[/url]
    Since random numbers are too important to be left to chance, let's generate some![/url]
    Learn to understand recursive CTEs by example.[/url]
    [url url=http://www.sqlservercentral.com/articles/St

  • Paul White

    SSC Guru

    Points: 150341

    dwain.c (5/16/2012)


    BTW. Someone recently linked me to (I believe it was) your article on the recursive CTE version of a really fast DISTINCT. Great job there!

    Thank you (though it was just a forum post rather than an article).

  • Dwain Camps

    SSC Guru

    Points: 86873

    SQL Kiwi (5/16/2012)


    dwain.c (5/16/2012)


    BTW. Someone recently linked me to (I believe it was) your article on the recursive CTE version of a really fast DISTINCT. Great job there!

    Thank you (though it was just a forum post rather than an article).

    Clearly with that kind of impressive performance gain, it should have been an article!


    My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]

    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?[/url]
    Since random numbers are too important to be left to chance, let's generate some![/url]
    Learn to understand recursive CTEs by example.[/url]
    [url url=http://www.sqlservercentral.com/articles/St

  • chris.stuart

    SSCarpal Tunnel

    Points: 4965

    I always enjoy reading the articles, but this one got me a bit stumped. Where would you actually use this?:unsure:

  • Jeff Moden

    SSC Guru

    Points: 994284

    SQL Kiwi (5/16/2012)


    Craig Freedman has a couple of great posts covering how recursive CTEs work:

    http://blogs.msdn.com/b/craigfr/archive/2007/10/25/recursive-ctes.aspx

    http://blogs.msdn.com/b/craigfr/archive/2007/11/07/recursive-ctes-continued.aspx

    I do wish folks would do a comparison against the equivalent While Loops to see just how bad recursion can actually be for reads and CPU.

    --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.
    "If you think its expensive to hire a professional to do the job, wait until you hire an amateur."--Red Adair
    "Change is inevitable... change for the better is not."
    When you put the right degree of spin on it, the number 3|8 is also a glyph that describes the nature of a DBAs job. 😉

    Helpful Links:
    How to post code problems
    Create a Tally Function (fnTally)

  • Paul White

    SSC Guru

    Points: 150341

    Jeff Moden (5/17/2012)


    SQL Kiwi (5/16/2012)


    Craig Freedman has a couple of great posts covering how recursive CTEs work:

    http://blogs.msdn.com/b/craigfr/archive/2007/10/25/recursive-ctes.aspx

    http://blogs.msdn.com/b/craigfr/archive/2007/11/07/recursive-ctes-continued.aspx

    I do wish folks would do a comparison against the equivalent While Loops to see just how bad recursion can actually be for reads and CPU.

    I must confess I am a little unsure how your comment relates to the post you quoted. Dwain expressed an interest (at the end of the article) in finding out more about how recursive CTEs work ("Now if I can only figure out how these pesky recursive CTEs really work, then I could post something really interesting!") so I pointed him to the best reference I know of.

  • Jeff Moden

    SSC Guru

    Points: 994284

    Sorry... the way my comment relates to the articles you cited and to Dwaine's article is that, while recursion is a mathematically sound way of expressing a problem, none of them explain that the use of recursive CTEs is usually not a good way to solve the problem either performance wise or resource usage wise simply because of the way SQL Server does the recursion. I'd like to see folks start to take a little responsibility in that area by doing a resource usage and performance comparison between the rCTE's and the equivalent While Loops.

    --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.
    "If you think its expensive to hire a professional to do the job, wait until you hire an amateur."--Red Adair
    "Change is inevitable... change for the better is not."
    When you put the right degree of spin on it, the number 3|8 is also a glyph that describes the nature of a DBAs job. 😉

    Helpful Links:
    How to post code problems
    Create a Tally Function (fnTally)

  • Paul White

    SSC Guru

    Points: 150341

    Jeff Moden (5/17/2012)


    Sorry... the way my comment relates to the articles you cited and to Dwaine's article is that, while recursion is a mathematically sound way of expressing a problem, none of them explain that the use of recursive CTEs is usually not a good way to solve the problem either performance wise or resource usage wise simply because of the way SQL Server does the recursion. I'd like to see folks start to take a little responsibility in that area by doing a resource usage and performance comparison between the rCTE's and the equivalent While Loops.

    It still seems that your issues are more with the author (and Craig Freedman) rather than me. I'm not sure if a more efficient WHILE-based solution is possible here; I was simply responding to the request for more details about how recursive CTEs actually work. Perhaps Dwain will respond to explain why a comparison with WHILE was not done.

    For what it's worth, I have never had to produce the sort of result shown in the article, but if I did, I might try to find a bit-position T-SQL solution, or perhaps write a solution in a language more suited to high-performance iteration (one of the CLR ones).

  • Dwain Camps

    SSC Guru

    Points: 86873

    chris.stuart (5/17/2012)


    I always enjoy reading the articles, but this one got me a bit stumped. Where would you actually use this?:unsure:

    Oh my! So it's practical that you seek.

    In my case, I had a finite set of events and I needed to know the all the possible combinations of those events that could occur regardless of sequencing and without recurrance. A separate problem (much easier to solve incidentally in a set-based fashion) was to find out which events had actually occurred.

    Another example would be a grocer who wishes to assemble for sale gift baskets consisting of various combinations of items that fall within a total cost range (so that he can sell the basket for a specific price and a profit margin). All you need to do is add your cost column and limit the results to those combinations that meet the combined cost criteria. Or add additional criteria to consider number of items (e.g., no less than 6) or cost/profit balancing.

    Or how about a more fun example? I am a thief and I've just entered a vault filled with valuable antiques. My cunning thief-like brain can easily establish the intrinsic value of each of these items (or at least amount that I know my cheap fence will pony up) but alas, my knapsack (and my old weary bones) can carry no more than a certain weight of items. My task is to steal the highest value of booty that I can carry out of there. Yes! The classic knapsack problem of dynamic programming. Assign your weight and value to each of the products and you can use this solution to solve the problem in a brute force fashion (assuming of course that there aren't too many items to choose from).

    These are examples of classic allocation problems and of course, this isn't the dynamic programming solution to this particular problem, but we'll have to leave that for another day.

    And yes, Jeff these solutions probably aren't the fastest solutions out there. The chalenge is to solve an intrinsically procedural solutions with a declarative program. And when recursive approaches exist, it is often possible to do so with a recursive CTE. (I know, just because something can be done doesn't mean that it should be done).

    Consider though that solutions of this nature are not likely to be running in production nightly. They're more often one-offs.

    And most of all, thanks for taking the time to take a look and share your thoughts!


    My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]

    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?[/url]
    Since random numbers are too important to be left to chance, let's generate some![/url]
    Learn to understand recursive CTEs by example.[/url]
    [url url=http://www.sqlservercentral.com/articles/St

  • Steph Locke

    SSCrazy

    Points: 2857

    chris.stuart (5/17/2012)


    I always enjoy reading the articles, but this one got me a bit stumped. Where would you actually use this?:unsure:

    ditto

    The query is neat and some mention to A's was made so perhaps it's trying to solve some text combinatorics issue.

    I tend to store things away in my head against a use to which I might put the knowledge to one day so it would be helpful to understand a practical application to generating non-unique combinations.

    Could you describe what the problem was you solved with this?

    Edit: cheers for the above post - I dithered over my post too long and didn't see that you'd already done what I was asking for 🙂

  • Jeff Moden

    SSC Guru

    Points: 994284

    SQL Kiwi (5/17/2012)


    It still seems that your issues are more with the author (and Craig Freedman) rather than me.

    Correct. I didn't mean to make it sound like I was pointing at you. I just quoted your entry so that folks would know which articles I was talking about.

    I'm not sure if a more efficient WHILE-based solution is possible here; I was simply responding to the request for more details about how recursive CTEs actually work. Perhaps Dwain will respond to explain why a comparison with WHILE was not done.

    Again... apologies but you weren't meant to be the target here. Shifting gears, just changing it to a While Loop using the exact same logic will make it more efficient. Since a lot of folks don't seem to realize that, perhaps yet another article on the "hidden RBAR" aspect of many types of rCTE's (not just rCTE's that count) is in order.

    For what it's worth, I have never had to produce the sort of result shown in the article, but if I did, I might try to find a bit-position T-SQL solution...

    Ditto that.

    --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.
    "If you think its expensive to hire a professional to do the job, wait until you hire an amateur."--Red Adair
    "Change is inevitable... change for the better is not."
    When you put the right degree of spin on it, the number 3|8 is also a glyph that describes the nature of a DBAs job. 😉

    Helpful Links:
    How to post code problems
    Create a Tally Function (fnTally)

  • Dwain Camps

    SSC Guru

    Points: 86873

    Jeff Moden (5/17/2012)


    SQL Kiwi (5/17/2012)


    It still seems that your issues are more with the author (and Craig Freedman) rather than me.

    ... apologies but you weren't meant to be the target here.

    Ditto that.

    I get it! Change RBAR in your avatar to Dwain.C and there you have it.

    Seriously, I'm smiling (:-D) because I figure that if I can stir up the emotions of the staunchly rigid and proper SQL aristocracy then I've done my job.

    Now waiting to be honored to have CELKO to take a run at me.


    My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]

    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?[/url]
    Since random numbers are too important to be left to chance, let's generate some![/url]
    Learn to understand recursive CTEs by example.[/url]
    [url url=http://www.sqlservercentral.com/articles/St

  • Jesse McLain

    SSCommitted

    Points: 1784

    chris.stuart (5/17/2012)


    I always enjoy reading the articles, but this one got me a bit stumped. Where would you actually use this?:unsure:

    I used this method in an algorithm to identify unique keys in raw data: http://www.sqlservercentral.com/scripts/T-SQL/62086/

    (I tried to include the link as IFCode, but it didn't work properly.)

Viewing 15 posts - 1 through 15 (of 52 total)

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