Slow query - Using where; Using temporary; Using filesort


I have some queries taking ~3-5 seconds to execute. With lots of queries being run all the time, it can take down the database.

The query in question is

SELECT partid, rtp.tableid, chainCount, type, charset, minLetters, maxLetters, index, chainLength, rtp.tableid, salt, CONVERT_TZ(DATE_ADD(NOW(), INTERVAL +2 DAY), @@global.time_zone, ‘+0:00’) AS expiration
FROM rainbowcrack_parts rtp
INNER JOIN rainbowcrack_tables rtt ON rtp.tableid = rtt.tableid AND rtp.status = 0
INNER JOIN rainbowcrack_tablesets rts ON rtt.tablesetid = rts.tablesetid
WHERE type != ‘lm’
ORDER BY rts.priority DESC, rtp.partid ASC LIMIT 1;

The table structure is the following:
CREATE TABLE rainbowcrack_parts (
partid int(11) NOT NULL auto_increment,
tableid int(11) NOT NULL,
userid int(11) default NULL,
chainStart int(11) NOT NULL,
chainCount int(11) NOT NULL,
ip varchar(255) default NULL,
status int(11) default NULL,
starttime datetime default ‘0000-00-00 00:00:00’,
finishedtime datetime default ‘0000-00-00 00:00:00’,
clientid int(10) unsigned NOT NULL default ‘0’,
creditvalue float unsigned NOT NULL default ‘0’,
PRIMARY KEY (partid),
KEY tableid (tableid),
KEY userid (userid),
KEY creditvalue (creditvalue),
KEY finishedtime (finishedtime),
KEY status (status)

and result of EXPLAIN is:

1 SIMPLE rtp ref tableid,status status 5 const 41886 Using where; Using temporary; Using filesort
1 SIMPLE rtt eq_ref PRIMARY,tablesetid,type PRIMARY 4 rainbowtables-distrrtgen.rtp.tableid 1 Using where
1 SIMPLE rts eq_ref PRIMARY PRIMARY 4 rainbowtables-distrrtgen.rtt.tablesetid 1

The table contains 668.000 rows

I have added indexes, but still gets “using temporary; Using filesort”… Any ideas?