How to structure the database - MYSQL performance question

Indexes on:
SELECTed fields
ORDER BY fields
WHERE fields
fields JOINed on

Thanks for the clarification CroNiX

I'm surprised that an index makes a difference on SELECTed fields, do you know why that is?

You're right to be surprised, because that's nonsense.

Indexes make a (positive) difference when used on fields that you do lookups by. That's why I previously said they should be created depending on your queries ... they're just meaningless otherwise.

Use the EXPLAIN statement to identify bottle-necks in your queries (what you've shown are PHP method calls, not SQL queries) and see what kind of look-ups on which fields they make. After you can see those points, knowing what to index should come naturally.