Thank you very much! The clue was exactly in the "not in" clause. Replacing it with "not exists" clause fixed performance problem.

"link_id" is a PK for this table, so it will never be null. There also was a compound unique index on fields suggested by Sean set before, so I guess cannot do much more to improve performance. Anyway, 10ms of execution time on a very slow development server, with +4000 rows in the table is more than enough for me.

Thank you again for your comments and help.

[Non-text portions of this message have been removed]