Estaba pensando en hacerlo con una consulta SQL,
no se si se podrá, que dicha consulta diga de agregar una notificación a todos los usuarios registros en lugar de usar un for en php, no se si será el mismo gasto la verdad...
Hacelo de forma inversa. Crea un tabla donde guardas las notificaciones a medida que los usuarios son notificados...
Así cuando un user entra, revisas en esa tabla si ya se notifico de X versión, si lo está no haces nada, si no lo esta, le mostras la notificación y luego creas el registro. entonces tu tabla no tendría un millón de registro de entrada, sino que se iría poblando a medida que van entrando los usuarios y solo se notificará a los usuarios activos.
Todo esto es en teoria, pero en un escenario real yo no usaría una base SQL para eso, mejor usaria una base como Redis que es mucho más eficiente y rápida y es el estándar de la industria para el realtime o cosas que necesiten mucha velocidad y el menor consumo manejando un volumen gigante de datos. Trabaja sobre la memoria ram, pero si tenes un sistema con un millón de usuarios supongo que tendrás un servidor con sobrados GB's de ram....
Otra forma que se me ocurre, un poco mas cutre, seria usar algun servicio de archivos estáticos con un cdn global, como Github.
Simplemente tendrías que crear un archivo json e ir metiendo ahí tus versiones. Entonces sería el cliente el que tendría que consultar el contenido de dicho archivo. Asi podes sacar toda la lógica de negocio de tu propia infraestructura, y a github un millón de peticiones no le hacen ni cosquillas...