Requête plus efficace que NOT IN (sélection imbriquée)

Passez à MySQL 5.6, qui optimise mieux les semi-jointures par rapport aux sous-requêtes.

Voir http://dev.mysql.com/doc/ refman/5.6/en/subquery-optimization.html

Ou bien utilisez une jointure d'exclusion :

SELECT COUNT(t1.table1_id) FROM table1 t1 
LEFT OUTER JOIN table2 t2 USING (table1_id)
WHERE t2.table1_id IS NULL

Assurez-vous également que table2.table1_id contient un index.