Actualización lenta en tabla grande con subconsulta

Con SourceTabletener> 15MM registros y Bad_Phrasetener> 3K registros, la siguiente consulta tarda casi 10 horas en ejecutarse en SQL Server 2005 SP4.

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

En inglés, esta consulta cuenta el número de frases distintas enumeradas en Bad_Phrase que son una subcadena del campo Nameen SourceTabley luego coloca ese resultado en el campo Bad_Count.

Quisiera algunas sugerencias sobre cómo hacer que esta consulta se ejecute considerablemente más rápido.

Aunque estoy de acuerdo con otros comentaristas que este es un problema computacionalmente caro, creo que hay mucho margen de mejora por ajustar el SQL que está utilizando. Para ilustrar esto, se crea un conjunto de datos falsos con nombres 15MM y 3K frases, corrió el enfoque de edad, y corrió un nuevo enfoque.

Script completo para generar un conjunto de datos falsos y probar el nuevo enfoque

TL; DR

En mi máquina y este conjunto de datos falsos, el enfoque original tarda aproximadamente 4 horas en ejecutarse. La propuesta de nuevo enfoque toma alrededor de 10 minutos , una mejora considerable. Aquí hay un breve resumen del enfoque propuesto:

• Para cada nombre, generar la subcadena que empieza en cada desplazamiento de caracteres (y un tope de la longitud de la frase más larga mala, como una optimización)
• Crear un índice agrupado en estas subcadenas
• Para cada frase mal, realice un buscar en estas subseries para identificar las coincidencias
• Para cada cadena original, calcular el número de frases malas distintas que coincide con uno o más subseries de esa cadena

enfoque original: análisis algorítmico

Del plan de la UPDATEdeclaración original , podemos ver que la cantidad de trabajo es linealmente proporcional tanto a la cantidad de nombres (15MM) como a la cantidad de frases (3K). Entonces, si multiplicamos el número de nombres y frases por 10, el tiempo de ejecución general será ~ 100 veces más lento.

La consulta es realmente proporcional a la longitud de la nameasí; Si bien esto está un poco oculto en el plan de consulta, aparece en el "número de ejecuciones" para buscar en el carrete de la tabla. En el plan real, podemos ver que esto ocurre no solo una vez por name, sino en realidad una vez por desplazamiento de carácter dentro de name. Así que este enfoque es O ( # names* # phrases* name length) de la complejidad en tiempo de ejecución.

Nuevo enfoque: Código

Este código también está disponible en el pleno Pastebin pero he copiado aquí por conveniencia. El Pastebin también tiene la definición del procedimiento completo, que incluye el @minIdy @maxIdlas variables que se ven a continuación para definir los límites del lote actual.

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

Nuevo enfoque: los planes de consulta

Primero, generamos la subcadena comenzando en cada desplazamiento de caracteres

Luego cree un índice agrupado en estas subcadenas

Ahora, para cada frase incorrecta buscamos en estas subcadenas para identificar cualquier coincidencia. Luego calculamos el número de frases malas distintas que coinciden con una o más subcadenas de esa cadena. Este es realmente el paso clave; Debido a la forma en que hemos indexado las subcadenas, ya no tenemos que verificar un producto cruzado completo de frases y nombres malos. Este paso, que realiza el cálculo real, representa solo alrededor del 10% del tiempo de ejecución real (el resto es el preprocesamiento de las subcadenas).

Por último, realice la declaración de actualización real, utilizando a LEFT OUTER JOINpara asignar un recuento de 0 a cualquier nombre para el que no encontramos frases malas.

Nuevo enfoque: análisis algorítmico

El nuevo enfoque se puede dividir en dos fases, preprocesamiento y coincidencia. Definamos las siguientes variables:

• N = # De nombres
• B = # de frases malas
• L = longitud promedio del nombre, en caracteres

La fase de pre-procesamiento es O(N*L * LOG(N*L))con el fin de crear N*Lsubseries y luego ordenarlos.

El juego real es O(B * LOG(N*L))con el fin de buscar en las subseries para cada frase mal.

De esta manera, hemos creado un algoritmo que no se escala linealmente con el número de frases malas, un desbloqueo clave del rendimiento a medida que escalamos a frases de 3K y más. Dicho de otra manera, la implementación original demora aproximadamente 10 veces siempre que pasemos de 300 frases malas a 3K frases malas. Del mismo modo, tomaría otros 10 veces más si pasáramos de 3K frases malas a 30K. La nueva implementación, sin embargo, se ampliará de forma sub-lineal y, de hecho, toma menos del doble del tiempo medido en 3K frases malas cuando se escala hasta 30K frases malas.

Supuestos / Advertencias

• Estoy dividiendo el trabajo general en lotes de tamaño modesto. Esta es probablemente una buena idea para cualquiera de los enfoques, pero es especialmente importante para el nuevo enfoque, de modo que SORTen las subcadenas sea independiente para cada lote y quepa fácilmente en la memoria. Puede manipular el tamaño del lote según sea necesario, pero no sería aconsejable probar todas las filas de 15MM en un lote.
• Estoy en SQL 2014, no en SQL 2005, ya que no tengo acceso a una máquina SQL 2005. He tenido cuidado de no utilizar cualquier sintaxis que no está disponible en SQL 2005, pero todavía podría estar recibiendo un beneficio de la escritura diferida tempdb función en SQL 2012+ y el paralelo SELECT INTO función en SQL 2014.
• La longitud de los nombres y frases es bastante importante para el nuevo enfoque. Supongo que las frases malas suelen ser bastante cortas, ya que es probable que coincidan con los casos de uso del mundo real. Los nombres son bastante más largos que las frases malas, pero se supone que no son miles de caracteres. Creo que esta es una suposición justa, y las cadenas de nombre más largas también ralentizarían su enfoque original.
• Una parte de la mejora (pero nada cerca de todo esto) se debe al hecho de que el nuevo enfoque puede aprovechar el paralelismo de manera más efectiva que el enfoque anterior (que funciona con un solo subproceso). Estoy en una computadora portátil de cuatro núcleos, por lo que es bueno tener un enfoque que pueda usar estos núcleos.

Publicación de blog relacionada

Aaron Bertrand explora este tipo de solución con más detalle en su publicación de blog. Una forma de obtener un índice para buscar un% comodín líder .

Vamos a dejar de lado la cuestión obvia criado por Aaron Bertrand en los comentarios de un segundo:

Entonces, ¿está escaneando la tabla 3K veces y potencialmente actualizando todas las filas de 15MM todas las 3K veces, y espera que sea rápido?

El hecho de que su subconsulta utiliza los comodines en ambos lados afecta dramáticamente sargability . Para tomar una cita de esa publicación de blog:

Eso significa que SQL Server tiene que leer cada fila de la tabla Producto, verificar si tiene "tuerca" en cualquier parte del nombre y luego devolver nuestros resultados.

Cambie la palabra "tuerca" por cada "mala palabra" y "Producto" para SourceTable, luego combine eso con el comentario de Aaron y debería comenzar a ver por qué es extremadamente difícil (lectura imposible) hacer que se ejecute rápidamente utilizando su algoritmo actual.

Veo algunas opciones:

1. Convencer a las empresas para que compren un servidor monstruo que tenga tanto poder que supere la consulta por fuerza bruta de corte. (Eso no va a suceder, así que cruza los dedos, las otras opciones son mejores)
2. Usando su algoritmo existente, acepte el dolor una vez y luego extiéndalo. Esto implicaría calcular las palabras malas en la inserción, lo que ralentizará las inserciones y solo actualizará toda la tabla cuando se ingrese / descubra una nueva palabra mala.
3. Acepta la respuesta de Geoff . Este es un gran algoritmo, y mucho mejor que cualquier cosa que hubiera inventado.
4. Haga la opción 2 pero sustituya su algoritmo por el de Geoff.

Dependiendo de sus requisitos, recomendaría la opción 3 o 4.

primero eso es solo una actualización extraña

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] te está matando
Eso no puede usar un índice

El diseño de los datos no es óptimo para la velocidad.
¿Puede dividir [Bad_Phrase]. [PHRASE] en una (s) frase (s) / palabra?
Si la misma frase / palabra aparece más de una, puede ingresarla más de una vez si desea que tenga un recuento más alto.
Entonces, el número de filas en mala frase aumentaría.
Si puede, esto será mucho más 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]

No estoy seguro si 2005 lo admite, pero el índice de texto completo y el uso contiene