Bin packing part 3: Need for speed

In the first post of this series, I explained the bin-packing problem and established a baseline solution. The second post investigated ways to increase the packing efficiency. In none of these posts did I pay particular attention to performance – and frankly, it shows. Performance of all solutions presented thus far sucks eggs. Time to see what can be done about that. If you look in detail at the most efficient solution so far (dbo.OrderDesc, as described in the second post of the series), you’ll see that all 40,000 registrations are processed one by one, with a cursor. No surprise…
Read More

Bin packing part 2: Packing it tighter

No Comments
In my previous post, I explained the bin packing problem, explained an example scenario, and established a baseline for both speed and efficiency of bin packing algorithms by writing a rather crude cursor-based procedure. In this part, I will look at some small modifications that can be made to this code to make it better at packing bins as full as possible, so that less bins will be needed. Reordering the cursor The Baseline procedure didn’t process the registrations in any particular order. Granted, there is an ORDER BY Year, Quarter in the cursor declaration, but that is only needed…
Read More

Bin packing part 1: Setting a baseline

No Comments
Some problems can only be solved by brute-forcing every possible combination. The problem with such an approach, is that execution time grows exponentially as the amount of input data grows – so that even on the best possible hardware, you will get inacceptable performance once the input data goes beyond the size of a small test set. These problems are called “NP-complete” or “NP-hard”, and the most viable way to deal with them is to use an algorithm that finds a solution that, while not perfect, is at least good enough – with a performance that, while not perfect, is…
Read More

Poor men see sharp – more cursor optimization

After making my post on cursor optimization I received some comments that triggered me to do some further investigation. Adam Machanic wrote in my blog’s comments that using SQLCLR to loop over a SqlDataReader would be much faster than any T-SQL based cursor. And Erland Sommarskog wrote in a usenet thread that he has some colleagues who think that a “poor man’s cursor” is always better than a real cursor. So I decided to give these options a try and see what comes out in a real test. I simply reused the test cases I had already used for testing…
Read More

Curious cursor optimization options

The best way to optimize performance of a cursor is, of course, to rip it out and replace it with set-based logic. But there is still a small category of problems where a cursor will outperform a set-based solution. The introduction of ranking functions in SQL Server 2005 has taken a large chunk out of that category – but some remain. For those problems, it makes sense to investigate the performance effects of the various cursor options. I am currently preparing a series of blog posts on a neat set-based solution I found for a problem that screams “cursor” from…
Read More

So-called “exact” numerics are not at all exact!

Attempting to dispel myths tends to make me feel like Don Quixote, riding against hordes of windmills that won’t budge. In this case, even some of my fellow MVPs and Microsoft’s own Books Online are among the windmills… Books Online says that there are two categories of numeric data types: “approximate” (float and real), and “exact” (all others, but for this discussion mainly decimal and numeric). It also says that “floating point data is approximate; therefore, not all values in the data type range can be represented exactly”, thereby suggesting that other numeric data types are capable of representing all…
Read More

How NOT to pass a lot of parameters

Did you know that SQL Server allows stored procedures to have up to 2100 parameters? And more important: do you care? Well, some people do care, and Joe Celko seems to be one of them. If you are a regular reader of SQL Server newsgroups, you probably know Joe Celko from his always unfriendly and often incorrect replies. Here is a typical example, one that I have seen several times recently, in a paraphrased form: Question: I want to send a list of values to my stored procedure, but WHERE ColumnName IN (@ValueList) does not work – how to solve…
Read More

What if null if null is null null null is null?

In this fourth and final part in my series about NULL, I’ll discuss some well-known and some less well-known functions and keywords that are specifically created to deal with NULL values. And I will, of course, explain why null if null is null null null is null. In case you have not yet read them, you can click these links to read the first, second, and third part.   IS NULL is not = NULL   I have already explained why tests for equality with NULL will always return Unknown instead of True or False. This holds true in all…
Read More

Dr. Unknown, or how I learned to stop worrying and love the NULL

Two months ago, I posted the first two parts of a series about NULL. After that, I went quiet. Much to do and little time was one excuse. But to be honest, I also lost interest. However, I felt I owe my readers to conclude the series, so I have now forced myself to write and publish the last parts before moving on to more interesting subjects J.   Before reading on, I suggest that you first read (or reread) the first and second part of this series, so that we’re all on the same level again.   Finished reading?…
Read More

Upcoming speaking events

I know I’ve been neglecting my blog lately, but I at least have a valid excuse this time. Four weeks ago, I received two emails on a single day, both inviting me to speak at two different Dutch events that will be held in the same week.   I replied “yes” to both mails, and since have been preparing my sessions. For those readers who would like to catch me speaking, I’ll give the details below.   For the “Software Developer Conference 2007”, to be held in Arnhem, the Netherlands on the 17th and 18th of September, I’ll deliver two…
Read More

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.