Оптимизация WHERE str LIKE 'a%' SORT BY LENGTH(str) LIMIT N?
like 'const%' может использовать индекс по полю.
если этот самый limit ограничивает выборку достаточно сильно, почему бы не сделать select… from (select… from… order by length(str) limit N) where str line '%a'