SELECT * vs SELECT COUNT(*) vs ... — что быстрее?
А для чего проверить-то?
Если вы не хотите вставлять дубликаты записей, то повесьте уник и вставляйте с помощью INSERT IGNORE - это будет явно быстрее всяких там дополнительных селектов :)
первый вариант