Optimizing SELECT in MYSQL

So I was getting really crummy responses from my site. I had just moved hosting providers, so obviously I thought this had something to do with it. On a hunch I ran some benchmark tests using Pear::Benchmark as described here:

http://www.onlamp.com/pub/a/php/2002/02/28/profilingphp.html

Well, it was MySQL, not my hoster (sorry for the frustrated email guys, I love ya, really)
I have indexes defined on all tables that matter, but here are some of the things I did to optimize:
1. Instead of inserting records one at a time, changed code to do bulk inserts; eg:
INSERT INTO table VALUES
('a','b','c','d'),
('e','f','g','h'),
('i','j','k','l') ;

instead of doing them one at a time.
Not a bad thing to do, but it didn't help.

2. Enabled a query cache for MySQL:
[cariapa@mysqlhost]$ mysqladmin variables|grep -i query_cache
| have_query_cache | YES |
| query_cache_limit | 1048576 |
| query_cache_min_res_unit | 4096 |
| query_cache_size | 26214400 |
| query_cache_type | ON |
| query_cache_wlock_invalidate| OFF |

This is a good thing too, but it didn't help in my situation.

3. Ran:
ANALYZE TABLE table_name
OPTIMIZE TABLE table_name

Even if you have indexes, you need to run these commands if your tables undergo any kind of activity. Ie pretty much everyone.

My select times dropped from about 13 seconds to 1.
Dang!

More reading:
http://www.databasejournal.com/features/mysql/article.php/1382791
http://dev.mysql.com/doc/refman/5.0/en/using-explain.html