Of the many ways to optimise queries in a relational database, indexes are the best place to start. When you index a column, the database stores the records for that column in sorted order to improve searching speeds. The price you pay for this is additional storage overhead and decreased speed for INSERT/UPDATE/DELETE statements.
When you search an unordered list for a value, worst case scenario you have to look at every record. If you have a list of 1,000,000 items, you have to scan all 1,000,000. If, on the other hand, the list is ordered, you can use a binary search instead, which can locate a matching record in no more than 20 lookups.
The easiest way to think of this is a phone directory, which is indexed on surname. So if you're looking for "Wilson", you can skip over most of the pages and go straight to "W". If, on the other hand, you are looking for a number to find out the name of the person that owns that number, you're forced to start at the beginning and work your way through one at a time, which would be incredibly painful.
Imagine now, that you have a second phone directory that is sorted on number. You now have twice as many books and this takes up more space, but if you're commonly looking up names based on a phone number then the trade-off is well worth it.
Database indexes are very much like this. As a general rule:
Index columns that you frequently include in WHERE/GROUP BY clauses.
select * from t1 where poo = 'smelly'
select category, count(*) from t2 group by category
Index foreign keys (columns that refer to keys in other tables). For example:
select * from t1 join t2 on t1.lol = t2.rofl
If the data in both tables is sufficiently large, an index on the foreign key
t1.lol could result in noticable gains. Foreign keys should not be indexed blindly: like any column, inappropriate indexes offer no benefits and can sometimes impede performance and result in issues like deadlocking.
Indexes can consist of multiple columns. In fact, if all the columns in the SELECT list can be found in an index, the query can be run against the index rather than the table. Multi-column indexes can be exploited by compound WHERE conditions using AND (e.g.,
a = 'lol AND b = 'rofl'), but not OR. If the previous predicate were rewritten as
a = 'lol OR b = 'rofl', you would be better served by two separate indexes on columns
This just scratches the surface, but will give you substantial gains for effort.