NOT EXISTS vs NOT IN – czyli o filtracji wykluczającej

O tym jak odfiltrować dane z jednego zbioru na podstawie danych z innego zbioru powiedziano już bardzo wiele. Mimo, że temat był dosyć mocno eksplorowany to z moich obserwacji wynika, że kwestia ta nie jest do końca zrozumiana. Dlatego też postanowiłem wykonać mój własny test filtracji wykluczającej – porównamy sobie wydajność i efektywność kilku podejść m.in NOT EXISTS oraz NOT IN ale nie tylko – zapraszam do lektury!

W naszym przykładzie wykorzystamy hurtownię WideWorldImportersDW i znajdujące się w niej tabele [Dimension].[Stock Item] oraz [Fact].[Movement]. Celem naszych zapytań będzie zwrócenie tych kolorów przedmiotów, które nigdy się nie sprzedały. Jedyną modyfikacją jakiej dokonamy na ten moment jest dodanie indeksu do tabeli faktów, tak aby był on pokrywający na potrzeby naszych testów. Każde zapytanie będziemy testować bez żadnych danych w pamięci, mierząc czas oraz koszt.

CREATE NONCLUSTERED INDEX [FK_Fact_Movement_Stock_Item_Key_MovementKey] ON [Fact].[Movement]
(
	[Stock Item Key] ASC,[Movement Key] ASC
)WITH (DROP_EXISTING = OFF)
GO

SET STATISTICS IO, TIME ON
GO
DBCC DROPCLEANBUFFERS
GO

(Komenda DROPCLEANBUFFERS będzie wykonywana przed każdym wywołaniem – dla czytelności nie będę tego pokazywał). Na pierwszy ogień pójdzie tradycyjne jedno z popularniejszych podejść czyli NOT IN:

SELECT DISTINCT DIS.Color FROM Dimension.[Stock Item] AS DIS
WHERE DIS.[Stock Item Key] NOT IN
(
 SELECT [Stock Item Key] FROM
 Fact.Movement AS F
 WHERE F.[Stock Item Key]=DIS.[Stock Item Key]
 )

Jak widać na powyższym planie wykonania, optymalizator zdecydował się przeskanować indeks kolumnowy tabeli faktów oraz klasyczny indeks zgrupowany dla tabeli wymiaru by następnie połączyć otrzymane dane algorytmem Hash Match i zagregować kolejnym Hash Matchem. Koszt takiego planu wyniósł 0.1814, czas wykonania 46ms – całkiem nieźle prawda?

Bez wgłębiania się w otrzymany rezultat przejdźmy dalej. Kolejną testową konstrukcją będzie OUTER JOIN z WHERE usuwającym niepasujące wiersze:

SELECT DISTINCT DIS.Color FROM Dimension.[Stock Item] AS DIS
LEFT JOIN Fact.Movement AS F
ON F.[Stock Item Key]=DIS.[Stock Item Key]
WHERE F.[Movement Key] IS NULL

W tym wypadku plan wygląda nieco inaczej, filtracja rezultatów nastąpiła już po złączeniu obu zbiorów operatorem FILTER, co jak możecie się domyślać skutkowało nieco większym kosztem całego planu wynoszącym 0.2301 w czasie 97ms. Filtracja jest oczywiście obligatoryjnym elementem gdyż w naszym scenariuszu testowym gdyż optymalizator nie był w stanie odrzucić niepasujących wierszy jeszcze przed wykonaniem dopasowania – logiczne. Mimo wszystko czas w jakim otrzymaliśmy rezultat był równie dobry i w pełni akceptowalny.

Dwa pierwsze proste testy mamy za sobą, czas wypróbować kolejną konstrukcję którą jest NOT EXISTS:

SELECT DISTINCT DIS.Color FROM Dimension.[Stock Item] AS DIS
WHERE NOT EXISTS
(
 SELECT 1 FROM
 Fact.Movement AS F
 WHERE F.[Stock Item Key]=DIS.[Stock Item Key]
 )

Tutaj zaczyna dziać się coś ciekawego gdyż plan znacznie różni się od poprzednich. Pierwszym elementem na jaki warto zwrócić uwagę jest to, że w elemencie NOT EXISTS napisałem SELECT 1 – dlaczego? Z prostego powodu, to co będzie zwracane w sekcji SELECT nie ma absolutnie żadnego znaczenia gdyż z EXISTS do ostatecznego rezultatu nie zwracane jest nic. Dlatego też mam taki “nawyk”, że zawsze wpisuje tam 1 mimo, że nawet jakbyśmy wpisali tam niesławną “*” to i tak optymalizator by to zignorował i nie miałoby to absolutnie żadnego znaczenia.

Sam plan jest ciekawy gdyż nie użyty został w ogóle indeks kolumnowy. Zamiast tego mamy index seek na indeksie nieklastrowanym założonym na kluczu obcym do wymiaru (Stock Item Key) tabeli faktów. Zaraz po nim następuje operacja Top 1 i Nested Loops do złączenia rezultatu. Dlaczego akurat TOP 1 i Nested Loops? Jak wiecie INNER INPUT z Nested Loops (ten w dolnej części planu) wykonywany jest tyle razy ile wierszy zwróci OUTER INPUT – w tym wypadku było to 672 razy! Następnie brany jest pierwszy z brzegu wiersz zwrócony przez Index Seek i wrzucony do połączenia w Nested Loops. Dlatego występuje tutaj TOP 1 ponieważ nie ważne ile wierszy zostałoby połączonych z wierszami zwróconymi przez Index Scan – jeśli chociaż jeden się łączy to wiersz powinien być odrzucony. To właśnie dlatego EXISTS jest bardzo często zalecanym podejściem filtrującym! Ponieważ nie sprawdza wszystkich kombinacji tylko jeśli coś zostaje zwrócone to warunek jest spełniony lub nie. Zgodnie z moimi przewidywaniami konstrukcja ta jest naszym dotychczasowym liderem gdyż koszt tego planu wynosi 0.1605 a całe wykonanie zajęło 43ms.

W dalszej kolejności do testów dorzuciłem też mało popularną konstrukcję tj. OUTER APPLY:

SELECT DISTINCT DIS.Color FROM Dimension.[Stock Item] AS DIS
OUTER APPLY
(
 SELECT F.[Stock Item Key] FROM
 Fact.Movement AS F
 WHERE F.[Stock Item Key]=DIS.[Stock Item Key]
) AS F
WHERE F.[Stock Item Key] IS NULL

OUTER APPLY działa w taki sposób, że zapytanie podane po tych słowach kluczowych jest wykonywane dla każdego wiersza z tabeli poprzedzającej te słowa kluczowe. Plan zapytania różni się od tego co dostaliśmy wyżej, tym razem wracamy do użycia indeksu kolumnowego. Plan bardzo przypomina ten występujący przy OUTER JOIN z tym wyjątkiem, że mamy tu dodatkowy operator Compute Scalar. Cały plan ma koszt 0.2133 z czasem 68ms.

Jak widać drastycznych różnic nie ma – jednakże podsumować trzeba i zwycięzcą okazał się NOT EXISTS. Ktoś z Was może powiedzieć, że nie ma to znaczenia skoro poruszamy się w ramach błędu pomiaru, są różne konfiguracje indeksów i struktur bazodanowych – i wiecie co? Macie rację! W bardzo wielu przypadkach różnice są na tyle małe, że nie ma to znaczenia – jednakże zawsze warto testować na swoim przykładzie bo nie w każdym wypadku indeksowanie będzie tak dostosowane, a i tryb batchowy który był używany przez zapytania (a o czym nie wspomniałem) nie zawsze będzie używany ( w szczególności w wersjach SQL Server starszych niż 2016). Sam czas również może się różnić w zależności od momentu wykonania zapytania i jedynym licznikiem wartym porównania jest właśnie koszt. Weźmy również pod uwagę to, że nie mogliśmy porównywać odczytów stron bo w indeksie kolumnowym tradycyjnych odczytów stron nie otrzymamy tylko LOB  a i sam indeks kolumnowy wpłynął pozytywnie na wydajność większości operatorów ze względu na kompresję i wspomniany tryb batchowy…

Warto też wspomnieć, że im wyższy koszt tym większa szansa , że przekroczymy Cost Treshold of Parallelism i optymalizator może zdecydować się na wykonanie naszego zapytania równolegle – co wtedy? A no właśnie.. Jest tak wiele możliwości, że nie ma pewności co do tego która metoda będzie najlepsza w uniwersalnym tego słowa znaczeniu. Powyższa konfiguracja struktur jest tylko jedną z możliwych i raczej wątpliwy jest sens tworzenia tutaj dziesiątek różnych konfiguracji stert, columnstore, rowstore itp. Co do rekomendacji to myślę, że można całość podsumować następująco – przy czym są to zasady, którymi sam się kieruje i są według mnie dobrym punktem startowym:

• chcemy odfiltrować wiersze z jednej tabeli na podstawie złączenia z drugą tabelą bez wyświetlania danych z drugiej tabeli: NOT EXISTS
• chcemy odfiltrować wiersze z jednej tabeli na podstawie złączenia z drugą tabelą wyświetlając dane z drugiej tabeli: JOIN
• chcemy odfiltrować wiersze z jednej tabeli na podstawie złączenia z funkcją tabelaryczną: APPLY

NOT IN nie używam od jakiegoś czasu praktycznie w ogóle, jednakże w każdym wypadku powinniśmy TESTOWAĆ! Nie ma złotych zasad – są tylko wytyczne. Jeżeli mielibyśmy same sterty wtedy też nasz test miałby inny rezultat, jeżeli nie mielibyśmy indeksów pokrywających też rezultat byłby inny.Osobiście najlepsze rezultaty zazwyczaj dostaje używając EXISTS i to jest mój domyślny wybór.

Dodatkowo chciałbym Wam powiedzieć o tym, o czym często się zapomina. Chodzi mianowicie o to, że każde z powyższych zapytań jest subsytutem i działa analogicznie oprócz NOT IN. Każde z zapytań opiera się o logikę dwu wartościową tj. TRUE i FALSE, IN z kolei opiera się o logikę trójwartościową tj. TRUE, FALSE oraz NULL!

Sprawdźmy to na przykładzie, mamy tabelę NullTable, która zawiera wartość NULL oraz 1. Mamy również tabelę TestTable, która zawiera NULL oraz 2 – naszym zadaniem jest napisanie takich zapytań, które zwracają tylko te wiersze z NullTable, których nie ma w TestTable – użyjemy oczywiście powyżej opisywanych struktur:

 with NullTable
 AS
 (
 SELECT NULL as Col1
 UNION ALL 
 SELECT 1 AS Col1
 ), TestTable
 AS
 (
 SELECT 2 as Col2
 UNION ALL 
 SELECT NULL AS Col2
 )
 SELECT Col1,'NOT IN' AS OPERATION FROM NullTable
 WHERE Col1 NOT IN (SELECT Col2 FROM TestTable)
 UNION ALL
SELECT Col1,'NOT EXISTS' AS OPERATION FROM NullTable AS O
 WHERE NOT EXISTS (SELECT 1 FROM TestTable AS I WHERE I.Col2=o.Col1)
 UNION ALL
SELECT O.Col1,'OUTER APPLY' AS OPERATION FROM NullTable AS O
OUTER APPLY (SELECT Col1 FROM TestTable AS I WHERE I.Col2=o.Col1) AS I
WHERE I.Col1 IS NULL
UNION ALL
SELECT O.Col1,'OUTER JOIN' AS OPERATION FROM NullTable AS O
LEFT OUTER JOIN TestTable AS I 
ON I.Col2=o.Col1
WHERE I.Col2 IS NULL

Rezultat jest dosyć łatwy do przewidzenia:

A może jednak nie taki łatwy? Każda metoda zwróciła wartość NULL z tabeli NullTable gdyż wartość ta porównana do jakiejkolwiek innej wartości daje wartość FALSE, a więc według naszej logiki nie jest równa żadnemu wierszowi z TestTable. Powiedziałem, że każda metoda? Oczywiście każda oprócz NOT IN dla której porównanie jakichkolwiek wartości do NULL daje rezultat UNKNOWN i cały warunek jest odrzucany – dlatego też zapytanie z wykorzystaniem tego konstruktu nie zwróciło nawet jednego wiersza! Innymi słowy przy zapisie WHERE Col1 NOT IN (SELECT Col2 FROM TestTable) otrzymaliśmy tak naprawdę zapis 1 <> NULL OR 1<>2 (występuje porównanie do NULL więc całe wyrażenie odrzucone) oraz dla drugiego wiersza NULL<>NULL OR NULL<>2 (jak poprzednio). Na cały zapis ma wpływ ustawienie ANSI_NULLS:

 SET ANSI_NULLS OFF

 with NullTable
 AS
 (
 SELECT NULL as Col1
 UNION ALL 
 SELECT 1 AS Col1
 ), TestTable
 AS
 (
 SELECT 2 as Col2
 UNION ALL 
 SELECT NULL AS Col2
 )
 SELECT Col1,'NOT IN' AS OPERATION FROM NullTable
 WHERE Col1 NOT IN (SELECT Col2 FROM TestTable)

Po wyłączeniu wspomnianej opcji NOT IN zwrócił następujące wiersze:

Dosyć specyficzne zachowanie prawda? Dlatego też uważam, że tej składni powinno się unikać, nie ze względu na wydajność ale przede wszystkim ze względu na to, iż możemy otrzymać dosyć nieoczekiwane rezultaty. Na szczęście wraz z SQL Server 2016 ustawienie ANSI_NULLS zostało oznaczone jako DEPRECATED więc powoli będzie wycofywane.

Cały artykuł mam nadzieję, że uświadomi Wam, że w świecie baz danych nie ma złotych zasad są tylko rekomendacje do poszczególnych scenariuszy. Testujcie swoje zapytania i uważajcie na IN/NOT IN. Do następnego!