令人困惑的性能增益與嵌套選擇*不存在

Question

我正在查詢的兩個表都有大約1.5億行。

下面的語句我結束之後，在沒有45分鐘回來，所以我不知道多久會運行：

select * from Cats outside 
    where not exists(select * from Cats cat 
        where exists(select dog.foo,dog.bar from Dogs dog 
         where cat.foo = dog.foo 
         and cat.bar = dog.bar))); 

：

select * from Cats cat 
where not exists(select dog.foo,dog.bar from Dogs dog 
        where cat.foo = dog.foo 
        and cat.bar = dog.bar); 

但此查詢在約3分鐘執行

我的問題是幕後發生了什麼，我看到了這種性能增益？

背後返回相同的結果集

推理：

第一個查詢（慢）規定給予不存在的基礎上，貓表中的所有元素。

第二個查詢（快速）聲明給存在的貓的子集中不存在的所有元素。

我期望以下查詢：

select dog.foo,dog.bar from Dogs dog 
          where cat.foo = dog.foo 
          and cat.bar = dog.bar 

返回[A，B，C]

這是常見的兩種功能。

我的貓表有以下幾點：[A，B，C，d，E]

我希望下面的查詢：

select * from Cats cat 
        where exists 

返回[A，B，C] 和最後一塊：

select * from Cats outside 
     where not exists 

返回[d，E]

UPD ATE

集符號在數學上證明我的要求（請糾正我，如果我使用了錯誤的符號）：

∀ Cat (Ǝ cat ≠ Ǝdog)  

對於貓的所有元素，返回一個包含沒有貓的每個元素的集合在狗

∀ Cat (Ǝ cat = Ǝdog) 

對於貓的所有元素等於一個元素，返回一個包含不相等的元素在狗貓的每個元素設定

∀ Cat (Ǝ innerCat ≠ Ǝcat) 

對於貓的所有元素，返回一個包含不貓

二更新

我看到我的數學不與排隊等於元素內貓的每個元素的集合我SQL。

Answer 1

我已經通過測試，這是最初的問題進行查詢的最有效的方式發現：

Select cat.foo,cat.bar from cats cat 

MINUS 

Select dog.foo,dog.bar from dogs dog 

這工作，因爲沒有我的列是空。

Answer 2

他們是不同的查詢結果不同。要使第二次返回與第一次相同，它需要類似於...

select * from cats outside 
    where not exists(select * from Cats cat 
        where exists(select dog.foo,dog.bar from Dogs dog 
         where cat.foo = dog.foo  
         and cat.bar = dog.bar) 
         and outside.foo = cat.foo 
         and outside.bar=cat.bar 
        ) 

Answer 3

您的問題的答案是檢查執行計劃。

一點題外話，你應該試試這個等效的查詢（見https://stackoverflow.com/a/1069467/44522）：

SELECT * FROM Cats cat LEFT OUTER JOIN Dogs dog 
    ON cat.foo = dog.foo and cat.bar = dog.bar 
WHERE dog.foo IS NULL and dog.bar IS NULL 

我打賭它會執行方式更快（假設你有正確的索引）。

Answer 4

顯然，不在和不存在是數據引擎優化的問題。從技術上講，這些被稱爲反連接（區別於等連接，半連接，非平等連接等）。

當一個連接很難優化時，引擎會使用嵌套循環連接。這些通常是性能最差的類型（儘管在SQL Server執行計劃中，它們通常看起來相同，因爲SQL Server在執行計劃中將索引查找稱爲「嵌套循環」）。

這兩個查詢有什麼區別？第一個只有一個NOT EXISTS，所以它可能做一些效率低下的事情。第二個是在最內層的子查詢上做一個EXISTS。這首先被優化，基本上作爲一個連接。如果鍵索引都很好。 SQL Server也可以爲這些選擇基於散列或基於合併的算法。

第二版中的「不存在」基於同一張表。這可能會給SQL Server更多空間進行優化。

最後，第二個版本可能會大大減少數據集。如果是這樣，即使外部的嵌套循環連接可能會更快。

Answer 5

執行時，第二個查詢是更優化，這就是爲什麼：

您別名外查詢的Cats表outside，但你不要指outside您where not exists的子句。因此，SQL可以做到以下幾點：

• 找到任何一個貓在那裏（從最內層查詢）
• 這意味着有確實存在，以滿足您的外where not exists所有貓outside貓
• 因此where not exists子句false所有行中outside
• 因此，對於查詢結果爲空

您的第一個查詢必須重新執行表中每個cat的嵌套查詢，因此速度較慢。