Was ist die Big-O-Anweisung für WHERE NOT IN?

Question

Ich habe eine einfache SQL-Abfrage, wo ich Zeilen aus Some_Table nur auswählen, wenn die ID in Some_Table nicht in der anderen Ergebnismenge von IDs ist.

Zum Beispiel:

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

Wenn das Unter Anweisung gibt eine Ergebnismenge wie

id 
---- 
160142 
160120 
160093 
160092 

Ist das nicht in einem O (N), wobei ein "some_table.id" gegeben, Es beginnt an der Spitze der Ergebnismenge und scannt jeden Datensatz linear, bis er einen Datensatz mit dem gleichen Wert findet? Oder verhält es sich mit einem Hash (wie ein HashSet in Java) und kann es in O (1) finden?

Ändert sich dies durch die SQL-Implementierung? In meiner Anwendung verwenden wir beispielsweise PostgreSQL. Aber ich wäre nicht überrascht, wenn es in Oracle oder MS SQL Server anders sein könnte.

Ich würde hoffen, dass dies eine konstante Operation ist. Aber ich weiß es nicht und bin nur neugierig.

Answer 1

Wenn n die Größe some_table und m ist die maximale Größe des Teilergebnisses, dann ist der naive Algorithmus jedes Elements des Prüfens in n gegen jedes Element in m ist O (mn).

In der Realität, wie jpmc26 erwähnt, würde die zugrundeliegende Implementierung dies entscheiden. Wenn zum Beispiel die ID in m indiziert ist, könnte sie in O (lg m) -Zeit erreicht werden, so dass n gegen m in O (nlg m) -Zeit überprüft werden könnte. Da Sie jedes Element von n mindestens überprüfen müssen, wäre jede Implementierung bei Ω (n) niedriger gebunden.