Es gibt zwei Tabellen:
A, die Ids Enthält
B, die teilweise Ids von A enthält

Ich will nun die Zeilen aus B haben, die einen Key haben, der nicht in A vorkommt

select *
from A outer join B on A.Key = B.FKey
where A.Key is null

oder

select *
from B
where B.FKey not in (select A.Key from A)

Edit:
MSSQL-Server 2005
count(A.Key) = 1.000
count(B.Key) = 50.000

Die "not exists"-Klausel ist doch genau für solche Fälle gedacht. Sie evaluiert meines Wissens nach bei Oracle zu einem Outerjoin. Was performanter ist lässt sich ohne Informationen über das eingesetzte RDBMS nicht klären.

Bei Oracle kannst du die Kosten abschätzen, in dem du dir von beiden Querys den Explain-Plan ausgeben lässt.

definitiv die Erste

dies kannst du selbst durchspielen...
beim Zweiten: für jede Zeile in der Datenbank B, muss die ganze Tabelle A ab geglichen werden.

beim Ersten wird zuerst eine große Tabellen erstellt... Dank des Outer Joins bereist hinreichend eingeschränkt. Danach werden alle Zeilen mir Nullwerten raus geschissen.
Da hier alle Kombinationen bereits vorab bekannt sind, kann auch die interne Optimierung des DBMS geschickter eingreifen.

Ich empfehle:

SELECT *
FROM   B
WHERE  NOT EXISTS (SELECT Key from A WHERE Key = B.FKey)

und einen Index auf A.Key. Unterm Strich mußt du testen was auf deinem Datenbanksystem schnell geht, an der Syntax allein kann man das nicht immer festmachen. Was Query Optimizer für einen Plan daraus macht, ist entscheidend - und die Optimizer untscheiden sich schon von DBMS zu DBMS.

Ich stimme den Meinungen, dass Variante 1 besser ist, nicht zu (zumindest bei SQL Server 2005 od. 2008). Bei der ersten Abfrage muss die DB auf jeden Fall alle Datensätze aus B lesen. Danach erfolgt der Join auf alle Datensätze der Tabelle A. Nachdem es sich um Schlüssel handelt, kann man davon ausgehen, dass auf A.Key ein Index liegt. Dementsprechend wird der Join über eine nested Loop gemacht. Das Ergebnis(!) kann anhand der Einschränkung "A.Key is null" gefiltert werden.

Im zweiten Fall geht die Datenbank fast gleich vor. Ebenfalls werden alle Zeilen aus B gelesen und über eine nested Loop wird je Zeile aus B in A nachgeschlagen. Der große Unterschied ist, dass am Ende kein Filter mehr notwendig ist.

Achtung: Diese Aussage ist falsch, falls
a) auf B.Key kein Index liegt
b) A.Key und/oder B.Key NULL erlauben
c) Foreign Keys zwischen A.Key und B.Key angelegt sind.
d) Die Datenmengen so verteilt sind, dass die DB keinen nested Loop Join sondern einen Hash Match macht (unwahrscheinlich).

Wer meine Aussage nachprüfen möchte, einfach die Tabellen im SQL Server anlegen und Execution Plans vergleichen.

Ich würde als erstes Fragen, welche Datenbank drunter werkelt. Erst an hand dieser Info kann man wirklich sagen was performanter ist. :)

Also ich würde dir den ersten Query empfehlen, da alles in einem durchgegangen wird. außerdem zeigst du mit dem OUTER JOIN auch direkt auf die Spalte, auf die du dich beziehst, was meiner Meinung nach performanter ist.

Einen kleinen Tip habe ich aber noch für dich: Benutze SELECT * nur, wenn du auch wirklich ALLE Spalten benötigst. Ansonsten selektiere die Spalten "manuell" also:
`spalte_1`,
`spalte_2`

usw...

Oder auch so:

SELECT B.* 
FROM B
LEFT JOIN A ON A.Key = B.FKey
WHERE A.Key IS NULL;

Vermutlich gibt dir aber ein EXPLAIN (vor der Abfrage) die richtige Antwort.

Da es darum geht:

Ich will nun die Zeilen aus B haben, die einen Key haben, der nicht in A vorkommt

und für eine Antwort die Querys

select *
from A outer join B on A.Key = B.FKey
where A.Key is null

und

select *
from B
where B.FKey not in (select A.Key from A)

zur Verfügung stehen, so muß man eindeutig sagen das die 2.Lösung in jedem Fall die performantere ist, da es die einzige Lösung ist die das Problem löst!
Pauschal gibt es die "Performantere Lösung" nicht! Diese ist IMMER von verschiedensten Faktoren abhängig: wieviele DS hat A, wieviele DS hat B, welche Indizes existieren, welches DBMS wird verwendet, gibt es NULL-Felder zu berücksichtigen, etc....

Die Antwort hängt von vielen Faktoren ab
1) Verwendetes Datenbanksystem
2) Mengengerüst: count(distinct B.FKey), count(B.FKey), count(A.Key), im Verhältnis zum verfügbaren Speicher (RAM)
3) Verfügbare Indizes
4) Aktualität der Statistiken
5) Hardware (Geschhwindigkeit und Anzahl Prozessoren, RAM Durchsatz, Festplatten Durchsatz)

Guten Datenbanken ist es fast egal, wie die Abfrage formuliert ist, denn das DB System optimiert die Abfrage ohnehin nach den Vorgaben. Ausnahmen bestätigen die Regel.

Wenn ein Index auf B.FKey (und auf a.Key) existiert, sollte der MSSQL Server bei großen Datenmengen einen simplen merge join durchführen können, der mit sehr wenig Speicher auskommt. Schneller gehts es nicht.

Wenn selbst für A.Key kein Index vorliegt und die Datenmenge nicht zu groß ist, könnte der MSSQL auch sinnvollerweise erst mal eine Hashtable für alle A.Key erzeugen, auf der dann ein hash join ausgeführt wird. Das könnte man mit der zweiten Variante "(select Key from A)" vielleicht sogar erzwingen. Da aber wohl A.Key indiziert ist, könnte ein loop join vielleicht effizienter sein. Das kommt aber immer darauf an, ob der Aufwand eine Hashtable zu erzeugen gerechtfertig ist. Normallerweise sind dafür zwei Bedingungen zu erfüllen: count(B.FKey) ist groß und count(A.Key) nicht zu groß, ums in RAM zu passen. Wenn aber ein Index auf A.Key existiert, der aber z.B. als clustered index zu groß ist für das RAM kann es sich auch wieder lohnen, erst aus allen A.Keys eine Hashtable zu bauen, wenn dann die Hashtable ins RAM paßt.

Ich glaube, dass für die meisten DB-Systeme bei großen Datenmenge die Formulierungen

select * from A outer join B on A.Key = B.FKey where A.Key is null

und

SELECT * FROM  B WHERE NOT EXISTS (SELECT Key from A WHERE Key = B.FKey)

besser zu optimieren sind als

select * from B where B.FKey not in (select A.Key from A)

Der Optimierer kann aber auch nicht alles retten. Manchmal ist das Umformulieren besser als jeder Optimierer.

Ein gutes DBMS zeigt Dir den Ausführungsplan und die Kosten dafür an.
Dann kann man die Statements vergleichen.

Ein Index an der richtigen Stelle beschleunigt einen Abfrage auch mehr als ein Optimierer.

Müsste es nicht genau anders herum sein? Ich weiß nicht wie intern die querys optimiert werden, allerdings schaut es doch wie folgt in der Theorie aus:

select * from A outer join B on A.Key = B.FKey where A.Key is null

Bei einem join wie diesem oder z.B. bei folgendem Query

select * from A, B

Wird intern das Kartesische Produkt beider Relationen gebildet und erst anschliessend die where Klausel abgearbeitet. Das bedeutet, dass in oben genanntem Fall eine neue Relation A X B gebildet werden muss. Diese enthält 50.000 * 1.000 = 50.000.000 Tupel.

SELECT * FROM  B WHERE NOT EXISTS (SELECT Key from A WHERE Key = B.FKey)

Diese korrelierte Unterabfrage sollte von der Performance her noch schlechter sein, denn er führt für jeden Tupel in B einen Query auf A aus. Daher 50.000 Tupel + Initial Query = 50.001 Query. (Dieser sollte vom DBMS automatisch zu nachfolgenden Query optimiert werden)

Der letzte Query:

select * from B where B.FKey not in (select A.Key from A)

benötigt nur zwei Abfragen. Benötigt dafür allerdings länger für die Abarbeitung der where Bedingung.

Um diese Frage zu klären muss man garnicht viel schreiben ;-):

Ein Join ist IMMER schneller (=Performanter) als ein Sub-select, manchmal kann man gewisse Sachen mit einem Sub-Select aber einfach "gemütlicher" abfragen.