On which fields to index? Fields queried (WHERE) or fields returned (SELECT) I have a large MySQL database table (~1 million rows and growing) on an AWS RDS Medium instance:

mysql&gt; describe clients;
+-----------------+---------------+------+-----+---------+----------------+
| Field           | Type          | Null | Key | Default | Extra          |
+-----------------+---------------+------+-----+---------+----------------+
| id              | int(11)       | NO   | PRI | NULL    | auto_increment |
| name            | varchar(500)  | YES  |     | NULL    |                |
| address         | varchar(500)  | YES  |     | NULL    |                |
| city            | varchar(200)  | YES  |     | NULL    |                |
| state           | varchar(100)  | YES  |     | NULL    |                |
| zip             | varchar(50)   | YES  |     | NULL    |                |
| country         | varchar(50)   | YES  |     | NULL    |                |
| phone           | varchar(20)   | YES  | UNI | NULL    |                |
| source          | varchar(20)   | YES  | MUL | NULL    |                |
| campaign        | varchar(200)  | YES  |     | NULL    |                |
| search_term     | varchar(200)  | YES  |     | NULL    |                |
| search_location | varchar(200)  | YES  |     | NULL    |                |
| added           | datetime      | YES  |     | NULL    |                |
| email           | varchar(150)  | YES  |     | NULL    |                |
| website         | varchar(150)  | YES  |     | NULL    |                |
| full_output     | varchar(5000) | YES  |     | NULL    |                |
| client          | varchar(50)   | YES  |     | NULL    |                |
| is_deleted      | int(2)        | YES  |     | 0       |                |
| is_valid        | int(2)        | YES  |     | 1       |                |
+-----------------+---------------+------+-----+---------+----------------+
19 rows in set (0.00 sec)


I often need to perform a variant of the following query:

SELECT name, zip FROM clients WHERE source IN ('Foo','foo','Bar','bar') AND added&gt;'2013-11-25 13:00:00' limit 150000, 150000;


And the relevant EXPLAIN:

mysql&gt; EXPLAIN SELECT name, zip FROM clients WHERE source IN ('Foo','foo','Bar','bar') AND added&gt;'2013-11-25 13:00:00' limit 150000, 150000;
+----+-------------+------------+-------+---------------+--------+---------+------+---------+-------------+
| id | select_type | table      | type  | possible_keys | key    | key_len | ref  | rows    | Extra       |
+----+-------------+------------+-------+---------------+--------+---------+------+---------+-------------+
|  1 | SIMPLE      | clients    | range | source        | source | 63      | NULL | 1168144 | Using where |
+----+-------------+------------+-------+---------------+--------+---------+------+---------+-------------+
1 row in set (0.03 sec)


What optimizations should I be making? Should I add indexes on the name and zip fields, or on the added and source fields?
The accepted answer overlooks the concept of covering indexes, and also does not mention the importance of indexes on multiple columns, together in one index.

A single index over both columns in the WHERE clause:

ALTER TABLE clients ADD KEY(source,added) -- adding this 
ALTER TABLE clients ADD KEY(added,source) -- or this


...will usually help you more than an individual index on each column, because the optimizer may otherwise only select to use one of the two columns.  Which of the above indexes will help more depends on the distribution of values in "source" and "added."  The selected index used for the query will appear in "key" in the EXPLAIN output.  "Using where" usually means that, out of the rows the chosen query plan will result in fetching, the server realizes that some number of them will still not meet the selection criteria and will have to be subsequently filtered by the server (as in the example, where potentially a large number would have to be filtered, since no index was used).

A covering index could be particularly valuable also, because contrary to the assertion that "the fields within a row are quick and easy for the engine to get," they are only quicker and easier than finding the rows by scanning the entire table -- they still take time, and consume resources.  

This is where covering indexes come in.  Adding an index with (source,added,zip,name) would likely improve your performance substantially, because once the server has found the relevant rows by using the index, it does not need to look up the rest of the data because the data is actually inside the index.  When a covering index is being used, the "key" column of explain will contain the name of the index being used, and the "Extra" column will include "using index" (meaning, using index to actually retrieve the data, not just find it.)

So while it is true that you index on your selection criteria, that is not the entire story.

Note also that no matter what is indexed, an index will only be used for actual searching starting with the leftmost column in the index, until a column is encountered that is not in the WHERE clause.

Thus, a index on (source,added) can optimize the finding of rows for a query with both "source" and "added" in the WHERE clause... or with just "source" in the WHERE clause, but this index will not be used for lookups with only "added" in the where clause, because there's a column to the left of that, that isn't being used.  Similarly, a single index on (source,added,zip,name) could optimize lookup for queries with WHERE clauses mentioning source ... or source and added ... or source and added and zip ... or source and added and zip and name... but not just "zip" ... not just "name" ... not "added" and "name" and "zip"... you get the idea.  An index is irrelevant beginning at, and to the right of, any column not referenced in WHERE when it comes to optimizing the lookup of rows.

Note that the order in which you list things in the where clause makes no difference, as long as all of the conditions are AND.  That's a misconception you'll find online.  Any equivalent expression is understood as equivalent by the optimizer.

Also, unless you explicitly disabled it, IN('Foo','foo') is redundant because the selection would be case-insensitive thanks to collations, so 'foo' should be sufficient to find any permutation of capitalization.