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

Question

Post reply

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

Steven Willis

SSCrazy Eights

Points: 9893
More actions
April 1, 2013 at 7:45 pm

#394504

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

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

You must be logged in to reply to this topic. Login to reply

Sean Smith SSCertifiable Points: 5941 More actions · Answer 1

Sean Smith

SSCertifiable

Points: 5941

April 12, 2013 at 11:28 am

#1606063

Just plain AWESOME!

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 2

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.

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

Steven Willis SSCrazy Eights Points: 9893 More actions · Answer 3

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

),

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

)

j-1064772 SSCertifiable Points: 5316 More actions · Answer 4

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]

akljfhnlaflkj SSC Guru Points: 76202 More actions · Answer 5

akljfhnlaflkj

SSC Guru

Points: 76202

May 12, 2015 at 8:49 am

#1797298

Love those Tally tables

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 6

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.

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

j-1064772 SSCertifiable Points: 5316 More actions · Answer 7

j-1064772

SSCertifiable

Points: 5316

May 21, 2015 at 2:49 pm

#1799841

Thanks for the link to newest string splitter.

Alan Burstein SSC Guru Points: 61136 More actions · Answer 8

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)

) 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