16

With SourceTable having >15MM records and Bad_Phrase having >3K records, the following query takes almost 10 hours to run on SQL Server 2005 SP4.

UPDATE [SourceTable] 
SET 
    Bad_Count=
             (
               SELECT 
                  COUNT(*) 
               FROM Bad_Phrase 
               WHERE 
                  [SourceTable].Name like '%'+Bad_Phrase.PHRASE+'%'
             )

In English, this query is counting the number of distinct phrases listed in Bad_Phrase that are a substring of the field Name in the SourceTable and then placing that result in the field Bad_Count.

I would like some suggestions on how to have this query run considerably faster.

  • 3
    So you are scanning the table 3K times, and potentially updating all 15MM rows all 3K times, and you expect it to be fast? – Aaron Bertrand Sep 23 '15 at 23:19
  • 1
    What is the length of the name column? Can you post a script or SQL fiddle that generates test data and reproduces this very slow query in a way that any of us can play with? Maybe I'm just an optimist, but I feel like we can do far better than 10 hours. I do agree with the other commenters that this is a computationally expensive problem, but I don't see why we can't still aim to make it "considerably faster". – Geoff Patterson Sep 24 '15 at 3:02
  • 3
    Matthew, have you considered full text indexing? You can used things like CONTAINS and still get the benefit of indexing for that search. – swasheck Sep 24 '15 at 3:17
  • In this case I'd suggest trying row-based logic (i.e. instead of 1 update of 15MM rows do 15MM updates each row in SourceTable, or update some relatively small chunks ). Total time is not gonna be faster (even though it's possible in this particular case), but such an approach allows the rest of the system continue working without any interruptions, gives you control over transaction log size (say commit every 10k updates), interrupt update at any time without losing all previous updates... – a1ex07 Sep 24 '15 at 14:46
  • 2
    @swasheck Full-text is a good idea to consider (it's new in 2005 I believe, so could be applicable here), but it wouldn't be possible to provide the same functionality the poster asked for since full-text indexes words and not arbitrary substrings. Said another way, full-text wouldn't find a match for "ant" within the word "fantastic". But it may be possible that the business requirements could be modified so that full-text becomes applicable. – Geoff Patterson Sep 25 '15 at 15:56
21
+100

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.

enter image description here


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

enter image description here

Then create a clustered index on these substrings

enter image description here

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).

enter image description here

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.

enter image description here


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 names
  • B = # of bad phrases
  • L = 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.

6

Let's shelve the obvious issue brought up by Aaron Bertrand in the comments for a second:

So you are scanning the table 3K times, and potentially updating all 15MM rows all 3K times, and you expect it to be fast?

The fact that your subquery uses the wild cards on both sides dramatically affects sargability. To take a quote from that blog post:

That means SQL Server has to read every row out of the Product table, check to see whether it’s got “nut” anywhere in the name, and then return our results.

Swap out the word "nut" for each "bad word" and "Product" for SourceTable, then combine that with Aaron's comment and you should start to see why it is extremely hard (read impossible) to make it run quickly using your current algorithm.

I see a few options:

  1. Convince business to buy a monster server that has so much power that it overcomes the query by shear brute force. (That isn't going to happen so cross your fingers the other options are better)
  2. Using your existing algorithm, accept the pain once and then spread it out. This would involve calculating the bad words on insert which will slow down inserts, and only update the whole table when a new bad word is entered/discovered.
  3. Embrace Geoff's answer. This is a great algorithm, and much better than anything I would have come up with.
  4. Do option 2 but substitute your algorithm with Geoff's.

Depending on your requirements I would recommend either option 3 or 4.

0

first that is just a strange update

Update [SourceTable]  
   Set [SourceTable].[Bad_Count] = [fix].[count]
  from [SourceTable] 
  join ( Select count(*) 
           from [Bad_Phrase]  
          where [SourceTable].Name like '%' + [Bad_Phrase].[PHRASE] + '%')

Like '%' + [Bad_Phrase].[PHRASE] is killing you
That cannot use an index

The data design is not optimal for speed
Can you break the [Bad_Phrase].[PHRASE] up into single phrase(s) / word?
If the same phrase / word appears more than one you can enter it more than once if you want it to have a higher count
So the number of rows in bad pharase would go up
If you can then this will be much much faster

Update [SourceTable]  
   Set [SourceTable].[Bad_Count] = [fix].[count]
  from [SourceTable] 
  join ( select [PHRASE], count(*) as count 
           from [Bad_Phrase] 
          group by [PHRASE] 
       ) as [fix]
    on [fix].[PHRASE] = [SourceTable].[name]  
 where [SourceTable].[Bad_Count] <> [fix].[count]

Not sure if 2005 supports it but Full Text Index and use Contains

  • 1
    I don't think the OP wants to count the instances of the bad word in the bad word table I think they want to count the number of bad words hidden in the source table. For example the original code would probably give a count of 2 for a name of "shitass" but your code would give a count of 0. – Erik Sep 24 '15 at 2:00
  • 1
    @Erik "can you break the [Bad_Phrase].[PHRASE] up into single phrase(s)?" Really you don't think a data design might be the fix? If the purpose is to find bad stuff then "eriK" with a count of one or more is enough. – paparazzo Sep 24 '15 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.