question

> So just as a polite suggestion, don't > be so quick to dismiss proven methods > just because you've heard that they're > bad, and also don't be so quick to > assume that magic methods like numbers > tables will always perform better. > Just because it doesn't look like a > loop doesn't mean it's not a loop. Finer words could not have been spoken. Just because someone uses a Tally Table, doesn’t mean that the solution will automatically be faster. The Tally Table is a “different animal” and if someone uses the same ol’ tired methods and formulas they use in loops in conjunction with a Tally Table, then the Tally Table code will frequently be slower. Before we get started, let’s have a little test for the folks reading this in the USA. C’mon… it’ll be fun! ;-) Ready? Answer these as quickly as possible. 1. **How many sides does a STOP sign have?** Good! You’ve been paying attention. STOP signs have 8 sides. 2. **What COLOR is a STOP sign?** Again, good! Most everyone in the USA knows that STOP signs are RED. If they've really been paying attention, they also know they have WHITE letters. 3. **How many sides does a YIELD sign have?** Excellent! Yes, a YIELD sign has 3 sides. You folks are really on a roll! 4. **What COLOR is a YIELD sign?** 70% of you in the USA answered “Yellow” and most of those added “with Black letters”… and you’re all WRONG! ;-) The official colors of Yield signs changed, more than 20 years ago, to Red and White. Sure, you may find a wicked old sign here and there that’s still Yellow, but almost all of them are Red and White and all of the new ones (less than 23 years old) are Red and White. That’s the real problem, isn’t it? People keep “thinking” the same way and, as a result, they make that same type of mistake in their code. They end up overriding the “magic” of the Tally Table with the same inefficient methods and formulas they use with loops because that’s what they’ve always known and that’s how they’ve always thought. As I've said many times, "Before you can think outside the box, you must FIRST realize... YOU'RE IN A FREAKIN' BOX!!!" ;-) and people just don’t realize what kind of box they’re in when it comes to using the Tally Table or “set based” programming methods, in general. I’ll also make the polite, yet, opposing suggestion that folks should usually dismiss “proven methods” if they involve a loop. Learn how to think when it comes to “set based” code and the use of the Tally Table. Learn to think in columns instead of rows. Think in “words” instead of “characters”. Learn to use the very high performance natural looping (I use R. Barry Young’s term for this… PSEUDO CURSOR) that occurs within a simple SELECT. Stop living in the same ol’ box, folks. I’ll make another polite suggestion that, if you really want to know how something will perform, you really, really need to learn how to make scads of test data because things like the use of GO 50000 skew the test a bit. What the use of GO 50000 will cause is 50000 reevaluations of whether or not the current execution plan can be reused or not and since that process is sometimes a little slower than some think, it can cause Set-based code to look like it’s running slower than looping code which always evaluates the reuse of the execution plans it made for the first row. For example… turn on the “Actual Execution Plan” and run the following simple code… SELECT TOP (1) N FROM dbo.Tally GO 10 See? 10 separate execution plans. Now, if you’re testing for singleton use of a function for use by a GUI, that might be ok, but it’s NOT ok when you’re trying to measure the performance a function will have when it’s used against a table containing a large number of rows. Only one execution plan per code snippet (SELECT, INSERT, UPDATE, DELETE, MERGE) should be created for a batch run (which is part of the reason why loops are so bad because they create multiple execution plans for each iteration). Ok… with that in mind, let’s create enough test data to make our tests worthwhile. As is normal for me, most of the details are included as comments in the code. The code will look much better in SSMS where wrapping doesn't take place. --===================================================================================================================== -- Create substantial quantities of highly randomized test data so our tests can more easily measure the -- performance of various methods even on fast machines. -- -- Note that this section of code is NOT a part of the solution. We're just building test data here. --===================================================================================================================== --===== Conditionally drop the test table to make reruns easier in SSMS IF OBJECT_ID('tempdb..#TestTable','U') IS NOT NULL DROP TABLE #TestTable; --===== Create and populate the test table on-th-fly with random length random data with randomly placed characters -- including some letters, digits, and some symbols (dashes in this case). The length of the data varies from -- 36 to 72 characters and the position of the symbols also varies because of the randomized lengths. SELECT TOP (100000) RowNum = IDENTITY(INT,1,1), SomeString = RIGHT(CAST(NEWID() AS VARCHAR(36)),ABS(CHECKSUM(NEWID()))%19+18) + RIGHT(CAST(NEWID() AS VARCHAR(36)),ABS(CHECKSUM(NEWID()))%19+18) INTO #TestTable FROM sys.all_columns ac1 CROSS JOIN sys.all_columns ac2 ; --===== Now, let's make all the even-numbered rows lower case so we can make sure the case sensitivity works UPDATE #TestTable SET SomeString = LOWER(SomeString) WHERE RowNum %2 = 0 ; --===== Show the Min/Max length of the SomeString column. SELECT MIN(LEN(SomeString)), MAX(LEN(SomeString)) FROM #TestTable ; --===== Show the first 10 rows of data we've built just to get a feel for what's going on. SELECT TOP (10) * FROM #TestTable ; As a bit of a sidebar, the real reason why most people don’t create test data is because {drum roll please}… they think they have to use a While Loop to create randomized data and While Loops just take too long in most folks eyes. With a While Loop, you have to first create a table and then you have to populate it. With a While Loop, the code to populate the table actually takes a fair bit of coding because you have to control the start of the process, the process itself, and the end of the process. Make a mistake and the code could run “forever”. Remember… the Yield sign isn’t Yellow, anymore. ;-) Now, if someone is going to claim that a given set-based technology, like the Tally Table, is worse than any form of RBAR *(pronounced “ree-bar” like the metal rods stuck in cement forever, means “Row By Agonizing Row”, and, yeah… I’m the person who coined that acronym on SQLServerCentral in 2005 [ http://www.sqlservercentral.com/articles/Advanced+Querying/calculatingworkdays/1660/][1] )* for a given problem, they at least need to build the principle component, the Tally Table itself, correctly. There MUST be a Clustered Index with a FILL FACTOR of 100 on the “N” column to truly make use of its “magic”. Without that Clustered Index, you’re just taking pot-shots with where the Table Scan decides to quit especially if you’re not using the numbers from the Tally Table in sequential order. The following method for building an 11,001 row, zero based (starts at 0) Tally Table is guaranteed to work because sys.all_columns has at least 4,000 rows (no guarantee past that, though) in it even on a brand new installation if you’ve installed the whole ball-of-wax. Why do I use the max number of 11,000? Read my article ([ http://www.sqlservercentral.com/articles/T-SQL/62867/][2] ) to find out. ;-) It’ll change your life if you don’t know how a Tally Table actually works even if you’re currently using it. Here’s the code to build a proper Tally Table. Yeah… you can use ROW_NUMBER() with an ISNULL to make it a NOT NULL column and subtract 1 from it to start at Zero instead of one, but why bother? That’s too much typing. ;-) --=================================================================== -- Create a Tally table from 0 to 11000 --=================================================================== --===== Create and populate the Tally table on the fly. SELECT TOP 11001 IDENTITY(INT,0,1) AS N INTO dbo.Tally FROM Master.sys.ALL_Columns ac1 CROSS JOIN Master.sys.ALL_Columns ac2 ; --===== Add a CLUSTERED Primary Key to maximize performance ALTER TABLE dbo.Tally ADD CONSTRAINT PK_Tally_N PRIMARY KEY CLUSTERED (N) WITH FILLFACTOR = 100 ; --===== Allow the general public to use it GRANT SELECT ON dbo.Tally TO PUBLIC ; GO Ok… we’ve got a decent amount of test data and we have a properly constructed Tally Table complete with the required Clustered Index. On with the show! As I said previously, the reason why the While Loop method (specifically the StripNonAlpha function) was able to beat the Tally Table methods that have been submitted, so far, is because people keep trying to use the same ol’ tired methods of doing the same thing as they do in loops (not to mention the crippling effect of not having the Clustered Index on the Tally Table). They’ve taken the first step in replacing the While Loop with the Pseudo-Cursor produced with a join to the Tally Table, but that’s all they’ve done. They haven’t replaced the truly bad technology, which might be called “CBAC” or “Character By Agonizing Character”. The Tally Table can do so much more if you let it. They’ve also violated one of the most important concepts of “set based” programming there is… they handle and move too much data. All of the methods given, so far, strip out one character, determine if it’s a “keeper”, and then concatenate it into a “keeper string”. That means the data is handled/moved at least twice per character, “keeper or not”. With that in mind, let’s write a Tally Table function that will wipe out only the unwanted characters using the STUFF function. And, no… it’s not an Inline Function. Not all Inline Functions are faster than Scalar Functions. In the true spirit that we all know only too well, “It Depends” and the Yield sign isn't Yellow, anymore. ;-) Here’s my rendition of what a string cleaner that uses a Tally Table should look like. CREATE FUNCTION dbo.CleanString /***************************************************************************************** Purpose: Given a string, this function removes unwanted characters according to a single character, case sensitive "LIKE" pattern. Reference: http://ask.sqlservercentral.com/questions/75404/strip-all-but-alpha-chars-out-of-a-string Revision History: Rev 00 - 17 Jul 2005 - Jeff Moden - Production code with certain non-relevant functionality removed for demonstration purposes on this site. *****************************************************************************************/ --===== Declare the I/) parameters for the function ( @pString VARCHAR(8000), @pPattern VARCHAR(300) ) RETURNS VARCHAR(8000) AS BEGIN --===== Find and "Stuff-out" only the characters found by the "pattern". -- Note that the pattern is "case sensitive" due to the collation used. -- Also notice how very simple and compact this code actually is. If it -- ever does need maintenance, it will be easy for someone to do SELECT @pString = STUFF(@pString,t.N,1,'') FROM dbo.Tally t WHERE t.N BETWEEN 1 AND LEN(@pString) AND SUBSTRING(@pString,t.N,1) LIKE @pPattern COLLATE Latin1_General_BIN ORDER BY t.N DESC ; RETURN @pString END ; Claims of performance aren’t valid nor tolerated without an actual test. With that thought in mind, run the code (further above on this post) that creates the test table and then run this test harness. --===== Conditionally drop the test results tables to make reruns easier in SSMS IF OBJECT_ID('tempdb..#CleanStringResults' ,'U') IS NOT NULL DROP TABLE #CleanStringResults; IF OBJECT_ID('tempdb..#StripNonAlphaResults','U') IS NOT NULL DROP TABLE #StripNonAlphaResults; --===== Setup the environment so that the While Loop code has a chance at being performant SET NOCOUNT ON; --Supresses the auto-display of row counts. --===== Declare a "timer" variable DECLARE @StartTime DATETIME; --===== Test the Tally Table string-cleaner ======================================================= -- Start the "timer" SELECT @StartTime = GETDATE(); -- Run the test SELECT RowNum, CleanString = dbo.CleanString(SomeString,'[^A-Za-z]') INTO #CleanStringResults FROM #TestTable ; -- Display the duration PRINT 'Duration(ms) for Tally Table: ' + CAST(DATEDIFF(ms,@StartTime,GETDATE()) AS VARCHAR(10)) ; --===== Test the While Loop string-cleaner ======================================================= -- Start the "timer" SELECT @StartTime = GETDATE(); -- Run the test SELECT RowNum, NonAlphaString = dbo.StripNonAlpha(SomeString) INTO #StripNonAlphaResults FROM #TestTable ; -- Display the duration PRINT 'Duration(ms) for While Loop: ' + CAST(DATEDIFF(ms,@StartTime,GETDATE()) AS VARCHAR(10)) ; Here are the results from my poor ol’ 9 year old, single CPU desktop… Duration(ms) for Tally Table: 15313 Duration(ms) for While Loop: 26170 I’m sure some person smarter than me will be able to turn the function into an iTVF (Inline Table Valued Function) for a bit of extra speed or maybe do the same thing with a CLR which is sometimes better for string handling, but this simple Tally Table code is nearly twice as fast as the While Loop function. Even my method uses “RBR” (Row-By-Row) technology because it’s a difficult thing to manipulate strings at a character level for each row without some form of “RBR”. You can, however, avoid exasperating the problem by keeping “RBAR” (Row-By-AGONIZING-Row) out of the function (if you understand the difference), itself. Just make sure you don’t include some “Hidden RBAR” that looks “Set Based” but really isn’t. Again, if I may politely suggest, there are going to be a whole lot of people that don’t know how to use the technology of the Tally Table correctly and there are going to be at least that number that use that fact to denounce it’s use. They’ll continue to tell folks to "not dismiss {sic} 'proven methods'” using a loop and they’ll seemingly prove it with code, which is the only true judge you should listen to. ;-) The problem is that those same people are normally so used to using RBAR methods that they can’t figure out how to use more advanced technology correctly and the people following the thread will frequently agree because… they don’t necessarily know how to use it correctly, either. Write it down and post it on your monitor… tattoo it to the back of your hand if you have to. If it has RBAR in it, whether it’s a discreet loop or “looks-like-set-based” recursion or “Triangular Joins”, there’s a VERY good chance (there ARE exceptions, of course. I'll see if I can come up with one in a couple of days) you’ve done it wrong despite what other people supposedly “prove” with code. ;-) How do I know this for sure? Heh… I’m also guilty of being a mere carbon-based life-form with bad habits to break. Take a look at the following article and see what I mean. Up until that article, I thought Yield signs were Yellow. ;-) [ http://www.sqlservercentral.com/articles/Tally+Table/72993/][3] Thanks for listening, folks. And, yes… the dust bunnies all say “Hi”. ;-) --Jeff Moden p.s. Magnus and GPO… VERY nice tries. Magnus... your code would be a lot faster (but still not as fast as the "Stuff" method I used) if it selected only the good characters instead of making a CASE decision on every character. Like this... CREATE FUNCTION dbo.fnGetAlphaModified (@pString VARCHAR(8000)) RETURNS TABLE AS RETURN SELECT AlphaString = ( SELECT SUBSTRING(@pString, t.N, 1) FROM dbo.Tally t WHERE t.n BETWEEN 1 AND LEN(@pString) AND SUBSTRING(@pString, t.N, 1) LIKE '[A-Za-z]' COLLATE Latin1_General_BIN ORDER BY t.n FOR XML PATH('') ) ; [1]: http://www.sqlservercentral.com/articles/Advanced+Querying/calculatingworkdays/1660/ [2]: http://www.sqlservercentral.com/articles/T-SQL/62867/ [3]: http://www.sqlservercentral.com/articles/Tally+Table/72993/