SQL – improve NOT EXISTS query performance

Is there a way I can improve this kind of SQL query performance:

INSERT
INTO ...
WHERE NOT EXISTS(Validation...)

The problem is when I have many data in my table (like million of rows), the execution of the WHERE NOT EXISTS clause if very slow. I have to do this verification because I can’t insert duplicated data.

I use SQLServer 2005

thx

Answer

Make sure you are searching on indexed columns, with no manipulation of the data within those columns (like substring etc.)