Maria Ramona

Maria Ramona, вы можете разпараллелить процессы, чтобы в одном потоке процесс не затягивать. Создайте мастер процесс, который запустит несколько потомков.
По архитекуре сами решите, сколько записей будете выбирать. Не забудьте настроить блокировки чтения, чтобы потомки не могли прочитать уже взятые записи.
Библиотеку можно взять тут. Работает асинхронно.
Ну и существуют ряд библиотек для работы с задачами:

1. https://github.com/chrisboulton/php-resque
2. https://packagist.org/packages/woojean/php-redis-queue

Этот список не полный.

По cron собирайте задания с складывайте в очередь (Redis подойдёт, но лучше RabbitMQ). А с другой стороны очереди поставьте сколько нужно обработчиков и рассылайте. Создание заданий пройдет куда быстрее чем отправка множества уведомлений во внешний мир