Se fai una query su colonne indicizzate non dovrebbe scansionare tutta la tabella.

Posta l'output di "CREATE TABLE tabella" e della query che fai preceduta da EXPLAIN.