Как найти записи в одной таблице, которым нет соответствия в другой

Есть две большие таблицы в MySQL. Теоретически между ними связь один-ко-многим. Практически — связь на уровне базы данных не задана, поэтому нет каскадного изменения/удаления данных во второй таблице при работе с первой таблицей. Итого: после удаления записей из первой таблицы во второй таблице остались мусорные данные.

Как найти подобные мусорные записи, если в обеих таблицах по несколько миллионов записей?

Вариант для небольших данных, в данном случае — не очень:

    SELECT bar.id
      FROM bar
 LEFT JOIN foo ON foo.id = bar.foo_id
     WHERE foo.id IS NULL; 

Не обязательно ограничиваться только силами MySQL.