WHERE NOT IN聲明中的Big-O是什麼？

我有一個簡單的sql查詢，我只在some_table中的id不在其他一些id結果集中時，才從some_table中選擇行。WHERE NOT IN聲明中的Big-O是什麼？

例如：

SELECT * FROM some_table 
WHERE some_table.id NOT IN 
     (SELECT id FROM 
     .... whatever statement might be related to this table 
    )

如果該子語句返回設定如

的是不是在O（N），其中，賦予了「some_table.id」的結果，它從結果集的頂部開始，併線性掃描每條記錄，直到找到具有相同值的記錄爲止？或者它是否使用散列（像Java中的HashSet）並能夠在O（1）中找到它？

這是否因SQL實現而異？例如，在我的應用程序中，我們使用PostgreSQL。但如果在Oracle或MS SQL Server中可能不同，我不會感到驚訝。

我希望這是一個不斷的操作。但我不知道，只是好奇。

2016-05-12 dfritch

+11

SQL是聲明式的。它沒有告訴你有關實施的任何內容，因此也沒有提及性能。值得注意的是，大多數關係數據庫可以爲同一個查詢使用不同的查詢計劃。這允許數據庫根據數據中的統計趨勢進行優化，這意味着同一系統上的相同查詢可能會在不同的時間點使用不同的計劃，因爲數據會發生變化。 – jpmc26

您可能會發現'EXPLAIN'命令很有用。使用「解釋查詢」按鈕時，pgAdmin將以圖形方式顯示計劃。 – jpmc26

如果Ñ是some_table大小和米是子結果的最大尺寸，則在米檢查Ñ針對每個元件的每個元件的幼稚算法是O（ mn）。

實際上，正如jpmc26提到的那樣，底層實現將決定這一點。例如，如果索引了m中的id，則可以在O（lg m）時間訪問它，因此可以在O（nlg m）時間內對照m檢查n。由於您必須至少檢查每個元素n，因此任何實現在Ω（n）處的下限都是有界的。

2016-05-12 22:26:06

索引通常是B-樹或其他樹結構（至少在PostgreSQL中），所以它不可能是O（1）。 – jpmc26

正確，所以取決於實施。它可能是SQL在該數組下的子查詢的結果（我不知道它是否可能，取決於你的查詢和SQL實現）。我敢打賭，大多數不在實施平均n（lg米） –

回答