Query più efficiente di NOT IN (selezione nidificata)

Esegui l'upgrade a MySQL 5.6, che ottimizza meglio i semi-join rispetto alle sottoquery.

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

Oppure usa un join di esclusione:

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

Inoltre, assicurati table2.table1_id ha un indice.