Do I need to index a key that I partition by?

You should create an index that involves lastname and maybe state,lastname.

Think of it. What would obligate a Query Optimizer to plan a query to search by lastname within a partition? The only course of action would be a full table scan within the correct partition.

Let's assume 50 U.S. States (no Puerto Rico, Guam, US Commonwealths, or Protectorates)

If you have 1 million rows, that would be average out 20,000 rows per state. A table scan of 20,000s for a lastname may not be that bad. However, we are talking about the United States. Huge numbers could live in New York, California, Texas and Florida. Smaller numbers will reside in Rhode Island, Idaho, Wyoming, and Montana. Search times via full table scans will vary greatly. In light of this, it would be beneficial to index names within each state.

I suggest two indexes

• LastName : The second index will get the Query Optimizer to search for LastName in every partition. Doing 50 index lookups would sure beat a 50 full table scans any given day. You mentioned you have an index on phonenumber only and the performance was great. The same would have to apply to a LastName-only index.
• State,LastName : The first index will get the Query Optimizer to search for LastName only down one partition, the state you selected (Maybe unnecessary if the Query Optimizer is intelligent enough to examine the query and select the correct partition).

UPDATE 2012-10-09 16:21 EDT

In all fairness to MySQL's partitioning, if the Query Optimizer is smart enough to navigate data retrieval from just one partition base on the WHERE clause, then indexing (state,lastname) may be unnecesaary. Nevertheless, you must still index on lastname. That way, each partition is indexing on lastname.

My original suggestion of indexing on (state,lastname) is actually based on how I used to index MyISAM tables that were combined under the MERGE storage engine.

Here were my past examples on MERGE tables:

• Jan 04, 2012 : get column from too many tables in mysql
• Jan 15, 2012 : Separate tables or partition one huge table?

Since Table Partitioning is implemented, indexing on lastname should suffice for you. In fact, recall you stated that the phonenumber is indexed and performance was great, So, I say for the second time, indexing lastname should also be as good for you.