Marino - 11:56 am on May 27, 2012 (gmt 0)
I'm facing the same problems. Have you set innodb_file_per_table in your my.cnf?
When you say "a MySQL database with several million rows", you mean a table, or a set of tables? May be time to shard your big table(s) too? Would you post the table(s) structure(s)?