Processe a geração de relatórios em segundo plano com queue jobs do Laravel, funciona super bem e não é difícil de programar.

Em questão de banco, eu prefiro PostgreSQL, é mais rápido, lida melhor com quantidades absurdas de registros e super confiável. Trabalho com suporte de um erp desktop que utiliza e pode atestar que é o melhor banco relacional open-source. Antes que me cancelem aqui (banco é um assunto com muitos fanboys), MySQL é largamente utilizado, até mesmo em grandes projetos, já utilizei muito, mas hoje sempre opto pelo Postgres. Somente essa consideração em relação ao banco, pois, querendo ou não, ele interfere no tempo.

Jogue o relatório para uma queue job e depois notifique o usuário para baixar.