Este erro ocorre quando o banco de dados precisa procurar em mais de 1 milhão de linhas para atender os requisitos de sua consulta.
Essa limitação não diz respeito a quantidade de registros em uma tabela e sim, em quantos registros serão lidos para satisfazer uma consulta sendo assim,
em uma tabela sem a devida otimização o mysql pode fazer várias consultas para atender ao resultado de uma query, a adição de índices, faz com que o mysql vasculhe menos registros.
Para solucionar o erro em questão:
Otimize sua query e também crie index em suas tabelas, aumentando assim a performance de sua base de dados.