Медленное обновление на большой таблице с подзапросом

Имея SourceTableзаписи> 15MM и записи Bad_Phrase> 3K, для выполнения следующего запроса на SQL Server 2005 SP4 требуется почти 10 часов.

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

В английском языке этот запрос подсчитывает количество различных фраз, перечисленных в Bad_Phrase, которые являются подстрокой поля Nameв, SourceTableи затем помещает этот результат в поле Bad_Count.

Я хотел бы получить несколько советов о том, как сделать этот запрос значительно быстрее.

Хотя я согласен с другими комментаторами в том, что это вычислительно дорогая проблема, я думаю, что есть много возможностей для улучшения путем настройки используемого вами SQL. Чтобы проиллюстрировать это, я создал поддельный набор данных с именами по 15 ММ и фразами по 3 КБ, применил старый подход и применил новый подход.

Полный сценарий для создания поддельного набора данных и опробовать новый подход

TL; DR

На моей машине и на этом поддельном наборе данных первоначальный подход занимает около 4 часов . Предлагаемый новый подход занимает около 10 минут , значительное улучшение. Вот краткое резюме предложенного подхода:

• Для каждого имени сгенерируйте подстроку, начинающуюся со смещения каждого символа (и ограниченную длиной самой длинной неверной фразы, в качестве оптимизации)
• Создайте кластерный индекс для этих подстрок
• Для каждой плохой фразы выполните поиск в этих подстроках, чтобы определить любые совпадения
• Для каждой исходной строки вычислите количество различных неверных фраз, соответствующих одной или нескольким подстрокам этой строки.

Оригинальный подход: алгоритмический анализ

Из плана исходного UPDATEутверждения видно, что объем работы линейно пропорционален как количеству имен (15 мм), так и количеству фраз (3 КБ). Таким образом, если мы умножим количество имен и фраз на 10, общее время выполнения будет примерно в 100 раз медленнее.

Запрос на самом деле пропорционален длине name; хотя это и немного скрыто в плане запроса, в «количестве выполнений» он находит поиск в спуле таблицы. В фактическом плане мы можем видеть, что это происходит не один раз для каждого name, а фактически один раз для каждого смещения символа в пределах name. Таким образом, этот подход O ( # names* # phrases* name length) в сложности времени выполнения.

Новый подход: код

Этот код также доступен в полном Pastebin , но я скопировал его здесь для удобства. Pastebin также имеет полное определение процедуры, который включает @minIdи @maxIdпеременные , которые вы видите ниже , чтобы определить границы текущей партии.

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

Новый подход: планы запросов

Сначала мы генерируем подстроку, начиная с каждого смещения символа

Затем создайте кластерный индекс для этих подстрок

Теперь для каждой плохой фразы мы ищем эти подстроки, чтобы определить совпадения. Затем мы вычисляем количество различных плохих фраз, которые соответствуют одной или нескольким подстрокам этой строки. Это действительно ключевой шаг; из-за того, как мы проиндексировали подстроки, нам больше не нужно проверять полный перекрестный продукт плохих фраз и имен. Этот шаг, который выполняет фактические вычисления, составляет только около 10% фактического времени выполнения (остальное - предварительная обработка подстрок).

Наконец, выполните фактический оператор обновления, используя a, LEFT OUTER JOINчтобы присвоить счетчик 0 любым именам, для которых мы не нашли плохих фраз.

Новый подход: алгоритмический анализ

Новый подход можно разделить на две фазы: предварительная обработка и сопоставление. Давайте определим следующие переменные:

• N = количество имен
• B = количество плохих фраз
• L = средняя длина имени в символах

Фаза предварительной обработки состоит O(N*L * LOG(N*L))в том, чтобы создать N*Lподстроки и затем отсортировать их.

Фактическое соответствие - O(B * LOG(N*L))это поиск подстрок для каждой плохой фразы.

Таким образом, мы создали алгоритм, который не масштабируется линейно с количеством плохих фраз, ключевая разблокировка производительности при масштабировании до 3K фраз и выше. Иными словами, исходная реализация занимает примерно 10 раз, если перейти от 300 плохих фраз к 3K плохим фразам. Точно так же потребовалось бы еще 10x, если бы мы перешли с 3K плохих фраз до 30K. Новая реализация, однако, будет увеличиваться сублинейно и на самом деле занимает менее чем в 2 раза больше времени, измеренного для 3K плохих фраз, когда масштабируется до 30K плохих фраз.

Предположения / предостережения

• Я делю всю работу на скромные партии. Вероятно, это хорошая идея для любого из этих подходов, но это особенно важно для нового подхода, чтобы SORTподстроки были независимыми для каждого пакета и легко помещались в памяти. Вы можете манипулировать размером пакета по мере необходимости, но было бы неразумно пробовать все 15-миллиметровые строки в одном пакете.
• Я использую SQL 2014, а не SQL 2005, поскольку у меня нет доступа к машине с SQL 2005. Я старался не использовать какой-либо синтаксис, который недоступен в SQL 2005, но я все еще могу получить выгоду от функции отложенной записи tempdb в SQL 2012+ и параллельной функции SELECT INTO в SQL 2014.
• Длина имен и фраз довольно важна для нового подхода. Я предполагаю, что плохие фразы, как правило, довольно короткие, так как они, вероятно, соответствуют реальным случаям использования. Имена немного длиннее, чем плохие фразы, но предполагается, что они не состоят из тысяч символов. Я думаю, что это справедливое предположение, и более длинные строки имен также замедляют ваш первоначальный подход.
• Некоторая часть улучшения (но далеко не все) связана с тем, что новый подход может использовать параллелизм более эффективно, чем старый (который работает однопоточным). Я работаю на четырехъядерном ноутбуке, поэтому приятно иметь подход, который может использовать эти ядра.

Связанное сообщение в блоге

Аарон Бертран более подробно рассматривает этот тип решения в своем посте в блоге. Один из способов получить индексный поиск по ведущему символу% .

Давайте на секунду отложим очевидную проблему, поднятую Аароном Бертраном в комментариях:

Итак, вы сканируете таблицу 3K раз и, возможно, обновляете все 15-миллиметровые строки все 3K раз, и ожидаете ли вы, что она будет быстрой?

Тот факт, что ваш подзапрос использует подстановочные знаки с обеих сторон, сильно влияет на саргиваемость . Чтобы взять цитату из этого сообщения в блоге:

Это означает, что SQL Server должен прочитать каждую строку из таблицы Product, проверить, есть ли у него «орех» где-либо в имени, а затем вернуть наши результаты.

Замените слово «орех» для каждого «плохого слова» и «Продукт» для SourceTable, затем объедините это с комментарием Аарона, и вы должны начать понимать, почему чрезвычайно трудно (читать невозможно) заставить его работать быстро, используя ваш текущий алгоритм.

Я вижу несколько вариантов:

1. Убедите бизнес купить сервер-монстр, обладающий такой мощью, что он справляется с запросом с помощью грубой силы. (Этого не произойдет, так что скрестите пальцы, другие варианты лучше)
2. Используя существующий алгоритм, примите боль один раз, а затем распространите ее. Это будет включать в себя вычисление плохих слов при вставке, что замедлит вставки и обновит всю таблицу только при вводе / обнаружении нового плохого слова.
3. Примите ответ Джеффа . Это отличный алгоритм, и он намного лучше всего, что я бы придумал.
4. Сделайте вариант 2, но замените ваш алгоритм на Джеффа.

В зависимости от ваших требований я бы порекомендовал вариант 3 или 4.

во-первых, это просто странное обновление

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

Как '%' + [Bad_Phrase]. [PHRASE] убивает вас,
который не может использовать индекс

Дизайн данных не является оптимальным для скорости
Можете ли вы разбить [Bad_Phrase]. [PHRASE] на одну фразу (фразы) / слово?
Если одна и та же фраза / слово встречаются более одного раза, вы можете ввести их несколько раз, если хотите, чтобы они имели большее число.
Таким образом, число строк в неправильной фазе будет увеличиваться.
Если вы сможете, то это будет намного быстрее.

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]

Не уверен, что 2005 поддерживает, но полнотекстовый индекс и использовать Содержит