Adam Machanic : string splitting, SQLCLR

SQLCLR String Splitting Part 2: Even Faster, Even More Scalable

Adam Machanic — Tue, 28 Apr 2009 18:54:00 GMT

Two days ago, after posting what I thought was a pretty solid SQLCLR string splitting method, I received a comment telling me about a big thread on SQLServerCentral dedicated to the question of how best to split strings. So I jumped in, and went back and forth, and back and forth, and back... and forth...

Many, many messages and several revisions and re-revisions later, I am happy to present the newer, better, more bug-free SQLCLR string splitting function. Not only is it faster than the previous one I posted, but it also handles multi-character delimiters, ignores consecutive delimiters as well as pre and post delimiters, and best of all, it won't get itself stuck in an infinite loop in certain cases (always a really great stability feature).

This version walks the SqlChars character array rather than using the IndexOf method on the string, which we found to be a somewhat faster technique--and it's certainly the most scalable and memory efficient method I can imagine.

Special thanks to SQLServerCentral member Florian Reischl, who was the main person keeping the thread going with me during the last couple of days, and who managed to re-write my versions and eke out even better performance by modifying the algorithms. Great stuff--it was definitely the most fun I've had on a technical forum in quite a long time.

But without further ado, the code:

using System;
using System.Collections;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;

public partial class UserDefinedFunctions
{
    [Microsoft.SqlServer.Server.SqlFunction(
       FillRowMethodName = "FillRow_Multi",
       TableDefinition = "item nvarchar(4000)"
       )
    ]
    public static IEnumerator SplitString_Multi(
      [SqlFacet(MaxSize = -1)]
      SqlChars Input,
      [SqlFacet(MaxSize = 255)]
      SqlChars Delimiter
       )
    {
        return (
            (Input.IsNull || Delimiter.IsNull) ?
            new SplitStringMulti(new char[0], new char[0]) :
            new SplitStringMulti(Input.Value, Delimiter.Value));
    }

    public static void FillRow_Multi(object obj, out SqlString item)
    {
        item = new SqlString((string)obj);
    }

    public class SplitStringMulti : IEnumerator
    {
        public SplitStringMulti(char[] TheString, char[] Delimiter)
        {
            theString = TheString;
            stringLen = TheString.Length;
            delimiter = Delimiter;
            delimiterLen = (byte)(Delimiter.Length);
            isSingleCharDelim = (delimiterLen == 1);

            lastPos = 0;
            nextPos = delimiterLen * -1;
        }

        #region IEnumerator Members

        public object Current
        {
            get
            {
                return new string(theString, lastPos, nextPos - lastPos);
            }
        }

        public bool MoveNext()
        {
            if (nextPos >= stringLen)
                return false;
            else
            {
                lastPos = nextPos + delimiterLen;

                for (int i = lastPos; i < stringLen; i++)
                {
                    bool matches = true;

                    //Optimize for single-character delimiters
                    if (isSingleCharDelim)
                    {
                        if (theString[i] != delimiter[0])
                            matches = false;
                    }
                    else
                    {
                        for (byte j = 0; j < delimiterLen; j++)
                        {
                            if (((i + j) >= stringLen) || (theString[i + j] != delimiter[j]))
                            {
                                matches = false;
                                break;
                            }
                        }
                    }

                    if (matches)
                    {
                        nextPos = i;

                        //Deal with consecutive delimiters
                        if ((nextPos - lastPos) > 0)
                            return true;
                        else
                        {
                            i += (delimiterLen-1);
                            lastPos += delimiterLen;
                        }
                    }
                }

                lastPos = nextPos + delimiterLen;
                nextPos = stringLen;

                if ((nextPos - lastPos) > 0)
                    return true;
                else
                    return false;
            }
        }

        public void Reset()
        {
            lastPos = 0;
            nextPos = delimiterLen * -1;
        }

        #endregion

        private int lastPos;
        private int nextPos;

        private readonly char[] theString;
        private readonly char[] delimiter;
        private readonly int stringLen;
        private readonly byte delimiterLen;
        private readonly bool isSingleCharDelim;
    }
};

Enjoy!

Faster, More Scalable SQLCLR String Splitting

Adam Machanic — Sun, 26 Apr 2009 23:59:00 GMT

It seems like every couple of months we see yet another post on SQLCLR string splitting routines. Many bloggers, I suppose, are still struggling, even three years later, to find that "perfect" use case for SQLCLR. Is string splitting it? Probably not. And with SQL Server 2008 table-valued parameters now available, SQLCLR string splitting has become an even less interesting exercise than it was before. None the less, a recent post on the Less Than Dot site has inspired me to counter with my own best SQLCLR string splitting method, for those of you who are still interested in solving this problem.

I've noticed that almost invariably, the methods posted online stress how very easy it is to do string splitting in .NET, thanks to the String.Split method. And while this easy method tends to work pretty well for small strings and on workloads that don't need to scale, it quickly breaks down when any amount of load is introduced (something that, unfortunately, most writers don't bother considering). The Less Than Dot writer, "onpnt" did do some testing, and discovered that--surprise, surprise--String.Split isn't all that great.

The issue? Well, it all comes down to large memory allocations and the art of scalable .NET programming--an area about which many SQL Server developers can (and do) remain blissfully naïve. In .NET, reduction of memory utilization--especially large allocation done en masse--is king, and String.Split does exactly the wrong thing. It takes the input string, breaks it into N chunks, and allocates all of the memory needed to store those chunks and pointers to those chunks, in one big huge operation. This can't possibly scale, and indeed it doesn't. I did a quick SQLQueryStress test of a TVF based on String.Split and saw fairly good performance when the input sentences were small (in the 40-400 byte range--see below), but after a certain point the AppDomains began recycling and performance became abysmal. Protections put in place for stability of the CLR host include memory leak detection, and this kicks in quite readily when we force allocation of so much memory in one shot--a good thing for the SQL Server instance as a whole, but not great when we're trying to really split a huge string.

Students of .NET who are concerned with scale (and really, everyone should be) are urged to look at the way problems are handled in LINQ. Here the vast majority of requests are internally handled using streaming iterator patterns, rather than moving around huge chunks of memory. This turns out to a much more scalable option for several reasons: Lower in-flight memory utilization, fewer large object heap allocations, and better access by the garbage collector to collect intermediate data that is no longer needed.

So how can we apply streaming to the string splitting problem? Rather than break the string up into all of its component parts upfront, we can walk the string step-by-step, only finding the next piece as required. In order to handle this, I created the following worker class:

    public class splitIt : IEnumerator
    {
        public splitIt(string theString, char delimiter)
        {
            this.theString = theString;
            this.delimiter = delimiter;
            this.lastPos = -1;
            this.nextPos = -1;
        }

        #region IEnumerator Members

        public object Current
        {
            get { return theString.Substring(lastPos, nextPos - lastPos).Trim(); }
        }

        public bool MoveNext()
        {
            if (nextPos >= theString.Length)
                return false;
            else
            {
                lastPos = nextPos + 1;

                if (lastPos == theString.Length)
                    return false;

                nextPos = theString.IndexOf(delimiter, lastPos);
                if (nextPos == -1)
                    nextPos = theString.Length;

                return true;
            }
        }

        public void Reset()
        {
            this.lastPos = -1;
            this.nextPos = -1;
        }

        #endregion

        private int lastPos;
        private int nextPos;
        private string theString;
        private char delimiter;
    }

This class is a simple enumerator implementation that looks for the next delimiter on each iteration, only when requested. Splitting strings in this way, rather than using String.Split, means that no huge upfront allocation takes place. Aside from the sentence itself, only one "chunk" is in play at any given time, and any chunks that have already been used can be garbage collected as needed when memory is tight.

Wiring this class up in a SQLCR TVF is just about as simple as when using String.Split:

    [Microsoft.SqlServer.Server.SqlFunction(FillRowMethodName = "FillIt", TableDefinition = "output nvarchar(4000)")]
    public static IEnumerator faster_split
        (
            SqlChars instr, 
            [SqlFacet(IsFixedLength=true, MaxSize=1)]
            SqlString delimiter
        )
    {
        return (
            (instr.IsNull || delimiter.IsNull) ? 
            new splitIt("", ',') : 
            new splitIt(instr.ToSqlString().Value, Convert.ToChar(delimiter.Value)));
    }

    public static void FillIt(object obj, out SqlString output)
    {
        output = (new SqlString((string)obj));
    }

I've enhanced this example slightly compared with most of the usual suspects: A SqlFacet attribute is used to make sure that the delimiter is only a single character, and I've added a bit of additional code in the main method to deal with NULL inputs.

The scalability difference between this method and the String.Split method is staggering in the simple tests I ran today on my SQL Server 2008 test server. With small sentences, even under moderate load (100 concurrent threads), each method performs more or less equivalently. But as sentence size increases to 50KB, the String.Split method begins slowing, taking almost 2 seconds per iteration, and the occasional AppDomain recycle is seen in the SQL Server log. The streaming method, on the other hand, continues to complete its job in just over 1/10th of a second, and causes no AppDomain recycles. Increasing to 500KB sentences, String.Split causes numerous AppDomain recycles and time per iteration increases to over 30 seconds, while the streaming method averages just 16 seconds per iteration. Jumping to 5MB sentences, String.Split causes almost continuous AppDomain recycles, and each iteration takes almost 6 minutes to complete. Yet with the streaming method, even with sentences of this size I am still unable to cause an AppDomain recycle to occur, and iterations complete in around 55 seconds.

The test I did was quite simple, and I won't post too many details here as I prefer that you test with your own workloads and draw your own conclusion about how this method fares when compared with T-SQL versions or the naïve String.Split method. I hope that if you do test you'll post back here with your results so that we can all learn the best way to handle these problems--whether or not string splitting really is all that interesting in the post-SQL Server 2005 world.