All the MySQL tables have the be optimized once in a while. Ideally, once a week perhaps.
You can do that by either going to your phpMyAdmin or, if you're a badass command line hacker, running the following command:
mysqlcheck -o --user=root --password=YourPassword -A
Create a cron job
The best way to deal with this is by creating a cron job that will run automatically.
Edit your cron:
Add the following line (will run the command weekly):
@weekly mysqlcheck -o --user=root --password=YourPassword -A