faster INSERT with possible pre-existing row?

I am working on a process that will be inserting tens of million rows
and need this to be as quick as possible.

The catch is that for each row I could potentially insert, I need to
look and see if the relationship is already there  to prevent
multiple entries.  Currently I am doing a SELECT before doing the
INSERT, but I recognize the speed penalty in doing to operations.  I
wonder if there is some way I can say "insert this record, only if it
doesn't exist already".  To see if it exists, I would need to compare
3 fields instead of just enforcing a primary key.

Even if this could be a small increase per record, even a few percent
faster compounded over the whole load could be a significant reduction.

Thanks for any ideas you might have.

-Dan