Por lo pronto, el uso de ORDER BY y GROUP BY es
por definición ineficiente en cualquier DMS, sea o no MySQL.
Pero además hay dos cosas: si haces una subconsulta sobre el mismo campo que ya identifica el mensaje, referido a otra tabla, se infiere que hay una relación entre ambas (especialmente si una se llama "mensajes" y la otra "destinatiarios".
En ese caso deberías estar usado un JOIN y no una subconsulta.
Si a esto le agregamos que todo mensaje
debería tener obligatoriamente un destinatario, entonces la consulta si o si debería ser INNER JOIN.
Así pues, por empezar la consulta debería andar por acá:
Código MySQL:
Ver originalFROM `mensajes` M
INNER JOIN `destinatarios` D
ON M.mensajeID
= D.mensajeID
M.fromID='".$_SESSION['MyID']."'
AND D.ToID
=".$_SESSION[MyID]."
Respecto al ordenamiento, el único modo de mejorarlo es creando un indice sobre el campo o campos invocados en el ORDER BY.
Hay, sí, un error severo: NO debes utilizar nombres como "datetime" para las columnas, porque son
palabras reservadas. Las palabras reservadas pueden generar errores sintácticos indetectables, desde el momento en que son parte del SQL (en ese cso es un tipo de dato).
Otra cosa que se infiere es que podría existir un error de diseño de la base, que también conspira contra la performance, desde que si existe un mensaje, el destinatario debe ser un atributo del mensaje (el destinatario
es del mensaje emitido, como también el remitente), y el destinatario debería ser un usuario, o un contacto del usuario.
En ese contexto hay dos tres posibilidades:
1) Si es un usuario del sistema, tanto el ID del destinatario como del remitente apuntan a la misma tabla (2 FK distintas a la misma tabla), pero requiere una tabla Mensajes_Destinatarios con dos campos (es tabla relacional).
2) Es un contacto no perteneciente al sistema sino al usuario. Requiere de una tabla de Contactos, una tabla Mensajes_Destinatarios y otra de Mensajes_Contactos.
Tengo la impresión de que a tu sistema le esta faltando algo... o no quedan clara las relaciones, y eso afectará la performance de todas las consultas.