Fastto

Используйте механизм очередей.

Смысл: когда вам нужно что-то выполнить «долгоиграющее» по определенным обстоятельствам или событиям, вы «помещаете в очередь на выполнение» определенную задачу. А сама очередь будет извлекать из стека задачи по одной и выполнять их. Это можно сделать например раз в минуту по крону специальным скриптом — крон-менеджером.

В качестве примера реализации можно посмотреть на таски симфони

Мне кажется будет эффективен следующий вариант (если не ошибаюсь, подобное решение в тасках симфони):
не использовать ни флаг ни время для выборки, а просто вторым, обрабатывающим сервисом «запоминать» последний успешно обработанный идентификатор, а выборку делать
where ID > @yourLastCalcedID

Это будет наиболее эффективно, естественно, если обработка сервисом протекает последовательно, линейно ID за ID, без пропусков и ветвлений между элементами обработки

в комплекте с mysql идет библиотека, как юзать смотрите тут

Введение в SQL (М.Грабер) /рус./
Добротный список