Пагинация очень больших наборов данных

У меня есть набор данных в MySQL, где использование limit уже является дорогостоящим запросом, и определение количества результатов также дорого. Таким образом, я бы не хотел делать еще один запрос, чтобы узнать количество результатов. Я не могу использовать MYSQL_CALC_FOUND_ROWS, потому что ограничение находится внутри подзапроса:

SELECT * FROM items,
(
  SELECT
    item_id
  FROM
    (etc)
  WHERE
    some.field=<parameter>
  AND (etc)
  GROUP BY (something)
  ORDER BY (something_else) DESC
  LIMIT 15
) subset
WHERE item.id=subset.item_id

Я мог бы оставить элементы соединения и отказаться от подзапроса, а затем иметь возможность использовать MYSQL_CALC_FOUND_ROWS, однако это очень, очень, медленно. Я перепробовал все оптимизации индекса, и давайте просто предположим, что об этом не может быть и речи.

Теперь это больше вопрос дизайна ... как разрешить пользователю просматривать эти данные, если я не знаю последнюю страницу? Я знаю только, зашли ли они слишком далеко (например: запрос не возвращает результатов).