# Find the position of all occurrences of an expression within a string

• Comments posted to this topic are about the item Find the position of all occurrences of an expression within a string

• Just plain AWESOME!

• Please consider using a Tally Table instead of a recursive CTE to count. Please see the following article as to why.

http://www.sqlservercentral.com/articles/T-SQL/74118/

If you don't know what a Tally Table (or Tally CTE) is or how it can be used to replace certain loops (including the loops of a recursive CTE which are frequently slower than WHILE loops), please see the following article.

http://www.sqlservercentral.com/articles/T-SQL/62867/

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

• 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.

http://www.sqlservercentral.com/articles/T-SQL/74118/

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`

`)`

• The second version has also taught me a lot.

I have been trying to complete the function so that it would return as separate "words" the characters between each delimiter (a comma).

I know that there is an excellent string splitter function by J. Moden, but for didactic purposes, I would like to see how the solution presented here can be updated to include the modern LEAD/LAG and OVER additions to SQL Server, in lieu of my clumsy attempt below.

[font="Courier New"]

DECLARE @tvf table (pk int not null primary key, pos int, endpos int, token varchar(20))

INSERT INTO @tvf(pk, pos) VALUES (0, 0)

DECLARE

@strInput VARCHAR(8000) = '1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16',

@delimiter VARCHAR(5) = ',';

WITH E1(N) AS ...

-- Replace the last SELECT statement in the original solution with:

INSERT INTO @tvf(pk, pos)

SELECT f.posnum, f.pos

FROM findchar f

UPDATE t2

SET endpos = t1.pos

FROM @tvf t2

INNER JOIN @tvf t1 ON t1.pk = t2.pk + 1

DELETE FROM @tvf WHERE pk = (SELECT MAX(pk) FROM @tvf)

UPDATE @tvf

SET token = SUBSTRING(@strInput, pos +1, endpos-pos-1)

WHERE NOT endpos IS NULL

SELECT * FROM @tvf[/font]

• Love those Tally tables

• j-1064772 (5/12/2015)

The second version has also taught me a lot.

I have been trying to complete the function so that it would return as separate "words" the characters between each delimiter (a comma).

I know that there is an excellent string splitter function by J. Moden, but for didactic purposes, I would like to see how the solution presented here can be updated to include the modern LEAD/LAG and OVER additions to SQL Server, in lieu of my clumsy attempt below.

[font="Courier New"]

DECLARE @tvf table (pk int not null primary key, pos int, endpos int, token varchar(20))

INSERT INTO @tvf(pk, pos) VALUES (0, 0)

DECLARE

@strInput VARCHAR(8000) = '1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16',

@delimiter VARCHAR(5) = ',';

WITH E1(N) AS ...

-- Replace the last SELECT statement in the original solution with:

INSERT INTO @tvf(pk, pos)

SELECT f.posnum, f.pos

FROM findchar f

UPDATE t2

SET endpos = t1.pos

FROM @tvf t2

INNER JOIN @tvf t1 ON t1.pk = t2.pk + 1

DELETE FROM @tvf WHERE pk = (SELECT MAX(pk) FROM @tvf)

UPDATE @tvf

SET token = SUBSTRING(@strInput, pos +1, endpos-pos-1)

WHERE NOT endpos IS NULL

SELECT * FROM @tvf[/font]

Eirikur Erikson rewrote the DelimitedSplit8K function using the very functionality you speak of and it's twice as fast. The article isn't named to be easy to find for that so here's the link.

http://www.sqlservercentral.com/articles/SQL+Server+2012/106903/

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

• 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.

http://www.sqlservercentral.com/articles/T-SQL/74118/

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.

"I cant stress enough the importance of switching from a sequential files mindset to set-based thinking. After you make the switch, you can spend your time tuning and optimizing your queries instead of maintaining lengthy, poor-performing code."

-- Itzik Ben-Gan 2001

Viewing 9 posts - 1 through 8 (of 8 total)