Salemaker always been slow, now takes 3-4 min between checkmark updates. Thoughts?

Salemaker seems like it has always been dramatically slow, at maybe a minute to update a checkmark. It is now taking somewhere between 3-4 minutes to update a single checkmark in a sale. Originally started site on 1.39 over 4 years ago, but wasn't really using salemaker or doing much for sales until after 1.50 upgrade.

Recent changes:
Rebuilt site on 1.54 last month, applied fixes for known issues, and updated php to 5.5.
Starting linking a majority of products to multiple categories during the last 2 months.

I use no add-ons, and my own customization outside the language files and CSS is pretty minimal (mostly just for schema.org tags in product listing and product info display).

I have 609 categories, 5483 products. Currently have 20 of 22 sales active, and all sales are showing fine and as expected.

Is this unreasonable behavior for Salemaker with that number of categories and products? Admin response time seems good for everything else, no problems with page load time, etc. Any other thoughts? Any other pertinent info I need to provide? Thanks much in advance for opinions and ideas.

Server info stuff:
Server Host: xxx Database Host: localhost (127.0.0.1)
Server OS: Linux 3.12.41-77.ELK6.x86_64 Database: MySQL 5.5.42-37.1
Server Date: 07/12/2015 19:27:40 Database Date: 07/12/2015 19:27:40
Server Up Time: 19:27:40 up 22 days, 11:59, 0 users, load average: 0.03, 0.01, 0.00 HTTP Server: Apache
PHP Version: 5.5.26 (Zend: 2.5.0) PHP Memory Limit: 256M PHP Safe Mode: Off
PHP File Uploads: On Max Size: 64M POST Max Size: 64M
Database Data Size: 40,526 kB Database Index Size: 6,897 kB

Zen Cart Zen Cart 1.5.4
Database Patch Level: 1.5.4
v1.5.4 [2015-06-15 20:24:37] (Version Update 1.5.3->1.5.4)
v1.5.3 [2015-06-15 20:24:37] (Version Update 1.5.2->1.5.3)
v1.5.2 [2015-06-15 20:24:37] (Version Update 1.5.1->1.5.2)
v1.5.1 [2014-07-27 10:21:11] (Version Update 1.5.0->1.5.1)
v1.5.0 [2012-09-11 23:08:36] (Version Update 1.3.9->1.5.0)
v1.3.9h [2011-01-23 14:36:29] (Fresh Installation)

My first thought is that perhaps something is slow on the MySQL end.
Here are some tuning tips for the webserver and MySQL performance: https://www.zen-cart.com/content.php?262-Webserver-Tuning-Tips

And then tuning tips to speed up your store generally: https://www.zen-cart.com/content.php?63-how-do-i-speed-up-my-site ... and while you said your site is speedy apart from this particular issue, it could be that some of these might be beneficial generally even if not specifically.

Another thing you could do is compare the database schema for the salemaker and products and categories and products_to_categories tables against the original ZC schema, specifically checking whether all the original indexes are present in the tables on your db. (Sometimes indexes get lost when importing from other db's, etc). NOTE: Generally with the latest version of ZC it's not necessary to add "more" indexes (and adding too many can unnecessarily slow things down, so don't go adding more unless you have a strategy for adding them).

I imagine that tuning MySQL will give the biggest benefit ... but that can be difficult if on a shared-hosting account.

Hi Dr. Byte! Thanks for the advice - I'll start going through and report back later if I get any improvements. I have to admit, it has been awhile (like since 1.39) since I've looked at the the general speed recommendations, and can't also help now but suspect my db indexes. I am on a shared server, so probably can't do mySQL tweaking. The site's not too terribly active, so also hadn't been thinking about server performance itself much either...hmmm. Thanks much!