OK, before my answer, subscribe to the MySQL Performance Blog, I've learned a lot (and I thought I already knew a lot about MySQL). Also, he's got a bitchin' tools page here.
Second off, here's some info about EXPLAIN (referenced from the High Performance MySQL book from O'Reilly):
When you run an EXPLAIN on a query, it tells you everything MySQL knows about that query in the form of reports for each table involved in the query.
Each of these reports will tell you...
- the ID of the table (in the query)
- the table's role in a larger selection (if applicable, might just say SIMPLE if it's only one table)
- the name of the table (duh)
- the join type (if applicable, defaults to const)
- a list of indexes on the table (or NULL if none), *possible_keys*
- the name of the index that MySQL decided to use, key
- the size of the key value (in bytes)
- ref shows the cols or values used to match against the key
- rows is the number of rows that MySQL thinks it needs to examine in order to satisfy the query. This should be kept as close to your calculated minimum as possible!
- ...then any extra information MySQL wishes to convey
The book is completely awesome at providing information like this, so if you haven't already, get your boss to sign off on a purchase.
Otherwise, I hope some more knowledgeable SO user can help :)