Jinak jak už zaznělo, funkci Max bys měl použít nad co nejmenším počtem záznamů, tedy je vhodná maximální předfiltrace, protože předpokládám, že "status=1" bude mít mnoho záznamů.

Jinak ještě, pokud záznamy přibývají výlučně na základě časového sledu, tak by nebylo od věci předomezit výběr pomocí SELECT TOP/LAST nad seřazeným id, řekněme 1000 řádek (záleží na tom, jak často se daný jev vyskytuje - toto není univerzální optimalizace!!). Zde pak přijde samozřejmě vhod index nad polem id.

edit: a jinak to vidím tak, že všechny key_id sis měl normalizovat do separátní tabulky, najoinovat a selektovat z ní, nikoli odkazem na celou velkou tabuli.