Optimizacija upita sa ORDER BY nad velikom tabelom

Imam 2 tabele (mysql_4.0) : items sa oko 500000 rekorda, i translacionu tabelu za items (lang_id, item_id, lang_value) nad kojim vrsim klasican where. Cim stavim ORDER BY po bilo cemu, i po primarnom kljucu isto, izvrsenje upita se drasticno poveca. Sa < 1s na preko 10sec. Problem je naravno do mysql-a koji ne koristi indexe za order by. I sad me zanima da li neko zna bilo kakvo resenje da mogu da radim sort podataka direktno u bazi, a da resenje bude brzo

Alternativni pristup bi bio presorting (ukoliko se sadržaj tabele ne menja često, pa čak i ako se menja, ima i za to rešenje - ostavljaš "rupe" u order brojkama). Dakle nova indeksirana numerička kolona sa redosledom koji želiš, i onda order by po tome. Možeš da ih nanižeš 1,2,3,4... ili 10,20,30,40 da bi mogao kasnije da ubacuješ nove bez apdejta cele tabele.