Почистить "дырки" (дефрагментация), обновить статистику и отсортировать индексы:
       OPTIMIZE TABLE имя_таблицы;
или использовать:   myisamchk --quick --check-only-changed --sort-index --analyze
Внимание, myisamchk нужно запускать при _не_ запущенном mysqld, иначе нужно
использовать утилиту mysqlcheck
(mysqlcheck --repair --analyze --optimize --all-databases --auto-repair)
Апдейт статистики оптимизатора:
      ANALYZE TABLE имя_таблицы;
или использовать:   myisamchk --analyze
Рекомендуется регулярно выполнять:
    isamchk -r --silent --sort-index -O sort_buffer_size=16M db_dir/*.ISM
    myisamchk -r --silent --sort-index  -O sort_buffer_size=16M db_dir/*.MYI