Finding Nth Occurrence Positions in Strings Using Recursive CTE in SQL Server

Problem Background and Requirements Analysis

In database development, there is frequent need to process string data containing specific delimiters. As shown in the examples of filenames like abc_1_2_3_4.gif and zzz_12_3_3_45.gif, where the underscore _ serves as a field separator. Accurately locating each underscore position is crucial for subsequent string splitting and data extraction.

The traditional CHARINDEX function can only return the first occurrence position, while actual business scenarios often require obtaining all occurrence positions. Although nested calls to CHARINDEX can achieve this, the approach becomes complex and difficult to maintain when the number of occurrences is uncertain or large.

Detailed Explanation of Recursive CTE Solution

Recursive Common Table Expressions (CTE) provide an elegant solution for such problems. The core concept involves recursively traversing the string to progressively locate each target character position.

Basic Implementation

First, create a test data table and insert sample data:

SELECT 'abc_1_2_3_4.gif' AS img INTO #T
INSERT #T VALUES ('zzz_12_3_3_45.gif')

Then use recursive CTE for position finding:

;WITH T AS (
    SELECT 0 AS row, CHARINDEX('_', img) pos, img FROM #T
    UNION ALL
    SELECT pos + 1, CHARINDEX('_', img, pos + 1), img
    FROM T
    WHERE pos > 0
)
SELECT img, pos FROM T WHERE pos > 0 ORDER BY img, pos

The execution results clearly show all underscore positions in each filename:

img                 pos
abc_1_2_3_4.gif     4
abc_1_2_3_4.gif     6
abc_1_2_3_4.gif     8
abc_1_2_3_4.gif     10
zzz_12_3_3_45.gif   4
zzz_12_3_3_45.gif   7
zzz_12_3_3_45.gif   9
zzz_12_3_3_45.gif   11

Recursive Process Analysis

The recursive CTE execution consists of two phases:

Anchor Member: Initializes the query using CHARINDEX('_', img) to find the first underscore position.

Recursive Member: Continues searching from the next character of the previous position using CHARINDEX('_', img, pos + 1).

The recursion termination condition is WHERE pos > 0, stopping when CHARINDEX returns 0 (indicating not found).

Extended Application: String Splitting

Building upon locating all delimiter positions, string splitting functionality can be further implemented:

;WITH T(img, starts, pos) AS (
    SELECT img, 1, CHARINDEX('_', img) FROM #t
    UNION ALL
    SELECT img, pos + 1, CHARINDEX('_', img, pos + 1)
    FROM t
    WHERE pos > 0
)
SELECT *, SUBSTRING(img, starts, 
    CASE WHEN pos > 0 THEN pos - starts ELSE LEN(img) END) token
FROM T
ORDER BY img, starts

This query not only returns position information but also extracts individual fields using the SUBSTRING function:

img                 starts  pos     token
abc_1_2_3_4.gif     1       4       abc
abc_1_2_3_4.gif     5       6       1
abc_1_2_3_4.gif     7       8       2
abc_1_2_3_4.gif     9       10      3
abc_1_2_3_4.gif     11      0       4.gif
zzz_12_3_3_45.gif   1       4       zzz
zzz_12_3_3_45.gif   5       7       12
zzz_12_3_3_45.gif   8       9       3
zzz_12_3_3_45.gif   10      11      3
zzz_12_3_3_45.gif   12      0       45.gif

Performance Analysis and Optimization

The recursive CTE method performs well with medium-length strings, but for very long strings or high-frequency invocation scenarios, consider the following optimization strategies:

Tally Table Method

As mentioned in the reference article, using a numbers table approach can avoid recursion through pre-generated number sequences:

WITH Occurrences AS (
    SELECT Number,
    ROW_NUMBER() OVER(ORDER BY Number) AS Occurrence
    FROM master.dbo.spt_values
    WHERE Number BETWEEN 1 AND LEN(@SearchedStr) AND type='P'
    AND SUBSTRING(@SearchedStr,Number,LEN(@TargetStr))=@TargetStr
)
SELECT Number FROM Occurrences WHERE Occurrence=@Occurrence

This method may offer better performance in certain scenarios, particularly when frequently querying specific Nth occurrences.

Inline Tally Table

To avoid dependency on system tables, use inline CTE to generate number sequences:

WITH E1(N) AS (SELECT N FROM (VALUES(1),(1),(1),(1),(1),(1),(1),(1),(1),(1))x(N)),
E2(N) AS (SELECT 1 FROM E1 a, E1 b),
E4(N) AS (SELECT 1 FROM E2 a, E2 b),
cteTally(N) AS (
    SELECT TOP (ISNULL(DATALENGTH(@SearchedStr),0)) 
    ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E4
)

Comparison with Alternative Methods

Nested CHARINDEX Method

As shown in Answer 1 from the Q&A data, subsequent occurrence positions can be found through nested CHARINDEX calls:

CHARINDEX('_', [TEXT], (CHARINDEX('_', [TEXT], 1))+1)

This approach is straightforward but becomes verbose and difficult to maintain when multiple positions need to be found.

User-Defined Function Method

Answer 3 demonstrates creating user-defined functions, but there is potential risk of infinite loops. The fixes mentioned in the reference article:

WHILE (@counter < @Occurrence) AND @pos <> 0

And:

IF @pos = 0 SET @counter = @Occurrence

These fixes ensure function correctness, but performance may not match set-based approaches.

Practical Application Scenarios

The techniques introduced in this article have significant application value in the following scenarios:

File Path Parsing: Processing file paths containing directory separators to extract filename, extension, and other information.

Log Analysis: Parsing structured log records to extract key fields for statistical analysis.

Data Cleaning: Processing text data with multiple delimiters for standardization and normalization.

URL Processing: Parsing URL parameters to extract individual parameter values from query strings.

Best Practice Recommendations

Based on this analysis and practical experience, the following best practices are recommended:

Performance Considerations: For scenarios with known maximum occurrence counts, recursive CTE is typically the best choice. For unknown counts or very long strings, consider the numbers table method.

Error Handling: Always check CHARINDEX return values to avoid logical errors when target characters are not found.

Code Readability: Add appropriate comments in complex queries to explain recursive logic and termination conditions.

Test Coverage: Ensure test cases include boundary conditions such as empty strings, absent target characters, and target characters at the beginning or end.

Conclusion

Using recursive CTE combined with the CHARINDEX function provides an efficient solution for finding Nth occurrence positions in strings within SQL Server. This method not only offers clear and understandable code but also has good scalability, easily handling various complex string processing requirements. In practical applications, choose the most suitable implementation based on specific scenarios and follow best practices to ensure code performance and reliability.