Search results matching tags 'Performance' and 'clr'

Splitting a list of integers : another roundup

AaronBertrand — Wed, 07 Jul 2010 21:35:00 GMT

Last August, I wrote a lengthy post about how I handle splitting up a list of integers that are passed into a procedure as a comma-separated list.

I am still using this method today. But since almost a year has passed, and because there have been plenty of articles written about splitting in the meantime, I've decided to try out a couple of other methods -- to make sure I was still doing "the right thing." First I wanted to test out Adam Machanic's CLR approach. I also took a great interest to the XML splitting methods publicized via a T-SQL tennis match between MVPs Brad Schulz and Adam Haines (part I and part II). And I wanted to test Peter Larsson's derived table approach. I also thought it only fair to compare a few of the methods I've used in the past before coming across these faster and/or more scalable solutions, if for nothing else, to illustrate how far we've come.

I'm not going to revisit why you may want to process a list of integers instead of handling each integer individually. I'm going to assume that, like me, you have cases where you simply don't know how many values might be passed in a parameter list... causing you to ditch the approach by Celko where he has n individual parameters so he can enjoy type safety at the cost of code that is long and horribly hard to maintain (see one of his illogical rants on this).

The Functions

First, I will outline the 9 methods I'm going to compare, in no particular order:

RBAR 1

This is the solution I see most often out in the wild. What does RBAR mean? "Row by agonizing row." I'm not sure where I first picked up that term, but because it sounds so much like "FUBAR," I really like it. While most solutions do use loops of some sort, this is the worst kind... take a chunk off the list, do some stuff with it, insert it into the table, assign a new value to the list, then move on to the next part of the list. Here is the function:

CREATE FUNCTION dbo.SplitInts_RBAR_1
(
   @List       VARCHAR(MAX),
   @Delimiter  CHAR(1)
)
RETURNS @Items TABLE
(
   Item INT
)
AS
BEGIN
   DECLARE
       @Item VARCHAR(12),
       @Pos  INT;

   WHILE LEN(@List)>0
   BEGIN
       SET @Pos = CHARINDEX(@Delimiter, @List);

       IF @Pos = 0
           SET @Pos = LEN(@List)+1;

       SET @Item = LEFT(@List, @Pos-1);

       INSERT @Items SELECT CONVERT(INT, LTRIM(RTRIM(@Item)));

       SET @List = SUBSTRING(@List, @Pos + LEN(@Delimiter), LEN(@List));
       
       IF LEN(@List) = 0 BREAK;
   END
   RETURN;
END

RBAR 2

This is a very slight variation on RBAR1 (can you spot the differences?), but results in about twice as many reads when just outputting the data (the reads are roughly the same when using the data for more practical purposes, like joining with existing tables). For those wishing to stick with RBAR for whatever reason (remember what it sounds like), you may want to compare RBAR 1 and RBAR 2 and see if you can ensure that your functions are not suffering from performance problems you might not know about.

CREATE FUNCTION dbo.SplitInts_RBAR_2
(
   @List      VARCHAR(MAX),
   @Delimiter CHAR(1)
)
RETURNS @Items TABLE
(
   Item INT
)
AS
BEGIN
   DECLARE 
       @Item VARCHAR(12),
       @Pos  INT;
       
   SELECT @Pos = 1;
    
   WHILE @Pos > 0
   BEGIN
       SELECT @Pos = CHARINDEX(@Delimiter, @List);

       IF @Pos > 0
           SELECT @Item = LEFT(@List, @Pos - 1);
       ELSE
           SELECT @Item = @List;
           
       INSERT @Items SELECT CONVERT(INT, LTRIM(RTRIM(@Item)));
       
       SELECT @List = RIGHT(@List, LEN(@List) - @Pos);

       IF LEN(@List) = 0 BREAK;
   END
   
   RETURN;
END

CTE 1

This function uses a recursive CTE, with the first element and the remainder functioning as the anchor query, whittling down each element in turn. It inserts into the @table variable until you reach the last element.

CREATE FUNCTION dbo.SplitInts_CTE_1
(
   @List       VARCHAR(MAX),
   @Delimiter  CHAR(1)
)
RETURNS @Items TABLE
(
   Item INT
)
AS
BEGIN
   WITH ints(item, remainder)
   AS
   (
       SELECT item   = SUBSTRING(@List, 1, CHARINDEX(@Delimiter, @List)-1),
           remainder = LTRIM(RTRIM(SUBSTRING(@List, CHARINDEX(@Delimiter, @List) + 1,
                       LEN(@List))))
       UNION ALL
       SELECT item   = SUBSTRING(remainder, 1, CHARINDEX(@Delimiter, remainder)-1),
           remainder = LTRIM(RTRIM(SUBSTRING(remainder, CHARINDEX(@Delimiter, remainder) + 1, 
                       LEN(remainder))))
           FROM ints
           WHERE CHARINDEX(@Delimiter, remainder) > 0
   )
   INSERT @Items SELECT item FROM ints
   OPTION (MAXRECURSION 0);
   
   RETURN;
END

CTE 2

This function is similar to the above recursive query, however it uses the positions in the string and fewer LEN() calls to extract each value.

CREATE FUNCTION dbo.SplitInts_CTE_2
(
   @List       VARCHAR(MAX),
   @Delimiter  CHAR(1)
)
RETURNS @Items TABLE (Item INT)
AS
BEGIN
   DECLARE @Len INT = LEN(@List) + 1;

   WITH a AS
   (
       SELECT
           [start] = 1,
           [end]   = COALESCE(NULLIF(CHARINDEX(@Delimiter, @List, 1), 0), @Len),
           [value] = LTRIM(RTRIM(SUBSTRING(@List, 1, 
                     COALESCE(NULLIF(CHARINDEX(@Delimiter, @List, 1), 0), @Len)-1)))
       UNION ALL
       SELECT
           [start] = CONVERT(INT, [end]) + 1,
           [end]   = COALESCE(NULLIF(CHARINDEX(@Delimiter, @List, [end] + 1), 0), @Len),
           [value] = LTRIM(RTRIM(SUBSTRING(@List, [end] + 1, 
                     COALESCE(NULLIF(CHARINDEX(@Delimiter, @List, [end] + 1), 0), @Len)-[end]-1)))
       FROM a
       WHERE [end] < @len
   )
   INSERT @Items SELECT [value]
   FROM a
   WHERE LEN([value]) > 0
   OPTION (MAXRECURSION 0);

   RETURN;
END

Numbers

This is the solution I am currently using in my production instances of SQL Server 2005 and SQL Server 2008. It uses a numbers table and, up until this week, was the fastest method I had tested to date.

CREATE FUNCTION dbo.SplitInts_Numbers
(
   @List       VARCHAR(MAX),
   @Delimiter  CHAR(1)
)
RETURNS TABLE
AS
   RETURN
   (
       SELECT
           Item = CONVERT(INT, LTRIM(RTRIM(
               SUBSTRING(@List, Number,
               CHARINDEX(@Delimiter, @List + @Delimiter, Number) - Number))))
       FROM
           dbo.Numbers WITH (NOLOCK)
       WHERE
           Number <= CONVERT(INT, LEN(@List))
           AND SUBSTRING(@Delimiter + @List, Number, 1) = @Delimiter
   );

Inline 1

This is a similar approach to the numbers table solution (first spotted as written by Peso but with some minor adjustments), without requiring access to a numbers table. This does populate a local table variable in the body of the function, in order to make use of a less complex CTE to generate a sufficient set of integers.

CREATE FUNCTION dbo.SplitInts_Inline_1
(
   @List       VARCHAR(MAX),
   @Delimiter  CHAR(1)
)
RETURNS @Items TABLE
(
   Item INT
)
AS
BEGIN
   WITH v0 AS
       (
           SELECT n = 0 
           UNION ALL SELECT 1
           UNION ALL SELECT 2
           UNION ALL SELECT 3
           UNION ALL SELECT 4
           UNION ALL SELECT 5
           UNION ALL SELECT 6
           UNION ALL SELECT 7
           UNION ALL SELECT 8
           UNION ALL SELECT 9
           UNION ALL SELECT 10
           UNION ALL SELECT 11
           UNION ALL SELECT 12
           UNION ALL SELECT 13
           UNION ALL SELECT 14
           UNION ALL SELECT 15
       ),
       v1 AS ( SELECT 16 * v0.n AS n FROM v0 ),
       v2 AS ( SELECT 256 * v0.n AS n FROM v0 ),
       v3 AS ( SELECT 4096 * v0.n AS n FROM v0 ),
       v4 AS ( SELECT 65536 * v0.n AS n FROM v0 WHERE n < 2 )
   INSERT @Items    
   SELECT Item = CONVERT(INT, (SUBSTRING(@Delimiter + @List + @Delimiter, 
       w.n + 1, CHARINDEX(@Delimiter, @Delimiter + @List + @Delimiter, w.n + 1) - w.n - 1)))
   FROM
   (
       SELECT n = v0.n + v1.n + v2.n + v3.n + v4.n
           FROM v0, v1, v2, v3, v4
   ) AS w
   WHERE w.n = CHARINDEX(@Delimiter, @Delimiter + @List + @Delimiter, w.n)
   AND w.n < LEN(@Delimiter + @List);
   
   RETURN;
END

Inline 2

Similar to the one above, but this time without the local table variable. You'll see that a lot more numbers had to be hard-coded into the function definition, but this will potentially pay off in terms of reads (stay tuned).

CREATE FUNCTION dbo.SplitInts_Inline_2
(
   @List       VARCHAR(MAX),
   @Delimiter  CHAR(1)
)
RETURNS TABLE
AS
   RETURN
   (
       SELECT Item = CONVERT(INT, (SUBSTRING(
           @Delimiter + @List + @Delimiter, 
           w.n + 1,
           CHARINDEX(@Delimiter, @Delimiter + @List + @Delimiter, w.n + 1) - w.n - 1
           )))
       FROM
       (

           SELECT n = v0.n + v1.n + v2.n + v3.n
               FROM  
               (
                   SELECT n = 0 
                   UNION ALL SELECT 1  UNION ALL SELECT 2  UNION ALL SELECT 3
                   UNION ALL SELECT 4  UNION ALL SELECT 5  UNION ALL SELECT 6
                   UNION ALL SELECT 7  UNION ALL SELECT 8  UNION ALL SELECT 9
                   UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL SELECT 12
                   UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL SELECT 15
               ) AS v0,
               (
                   SELECT n = 0 
                   UNION ALL SELECT 16  UNION ALL SELECT 32  UNION ALL SELECT 48
                   UNION ALL SELECT 64  UNION ALL SELECT 80  UNION ALL SELECT 96
                   UNION ALL SELECT 112 UNION ALL SELECT 128 UNION ALL SELECT 144
                   UNION ALL SELECT 160 UNION ALL SELECT 176 UNION ALL SELECT 192
                   UNION ALL SELECT 208 UNION ALL SELECT 224 UNION ALL SELECT 240
               ) AS v1,
               (
                   SELECT n = 0
                   UNION ALL SELECT 256  UNION ALL SELECT 512  UNION ALL SELECT 768 
                   UNION ALL SELECT 1024 UNION ALL SELECT 1280 UNION ALL SELECT 1536 
                   UNION ALL SELECT 1792 UNION ALL SELECT 2048 UNION ALL SELECT 2304
                   UNION ALL SELECT 2560 UNION ALL SELECT 2816 UNION ALL SELECT 3072
                   UNION ALL SELECT 3328 UNION ALL SELECT 3584 UNION ALL SELECT 3840
               ) AS v2,
               (
                   SELECT n = 0
                   UNION ALL SELECT 4096   UNION ALL SELECT 8192   UNION ALL SELECT 12288
                   UNION ALL SELECT 16384  UNION ALL SELECT 20480  UNION ALL SELECT 24576
                   UNION ALL SELECT 28672  UNION ALL SELECT 32768  UNION ALL SELECT 36864
                   UNION ALL SELECT 40960  UNION ALL SELECT 45056  UNION ALL SELECT 49152
                   UNION ALL SELECT 53248  UNION ALL SELECT 57344  UNION ALL SELECT 61440
                   UNION ALL SELECT 65536  UNION ALL SELECT 69632  UNION ALL SELECT 73728
                   UNION ALL SELECT 77824  UNION ALL SELECT 81920  UNION ALL SELECT 86016
                   UNION ALL SELECT 90112  UNION ALL SELECT 94208  UNION ALL SELECT 98304
                   UNION ALL SELECT 102400 UNION ALL SELECT 106496 UNION ALL SELECT 110592
                   UNION ALL SELECT 114688 UNION ALL SELECT 118784 UNION ALL SELECT 122880 
                   UNION ALL SELECT 126976 UNION ALL SELECT 131072 UNION ALL SELECT 135168
                   UNION ALL SELECT 139264 UNION ALL SELECT 143360 UNION ALL SELECT 147456
               ) v3
       ) w
       WHERE w.n = CHARINDEX(@Delimiter, @Delimiter + @List + @Delimiter, w.n)
       AND w.n < LEN(@Delimiter + @List)
   );

CLR

This was an adaptation of Adam Machanic's CLR approach (as mentioned above), with very minor modifications to return a table of integers instead of strings. I won't re-list his CLR function but will gladly share my modifications. You may want to play with Erland's CLR version as well, which is a lot more straightforward and will potentially scale equally well, at least to moderately-sized strings. Here is the wrapper to the function (I created a StringHelper.dll with several user-defined functions, including SplitInts()):

CREATE FUNCTION dbo.SplitInts_CLR
(
   @List       NVARCHAR(MAX),
   @Delimiter  CHAR(1)
)
RETURNS TABLE
(
   Item INT
)
EXTERNAL NAME [StringHelper].[UserDefinedFunctions].[SplitInts];
GO

XML

Again, this solution was thrown into the mix due to some heavy touting and promise indicated by Brad Schulz. I've always been wary of XML solutions for splitting / concatenating because of the overhead of constructing and deconstructing the XML around the data. Soon we'll see if my concerns are justified.

CREATE FUNCTION dbo.SplitInts_XML
(
   @List       VARCHAR(MAX),
   @Delimiter  CHAR(1)
)
RETURNS TABLE
AS
   RETURN 
   (
       SELECT Item = CONVERT(INT, Item)
       FROM
       (
           SELECT Item = x.i.value('(./text())[1]', 'INT')
           FROM
           (
               SELECT [XML] = CONVERT(XML, '<i>' 
                    + REPLACE(@List, @Delimiter, '</i><i>') 
                    + '</i>').query('.')
           ) AS a
           CROSS APPLY
           [XML].nodes('i') AS x(i)
       ) AS y
       WHERE Item IS NOT NULL
   );

I'm leaving out error handling for brevity, and I'm also leaving out any validation that the list consists of only integers -- I'm going to assume that you can perform that kind of checking much more efficiently in your application code, and can add it to the T-SQL side if you see fit. I'm also not worrying at this stage about removing duplicates or about preserving the order that the values were originally defined in the list.

Finally, I wanted to ensure that each solution could handle 50,000 entries in the list; since your needs may be a lot more modest than this, you may want to pare down your entries to improve performance (for example, you don't need as many entries in "Inline 2", and your Numbers table can contain fewer rows - for some solutions, you'll need a numbers table covering 14 * <max number of elements> since an INT can be up to 12 digits and the comma and perhaps a space). In this situation, since I knew all of my values would be <= 2 characters and I didn't have any embedded spaces, I didn't really need a Numbers table quite so large, and I didn't really need to define so many permutations in the "Inline 2" function.

The Testing Process

First, since a few of the solutions require a numbers or tally table, I prepared the following table:

SET NOCOUNT ON;
DECLARE @UpperLimit INT;
SET @UpperLimit = 256000;

WITH n AS 
(
   SELECT x = 1 
   UNION ALL
   SELECT x = x + 1
     FROM n
     WHERE x < @UpperLimit
)
SELECT [Number] = x 
  INTO dbo.Numbers 
  FROM n
  WHERE x <= 256000
  OPTION (MAXRECURSION 0);
GO  
CREATE UNIQUE CLUSTERED INDEX n ON dbo.Numbers([Number]);

Then I started a trace with a filter of TextData LIKE '%dbo.SplitInts%' and with the following columns: TextData, Reads, Writes, CPU, Duration. Once the trace was running, I ran the following code block three times, giving me a good sample of how each solution performs:

DECLARE
   @List      VARCHAR(MAX) = '1,2,3,4,5,6,7,8,9,10,',
   @Delimiter CHAR(1)  = ',';

DECLARE c CURSOR LOCAL STATIC READ_ONLY FORWARD_ONLY FOR
   SELECT List FROM
   (
                 SELECT r = 1, List = REPLICATE(@List, 10)
       UNION ALL SELECT r = 2, List = REPLICATE(@List, 50)
       UNION ALL SELECT r = 3, List = REPLICATE(@List, 100)
       UNION ALL SELECT r = 4, List = REPLICATE(@List, 500)
       UNION ALL SELECT r = 5, List = REPLICATE(@List, 1000)
       UNION ALL SELECT r = 6, List = REPLICATE(@List, 2500)
       UNION ALL SELECT r = 7, List = REPLICATE(@List, 5000)
   ) AS x
   ORDER BY r;

OPEN c;

FETCH NEXT FROM c INTO @List;

WHILE @@FETCH_STATUS = 0
BEGIN
   SELECT Item FROM dbo.SplitInts_CLR      (@List, @Delimiter);
   SELECT Item FROM dbo.SplitInts_RBAR_1   (@List, @Delimiter);
   SELECT Item FROM dbo.SplitInts_RBAR_2   (@List, @Delimiter);
   SELECT Item FROM dbo.SplitInts_Numbers  (@List, @Delimiter);
   SELECT Item FROM dbo.SplitInts_XML      (@List, @Delimiter);
   SELECT Item FROM dbo.SplitInts_CTE_1    (@List, @Delimiter);
   SELECT Item FROM dbo.SplitInts_CTE_2    (@List, @Delimiter);
   SELECT Item FROM dbo.SplitInts_Numbers_1(@List, @Delimiter);
   SELECT Item FROM dbo.SplitInts_Numbers_2(@List, @Delimiter);
   
   FETCH NEXT FROM c INTO @List;
END

DEALLOCATE c;

I ran the test 10 times, then pulled averages from the trace tables for each function and element count.

The Results

In terms of duration, CLR won every time. Heck, CLR won every time in every category. (This might not come as a big surprise to you. After all, just yesterday, I let the cat out of the bag by declaring that I'd finally given in and am letting the CLR into my life.)

But if you are one of many who are not able to implement CLR functions in your production environments, you may want to pay attention to some of the other methods. In the chart below I've highlighted the winners and losers as follows: longest duration at each interval (red), shortest duration at each interval (light green), and the shortest duration other than CLR (even lighter green). Note that "CTE 1" for 50,000 elements, at over 26,000ms total duration, is way off the chart.

Duration, in milliseconds, for splitting delimited strings of varying numbers of elements

We can see that duration for the CLR method and a few others creep up very slowly, while several of the remaining methods increase at a much more rapid pace. There is also an inexplicable bump for the XML method at 500 and 1,000 elements, where duration is longer than found with 25,000 elements. I thought this may be an anomaly or due to other pressure on the box, but this was repeatable time and time again. We can see that the "CTE 1" method is the absolute worst performer at 5,000 rows and above, and that aside from the CLR method, the numbers table was the winner up to 10,000 elements; beyond that, the "Inline 2" method took over -- but granted, not by much.

As mentioned before, I examined reads, writes, CPU and duration to compare these different splitting techniques. CPU correlated almost identically to duration, so I'm not going to bother repeating a similar chart as above. Writes did not seem to factor in; the only method that performed any writes to speak of was the "CTE 1" function, and based on duration alone we are discarding that as an alternative in any case. Here are the reads (again I've highlighted the winners in green and the losers in red):

Logical reads, in 8K pages, for splitting delimited strings of varying numbers of elements

I didn't graph the reads because, due to the range of values involved, I'd have to do it logarithmically to even present it on your screen, and that would take away some of the "punch" you get with these numbers. :-)

What I've Learned

If you are going to be mainly dealing with < 100 items in your lists, then the difference between the various methods was so minuscule, it was not even worth mentioning the actual figures. Even at 1000 items, the only real loser was the XML method (even though the reads on the CTE methods might make you think otherwise). Once you get over 10,000 items in the list, you start to see a greater separation between the men and the boys; there is clearly a set of options that yield unacceptable performance, and a set of options that aren't all that different. To a large degree, the duration figures correlate almost directly to the reads, but even though several methods provide the same 0-level of reads, the CLR always wins in duration. You may nit-pick and find little things that will make various methods a little bit faster, but I don't think there is anything ground-breaking that will change any function's performance by an order of magnitude.

The major lessons to learn here are as follows:

You should test all available solutions both with varying numbers of parameters. In this case if I had tested only against a smaller list, I might have ended up with a solution that would have been a real performance problem should I need to deal with thousands of elements -- and without proper testing scenarios in place, this would most likely happen at an inconvenient time.
While this stands true for any type of performance test, I couldn't leave it out: If you are running tests on a local machine or a test server, you should test on the destination hardware as well, since there are many factors that could change performance in that environment. Without belaboring the point too much, I had slightly different results on a local machine with less RAM and fewer processors that might have led me in a different direction if I had been less thorough.
The usage of LEN() or DATALENGTH(), combined with using a @table variable inside the function to hold intermediate results, can increase the reads and overall duration in a major way; it is clear that certain functions above are not optimized for this type of implementation.

Conclusion

Based on these tests, I will be proceeding with introducing CLR functions to my primary systems to help with certain string functionality. For now, I will be limiting this to splitting, concatenation, parsing, and RegEx matching. For splitting specifically, as time goes on, we are introducing more and more bits of functionality that require accepting application data in a list (permissions, network associations, etc.), and I am looking only slightly ahead to a day where we will need to process thousands of items in some of these lists. While the overall duration and read savings compared to a numbers table was quite modest, centralizing this functionality for further extensibility and without the limitations of T-SQL UDFs seems to be a worthwhile investment to me.

Soon I hope to perform some tests revolving around file system access, since we have several C# command-line apps, as well as inline T-SQL using xp_cmdshell, all for the purpose of processing files. These files are almost always processed in the same type of way; the biggest difference is either the location or the purpose of the file.

10 lessons from 35K tps

Paul Nielsen — Thu, 13 Dec 2007 05:29:00 GMT

I’ve spent the last 6 months on a contract designing and developing a high transaction database – a couple orders of magnitude higher than the average OLTP SQL Server database. The SLA specified a hard transaction duration and the primary fetch feature required some complex business logic. That level of concurrency drives out a few lessons. Some reinforced what I already believed and some lessons were a surprise.

I’m under a strict NDA not to reveal the client or the industry, but I have permission to discuss some of the technology. Let me just say that if you live in the industrialized world, I’d bet $100 that your data has gone through this system at least once.

Lesson 1: At 35K tps, it’s difficult to configure a stable test or production platform. We had more trouble just getting the servers stable than we did developing the code. A good system administrator who knows how to properly configure every component in the network, server, routers, SAN is worth their weight in gold. And at this tps, don’t try iSCSI.

Lesson 2: We moved all the business logic into the database design and stored procedures to use set-based code. The middle tier was mostly a pass-through from the mainframe handling the manually partitioning and the connection pooling. The creative data-driven design allowed for flexibility and performed great.

Lesson 3: I developed both a denormalized and normalized version of the schema and the stored procedures using the same API. The denormalized version violated first normal form and repeated columns (part1, part2, part3, part4). It seemed like a reasonable idea at the time because a single clustered seek could fetch all the data without any other reads and the number of parts was fixed. However, several other descriptive columns were added for each “part”. The amount of code required to normalize the parts inside the proc, and the extra indexes, cost the denormalized solution, the result was that the normalized version actually out performed the denormalized version by several precious milliseconds. ("Ah, my Precious" said Gollum)

Lesson 4: When developing the upsert proc prior to tuning the indexes, I first trusted that the If Exists(Select…) line would fire for any item and would prohibit duplicates. Nada. In a short time there were thousands of duplicates because the same item would hit the upsert at the same millisecond and both transactions would see a not exists and perform the insert. After much testing the solution was to use the unique index, catch the error, and retry allowing the transaction to see the row and perform an update instead an insert.

Lesson 5: This app requires that several hundred “items” are passed into the stored procedure for processing as a set. I chose to input the data as comma delimited VarChar(max), originally using Erland’s iterative string2set function to parse string into a set inside the proc. It worked well enough. The plan was to substitute a CLR function near the end of development. When the time came, the CLR function ran blazingly fast on my notebook, but under stress it was painfully sloooooow. I didn’t understand at all why. This is exactly what we were told by Microsoft the CLR was for. Pass string data in, manipulate it, pass it back – no data access – sounds great right? In a few emails to my friend Adam, he told me he had the same issues a while back and the CLR simply couldn't keep up with the marshalling of the VarChar(max).

So back to the T-SQL function and time to make it faster. I switched to the Table of Numbers solution and found that with test data using many short strings (‘abc,qwe,wer,ert x9000) it out performed the iterative function by over 2x. But when double checking with our real data the iterative function ran faster by a magnitude. The reason was that our data has much longer strings, and the iterative solution quickly jumped to the next comma, cut the string and moved on.

Lesson 6: Agile iterative development with unit testing is a blast! During the development I maintained two scripts: one that created the database, tables, and procs, and a second one with test data and unit test calls. During the crunch of development, I would grasp the next 10-15% of the user requirements (some of which were a bit complex) and then build out those requirements. When it passed the tests and the client could see that it was working we moved on to the next level of complexity – rip it up and rebuild better and stronger with the next iteration. But then as the rush of development ended and it moved into integration testing, I had to conform to source code control. A file for every proc is a good thing for IT control, but it sure slowed down my development.

Lesson 7: At this transaction level the nonclustered indexes can get 97% fragmented in a day. Be very careful when choosing nonclustered indexes.

Lesson 8: The code went through several rounds of fine tuning and searching for ways to reduce any millisecond possible. The overall distribution of my time was about ½ design and code, ¼ unit testing, and ¼ integration and performance testing/tuning.

Lesson 9: Despite the best efforts to agree on an API between the middle tier and the database, little things like agreeing on the return codes and error handling, and formatting of dates were only discovered during integration testing.

Lesson 10: At 35K tps ADO.Net connection pooling is harder than it sounds.

So one day of knowledge transfer left on the contract. It’s about to go live and under a full production load it’s performing about 33% faster than required. The last thing to say about this project is that the folks were great to work with – I had a blast!

Poor men see sharp - more cursor optimization

Hugo Kornelis — Tue, 27 Nov 2007 22:47:00 GMT

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 the various cursor options, but with the code adapted to use SQLCLR or to use a cursor-less iteration.

The poor man’s cursor

I don’t think that “poor man’s cursor” is an official phrase, but what the hay – if we all start using it, we can make it official J. In case you want to know what a term means before using it, the term “poor man’s cursor” refers to any method of iterating over the rows in the result set of a query, processing them one by one, without using the DECLARE CURSOR, OPEN CURSOR, FETCH, CLOSE CURSOR, and DEALLOCATE CURSOR keywords that were added to T-SQL for the sole purpose of iterating over the rows in a result set of a query.

Why would you want to do that, you may ask? Well, I think that the most common reason is that programmers have heard that cursors are generally bad for performance, but fail to understand that the performance impact is not caused by the cursor itself, but by the fact that iterating over a result set reduces the options available to the query optimizer and negates the development team in Redmond has done to optimize SQL Server for set based operations. So they think that the cursor itself is to blame, and try to code around it without moving from their algorithmic, iteration-based approach to a declarative, set-based approach.

Usenet newsgroups and web-forums being full of simple one-liners such as “cursors are evil”, many people claiming that cursors incur a heavy overhead, and even some otherwise respectable websites listing WHILE loops first in a list of cursor alternatives, all have done their fair share to contribute to the popularity of the idea that you can improve cursor performance by simply replacing it with a different iteration mechanism. So, let’s find out if there is any truth to this claim.

Reading data

I started with the fastest of all cursor options, the one using a local, forward only, static, read only cursor with an ORDER BY matching the clustered index. I ripped out all cursor-related command and replaced them with the appropriate SELECT TOP(1) commands to read and process one row at a time, and ended up with this code:

-- Keep track of execution time

DECLARE @start datetime;

SET @start = CURRENT_TIMESTAMP;

-- Declare and initialize variables for loop

DECLARE @SalesOrderID int,

@SalesOrderDetailID int,

@OrderQty smallint,

@ProductID int,

@LineTotal numeric(38,6),

@SubTotal numeric(38,6);

SET @SubTotal = 0;

-- Read first row to start loop

SELECT TOP (1) @SalesOrderID = SalesOrderID,

@SalesOrderDetailID = SalesOrderDetailID,

@OrderQty = OrderQty,

@ProductID = ProductID,

@LineTotal = LineTotal

FROM Sales.SalesOrderDetail

ORDER BY SalesOrderID, SalesOrderDetailID;

-- Process all rows

WHILE @@ROWCOUNT > 0

BEGIN;

-- Accumulate total

SET @SubTotal = @SubTotal + @LineTotal;

-- Read next row

SELECT TOP (1) @SalesOrderID = SalesOrderID,

@SalesOrderDetailID = SalesOrderDetailID,

@OrderQty = OrderQty,

@ProductID = ProductID,

@LineTotal = LineTotal

FROM Sales.SalesOrderDetail

WHERE SalesOrderID > @SalesOrderID

OR ( SalesOrderID = @SalesOrderID

AND SalesOrderDetailID > @SalesOrderDetailID)

ORDER BY SalesOrderID, SalesOrderDetailID;

END;

-- Display result and duration

SELECT @SubTotal;

SELECT DATEDIFF(ms, @start, CURRENT_TIMESTAMP);

I ran this code five times in a row and calculated average execution time as 3166 milliseconds. I then re-ran the cursor code five times (I didn’t want to use the old measurements, as I was unsure if I had the same applications active – and having a different load on my machine would surely influence results); this code took 3265 milliseconds. So the first round goes to the poor man’s cursor, for beating the “real” cursor by three percent. I must add to this that I have later run another test, as part of research for a future blog post, where the results were reversed and the real cursor beat the poor man’s cursor by a small margin.

Of course, real life is not always so nice as to throw us only problems that require ordering the data by the clustered index key. So my next step was to investigate what happens to the comparison if the problem requires the data to be read in an order that can be served by a clustered index. Remember that I had a similar test case in the cursor option comparison, so I again was able to reuse the existing cursor code for ordering by ProductID. For the poor man’s cursor version, this involved changing the ORDER BY on both queries, but I also had to change the WHERE clause in the second – to make sure that the WHERE clause filters out all rows already processed, I have to include rows with a higher ProductID as well as rows with an equal ProductID and a higher primary key value – and in order for this to work, I also have to include the primary key columns as tie-breakers to the ORDER BY clause. I won’t post the full code, as most of it remains the same, but the “Read next row” query in the loop now reads like this:

-- Read next row

SELECT TOP (1) @SalesOrderID = SalesOrderID,

@SalesOrderDetailID = SalesOrderDetailID,

@OrderQty = OrderQty,

@ProductID = ProductID,

@LineTotal = LineTotal

FROM Sales.SalesOrderDetail

WHERE ProductID > @ProductID

OR ( ProductID = @ProductID

AND SalesOrderID > @SalesOrderID)

OR ( ProductID = @ProductID

AND SalesOrderID = @SalesOrderID

AND SalesOrderDetailID > @SalesOrderDetailID)

ORDER BY ProductID, SalesOrderID, SalesOrderDetailID;

The impact on performance is dramatic, to say the least. With this slight modification in the order in which rows have to be processed, the average execution time for five consecutive test runs rises to 5822 ms. The cursor version gets slower as well as a result of the new sort order, but by far less – it still takes only 3377 ms, so the poor man’s cursor is now worse by over seventy percent!

For the final test, I checked the effects of ordering by a column that’s not indexed at all. I did this in the original cursor test by ordering on LineTotal, so I’ll do the same here. Since LineTotal is, like ProductID in the previous test case, not constrained to be unique, the same consideration apply. That means that I can reuse the code of the version that ordered by ProductID except of course that I have to change each occurrence of ProductID to LineTotal.

This change really wrecked performance for the poor man’s cursor. I wanted to sit it out, but finally decided to kill the test after one and a half hours. I finally realized that the LineTotal column I was using is a non-persisted computed column, which adds an enormous amount of overhead – for each of the 121,317 iterations, SQL Server has to recalculate the LineTotal for each of the 121,317 rows – that is a total of almost 15 billion calculations! So I decided to change this test case to sort on OrderQty instead, then left the computer to execute the test run overnight. The next day, the duration was listed as a whopping 27,859,593 ms (seven and three quarter hours!) – just a tad slower than the real cursor, which clocked in at an average execution time of 3430 ms when sorting on the computed LineTotal column and 3352 ms when sorting of OrderQty.

Modifying data

Naturally, I wanted to test the performance of a poor man’s cursor in a modifying scenario as well. I didn’t really expect any surprises. After all, I already know that the fastest cursor solution uses the exact same cursor options as when reading data. I’ll spare you the poor man’s cursor code this time, since it’s based on the cursor code published on my previous blog posts, with the same modifications as above. Since this update scenario happens to be based on ordering by the clustered index key, I expected the poor man’s cursor to be just a tad faster, just as in the reading scenario.

After running the tests, I was surprised. The real cursor version took 5009 ms on average; the poor man’s cursor achieved the same task in just 4722 ms – a speed gain of over five percent. The speed gain was so much more than I expected that I actually repeated the tests – but with the same results. I must admit that I have no idea why the exact same cursor, transformed to the exact same poor man’s cursor, results in more speed gain when the rows are then updated then when they are merely used in a computation.

I did not test performance of the poor man’s cursor in a scenario where the rows have to be processed in a different order than the clustered index key. Based on the results of the tests for reading data, I expect performance to go down the drain in a very similar way.

Conclusion

People claiming that a poor man’s cursor performs better than a real cursor are mostly wrong. When the order in which rows have to be processed does not match the clustered index key, a properly optimized cursor will run rings around the poor man’s cursor.

The only exception is if the required ordering happens to coincide with the clustered index key. In those cases, a poor man’s cursor may sometimes beat a real cursor by a few percent, although there are other cases where the cursor still wins (also by a few percent). Even in the cases where the poor man’s cursor does win, the margin is so small that I’d recommend just using real cursors, with the appropriate options for maximum performance (that is, LOCAL, FORWARD_ONLY, STATIC, and READ_ONLY) in all cases.

Except of course in the 99.9% of all cases where a set-based solution beats the cursor-based one J.

Using the CLR

When you use CLR code to process data provided by SQL Server, iterating over rows to process them one at a time becomes the standard – after all, there is no support for set-based operations in C#, VB.Net, or any other .Net enabled programming language. As such, the claim made by Adam Machanic has valid grounds. A language that has no other option but to iterate over the rows and process them one at a time pretty well should be optimized for this kind of processing!

Reading data

The CLR version of the code to calculate the sum of all LineTotal values is about as simple as it gets:

[Microsoft.SqlServer.Server.SqlProcedure]

public static SqlInt32 ReadData([SqlFacet(Precision = 38, Scale = 6)] out SqlDecimal Total)

{

// Initialize subtotal

decimal SubTotal = 0;

// Set up connection and query

SqlConnection conn = new SqlConnection("context connection=true");

conn.Open();

SqlCommand cmd = conn.CreateCommand();

cmd.CommandText = "SELECT SalesOrderID, SalesOrderDetailID, " +

" OrderQty, ProductID, LineTotal " +

"FROM Sales.SalesOrderDetail " +

"ORDER BY SalesOrderID, SalesOrderDetailID;";

//"ORDER BY ProductID;";

//"ORDER BY LineTotal;";

//"ORDER BY OrderQty;";

cmd.CommandType = CommandType.Text;

// Process rows from reader; accumulate total

SqlDataReader rdr = cmd.ExecuteReader();

while (rdr.Read() == true)

{

SubTotal += (decimal)rdr[4];

}

// Clean up and return result

conn.Dispose();

Total = new SqlDecimal(SubTotal);

return 0;

}

Note that I did not do any dynamic SQL or fancy stuff to make the processing order variable; I just commented one line, uncommented another and recompiled. This avoids dangerous dynamic SQL and complex CASE expressions in the ORDER BY, plus it mimics much better how a real application would work – cursors and other iterative solutions are often used when developers (think they) need to process in a certain order, so the ORDER BY would usually be fixed.

The results of running the tests proved that Adam got it completely right – this CLR implementation does indeed run rings around even the fastest of all cursor solution, taking on average only 1060 milliseconds when ordering by the clustered index, 1072 milliseconds when ordering by the nonclustered index, 1132 milliseconds when ordering by the computed non-indexed column, and 1050 milliseconds when ordering by the non-computed non-indexed column. Three of these are so close together that I think that the differences are within the statistical margin of error and that they should be considered to be the same. The 70 extra milliseconds for ordering by a computed column are obviously the time taken to compute the value for each row in order to do the sorting.

I don’t understand why ordering by the clustered index key doesn’t result in some additional performance gain, as I expected this one to differ from the others by one sort step in the execution plan. This was another test case I repeated a few more times to make sure that I didn’t accidentally mess things up. If I execute the cmd.CommandText as a separate query in SQL Server Management Studio, I do get a significant cheaper execution plan when ordering by the clustered key index, so I guess that this will just have to be filed as one of the many things of SQL Server I don’t understand.

Modifying data

The CLR starts showing a completely different face when you have to modify the data you read from a cursor. The main problem is that you can’t use SqlDataReader anymore, since this blocks the context connection from being used for any other queries. You could choose to open a separate connection, but that has the disadvantage that you perform the updates in a separate transaction context so that you run into a huge blocking risk, plus a rollback of the main transaction would not roll back the changes made from this procedure.

So that leaves me with only one other option – use SqlDataAdapter.Fill method to copy the entire results of the query to a DataSet, then loop over it and process its rows one by one. This results in the CLR version doing a lot more work and using a significant amount of memory. The fact that we no longer update the row we have just read, but rather read them all and only then update them all means that there is also an increased chance that the row is no longer in the data cache and hence has to be read from disk a second time for the update, effectively doubling the amount of physical I/O (though this did not happen in my case).

[Microsoft.SqlServer.Server.SqlProcedure]

public static SqlInt32 ModifyData()

{

// Open connection (context connection since we're called in-process)

SqlConnection conn = new SqlConnection("context connection=true");

conn.Open();

// Prepare commands to fetch rows and to update

String SelCmd = "SELECT SalesOrderID, SalesOrderDetailID, " +

" OrderQty, ProductID, LineTotal " +

"FROM Sales.SalesOrderDetail " +

"ORDER BY SalesOrderID, SalesOrderDetailID;";

SqlDataAdapter da = new SqlDataAdapter(SelCmd, conn);

String UpdCmd = "UPDATE Sales.SalesOrderDetail " +

"SET OrderQty = @OrderQty " +

"WHERE SalesOrderID = @SalesOrderID " +

"AND SalesOrderDetailID = @SalesOrderDetailID;";

SqlCommand upd = new SqlCommand(UpdCmd, conn);

upd.Parameters.Add("@SalesOrderID", SqlDbType.Int);

upd.Parameters.Add("@SalesOrderDetailID", SqlDbType.Int);

upd.Parameters.Add("@OrderQty", SqlDbType.SmallInt);

// Read rows to process; copy to DataAdapter

DataSet ds = new DataSet();

da.Fill(ds);

// Process rows

foreach (DataRow dr in ds.Tables[0].Rows)

{

Int32 SalesOrderID = (Int32)dr[0];

Int32 SalesOrderDetailID = (Int32)dr[1];

Int16 OrderQty = (Int16)dr[2];

// Set parameters; perform update

upd.Parameters[0].Value = SalesOrderID;

upd.Parameters[1].Value = SalesOrderDetailID;

upd.Parameters[2].Value = OrderQty + 1;

upd.ExecuteNonQuery();

}

// Cleanup and return

conn.Dispose();

return 0;

}

After compiling and deploying the code above, I once more ran 5 tests. The average execution time for this version was 12,215 milliseconds, almost 150% more than the cursor version. My guess is that this huge increase in time is not a result of the update command itself, but a result of the requirement to pre-load the data in a DataSet and then iterate over that. I did not test it, but I expect to see a similar problem if a cursor requires reading some additional data, based on the data read in the cursor – this, too, would require the CLR version to employ a DataSet instead of simply looping over a SqlDataReader.

Conclusion

Adam’s suggestion to use CLR makes sense, but only for cases where no additional data access, either reading or modifying, is required when processing the rows in the cursor. As soon as the latter becomes a requirement, the CLR version has to switch from using a SqlDataReader to using SqlDataAdapter.Fill, and performance suffers horribly.