Неожиданные сканирования во время операции удаления с использованием WHERE IN

У меня есть запрос, подобный следующему:

DELETE FROM tblFEStatsBrowsers WHERE BrowserID NOT IN (
    SELECT DISTINCT BrowserID FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID IS NOT NULL
)

tblFEStatsBrowsers получил 553 строки.
У tblFEStatsPaperHits есть 47,974,301 строк.

tblFEStatsBrowsers:

CREATE TABLE [dbo].[tblFEStatsBrowsers](
    [BrowserID] [smallint] IDENTITY(1,1) NOT NULL,
    [Browser] [varchar](50) NOT NULL,
    [Name] [varchar](40) NOT NULL,
    [Version] [varchar](10) NOT NULL,
    CONSTRAINT [PK_tblFEStatsBrowsers] PRIMARY KEY CLUSTERED ([BrowserID] ASC)
)

tblFEStatsPaperHits:

CREATE TABLE [dbo].[tblFEStatsPaperHits](
    [PaperID] [int] NOT NULL,
    [Created] [smalldatetime] NOT NULL,
    [IP] [binary](4) NULL,
    [PlatformID] [tinyint] NULL,
    [BrowserID] [smallint] NULL,
    [ReferrerID] [int] NULL,
    [UserLanguage] [char](2) NULL
)

В tblFEStatsPaperHits есть кластерный индекс, который не включает BrowserID. Выполнение внутреннего запроса, таким образом, потребует полного сканирования таблицы tblFEStatsPaperHits - что вполне нормально.

В настоящее время полное сканирование выполняется для каждой строки в tblFEStatsBrowsers, что означает, что у меня есть 553 полных сканирования таблицы tblFEStatsPaperHits.

Переписывание только ГДЕ СУЩЕСТВУЕТ не меняет план:

DELETE FROM tblFEStatsBrowsers WHERE NOT EXISTS (
    SELECT * FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID = tblFEStatsBrowsers.BrowserID
)

Однако, как предлагает Адам Мачаник, добавление опции HASH JOIN приводит к оптимальному плану выполнения (всего одно сканирование tblFEStatsPaperHits):

DELETE FROM tblFEStatsBrowsers WHERE NOT EXISTS (
    SELECT * FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID = tblFEStatsBrowsers.BrowserID
) OPTION (HASH JOIN)

Теперь вопрос не в том, как это исправить - я могу либо использовать OPTION (HASH JOIN), либо создать временную таблицу вручную. Мне больше интересно, почему оптимизатор запросов будет использовать план, который он использует в настоящее время.

Поскольку в QO нет статистики по столбцу BrowserID, я предполагаю, что оно предполагает худшее - 50 миллионов различных значений, что требует довольно большой рабочей таблицы в памяти / tempdb. Таким образом, самый безопасный способ - выполнить сканирование для каждой строки в tblFEStatsBrowsers. Между столбцами BrowserID в этих двух таблицах нет связи по внешнему ключу, поэтому QO не может вычесть какую-либо информацию из tblFEStatsBrowsers.

Это так просто, как кажется, причина?

Обновление 1
Чтобы дать пару характеристик: ОПЦИЯ (HASH JOIN):
208,711 логических чтений (12 сканирований)

ОПЦИЯ (LOOP JOIN, HASH GROUP):
11,008,698 логических операций чтения (~ сканирование на BrowserID (339))

Нет параметров:
11,008,775 логических операций чтения (~ сканирование на BrowserID (339))

Обновление 2
Отличные ответы, всем вам - спасибо! Трудно выбрать только один. Хотя Мартин был первым, а Ремус предлагает отличное решение, я должен дать его киви за то, что он разбирается в деталях :)

«Мне больше интересно, почему оптимизатор запросов будет использовать план, который он использует в настоящее время».

Другими словами, вопрос в том, почему следующий план выглядит для оптимизатора самым дешевым, по сравнению с альтернативами (которых много ).

Внутренняя сторона объединения по существу выполняет запрос следующей формы для каждого коррелированного значения BrowserID:

DECLARE @BrowserID smallint;

SELECT 
    tfsph.BrowserID 
FROM dbo.tblFEStatsPaperHits AS tfsph 
WHERE 
    tfsph.BrowserID = @BrowserID 
OPTION (MAXDOP 1);

Обратите внимание, что предполагаемое количество строк составляет 185 220 (не 289 013 ), поскольку сравнение равенства неявно исключает NULL(если не ANSI_NULLSявляется OFF). Ориентировочная стоимость вышеуказанного плана составляет 206,8 единицы.

Теперь давайте добавим TOP (1)предложение:

DECLARE @BrowserID smallint;

SELECT TOP (1)
    tfsph.BrowserID 
FROM dbo.tblFEStatsPaperHits AS tfsph 
WHERE 
    tfsph.BrowserID = @BrowserID 
OPTION (MAXDOP 1);

Ориентировочная стоимость сейчас составляет 0,00452 единицы. Добавление физического оператора Top устанавливает цель строки в 1 строку в операторе Top. Тогда возникает вопрос, как получить «цель строки» для сканирования кластерного индекса; то есть сколько строк должно обработать сканирование, прежде чем одна строка будет соответствовать BrowserIDпредикату?

Доступная статистическая информация показывает 166 различных BrowserIDзначений (1 / [Все плотности] = 1 / 0,006024096 = 166). В калькуляции предполагается, что различные значения распределены равномерно по физическим строкам, поэтому для целевого ряда при сканировании кластерного индекса установлено значение 166,302 (с учетом изменения количества элементов таблицы с момента сбора выборочной статистики).

Оценочная стоимость сканирования ожидаемых 166 строк не очень велика (даже выполняется 339 раз, по одному разу для каждого изменения BrowserID) - при сканировании кластерного индекса оценивается приблизительная стоимость в 1,3219 единиц, что показывает эффект масштабирования цели строки. Немасштабированные затраты оператора на ввод / вывод и ЦП показаны как 153,931 и 52,8698 соответственно:

На практике очень маловероятно, что первые 166 строк, отсканированных из индекса (в любом порядке, в котором они будут возвращены), будут содержать одно из возможных BrowserIDзначений. Тем не менее, DELETEплан стоит всего 1.40921 единиц и выбирается оптимизатором по этой причине. Барт Дункан показывает еще один пример такого типа в недавнем посте под названием Row Goals Gone Rogue .

Также интересно отметить, что оператор Top в плане выполнения не связан с Anti Semi Join (в частности, упоминается «короткое замыкание» Мартина). Мы можем начать видеть, откуда взялась вершина, сначала отключив правило исследования под названием GbAggToConstScanOrTop :

DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, LOOP JOIN, RECOMPILE);
GO
DBCC RULEON ('GbAggToConstScanOrTop');

Этот план имеет ориентировочную стоимость 364,912 и показывает, что топ заменил группу по совокупности (группировка по коррелированному столбцу BrowserID). Совокупность не связана с избыточностью DISTINCTв тексте запроса: это оптимизация, которая может быть представлена ​​двумя правилами исследования, LASJNtoLASJNonDist и LASJOnLclDist . Отключение этих двух также производит этот план:

DBCC RULEOFF ('LASJNtoLASJNonDist');
DBCC RULEOFF ('LASJOnLclDist');
DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, LOOP JOIN, RECOMPILE);
GO
DBCC RULEON ('LASJNtoLASJNonDist');
DBCC RULEON ('LASJOnLclDist');
DBCC RULEON ('GbAggToConstScanOrTop');

Этот план оценивается в 40729,3 единицы.

Без преобразования из группы «В» в верх оптимизатор «естественно» выбирает план хеш-соединения с BrowserIDагрегацией перед анти-полусоединением:

DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, RECOMPILE);
GO
DBCC RULEON ('GbAggToConstScanOrTop');

И без ограничения MAXDOP 1, параллельный план:

Другой способ «исправить» исходный запрос - создать отсутствующий индекс, о BrowserIDкотором сообщается в плане выполнения. Вложенные циклы работают лучше всего, когда внутренняя сторона индексируется. Оценка кардинальности для полусоединений является сложной задачей в лучшие времена. Отсутствие надлежащей индексации (у большой таблицы даже нет уникального ключа!) Не поможет вообще.

Я написал больше об этом в Строковых Целях, Часть 4: Anti Anti Anti Pattern .

Когда я запускаю ваш скрипт для создания базы данных только для статистики и запроса в вопросе, я получаю следующий план.

Кардинальности таблицы, показанные в плане

• tblFEStatsPaperHits: 48063400
• tblFEStatsBrowsers : 339

Таким образом, он оценивает, что ему нужно будет выполнить сканирование в tblFEStatsPaperHits339 раз. Каждое сканирование имеет коррелированный предикат, tblFEStatsBrowsers.BrowserID=tblFEStatsPaperHits.BrowserID AND tblFEStatsPaperHits.BrowserID IS NOT NULLкоторый помещается в оператор сканирования.

План не означает, что будет проведено 339 полных сканирований. Так как он находится под оператором anti semi join, как только будет найдена первая подходящая строка в каждом сканировании, он может замкнуть остальную часть. Ориентировочная стоимость поддерева для этого узла составляет 1.32603весь план 1.41337.

Для Hash Join это дает план ниже

Общий план оценивается в 418.415(примерно в 300 раз дороже, чем план с вложенными циклами), при этом один полный просмотр кластерного индекса tblFEStatsPaperHitsстоит 206.8один. Сравните это с 1.32603оценкой для 339 частичных сканирований, данной ранее (Средняя оценочная стоимость частичного сканирования = 0.003911592).

Таким образом, это указывает на то, что каждое частичное сканирование обходится в 53000 раз дешевле, чем полное сканирование. Если бы затраты были масштабированы линейно с количеством строк, то это означало бы, что предполагается, что в среднем потребуется только 900 строк на каждой итерации, прежде чем он найдет соответствующую строку и сможет замкнуть цепь.

Однако я не думаю, что затраты действительно линейно масштабируются. Я думаю, что они также включают некоторый элемент фиксированной стоимости запуска. Попытка различных значений TOPв следующем запросе

SELECT TOP 147 BrowserID 
FROM [dbo].[tblFEStatsPaperHits] 

147дает ближайшую оценочную стоимость поддерева 0.003911592в 0.0039113. В любом случае очевидно, что в основе затрат лежит предположение, что при каждом сканировании необходимо обрабатывать лишь небольшую часть таблицы, порядка сотен строк, а не миллионов.

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

В моей книге даже одно сканирование 50-метровых строк недопустимо ... Мой обычный трюк состоит в том, чтобы материализовать отдельные значения и делегировать движок, чтобы он обновлялся:

create view [dbo].[vwFEStatsPaperHitsBrowserID]
with schemabinding
as
select BrowserID, COUNT_BIG(*) as big_count
from [dbo].[tblFEStatsPaperHits]
group by [BrowserID];
go

create unique clustered index [cdxVwFEStatsPaperHitsBrowserID] 
  on [vwFEStatsPaperHitsBrowserID]([BrowserID]);
go

Это дает вам материализованный индекс по одной строке на BrowserID, избавляя от необходимости сканировать 50M строк. Движок будет поддерживать его для вас, и QO будет использовать его «как есть» в заявлении, которое вы опубликовали (без всякой подсказки или переписывания запроса).

Недостатком является, конечно, утверждение. Любая операция вставки или удаления в tblFEStatsPaperHits(и я предполагаю, что это таблица журналов с тяжелыми вставками) должна будет сериализовать доступ к данному BrowserID. Есть способы сделать это работоспособным (отложенные обновления, 2-х этапное ведение журнала и т. Д.), Если вы готовы купить его.