EXPLAIN output suggests that my index is not being used
You misunderstand what the 'rows' field is. It is the number of rows that mysql estimates it shall need to read to satisfy your query. This value can be quite inaccurate. It does not mean this is the number of rows in the result - or the actual number of rows read by mysql