Why does MySQL ignore the index even on force for this order by? I run an EXPLAIN:  

mysql&gt; explain select last_name from employees order by last_name;
+----+-------------+-----------+------+---------------+------+---------+------+-------+----------------+  
| id | select_type | table     | type | possible_keys | key  | key_len | ref  | rows  | Extra          |
+----+-------------+-----------+------+---------------+------+---------+------+-------+----------------+  
|  1 | SIMPLE      | employees | ALL  | NULL          | NULL | NULL    | NULL | 10031 | Using filesort |
+----+-------------+-----------+------+---------------+------+---------+------+-------+----------------+  
1 row in set (0.00 sec)  


The indexes in my table:  

mysql&gt; show index from employees;  
+-----------+------------+---------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+  
| Table     | Non_unique | Key_name      | Seq_in_index | Column_name   | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |  
+-----------+------------+---------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+  
| employees |          0 | PRIMARY       |            1 | subsidiary_id | A         |           6 |     NULL | NULL   |      | BTREE      |         |               |  
| employees |          0 | PRIMARY       |            2 | employee_id   | A         |       10031 |     NULL | NULL   |      | BTREE      |         |               |  
| employees |          1 | idx_last_name |            1 | last_name     | A         |       10031 |      700 | NULL   |      | BTREE      |         |               |  
| employees |          1 | date_of_birth |            1 | date_of_birth | A         |       10031 |     NULL | NULL   | YES  | BTREE      |         |               |  
| employees |          1 | date_of_birth |            2 | subsidiary_id | A         |       10031 |     NULL | NULL   |      | BTREE      |         |               |  
+-----------+------------+---------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+  
5 rows in set (0.02 sec)  


There is an index on last_name but the optimizer does not use it.
So I do:  

mysql&gt; explain select last_name from employees force index(idx_last_name) order by last_name;  
+----+-------------+-----------+------+---------------+------+---------+------+-------+----------------+  
| id | select_type | table     | type | possible_keys | key  | key_len | ref  | rows  | Extra          |  
+----+-------------+-----------+------+---------------+------+---------+------+-------+----------------+  
|  1 | SIMPLE      | employees | ALL  | NULL          | NULL | NULL    | NULL | 10031 | Using filesort |  
+----+-------------+-----------+------+---------------+------+---------+------+-------+----------------+  
1 row in set (0.00 sec)  


But still the index is not used! What am I doing wrong here?
Does it have to do with the fact that the index is NON_UNIQUE? 
BTW the last_name is VARCHAR(1000)  

Update requested by @RolandoMySQLDBA  

mysql&gt; SELECT COUNT(DISTINCT last_name) DistinctCount FROM employees;  
+---------------+  
| DistinctCount |  
+---------------+  
|         10000 |  
+---------------+  
1 row in set (0.05 sec)  


mysql&gt; SELECT COUNT(1) FROM (SELECT COUNT(1) Count500,last_name FROM employees GROUP BY last_name HAVING COUNT(1) &gt; 500) A;  
+----------+  
| COUNT(1) |  
+----------+  
|        0 |  
+----------+  
1 row in set (0.15 sec)
Actually, the problem here is that this looks like a prefix index. I don't see the table definition in the question, but sub_part = 700?  You haven't indexed the whole column, so the index can't be used for sorting and is not useful as a covering index, either.  It could only be used to find the rows that &quot;might&quot; match a WHERE and the server layer (above the storage engine) would have to further filter the rows matched.  Do you really need 1000 characters for a last name?

update to illustrate:  I have a table test table with a litle over 500 rows in it, each with the domain name of a web site in a column domain_name VARCHAR(254) NOT NULL and no indexes.
mysql&gt; alter table keydemo add key(domain_name);
Query OK, 0 rows affected (0.17 sec)
Records: 0  Duplicates: 0  Warnings: 0

With the full column indexed, the query uses the index:
mysql&gt; explain select domain_name from keydemo order by domain_name;
+----+-------------+---------+-------+---------------+-------------+---------+------+------+-------------+
| id | select_type | table   | type  | possible_keys | key         | key_len | ref  | rows | Extra       |
+----+-------------+---------+-------+---------------+-------------+---------+------+------+-------------+
|  1 | SIMPLE      | keydemo | index | NULL          | domain_name | 764     | NULL |  541 | Using index |
+----+-------------+---------+-------+---------------+-------------+---------+------+------+-------------+
1 row in set (0.01 sec)

So, now, I'll drop that index, and just index the first 200 characters of domain_name.
mysql&gt; alter table keydemo drop key domain_name;
Query OK, 0 rows affected (0.11 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql&gt; alter table keydemo add key(domain_name(200));
Query OK, 0 rows affected (0.08 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql&gt; explain select domain_name from keydemo order by domain_name;
+----+-------------+---------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table   | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+---------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | keydemo | ALL  | NULL          | NULL | NULL    | NULL |  541 | Using filesort |
+----+-------------+---------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

mysql&gt;

Voila.
Note also, that the index, at 200 characters, is longer than the longest value in the column...
mysql&gt; select max(length(domain_name)) from keydemo;
+--------------------------+
| max(length(domain_name)) |
+--------------------------+
|                       43 |
+--------------------------+
1 row in set (0.04 sec)

...but that doesn't make any difference.  An index declared with a prefix length can only be used for lookups, not for sorting, and not as a covering index, since it doesn't contain the full column value, by definition.
Also, the above queries were run on an InnoDB table, but running them on a MyISAM table yields virtually identical results.  The only difference in this case is that the InnoDB count for rows is slightly off (541) while MyISAM shows the exact number of rows (563) which is normal behavior since the two storage engines handle index dives very differently.
I would still assert that the last_name column is likely larger than needed, but it still is possible to index the entire column, if you are using InnoDB and running MySQL 5.5 or 5.6:

By default, an index key for a single-column index can be up to 767 bytes. The same length limit applies to any index key prefix. See Section 13.1.13, “CREATE INDEX Syntax”. For example, you might hit this limit with a column prefix index of more than 255 characters on a TEXT or VARCHAR column, assuming a UTF-8 character set and the maximum of 3 bytes for each character. When the innodb_large_prefix configuration option is enabled, this length limit is raised to 3072 bytes, for InnoDB tables that use the DYNAMIC and COMPRESSED row formats.
— http://dev.mysql.com/doc/refman/5.5/en/innodb-restrictions.html