ORDER BY po kolumnie z indeksem długo działa Opcje

[TomASS]

Mam zapytanie

[SQL] pobierz, plaintext 
[/sql]
SELECT *    
		  FROM m_transporty_miejsca AS TM
		  LEFT JOIN m_transporty AS T ON (T.ID=TM.ID_transport)
		  LEFT JOIN m_magazyny AS M ON (M.ID=T.ID_magazyn)
		  LEFT JOIN m_przewoznicy AS Pr ON (Pr.ID=T.ID_przewoznik)
		  WHERE Miejsce='akt' AND DATE(T.DateRealizacji) >= '2016-11-26'  AND T.RodzajCiezarowki='plandeka24'  AND DATE(T.DateRealizacji) <= '2016-11-28'  AND 1 ORDER BY `Status` ASC LIMIT 0, 40
[sql]
[SQL] pobierz, plaintext 

Na kolumnie Status jest indeks. Status to CHAR(10).

Takie zapytanie wykonuje się 78sekund
Po usunięciu ORDER BY `Status` czas spada do 2-3sekund.

Co robić?
Indeks jest
Zmieniałem bazę danych z MySQL 5.0 na 5.6 i tak się porobiło :/
Explain pokazuje: