Подумайте о запуске этого в пакетном режиме. Цикл, запускающий 1000 записей за один раз, может быть намного быстрее, чем один запрос, который делает все, и, кроме того, он не будет держать таблицу заблокированной для других пользователей в течение длительного времени.
Если у вас есть каскадное удаление (и многие таблицы внешних ключей затронуты) или задействованы триггеры, вам может потребоваться запускать в еще меньших партиях. Вам придется поэкспериментировать, чтобы увидеть, какой номер лучше всего подходит для вашей ситуации. У меня были таблицы, где мне приходилось удалять партиями по 100, а другие - по 50000 (к счастью, я удалял миллион записей).
Но в любом случае я бы поместил значения моих ключей, которые я намерен удалить, во временную таблицу и удалил оттуда.