SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


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


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

Author
Message
Steven Willis
Steven Willis
SSCrazy
SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)

Group: General Forum Members
Points: 2081 Visits: 1721
Comments posted to this topic are about the item Find the position of all occurrences of an expression within a string
Sean Smith (SSC)
Sean Smith (SSC)
UDP Broadcaster
UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)

Group: General Forum Members
Points: 1474 Visits: 1012
Just plain AWESOME!
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)

Group: General Forum Members
Points: 218560 Visits: 41997
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.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
Steven Willis
Steven Willis
SSCrazy
SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)

Group: General Forum Members
Points: 2081 Visits: 1721
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
)






 
j-1064772
j-1064772
Ten Centuries
Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)

Group: General Forum Members
Points: 1287 Visits: 1213
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.


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[size="3"][/size]

Iwas Bornready
Iwas Bornready
SSC-Insane
SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)

Group: General Forum Members
Points: 22616 Visits: 885
Love those Tally tables
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)SSC Guru (218K reputation)

Group: General Forum Members
Points: 218560 Visits: 41997
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.


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[size="3"][/size]


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.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
j-1064772
j-1064772
Ten Centuries
Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)

Group: General Forum Members
Points: 1287 Visits: 1213
Thanks for the link to newest string splitter.
Alan.B
Alan.B
SSChampion
SSChampion (13K reputation)SSChampion (13K reputation)SSChampion (13K reputation)SSChampion (13K reputation)SSChampion (13K reputation)SSChampion (13K reputation)SSChampion (13K reputation)SSChampion (13K reputation)

Group: General Forum Members
Points: 13630 Visits: 8013
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.

-- Alan Burstein



Best practices for getting help on SQLServerCentral
Need to split a string? Try DelimitedSplit8K or DelimitedSplit8K_LEAD (SQL 2012+)
Need a pattern-based splitter? Try PatternSplitCM
Need to remove or replace those unwanted characters? Try PatExclude8K and PatReplace8K.

"I can't 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. " -- Itzek Ben-Gan 2001
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search