Как вариант, как это реализовано в IPB. в админке при всяких операциях зачистки, можно выставить количество одновременно обрабатываемых записей. И делать это в несколько проходов. И как ужу написали, может стоит все в один запрос укомплектовать, у БД сервера явно мощи побольше будет.