Multiple String REPLACEs with T-SQL CTEs (2)

My algorithm on replacing multiple strings in an SQL Server table works in principle, but soon after publishing the article, I noticed that it has terrible performance once you define more than just 2 or 3 text translations.

Originally I thought it would be a good idea to calculate all permutations of replacements, so that the “best” permutation of an original string would win, but as it turned it: it is not.

The core of the problem is that the LIKE operation creates a recursion to the order of n factorial! I guess that’s one of the least efficient solutions I’ve ever written.

New approach: the translation table contains a sequence identifier, and its translations are thus executed in the given order.

CREATE TABLE #T (
    level INT IDENTITY(1,1),
    old NVARCHAR(50),
    new NVARCHAR(50)
)

CREATE TABLE #Data (
	data NVARCHAR(50)
)

I named the column “level” because it is joined with the level counter of the CTE. The Identity clause causes the translations to the performed in the order of the INSERT statements.

The new CTE with ordered translations:

WITH CTE (org, calc, data, level) AS
(
    SELECT data, data, data, 1
    FROM	#Data
	
    UNION ALL
	
    SELECT CTE.org, CTE.data, 
        CONVERT(NVARCHAR(50), REPLACE(CTE.data, #T.old, #T.new)), 
        CTE.level + 1
    FROM	CTE
    INNER JOIN #T ON #T.level = CTE.level
)
SELECT DISTINCT org, data
FROM CTE
WHERE level = 
    (SELECT MAX(LEVEL) FROM CTE c WHERE CTE.org = c.org)

2 Responses to Multiple String REPLACEs with T-SQL CTEs (2)

  1. […] Cyrillic into Latin alphabet with T-SQL After sketching my CTE-based multi-REPLACE procedure, I wanted to test in on a real-life scenario. First example is a translation table to convert the […]

  2. […] Kana into Latin alphabet using T-SQL One more example of replacing multiple strings using a CTE. After Russian / Cyrillic, it’s time for the Japanese […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: