Desafortunadamente, es un dolor de cabeza notorio hacer esto en MySQL.
Consulte ¿Puede MySQL reemplazar varios caracteres?
Prueba esto:
ORDER BY replace(replace(phrase,'¿',''),'¡','')
para eliminar la puntuación del prefijo en español de sus frases a medida que se ordenan. Uno desearía que MySQL tuviera una función REGEXP_REPLACE.
En cuanto al rendimiento, debería estar bien con las funciones ORDER BY a menos que tenga millones de frases. Docenas, no hay problema.
