This is because the index is not very useful for this kind of query, so the database must perform a full table scan. If the query is for some reason slower than the simple "SELECT * FROM TABLE", do it instead and filter out the unwanted identifiers in the program.
EDIT: In your comment, I admit that you are using a subquery instead of a list. Because of this, there are three possible ways to do the same (hopefully one of them is faster):
Original statement:
select * from mytable where id not in (select id from othertable);
Alternative 1:
select * from mytable where not exists
(select 1 from othertable where mytable.id=othertable.id);
Alternative 2:
select * from mytable
minus
select mytable.* from mytable in join othertable on mytable.id=othertable.id;
Alternative 3: (ugly and hard to understand, but if all else fails ...)
select * from mytable
left outer join othertable on (mytable.id=othertable.id)
where othertable.id is null;
source
share