Steven Willis (4/19/2013)
Jeff Moden (4/14/2013)
Please consider using a Tally Table instead of a recursive CTE to count. Please see the following article as to why.Thanks for the suggestion Jeff.
Below is an updated version using the cteTally table. I tested this against the first function and for a 10,000 row test file the cteTally version was 1200ms faster per run on average than the regular recursive CTE. Not a HUGE difference, but significant. Otherwise, everything about the function still works the same.
I didn't quite understand that even in an iTVF that a recursive CTE is just a loop counter. After studying your article some more and looking at this function I can see the difference now. If nothing else, limiting the number of iterations right up front with the tally table definition at least limits how high the counter can go. The light is coming on slowly!
CREATE FUNCTION [dbo].[itvfFindPosTally]
(
@strInput VARCHAR(8000)
,@delimiter VARCHAR(5)
)
RETURNS TABLE WITH SCHEMABINDING
AS
RETURN
(
WITH E1(N) AS (
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
),
E2(N) AS (SELECT 1 FROM E1 a, E1 b
),
E4(N) AS (SELECT 1 FROM E2 a, E2 b
),
cteTally(N) AS (SELECT 0 UNION ALL
SELECT TOP (DATALENGTH(ISNULL(@strInput,1))) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E4
),
findchar (posnum,pos)
AS
(
SELECT
ROW_NUMBER() OVER (ORDER BY t.N) AS posnum
,CHARINDEX(@delimiter,@strInput,t.N) AS pos
FROM
cteTally t
WHERE
(SUBSTRING(@strInput,t.N,1) = @delimiter)
)
SELECT
posnum
,pos
FROM
findchar
WHERE
pos > 0
)
I know that it's been a few months but your function, as written, will only work for strings with a length of one. You need to change:
(SUBSTRING(@strInput,t.N,1) = @delimiter)
to:
(SUBSTRING(@strInput,t.N,(LEN(@delimiter))) = @delimiter)
Now it will work for strings of any length (up to varchar(5) in your case but no harm in increasing that for this purpose).
Not a HUGE difference, but significant. Otherwise, everything about the function still works the same.
It's also worth noting that the performance gains will become more dramatic the longer the string. Also, the recursive CTE itvf will never get you a parallel query plan; another benefit of using the tally table version.
Lastly, you can accomplish this using my updated NGrams8K function. It's also an ITVF that uses a tally table and performs this task about 2.5 faster than the corrected version of the function you posted.
The NGrams8k function:
CREATE FUNCTION dbo.nGrams8K (@string varchar(8000), @k int)
/********************************************************************
Created by: Alan Burstein
Created on: 3/10/2014
Last Updated on: 5/22/2015
n-gram defined:
In the fields of computational linguistics and probability,
an n-gram is a contiguous sequence of n items from a given
sequence of text or speech. The items can be phonemes, syllables,
letters, words or base pairs according to the application.
For more information see: http://en.wikipedia.org/wiki/N-gram
Use:
Outputs a stream of tokens based on an input string.
Similar to mdq.nGrams:
http://msdn.microsoft.com/en-us/library/ff487027(v=sql.105).aspx.
Except it only returns characters as long as K.
nGrams8K also includes the position of the "Gram" in the string.
Examples of how to use:
SELECT position, token FROM dbo.nGrams8K('abcdefg',1);
SELECT position, token FROM dbo.nGrams8K('abcdefg',2);
SELECT position, token FROM dbo.nGrams8K('abcdefg',3);
Revision History:
Rev 00 - 03/10/2014 Initial Development - Alan Burstein
Rev 01 - 05/22/2015 Removed DQS N-Grams functionality,
improved iTally - Alan Burstein
Rev 02 - 05/22/2015 Changed TOP logic to remove implicit conversion
- Alan Burstein
********************************************************************/
RETURNS TABLE WITH SCHEMABINDING AS RETURN
WITH
L1(N) AS
(
SELECT 1
FROM (VALUES
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL)
) t(N)
),
iTally(N) AS
(
SELECT TOP(CONVERT(BIGINT,(LEN(@string)-(@k-1)),0))
ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM L1 a CROSS JOIN L1 b -- add two more cross joins to support varchar(max)
)
SELECT
position = N,
token = SUBSTRING(@string,N,@k)
FROM iTally;
The performance tests:
SET NOCOUNT ON;
IF OBJECT_ID('tempdb..#vals') IS NOT NULL DROP TABLE #vals;
SELECT TOP 100000
ID = ROW_NUMBER() OVER (ORDER BY (SELECT NULL)),
String = CAST(newid() AS varchar(36))
INTO #vals
FROM sys.all_columns a, sys.all_columns b;
GO
/**** Test the functionality ****/
SELECT TOP 10 *
FROM #vals
CROSS APPLY dbo.nGrams8K(String,2)
WHERE token = 'AA';
SELECT TOP 10 *
FROM #vals
CROSS APPLY dbo.itvfFindPosTally(String, 'AA');
GO
/**** Performance tests ****/
-- Note: on my system (SQL Server 2014 Ent, 8CPU, 32GB) - I get a parallel plan (DOP 8)
PRINT '=== ngrams parallel ==='
DECLARE @st datetime = getdate(), @x int;
SELECT @x = position
FROM #vals
CROSS APPLY dbo.nGrams8K(String,2)
WHERE token = 'AA';
PRINT DATEDIFF(ms,@st,getdate());
GO 3
PRINT '=== itvfFindPosTally parallel ==='
DECLARE @st datetime = getdate(), @x int;
SELECT @x = pos --ID, String, posnum, pos
FROM #vals
CROSS APPLY dbo.itvfFindPosTally(String, 'AA');
PRINT DATEDIFF(ms,@st,getdate());
GO 3
-- Second tests forcing a serial plan
PRINT '=== ngrams serial ==='
DECLARE @st datetime = getdate(), @x int;
SELECT @x = position
FROM #vals
CROSS APPLY dbo.nGrams8K(String,2)
WHERE token = 'AA'
OPTION (MAXDOP 1);
PRINT DATEDIFF(ms,@st,getdate());
GO 3
PRINT '=== itvfFindPosTally serial ==='
DECLARE @st datetime = getdate(), @x int;
SELECT @x = pos --ID, String, posnum, pos
FROM #vals
CROSS APPLY dbo.itvfFindPosTally(String, 'AA')
OPTION (MAXDOP 1);
PRINT DATEDIFF(ms,@st,getdate());
GO 3
Results:
Beginning execution loop
=== ngrams parallel ===
180
=== ngrams parallel ===
126
=== ngrams parallel ===
130
Batch execution completed 3 times.
Beginning execution loop
=== itvfFindPosTally parallel ===
323
=== itvfFindPosTally parallel ===
313
=== itvfFindPosTally parallel ===
323
Batch execution completed 3 times.
Beginning execution loop
=== ngrams serial ===
470
=== ngrams serial ===
490
=== ngrams serial ===
483
Batch execution completed 3 times.
Beginning execution loop
=== itvfFindPosTally serial ===
1133
=== itvfFindPosTally serial ===
1133
=== itvfFindPosTally serial ===
1140
Batch execution completed 3 times.
Edit: Text formatting got messed up.
-- Itzik Ben-Gan 2001