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".
    "Dear Lord... I'm a DBA so please give me patience because, if you give me strength, I'm going to need bail money too!"

    Helpful Links:
    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".
    "Dear Lord... I'm a DBA so please give me patience because, if you give me strength, I'm going to need bail money too!"

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

  • Thanks for the link to newest string splitter.

  • 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 9 (of 9 total)

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