I have to admit that when I posted an entry a few days ago on creating indexes to make your database queries run faster, I made a small error of omission when I suggested that indexes be created for every two columns that are used in a join. The fact is that you should create indexes even for single columns if they're the main lookup in the query. From the MySQL documentation:
Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows. The larger the table, the more this costs. If the table has an index for the columns in question, MySQL can quickly determine the position to seek to in the middle of the data file without having to look at all the data. If a table has 1,000 rows, this is at least 100 times faster than reading sequentially.