Of course, if goes without saying, make a backup of the database before trying anything, but you'd work with the original version of the database—I'd try two things: WordPress database repair and maintenance, and phpMyAdmin's optimize tables:
This came from this page, which has a lot of info WP Knowledgebase, but you start by adding this line to your site's wp-config.php:
then go to http://yoursite.com/wp-admin/maint/repair.php
You should see a page with two options: 'Repair Database' and 'Repair and Optimize Database.'
Clickon 'Repair and Optimize Database' and give the script time to run. Once they've run successfully, you'll get update messages letting you know the status of various tables.
As soon as it has run, very important, remove the wp_allow_repair line you just added to wp-config.php, delete it from the wp-config.php file.
If that doesn't work, you can try phpMyAdmin's table optimization, but if WordPress's didn't help, that may not either. I'd try it on the same version of the database you ran the last repair on.
Go into phpMyAdmin, select your database, scroll to the bottom of the page, check 'Check All' to select all of the tables in the database, then select "Optimize Table" from the select menu next to it. That's it, it will start automatically.
Here's more detail and screenshots: WPMUDev
If those two steps don't work—alone or together—you can try using another copy of your backup database to run them in the reverse order... Good luck!