Оптимизировать этот запрос, извлекать пользователей из базы данных MySQL с 500 000 пользователей и одной условной

Suposse У меня есть следующая база данных MySQL с 500 000 строк :

users
{ 
    id       - int, 
    name     - varchar(32), 
    verified - tinyint(1)
}

primary { id }
index   { verified }

И мне нужно получить последних 20 неподтвержденных пользователей поэтому я использую следующий запрос:

SELECT * FROM users WHERE verified != 1 ORDER BY id DESC LIMIT 20

Но для его завершения требуется 1,2 секунды .

Как его оптимизировать? Или получить тот же результат с другим способом в php .

[EDIT]

ID - это первичный индекс, VERIFIED - тоже индекс

[РЕДАКТИРОВАТЬ 2]

CREATE TABLE `users` (
  `id` int(10) unsigned NOT NULL auto_increment COMMENT 'Identificador del usuario',
  `login` varchar(32) NOT NULL COMMENT 'Login para entrar',
  `password` varchar(32) NOT NULL COMMENT 'Password para entrar',
  `email` varchar(384) NOT NULL COMMENT 'Email del usuario',
  `group_id` int(10) unsigned default NULL,
  `display_name` varchar(64) NOT NULL COMMENT 'Nombre para mostrar',
  `email_verified` tinyint(3) unsigned default '0' COMMENT 'Email verificado?',
  `banned` tinyint(3) unsigned default '0' COMMENT 'Baneado?',
  `admin` tinyint(3) unsigned default '0' COMMENT 'Es un super administrador del sitio?',
  `registered` int(10) unsigned NOT NULL COMMENT 'Fecha del registro',
  PRIMARY KEY  (`id`),
  KEY `login` (`login`),
  KEY `password` (`password`),
  KEY `email` (`email`(333)),
  KEY `group_id` (`group_id`),
  KEY `email_verified` (`email_verified`),
  KEY `banned` (`banned`),
  KEY `admin` (`admin`),
  KEY `registered` (`registered`)
) ENGINE=MyISAM AUTO_INCREMENT=500002 DEFAULT CHARSET=utf8;

[ПРАВИТЬ 3]

EXPLAIN(SELECT id FROM users WHERE email_verified != 1 ORDER BY id DESC LIMIT 20)

- это

id: 1   
select_type: SIMPLE 
table: users    
type: range 
possible_keys: email_verified   
key: email_verified 
key_len: 2      
ref:
rows: 345195    
Extra: Using where; Using filesort

И профиль запроса:

Status  Duration
(initialization)    0.0000307
Opening tables  0.000003
System lock 0.0000017
Table lock  0.0000042
init    0.000017
optimizing  0.0000077
statistics  0.000097
preparing   0.000054
executing   0.0000007
Sorting result  1.2321507
Sending data    0.000272
end 0.000004
query end   0.0000025
freeing items   0.0000099
closing tables  0.0000025
logging slow query  0.0000005