Atualização lenta na tabela grande com subconsulta

Com SourceTableregistros> 15MM e registros Bad_Phrase> 3K, a consulta a seguir leva quase 10 horas para ser executada no SQL Server 2005 SP4.

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

Em inglês, essa consulta está contando o número de frases distintas listadas em Bad_Phrase que são uma substring do campo Nameno SourceTablee, em seguida, colocando esse resultado no campo Bad_Count.

Gostaria de algumas sugestões sobre como executar essa consulta consideravelmente mais rápido.

Embora eu concorde com outros comentadores de que este é um problema computacionalmente caro, acho que há muito espaço para melhorias, aprimorando o SQL que você está usando. Para ilustrar, criei um conjunto de dados falso com nomes de 15MM e frases de 3K, executei a abordagem antiga e uma nova abordagem.

Script completo para gerar um conjunto de dados falso e experimentar a nova abordagem

TL; DR

Na minha máquina e neste conjunto de dados falsos, a abordagem original leva cerca de 4 horas para ser executada. A nova abordagem proposta leva cerca de 10 minutos , uma melhoria considerável. Aqui está um breve resumo da abordagem proposta:

• Para cada nome, gere a substring começando em cada deslocamento de caractere (e limitado no comprimento da frase incorreta mais longa, como uma otimização)
• Crie um índice em cluster nessas substrings
• Para cada frase incorreta, faça uma busca nessas substrings para identificar quaisquer correspondências
• Para cada sequência original, calcule o número de frases incorretas distintas que correspondem a uma ou mais substrings dessa sequência

Abordagem original: análise algorítmica

No plano da UPDATEdeclaração original , podemos ver que a quantidade de trabalho é linearmente proporcional ao número de nomes (15MM) e ao número de frases (3K). Portanto, se multiplicarmos o número de nomes e frases por 10, o tempo de execução geral será aproximadamente 100 vezes mais lento.

A consulta também é proporcional ao comprimento da name; Embora isso esteja um pouco oculto no plano de consulta, ele aparece no "número de execuções" para procurar no spool da tabela. No plano real, podemos ver que isso ocorre não apenas uma vez por name, mas na verdade uma vez por deslocamento de caractere dentro do name. Portanto, essa abordagem é O ( # names* # phrases* name length) na complexidade do tempo de execução.

Nova abordagem: código

Esse código também está disponível no pastebin completo, mas eu o copiei aqui por conveniência. O pastebin também possui a definição completa do procedimento, que inclui as variáveis @minIde @maxIdque você vê abaixo para definir os limites do lote atual.

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

Nova abordagem: planos de consulta

Primeiro, geramos a substring começando em cada deslocamento de caractere

Em seguida, crie um índice em cluster nessas substrings

Agora, para cada frase ruim, procuramos nessas substrings para identificar quaisquer correspondências. Em seguida, calculamos o número de frases ruins distintas que correspondem a uma ou mais substrings dessa sequência. Este é realmente o passo chave; devido à maneira como indexamos as substrings, não precisamos mais verificar um produto cruzado completo de frases e nomes ruins. Esta etapa, que faz o cálculo real, responde por apenas cerca de 10% do tempo de execução real (o restante é o pré-processamento de substrings).

Por fim, execute a instrução de atualização real, usando a LEFT OUTER JOINpara atribuir uma contagem de 0 a qualquer nome para o qual não encontramos frases ruins.

Nova abordagem: análise algorítmica

A nova abordagem pode ser dividida em duas fases, pré-processamento e correspondência. Vamos definir as seguintes variáveis:

• N = número de nomes
• B = # de frases ruins
• L = comprimento médio do nome, em caracteres

A fase de pré-processamento é O(N*L * LOG(N*L))para criar N*Lsubstrings e depois classificá-los.

A correspondência real é O(B * LOG(N*L))para procurar nas substrings para cada frase incorreta.

Dessa maneira, criamos um algoritmo que não é escalável linearmente com o número de frases ruins, um desbloqueio de desempenho importante à medida que escalamos para frases 3K e além. Dito de outra maneira, a implementação original leva aproximadamente 10x, desde que passemos de 300 frases ruins para 3K frases ruins. Da mesma forma, levaria mais 10 vezes mais tempo se passássemos de 3 mil frases ruins para 30 mil. A nova implementação, no entanto, aumentará de forma sub-linear e, na verdade, leva menos de duas vezes o tempo medido em 3 mil frases ruins quando escalado até 30 mil frases ruins.

Pressupostos / Advertências

• Estou dividindo o trabalho geral em lotes de tamanho modesto. Provavelmente, essa é uma boa idéia para qualquer uma das abordagens, mas é especialmente importante para a nova abordagem, para que SORTas substrings sejam independentes para cada lote e se ajustem facilmente à memória. Você pode manipular o tamanho do lote conforme necessário, mas não seria prudente tentar todas as 15MM linhas em um lote.
• Estou no SQL 2014, não no SQL 2005, pois não tenho acesso a uma máquina SQL 2005. Tomei cuidado para não usar nenhuma sintaxe que não esteja disponível no SQL 2005, mas ainda posso estar me beneficiando do recurso de gravação lenta tempdb no SQL 2012+ e do recurso SELECT INTO paralelo no SQL 2014.
• A extensão dos nomes e frases é bastante importante para a nova abordagem. Estou assumindo que as frases ruins são geralmente bastante curtas, pois provavelmente corresponderão a casos de uso do mundo real. Os nomes são um pouco mais longos que as frases ruins, mas supõe-se que não sejam milhares de caracteres. Eu acho que essa é uma suposição justa, e cadeias de nomes mais longas desacelerariam sua abordagem original também.
• Parte da melhoria (mas nem um pouco próxima disso) se deve ao fato de que a nova abordagem pode alavancar o paralelismo com mais eficiência do que a abordagem antiga (que é executada em thread único). Eu estou em um laptop quad core, então é bom ter uma abordagem que possa colocar esses núcleos em uso.

Post do blog relacionado

Aaron Bertrand explora esse tipo de solução com mais detalhes em sua postagem no blog. Uma maneira de obter uma pesquisa de índice para um% curinga líder .

Vamos arquivar a questão óbvia levantada por Aaron Bertrand nos comentários por um segundo:

Então, você está varrendo a tabela 3K vezes e potencialmente atualizando todas as linhas de 15MM todas as 3K vezes, e espera que seja rápido?

O fato de sua subconsulta usar os curingas de ambos os lados afeta drasticamente a sargabilidade . Para fazer uma cotação dessa postagem no blog:

Isso significa que o SQL Server precisa ler todas as linhas da tabela Produto, verificar se há "porcas" em qualquer lugar do nome e retornar nossos resultados.

Troque a palavra "porca" por cada "palavra ruim" e "Produto" para SourceTable, em seguida, combine isso com o comentário de Aaron e comece a ver por que é extremamente difícil ( não é possível ler) fazer com que seja executado rapidamente usando o algoritmo atual.

Vejo algumas opções:

1. Convença as empresas a comprar um servidor monstro com tanto poder que supera a consulta por força bruta de cisalhamento. (Isso não vai acontecer, então cruze os dedos para que outras opções sejam melhores)
2. Usando seu algoritmo existente, aceite a dor uma vez e depois espalhe-a. Isso envolveria o cálculo de palavrões na inserção, o que reduzirá a velocidade as inserções e somente atualizará a tabela inteira quando uma nova palavra incorreta for inserida / descoberta.
3. Aceite a resposta de Geoff . Este é um ótimo algoritmo, e muito melhor do que qualquer coisa que eu teria inventado.
4. Faça a opção 2, mas substitua seu algoritmo pelo de Geoff.

Dependendo dos seus requisitos, eu recomendaria a opção 3 ou 4.

primeiro que é apenas uma atualização estranha

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

Como '%' + [Bad_Phrase]. [PHRASE] está matando você
Isso não pode usar um índice

O design dos dados não é ideal para velocidade
Você pode dividir a [Bad_Phrase]. [PHRASE] em uma única frase / palavras?
Se a mesma frase / palavra aparecer mais de uma, você poderá inseri-la mais de uma vez, se desejar que ela tenha uma contagem mais alta.
Portanto, o número de linhas em má posição aumentaria.
Se você puder, isso será muito mais rápido.

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]

Não tenho certeza se 2005 o suporta, mas o Índice de texto completo e o uso Contém