По-ефективна заявка от NOT IN (вложен избор)

Надстройте до MySQL 5.6, което оптимизира по-добре полусъединенията срещу подзаявки.

Вижте http://dev.mysql.com/doc/ refman/5.6/en/subquery-optimization.html

Или използвайте съединение за изключване:

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

Също така се уверете, че table2.table1_id има индекс върху него.