performance af et simpelt select i en kæmpe database

Jeg har to tabeller som jeg gerne vil sammenligne med nedenstående lille select.
Problemet er, at tabellerne er meget store, og der er ikke indeks på kolonnerne.

Tabellen ELK har 75 mill records,
heraf har de 28 mill records art = 0 eller 9
Tabellen ELM har 26 mill records
Værdierne i PK kolonnen er ens for tilsvarende records i de to tabeller (ELM er en delmængde af ELK)

Jeg forventer altså et resultat af min kontrol på 2 mill records fra ELK.
Rent intuitivt laver jeg et select i ELK efter de records, der har den rigtige art, og som ikke findes i ELM:

select pk from ELK
where ELM.art not in (0,9)
and pk not in (select pk from ELM);

Det tager meeeeget lang tid....

En kollega sagde noget om, at 'not in' er dyr rent performance mæssigt, er det rigtigt, - og i så fald...
hvordan gør man det bedre ?

på forhånd tak