Jaki algorytm kryje się za operatorem EXCEPT?

Jaki jest wewnętrzny algorytm jak wyjątkiem operatora działa pod kołdrą w SQL Server? Czy to wewnętrznie zajmuje hash każdego wiersza i porównuje?

David Lozinksi przeprowadził badanie, SQL: Najszybszy sposób wstawiania nowych rekordów tam, gdzie jeszcze nie istnieje . Pokazał, że instrukcja Except jest najszybsza dla dużej liczby wierszy; ściśle powiązane z naszymi wynikami poniżej.

Założenie: Sądzę, że lewe łączenie byłoby najszybsze, ponieważ porównuje tylko 1 kolumnę, z wyjątkiem najdłuższego, ponieważ musi porównać wszystkie kolumny.
Z tymi wynikami, teraz nasze myślenie jest wyjątkiem, z wyjątkiem tego, że automatycznie pobiera skrót każdego wiersza? Spojrzałem na plan wykonania z wyjątkiem, który wykorzystuje pewien skrót.

Tło: Nasz zespół porównywał dwie tabele stert. Tabela A Rzędy niewymienione w tabeli B zostały wstawione do tabeli B.

Tabele sterty (ze starszego systemu plików tekstowych) nie mają kluczy głównych / prowadnic / identyfikatorów. Niektóre tabele miały zduplikowane wiersze, więc znaleźliśmy wartość skrótu każdego wiersza, usunęliśmy duplikaty i utworzyliśmy identyfikatory klucza głównego.

1) Najpierw uruchomiliśmy instrukcję wyjątkiem, z wyłączeniem (kolumna mieszania)

select * from TableA
Except
Select * from TableB,

2) Następnie przeprowadziliśmy porównanie lewego łączenia między dwiema tabelami na HashRowId

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

zaskakująco, z wyjątkiem instrukcji Insert Insert było najszybsze.

Wyniki faktycznie są zbliżone do wyników testów Davida Lozinksi

Jaki jest wewnętrzny algorytm działania operatora wyjątku pod przykryciem w programie SQL Server?

Nie powiedziałbym, że istnieje specjalny wewnętrzny algorytm dla EXCEPT. Ponieważ A EXCEPT Bsilnik pobiera odrębne (w razie potrzeby) krotki z A i odejmuje wiersze pasujące do B. Nie ma specjalnych operatorów planu zapytań. Odróżnianie i odejmowanie są realizowane za pomocą typowych operatorów, które można zobaczyć za pomocą sortowania lub łączenia. Obsługiwane są łączenie w pętli zagnieżdżonej, łączenie scalające i łączenie mieszające. Aby to pokazać, wrzucę 15 milionów wierszy w parę hałd:

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

Optymalizator zazwyczaj podejmuje decyzje oparte na kosztach dotyczące sposobu sortowania i łączenia. Z dwoma hałdami otrzymuję haszowanie zgodnie z oczekiwaniami. Możesz oczywiście zobaczyć inne typy złączeń, dodając indeksy lub zmieniając dane w dowolnej tabeli. Poniżej wymuszam połączenia scalania i łączenia z podpowiedziami tylko w celach ilustracyjnych:

Czy to wewnętrznie zajmuje hash każdego wiersza i porównuje?

Nie. Jest implementowany jak każde inne połączenie. Jedną różnicą jest to, że wartości NULL są traktowane jako równe. Jest to specjalny rodzaj porównania, które można zobaczyć w planie wykonanie: <Compare CompareOp="IS">. Możesz jednak uzyskać ten sam plan dzięki T-SQL, który nie zawiera EXCEPTsłowa kluczowego. Na przykład poniższe ma dokładnie ten sam plan zapytań, co EXCEPTzapytanie wykorzystujące sprzężenie mieszające:

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

Zróżnicowanie XML planów wykonania ujawnia jedynie powierzchowne różnice wokół aliasów i tego typu rzeczy. Resztki sondy dla połączeń mieszających wykonują porównanie wierszy. Są takie same dla obu zapytań:

Jeśli nadal masz wątpliwości, uruchomiłem PerfView z najwyższą dostępną częstotliwością próbkowania, aby uzyskać stosy wywołań dla zapytania ziEXCEPT zapytania bez niego. Oto wyniki obok siebie:

Nie ma prawdziwej różnicy. Stosy wywołań w tym haszowaniu referencyjnym są obecne z powodu dopasowań skrótu w planie. Jeśli dodam indeksy, aby uzyskać naturalne połączenie scalające, nie zobaczysz żadnych odniesień do mieszania w stosach połączeń:

Występujące haszowanie wynika z implementacji operatorów dopasowania mieszania. Nie ma w tym nic specjalnego, EXCEPTco prowadzi do specjalnego, wewnętrznego porównania skrótów.