Прословута болка във врата е да се прави това в MySQL, за съжаление.
Вижте Може ли MySQL да замени няколко знака?
Опитайте това:
ORDER BY replace(replace(phrase,'¿',''),'¡','')
за да премахнете пунктуацията на префикса на испански език от вашите фрази, докато са сортирани. Човек би искал MySQL да има функция REGEXP_REPLACE.
Що се отнася до производителността, трябва да сте добре с функциите ORDER BY, освен ако нямате милиони фрази. Десетки, няма проблем.