I guess they didn't give you any hints at how to do that did they?

If it's intermittently not responding, it suggests that the problem is server-related.

If you're using ZC v1.3.8, you will have an "Optimize Database" option in your Admin->Tools->Store Manager which will go through each table and reclaim wasted space resulting from deleted records. If you don't have that option, you'll have to do the optimize on each table manually via a tool like phpMyAdmin.

Nevertheless, I doubt that optimizing your tables is going to totally "solve" your problem.

Frankly, if the support person was worth their salt, they would have optimized your database as part of the diagnostics. I suspect your problem is that they've (typically) got you on an overloaded server that can't keep up with the demands of your shop. If they won't move you to a less-crowded server, they'll try to upsell you to something more expensive ... which would likely cost you more than a conventional hosting company would charge for better services than you're getting now. If you want hosting suggestions, see the link at the top of this page.