Давно хотел записать, чтобы не потерять. Выдержка из главы «Defragmenting a Table» руководства по MySQL:

It can speed up index scans if you periodically perform a “null” ALTER TABLE operation: ALTER TABLE tbl_name ENGINE=INNODB

That causes MySQL to rebuild the table. Another way to perform a defragmentation operation is to use mysqldump to dump the table to a text file, drop the table, and reload it from the dump file.

По-русски говоря, таблицы в формате InnoDB могут сильно фрагметироваться в процессе работы, для того, чтобы избавиться от фрагметрации выполняйте иногда это «магическую» конструкцию или снимайте дамп с таблицы и заливайте обратно.

mysql_connect('localhost', 'root', 'пароль');

$res = mysql_query('SHOW DATABASES');

while (list($dbname) = mysql_fetch_row($res))
{
        mysql_select_db($dbname);

        $rec = mysql_query('SHOW TABLE STATUS');

        while ($data = mysql_fetch_object($rec))
        if ($data->Engine == 'InnoDB')
        {
                echo 'Processing ', $dbname, '.', $data->Name, ' ... '; flush();

                mysql_query("ALTER TABLE {$data->Name} ENGINE=InnoDB");

                echo "done.n";
        }

        mysql_free_result($rec);
}

mysql_free_result($res);

P.S. Как справедливо заметил Jimi Dini, в MySQL 5.0 и выше OPTIMIZE TABLE делает то же самое для InnoDB.