Há uma consulta para encontrar rapidamente as linhas órfãs em uma tabela com uma referência de junção à esquerda.
SELECT t1.id_referencing_t2
FROM a_table AS t1
LEFT JOIN referenced_table AS t2
ON t1.id_referencing_t2 = t2.primary_id_of_t2
WHERE t2.primary_id_of_t2 IS NULL