A Solution for the Bin Packing Problem

  • Comments posted to this topic are about the item A Solution for the Bin Packing Problem

  • This is an interesting approach, however I feel constrained to point out that because of the recursive CTE, this isn't completely set-based. If I get some free time, I'd like to see if it's possible to use a tally table in this solution for a truly set-based solution. It also occurred to me that with a few tweaks this could be used to help with room assignments at SQL Saturday events!

  • First, and to be sure, I always appreciate anyone that steps up to the plate with an article, especially on such a topic.

    I agree with Aaron.  This is NOT a "Set-Based" solution because incremental rCTEs (recursive CTEs) are NOT "Set-Based".  The bit of code that makes this rCTE "incremental" is the following code snippet from the "C1" CTE...

    from #regs Regs
    inner join C1 on Regs.Rn = C1.Rn + 1

    In many cases, a properly written WHILE loop can beat an incremental rCTE while using a whole lot less resources in the form of logical reads.

    I also don't actually know if this code does a good job at how it does the packing.  That's not to say that it's doing a bad job but I look at this and can't say it's actually doing a good job, either.  That will take a bit more scrutiny.

    As a suggestion, the table output that you have in the article doesn't match the output from the code.  It will provide less confusion to your readers if it does.

    As a general observation (lots of other authors end up doing the same) and another suggestion, it doesn't instill a whole lot of faith in an author when they talk about having a created a set based solution and then they use a WHILE loop to build the test data.

    Just to reiterate, though, thank you.  I appreciate that you took the time to write and publish this article.  I'll echo Aaron's statement that this IS an interesting approach and the article has gotten people's creative juices flowing.

    --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".
    "Dear Lord... I'm a DBA so please give me patience because, if you give me strength, I'm going to need bail money too!"

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

  • Nice article.

    R Glen Cooper

  • Thanks you Jeff for your accurate post; I will keep your observations in mind and I will consider them in they more general meaning. At the moment I am going to remove the inaccuracy related to the 'set-based' word in order to not give a wrong information to future readers.

  • Alessandro Mortola wrote:

    Thanks you Jeff for your accurate post; I will keep your observations in mind and I will consider them in they more general meaning. At the moment I am going to remove the inaccuracy related to the 'set-based' word in order to not give a wrong information to future readers.

    Ok, Alessandro... it's not for me to judge but you've just impressed the hell out of me.  That's both thoughtful and incredibly responsible of you.  My hat is off to you, good Sir!

    As a bit of a side bar and although it doesn't show an example of beating an rCTE with a well written WHILE loop, you might want to have a look at the following article on the "Hidden RBAR" nature of rCTEs.  The differences between some of the other methods and the rCTE method for the simple act of "counting" will amaze you (disclaimer... I've not run the same tests recently but I now have the incentive to).

    https://www.sqlservercentral.com/articles/hidden-rbar-counting-with-recursive-ctes

    Do note that I'm not implying that ALL rCTEs are bad.  As with anything else in T-SQL, "It Depends" but rCTEs that are incremental (have a counter in them, usually incrementing by 1) are usually a very bad thing.  I also don't justify using such bad code just because of small row counts.  You'll see that in the article where I talk about the graph that has the "red rocket" in it.

    --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".
    "Dear Lord... I'm a DBA so please give me patience because, if you give me strength, I'm going to need bail money too!"

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

Viewing 6 posts - 1 through 6 (of 6 total)

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