Батчами (LIMIT + цикл), чтобы не блокировать таблицу и не исчерпывать память. Транзакции на батч. При возможности - один запрос с временной таблицей или bulk update. Индексы и мониторинг блокировок.