Правильный подход к пагинации

Доброго времени суток, в каждом своем проекте строю пагинацию по новому, т.к. не нравится предыдущее решение, хочу получить дельный совет по правильному подходу к данному процессу.

Подход в к построению самой пагинации мне понятен, вопрос только в том как реализовать малыми нагрузками на БД?

Данные: - база данных, преимущественно mysql - обработчик данных php

Что делал в разных подходах:

1. Считал кол-во перед выводом данных и строил пагинацию, на понравилось из-за лишнего запроса.
2. Пробовал записывать данные в базе о кол-ве данных, не понравилось отсутствием гибкости.
3. Пробовал загонять всю таблицу в память и работать далее динамически, естественно не подходит из-за размера данных.
4. Сейчас преимущественно при построении запроса использую SELECT SQL_CALC_FOUND_ROWS ...., и после построения запроса выполняю еще один запрос SELECT FOUND_ROWS(); Это самое удобное решение на данные момент, но не нравится присутствие двух запросов.

ps Не нравится во всех этих подходах, что при предоставлению клиентам возможности сортировок, все слетает и приходится осуществлять повторные запросы. Кто как поборол это? Если не вы то остается разбирать чужие скрипты.