Optimize this query, retrieve users from a MySQL db with 500.000 users and one conditional

Question

Suposse I have the next MySQL database with 500.000 rows:

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

primary { id }
index   { verified }

And I need to get last 20 not verified users, so I use the next query:

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

But it takes 1.2 seconds to complete.

How can I optimize it? Or get the same result with other way in php.

[EDIT]

ID is the primary index, VERIFIED is a index too

[EDIT 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;

[EDIT 3]

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

is

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

And a profile of the query:

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

Answer 1

You need an index that encompasses both id and email_verfied

KEY `foo` (`id`,`email_verified`)

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

+----+-------------+-------+-------+----------------+---------+---------+------+------+--------------------------+
| id | select_type | table | type  | possible_keys  | key     | key_len | ref  | rows | Extra                    |
+----+-------------+-------+-------+----------------+---------+---------+------+------+--------------------------+
|  1 | SIMPLE      | users | index | email_verified | Index 4 | 6       | NULL |    5 | Using where; Using index |
+----+-------------+-------+-------+----------------+---------+---------+------+------+--------------------------+

Especially the slow Using filesort is gone.

Answer 2

Add a new index: {verified, id}. otherwise you will have to do a full table scan.