Какой алгоритм стоит за исключением оператора EXCEPT?

Каков внутренний алгоритм работы оператора Except под оболочками в SQL Server? Это внутренне берет хеш каждой строки и сравнивает?

Дэвид Лозинкси (David Lozinksi) провел исследование « SQL: самый быстрый способ вставки новых записей, когда его еще нет». Он показал, что оператор «Кроме» - самый быстрый для большого числа строк; тесно связывая с нашими результатами ниже.

Предположение: я думаю, что левое соединение будет самым быстрым, так как оно сравнивает только 1 столбец, за исключением того, что оно будет самым длинным, поскольку оно должно сравнивать все столбцы.
С этими результатами наше мышление теперь разве что автоматически и внутренне берет хеш каждой строки? Я посмотрел на «кроме плана выполнения», и он использует некоторый хэш.

История вопроса: наша команда сравнивала две таблицы кучи. Таблица A Строки, не указанные в таблице B, были вставлены в таблицу B.

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

1) Сначала мы запустили оператор исключений, исключая (столбец хеша)

select * from TableA
Except
Select * from TableB,

2) Затем мы запустили сравнение левого соединения между двумя таблицами в HashRowId.

select * 
FROM dbo.TableA A
left join dbo.TableB B
    on A.RowHash =  B.RowHash
where B.Hash is null

Удивительно, но вставка с оператором кроме была самой быстрой.

На самом деле результаты сопоставлены с результатами тестирования Дэвида Лозинкси

Каков внутренний алгоритм работы оператора Except под оболочками в SQL Server?

Я бы не сказал, что есть специальный внутренний алгоритм для EXCEPT. Для A EXCEPT B, движок берет различные (при необходимости) кортежи из A и вычитает строки, которые совпадают в B. Не существует специальных операторов плана запроса. Отличное и вычитание реализуются через типичные операторы, которые вы могли бы видеть с помощью сортировки или объединения. Поддерживается соединение с вложенным циклом, объединение слиянием и объединение хешей. Чтобы показать это, я брошу 15 миллионов строк в пару куч:

DROP TABLE IF EXISTS dbo.TABLE_1;

CREATE TABLE dbo.TABLE_1 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_1 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);


DROP TABLE IF EXISTS dbo.TABLE_2;

CREATE TABLE dbo.TABLE_2 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_2 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);

Оптимизатор принимает обычные, основанные на затратах решения о том, как реализовать сортировку и объединение. С двумя кучами я получаю хеш-соединение, как и ожидалось. Вы можете увидеть другие типы объединения естественным образом, добавив индексы или изменив данные в любой таблице. Ниже я приведу принудительное объединение и циклическое соединение с подсказками только для иллюстрации:

Это внутренне берет хеш каждой строки и сравнивает?

Нет. Это реализовано как любое другое соединение. Единственное отличие состоит в том, что NULL считаются равными. Это особый тип сравнения , который вы можете увидеть в плане выполнения: <Compare CompareOp="IS">. Тем не менее, вы можете получить тот же план с T-SQL, который не включает EXCEPTключевое слово. Например, следующий план имеет тот же план EXCEPTзапроса, что и запрос, использующий хеш-соединение:

SELECT t1.*
FROM
(
    SELECT DISTINCT COL1, COL2
    FROM dbo.TABLE_1
) t1
WHERE NOT EXISTS (
    SELECT 1
    FROM dbo.TABLE_2 t2
    WHERE (t1.COL1 = t2.COL1 OR (t1.COL1 IS NULL AND t2.COL1 IS NULL))
    AND (t1.COL2 = t2.COL2 OR (t1.COL2 IS NULL AND t2.COL2 IS NULL))
);

Различия в XML планов выполнения показывают только поверхностные различия между псевдонимами и тому подобными вещами. Остатки зондов для хеш-соединений выполняют сравнение строк. Они одинаковы для обоих запросов:

Если у вас все еще есть сомнения, я запустил PerfView с самой высокой доступной частотой выборки, чтобы получить стеки вызовов для запроса с EXCEPTзапросом и без него. Вот результаты рядом:

Там нет никакой разницы. Стеки вызовов там, ссылки хэширования присутствуют из-за совпадений хэшей в плане. Если я добавлю индексы для получения естественного объединения слиянием, вы не увидите никаких ссылок на хеширование в стеках вызовов:

Любое хэширование происходит из-за реализации операторов совпадения хешей. Нет ничего особенного, EXCEPTчто приводит к специальному внутреннему сравнению хэширования.