While I agree with other commenters that this is a computationally expensive problem, I think that there is a lot of room for improvement by tweaking the SQL that you are using. To illustrate, I create a fake data set with 15MM names and 3K phrases, ran the old approach, and ran a new approach.
Full script to generate a fake data set and try out the new approach
TL;DR
On my machine and this fake data set, the original approach takes about 4 hours to run. The proposed new approach takes about 10 minutes, a considerable improvement. Here is a short summary of the proposed approach:
- For each name, generate the substring starting at each character offset (and capped at the length of the longest bad phrase, as an optimization)
- Create a clustered index on these substrings
- For each bad phrase, perform a seek into these substrings to identify any matches
- For each original string, compute the number of distinct bad phrases that matches one or more substrings of that string
Original approach: algorithmic analysis
From the plan of the original UPDATE statement, we can see that the amount of work is linearly proportional to both the number of names (15MM) and the number of phrases (3K). So if we multiple both the number of names and phrases by 10, the overall run time is going to be ~100 times slower.
The query is actually proportional to the length of the name as well; while this is a bit hidden in the query plan, it comes through in the "number of executions" for seeking into the table spool. In the actual plan, we can see that this occurs not just once per name, but actually once per character offset within the name. So this approach is O(# names * # phrases * name length) in run-time complexity.
New approach: code
This code is also available in the full pastebin but I've copied it here for convenience. The pastebin also has the full procedure definition, which includes the @minId and @maxId variables that you see below to define the boundaries of the current batch.
-- For each name, generate the string at each offset
DECLARE @maxBadPhraseLen INT = (SELECT MAX(LEN(phrase)) FROM Bad_Phrase)
SELECT s.id, sub.sub_name
INTO #SubNames
FROM (SELECT * FROM SourceTable WHERE id BETWEEN @minId AND @maxId) s
CROSS APPLY (
-- Create a row for each substring of the name, starting at each character
-- offset within that string. For example, if the name is "abcd", this CROSS APPLY
-- will generate 4 rows, with values ("abcd"), ("bcd"), ("cd"), and ("d"). In order
-- for the name to be LIKE the bad phrase, the bad phrase must match the leading X
-- characters (where X is the length of the bad phrase) of at least one of these
-- substrings. This can be efficiently computed after indexing the substrings.
-- As an optimization, we only store @maxBadPhraseLen characters rather than
-- storing the full remainder of the name from each offset; all other characters are
-- simply extra space that isn't needed to determine whether a bad phrase matches.
SELECT TOP(LEN(s.name)) SUBSTRING(s.name, n.n, @maxBadPhraseLen) AS sub_name
FROM Numbers n
ORDER BY n.n
) sub
-- Create an index so that bad phrases can be quickly compared for a match
CREATE CLUSTERED INDEX IX_SubNames ON #SubNames (sub_name)
-- For each name, compute the number of distinct bad phrases that match
-- By "match", we mean that the a substring starting from one or more
-- character offsets of the overall name starts with the bad phrase
SELECT s.id, COUNT(DISTINCT b.phrase) AS bad_count
INTO #tempBadCounts
FROM dbo.Bad_Phrase b
JOIN #SubNames s
ON s.sub_name LIKE b.phrase + '%'
GROUP BY s.id
-- Perform the actual update into a "bad_count_new" field
-- For validation, we'll compare bad_count_new with the originally computed bad_count
UPDATE s
SET s.bad_count_new = COALESCE(b.bad_count, 0)
FROM dbo.SourceTable s
LEFT JOIN #tempBadCounts b
ON b.id = s.id
WHERE s.id BETWEEN @minId AND @maxId
New approach: query plans
First, we generate the substring starting at each character offset
Then create a clustered index on these substrings
Now, for each bad phrase we seek into these substrings to identify any matches. We then compute the number of distinct bad phrases that matches one or more substrings of that string. This is really the key step; because of the way that we have indexed the substrings, we no longer have to check a full cross-product of bad phrases and names. This step, which does the actual computation, accounts for only about 10% of the actual run-time (the rest is the pre-processing of substrings).
Lastly, perform the actual update statement, using a LEFT OUTER JOIN to assign a count of 0 to any names for which we found no bad phrases.
New approach: algorithmic analysis
The new approach can be divided into two phases, pre-processing and matching. Let's define the following variables:
N = # of namesB = # of bad phrasesL = average name length, in characters
The pre-processing phase is O(N*L * LOG(N*L)) in order to create N*L substrings and then sort them.
The actual matching is O(B * LOG(N*L)) in order to seek into the substrings for each bad phrase.
In this way, we have created an algorithm that does not scale linearly with the number of bad phrases, a key performance unlock as we scale to 3K phrases and beyond. Said another way, the original implementation takes roughly 10x as long as we go from 300 bad phrases to 3K bad phrases. Similarly it would take another 10x as long if we were to go from 3K bad phrases to 30K. The new implementation, however, will scale up sub-linearly and in fact takes less than 2x the time measured on 3K bad phrases when scaled up to 30K bad phrases.
Assumptions / Caveats
- I am dividing the overall work into modestly sized batches. This is probably a good idea for either approach, but it is especially important for the new approach so that the
SORT on the substrings is independent for each batch and easily fits in memory. You can manipulate the batch size as needed, but it would not be wise to try all 15MM rows in one batch.
- I am on SQL 2014, not SQL 2005, since I don't have access to a SQL 2005 machine. I have been careful not to use any syntax that is not available in SQL 2005, but I may still be getting a benefit from the tempdb lazy write feature in SQL 2012+ and the parallel SELECT INTO feature in SQL 2014.
- The lengths of both the names and phrases is fairly important to the new approach. I'm assuming that the bad phrases are typically fairly short since that is likely to match real-world use cases. The names are quite a bit longer than the bad phrases, but are assumed not to be thousands of characters. I think this is a fair assumption, and longer name strings would slow down your original approach as well.
- Some portion of the improvement (but nowhere close to all of it) is due to the fact that the new approach can leverage parallelism more effectively than the old approach (which runs single-threaded). I'm on a quad core laptop, so it is nice to have approach that can put these cores to use.
Related blog post
Aaron Bertrand explores this type of solution in more detail in his blog post One way to get an index seek for a leading %wildcard.
