15 млн для MySQL при грамотной схеме и запросах вообще ничто.
Впрочем
1. Памяти хорошо бы побольше (и это не зависит, MySQL или что-то более модное), и эту память нужно ещё правильно "отдать" (настроить конфиги) MySQL-ю.
2. Смотрите конкретный SQL-запрос.
Возможно, его имеет смысл разбить на несколько, без JOIN-ов (JOIN-ы часто хотят ооочень много памяти, а если её не хватает, тормозят жутко). Особенно при использовании сортировки. (Ваше "когда сортировку включаешь" косвенно указывает, что тут и есть проблема).