Zdravím, potřeboval bych optimalizovat SQL dotaz, ale nemám představu jak přesně...

Zadání: Potřebuji z tabulky níže vybrat řádky, které jsou nejnovější k hodnotě key_id, ale přitom daný řádek má status = 1

id	key_id	tstamp		status
----------------------------------
9	1	1412067222	1
8	2	1412067174	2
7	4	1412067126	2
6	4	1412067078	1
5	2	1412067030	2
4	3	1412066982	1
3	2	1412066934	1
2	1	1412066886	2
1	3	1412066838	1

Výstup by pak měl vypadat takto:

id	key_id	tstamp		status
----------------------------------
9	1	1412067222	1
4	3	1412066982	1

Současný dotaz vypadá takto:

SELECT * FROM tabulka as t 
WHERE t.tstamp >= (SELECT max(tstamp) FROM tabulka WHERE key_id	= t.key_id)
AND t.status=1

Jelikož mám v tabulce skoro 500 000 záznamů, tak tento dotaz trvá na mém serveru kolem 4 vteřin.
Děkuji za pomoc