Parece que também é
- Desequilíbrio do índice ao longo do tempo
- Fragmentação de disco
- Fragmentação de arquivos de dados innodb internos
Você pode tentar
analyze table foo
que não leva bloqueios, apenas alguns mergulhos de índice e leva alguns segundos. Se isso não resolver, você pode usar
mysql> SET PROFILING=1;
mysql> INSERT INTO foo ($testdata);
mysql> show profile for QUERY 1;
e você deve ver onde a maior parte do tempo é gasto.
Aparentemente o innodb funciona melhor quando as inserções são feitas na ordem PK, é este o seu caso?