Мне было бы интересно узнать, как вы выяснили, что проблема заключается в «предложении ORDER BY и отсутствии какого-либо индекса в таблице« a »». Я нахожу это немного подозрительным, потому что в таблице a есть индекс первичного ключа, как вы потом скажете.
Рассматривая природу запроса и то, что я могу догадаться о природе данных, я думаю, что этот запрос, как правило, даст относительно мало результатов по сравнению с размером используемых таблиц, и, таким образом, ORDER BY было бы очень дешево. Конечно, это всего лишь предположение.
Будет ли индекс вообще помогать, зависит от данных в таблице. Какие показатели будет использовать ваш оптимизатор запросов при выполнении запроса, зависит от множества различных факторов, одним из самых больших из которых является ожидаемое количество результатов, полученных в результате поиска.
Одна вещь, которая очень помогла бы, это если бы вы опубликовали результаты EXPLAINing вашего запроса.