O índice que você precisa criar é fornecido nas cláusulas WHERE e ORDER BY, estados e data_atualizada
ALTER TABLE items ADD INDEX states_updated_date_ndx (states,updated_date);
Execute novamente o seu plano EXPLAIN depois.
Você também pode reduzir o tamanho das colunas executando PROCEDURE ANALYZE () assim:
SELECT states,updated_date FROM items PROCEDURE ANALYSE();
Isso não mostrará todas as linhas. Ele simplesmente passará por todas as linhas e determinará os tipos de dados ideais para os estados e as colunas atualizadas.
Se a tabela items for MyISAM, você terá que aumentar key_buffer_size. Se InnoDB, aumente innodb_buffer_pool_size. No mínimo, certifique-se de que caches já são grandes o suficiente .
Experimente!